98
M´ ethodes directes pour la r´ esolution des syst` emes lin´ eaires
Programme 12 - backband : Substitution r´ etrograde pour une matrice U de
largeur de bande q
function [b]=backband (U,q,b)
%BACKBAND Substitution r´ etrograde pour une matrice bande
% X=BACKBAND(U,Q,B) r´ esout le syst` eme triangulaire inf´ erieur U*X=B
% o` u U est une matrice de largeur de bande sup´ erieure Q.
[n,m]=size(U);
if n ˜= m, error(’Seulement les syst` emes carr´ es’); end
for j=n:-1:1
b (j) = b (j) / U (j,j);
i = [max(1,j-q):j-1]; b(i)=b(i)-U(i,j)*b(j);
end
return
Dans ces programmes toute la matrice est stock´ ee (y compris les termes nuls).
Dans le cas tridiagonal, l’algorithme de Thomas peut ˆ etre impl´ ement´ e
de plusieurs fa¸ cons. En particulier, quand on l’impl´ emente sur des calculateurs pour lesquels les divisions sont beaucoup plus coˆ uteuses que les multiplications, il est possible d’´ ecrire une version de l’algorithme sans division
dans (3.51) et (3.52), en recourant `
a la factorisation suivante :
A = LDM
T =
⎡
⎢
⎢
⎢
⎢
⎣
γ
−1
1
0
0
b2
γ
−1
2
. . .
. . .
. . .
0
0
bn γ
−1
n
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
γ1
0
γ2
. . .
0
γn
⎤
⎥
⎥
⎥
⎥
⎦
⎡
⎢
⎢
⎢
⎢
⎣
γ
−1
1
c1
0
0
γ
−1
2
. . .
. . .
. . . cn−1
0
0
γ
−1
n
⎤
⎥
⎥
⎥
⎥
⎦
.
Les coefficients γ i peuvent ˆ etre calcul´ es par les formules de r´ ecurrence
γ i = (a i − b i γ i−1 c i−1 )
−1 pour i = 1, . . ., n,
o` u on a suppos´ e γ 0 = 0, b 1 = 0 et c n = 0. Les algorithmes de substitution
directe et r´ etrograde s’´ ecrivent respectivement
(Ly = f ) y 1 = γ 1 f 1 , y i = γ i (f i − b i y i−1 ), i = 2, . . . , n ,
(Ux = y) x n = y n
x i = y i − γ i c i x i+1 ,
i = n − 1, . . ., 1.
(3.53)
On pr´ esente dans le Programme 13 une impl´ ementation de l’algorithme de
Thomas de la forme (3.53) sans division. En entr´ ee, les vecteurs a, b et c
contiennent respectivement les coefficients de la matrice tridiagonale {a i },
{b i } et {c i }, et le vecteur f contient les composantes {f i } du membre de
droite f.