96
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Dans ce cas, les matrices L et U de la factorisation LU de A sont des matrices
bidiagonales de la forme
L =
⎡
⎢
⎢
⎢
⎢
⎣
1
0
β 2 1
. . .
. . .
0
β n 1
⎤
⎥
⎥
⎥
⎥
⎦
, U =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
α 1 c 1
0
α 2
. . .
. . . c n−1
0
α n
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
Les coefficients α i et β i s’obtiennent facilement avec les relations suivantes
α 1 = a 1 , β i =
b i
α i−1
, α i = a i − β i c i−1 , i = 2, . . ., n.
(3.50)
Ces formules sont connues sous le nom d’ algorithme de Thomas et peuvent
ˆ etre vues comme un cas particulier de la factorisation de Doolittle sans changement de pivot. Quand il n’est pas utile de conserver les ´ el´ ements de la matrice
originale, les coefficients α i et β i peuvent ˆ etre stock´ es dans A.
On peut ´ etendre l’algorithme de Thomas `
a la r´ esolution du syst` eme Ax =
f . Cela revient `
a r´ esoudre deux syst` emes bidiagonaux, Ly = f et Ux = y,
pour lesquels on a les formules suivantes :
(Ly = f ) y 1 = f 1 , y i = f i − β i y i−1 , i = 2, . . . , n,
(3.51)
(Ux = y) x n =
y n
α n
, x i = (y i − c i x i+1 ) /α i , i = n − 1, . . . , 1.
(3.52)
L’algorithme ne requiert que 8n − 7 flops : plus pr´ ecis´ ement, 3(n − 1) flops
pour la factorisation (3.50) et 5n − 4 flops pour la substitution (3.51)-(3.52).
Pour ce qui est de la stabilit´ e de la m´ ethode, si A est une matrice tridiagonale inversible et si
L et
U sont les matrices effectivement calcul´ ees au terme
de la factorisation, alors
|δA| ≤ (4u + 3u
2 + u
3 )|
L| |
U|,
o` u δA est d´ efinie implicitement par la relation A+δA =
L
U, et o` u u est l’unit´ e
d’arrondi. En particulier, si A est ´ egalement sym´ etrique d´ efinie positive ou si
A est une M-matrice, alors
|δA| ≤
4u + 3u
2 + u
3
1 − u
|A|,
ce qui implique la stabilit´ e de la factorisation dans ces cas. Il existe un r´ esultat
analogue dans le cas o` u A est ` a diagonale dominante.
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Dans ce cas, les matrices L et U de la factorisation LU de A sont des matrices
bidiagonales de la forme
L =
⎡
⎢
⎢
⎢
⎢
⎣
1
0
β 2 1
. . .
. . .
0
β n 1
⎤
⎥
⎥
⎥
⎥
⎦
, U =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
α 1 c 1
0
α 2
. . .
. . . c n−1
0
α n
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
Les coefficients α i et β i s’obtiennent facilement avec les relations suivantes
α 1 = a 1 , β i =
b i
α i−1
, α i = a i − β i c i−1 , i = 2, . . ., n.
(3.50)
Ces formules sont connues sous le nom d’ algorithme de Thomas et peuvent
ˆ etre vues comme un cas particulier de la factorisation de Doolittle sans changement de pivot. Quand il n’est pas utile de conserver les ´ el´ ements de la matrice
originale, les coefficients α i et β i peuvent ˆ etre stock´ es dans A.
On peut ´ etendre l’algorithme de Thomas `
a la r´ esolution du syst` eme Ax =
f . Cela revient `
a r´ esoudre deux syst` emes bidiagonaux, Ly = f et Ux = y,
pour lesquels on a les formules suivantes :
(Ly = f ) y 1 = f 1 , y i = f i − β i y i−1 , i = 2, . . . , n,
(3.51)
(Ux = y) x n =
y n
α n
, x i = (y i − c i x i+1 ) /α i , i = n − 1, . . . , 1.
(3.52)
L’algorithme ne requiert que 8n − 7 flops : plus pr´ ecis´ ement, 3(n − 1) flops
pour la factorisation (3.50) et 5n − 4 flops pour la substitution (3.51)-(3.52).
Pour ce qui est de la stabilit´ e de la m´ ethode, si A est une matrice tridiagonale inversible et si
L et
U sont les matrices effectivement calcul´ ees au terme
de la factorisation, alors
|δA| ≤ (4u + 3u
2 + u
3 )|
L| |
U|,
o` u δA est d´ efinie implicitement par la relation A+δA =
L
U, et o` u u est l’unit´ e
d’arrondi. En particulier, si A est ´ egalement sym´ etrique d´ efinie positive ou si
A est une M-matrice, alors
|δA| ≤
4u + 3u
2 + u
3
1 − u
|A|,
ce qui implique la stabilit´ e de la factorisation dans ces cas. Il existe un r´ esultat
analogue dans le cas o` u A est ` a diagonale dominante.