248
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
obtenue apr` es m it´ erations, cette derni` ere s’´ ecrit finalement (voir Exercice 13)
x
(k+1) = x
(k)
− ω k
M
m−1
k
+ . . . + I
(D k − ω k E k )
−1 F(x
(k) ).
(6.45)
Dans cette m´ ethode, on effectue donc `
a la k-i` eme ´ etape, m it´ erations de SOR
en partant de x
(k) pour r´ esoudre le syst` eme (6.42) de mani` ere approch´ ee.
L’entier m, ainsi que ω k , peuvent d´ ependre de l’indice k ; le choix le plus
simple consiste ` a effectuer ` a chaque it´ eration de Newton, une seule it´ eration
de SOR. On d´ eduit alors de (6.44) avec r = 1 la m´ ethode de Newton-SOR ` a
un pas
x
(k+1) = x
(k)
− ω k (D k − ω k E k )
−1 F(x
(k) ).
De mani` ere analogue, la m´ ethode de Newton-Richardson pr´ econditionn´ ee par
P k tronqu´ ee ` a la m-i` eme it´ eration, s’´ ecrit
x
(k+1) = x
(k)
−
I + M k + . . . + M
m−1
k
P
−1
k F(x
(k) ),
o` u P k est le pr´ econditionneur de J F et
M k = P
−1
k N k , N k = P k − J F (x
(k) ).
Nous renvoyons au package MATLAB d´ evelopp´ e dans [Kel99] pour une
impl´ ementation efficace de ces techniques.
3. Approximations de la matrice Jacobienne
Une autre possibilit´ e est de remplacer J F (x
(k) ) (dont le calcul explicite est
souvent coˆ uteux) par une approximation du type
(J
(k)
h ) j =
F(x
(k) + h
(k)
j e j ) − F(x
(k) )
h
(k)
j
∀k ≥ 0,
(6.46)
o` u e j est le j-i` eme vecteur de la base canonique de R
n et les h
(k)
j
> 0 sont des
incr´ ements convenablement choisis ` a chaque pas k de (6.42). On peut alors
montrer le r´ esultat suivant :
Propri´ et´ e 6.8 Soient F et x
∗ satisfaisant les hypoth` eses du Th´ eor` eme 6.2
o` u · · d´ esigne `
a la fois la norme vectorielle · · 1 et la norme matricielle
induite. S’il existe deux constantes positives ε et h telles que x
(0)
∈ B(x
∗ , ε)
et 0 < |h
(k)
j | ≤ h pour j = 1, . . . , n alors la suite
x
(k+1) = x
(k)
−
J
(k)
h
−1
F(x
(k) ),
(6.47)
est bien d´ efinie et converge lin´ eairement vers x
∗ . Si de plus il existe une
constante positive C telle que max
j
|h
(k)
j | ≤ C
(k)
− x
∗
ou, de mani` ere ´ equivalente, s’il existe une constante positive c telle que max
j
|h
(k)
j | ≤ cF(x
(k) ),
alors la suite (6.47) converge quadratiquement.
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
obtenue apr` es m it´ erations, cette derni` ere s’´ ecrit finalement (voir Exercice 13)
x
(k+1) = x
(k)
− ω k
M
m−1
k
+ . . . + I
(D k − ω k E k )
−1 F(x
(k) ).
(6.45)
Dans cette m´ ethode, on effectue donc `
a la k-i` eme ´ etape, m it´ erations de SOR
en partant de x
(k) pour r´ esoudre le syst` eme (6.42) de mani` ere approch´ ee.
L’entier m, ainsi que ω k , peuvent d´ ependre de l’indice k ; le choix le plus
simple consiste ` a effectuer ` a chaque it´ eration de Newton, une seule it´ eration
de SOR. On d´ eduit alors de (6.44) avec r = 1 la m´ ethode de Newton-SOR ` a
un pas
x
(k+1) = x
(k)
− ω k (D k − ω k E k )
−1 F(x
(k) ).
De mani` ere analogue, la m´ ethode de Newton-Richardson pr´ econditionn´ ee par
P k tronqu´ ee ` a la m-i` eme it´ eration, s’´ ecrit
x
(k+1) = x
(k)
−
I + M k + . . . + M
m−1
k
P
−1
k F(x
(k) ),
o` u P k est le pr´ econditionneur de J F et
M k = P
−1
k N k , N k = P k − J F (x
(k) ).
Nous renvoyons au package MATLAB d´ evelopp´ e dans [Kel99] pour une
impl´ ementation efficace de ces techniques.
3. Approximations de la matrice Jacobienne
Une autre possibilit´ e est de remplacer J F (x
(k) ) (dont le calcul explicite est
souvent coˆ uteux) par une approximation du type
(J
(k)
h ) j =
F(x
(k) + h
(k)
j e j ) − F(x
(k) )
h
(k)
j
∀k ≥ 0,
(6.46)
o` u e j est le j-i` eme vecteur de la base canonique de R
n et les h
(k)
j
> 0 sont des
incr´ ements convenablement choisis ` a chaque pas k de (6.42). On peut alors
montrer le r´ esultat suivant :
Propri´ et´ e 6.8 Soient F et x
∗ satisfaisant les hypoth` eses du Th´ eor` eme 6.2
o` u · · d´ esigne `
a la fois la norme vectorielle · · 1 et la norme matricielle
induite. S’il existe deux constantes positives ε et h telles que x
(0)
∈ B(x
∗ , ε)
et 0 < |h
(k)
j | ≤ h pour j = 1, . . . , n alors la suite
x
(k+1) = x
(k)
−
J
(k)
h
−1
F(x
(k) ),
(6.47)
est bien d´ efinie et converge lin´ eairement vers x
∗ . Si de plus il existe une
constante positive C telle que max
j
|h
(k)
j | ≤ C
(k)
− x
∗
ou, de mani` ere ´ equivalente, s’il existe une constante positive c telle que max
j
|h
(k)
j | ≤ cF(x
(k) ),
alors la suite (6.47) converge quadratiquement.