Evaluation de Ai(x) : cancellation catastrophique et comment y échapper

English

Séminaire Modèles et Algorithmes Déterministes: CASYS

5/04/2013 - 11:00 Mr Marc Mezzarobba (INRIA - LIP - ENS Lyon) Petit Amphi de l'INRIA Rhône-Alpes, Montbonnot

Le développement de Taylor à l'origine de la fonction d'Airy Ai converge 
sur tout le plan complexe, mais sa sommation numérique pour x>0 est un 
problème extrêmement mal conditionné. En effet, les coefficients non 
nuls sont de signe alterné et se compensent presque, de sorte que, 
lorsque l'on calcule la somme à précision finie pour x modérément grand, 
toute l'information significative est perdue dans les erreurs d'arrondi. 
Ce phénomène appelé cancellation catastrophique est fréquent dans 
l'évaluation des développements de Taylor de fonctions entières 
usuelles.

Dans cet exposé, je présenterai une méthode due à Gawronski, Müller et 
Reinhard [1, 2] qui, à partir d'une étude asymptotique d'une série 
entière y(z), aide à trouver deux fonctions auxiliaires F et G bien 
conditionnées vis-à-vis de la sommation et telles que y(z)=G(z)/F(z). Je 
montrerai comment une petite extension de cette méthode la rend 
applicable au cas de Ai. J'expliquerai ensuite comment l'on construit à 
partir de la formule obtenue un algorithme garanti d'évaluation en 
virgule flottante à précision arbitraire dans lequel la précision de 
travail reste toujours du même ordre de grandeur que la précision cible. 
L'algorithme fait appel à la méthode de récurrence arrière de Miller 
pour le calcul des coefficients de la série G(z), et son analyse (pour 
borner les erreurs commises) fait appel notamment à l'encadrement des 
coefficients de G(z) par la méthode du col.

Il s'agit d'un travail en commun avec Sylvain Chevillard (APICS, Inria).


Références :

[1] W. Gawronski, J. Müller, and M. Reinhard, Reduced cancellation in
the evaluation of entire functions and applications to the error 
function, SIAM Journal on Numerical Analysis 45 (2007), no. 6, 2564–
2576.

[2] M. Reinhard, Reduced cancellation in the evaluation of entire 
functions and applications to certain special functions, Ph.D. thesis, 
Universität
Trier, 2008.

[3] S. Chevillard and Marc Mezzarobba, Multiple-precision evaluation of 
the Airy Ai function with reduced cancellation, 21st IEEE Symposium on 
Computer Arithmetic, Austin, TX, US, 2013 (to appear).