3.7 Syst` emes bandes
97
3.7.2 Impl´ ementations
Une impl´ ementation MATLAB de la factorisation LU pour les matrices bandes
est propos´ ee dans le Programme 10.
Programme 10 - luband : Factorisation LU pour une matrice bande
function [A]=luband(A,p,q)
%LUBAND Factorisation LU d’une matrice bande
% Y=LUBAND(A,P,Q): U est stock´ e dans la partie triangulaire sup´ erieure
% de Y et L est stock´ e dans la partie triangulaire inf´ erieure
% stricte de Y, pour une matrice bande A de largeur de bande sup´ erieure
% Q et de largeur de bande inf´ erieure P.
[n,m]=size(A);
if n ˜= m, error(’Seulement les syst` emes carr´ es’); end
for k = 1:n-1
for i = k+1:min(k+p,n), A(i,k)=A(i,k)/A(k,k); end
for j = k+1:min(k+q,n)
i = [k+1:min(k+p,n)];
A(i,j)=A(i,j)-A(i,k)*A(k,j);
end
end
return
Dans le cas o` u n p et n q, cet algorithme effectue approximativement
2npq flops, ce qui repr´ esente une ´ economie substantielle par rapport au cas
d’une matrice pleine.
On peut concevoir aussi des versions ad hoc des m´ ethodes de substitution
(voir les Programmes 11 et 12). Leurs coˆ uts sont, respectivement, de l’ordre
de 2np flops et 2nq flops, toujours en supposant n p et n q.
Programme 11 - forwband : Substitution directe pour une matrice L de
largeur de bande p
function [b]=forwband (L,p,b)
%FORWBAND Substitution directe pour une matrice bande
% X=FORWBAND(L,P,B) r´ esout le syst` eme triangulaire inf´ erieur L*X=B
% o` u L est une matrice de largeur de bande inf´ erieure P.
[n,m]=size(L);
if n ˜= m, error(’Seulement les syst` emes carr´ es’); end
for j = 1:n
i=[j+1:min(j+p,n)]; b(i) = b(i) - L(i,j)*b(j);
end
return