Condizionamento di sistemi lineari.

(1)

Condizionamento di sistemi lineari.

´

Angeles Mart´ınez Calomardo e Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica Pura e Applicata

10 dicembre 2012

(2)

Risoluzione di un sistema lineare in Matlab/Octave

I _{Il sistema lineare Ax = b si risolve in Matlab/Octave con}

il comandoA\b.

I Se A `e una matrice quadrata invertibile generale, l’operatore \ restituisce la soluzione x = A−1b calcolata con il metodo di eliminazione di Gauss con pivoting.

(3)

Risoluzione di un sistema lineare in Matlab/Octave

I Nel caso di termine noto con pi`u colonne, la scritturaA\B, con B = [b1b2. . . bm] risolve AX = B, ovvero gli m sistemi

lineari Axi = bi, con X = [x1x2. . . xm].

I Nel caso di sistemi sovradeterminati (pi`u equazioni che incognite), il comando\ calcola automaticamente la soluzione ai minimi quadrati.

(4)

Condizionamento dei sistemi lineari

Consideriamo il sistema di equazioni lineari Ax = b, con A ∈ Rn×n

e b ∈ Rn.

In seguito ad una perturbazione δb sul termine noto b (per semplicit`a, assumiamo δA = 0 ∈ Rn×n), si ha un errore sul risultato δx = e = x − ¯x .

Il sistema che si risolve `e

A(x + δx ) = b + δb (1)

Da cui, poich`e Ax = b, si ha

Aδx = b; δx = A−1δb (2)

Rispetto ad una qualsiasi norma matriciale indotta da quella vettoriale, seguono le maggiorazioni

(5)

Condizionamento di un sistema lineare

Moltiplicando tra di loro la (3) e la (4), si ha infine kδxk kxk ≤ kAk kA −1_k kδbk kbk , (5) dove κ(A) = kAk kA−1k (6)

si chiamanumero di condizionamentodella matrice A.

Il numero di condizionamento, κ(A), `e sempre maggiore o uguale a 1 in quanto si ha:

1 = kI k = kAA−1k ≤ kAk kA−1k = κ(A)

(6)

Malcondizionamento

Considerando che A(x + δx ) = b + δb e quindi

A¯x = b + δb =⇒ δb = A¯x − b = −r

la seguente espressione lega la norma dell’errore a quella del residuo (relativi):

kx − ¯x k

kxk ≤ K (A)

kr k kbk.

I Per valori molto grandi di κ(A), diciamo per κ(A) > 103, l’errore relativo sulla soluzione pu`o essere molto grande anche se `e piccolo l’errore relativo sui dati.

I Vale a dire che a residuo piccolo pu`o non corrispondere un errore piccolo. Si parla allora di malcondizionamento del sistema o, per abuso di linguaggio, della matrice.

I Pi`u grande `e il condizionamento, meno accurata potrebbe essere la soluzione del sistema lineare.

(7)

Numero di condizionamento in Matlab/Octave

Comandocond

Il numero κ(A) di una matrice definito come kAk2· kA−1k2 si

calcola in Matlab/Octave con il comandocond.

>> A = [ 4 −1 2 ; 1 3 1 ; 0 −3 5 ] A = 4 −1 2 1 3 1 0 −3 5 >> c o n d( A ) a n s = 2 . 4 2 4 9

Specificando come secondo parametro del comandocond uno tra

1,inf,frosi ottiene rispettivamente il numero di condizionamento κ(A) = kAk · kA−1k in norma 1, ∞ e di Frobenius.

(8)

Esempi di matrici malcondizionate

Matrici di Hilbert

I Una classe di matrici malcondizionate `e fornita dalle matrici di Hilbert di ordine n i cui elementi sono hij =

1 1 + i + j.

I _{In Matlab/Octave tali matrici si creano tramite il}

(9)

Esempi di matrici malcondizionate

Matrici di Hilbert

Il seguente script (scripthilb.m) crea le matrici di Hilbert di ordine n, per n = 3, . . . , 15 e ne calcola il numero di condizionamento.

f o r n =3:15

H=h i l b( n ) ; k=c o n d( H ) ;

f p r i n t f(’ \ n \ t [ N ] %3d [COND] %6.4 e ’, n , k )

end

I numeri di condizionamento calcolati sono:

(10)

Esempi di matrici malcondizionate

Il seguente script (solhilb.m) genera la matrice di Hilbert H di ordine 12 e risolve il sistema lineare Hx = b, dove b `e stato calcolato in modo che la soluzione esatta del sistema sia x = [1, · · · 1]T_{. Lo script calcola anche il numero di}

condizionamento di H e l’errore e il residuo relativi.

n = 1 2 ; x v e r a = o n e s ( n , 1 ) ; H = h i l b( n ) ; k a p p a = c o n d( H ) ; f p r i n t f(’ \ n \ t [COND K 2 (H) ] %3.3 e ’, kappa ) ; b = H∗ xvera ; x = H \ b ;

e r r _ r e l = norm( x−xvera ) /norm( xvera ) ;

f p r i n t f(’ \ n \ t [ ERRORE RELATIVO ] %3.3 e ’, e r r _ r e l ) ; r e s _ r e l = norm( b−H∗x ) /norm( b ) ;

