Vitesse de convergence

En analyse numérique, la vitesse de convergence d'une suite représente la vitesse à laquelle les termes de la suite se rapprochent de sa limite. Bien que cet ordre de grandeur de vitesse de convergence ne fournisse pas d'information sur toute partie finie de l'ensemble des termes de la suite, ce concept a une grande importance pratique lorsque nous travaillons avec une suite d'approximations successives obtenue à partir d'une méthode itérative, car en général peu d'itérations sont nécessaires pour donner une valeur approchée intéressante lorsque la vitesse de convergence est grande.

Définition de la vitesse de convergence

Supposons que la suite (xk) converge vers le nombre ξ.

On dit que cette suite converge linéairement vers ξ, s'il existe μ ∈ ] 0 , 1 [ {\displaystyle \mu \in {}]0,1[} tel que

lim k → ∞ | x k + 1 − ξ | | x k − ξ | = μ ( 1 ) {\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-\xi |}{|x_{k}-\xi |}}=\mu \quad \quad (1)}

Le nombre μ est appelé vitesse de convergence.

Si (1) est vérifiée pour μ = 0, alors la convergence de la suite est dite super-linéaire. On dit aussi que la suite converge super-linéairement. Au contraire, on dit que la vitesse de convergence de la suite est sous-linéaire lorsque (1) n'est vérifiée pour aucun μ < 1.

La définition suivante sert à distinguer les différentes vitesses de convergence super-linéaires.

On dit que la suite de limite ξ est convergente d'ordre q pour q > 1 s'il existe μ > 0 {\displaystyle \mu >0} tel que

lim k → ∞ | x k + 1 − ξ | | x k − ξ | q = μ ( 2 ) {\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-\xi |}{|x_{k}-\xi |^{q}}}=\mu \quad \quad (2)}

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.
  • la convergence d'ordre 5 est dite quintique.

Commentaires

Dans la pratique, on espère rarement obtenir une convergence plus que quadratique, qui est déjà très satisfaisante. Une telle vitesse de convergence correspond à un doublement du nombre de chiffres précis à chaque étape, et donc typiquement une approximation de la limite à 30 décimales correctes après seulement 5 pas, si la valeur initiale est convenablement choisie. Un exemple célèbre de méthode qui converge quadratiquement est celui de la méthode de Newton.

Quelque résultat sur la vitesse de convergence

Vitesse de convergence vers un point fixe

On considère ϕ ∈ C 1 ( [ a , b ] , R ) {\displaystyle \phi \in C^{1}([a,b],\mathbb {R} )} . Si ϕ ( [ a , b ] ) ⊂ [ a , b ] {\displaystyle \phi ([a,b])\subset [a,b]} et | ϕ ′ | < 1 {\displaystyle |\phi '|<1} , alors d'après le théorème du point fixe de Banach, il vient que ϕ {\displaystyle \phi } admet un unique point fixe.


On peut aller plus loin et montrer que pour x ∗ ∈ ] a , b [ {\displaystyle x^{*}\in ]a,b[} vérifiant | ϕ ′ ( x ∗ ) | < 1 {\displaystyle |\phi '(x^{*})|<1} , on dispose d'un voisinage fermé V {\displaystyle V} de x ∗ {\displaystyle x^{*}} tel que ϕ {\displaystyle \phi } restreinte à V {\displaystyle V} soit contractante de point fixe x ∗ {\displaystyle x^{*}} .


On peut alors poser la suite des itérées ( x k ) k ≥ 0 {\displaystyle (x_{k})_{k\geq 0}} avec x 0 ∈ V {\displaystyle x_{0}\in V} et x k + 1 = ϕ ( x k ) {\displaystyle x_{k+1}=\phi (x_{k})} et discuter de la vitesse de convergence de cette suite en fonction de ϕ {\displaystyle \phi } . On sait qu'elle est au moins d'ordre 1 puisque l'on a | x k + 1 − x ∗ | ≤ sup t ∈ V ϕ ′ ( t ) | x k − x ∗ | {\displaystyle |x_{k+1}-x^{*}|\leq \sup _{t\in V}\phi '(t)|x_{k}-x^{*}|} . Mais on peut avoir un résultat plus général.

Théorème —  Ordre de convergence en fonction de ϕ {\displaystyle \phi }

On pose p > 1 {\displaystyle p>1} et ϕ ∈ C p ( [ a , b ] , R ) {\displaystyle \phi \in C^{p}([a,b],\mathbb {R} )} . Si pour tout 1 ≤ j ≤ p − 1 {\displaystyle 1\leq j\leq p-1} , on a

ϕ j ( x ∗ ) = 0 {\displaystyle \phi ^{j}(x^{*})=0}
ϕ p ( x ∗ ) ≠ 0 {\displaystyle \phi ^{p}(x^{*})\neq 0}

Alors il existe un voisinage fermé V {\displaystyle V} de x ∗ {\displaystyle x^{*}} tel que ϕ {\displaystyle \phi } restreinte à V {\displaystyle V} soit contractante de point fixe x ∗ {\displaystyle x^{*}} et la suite ( x k ) k ≥ 0 {\displaystyle (x_{k})_{k\geq 0}} définie plus haut est exactement d'ordre p {\displaystyle p} .


Démonstration

Comme on a | ϕ ′ ( x ∗ ) | = 0 < 1 {\displaystyle |\phi '(x^{*})|=0<1} , il y a seulement à démontrer que ( x k ) k ≥ 0 {\displaystyle (x_{k})_{k\geq 0}} est d'ordre p {\displaystyle p} .

Pour cela, on utilise la formule de Taylor qui donne l'existence d'un η k ∈ ( x k , x ∗ ) {\displaystyle \eta _{k}\in (x_{k},x^{*})} , tel qu'on est l'égalité

ϕ ( x k ) = ϕ ( x ∗ ) + ∑ j = 0 p − 1 ϕ ( j ) ( x ∗ ) j ! ( x k − x ∗ ) j + ϕ ( p ) ( η k ) p ! ( x k − x ∗ ) p {\displaystyle \phi (x_{k})=\phi (x^{*})+\sum _{j=0}^{p-1}{\frac {\phi ^{(j)}(x^{*})}{j!}}(x_{k}-x^{*})^{j}+{\frac {\phi ^{(p)}(\eta _{k})}{p!}}(x_{k}-x^{*})^{p}}

Par hypothèse, on en déduit

x k + 1 − x ∗ = ϕ ( p ) ( η k ) p ! ( x k − x ∗ ) p {\displaystyle x_{k+1}-x^{*}={\frac {\phi ^{(p)}(\eta _{k})}{p!}}(x_{k}-x^{*})^{p}}

Comme ( η k ) k ≥ 0 {\displaystyle (\eta _{k})_{k\geq 0}} est une suite encadrée par ( x k ) k ≥ 0 {\displaystyle (x_{k})_{k\geq 0}} et x ∗ {\displaystyle x^{*}} , on en déduit; tant ( x k ) k ≥ 0 {\displaystyle (x_{k})_{k\geq 0}} n'est pas stationnaire,

x k + 1 − x ∗ ∼ ϕ ( p ) ( x ∗ ) p ! ( x k − x ∗ ) p {\displaystyle x_{k+1}-x^{*}\thicksim {\frac {\phi ^{(p)}(x^{*})}{p!}}(x_{k}-x^{*})^{p}}

Ce qui conclut.

Articles connexes

  • icône décorative Portail de l'analyse