3.8 Syst` emes par blocs
101
3.8.3 Syst` emes tridiagonaux par blocs
Consid´ erons les syst` emes tridiagonaux par blocs de la forme
⎡
⎢
⎢
⎢
⎢
⎢
⎣
A 11 A 12
0
A 21 A 22
. . .
. . .
. . .
A n−1,n
0
A n,n−1
A nn
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
x n
⎤
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
b 1
. . .
. . .
b n
⎤
⎥
⎥
⎥
⎥
⎦
,
(3.55)
o` u les A ij sont des matrices d’ordre n i × n j et o` u les x i et b i sont des vecteurs
colonnes de tailles n i , pour i, j = 1, . . ., n. Nous supposons les blocs diagonaux
carr´ es, mais de tailles ´ eventuellement diff´ erentes. Pour k = 1, . . ., n, posons
A k =
⎡
⎢
⎢
⎢
⎢
⎣
I n1
0
L 1 I n2
. . .
. . .
0
L k−1 I nk
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎣
U 1 A 12
0
U 2
. . .
. . . A k−1,k
0
U k
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
En identifiant pour k = n les blocs de cette matrice avec les blocs correspondants de A n , on trouve tout d’abord U 1 = A 11 . Les blocs suivants sont obtenus
en r´ esolvant successivement, pour i = 2, . . . , n, les syst` emes L i−1 U i−1 = A i,i−1
pour les colonnes de L et en calculant U i = A ii − L i−1 A i−1,i .
Ce proc´ ed´ e est bien d´ efini `
a condition que toutes les matrices U i soient inversibles, ce qui est le cas si, par exemple, les matrices A 1 , . . ., A n le sont. Une
alternative serait de recourir aux m´ ethodes de factorisation pour les matrices
bandes, mˆ eme si celles-ci impliquent le stockage d’un grand nombre de termes
nuls (` a moins qu’un r´ earrangement convenable des lignes de la matrice ne soit
effectu´ e).
Int´ eressons-nous au cas particulier o` u les matrices sont tridiagonales par
blocs et sym´ etriques, avec des blocs eux-mˆ emes sym´ etriques et d´ efinis positifs.
Dans ce cas, (3.55) s’´ ecrit
⎡
⎢
⎢
⎢
⎢
⎢
⎣
A 11 A
T
21
0
A 21 A 22
. . .
. . .
. . .
A
T
n,n−1
0
A n,n−1
A nn
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
x n
⎤
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
b 1
. . .
. . .
b n
⎤
⎥
⎥
⎥
⎥
⎦
.
Consid´ erons une extension au cas par blocs de l’algorithme de Thomas qui
transforme A en une matrice bidiagonale par blocs. Pour cela, on doit tout
d’abord ´ eliminer le bloc A 21 . Supposons qu’on connaisse la d´ ecomposition
de Cholesky de A 11 et notons H 11 la matrice de Cholesky. En multipliant la
premi` ere ligne du syst` eme (par blocs) par H
−T
11 , on trouve
H 11 x 1 + H
−T
11 A
T
21 x 2 = H
−T
11 b 1 .
101
3.8.3 Syst` emes tridiagonaux par blocs
Consid´ erons les syst` emes tridiagonaux par blocs de la forme
⎡
⎢
⎢
⎢
⎢
⎢
⎣
A 11 A 12
0
A 21 A 22
. . .
. . .
. . .
A n−1,n
0
A n,n−1
A nn
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
x n
⎤
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
b 1
. . .
. . .
b n
⎤
⎥
⎥
⎥
⎥
⎦
,
(3.55)
o` u les A ij sont des matrices d’ordre n i × n j et o` u les x i et b i sont des vecteurs
colonnes de tailles n i , pour i, j = 1, . . ., n. Nous supposons les blocs diagonaux
carr´ es, mais de tailles ´ eventuellement diff´ erentes. Pour k = 1, . . ., n, posons
A k =
⎡
⎢
⎢
⎢
⎢
⎣
I n1
0
L 1 I n2
. . .
. . .
0
L k−1 I nk
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎢
⎣
U 1 A 12
0
U 2
. . .
. . . A k−1,k
0
U k
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
En identifiant pour k = n les blocs de cette matrice avec les blocs correspondants de A n , on trouve tout d’abord U 1 = A 11 . Les blocs suivants sont obtenus
en r´ esolvant successivement, pour i = 2, . . . , n, les syst` emes L i−1 U i−1 = A i,i−1
pour les colonnes de L et en calculant U i = A ii − L i−1 A i−1,i .
Ce proc´ ed´ e est bien d´ efini `
a condition que toutes les matrices U i soient inversibles, ce qui est le cas si, par exemple, les matrices A 1 , . . ., A n le sont. Une
alternative serait de recourir aux m´ ethodes de factorisation pour les matrices
bandes, mˆ eme si celles-ci impliquent le stockage d’un grand nombre de termes
nuls (` a moins qu’un r´ earrangement convenable des lignes de la matrice ne soit
effectu´ e).
Int´ eressons-nous au cas particulier o` u les matrices sont tridiagonales par
blocs et sym´ etriques, avec des blocs eux-mˆ emes sym´ etriques et d´ efinis positifs.
Dans ce cas, (3.55) s’´ ecrit
⎡
⎢
⎢
⎢
⎢
⎢
⎣
A 11 A
T
21
0
A 21 A 22
. . .
. . .
. . .
A
T
n,n−1
0
A n,n−1
A nn
⎤
⎥
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
x 1
. . .
. . .
x n
⎤
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎢
⎣
b 1
. . .
. . .
b n
⎤
⎥
⎥
⎥
⎥
⎦
.
Consid´ erons une extension au cas par blocs de l’algorithme de Thomas qui
transforme A en une matrice bidiagonale par blocs. Pour cela, on doit tout
d’abord ´ eliminer le bloc A 21 . Supposons qu’on connaisse la d´ ecomposition
de Cholesky de A 11 et notons H 11 la matrice de Cholesky. En multipliant la
premi` ere ligne du syst` eme (par blocs) par H
−T
11 , on trouve
H 11 x 1 + H
−T
11 A
T
21 x 2 = H
−T
11 b 1 .