f p r i n t f(’ \ n \ t [ RESIDUO RELATIVO ] %3.3 e ’, r e s _ r e l ) ;

f p r i n t f(’ \ n ’) ;

(11)

Commenti all’esercizio

L’esecuzione dello script solhilb.m fornisce i seguenti risultati

>> s o l h i l b [ COND K_2 ( H ) ] 1 . 6 4 1 e+16 [ ERRORE R E L A T I V O ] 3 . 3 6 9 e−04 [ R E S I D U O R E L A T I V O ] 8 . 3 7 9 e−16 >>w a r n i n g : matrix s i n g u l a r to m a c h i n e precision , r c o n d = 2 . 4 5 3 3 9 e−17 w a r n i n g : a t t e m p t i n g to f i n d m i n i m u m norm s o l u t i o n w a r n i n g : m a t r i x s i n g u l a r to m a c h i n e p r e c i s i o n , r c o n d = 2 . 4 6 9 6 3 e−17 w a r n i n g : a t t e m p t i n g to f i n d m i n i m u m norm s o l u t i o n w a r n i n g : d g e l s d : r a n k d e f i c i e n t 12 x12 matrix , r a n k = 11 Si osserva che:

I il residuo relativo `e inferiore alla precisione di macchina mentre l’errore relativo `e dell’ordine di 10−4.

I non sorprende: il numero di condizionamento `e molto grande. I un warning indica che la matrice `e molto malcondizionata e

quindi i risultati potrebbero non essere attendibili.

(12)

Esempi di matrici malcondizionate

Matrice di Vandermonde

Un altro esempio di matrice malcondizionata `e la matrice di Vandermonde di ordine n, definita a partire da un vettore x = (x1, · · · , xn) come Vij = xin−j.

In Matlab/Octave tale matrice si crea con il comando vander(x).

Come esempio, consideriamo lo script vandercond.m in cui si considera la matrice di Vandermonde della base monomiale in n punti equispaziati dell’intervallo [1, 2]:

(13)

Esempi di matrici malcondizionate

Matrice di Vandermonde 102 103 104 105 106 107 108 109 1010 1011 1012 3 4 5 6 7 8 9 10 log(cond(A))

dimensione della matrice n Condizionamento della matrice di Vandermonde

Figura : Grafico in scala semilogaritmica del condizionamento della matrice di Vandermonde al crescere della dimensione n.

(14)

Effetti del malcondizionamento della matrice di

Vandermonde.

Script illcond.m % x x : n o d i d i i n t e r p o l a z i o n e xx = [ 1 2 0 0 . 5 1 2 0 1 . 5 1 2 0 2 . 5 1203 1204 1 2 0 5 ] ; y = [ 3 1 . 5 1 . 5 1 1 0 ] ; n = l e n g t h( xx ) −1; % g r a d o d e l p o l i n o m i o d i i n t e r p o l a z i o n e % C a l c o l o d e l l ’ i n t e r p o l a n t e t r a m i t e p o l y f i t x v a l = l i n s p a c e( xx ( 1 ) , xx (end) ) ;

c o e f = p o l y f i t( xx , y , n ) ; yval = p o l y v a l( coef , xval ) ;

% C a l c o l o d e l l ’ i n t e r p o l a n t e c o n L a g r a n g e f o r i =1:l e n g t h( xval ) ; yy ( i ) = l a g r a n g e ( xx , y , x v a l ( i ) ) ; end % C a l c o l o d e l p o l . d i i n t p . c o n f u n z i o n i b a s e m o n o m i a l i A = v a n d e r( xx ) ; d i s p( [’ C o n d i z i o n a m e n t o m a t r i c e d i Vandermonde = ’,n u m 2 s t r( c o n d( A ) ) ] ) c o e f m o n o = A \ y ’ ; y v a l m o n o = p o l y v a l( coefmono , xval ) ; h o l d on ;p l o t( xval , yval , ’ b− ’) ; p l o t( xx , y ,’ k+ ’,’ L i n e w i d t h ’, 3 ) ;

p l o t( xval , yy ,’ r − ’) ; p l o t( xval , yvalmono ,’ g− ’) ; h o l d off ;

l e g e n d(’ g r a d o 5 c o n p o l y f i t ’,’ p u n t i ’,’ g r a d o 5 c o n L a g r a n g e ’,

’ g r a d o 5 c o n Vandermonde ’)

(15)

Esempi di matrici malcondizionate

Matrice di Vandermonde 0 0.5 1 1.5 2 2.5 3 1200 1201 1202 1203 1204 1205

grado 5 con polyfit punti grado 5 con Lagrange grado 5 con Vandermonde

Figura : Esempio degli effetti del malcondizionamento della matrice di Vandermonde sul calcolo del polinomio interpolante.

(16)

Esercizio proposto

Data la matrice A =     15 6 8 11 6 6 5 3 8 5 7 6 11 3 6 9    

1. Si risolvano i sistemi A1x = b1, A2x = b2, A3x = b3 dove

Ai = Ai, i = 1, 2, 3 e bi = Ai∗ ones(4, 1).

2. Si visualizzi il vettore soluzione di ogni sistema con 14 cifre significative.

3. Si spieghino i risultati ottenuti.