La plupart des suites convergent vers des constantes mathématiques (π,e, √2,etc..), où des fractions de ces constantes, et on est tenté de les utiliser pour calculer ces constantes avec une précision de plus en plus grande.
La précision obtenue dépend bien entendu en premier lieu de la vitesse de convergence de la suite. Mais elle dépend également d'autres facteurs comme la difficulté de calculer le terme de rang n de la suite, nécessitant parfois n iétérations comme dans le cas de la suite d'Euler (1+1/n)n que nous avons déjà rencontrée plusieurs fois. Ou bien la précision du type numérique utilisé pour les calculs (float, double, etc...).
Nous nous préoccupons ici des améliorations que l'on peut obtenir en augmentant la vitesse de convergence d'une suite initiale par des procédés relativement simples (transformations linéaires).
Les conditions d'applications de ces procédés sont assez restrictives, elles supposent parfaitement connu le mode de convergence de la suite initiale.

Comparaison des vitesses de convergence

Soient (un= et (vn) deux suites convergeant toutes deux vers la même limite a.
On suppose en outre que pour n suffisamment grand on a toujours un≠a.
Dans ces conditions on dit que la suite (vn) converge vers a 'plus rapidement' que la suite (un) ssi:
lim
vn-a

un-a
n→∞
=0

Exemple:

Un des procédés pour accélérer la convergence d'une suite est l'extraction. Prenons par exemple la suite d'Euler un=(1+1/n)n dont la convergence est manifestement lente. Si nous posons vn=u2n, on vérifie immédiatement qu'on obtient une suite dont la convergence est géométrique de vitesse 1/2. Cependant cette accélération est purement factice, tout à fait illusoire, puisque le coût du calcul du terme de rang n de la suite d'Euler est en O(n) (produit de n facteurs) donc le coût du calcul de vn est en O(2n). Il faut donc se tourner vers des procédés qui augmente la vitesse de convergence 'à coût constant'.
Le point de départ de notre développement est le résultat suivant.
Si la suite un converge vers la limite a avec:
lim
un+1-a

un-a
n→∞
=k
où k vérifie 0<k<1.
Alors la suite (vn) définie par:
vn=
un+1-kun

1-k
converge également vers a plus rapidement que u.
Il suffit pour le voir de faire tendre n vers ∞ dans le membre de droite de la formule:
vn-a

un-a
=
1

1-k
×
un+1-a

un-a
 - 
k

1-k

La méthode de Richardson-Romberg

Lewis Fry Richardson(1909-2003) UK Werner Romberg (1880-1953) DE
Image Wikipédia Image HNMI(USA)
La méthode dite de 'Richardson' ou de 'Romberg' résulte de l'application de la remarque précédente au cas de suites convergeant géométriquement.
Plus précisément:
Soit (un) une suite dont le terme général est de la forme:
un=a+λkn+O(hn) où on a |h|<|k|<1.
Posons:
vn=
un+1-kun

1-k
Alors vn-a=O(hn)
La preuve est immédiate.
Posons wn=un-a-λkn de sorte que wn=O(hn).
Alors
vn-a=
wn+1-kwn

1-k
|vn-a|
|wn+1|+|k||wn|

1-k
A(|h|+|k|)

1-k
×|h|n
M|h|n
Voici un programme qui applique le procédé de Richardson Romberg à la suite d'Archimède:
un=2nsin(π/2n)
Nous prendrons pour acquis que la suite converge géométriquement avec la vitesse 1/4, chose que nous n'avons fait que vérifier empiriquement (une démonstration rigoureuse est fondée sur le développement en série entière de la fonction sinus). Nous admettrons également que l'accélérée de Richardson de cette suite converge avec la vitesse 1/16. Nous avons ici enchainé deux processus d'accélération. Nous verrons par la suite qu'il existe un moyen d'itérer ces procédés sans connaître les vitesses de convergence.

Et voici le résultat de l'exécution:
0.313165528844 0.00244508327756 2.2604598553e-06
0.0801251946691 0.000154936885962 3.56186848904e-08
0.0201475013317 9.71694788943e-06 5.57736523632e-10
0.00504416304385 6.0783212108e-07 8.73523475775e-12
0.00126149663505 3.79976969889e-08 3.50386386572e-13
0.000315402657036 2.37518449353e-09 -1.19237952845e-12
7.88524456476e-05 1.4733103626e-10 -3.62820884448e-12

La méthode d'Aitken

Alexander Aitken (1895-1967) NZ
Image: http://www.maths.otago.ac.nz
La méthode d'Aitken est fondée sur ce qui précède, conjointement avec le résultat rappelé ici.
Posons donc :
vn=
un+1-knun

1-kn
kn=
un+1-un

un-un-1
On a donc:
lim
vn-a

un-a
n→∞
=
lim
1

1-kn
(
un+1-a

un-a
 -  kn
)
n→∞
=0
On peut également exprimer vn de la manière suivante:
vn=
un-1 - 
(un-un-1)2

un+1-2un+un-1
ou bien encore:
vn=
un-1 - 
(Δun)2

Δ2un

Δun=un+1-un
et
Δ2un=un+2-2un+1+un
Voici un programme qui applique le procédé d'Aitken pour le calcul de π par la méthode d'Archimède avec 2 itérations successives.
L'avantage de cette méthode réside évidemment dans le fait qu'on n'a pas besoin de connaître les vitesses de convergence, aussi bien pour la suite initiale que pour les suites accélérées quand on itère le processus.

Résultat de l'exécution:
0.0201475013317 -3.91596509708e-05 -3.98591541995e-08
0.00504416304385 -2.43586940085e-06 -6.1611027391e-10
0.00126149663505 -1.52061584213e-07 -9.30322485715e-12
0.000315402657036 -9.50077438944e-09 -1.9433343823e-12