250
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
et on pose x
(k+1) = x
(k) + δx
(k+1) . La matrice Q k , de taille n × n, est telle
que
Q k δx
(k) = F(x
(k) ) − F(x
(k−1) ) = b
(k) ,
k≥ 1.
(6.49)
Elle est obtenue en g´ en´ eralisant formellement (6.13). N´ eanmoins, l’´ egalit´ e cidessus ne suffit pas ` a d´ eterminer Q k de mani` ere unique. Pour cela, on impose
` a Q k , pour k ≥ n, d’ˆ etre solution des n syst` emes d’´ equations
Q k
x
(k)
− x
(k−j)
= F(x
(k) ) − F(x
(k−j) ),
j = 1, . . . , n.
(6.50)
Si les vecteurs x
(k−j) , . . ., x
(k) sont lin´ eairement ind´ ependants, le syst` eme
(6.50) permet de calculer les coefficients inconnus {(Q k ) lm , l, m = 1, . . . , n}
de Q k . Malheureusement, ces vecteurs tendent en pratique `
a devenir li´ es et
la m´ ethode obtenue est instable, sans parler de la n´ ecessit´ e de stocker les n
it´ er´ ees pr´ ec´ edentes.
Pour ces raisons, on suit une approche alternative qui consiste `
a conserver
l’information fournie par la m´ ethode `
a l’´ etape k. Plus pr´ ecis´ ement, on cherche
Q k de mani` ere ` a ce que la diff´ erence entre les approximations lin´ eaires de
F(x
(k−1) ) et F(x
(k) ) donn´ ees par
F(x
(k) ) + Q k (x − x
(k) ) et F(x
(k−1) ) + Q k−1 (x − x
(k−1) ),
soit minimis´ ee sous la contrainte que Q k soit solution de (6.50). En utilisant
(6.50) avec j = 1, on voit que la diff´ erence entre deux approximations est
donn´ ee par
d k = (Q k − Q k−1 )
x − x
(k−1)
.
(6.51)
D´ ecomposons le vecteur x−x
(k−1) de la fa¸ con suivante : x−x
(k−1) = αδx
(k) +
s, o` u α ∈ R et s
T
δx
(k) = 0. Alors (6.51) devient
d k = α (Q k − Q k−1 ) δx
(k) + (Q k − Q k−1 ) s.
Seul le second terme de cette relation peut ˆ etre minimis´ e. Le premier est en
effet ind´ ependant de Q k puisque
(Q k − Q k−1 )δx
(k) = b
(k)
− Q k−1 δx
(k) .
Le probl` eme s’´ ecrit donc : trouver la matrice Q k telle que (Q k − Q k−1 ) s
est minimis´ e ∀s orthogonal `
a δx
(k) sous la contrainte (6.50). On montre qu’un
telle matrice existe et qu’elle peut ˆ etre calcul´ ee par la formule de r´ ecurrence
Q k = Q k−1 +
(b
(k)
− Q k−1 δx
(k) )δx
(k) T
δx (k) T δx (k)
.
(6.52)
La m´ ethode (6.48) avec la matrice Q k donn´ ee par (6.52) est appel´ ee m´ ethode
de Broyden. Pour initialiser (6.52), on prend Q 0 ´ egal ` a la matrice J F (x
(0) ) ou `
a
une de ses approximations (par exemple celle donn´ ee par (6.46)). Concernant
la convergence de la m´ ethode de Broyden, on a le r´ esultat suivant :
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
et on pose x
(k+1) = x
(k) + δx
(k+1) . La matrice Q k , de taille n × n, est telle
que
Q k δx
(k) = F(x
(k) ) − F(x
(k−1) ) = b
(k) ,
k≥ 1.
(6.49)
Elle est obtenue en g´ en´ eralisant formellement (6.13). N´ eanmoins, l’´ egalit´ e cidessus ne suffit pas ` a d´ eterminer Q k de mani` ere unique. Pour cela, on impose
` a Q k , pour k ≥ n, d’ˆ etre solution des n syst` emes d’´ equations
Q k
x
(k)
− x
(k−j)
= F(x
(k) ) − F(x
(k−j) ),
j = 1, . . . , n.
(6.50)
Si les vecteurs x
(k−j) , . . ., x
(k) sont lin´ eairement ind´ ependants, le syst` eme
(6.50) permet de calculer les coefficients inconnus {(Q k ) lm , l, m = 1, . . . , n}
de Q k . Malheureusement, ces vecteurs tendent en pratique `
a devenir li´ es et
la m´ ethode obtenue est instable, sans parler de la n´ ecessit´ e de stocker les n
it´ er´ ees pr´ ec´ edentes.
Pour ces raisons, on suit une approche alternative qui consiste `
a conserver
l’information fournie par la m´ ethode `
a l’´ etape k. Plus pr´ ecis´ ement, on cherche
Q k de mani` ere ` a ce que la diff´ erence entre les approximations lin´ eaires de
F(x
(k−1) ) et F(x
(k) ) donn´ ees par
F(x
(k) ) + Q k (x − x
(k) ) et F(x
(k−1) ) + Q k−1 (x − x
(k−1) ),
soit minimis´ ee sous la contrainte que Q k soit solution de (6.50). En utilisant
(6.50) avec j = 1, on voit que la diff´ erence entre deux approximations est
donn´ ee par
d k = (Q k − Q k−1 )
x − x
(k−1)
.
(6.51)
D´ ecomposons le vecteur x−x
(k−1) de la fa¸ con suivante : x−x
(k−1) = αδx
(k) +
s, o` u α ∈ R et s
T
δx
(k) = 0. Alors (6.51) devient
d k = α (Q k − Q k−1 ) δx
(k) + (Q k − Q k−1 ) s.
Seul le second terme de cette relation peut ˆ etre minimis´ e. Le premier est en
effet ind´ ependant de Q k puisque
(Q k − Q k−1 )δx
(k) = b
(k)
− Q k−1 δx
(k) .
Le probl` eme s’´ ecrit donc : trouver la matrice Q k telle que (Q k − Q k−1 ) s
est minimis´ e ∀s orthogonal `
a δx
(k) sous la contrainte (6.50). On montre qu’un
telle matrice existe et qu’elle peut ˆ etre calcul´ ee par la formule de r´ ecurrence
Q k = Q k−1 +
(b
(k)
− Q k−1 δx
(k) )δx
(k) T
δx (k) T δx (k)
.
(6.52)
La m´ ethode (6.48) avec la matrice Q k donn´ ee par (6.52) est appel´ ee m´ ethode
de Broyden. Pour initialiser (6.52), on prend Q 0 ´ egal ` a la matrice J F (x
(0) ) ou `
a
une de ses approximations (par exemple celle donn´ ee par (6.46)). Concernant
la convergence de la m´ ethode de Broyden, on a le r´ esultat suivant :