Premier exemple: Calcul de π par la méthode d'Archimède.

Portrait d'imagination d'Archimède par Fetti (1620)
n désigne un entier quelconque.
Désignons par Sn le demi-périmètre du polygone régulier à n-côtés inscrit dans un cercle de rayon 1.
Désignons par Tn le demi-périmètre du polygone régulier à n-côtés exinscrit à ce même cercle.
On peut vérifier par un petit calcul de trigonométrie que:
Sn=nsin(π/n)
Tn=ntan(π/n)
On peut vérifier rapidement les relations de récurrence entre les deux suites:
T2n=
2SnTn
Sn+Tn
S2n=
√(SnT2n)
L'appliquette suivante montre la méthode d'Archimède pour le calcul de π.
Au début, n=4,S4=2√2, T4=4.
Appuyez sur le bouton 'Click!' pour doubler n.
Appuyez sur 'Restart' pour recommencer depuis le début.

Cliquez pour voir l'algorithme d'Archimède
Suivant:
Voici maintenant un programme Python qui calcule les termes des deux suites adjacentes S2n et T2n. La valeur de π se trouve donc à chaque étape entre les deux valeurs calculées.
Nous faisons 12 itérations successives à partir de n=4. Nous trouvons donc à la fin des polygones à 213=8192 côtés.

Voici le résultat de l'exécution. Nous avons à chaque étape mis en valeur les décimales exactes du calcul de π.
i= 0 n= 4 2.82842712475 4 1.17157287525
i= 1 n= 8 3.06146745892 3.31370849898 0.252241040064
i= 2 n= 16 3.12144515226 3.18259787807 0.0611527258165
i= 3 n= 32 3.13654849055 3.15172490743 0.0151764168833
i= 4 n= 64 3.14033115695 3.14411838525 0.00378722829115
i= 5 n= 128 3.14127725093 3.14222362994 0.000946379009684
i= 6 n= 256 3.14151380114 3.14175036917 0.000236568024666
i= 7 n= 512 3.14157294037 3.1416320807 5.91403360906e-05
i= 8 n= 1024 3.14158772528 3.14160251026 1.47849796495e-05
i= 9 n= 2048 3.14159142151 3.14159511775 3.69623838914e-06
i= 10 n= 4096 3.14159234557 3.14159326963 9.24059189611e-07
i= 11 n= 8192 3.14159257658 3.1415928076 2.31014772201e-07
0.215301194993
0.24243765329
0.248172369763
0.249546933263
0.24988697193
0.249971757874
0.249992940399
0.249998235161
0.249999558794
0.249999889706
0.249999972727
Dans un second temps nous listons les rapports des différences des incertitudes Tn-Sn. Il semble que ces rapports tendent vers la valeur 0.25, c'est à dire que toute nouvelle incertitude soit 4 fois plus petite que la précédente. Nous avons 6 décimales exactes après 11 itérations.

Second exemple: La méthode de Newton.

Portrait de Sir Isaac Newton
http://fr.wikipedia.org/wiki/Fichier:GodfreyKneller-IsaacNewton-1689.jpg
C'est une méthode d'approximation des racines d'équations du type f(x)=0, pour des fonctions satisfaisant à certaines conditions, concernant principalement leur dérivabilité. Nous n'exposerons ici cette méthode que sur un cas très particulier, la détermination de la racine de l'équation x²=2 sur l'intervalle [1,2]. La méthode de Newton conduit à la construction d'une suite récurrente donnée par: Voici un programme Python qui calcule les 8 premiers termes de cette suite.

Voici le résultat d'une exécution:
i= 0 : 1
i= 1 : 1.5
i= 2 : 1.4166666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667
i= 3 : 1.4142156862745098039215686274509803921568627450980392156862745098039215686274509803921568627450980392
i= 4 : 1.4142135623746899106262955788901349101165596221157440445849050192000543718353892683589900431576443402
i= 5 : 1.4142135623730950488016896235025302436149819257761974284982894986231958242289236217849418367358303566
i= 6 : 1.4142135623730950488016887242096980785696718753772340015610131331132652556303399785317871612507104752
i= 7 : 1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276416016

    √2=1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727
