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 π.
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.
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:
u0=1
un+1=un+(2-un2)/(2un)
Voici un programme Python qui calcule les 8 premiers termes de cette suite.
Voici le résultat d'une exécution:
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 :
la convergence d'ordre 2 est dite 'quadratique'.
la convergence d'ordre 3 est dite 'cubique'.
la convergence d'ordre 4 est dite 'quartique'.
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:
u2n=1/n
u2n+1=2/n
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:
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:
Le cas où 0<k<1
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
Le cas où -1<k<0
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:
si p est impair
k1p
≤
un+p+1-un+p
un+1-up
≤
k2p
si p est pair
k2p
≤
un+p+1-un+p
un+1-up
≤
k1p
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
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: