next up previous contents
Next: Esempio Fattorizzazione con Pivoting Up: Fattorizzazione LU con Pivoting Previous: Osservazione   Indice

Algoritmo fattorizzazione Pivoting Parziale

function[A,p]=fattorizzazionePivotingParziale(A)
%Questo  il metodo di fattorizzazione con Pivoting Parziale
%Calcola la fattorizzazione della matrice A=LU 
%Prima di applicare un passo di Gauss si moltiplica la matrice A per una
%matrice di permutazione elementare che permuta le righe di A in modo che
%l'elemento in posizione a_ii sia il massimo della colonna i-esima e
%quindi, essendo la matrice non singolare, diverso da zero.
%Questo permette di evitare il controllo a_ii diverso da zero per ogni i

%PREREQUISITI: la matrice A deve essere non singolare

%OCCUPAZIONE DI MEMORIA: n^2 perch  possibile memorizzare L ed U nella
%matrice A

%COSTO OPERAZIONI: 2/3 n^3 flops che equivale al metodo di eliminazione di
%Gauss, in pi vi sono ad ogni ciclo n-1 confronti per trovare il massimo
%della colonna ed 2*n spostamenti di memoria (2*n^2 spostamenti ed 1/2*n^2
%confronti)

n=length(A);
p=1:n;
mi=0;
ki=0;
for i=1:n-1
    %begin Pivoting
    [mi,ki]=max(abs(A(i:n,i))); %mi  il valore massimo 
    			        %che si trova in posizione ki
    ki=ki+i-1;
    if(mi==0)
        error('La matrice  singolare');
    end
    if(ki>i)
        A([i,ki],:)=A([ki,i],:);
        p([i,ki])=p([ki,i]);
    end
    %end Pivoting
    %begin Gauss
    A(i+1:n,i)=A(i+1:n,i)/A(i,i); %n-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);%2*(n-i)^2
    %end Gauss
end
end
Come possiamo notare l'algoritmo si divide in due parti, una per il pivoting (scambio delle righe della matrice) ed un'altra per la fattorizzazione di Gauss.
Il costo del pivoting di n-1 confronti e 2*n spostamenti di memoria lungo le righe; in totale il pivoting fa \(\frac{1}{2}n^{2}\) confronti e $2*n^{2}$ spostamenti.



2005-09-05