NUMÉRIQUE ANALYSE

Accélérations de convergence

Problématique

On suppose donnée une forme linéaire continue L sur un espace vectoriel normé de fonctions E et un processus linéaire d'interpolation (L_n) de L. Pour tout élément f de E, la suite numérique a_n = L_n(f ) converge ou non vers a = L(f ) ; il peut arriver que la suite (a_n) diverge, ou encore qu'elle converge vers a, mais trop lentement pour être utilisable en analyse numérique.

Voici deux exemples très élémentaires mais fondamentaux d'une telle situation.

Sommes de séries. Ici E est l'espace vectoriel l¹(C) des suites sommables muni de la norme N₁. L'application qui à u = (u_p) associe

est une forme linéaire continue qu'on approche par les sommes partielles S_n(u) = s_n ; ici le processus d'approximation est stable, puisque ∥S_n∥ = 1. La qualité de l'approximation de S(u) est mesurée par le reste r_n = (S − S_n)(u).

L'exemple classique des séries de Riemann

montre que la convergence peut être lente puisque alors :

lorsque α = 2, il faudrait prendre 10¹⁰ termes pour obtenir la précision 10⁻¹⁰.

Dans d'autres cas, les sommes partielles divergent vers + ∞ mais, par un développement asymptotique, on se ramène à l'étude d'une suite convergente. L'exemple de la série harmonique :

est frappant :

on cherche alors à approcher la constante d'Euler :

Intégrales. Ici E = C([a, b]) est l'espace vectoriel des fonctions continues sur[a, b]à valeurs complexes muni de la norme N_∞. L'application qui à un élément f associe :

est une forme linéaire continue qu'on peut approcher par un processus interpolatoire (I_n). Dans la méthode des rectangles, ou des trapèzes, on a ∥I_n∥ = 1, et le processus est donc stable, mais la rapidité de convergence est médiocre, de l'ordre de 1/n pour les rectangles et de 1/n² pour les trapèzes.

Pour améliorer la performance, on peut soit changer complètement d'algorithme d'approximation – pour les intégrales, on peut, par exemple, recourir à des méthodes gaussiennes –, soit garder le même algorithme de base (L_n) mais améliorer sa rapidité de convergence par des transformations purement algébriques portant sur la suite (L_n(f )) ; on dit alors qu'on effectue une accélération de convergence. Dans la suite, nous décrirons deux exemples significatifs de telles méthodes d'accélération : la première, de portée très générale, s'appelle méthode d'extrapolation à la limite ; elle utilise des barycentrations. La seconde, due à Euler, s'applique aux séries alternées et, plus généralement, aux séries trigonométriques.

Méthode d'extrapolation à la limite

La méthode d'extrapolation à la limite consiste à utiliser une évaluation asymptotique de la différence L_n(f ) − L(f ). Pour des commodités d'écriture, on utilisera pour les suites la notation fonctionnelle a(n) = L_n(f ) et a = L(f ).

Principe

Plaçons-nous d'abord dans l'hypothèse simple où l'on a établi que :

avec |k′| < |k| < 1 et λ ∈ C.

Trois cas peuvent se présenter :

I. On connaît explicitement k et λ. Pour accélérer la convergence, il suffit évidemment de corriger la suite (a(n)) en posant :

II. On connaît explicitement le nombre k mais pas le coefficient λ. On effectue alors une barycentration de a(n) et a(n + 1) de manière à éliminer le terme inconnu λkⁿ ; on écrit :

d'où :

ce qui conduit à poser :

dans ces conditions, on a

III. On connaît seulement l'existence de k et λ sans connaître leur valeur explicite. On se ramène alors au cas (II) en remplaçant k par une valeur approchée ; on observe que :

On pose alors :

dans ces conditions,

Cette méthode s'applique aussi au cas où l'on a établi que :

où O < α < α′, en introduisant la suite [...]

La suite de cet article est accessible aux abonnés

Des contenus variés, complets et fiables
Accessible sur tous les écrans
Pas de publicité

Découvrez nos offres

Déjà abonné ? Se connecter

Écrit par

Jean-Louis OVAERT : agrégé de l'Université, ancien élève de l'École normale supérieure, professeur de mathématiques spéciales
Jean-Luc VERLEY : maître de conférences honoraire à l'université de Paris-VII

Carte mentale
Élargissez votre recherche dans Universalis

Classification

Autres références

ALGORITHME
- Écrit par Thomas SEILLER et Alberto NAIBO
- 5 919 mots
- 3 médias
...donné par ce qu’on appelle les algorithmes de recherche d’un zéro d’une fonction, c’est-à-dire d’une valeur de x telle que f(x) = 0, dans le cadre de l’analyse numérique telle que l’algorithme de la méthode de calcul de Newton (qui permet par exemple de calculer une approximation de la valeur ...
ALGORITHMIQUE
- Écrit par Philippe COLLARD et Philippe FLAJOLET
- 6 652 mots
- 3 médias
.... Une erreur relative, même faible, sur u_n entraîne donc une erreur beaucoup plus importante sur u₂_n. De tels phénomènes sont courants en analyse numérique. On obtient des formules qui ne présentent pas ce caractère de difficulté en multipliant le radical :
par sa quantité conjuguée. Il vient,...
DÉRIVÉES PARTIELLES (ÉQUATIONS AUX) - Analyse numérique
- Écrit par Claude BARDOS et Martin ZERNER
- 5 849 mots
- 7 médias
Plus peut-être que tout autre domaine des mathématiques, les équations aux dérivés partielles étaient prédisposées à bénéficier de l'utilisation des ordinateurs, pour de nombreuses raisons. La plus importante est leur intervention dans de nombreux problèmes techniques. C'est d'ailleurs...
DIFFÉRENTIELLES ÉQUATIONS
- Écrit par Christian COATMELEC , Encyclopædia Universalis et Maurice ROSEAU
- 11 635 mots
...problème discrétisé associé à P₁. On remarque alors immédiatement qu'une notion importante va devoir être précisée : comment dire que la solution de P_n converge vers celle de P₁ lorsque n tend vers + ∞. L'analysenumérique devra fournir des majorations pour |y(x_i) − y_i|.
Afficher les 10 références