Innanzitutto vediamo qual’` e la funzione Matlab che ci permette di calco- lare il numero di condizione di una matrice:

Francesca Mazzia

Dipartimento Interuniversitario di Matematica Universit` a di Bari

MATLAB:Condizionamento Sistemi Lineari.

Innanzitutto vediamo qual’` e la funzione Matlab che ci permette di calco- lare il numero di condizione di una matrice:

>> help cond

COND Condition number with respect to inversion.

COND(X) returns the 2-norm condition number (the ratio of the largest singular value of X to the smallest). Large condition numbers indicate a nearly singular matrix.

COND(X,P) returns the condition number of X in P-norm:

NORM(X,P) * NORM(INV(X),P).

where P = 1, 2, inf, or ’fro.’

See also RCOND, CONDEST, CONDEIG, NORM, NORMEST.

>> A = [ 9 0 1 2

9 3 2 1

4 8 1 0

8 0 6 7]

A =

9 0 1 2

9 3 2 1

4 8 1 0

8 0 6 7

>> cond(A) ans =

23.5314

La matrice A ha numero di condizione piccolo quindi ` e ben condizionata. Ora costruiamo la matrice di Hilbert che ` e una classica matrice mal condizionata e ci calcoliamo il numero di condizione. L’istruzione hilb(N) genera una matrice N per N con elementi 1/(i+j-1),

>> A = hilb(4);

>> cond(A) ans =

1.5514e+04

>> A = hilb(5);

>> cond(A) ans =

4.7661e+05

Il numero di condizione cresce al crescere di N.

>> A = hilb(10);

>> cond(A) ans =

1.6025e+13

Per N=10 la matrice diventa molto mal condizionata. Proviamo a risolvere un sistema lineare usando la function del Matlab, l’algoritmo ` e stabile, ma la soluzione numerica ` e molto diversa da quella teorica. Costruiamoci un vettore con elementi tutti uguali ad 1

>> x = ones(10,1);

>> b=A*x b =

2.9290 2.0199 1.6032 1.3468 1.1682 1.0349 0.9307 0.8467 0.7773 0.7188

Il nostro sistema lineare ha termine noto b e soluzione teorica x, calcoliamo la soluzione numerica:

>> xn = A\b xn =

1.0000

1.0000

1.0000

1.0000

1.0001 0.9997 1.0005 0.9995 1.0002 0.9999

si vede chiaramente che l’errore ` e molto alto,calcoliamo l’errore relativo

>> norm(xn-x,’inf’)/norm(x,’inf’) ans =

4.7006e-04

Se moltiplichiamo la precisione di macchina per il numero di condizione otteniamo:

>> format short e

>> eps*cond(A) ans =

3.5582e-03

Quando risolviamo il sistema perturbato:

(A + δA)δx = δb − δAx l’errore relativo verifica la seguente disuguaglianza:

kδxk

kxk ≤ kA

kkAk 1 − kA

kkδAk

kδbk

kbk + kδAk kAk

!

e la perturbazione relativa sui dati di input sar` a collegata alla precisione di

macchina perch` e lavoriamo con numeri floating point, in questo caso l’errore

relativo sar` a vicino a eps ∗cond(A) e quindi molto grande, qualsiasi algoritmo

utilizziamo per la soluzione. Calcoliamo il residuo

>> r=A*xn-b r =

0 0 0 0 0 0 0 0 0 0

Il residuo ci dice che abbiamo calcolato una soluzione accurata, ma in realt` a l’errore ` e grande perch` e a matrice ` e mal condizionata. Il condizionamento di una matrice pu` o essere modificato dallo SCALING. Con tale metodo si va alla ricerca di due matrici diagonali D

e D

in modo da minimizzare K(D

AD

).

Esempio:

consideriamo la seguente matrice:

>> A=[1.0000e-010 9.0000e-001 -4.0000e-001 0 9.0000e-001 -4.0000e-001

0 0 1.0000e-010]

A =

1.0000e-010 9.0000e-001 -4.0000e-001 0 9.0000e-001 -4.0000e-001

0 0 1.0000e-010

>> D1=diag([1 1 1e10]) D1 =

1.0000e+000 0 0

0 1.0000e+000 0

0 0 1.0000e+010

>> D1*A ans =

1.0000e-010 9.0000e-001 -4.0000e-001 0 9.0000e-001 -4.0000e-001

0 0 1.0000e+000

>> cond(A,1) ans =

2.6000e+010

>> cond(D1*A,1) ans =

1.8000e+010

>> D2=diag([1e10 1 1]) D2 =

1.0000e+010 0 0

0 1.0000e+000 0

0 0 1.0000e+000

>> A*D2 ans =

1.0000e+000 9.0000e-001 -4.0000e-001 0 9.0000e-001 -4.0000e-001

0 0 1.0000e-010

>> cond(A*D2,1) ans =

2.6000e+010

>> cond(D1*A*D2,1) ans =

3.8000e+000

Esempio:

si consideri la matrice A e il vettore b dati da:

>> format short e

>> A=[1.2969 0.8648;0.2161 0.1441]

