Critères d'arrêt, résumé et méthode de Muller

Objectifs d'apprentissage

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

Choisir des critères d'arrêt appropriés pour une méthode itérative
Comparer les méthodes selon leurs caractéristiques de convergence
Connaître l'existence de méthodes plus avancées comme Muller

Critères d'arrêt

Le problème

Toutes nos méthodes itératives génèrent une suite $\{X_n\}$ qui converge vers la racine $r$ . Mais en pratique, on ne peut pas itérer indéfiniment. Il faut décider quand s'arrêter.

Critère 1 : Tolérance sur la racine

On s'arrête quand deux approximations successives sont suffisamment proches :

|X_{n+1} - X_n| < \delta

où $\delta$ est la tolérance souhaitée sur la racine.

Interprétation : Si $X_{n+1}$ et $X_n$ sont très proches, on suppose que les deux sont proches de la vraie racine.

Avantage : Simple à calculer, ne nécessite pas d'évaluer $F$ .

Limitation : Pour une convergence lente, $X_{n+1} - X_n$ peut être petit alors que $X_n$ est encore loin de $r$ .

Critère 2 : Tolérance sur la fonction

On s'arrête quand la fonction est suffisamment proche de zéro :

|F(X_{n+1})| < \varepsilon

où $\varepsilon$ est la tolérance souhaitée sur la fonction.

Interprétation : Si $F(X_{n+1}) \approx 0$ , alors $X_{n+1}$ est proche d'une racine.

Avantage : Vérifie directement que l'on s'approche d'une solution.

Limitation : Si $F'(r)$ est très petit (pente faible), $F(X)$ peut être petit même si $X$ est loin de $r$ . Inversement, si $F'(r)$ est grand (pente forte), $F(X)$ peut être grand même si $X$ est proche de $r$ .

Critère 3 : Combinaison des deux

En pratique, on combine souvent les deux critères :

|X_{n+1} - X_n| < \delta \quad \text{ET} \quad |F(X_{n+1})| < \varepsilon

ou parfois avec un OU :

|X_{n+1} - X_n| < \delta \quad \text{OU} \quad |F(X_{n+1})| < \varepsilon

Critère de sécurité : nombre maximal d'itérations

On ajoute toujours une condition de sécurité pour éviter les boucles infinies :

n < n_{\max}

Si ce critère est atteint sans convergence, on signale un échec.

Résumé des critères

Critère	Formule	Vérifie
Tolérance sur X	$\|X_{n+1} - X_n\| < \delta$	Stabilité de la suite
Tolérance sur F	$\|F(X_{n+1})\| < \varepsilon$	Proximité d'une racine
Sécurité	$n < n_{\max}$	Évite boucle infinie

Résumé des méthodes

Tableau comparatif

Méthode	Ordre p	Constante C	Remarques
Bissection	1	0.5	Robuste, convergence garantie si encadrement
Interpolation linéaire	1	Variable	Garde l'encadrement, peut être lente
Sécante	≈ 1.618	—	Nombre d'or, bon compromis
Newton (simple)	2	$\frac{\|G''(r)\|}{2}$	Quadratique, nécessite $F'$
Newton (multiple)	1	$\frac{m-1}{m}$	Linéaire pour racine de multiplicité m
Point fixe	1, 2 ou 3	Dépend de $g'(r)$	Flexible, dépend du choix de $g$

Caractéristiques clés

Bissection :

Toujours convergente si $F(a) \cdot F(b) < 0$
Prévisible : l'erreur est divisée par 2 à chaque itération
Lente (convergence linéaire)
Nécessite un encadrement initial

Interpolation linéaire (Regula Falsi) :

Garde l'encadrement (pas de divergence)
Une borne peut rester « bloquée »
Peut être plus lente que la bissection

Sécante :

