118
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
4.2 M´ ethodes it´ eratives lin´ eaires
Une technique g´ en´ erale pour d´ efinir une m´ ethode it´ erative lin´ eaire consistante
est bas´ ee sur la d´ ecomposition, ou splitting, de la matrice A sous la forme
A=P−N, o` u P est une matrice inversible. Pour des raisons qui s’´ eclairciront
dans les prochaines sections, P est appel´ ee matrice de pr´ econditionnement ou
pr´ econditionneur.
On se donne x
(0) , et on calcule x
(k) pour k ≥ 1, en r´ esolvant le syst` eme
Px
(k+1) = Nx
(k) + b, k ≥ 0.
(4.6)
La matrice d’it´ eration de la m´ ethode (4.6) est B = P
−1 N, et f = P
−1 b. On
peut aussi ´ ecrire (4.6) sous la forme
x
(k+1) = x
(k) + P
−1 r
(k) ,
(4.7)
o` u
r
(k) = b − Ax
(k)
(4.8)
d´ esigne le r´ esidu ` a l’it´ eration k. La relation (4.7) montre qu’on doit r´ esoudre un
syst` eme lin´ eaire de matrice P ` a chaque it´ eration. En plus d’ˆ etre inversible, P
doit donc ˆ etre “facile ` a inverser” afin de minimiser le coˆ ut du calcul. Remarquer
que si P est ´ egale ` a A et N=0, la m´ ethode (4.7) converge en une it´ eration,
mais avec le mˆ eme coˆ ut qu’une m´ ethode directe.
Citons deux r´ esultats qui garantissent la convergence de (4.7), sous des
hypoth` eses convenables concernant le splitting de A (voir p. ex. [Hac94] pour
les d´ emonstrations).
Propri´ et´ e 4.1 Soit A = P − N, avec A et P sym´ etriques d´ efinies positives.
Si la matrice 2P − A est d´ efinie positive, alors la m´ ethode it´ erative (4.7) est
convergente pour toute donn´ ee initiale x
(0) et
ρ(B) = B A = B P < 1.
De plus, la convergence de la suite est monotone pour les normes ·· P et A
( i.e. e
(k+1)
P < e
(k)
P et e
(k+1)
A < e
(k)
A , k = 0, 1, . . .).
Propri´ et´ e 4.2 Soit A = P − N avec A sym´ etrique d´ efinie positive. Si la
matrice P + P
T
− A est d´ efinie positive, alors P est inversible, la m´ ethode
it´ erative (4.7) converge de mani` ere monotone pour la norme · · A et ρ(B) ≤
B A < 1.
4 M´ ethodes it´ eratives pour la r´ esolution des syst` emes lin´ eaires
4.2 M´ ethodes it´ eratives lin´ eaires
Une technique g´ en´ erale pour d´ efinir une m´ ethode it´ erative lin´ eaire consistante
est bas´ ee sur la d´ ecomposition, ou splitting, de la matrice A sous la forme
A=P−N, o` u P est une matrice inversible. Pour des raisons qui s’´ eclairciront
dans les prochaines sections, P est appel´ ee matrice de pr´ econditionnement ou
pr´ econditionneur.
On se donne x
(0) , et on calcule x
(k) pour k ≥ 1, en r´ esolvant le syst` eme
Px
(k+1) = Nx
(k) + b, k ≥ 0.
(4.6)
La matrice d’it´ eration de la m´ ethode (4.6) est B = P
−1 N, et f = P
−1 b. On
peut aussi ´ ecrire (4.6) sous la forme
x
(k+1) = x
(k) + P
−1 r
(k) ,
(4.7)
o` u
r
(k) = b − Ax
(k)
(4.8)
d´ esigne le r´ esidu ` a l’it´ eration k. La relation (4.7) montre qu’on doit r´ esoudre un
syst` eme lin´ eaire de matrice P ` a chaque it´ eration. En plus d’ˆ etre inversible, P
doit donc ˆ etre “facile ` a inverser” afin de minimiser le coˆ ut du calcul. Remarquer
que si P est ´ egale ` a A et N=0, la m´ ethode (4.7) converge en une it´ eration,
mais avec le mˆ eme coˆ ut qu’une m´ ethode directe.
Citons deux r´ esultats qui garantissent la convergence de (4.7), sous des
hypoth` eses convenables concernant le splitting de A (voir p. ex. [Hac94] pour
les d´ emonstrations).
Propri´ et´ e 4.1 Soit A = P − N, avec A et P sym´ etriques d´ efinies positives.
Si la matrice 2P − A est d´ efinie positive, alors la m´ ethode it´ erative (4.7) est
convergente pour toute donn´ ee initiale x
(0) et
ρ(B) = B A = B P < 1.
De plus, la convergence de la suite est monotone pour les normes ·· P et A
( i.e. e
(k+1)
P < e
(k)
P et e
(k+1)
A < e
(k)
A , k = 0, 1, . . .).
Propri´ et´ e 4.2 Soit A = P − N avec A sym´ etrique d´ efinie positive. Si la
matrice P + P
T
− A est d´ efinie positive, alors P est inversible, la m´ ethode
it´ erative (4.7) converge de mani` ere monotone pour la norme · · A et ρ(B) ≤
B A < 1.