Sistemi lineari: metodi diretti II

Sistemi lineari: metodi diretti II

Ana Alonso

Dipartimento di Matematica - Universit`a di Trento

9 ottobre 2014

Metodo di eliminazione di Gauss (senza pivotazione)

Ax = b ⇔ Ux = c U matrice triangolare superiore.

for k = 1 : n − 1 for i = k + 1 : n

m

= a

/a

for j = k + 1 : n

a

= a

− m

∗ a

end

b

= b

− m

∗ b

end

end

U = A

c = b

.

Metodo di eliminazione di Gauss (senza pivotazione)

function x=Gauss0(A,b) x=zeros(size(b));

M=zeros(size(A));

n=length(b);

for k=1:n-1 for i=k+1:n

M(i,k)=A(i,k)/A(k,k);

for j=k+1:n

A(i,j)=A(i,j)-M(i,k)*A(k,j);

end

b(i)=b(i)-M(i,k)*b(k);

end end

% Sostituzione all’indietro.

x(n)=b(n)/A(n,n);

for i= n-1:-1:1

x(i)=(b(i)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);

end

Nell’implementazione non si azzerano gli elementi sotto la

diagonale. Ma la sostituzione all’indietro risolve [triu(A)]x = b.

Metodo di eliminazione di Gauss (senza pivotazione)

Possiamo salvare i moltiplicatori sotto la diagonale.

function x=Gauss1(A,b) x=zeros(size(b));

n=length(b);

for k=1:n-1 for i=k+1:n

A(i,k)=A(i,k)/A(k,k); % Moltiplicatori!

for j=k+1:n

A(i,j)=A(i,j)-A(i,k)*A(k,j);

end

b(i)=b(i)-A(i,k)*b(k);

end end

% Sostituzione all’indietro.

x(n)=b(n)/A(n,n);

for i= n-1:-1:1

x(i)=(b(i)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);

end

Metodo di eliminazione di Gauss (senza pivotazione)

Possiamo sfruttare meglio le operazioni matriciali di Matlab.

function x=Gauss2(A,b) x=zeros(size(b));

n=length(b);

for k=1:n-1

A(k+1:n,k)=A(k+1:n,k)/A(k,k);

A(k+1:n, k+1:n) = A(k+1:n, k+1:n)- A(k+1:n,k)*A(k,k+1:n);

b(k+1:n)=b(k+1:n)-A(k+1:n,k)*b(k);

end

% Sostituzione all’indietro.

x(n)=b(n)/A(n,n);

for i= n-1:-1:1

x(i)=(b(i)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);

end

Metodo di eliminazione di Gauss (senza pivotazione)

Senza pivotazione il metodo di Gauss fornisce anche la fattorizzazione LU della matrice A.

function [x,L,U]=Gauss3(A,b) x=zeros(size(b));

n=length(b);

for k=1:n-1

A(k+1:n,k)=A(k+1:n,k)/A(k,k);

A(k+1:n, k+1:n) = A(k+1:n, k+1:n)- A(k+1:n,k)*A(k,k+1:n);

b(k+1:n)=b(k+1:n)-A(k+1:n,k)*b(k);

end

% Sostituzione all’indietro.

x(n)=b(n)/A(n,n);

for i= n-1:-1:1

x(i)=(b(i)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);

end

L=tril(A,-1)+eye(n); % Elementi sotto la diagonale principale

% ed elementi diagonali ugulai a uno.

U=triu(A); % Parte triangolare superiore.

Pivotazione parziale per righe

Nella colonna k-esima

I

cerco una riga r con k ≤ r ≤ n tale che

|a

| = max

k≤i ≤n

|a

| ;

r=k;

p=abs(A(k,k));

for i=k+1:n aux=abs(A(i,k));

if aux > p p=aux;

r=i;

end end

I

scambio le righe r e k della matrice e del termine noto.

A([k,r],:)=A([r,k],:);

b([k,r])=b([r,k]);

Pivotazione parziale per righe

function [x,L,U,P]=GaussP0(A,b) x=zeros(size(b));

n=length(b);

P=1:n; % NEW!!

for k=1:n-1

% Cerco l’elemento pivot r=k; p=abs(A(k,k));

for i=k+1:n aux=abs(A(i,k));

if aux > p, p=aux; r=i; end end

% Scambio le righe k e r in A e b A([k,r],:)=A([r,k],:); b([k,r])=b([r,k]);

P([k,r])=P([r,k]); % NEW!!

A(k+1:n,k)=A(k+1:n,k)/A(k,k);

A(k+1:n, k+1:n) = A(k+1:n, k+1:n)- A(k+1:n,k)*A(k,k+1:n);

b(k+1:n)=b(k+1:n)-A(k+1:n,k)*b(k);

end

% Sostituzione all’indietro.

x(n)=b(n)/A(n,n);

for i= n-1:-1:1

x(i)=(b(i)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);

end

L=tril(A,-1)+eye(n); % Matrice L.

U=triu(A); % Matrice U.

Pivotazione parziale per righe

I

Se si fa la pivotazione per righe LU 6= A.

I

Se P la matrice di permutazione corrispondente agli scambi fatti

LU = PA .

I

In linguaggio Matlab

L ∗ U = A(P, :)

essendo P il vettore che indica gli scambi fatti.

Pivotazione parziale per righe

function [x,L,U,P]=GaussP(A,b) x=zeros(size(b));

n=length(b);

P=1:n;;

for k=1:n-1

% Cerco l’elemento pivot

r=find(abs(A(k:n,k))==max(abs(A(k:n,k))),1); % Comando find!!

r=r+k-1;

% Scambio le righe k e r in A e b A([k,r],:)=A([r,k],:); b([k,r])=b([r,k]);

P([k,r])=P([r,k]);

A(k+1:n,k)=A(k+1:n,k)/A(k,k);

A(k+1:n, k+1:n) = A(k+1:n, k+1:n)- A(k+1:n,k)*A(k,k+1:n);

b(k+1:n)=b(k+1:n)-A(k+1:n,k)*b(k);

end

% Sostituzione all’indietro.

x(n)=b(n)/A(n,n);

for i= n-1:-1:1

x(i)=(b(i)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);

end

L=tril(A,-1)+eye(n); % Matrice L.

U=triu(A); % Matrice U.

Il comando lu e il comando chol

[L,U,P]=lu(A)

I

L U = P A

I

L triangolare inferiore con gli elementi diagonali uguali a 1.

I

U triangolare superiore.

I

P matrice di permutazioni.

[L,U]=lu(A)

I

L U = A

I

L non ` e triangolare inferiore ma una permutazione di righe la rende triangolare inferiore con tutti gli elementi diagonali uguali a 1.

I

U triangolare superiore.

R=chol(A)

I

A deve essere simmetrica definita positiva

I

R

R = A

I

R triangolare superiore con tutti gli elementi diagonali positivi.

Matrice di Hilbert

I

hilb(n) calcola la matrice di Hilbert di dimensione n.

h

= 1/(i + j − 1).

I

Esercizio:

Sia A la matrice di Hilbert 8 × 8, sia b=A*ones(8,1) e c=b+1.e-10*rand(8,1).

I

Usando i comandi di Matlab risolvere Ax = b e Ay = c.

I

Calcolare

e confrontare con

.

I

Calcolare il numero di condizionamento di A.

I

Commentare i risultati.