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 qui converge vers la racine . 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 :

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

Interprétation : Si et sont très proches, on suppose que les deux sont proches de la vraie racine.

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

Limitation : Pour une convergence lente, peut être petit alors que est encore loin de .

Critère 2 : Tolérance sur la fonction

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

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

Interprétation : Si , alors est proche d'une racine.

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

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

Critère 3 : Combinaison des deux

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

ou parfois avec un OU :

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

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

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

Résumé des critères

Résumé des méthodes

Tableau comparatif

Caractéristiques clés

Bissection :

• Toujours convergente si
• 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 ()
• Une seule évaluation de par itération
• Peut diverger (pas d'encadrement garanti)
• Nécessite deux points de départ

Newton :

• Convergence quadratique (très rapide)
• Nécessite
• 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
• Nécessite

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 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 :

1. Phase 1 : Utiliser la bissection pour obtenir un bon encadrement et une approximation grossière
2. 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 . 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.

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 , , pour construire une parabole passant par ces points.

Construction de la parabole

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

Les coefficients , , sont déterminés par le système :

Calcul de la nouvelle approximation

Une fois la parabole construite, on cherche ses racines en résolvant :

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

Avantages de Muller

• Ordre de convergence : environ (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

1. Formulation du problème : résoudre

2. Méthodes d'encadrement :

   • Bissection : divise l'intervalle par 2
   • Interpolation linéaire : utilise une droite

3. Méthodes ouvertes :

   • Sécante : approximation de la dérivée
   • Newton : utilise la tangente
   • Point fixe : reformulation

4. Analyse de convergence :

   • Ordre de convergence
   • Constante asymptotique
   • Forme de l'erreur :

5. Critères d'arrêt :

   • Sur la racine :
   • Sur la fonction :

Tableau final

Points clés à retenir

1. Pas de méthode universelle : chaque méthode a ses avantages et inconvénients

2. Compromis robustesse/vitesse : les méthodes rapides (Newton) sont moins robustes

3. L'ordre de convergence est crucial : quadratique >> linéaire

4. Le choix du point de départ est important pour les méthodes ouvertes

5. Combiner les méthodes est souvent la meilleure stratégie