Convergence superlinéaire ( $p \approx 1.618$ )
Une seule évaluation de $F$ par itération
Peut diverger (pas d'encadrement garanti)
Nécessite deux points de départ

Newton :

Convergence quadratique (très rapide)
Nécessite $F'$
Peut diverger si mauvais point de départ
Perd la convergence quadratique pour les racines multiples

Point fixe :

Très flexible (plusieurs formulations possibles)
Peut atteindre convergence quadratique ou cubique si bien choisi
Convergence dépend fortement du choix de $g$
Nécessite $|g'(r)| < 1$

Comment choisir une méthode ?

Arbre de décision

Question 1 : Avez-vous un encadrement de la racine ?

Oui → Bissection ou Regula Falsi (sûr)
Non → Newton ou Sécante (rapide mais risqué)

Question 2 : Pouvez-vous calculer $F'$ facilement ?

Oui → Newton (si bonne initialisation)
Non → Sécante

Question 3 : La robustesse est-elle prioritaire ?

Oui → Bissection
Non → Newton ou Sécante

Question 4 : La racine est-elle multiple ?

Oui → Newton modifié ou autre méthode
Non → Newton standard

Stratégie hybride

Une approche courante est de combiner les méthodes :

Phase 1 : Utiliser la bissection pour obtenir un bon encadrement et une approximation grossière
Phase 2 : Passer à Newton pour affiner rapidement la solution

Cette stratégie combine la robustesse de la bissection et la rapidité de Newton.

Vers où converge-t-on ?

Le problème des multiples racines

Considérons une fonction avec plusieurs racines. Où va converger chaque méthode ?

Bissection : Converge vers la racine dans l'intervalle initial $[a, b]$ . Si l'intervalle contient plusieurs racines, le comportement est imprévisible.

Interpolation linéaire : Même comportement que la bissection.

Sécante : Converge vers une racine proche des points de départ, mais peut « sauter » vers une autre racine.

Newton : Très sensible au point de départ. Peut converger vers une racine inattendue ou même diverger.

⚠️

Attention

Le choix du point de départ est crucial pour Newton et la sécante. Une bonne pratique est de d'abord localiser les racines (par exemple avec un graphique ou une recherche par bissection) avant d'appliquer une méthode rapide.

Introduction à la méthode de Muller

Motivation

Toutes les méthodes vues jusqu'ici sont basées sur des approximations linéaires (droites) de la fonction. La méthode de Muller utilise une approximation parabolique (degré 2), ce qui peut accélérer la convergence.

Principe

Au lieu de deux points, on utilise trois points $(X_0, F(X_0))$ , $(X_1, F(X_1))$ , $(X_2, F(X_2))$ pour construire une parabole passant par ces points.

Construction de la parabole

On cherche un polynôme de degré 2 sous la forme :

P(X) = a(X - X_0)^2 + b(X - X_0) + c

Les coefficients $a$ , $b$ , $c$ sont déterminés par le système :

\begin{cases} P(X_0) = F(X_0) \\ P(X_1) = F(X_1) \\ P(X_2) = F(X_2) \end{cases}

Calcul de la nouvelle approximation

Une fois la parabole construite, on cherche ses racines en résolvant $P(X) = 0$ :

r_{1,2} = X_0 + \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}

On choisit la racine la plus proche de $X_0$ comme nouvelle approximation $X_3$ , puis on recommence avec trois nouveaux points.

Avantages de Muller

Ordre de convergence : environ $p \approx 1.84$ (plus rapide que la sécante)
Racines complexes : peut trouver des racines complexes même en partant de points réels (grâce au discriminant qui peut être négatif)

Inconvénients

Plus complexe à implémenter
Nécessite trois points de départ

Résumé du chapitre 2

Ce que nous avons appris

Formulation du problème : résoudre $F(X) = 0$
Méthodes d'encadrement :
- Bissection : divise l'intervalle par 2
- Interpolation linéaire : utilise une droite
Méthodes ouvertes :
- Sécante : approximation de la dérivée
- Newton : utilise la tangente
- Point fixe : reformulation $X = g(X)$
Analyse de convergence :
- Ordre de convergence $p$
- Constante asymptotique $C$
- Forme de l'erreur : $e_{n+1} \approx C \cdot e_n^p$
Critères d'arrêt :
- Sur la racine : $|X_{n+1} - X_n| < \delta$
- Sur la fonction : $|F(X_{n+1})| < \varepsilon$

Tableau final

Méthode	Type	Ordre	Points requis	Dérivée ?
Bissection	Encadrement	1	2 (signes opposés)	Non
Regula Falsi	Encadrement	1	2 (signes opposés)	Non
Sécante	Ouverte	1.618	2	Non
Newton	Ouverte	2	1	Oui
Point fixe	Ouverte	1-3	1	Selon g
Muller	Ouverte	≈ 1.84	3	Non

Points clés à retenir

Pas de méthode universelle : chaque méthode a ses avantages et inconvénients
Compromis robustesse/vitesse : les méthodes rapides (Newton) sont moins robustes
L'ordre de convergence est crucial : quadratique >> linéaire
Le choix du point de départ est important pour les méthodes ouvertes
Combiner les méthodes est souvent la meilleure stratégie