5.6 Comment résoudre un système tridiagonal
153
x −
x
x
≤ K(A)
r
b
(5.32)
Donc si K(A) est “petit”, on peut être sûr que l’erreur est petite
quand le résidu est petit, tandis que ce n’est pas nécessairement le cas
quand K(A) est “grand”.
Exemple 5.11 Les résidus associés à la solution numérique des systèmes linéaires de l’Exemple 5.9 sont très petits (leurs normes varient entre 10
−16 et
10
−11 ) ; pourtant les solutions calculées différent notablement de la solution
exacte.
Voir Exercices 5.9–5.10.
5.6 Comment résoudre un système tridiagonal
Dans de nombreuses applications (voir par exemple le Chapitre 8), on
doit résoudre un système dont la matrice est de la forme
A =
⎡
⎢
⎢
⎢
⎣
a 1 c 1
0
e 2 a 2
. . .
. . .
c n−1
0
e n a n
⎤
⎥
⎥
⎥
⎦
.
On dit que cette matrice est tridiagonale car les seuls éléments non
nuls sont sur la diagonale principale et sur les premières sur- et sousdiagonales.
Alors, si la factorisation LU de A existe, les matrices L et U sont
bidiagonales (inférieure et supérieure respectivement), plus précisément
L =
⎡
⎢
⎢
⎣
1
0
β 2 1
. . .
. . .
0
β n 1
⎤
⎥
⎥
⎦ , U =
⎡
⎢
⎢
⎢
⎣
α 1 c 1
0
α 2
. . .
. . . c n−1
0
α n
⎤
⎥
⎥
⎥
⎦
.
Les coefficients inconnus α i et β i sont déterminés en écrivant l’égalité
LU = A. Ceci conduit aux relations de récurrence
α 1 = a 1 , β i =
e i
α i−1
, α i = a i − β i c i−1 ,
i = 2, . . ., n. (5.33)
Avec (5.33), il est facile de résoudre les deux systèmes bidiagonaux Ly =
b et Ux = y, pour obtenir les formules suivantes
(Ly = b) y 1 = b 1 , y i = b i − β i y i−1 , i = 2, . . ., n,
(5.34)
(Ux = y) x n =
y n
α n
, x i = (y i − c i x i+1 )/α i , i = n − 1, . . . , 1. (5.35)
153
x −
x
x
≤ K(A)
r
b
(5.32)
Donc si K(A) est “petit”, on peut être sûr que l’erreur est petite
quand le résidu est petit, tandis que ce n’est pas nécessairement le cas
quand K(A) est “grand”.
Exemple 5.11 Les résidus associés à la solution numérique des systèmes linéaires de l’Exemple 5.9 sont très petits (leurs normes varient entre 10
−16 et
10
−11 ) ; pourtant les solutions calculées différent notablement de la solution
exacte.
Voir Exercices 5.9–5.10.
5.6 Comment résoudre un système tridiagonal
Dans de nombreuses applications (voir par exemple le Chapitre 8), on
doit résoudre un système dont la matrice est de la forme
A =
⎡
⎢
⎢
⎢
⎣
a 1 c 1
0
e 2 a 2
. . .
. . .
c n−1
0
e n a n
⎤
⎥
⎥
⎥
⎦
.
On dit que cette matrice est tridiagonale car les seuls éléments non
nuls sont sur la diagonale principale et sur les premières sur- et sousdiagonales.
Alors, si la factorisation LU de A existe, les matrices L et U sont
bidiagonales (inférieure et supérieure respectivement), plus précisément
L =
⎡
⎢
⎢
⎣
1
0
β 2 1
. . .
. . .
0
β n 1
⎤
⎥
⎥
⎦ , U =
⎡
⎢
⎢
⎢
⎣
α 1 c 1
0
α 2
. . .
. . . c n−1
0
α n
⎤
⎥
⎥
⎥
⎦
.
Les coefficients inconnus α i et β i sont déterminés en écrivant l’égalité
LU = A. Ceci conduit aux relations de récurrence
α 1 = a 1 , β i =
e i
α i−1
, α i = a i − β i c i−1 ,
i = 2, . . ., n. (5.33)
Avec (5.33), il est facile de résoudre les deux systèmes bidiagonaux Ly =
b et Ux = y, pour obtenir les formules suivantes
(Ly = b) y 1 = b 1 , y i = b i − β i y i−1 , i = 2, . . ., n,
(5.34)
(Ux = y) x n =
y n
α n
, x i = (y i − c i x i+1 )/α i , i = n − 1, . . . , 1. (5.35)