A =

1.2969e+00 8.6480e-01 2.1610e-01 1.4410e-01

>> b=[0.8642;0.1440]

b =

8.6420e-01 1.4400e-01

La soluzione esatta del sistema Ax = b ` e:

>> x=A\b x =

2.0000e+00 -2.0000e+00

Sia ora

>> xtilde=[0.9911;-0.4870]

xtilde = 9.9110e-01 -4.8700e-01

e sia

>> r=A*xtilde-b r =

-1.0000e-08 1.0000e-08

Questo valore di r fa intendere che xtilde ` e una buona approssimazione della soluzione esatta anche se in realt` a non lo ` e.

La matrice inversa di A ` e data da:

>> inv(A) ans =

1.4410e+07 -8.6480e+07 -2.1610e+07 1.2969e+08

per cui

>> cond(A,inf) ans =

3.2707e+08

Quindi A ` e mal condizionata.

Fattorizzazione di Cholesky.

Costruiamo una funzione Matlab che ci permette di effettuare la fattoriz- zazione di Cholesky di una matrice A :

function L = fchol(A)

%

% FATTORIZZAZIONE DI CHOLESKY

%

% Dati di input:

% A = matrice quadrata

%

% Dati di output:

% L = matrice triangolare inferiore

% tale che A = L*L’

[n,m]=size(A);

if n ~= m

error(’ERRORE: la matrice di input non e’’ quadrata’) end

L=zeros(n,n);

for k=1:n

if (A(k,k)-sum(L(k,1:k-1).^2))<0

error(’ERRORE: la matrice di input non e’’ definita positiva’) else

L(k,k)=sqrt(A(k,k)-sum(L(k,1:k-1).^2));

for j=k+1:n

L(j,k)=(A(k,j)-sum(L(k,1:k-1).*L(j,1:k-1)))/L(k,k);

end

end

end

Esempio:

>> A=[1 2 3;2 5 4;3 4 8]

A =

1 2 3

2 5 4

3 4 8

>> L=fchol(A)

??? Error using ==> fchol

ERRORE: la matrice di input non e’ definita positiva

>> A=[1 -1 -1;-1 2 0;-1 0 3]

A =

1 -1 -1

-1 2 0

-1 0 3

>> L=fchol(A) L =

1 0 0

-1 1 0

-1 -1 1

>> A-L*L’

ans =

0 0 0

0 0 0

0 0 0

>> help chol

CHOL Cholesky factorization.

CHOL(X) uses only the diagonal and upper triangle of X.

The lower triangular is assumed to be the (complex conjugate) transpose of the upper. If X is positive definite, then R = CHOL(X) produces an upper triangular R so that R’*R = X.

If X is not positive definite, an error message is printed.

[R,p] = CHOL(X), with two output arguments, never produces an error message. If X is positive definite, then p is 0 and R is the same as above. But if X is not positive definite, then p is a positive integer.

When X is full, R is an upper triangular matrix of order q = p-1 so that R’*R = X(1:q,1:q).

When X is sparse, R is an upper triangular matrix of size q-by-n so that the L-shaped region of the first q rows and first q columns of R’*R agree with those of X.

See also CHOLINC, CHOLUPDATE.

Se A ` e definita positiva allora dopo l’istruzione R = chol(A)

la variabile R ` e la matrice triangolare superiore della fattorizzazione di Cho- lesky ed ` e tale che

R

∗ R = A

Infatti:

>> A=[1 -1 -1;-1 2 0;-1 0 3]

A =

1 -1 -1

-1 2 0

-1 0 3

>> R=chol(A) R =

1 -1 -1

0 1 -1

0 0 1

>> A-R’*R ans =

0 0 0

0 0 0

0 0 0

Costruima altre matrici di esempio usando la funzione gallery del Matlab.

Esempio:

>> A = gallery(’minij’,5) A =

1 1 1 1 1

1 2 2 2 2

1 2 3 3 3

1 2 3 4 4

1 2 3 4 5

genera una matrice simmetrica e definita positiva. Calcoliamo gli autovalori di A:

>> eig(A) ans =

2.7155e-01 3.5325e-01 5.8296e-01 1.4487e+00 1.2344e+01

sono tutti positivi. Calcoliamo la fattorizzazione di Cholesky:

>> R = chol(A) R =

1 1 1 1 1

0 1 1 1 1

0 0 1 1 1

0 0 0 1 1

0 0 0 0 1

>> R’*R ans =

1 1 1 1 1

1 2 2 2 2

1 2 3 3 3

1 2 3 4 4

1 2 3 4 5

Costruimoci una matrice simmetrica ma non definita positiva:

>> A = [ 1 3 5; 3 1 2; 5 2 1]

A =

1 3 5

3 1 2

5 2 1

>> eig(A) ans =

-4.1284e+00 -7.1069e-01 7.8391e+00

e proviamo ad eseguire la fattorizzazione di CHOLESKY:

>> R = chol(A)

??? Error using ==> chol

Matrix must be positive definite.

>>

Si verifica un errore perche’ la fattorizzazione esiste solo per matrici definite

positive.