II.2. Conditions de minimalité du second ordre
soit encore
f (x k+1 ) − f = [f (x k ) − f ]
1 −
d k 4
2(f (x k ) − f ) Ad k , d k
(toujours sous l’hypothèse ∇f (x k ) = 0, qui est équivalente à f (x k ) − f > 0).
Un simple calcul à présent montre que
A
−1 d k , d k = A
−1 (Ax k + b), Ax k + b
= 2
1
2
Ax k , x k + b, x k +
1
2
A
−1 b, b
= 2
f (x k ) − f
car
1
2
A
−1 b, b = c − f
.
D’où l’expression (2.5).
3 ◦ ) De l’inégalité de Kantorovitch on déduit (toujours lorsque d k = 0) :
d k 4
Ad k , d k A −1 d k , d k
4
λ 1
λ n
+
λ n
λ 1
−2
= 4
λ 1 /λ n
(λ 1 /λ n + 1) 2 ·
Ainsi, d’après (2.5) :
∀k ∈ N, f(x k+1 ) − f [f (x k ) − f ]
1 − 4
c 2 (A)
(c 2 (A) + 1) 2
[f (x k ) − f ]
c 2 (A) − 1
c 2 (A) + 1
2
.
L’inégalité (2.6) s’ensuit alors facilement.
Par ailleurs on a :
f (x k ) − f =
1
2
Ax k , x k + b, x k + c − f
=
1
2
A(x k − x), x k − x
car Ax = −b
et c − f =
1
2 A −1 b, b
1
2
λ n x k − x
2 ;
d’où (2.7).
D’après (2.6) et (2.7), plus c 2 (A) est proche de 1, plus la méthode (du
gradient à pas optimal) converge rapidement. Le cas limite serait celui où
c 2 (A) = 1, ce qui suppose f (x) = λ x − x 2 pour un certain λ > 0, auquel
cas on atteint x dès la 1 re itération x 1 .
Par contre, lorsque c 2 (A) est grand, c’est-à-dire lorsque les valeurs propres
extrêmes sont très différentes, la méthode est (dans le pire des cas) très lente.
55