Chapitre II. Minimisation sans contraintes. Conditions de minimalité
3 ◦ ) Soit λ 1 λ 2 · · · λ n les valeurs propres de A rangées dans l’ordre
décroissant. On pose
c 2 (A) :=
λ 1
λ n
, appelé conditionnement de A.
Démontrer les inégalités suivantes : Pour tout k ∈ N,
f (x k ) − f [f (x 0 ) − f ]
c 2 (A) − 1
c 2 (A) + 1
2k
,
(2.6)
x k − x
2(f (x 0 ) − f )
λ n
1/2
c 2 (A) − 1
c 2 (A) + 1
k
.
(2.7)
On pourra pour cela utiliser librement l’inégalité de Kantorovitch que voici :
∀x ∈ R
n , Ax, x A
−1 x, x
1
4
λ 1
λ n
+
λ n
λ 1
2
x
4 .
Quels commentaires peut-on faire à partir des inégalités (2.6) et (2.7) quant à
la rapidité de convergence de la méthode de gradient à pas optimal ?
Solution : 1 ◦ ) f est quadratique strictement convexe, 1-coercive sur R n : il
existe donc un et un seul x minimisant f sur R n . La différentiabilité de f alliée
à sa convexité assurent que x est l’unique solution de l’équation ∇f (x) = 0.
Si on veut préciser en fonction des données de (P), x = −A −1 b et la valeur
optimale est f = f (x) = −
1
2 A −1 b, b + c.
2 ◦ ) Comme f (x k + td k ) = f (x k ) +
1
2 t 2 Ad k , d k + tAx k + b, d k , la fonction
t ∈ R −→ f (x k + td k ) est minimisée sur R (lorsque d k = −∇f (x k ) = 0) en
un seul point, qui est t k =
d k 2
Ad k , d k
(> 0).
Ensuite :
d k+1 = −(Ax k+1 + b) = −Ax k − b − t k Ad k = d k − t k Ad k ,
d k+1 , d k = d k , d k − t k Ad k , d k = 0.
En développant f (x k+1 ) = f (x k + t k d k ) on obtient
f (x k+1 ) = f (x k ) −
1
2
d k 4
Ad k , d k
,
54