Leçon 1.3 : Méthode de Newton locale

Objectif

Comprendre la méthode de Newton et sa convergence quadratique pour les problèmes d’optimisation.

1. Fondements théoriques

3.1.1 Développement de Taylor au second ordre

Soit une fonction f dérivable deux fois.

Autour d’un point x, on a :

f(x + h) ≈ f(x) + ∇f(x)^T h + (1/2) h^T H(x) h

où :

∇f(x) est le gradient
H(x) est la matrice hessienne

Interprétation

On approxime la fonction par une parabole (en dimension 1) ou une surface quadratique.

Exemple corrigé

Énoncé : Approcher f(x) = x² au voisinage de x = 1

f'(x) = 2x, f''(x) = 2

À x = 1 :

f(1 + h) ≈ 1 + 2h + (1/2) × 2 × h²

f(1 + h) ≈ 1 + 2h + h²

3.1.2 Direction de Newton

On minimise l’approximation quadratique :

d_k = − H(x_k)⁻¹ ∇f(x_k)

Interprétation

On corrige la direction du gradient en tenant compte de la courbure.

Exemple corrigé

Énoncé : Trouver la direction de Newton pour f(x) = x² au point x = 2

∇f(x) = 2x → ∇f(2) = 4

H(x) = 2

d = − 4 / 2 = −2

3.1.3 Résolution du système linéaire

On doit résoudre :

H(x_k) d_k = − ∇f(x_k)

Cas multidimensionnel

On résout un système linéaire classique.

Exemple corrigé

Énoncé : Résoudre H d = −∇f avec :

H = [[2,0],[0,4]] et ∇f = (2,8)

On a :

2d₁ = −2 → d₁ = −1

4d₂ = −8 → d₂ = −2

Donc d = (−1, −2)

3.1.4 Condition de définition positive

La hessienne doit être définie positive pour garantir une direction de descente.

Condition

z^T H z > 0 pour tout z ≠ 0

Exemple corrigé

Énoncé : Vérifier si H = [[2,0],[0,4]] est définie positive

z = (z₁, z₂)

z^T H z = 2z₁² + 4z₂² > 0

Donc H est définie positive.

2. Convergence quadratique

3.2.1 Définition et propriétés

La convergence est quadratique si :

||x_k+1 − x*|| ≤ C · ||x_k − x*||²

Interprétation

L’erreur est multipliée par elle-même → convergence très rapide.

3.2.2 Conditions suffisantes

f est deux fois dérivable
H(x*) est définie positive
x₀ proche de x*

3.2.3 Comparaison avec la convergence linéaire

Gradient : convergence linéaire
Newton : convergence quadratique

Newton est plus rapide mais plus coûteux.

3. Versant pratique

3.3.1 Calcul de la hessienne

La hessienne contient les dérivées secondes :

H = [ ∂²f / ∂x_i∂x_j ]

Exemple corrigé

Énoncé : Calculer la hessienne de f(x,y) = x² + y²

H = [[2,0],[0,2]]

3.3.2 Résolution numérique du système

On utilise :

méthode de Gauss
factorisation LU

Exemple

Résoudre un système 2×2 comme vu précédemment.

3.3.3 Gestion des hessiennes non définies positives

Si H n’est pas définie positive :

la direction peut ne pas être descendante

Solutions

modifier H
ajouter une régularisation : H + λI

Exemple corrigé

Énoncé : Corriger H = [[-1,0],[0,2]]

On prend :

H' = H + 2I = [[1,0],[0,4]]

H' est définie positive.

Exercices corrigés

Exercice 1

Énoncé :

Soit f(x) = x² − 4x

Calculer le gradient
Calculer la hessienne
Donner la direction de Newton en x = 0
Calculer x₁
Trouver le minimum

Correction :

∇f(x) = 2x − 4
H = 2
À x = 0 : ∇f = −4 → d = −(−4)/2 = 2
x₁ = 0 + 2 = 2
Minimum en x = 2

Exercice 2

Énoncé :

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

Calculer le gradient
Calculer la hessienne
Donner la direction de Newton en (1,1)
Faire une itération
Conclusion

Correction :

∇f = (2x,2y)
H = [[2,0],[0,2]]
À (1,1) : ∇f = (2,2)

d = − H⁻¹ ∇f = (−1,−1)

(1,1) + (−1,−1) = (0,0)
Convergence en une étape

Exercice 3

Énoncé :

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

Gradient
Hessienne
Direction de Newton en (1,1)
Itération
Comparer avec le gradient

Correction :

∇f = (2x,8y)
H = [[2,0],[0,4]]
À (1,1) : ∇f = (2,8)

d = (−1,−2)

(1,1) → (0,−1)
Newton est plus rapide que le gradient

Exercices d’entraînement

Exercice A

f(x) = x² + 2x
Calculer gradient et hessienne
Direction de Newton
Faire une itération
Trouver le minimum

Exercice B

f(x,y) = x² + 3y²
Calculer gradient et hessienne
Direction en (2,1)
Faire une itération
Comparer avec le gradient

Conclusion

La méthode de Newton :

utilise la courbure (hessienne)
converge très rapidement
est plus coûteuse à chaque itération

Méthode de Newton

Leçon 1.3 : Méthode de Newton locale

Objectif

1. Fondements théoriques