En première année de prépa ECG, l’étude des suites se restreint d’abord à la question : « La suite converge-t-elle ? » Pourtant, comme tu l’a vu ou le verra par la suite, la vitesse de convergence de la suite vers sa limite est une autre problématique importante lors de l’étude de cette dernière. En pratique, certaines suites ont une convergence lente et on aimerait bien qu’elles convergent plus rapidement vers leur limite. Le procédé consiste à remplacer une suite \(u_n\) par une autre suite \(v_n\) convergeant vers la même limite, mais plus rapidement. On appelle ça l’accélération de convergence. Nous étudierons donc dans un premier temps une typologie des vitesses de convergence, avant de voir une première méthode (dite de Richardson), puis celle d’Aitken. Nous conclurons cet article sur un exemple d’application de ces méthodes.
NB : Cet article a comme prérequis la notion d’équivalences et de négligeabilités des suites. Voici un article qui évoque la question si tu ne te sens pas au clair sur les enjeux.
Comparaison des vitesses de convergence
Soit \(u_n\) une suite convergeant vers une limite \(\ell\). On cherche à quantifier la vitesse à laquelle l’erreur \(e_n = |u_n – \ell|\) tend vers 0. Nous allons ici analyser trois vitesses de convergence classiques et donner des exemples de suite qui convergent à cette vitesse.
Convergence linéaire
On dit que la convergence est linéaire s’il existe \(c \in ]0, 1[\) tel que \(|u_{n+1} – \ell| \sim c |u_n – \ell|\).
Exemple : \(u_n = (\frac{1}{2})^n\). Ici \(\ell = 0\).
Démonstration
\[\frac{|u_{n+1} – 0|}{|u_n – 0|} = \frac{1/2^{n+1}}{1/2^n} = \frac{1}{2}\]
La limite est \(c = 1/2 < 1\). Chaque terme divise l’erreur par 2 : c’est logique, le terme suivant est égal au terme précédent divisé par deux.
Convergence logarithmique
On dit que la convergence est logarithmique si :
\[\lim \limits_{n \to +\infty} {\frac{|u_{n+1} – \ell|}{|u_n – \ell|}} = 1\]
Exemple : \(u_n = \frac{1}{n}\). Ici \(\ell = 0\).
Démonstration
\[\lim \limits_{n \to +\infty} \frac{u_{n+1}}{u_n} = \lim \limits_{n \to +\infty}\frac{n}{n+1} = \lim \limits_{n \to +\infty}1 – \frac{1}{n+1} = 1\]
C’est une convergence très lente en calcul numérique, puisque plus les \(n\) sont grands, plus la convergence se fait de plus en plus lentement. Concrètement avec notre exemple, passer de \(u_1\) à \(u_2\) nous rapproche plus de la limite que passer de \(u_{100}\) à \(u_{101}\) (\(u_2 – u_1 > u_{101} – u_{100}\)).
Convergence quadratique
On parle de convergence quadratique lorsque l’erreur est au carré d’une étape à l’autre :
\[|u_{n+1} – \ell| \sim C |u_n – \ell|^2\]
Exemple : la suite de Newton pour \(\sqrt{2}\) (il s’agit d’une célèbre suite qui converge ici vers \(\sqrt{2}\)) : \(u_{n+1} = \frac{1}{2}(u_n + \frac{2}{u_n})\) avec \(u_0 = 2\).
Démonstration
Un développement de Taylor que nous admettrons ici permet de montrer que l’on a :
\[u_{n+1} – \sqrt{2} \sim \frac{1}{2\sqrt{2}}(u_n – \sqrt{2})^2\]
Concrètement, le nombre de décimales exactes double à chaque itération, donc on obtient une suite qui converge rapidement vers sa limite. C’est donc une situation préférable.
Cette typologie étant désormais acquise, étudions des méthodes qui permettent de construire des suites de même limite qui convergent plus rapidement que celle étudiée initialement.
La méthode de Richardson
Définition
On suppose que \(u_n = \ell + \frac{a}{n^k} + o(\frac{1}{n^k})\) avec \(a \neq 0\) inconnu.
L’accélérateur de Richardson est défini par la combinaison linéaire :
\[v_n = \frac{2^k u_{2n} – u_n}{2^k – 1}\]
Démonstration
Écrivons les développements de \(u_n\) et \(u_{2n}\) :
- \(u_n = \ell + \frac{a}{n^k} + o(\frac{1}{n^k})\)
- \(u_{2n} = \ell + \frac{a}{(2n)^k} + o(\frac{1}{n^k}) = \ell + \frac{a}{2^k n^k} + o(\frac{1}{n^k})\)
Multiplions l’équation (2) par \(2^k\) :
\[2^k u_{2n} = 2^k \ell + \frac{a}{n^k} + o(\frac{1}{n^k})\]
Soustrayons l’équation (1) :
\[2^k u_{2n} – u_n = (2^k \ell – \ell) + (\frac{a}{n^k} – \frac{a}{n^k}) + o(\frac{1}{n^k})\]
\[2^k u_{2n} – u_n = \ell(2^k – 1) + o(\frac{1}{n^k})\]
En divisant par \((2^k – 1)\), on obtient :
\[v_n = \ell + o(\frac{1}{n^k})\]
La suite \(v_n\) converge bien vers \(\ell\) plus vite que \(u_n\). En effet, si l’on compare le développement limité de \(u_n\) à celui de \(v_n\), on constate que celui de \(v_n\) fait disparaître le terme \(\frac{a}{n^k}\).
La méthode de Richardson suppose néanmoins que la suite étudiée initialement admette un développement limité bien précis. Cela restreint les cas d’utilisation de cette méthode.
La méthode d’Aitken
Définition
On suppose que \(u_n = \ell + a \cdot k^n + o(k^n)\) avec \(|k| < 1\).
L’accélérateur d’Aitken est défini (de manière plus complexe qu’avec la méthode de Richardson) par :
\[v_n = u_n – \frac{(u_{n+1} – u_n)^2}{u_{n+2} – 2u_{n+1} + u_n}\]
Démonstration
Cette démonstration complète est plus longue et présente un intérêt moindre, nous ne développerons ainsi que la preuve que \(v_n\) converge bien vers \(l\).
Comme la suite est supposée géométrique : \(u_n – \ell = a \cdot k^n\).
Alors \((u_{n+1} – \ell)^2 = (u_n – \ell)(u_{n+2} – \ell)\).
En développant :
\[u_{n+1}^2 – 2\ell u_{n+1} + \ell^2 = u_n u_{n+2} – \ell(u_n + u_{n+2}) + \ell^2\]
En simplifiant \(\ell^2\) et en isolant \(\ell\) :
\[\ell(u_n + u_{n+2} – 2u_{n+1}) = u_n u_{n+2} – u_{n+1}^2\]
D’où :
\[\ell = \frac{u_n u_{n+2} – u_{n+1}^2}{u_{n+2} – 2u_{n+1} + u_n}\]
En réarrangeant les termes, on montrerait que cette expression est égale à celle donnée dans la partie A.
Exemple
Énoncé
Soit \(u_n = \sum_{k=1}^n \frac{1}{k^2}\). On admet que l’on a \(u_n = \frac{\pi^2}{6} – \frac{1}{n} + O(\frac{1}{n^2})\).
Cette démonstration a d’ailleurs fait l’objet d’exercices de type EMLyon/EDHEC.
Déterminer une suite de même limite convergeant plus rapidement que \(u_n\).
Corrigé
Par identification du développement limité, on reconnaît qu’il convient d’utiliser la formule de Richardson. Ici \(k=1\). On pose :
\[v_n = 2u_{2n} – u_n\]
D’après la méthode de Richardson, cette suite converge en \(O(\frac{1}{n^2})\).
Conclusion
En définitive, afin d’accélérer la convergence de suites, tu disposes désormais de deux méthodes. Il convient donc de connaître la forme du développement limité de la suite afin de trouver la méthode à utiliser (Richardson ou Aitken). Il ne reste désormais plus qu’à croiser les doigts pour qu’une telle notion tombe aux concours !
Tu peux également retrouver ici le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux aussi accéder ici à toutes nos autres ressources mathématiques !
