Accélération de convergence (Aitken)

(Exercice d’oral Centrale Mp)
Soit {I} un intervalle réel d’intérieur non vide.

Soit {f:I\to I}, de classe {\mathcal{C}^{2}}, telle que {M=\sup\limits_{x\in I}\left|{f'(x)}\right|\lt 1}.

On suppose : {\exists\, \alpha\in I,\;f(\alpha)=\alpha} et {\rho=f'(\alpha)\ne0}.

On définit {(u_{n})_{n\ge0}} par {u_0\in I} et {\forall\, n\in\mathbb{N},\;u_{n+1}=f(u_n)}.

On pose : {\forall\, n\in\mathbb{N},\;e_{n}=u_{n}-\alpha,\;v_{n}=\rho^{-n}e_n}.

  1. Montrer que la série {\displaystyle\sum_{n\ge0}\left|{e_{n}}\right|} converge.

    En déduire : {\exists\, \lambda\in\mathbb{R},\;u_n=\alpha + \lambda \rho^n + \text{o}(\rho^n)}.

  2. Montrer qu’on a en fait un développement : {u_n=\alpha + \lambda \rho^n + \mu \rho^{2n} +\text{o}\big( \rho^{2n} \big)}
  3. Soit {D_{n}} la droite passant par {(u_{n-1},u_{n})} et {(u_n,u_{n+1})}.

    On suppose qu’elle est bien définie et non parallèle à {\Delta:(y=x)}.

    On note {x_n} l’abscisse du point d’intersection de {D_{n}} avec {\Delta}.

    Montrer que {(x_{n})_{n\ge0}} converge vers {\alpha}, et que {x_n - \alpha =\text{o}( u_n - \alpha)}.

Cliquer ici pour voir (ou cacher) le corrigé

    • Avec les accroissements finis : {| e_{n+1} | = | f(u_n) - f(\alpha) | \leq M |u_n - \alpha| = M |e_n|}Ainsi {|e_n| \leq M^n |e_0|}, avec {0\le M\lt 1}.

      La série {\displaystyle\sum_{n\ge0}\left|{e_{n}}\right|} est donc convergente.

    • S’il existe {n_0} tel que {u_{n_{0}}=\alpha}, alors {(u_{n})} stationne en {\alpha}.

      Dans ce cas {u_n=\alpha + \lambda \rho^n + \text{o}( \rho^n)}, avec {\lambda=0}.

      Dans la suite on suppose donc qu’on a toujours {u_{n}\ne \alpha} (donc {e_{n}\ne0}.

    • On applique la formule de Taylor-Young à {f} en {\alpha} à l’ordre {2} : {u_{n+1}=f(u_n)=f(\alpha)+f'(\alpha)e_n+ \dfrac {f''(\alpha)}2e_n^2 + \text{o}(e_n^2)}Ainsi : {e_{n+1}=\rho e_n + K e_n^2 + \text{o}( e_n^2)}, avec {K=\dfrac 12 f''(\alpha)}.

      Comme {\dfrac{v_{n+1}}{v_n}=\dfrac{e_{n+1}}{\rho e_n}}, et en notant {C=\dfrac{K}{\rho}}, on obtient : {\dfrac{v_{n+1}}{v_n} = 1 + C e_n +\text{o}(e_n)}À partir d’un certain rang, on peut donc écrire : {\ln \Big( \dfrac{v_{n+1}}{v_n} \Big) = \ln \Big( 1 + C e_n + o(e_n) \Bigr) \sim C e_n}Ainsi {\displaystyle\sum_{n\ge0}\big(\ln\left|{v_{n+1}}\right|-\ln\left|v_{n}\right|\bigr)} converge donc {\ln\left|v_{n}\right|} converge.

      Finalement, on peut écrire {v_n \to \lambda\in\mathbb{R}^{*}}.

      Ainsi {v_n = \lambda + \text{o}(1)} donc {e_{n}\sim \lambda\rho^{n}} donc {u_n = \alpha + \lambda \rho^n + \text{o}( \rho^n)}.

  1. On suppose qu’on a toujours {u_{n}\ne\alpha}, sinon il n’y a rien à démontrer.

    On sait que {\ln(v_{n+1})-\ln(v_n)=\ln \Big( \dfrac{v_{n+1}}{v_n} \Big) \sim C e_n\sim C\lambda \rho^n}.

    • Si {\rho>0}, ce sont des séries dont le terme général garde un signe fixe.

      Dans ces conditions, on sait que les restes sont équivalents (ça se redémontre).

      Ainsi, quand {n\to+\infty}, et en posant {A=\dfrac{C \lambda}{1-\rho}} : {\ln(\lambda)-\ln(v_n) \sim C \lambda \sum\limits_{k=n}^{+\infty} \rho^k = A \rho^n}Ainsi {\ln(v_n)=\ln(\lambda)-A \rho^n + \text{o}( \rho^n)} donc {v_n=\lambda(1-A \rho^n +\text{o}(\rho^n))}.

      Comme {u_n = \alpha + \rho^n v_n}, il vient : {u_n=\alpha + \lambda \rho^n + \mu \rho^{2n} + o \big( \rho^{2n} \big)\text{\ où\ }\mu=-\lambda A}

    • Enfin, si {\rho\lt 0}, pour ne pas sommer des équivalents de termes de signes non fixes, on passe par {v_{2n}} et {v_{2n+1}} (pour faire apparaître {\rho^2}) et on trouve le même résultat.
    • On détermine l’équation de la droite et on trouve : {x_n=\dfrac{u_{n+1}u_{n-1}-u_n^2}{u_{n+1}-2u_n+u_{n-1}}}
    • On note {\begin{cases}N_n = u_{n+1}u_{n-1}-u_n^2\\ D_n=u_{n+1}-2u_n+u_{n-1}\end{cases}}. On trouve : {D_n =\lambda \Big( \rho -2 + \dfrac{1}{\rho} \Big) \rho^{n}+ \mu \Big( \rho^2 - 2 + \dfrac{1}{\rho^2} \Big) \rho^{2n}+ o \Big( \rho^{2n} \Big)}De même : {\begin{array}{rl}N_n &= u_{n+1}u_{n-1}-u_n^2 \\\\&=\alpha \lambda \Big( \rho -2 + \dfrac{1}{\rho} \Big) \rho^{n}+ \alpha \mu \Big( \rho^2 - 2 + \dfrac{1}{\rho^2} \Big) \rho^{2n}+ o \Big( \rho^{2n} \Big)\end{array}}Posons {a=\lambda \Big( \rho -2 + \dfrac{1}{\rho} \Big) \neq 0} et {b=\mu \Big( \rho^2 - 2 + \dfrac{1}{\rho^2} \Big)}. On a alors : {x_n=\dfrac{N_n}{D_n}=\alpha \dfrac{a \rho^{n}+ b \rho^{2n}+ \text{o}\big( \rho^{2n} \big)}{a \rho^{n}+ b \rho^{2n}+ \text{o} \big( \rho^{2n} \big)}=\alpha \big( 1+ \text{o}(\rho^n) \big)}Comme {u_n - \alpha \sim \lambda \rho^n} (avec {\lambda \neq 0}), on voit que {x_n - \alpha =\text{o}( u_n - \alpha)}.