Sistemi lineari: metodo diretti
Ana Alonso
University of Trento
3-10 ottobre 2013
Sistemi triangolari
a1,1 0 0 . . . 0 0
a2,1 a2,2 0 . . . 0 0
a3,1 a3,2 a3,3 . . . 0 0 ..
. ..
. . .. ...
an−1,1 an−1,2 an−1,3 . . . an−1,n−1 0 an,1 an,2 an,3 . . . an,n−1 an,n
x1
x2
x3
.. . xn−1
xn
=
b1
b2
b3
.. . bn−1
bn
Sostituzione in avanti:
x1= b1/a1,1
For i = 2 : n xi = a1
i ,i
bi −Pi −1 j =1ai ,jxj
Sistemi triangolari
x1= b1/a1,1
For i = 2 : n xi = a1
i ,i
bi −Pi −1 j =1ai ,jxj Implementazione:
[c1, c2, c3]
d1 d2
d3
= c1d1+ c2d2+ c3d3=
3
X
j =1
cjdj
Pi −1
j =1ai ,jxj A(i,1:i-1)*x(1:i-1,1) Esercizio. Scrivere una funzione di Matlab che implementi il metodo della sostituzione in avanti.
Sostituzione in avanti
function [x]=forward(L,b)
% x=forward(L,b)
% Risolve il sistema triangolare inferiore Lx=b.
% Usa il metodo della sostituzione in avanti.
[n,m]=size(L);
if n~=m, error(’Solo sistemi quadrati’); end
if min(abs(diag(L)))==0, error(’Sistema singolare’); end x(1,1)=b(1)/L(1,1);
for i=2:n
x(i,1)=(b(i)-L(i,1:i-1)*x(1:i-1,1))/L(i,i);
end return
Sistemi triangolari
a1,1 a1,2 a1,3 . . . a1,n−1 a1,n
0 a2,2 a2,3 . . . a2,n−1 a2,n
0 0 a3,3 . . . a3,n−1 a3,n
... ... . .. ... 0 0 0 . . . an−1,n−1 an−1,n
0 0 0 . . . 0 an,n
x1
x2
x3
... xn−1 xn
=
b1
b2
b3
... bn−1 bn
Sostituzione all’indietro:
xn= bn/an,n
For i = n − 1 : −1 : 1 xi = a1
i ,i
bi −Pn
j =i +1ai ,jxj
Esercizio. Scrivere una funzione di Matlab che implementi il metodo della sostituzione all’indietro.
Sostituzione all’indietro
function [x]=backward(U,b)
% x=backward(U,b)
% Risolve il sistema triangolare superiore Ux=b.
% Usa il metodo della sostituzione all’indietro.
[n,m]=size(U);
if n~=m, error(’Solo sistemi quadrati’); end
if min(abs(diag(U)))==0, error(’Sistema singolare’); end x(n,1)=b(n)/U(n,n);
for i=n-1:-1:1
x(i,1)=(b(i)-U(i,i+1:n)*x(i+1:n,1))/U(i,i);
end return
Istruzione condizionale
I Se r `e no negativo calcola la radice quadra
if r >= 0
radice=sqrt(r);
end
I Se r `e no negativo calcola√
r altrimenti scrive “r negativo”.
if r >= 0
radice=sqrt(r);
else
disp(’r negativo’) end
I ax2+ b x + c = 0 disc = b2− 4ac
if disc > 0
disp(’Due radici reali diverse’) elseif disc==0
disp(’Una radice reale doppia’) else
disp(’Due radici complesse coniugate’) end
Operatori e altro
I Operatori relazionali:
< <= > >= == ~=
(Il simbolo “ = “ `e un’assegnazione. Possiamo scrivere a=a+1.)
I Operatori logici:
& | ~
I return: uscita incondizionata dalla funzione.
I error: visualizza il messaggio ed esce dalla funzione.
I break: uscita da un ciclo for o while.
Risoluzione di sistemi lineari
Il comando \ (backslash)
I Se A `e una matrice n × n e b `e un vettore colonna di dimensione n
x=A \ b calcola la soluzione del sistema lineare
A x = b .
I Non calcola l’inversa.
I Usa un algoritmo diverso dipendendo dalla struttura della matrice A.
Il comando inv.
I Calcola esplicitamente l’inversa della matrice A.
I Non `e conveninte usare questo comando per risolvere un sistema lineare perche `e pi`u costoso.
Altri comandi per matrici (e vettori)
I det(A) calcola in determinante della matrice A.
I v=diag(A) se A `e una matrice calcola il vettore con la diagonale di A.
I D=diag(v) se v calcola la matrice diagonale che ha nella diagonale i valori di v.
I M=tril(A) restituisce la parte triangolare inferiore di A.
(Provare anche tril(A,1) o tril(A,-2)).
I M=triu(A) restituisce la parte triangolare superiore di A.
Analogo a tril.
I v=eig(A) calcola gli autovalori di A.
I [M,v]=eig(A) calcola gli autovettori e gli autovalori di A.
I norm(A) calcola la norma 2 di A.
I cond(A) calcola il condizionamento in norma 2 di A.
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
mi ,k = ai ,k(k)/a(k)k,k for j = k + 1 : n
a(k+1)i ,j = ai ,j(k)− mi ,k∗ a(k)k,j end
b(k+1)i = b(k)i − mi ,k∗ bk(k) end
end
U = A(n) c = b(n).
Metodo di eliminazione di Gauss (senza pivotazione)
Implementazione:
A=[A 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+1)=A(k+1:n,k+1:n+1)-A(k+1:n,k)*A(k,k+1:n+1);
end
. .. . . .
ak,k(k) a(k)k,k+1 . . . a(k)k,n b(k)k mk+1,k a(k+1)k+1,k+1 . . . a(k+1)k+1,n b(k+1)k+1
... ... ...
mn,k a(k+1)n,k+1 . . . an,n(k+1) b(k+1)n
Metodo di eliminazione di Gauss (senza pivotazione)
Implementazione:
A=[A 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+1)=A(k+1:n,k+1:n+1)-A(k+1:n,k)*A(k,k+1:n+1);
end
Osservazione:
c1 c2
ce
[d1, d2, d3, d4] =
c1d1 c1d2 c1d3 c1d4 c2d1 c2d2 c2d3 c2d4
c3d1 c3d2 c3d3 c3d4
Metodo di eliminazione di Gauss (senza pivotazione)
function [x]=Gauss(A,b)
% x=Gauss(A,b)
% Risolve il sistema lineare Ax=b.
% Usando il metodo di eliminazione di Gauss senza pivoting.
[n,m]=size(A);
if n~=m, error(’Solo sistemi quadrati’); end A=[A b];
for k=1:n-1
if A(k,k)==0, error(’Elemento pivotale nullo’); end A(k+1:n,k)=A(k+1:n,k)/A(k,k);
A(k+1:n,k+1:n+1)=A(k+1:n,k+1:n+1)-A(k+1:n,k)*A(k,k+1:n+1);
end
if A(n,n)==0, error(’Sistema singolare’); end x(n,1)=A(n,n+1)/A(n,n);
for i=n-1:-1:1
x(i,1)=(A(i,n+1)-A(i,i+1:n)*x(i+1:n,1))/A(i,i);
end return
Metodo di eliminazione di Gauss (senza pivotazione)
function [x]=Gauss(A,b)
% x=Gauss(A,b)
% Risolve il sistema lineare Ax=b.
% Usando il metodo di eliminazione di Gauss senza pivoting.
[n,m]=size(A);
if n~=m, error(’Solo sistemi quadrati’); end A=[A b];
for k=1:n-1
if A(k,k)==0, error(’Elemento pivotale nullo’); end A(k+1:n,k)=A(k+1:n,k)/A(k,k);
A(k+1:n,k+1:n+1)=A(k+1:n,k+1:n+1)-A(k+1:n,k)*A(k,k+1:n+1);
end
x=backward(A(:,1:n),A(:,n+1));
return
Pivotazione parziale per righe
1 2 3 1 0 0 4 1 0 5 6 1 0 1 2 1
x1
x2 x3 x4
=
7 5 12
4
m3,2 = 5/0 m4,2 = 1/0 !!!
Per risolvere il sistema lineare bastascambiare due equazionie poi andare avanti col metodo di eliminazione.
Scambio di righe:
A([k,i],:)=A([i,k],:);
Pivotazione parziale per righe (solo se necessario)
function [x]=Gauss(A,b)
% x=Gauss(A,b)
% Risolve il sistema lineare Ax=b.
[n,m]=size(A);
if n~=m, error(’Solo sistemi quadrati’); end A=[A b];
err=0;
for k=1:n-1 if A(k,k)==0
err=1;
for i=k+1:n if A(i,k)~=0
A([k,i],:)=A([i,k],:);
err=0;
break end end end
if err, error(’Matrice singolare’); end A(k+1:n,k)=A(k+1:n,k)/A(k,k);
A(k+1:n,k+1:n+1)=A(k+1:n,k+1:n+1)-A(k+1:n,k)*A(k,k+1:n+1);
end
if A(n,n)==0, error(’Matrice singolare’); end x=backward(A(:,1:n),A(:,n+1));
return
Pivotazione parziale per righe
function [x]=Gauss(A,b)
% x=Gauss(A,b)
% Risolve il sistema lineare Ax=b.
[n,m]=size(A);
if n~=m, error(’Solo sistemi quadrati’); end A=[A b];
for k=1:n-1
npivot=abs(A(k,k));
r=k;
for i=k+1:n
if abs(A(i,k))>npivot npivot=abs(A(i,k));
r=i;
end end
if npivot==0, error(’Matrice singolare’); end if r~=k, A([k,r],:)=A([r,k],:); end
A(k+1:n,k)=A(k+1:n,k)/A(k,k);
A(k+1:n,k+1:n+1)=A(k+1:n,k+1:n+1)-A(k+1:n,k)*A(k,k+1:n+1);
end
if A(n,n)==0, error(’Matrice singolare’); end x=backward(A(:,1:n),A(:,n+1));
return
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 RTR = A
I R triangolare superiore con tutti gli elementi diagonali positivi.
Il metodo di Gauss e la fattorizzazione LU
A =
u1,1 u1,2 u1,3 . . . u1,n−1 u1,n c1 m2,1 u2,2 u2,3 . . . u2,n−1 u2,n c2 m3,1 m3,2 u3,3 . . . u3,n−1 u3,n c3
.. .
.. . mn,1 mn,2 mn,3 . . . mn,n−1 un,n cn
L =
1 m2,1 1 m3,1 m3,2 1
.. .
.. . ..
.
.. . mn,1 mn,2 mn,3 . . . mn,n−1 1
U =
u1,1 u1,2 u1,3 . . . u1,n−1 u1,n u2,2 u2,3 . . . u2,n−1 u2,n u3,3 . . . u3,n−1 u3,n
...
.. . ...
.. . un,n
L=tril(A,-1)+eye(n) U=triu(A(:,1:end-1))
I Senza pivotazione A = LU.
I Con pivotazione PA = LU essendoP unamatrice di permutazione.
Esercizio
Partendo dal programma che implementa il metodo di eliminazione di Gauss senza pivotazione scrivere una funzione di Matlab che calcoli la fattorizzazione LU di una matrice A.
function A=mylu0(A) [n,m]=size(A);
if n~=m, error(’Solo matrici quadrate’); end for k=1:n-1
if A(k,k)==0, error(’Elemento pivotale nullo’); end 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); end
Esercizio
Partendo dal programma che implementa il metodo di eliminazione di Gauss senza pivotazione scrivere una funzione di Matlab che calcoli la fattorizzazione LU di una matrice A.
function A=mylu0(A) [n,m]=size(A);
if n~=m, error(’Solo matrici quadrate’); end for k=1:n-1
if A(k,k)==0, error(’Elemento pivotale nullo’); end 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);
end
LU=PA
function [A,p]=mylu1(A) [n,m]=size(A);
if n~=m, error(’Solo matrici quadrate’); end p=1:n;
for k=1:n-1
npivot=abs(A(k,k));
r=k;
for i=k+1:n
if abs(A(i,k))>npivot npivot=abs(A(i,k));
r=i;
end end
if npivot==0, error(’Matrice singolare’); end
if r~=k, A([k,r],:)=A([r,k],:); p([k,r])=p([r,k]); end 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);
end
