Analyse des méthodes

Leçon 1.4 : Analyse comparative des méthodes

Objectif

Savoir comparer les performances des méthodes du gradient et de Newton sur différentes fonctions.

---

1. Fonctions tests

4.1.1 Fonction quadratique anisotrope

Définition

f(x,y) = x² + 10y²

Propriétés

• Courbes de niveau elliptiques
• Différences de courbure selon les directions

Exemple corrigé

Énoncé : Étudier le comportement du gradient à partir de (1,1)

∇f = (2x, 20y)

Au point (1,1) → ∇f = (2,20)

Direction : d = (−2, −20)

Conclusion : La descente est dominée par la direction y → oscillations possibles.

---

4.1.2 Fonction de Rosenbrock

Définition

f(x,y) = (1 − x)² + 100(y − x²)²

Propriétés

• Minimum en (1,1)
• Vallée très étroite
• Difficile pour le gradient

Exemple corrigé

Énoncé : Identifier le minimum

On remarque que :

(1 − x) = 0 → x = 1

(y − x²) = 0 → y = 1

Donc minimum en (1,1)

---

4.1.3 Critères de comparaison

• Vitesse de convergence
• Robustesse
• Coût de calcul

---

2. Métriques d’évaluation

4.2.1 Nombre d’itérations

Nombre d’étapes nécessaires pour atteindre une précision donnée.

Exemple

• Gradient : 100 itérations
• Newton : 5 itérations

---

4.2.2 Évolution de la fonction objectif

On observe f(x_k) au cours des itérations.

Interprétation

• Diminution rapide → méthode efficace
• Diminution lente → méthode inefficace

---

4.2.3 Évolution du gradient

On suit ||∇f(x_k)||

Objectif

Se rapprocher de 0

---

4.2.4 Visualisation des trajectoires

Représenter les points x_k sur les courbes de niveau.

Exemple

• Gradient : trajectoire en zigzag
• Newton : trajectoire directe

---

3. Analyse des résultats

4.3.1 Robustesse au point de départ

Définition

Capacité à converger depuis différents points initiaux.

Comparaison

• Gradient : robuste
• Newton : sensible

Exemple corrigé

Énoncé : Comparer les méthodes depuis x₀ loin du minimum

Gradient : converge lentement mais sûrement

Newton : peut diverger

---

4.3.2 Vitesse de convergence

• Gradient : convergence linéaire
• Newton : convergence quadratique

Exemple corrigé

Énoncé : Comparer le nombre d’itérations

Gradient : beaucoup d’itérations

Newton : peu d’itérations

---

4.3.3 Coût par itération

• Gradient : calcul simple
• Newton : calcul de la hessienne + inversion

Exemple corrigé

Énoncé : Comparer le coût

Gradient : O(n)

Newton : O(n³)

---

4.3.4 Choix de la méthode selon le problème

• Problème simple → Newton
• Grande dimension → Gradient
• Mauvais conditionnement → Newton préférable

---

Exercices corrigés

Exercice 1

Énoncé :

Soit f(x,y) = x² + 10y²

1. Calculer le gradient
2. Calculer la hessienne
3. Comparer une étape de gradient et Newton en (1,1)
4. Donner la direction dans chaque cas
5. Conclusion

Correction :

1. ∇f = (2x,20y)
2. H = [[2,0],[0,20]]
3. Au point (1,1)
4. Gradient : d = (−2,−20)
5. Newton : d = (−1,−1)
6. Newton est plus stable

---

Exercice 2

Énoncé :

Comparer les deux méthodes sur f(x) = x²

1. Gradient
2. Newton
3. Nombre d’itérations
4. Coût
5. Conclusion

Correction :

1. Gradient : plusieurs itérations
2. Newton : une itération
3. Newton plus rapide
4. Mais plus coûteux
5. Choix dépend du contexte

---

Exercice 3

Énoncé :

Soit f(x,y) = (1 − x)² + 100(y − x²)²

1. Donner le minimum
2. Décrire la difficulté
3. Comparer les trajectoires
4. Quelle méthode est meilleure ?
5. Justifier

Correction :

1. Minimum en (1,1)
2. Vallée étroite
3. Gradient : zigzag
4. Newton : direct
5. Newton est meilleur

---

Exercices d’entraînement

Exercice A

• f(x,y) = x² + 5y²
• Calculer gradient et hessienne
• Comparer les directions
• Analyser la convergence
• Conclusion

Exercice B

• f(x,y) = (1 − x)² + 50(y − x²)²
• Trouver le minimum
• Analyser la difficulté
• Comparer gradient/Newton
• Conclusion

---

Conclusion

Le choix de la méthode dépend :

• de la taille du problème
• du conditionnement
• du coût de calcul

Newton est rapide mais coûteux, le gradient est simple mais lent.