Analyse de convergence — Point fixe et Newton

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

• Appliquer le théorème de la moyenne pour analyser la convergence
• Démontrer l'ordre de convergence de la méthode du point fixe
• Démontrer l'ordre de convergence de la méthode de Newton
• Comprendre l'impact des racines multiples sur la convergence

Rappel : le théorème de la moyenne

Le théorème de la moyenne (aussi appelé théorème des accroissements finis) est un outil fondamental pour analyser la convergence.

Interprétation géométrique

Ce théorème dit qu'il existe au moins un point où la tangente à la courbe est parallèle à la sécante reliant les points et .

Forme utile pour notre analyse

On peut réécrire le théorème sous la forme :

Cette forme sera utilisée pour relier l'erreur à l'itération à l'erreur à l'itération .

Convergence de la méthode du point fixe

Rappel de la méthode

La méthode du point fixe transforme en et itère :

La racine est un point fixe : .

Analyse par le théorème de la moyenne

Calculons l'erreur :

En appliquant le théorème de la moyenne à entre et , il existe entre ces deux points tel que :

Donc :

Passage à la limite

Quand , on a , donc (car est entre et ).

Si :

En comparant avec la définition de l'ordre de convergence (avec ), on identifie :

Condition de convergence

Pour avoir convergence, il faut , donc :

Analyse par développement de Taylor

Le théorème de la moyenne nous dit que la convergence est linéaire quand . Mais que se passe-t-il si ?

Pour répondre, utilisons le développement de Taylor.

Développement de g(Xₙ)

On développe autour du point fixe :

Comme (point fixe) et :

En soustrayant des deux côtés :

Cas 1 : g'(r) ≠ 0 — Convergence linéaire

Si , le terme dominant est :

Quand , , donc :

Conclusion : Convergence linéaire avec .

Cas 2 : g'(r) = 0, g''(r) ≠ 0 — Convergence quadratique

Si , le développement devient :

Le terme dominant est maintenant :

Quand :

Conclusion : Convergence quadratique avec .

Cas 3 : g'(r) = g''(r) = 0, g'''(r) ≠ 0 — Convergence cubique

Si les deux premières dérivées s'annulent :

Conclusion : Convergence cubique avec .

Résumé pour le point fixe

Observation clé : Plus de dérivées s'annulent au point fixe, plus la convergence est rapide !

Convergence de la méthode de Newton

Newton comme méthode de point fixe

La méthode de Newton peut s'écrire comme une méthode de point fixe avec :

Pour déterminer l'ordre de convergence, nous devons calculer .

Calcul de G'(X)

En utilisant la règle du quotient :

Évaluation en X = r (racine simple)

Au point , on a . Donc :

Conclusion pour une racine simple

Puisque , d'après notre analyse du point fixe (cas 2), la méthode de Newton a une convergence quadratique !

C'est ce qui explique pourquoi Newton converge si rapidement : le nombre de décimales correctes double à chaque itération.

Racines multiples

Définition

Une racine est de multiplicité m si :

où .

Exemples :

• : racine simple () en
• : racine double () en
• : racine triple () en

Caractérisation par les dérivées

Pour une racine de multiplicité :

Impact sur Newton

Pour une racine de multiplicité , calculons .

Avec , les dérivées sont :

En évaluant en et en simplifiant (les puissances de se simplifient), on obtient :

Conséquence

Pour une racine de multiplicité :

• La convergence est linéaire avec

Modification de Newton pour les racines multiples

Si on connaît la multiplicité , on peut modifier la formule de Newton :

Cette modification restaure la convergence quadratique.

Résumé général

Points clés

1. Théorème de la moyenne : permet de relier à via

2. Point fixe : l'ordre de convergence dépend de combien de dérivées de s'annulent en

3. Newton = point fixe avec

4. Newton et racine simple : → convergence quadratique

5. Newton et racine multiple : → convergence linéaire

6. Condition de convergence : est une condition suffisante