Nous remarquons cette fois que la convergence est plus rapide. L'erreur sur la limite n'évolue par de façon linéaire avec n comme dans l'exemple précédent, mais on peut prouver qu'il s'agit d'une convergence 'quadratique' c'est à dire que l'erreur varie de façon inversement proportionelle au carré du rang de n. D'où une convergence extrêmement rapide. Nous avons 11 décimales exactes après seulement 4 itérations (à comparer avec le cas précédent).

Troisième exemple: une convergence lente.

Reprenons maintenant l'exemple traité ici.Soit la suite récurrente définie par u0=1 et un=un-1+(-1)n/(n+1).
On constate que la limite se trouve dans tout intervalle ]u2n,u2n-1[ de longueur 1/(2n+1).
On constate cependant que la longueur de ces intervalles ne décroit pas dans un rapport donné parce que le rapport des longueurs de ces intervalles tend vers 1.
C'est ce que nous appelons un cas de 'convergence lente'.
Après 80000 itérations nous n'avons que 4 décimales exactes. Après 5000 nous en avions déjà 3.

Définitions

On suppose que la suite u=(un) tend vers la limite a.
On dit que la suite u converge 'linéairement' ou 'géométriquement' vers a, s'il existe un nombre k , 0<k<1 tel que:
lim
|un+1-a|
|un-a|
n→∞
=k
Le nombre k est appelé 'vitesse de convergence'
Si
lim
|un+1-a|
|un-a|
n→∞
=k
est vérifiée pour k = 0, alors la convergence de la suite est dite 'rapide'.
On dit que la suite (un) de limite a est 'convergente d'ordre q', s'il existe un nombre k , 0<k<1 tel que:
lim
|un+1-a|
|un-a|q
n→∞
=k
En particulier :
On parle de 'convergence lente' lorsqu'on a:
lim
|un+1-a|
|un-a|
n→∞
=1

Propriétés

Tout d'abord il est possible qu'une suite converge et que la vitesse de convergence n'existe pas.
Prendre par exemple la suite définie par:
Cette suite converge vers 0.
Si n est impair un+1/un=2
Si n est pair un+1/un=1/2
Donc la limite de (un+1-0)/(un-0) n'existe pas.
On peut parfois déterminer la vitesse de convergence d'une suite, (sachant qu'elle existe) en utilisant le résultat suivant:
Supposons que
lim
un+1-a
un-a
n→∞
=k
existe avec k &isin ]-1,0[ ∪ ]0,1[
Ce qui entraîne en particulier que u converge avec la vitesse |k|.
Dans ces conditions, s'il existe un entier N≥1 tel que un+1≠un si n≥N, on a également:
lim
un+1-un
un-un-1
n→∞
=k
Tout repose sur la formule:
un+1-un
un-un-1
=
un-a
un-1-a
×
1-
un+1-a
un-a
1-
un-a
un-1-a
Il suffit de faire tendre n vers +∞ dans le membre de droite et d'appliquer les résultats concernant les limites et les opérations algébriques.
Mais attention!
Il se peut que la suite possède une vitesse de convergence sans que la limite de:
un+1-un
un-un-1
existe.
Voici un exemple:
Soit u la suite définie par: Cette suite converge clairement vers 0 avec la vitesse k si 0<k<1
Mais on a:
u2p+1-u2p
u2p-u2p-1
=
k(1-k)
k+1
et aussi:
u2p+2-u2p+1
u2p+1-u2p
=
k(k+1)
1-k
Ce qui prouve que
un+1-un
un-un-1
n'est pas convergente.
Cependant nous disposons de la condition suffisante suivante, connue sous le nom de 'test de d'Alembert':
Si pour n suffisamment grand un ≠ un-1 et:
lim
un+1-un
un-un-1
n→∞
=k
où k est un réel vérifiant -1<k<1.
Alors (un) converge vers une limite finie a:

Montrons d'abord la convergence de la suite.
Choisissons ε de façon que |k|+ε = k1 <1
Il existe alors un entier N tel que:
n>N⇒
|
un+1-un
un-un-1
|
≤k1
De là nous tirons par multiplication:
|
un+1-un
uN+1-uN
|
≤
n-N
k1
puis |un+1-un| ≤ k1n-N|uN+1-uN|
Posant K = |uN+1-uN|, nous obtenons si p>q >N:

|up-uq| ≤ |up-up-1|+|up-1-up-2|+ ... +|uq+1-uq|
|up-uq| ≤ Kk1p-N+ ... +Kk1q-N
|up-uq| ≤Kk1q-N(1+k1+ ... +k1p-q)
|up-uq|≤
Kk1q-N
(
1-k1p-q+1
1-k1
)
Et comme k1 < 1
|up-uq|≤
Kk1q-N
(
1
1-k1
)
Soit en posant H=K/(1-k1)
|up-uq| ≤ Hk1q-N
Et à nouveau en invoquant le fait que k1 <1 on voit que (un) est une suite de Cauchy. Elle est donc convergente.
Nous allons maintenant distinguer 3 cas:
  1. Le cas où 0<k<1
    2. Choisissons ε < inf(1-k,k) et posons k1=k-ε et k2=k+ε
    Il existe donc un entier N tel que si n>N on a:
    0 <k1 < qn < k2<1
    où:
    qn=
    un+2-un+1
    un+1-un
    On en déduit par multiplication que:
    (k1)p ≤ qnqn+1qn+2 ...qn+p-1 ≤ (k2)p ∀ p ≥1
    Par sommation on en déduit que si n > N et p ≥ 1, on a:
    1+k1+k12+ ...+k1p≤
    un+p+1-un
    un+1-un
    		≤1+k2+k22+ ... +k2p
    En laissant n fixe et en faisant tendre p vers +∞ on obtient:
    1
    1-k1
    		≤
    a-un
    un+1-un
    		≤
    1
    1-k2
    d'où on déduit:
    1-k1≥
    un+1-un
    a-un
    		≥1-k2
    puis pour tout n >N
    k1≤
    un+1-a
    un-a
    		≤k2
    Comme k1 et k2 peuvent être choisis aussi près qu'on veut de k on en déduit:
    lim
    un+1-a
    un-a
    n→∞
    		=k
    CQFD
  2. Le cas où -1<k<0
    3. Nous conservons la méthode et les notations du cas précédent.
    Soient donc k1 et k2 tels que -1 <k1<k<k2<0
    Comme précédemment, à partir d'un certain rang N, nous avons k1<qn<k2<0 Par produit nous aurons: Par sommation, il vient alors si n>N et si p est impair
    1+k1+k22+k13+ ...+k2p-1+k1p≤
    un+p+1-un
    un+1-un
    		≤1+k2+k12+k23+ ... +k1p-1+k2p
    On obtient donc en laissant fixe n et en faisant tendre p vers +∞
    1+
    k1
    1-k12
    		+
    k22
    1-k22
    		≤
    a-un
    un+1-un
    		≤
    1+
    k2
    1-k22
    		+
    k12
    1-k12
    Or k1 et k2 peuvent être choisis aussi près de k qu'on le désire. Mais alors les 2 expressions qui encadrent le quotient
    a-un
    un+1-un
    Sont aussi près de 1/(1-k) qu'on le désire.
    Il en résulte que:
    lim
    a-un
    un+1-un
    n→∞
    		=1/(1-k)
    Donc que:
    lim
    un+1-a
    un-a
    n→∞
    		=k
  3. Le cas k=0 Soit ε un réel donné vérifiant 0<ε<1
    Il existe donc un entier N tel que pour n>N on ait: |qn|<ε
    On a donc pour n>N et tout entier p:
    |
    un+p+1-un+p
    un+1-un
    		|
    		≤
    p
    ε
    En sommant à partir de p=1, il vient:
    |
    un+p+1-un+1
    un+1-un
    		|
    		≤ε+ ... +εp
    En faisant tendre p vers +∞ on en déduit:
    |
    a-un+1
    un+1-un
    		|
    		≤ε/(1-ε)
    Et donc, comme ε est arbitrairement petit:
    lim
    |
    a-un+1
    un+1-un
    		|
    n→∞
    		=0+
    Nous obtenons donc par inversion:
    lim
    |
    un-a
    un+1-a
    		 -  1
    		|
    n→∞
    		=+∞
    D'où nous tirons:
    lim
    |
    un-a
    un+1-a
    		|
    n→∞
    		=+∞
    et par une nouvelle inversion:
    lim
    |
    un+1-a
    un-a
    		|
    n→∞
    		=0+