6.7 R´ esolution des syst` emes d’´ equations non lin´ eaires
245
D´ emonstration. On va montrer par r´ ecurrence sur k la relation (6.43) et le fait
que x
(k+1) ∈ B(x
∗ ; r), avec r = min(R, 1/(2CL)). Prouvons tout d’abord que pour
tout x
(0) ∈ B(x
∗ ; r) la matrice inverse J
−1
F (x
(0) ) existe bien. On a
−1
F (x
∗ )[JF(x
(0) ) − JF(x
∗ )] ≤ ≤J
−1
F (x
∗ )
(0) ) − JF(x
∗ ) ≤ CLr ≤
1
2
,
et on d´ eduit du Th´ eor` eme 1.5 que J
−1
F (x
(0) ) existe car
−1
F (x
(0) ) ≤
−1
F (x
∗ )
1 − −J
−1
F (x ∗ )[JF(x (0) ) − JF(x ∗ )]
≤ 2J
−1
F (x
∗ ) ≤ 2C.
Par cons´ equent, x
(1) est bien d´ efini et
x
(1) − x
∗ = x
(0) − x
∗ − J
−1
F (x
(0) )[F(x
(0) ) − F(x
∗ )].
En mettant en facteur J
−1
F (x
(0) ) dans le membre de droite et en prenant les normes,
on obtient
(1) − x
∗ ≤ ≤J
−1
F (x
(0) )
∗ ) − F(x
(0) ) − JF(x
(0) )[x
∗ − x
(0) ]
≤ 2C
L
2
∗ − x
(0)
2
o` u on a major´ e le reste de la s´ erie de Taylor de F. Cette relation montre (6.43)
pour k = 0 ; comme de plus x
(0) ∈ B(x
∗ ; r), on a x
∗ − x
(0) ≤ 1/(2CL), d’o` u
(1) − x
∗ ≤
1
2
∗ − x
(0) . Ce qui assure que x
(1) ∈ B(x
∗ ; r).
On montre de mani` ere analogue que si on suppose la relation (6.43) vraie pour
un certain k, alors elle est encore vraie pour k + 1. Ceci prouve le th´ eor` eme.
3
Le Th´ eor` eme 6.2 montre que la m´ ethode de Newton converge de mani` ere quadratique si x
(0) est assez proche de la solution x
∗ et si la matrice jacobienne
est inversible. Il faut noter que la r´ esolution du syst` eme lin´ eaire (6.42) peut
s’av´ erer excessivement coˆ uteuse quand n devient grand. De plus, la matrice
J F (x
(k) ) peut ˆ etre mal conditionn´ ee, ce qui rend difficile l’obtention d’une
solution pr´ ecise. Pour ces raisons, plusieurs versions modifi´ ees de la m´ ethode
de Newton ont ´ et´ e propos´ ees. Nous les aborderons bri` evement dans les prochaines sections et nous renvoyons ` a la litt´ erature sp´ ecialis´ ee pour plus de
d´ etails (voir [OR70], [DS83], [Erh97], [BS90], [SM03], [Deu04] et les r´ ef´ erences
qu’ils contiennent).
Remarque 6.3 Si on note r
(k) = F(x
(k) ) le r´ esidu `
a l’´ etape k, on d´ eduit de
(6.42) que la m´ ethode de Newton peut ˆ etre r´ ecrite sous la forme
I − J G (x
(k) )
x
(k+1)
− x
(k)
= −r
(k) ,
o` u G(x) = x − F(x). Cette relation nous permet d’interpr´ eter la m´ ethode
de Newton comme une m´ ethode de Richardson stationnaire pr´ econditionn´ ee.
Ceci nous incite ` a introduire un param` etre d’acc´ el´ eration α k :
I − J G (x
(k) )
x
(k+1)
− x
(k)
= −α k r
(k) .
Pour le choix de ce param` etre, voir p. ex. [QSS07], Section 7.2.6.
245
D´ emonstration. On va montrer par r´ ecurrence sur k la relation (6.43) et le fait
que x
(k+1) ∈ B(x
∗ ; r), avec r = min(R, 1/(2CL)). Prouvons tout d’abord que pour
tout x
(0) ∈ B(x
∗ ; r) la matrice inverse J
−1
F (x
(0) ) existe bien. On a
−1
F (x
∗ )[JF(x
(0) ) − JF(x
∗ )] ≤ ≤J
−1
F (x
∗ )
(0) ) − JF(x
∗ ) ≤ CLr ≤
1
2
,
et on d´ eduit du Th´ eor` eme 1.5 que J
−1
F (x
(0) ) existe car
−1
F (x
(0) ) ≤
−1
F (x
∗ )
1 − −J
−1
F (x ∗ )[JF(x (0) ) − JF(x ∗ )]
≤ 2J
−1
F (x
∗ ) ≤ 2C.
Par cons´ equent, x
(1) est bien d´ efini et
x
(1) − x
∗ = x
(0) − x
∗ − J
−1
F (x
(0) )[F(x
(0) ) − F(x
∗ )].
En mettant en facteur J
−1
F (x
(0) ) dans le membre de droite et en prenant les normes,
on obtient
(1) − x
∗ ≤ ≤J
−1
F (x
(0) )
∗ ) − F(x
(0) ) − JF(x
(0) )[x
∗ − x
(0) ]
≤ 2C
L
2
∗ − x
(0)
2
o` u on a major´ e le reste de la s´ erie de Taylor de F. Cette relation montre (6.43)
pour k = 0 ; comme de plus x
(0) ∈ B(x
∗ ; r), on a x
∗ − x
(0) ≤ 1/(2CL), d’o` u
(1) − x
∗ ≤
1
2
∗ − x
(0) . Ce qui assure que x
(1) ∈ B(x
∗ ; r).
On montre de mani` ere analogue que si on suppose la relation (6.43) vraie pour
un certain k, alors elle est encore vraie pour k + 1. Ceci prouve le th´ eor` eme.
3
Le Th´ eor` eme 6.2 montre que la m´ ethode de Newton converge de mani` ere quadratique si x
(0) est assez proche de la solution x
∗ et si la matrice jacobienne
est inversible. Il faut noter que la r´ esolution du syst` eme lin´ eaire (6.42) peut
s’av´ erer excessivement coˆ uteuse quand n devient grand. De plus, la matrice
J F (x
(k) ) peut ˆ etre mal conditionn´ ee, ce qui rend difficile l’obtention d’une
solution pr´ ecise. Pour ces raisons, plusieurs versions modifi´ ees de la m´ ethode
de Newton ont ´ et´ e propos´ ees. Nous les aborderons bri` evement dans les prochaines sections et nous renvoyons ` a la litt´ erature sp´ ecialis´ ee pour plus de
d´ etails (voir [OR70], [DS83], [Erh97], [BS90], [SM03], [Deu04] et les r´ ef´ erences
qu’ils contiennent).
Remarque 6.3 Si on note r
(k) = F(x
(k) ) le r´ esidu `
a l’´ etape k, on d´ eduit de
(6.42) que la m´ ethode de Newton peut ˆ etre r´ ecrite sous la forme
I − J G (x
(k) )
x
(k+1)
− x
(k)
= −r
(k) ,
o` u G(x) = x − F(x). Cette relation nous permet d’interpr´ eter la m´ ethode
de Newton comme une m´ ethode de Richardson stationnaire pr´ econditionn´ ee.
Ceci nous incite ` a introduire un param` etre d’acc´ el´ eration α k :
I − J G (x
(k) )
x
(k+1)
− x
(k)
= −α k r
(k) .
Pour le choix de ce param` etre, voir p. ex. [QSS07], Section 7.2.6.