3.7 Syst` emes bandes
95
m´ ethode de Gauss ou de la d´ ecomposition LU sp´ ecialement adapt´ ees aux matrices de ce type. Le lecteur trouvera des d´ emonstrations et une approche plus
exhaustive dans [GL89] et [Hig88] pour ce qui concerne les matrices bandes ou
par blocs, et dans [JM92], [GL81], [Saa96] pour ce qui concerne les matrices
creuses et leur stockage.
Voici le principal r´ esultat pour les matrices bandes :
Propri´ et´ e 3.4 Soit A∈ R
n×n . Supposons qu’il existe une factorisation LU de
A. Si A a une largeur de bande sup´ erieure q et une largeur de bande inf´ erieure
p, alors U a une largeur de bande sup´ erieure q et L a une largeur de bande
inf´ erieure p.
Remarquons en particulier que la zone m´ emoire utilis´ ee pour A est suffisante
pour stocker sa factorisation LU. En effet, une matrice A dont la largeur
de bande sup´ erieure est q et inf´ erieure p est g´ en´ eralement stock´ ee dans une
matrice B (p + q + 1) × n, avec
b i−j+q+1,j = a ij
pour tous les indices i, j situ´ es dans la bande de la matrice. Par exemple, dans
le cas d’une matrice tridiagonale (i.e. q = p = 1) A=tridiag 5 (−1, 2, −1), le
stockage compact s’´ ecrit
B =
⎡
⎣
0 −1 −1 −1 −1
2
2
2
2
2
−1 −1 −1 −1
0
⎤
⎦ .
Le mˆ eme format peut ˆ etre utilis´ e pour stocker la factorisation LU de A. Notons
que ce format peut ˆ etre mal adapt´ e au cas o` u seules quelques bandes de la
matrice sont larges : dans le cas extrˆ eme o` u seule une colonne et une ligne
seraient pleines, on aurait p = q = n et B serait alors une matrice pleine avec
de nombreux termes nuls.
Notons enfin que l’inverse d’une matrice bande est en g´ en´ eral pleine (c’est
ce qui se produit pour la matrice B ci-dessus).
3.7.1 Matrices tridiagonales
Consid´ erons le cas particulier d’un syst` eme lin´ eaire dont la matrice est tridiagonale et inversible :
A =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
a 1 c 1
0
b 2 a 2
. . .
. . .
c n−1
0
b n
a n
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.
95
m´ ethode de Gauss ou de la d´ ecomposition LU sp´ ecialement adapt´ ees aux matrices de ce type. Le lecteur trouvera des d´ emonstrations et une approche plus
exhaustive dans [GL89] et [Hig88] pour ce qui concerne les matrices bandes ou
par blocs, et dans [JM92], [GL81], [Saa96] pour ce qui concerne les matrices
creuses et leur stockage.
Voici le principal r´ esultat pour les matrices bandes :
Propri´ et´ e 3.4 Soit A∈ R
n×n . Supposons qu’il existe une factorisation LU de
A. Si A a une largeur de bande sup´ erieure q et une largeur de bande inf´ erieure
p, alors U a une largeur de bande sup´ erieure q et L a une largeur de bande
inf´ erieure p.
Remarquons en particulier que la zone m´ emoire utilis´ ee pour A est suffisante
pour stocker sa factorisation LU. En effet, une matrice A dont la largeur
de bande sup´ erieure est q et inf´ erieure p est g´ en´ eralement stock´ ee dans une
matrice B (p + q + 1) × n, avec
b i−j+q+1,j = a ij
pour tous les indices i, j situ´ es dans la bande de la matrice. Par exemple, dans
le cas d’une matrice tridiagonale (i.e. q = p = 1) A=tridiag 5 (−1, 2, −1), le
stockage compact s’´ ecrit
B =
⎡
⎣
0 −1 −1 −1 −1
2
2
2
2
2
−1 −1 −1 −1
0
⎤
⎦ .
Le mˆ eme format peut ˆ etre utilis´ e pour stocker la factorisation LU de A. Notons
que ce format peut ˆ etre mal adapt´ e au cas o` u seules quelques bandes de la
matrice sont larges : dans le cas extrˆ eme o` u seule une colonne et une ligne
seraient pleines, on aurait p = q = n et B serait alors une matrice pleine avec
de nombreux termes nuls.
Notons enfin que l’inverse d’une matrice bande est en g´ en´ eral pleine (c’est
ce qui se produit pour la matrice B ci-dessus).
3.7.1 Matrices tridiagonales
Consid´ erons le cas particulier d’un syst` eme lin´ eaire dont la matrice est tridiagonale et inversible :
A =
⎡
⎢
⎢
⎢
⎢
⎢
⎣
a 1 c 1
0
b 2 a 2
. . .
. . .
c n−1
0
b n
a n
⎤
⎥
⎥
⎥
⎥
⎥
⎦
.