Implementazione in Matlab

L'algoritmo che implementa il metodo del pivoting parziale per fattorizzare la matrice come $PA=LU$.

function [A,P]=fattPALU(A)
%FATTPALU Fattorizza la matrice A come LU tramite il metodo di
%   eliminazione di Gauss applicando il pivoting
%
%   [A,P]=FATTPALU(A)
%
%   I parametri della funzione sono:
%       A -> la matrice quadrata da fattorizzare
%
%   I valori di ritorno sono:
%       A -> la matrice modificata contenente nella parte
%            triangolare superiore U e nella parte strettamente
%            triangolare inferiore L
%       P -> vettore di permutazione
%
%   See Also SOLVEPALU, FATTLU, FATTLDLT, FATTQR
  n=length(A);
  P=1:n;
  for i=1:n-1
     [m,ki]=max(abs(A(i:n,i)));
     if m==0
        disp('Matrice non fattorizzabile perché singolare')
        return
     end;
     ki=ki+i-1;
     if ki>i
        P([i,ki])=P([ki,i]);
        A([i,ki],:)=A([ki,i],:);
     end
     A(i+1:n,i)=A(i+1:n,i)/A(i,i);
     A(i+1:n,i+1:n)=A(i+1:n,i+1:n)-A(i+1:n,i)*A(i,i+1:n);
  end

Invece di utilizzare una matrice di permutazione è stato scelto di utilizzare un vettore di permutazione che contiene al suo interno gli scambi effettuati durante l'algoritmo perché possano poi essere applicati al vettore dei termini noti.

Per quanto riguarda il costo computazionale, oltre a quanto già visto per $A=LU$, il pivoting parziale introduce un costo dovuto ai confronti che sono $n-i$ al passo i-esimo, perciò

\begin{displaymath}\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} \approx n^2\end{displaymath}



Morpheus 2004-01-04