Fattorizzazione LU ed eliminazione gaussiana in Matlab

(1)

Fattorizzazione LU ed eliminazione gaussiana in Matlab

Alvise Sommariva

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

(2)

Soluzione di sistemi lineari con

backslash

L’ambiente Matlab utilizza varie strategie per risolvere i sistemi lineari. Il

comando per fare questa operazione ´

e

mldivide

o alternativamente il

backslash

.

A tal proposito, digitando ”

help \

” ricaviamo

>> h e l p \

\ B a c k s l a s h or l e f t m a t r i x d i v i d e .

A\B is the m a t r i x d i v i s i o n of A i n t o B , w h i c h is r o u g h l y the

s a m e as INV ( A )∗B , except it is computed in a different way .

If A is an N−by−N m a t r i x and B is a c o l u m n v e c t o r w i t h N c o m p o n e n t s , or a m a t r i x w i t h s e v e r a l s u c h columns , t h e n X = A\B is the s o l u t i o n to the e q u a t i o n A∗X = B . A warning m e s s a g e is p r i n t e d i f A is b a d l y s c a l e d or n e a r l y s i n g u l a r . A\ EYE ( S I Z E ( A ) ) p r o d u c e s the i n v e r s e of A .

. . .

See a l s o ldivide , rdivide , m r d i v i d e . R e f e r e n c e p a g e f o r m l d i v i d e

O t h e r f u n c t i o n s n a m e d m l d i v i d e >>

(3)

Soluzione di sistemi lineari con

backslash

Il comando

mldivide

´

e molto complicato. Matlab distingue tra varie tipologie di

matrici e poi determina il metodo pi´

u adatto. Vediamo il seguente esempio

>> s p p a r m s(’ s p u m o n i ’, 1 ) ; >> A=g a l l e r y(’ p o i s s o n ’, 3 ) ; % m a t r i c e d i t i p o P o i s s o n ( f o r m u l a z i o n e c o m p a t t a ) >> f u l l( A ) % m a t r i c e d i t i p o P o i s s o n ( d i s p l a y c o m p o n e n t e p e r c o m p o n e n t e ) a n s = 4 −1 0 −1 0 0 0 0 0 −1 4 −1 0 −1 0 0 0 0 0 −1 4 0 0 −1 0 0 0 −1 0 0 4 −1 0 −1 0 0 0 −1 0 −1 4 −1 0 −1 0 0 0 −1 0 −1 4 0 0 −1 0 0 0 −1 0 0 4 −1 0 0 0 0 0 −1 0 −1 4 −1 0 0 0 0 0 −1 0 −1 4 >> b=ones (s i z e( A , 1 ) , 1 ) ; % t e r m i n e n o t o >> x=m l d i v i d e ( A , b ) ; % r i s o l v e Ax=b sp \ : b a n d w i d t h = 3+1+3. sp \ : is A d i a g o n a l ? no .

sp \ : is b a n d d e n s i t y ( 0 . 6 4 7 0 5 9 ) > b a n d d e n ( 0 . 5 ) to try band ed solver ? yes . sp \ : is LAPACK ’ s b a n d e d s o l v e r s u c c e s s f u l ? yes .

>>

(4)

Soluzione di sistemi lineari con

backslash

(5)

Soluzione di sistemi lineari con

backslash

Vediamo un esempio di uso del comando

backslash

.

(6)

Fattorizzazione LU

Se ´

e disponibile una fattorizzazione

PA=LU

, ´

e possibile risolvere il sistema

lineare Ax = b in O(n

2

) operazioni mediante l’applicazione dei metodi di

sostituzione in avanti e all’indietro.

Il comando

lu

calcola la corrispettiva fattorizzazione di una matrice A con n

righe e colonne, ottenuta mediante eliminazione di Gauss con pivoting.

La chiamata

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

determina le matrici

L = (l

i ,j

) ∈ R

n×n

triangolare inferiore, ovvero tale che l

i ,j

= 0 se j > i con

l

i ,i

= 1,

U = (u

i ,j

) ∈ R

n×n

triangolare superiore, ovvero tale che u

i ,j

= 0 se j < i ,

P = (p

i ,j

) ∈ R

n×n

di

permutazione, ovvero con esclusivamente un valore

non nullo e pari a 1 per ogni riga e colonna,

(7)

Fattorizzazione LU: Esempio 1

Vediamo un primo esempio.

(8)

Fattorizzazione LU: Esempio 2

Vediamo un secondo esempio.

(9)

Soluzione di sistemi lineari con fattorizzazione LU

Supponiamo sia

A ∈ R

n×n

_{, con det(A) 6= 0,}

b ∈ R

n

,

In tali ipotesi, esiste un unico x

∗

_{∈ R}

n

_{che risolva il}

_{sistema lineare Ax = b.}

Sotto queste ipotesi si pu`

o provare che se PA = LU, allora necessariamente

det(P) = ±1, P

−1

= P

T

,

det(L) = 1

det(U) 6= 0.

Quindi, posto

Pb = c

, visto che P ´ınvertibile, abbiamo

Ax = b ⇔ PAx = Pb ⇔ LUx = Pb ⇔ LUx = c.

Di conseguenza

posto

y = Ux

, y `

e soluzione del sistema triangolare inferiore Ly = c;

calcolato y , la soluzione x del sistema Ax = b `

e pure soluzione del sistema

triangolare superiore

Ux = y;

Quindi per risolvere Ax = b, nota la fattorizzazione

PA=LU

:

1

si valuta

c=P*b

;

(10)

Soluzione di sistemi lineari con

metodo LU

In generale per risolvere il sistema lineare, utilizzandobackslashsolo per risolvere convenientemente i sistemi triangolari, possiamo scrivere la seguente funzione fattorizzazione LUper risolvere i sistemi lineari.

f u n c t i o n x=m e t o d o _ L U ( A , b )

[ L , U , P ]=l u( A ) ; % f a t t o r i z z a z i o n e PA=LU

c=P∗b ;

y=L\c ; % s i s t e m a t r i a n g o l a r e i n f e r i o r e

x=U\y ; % s i s t e m a t r i a n g o l a r e s u p e r i o r e

Vogliamo paragonarlo con il comando dibackslashsu alcune matrici di speciale interesse introdotte nellagallerydi Matlab.

>> h e l p g a l l e r y

g a l l e r y H i g h a m t e s t m a t r i c e s .

[ out1 , out2 , . . . ] = g a l l e r y( matname , param1 , param2 , . . . )

(11)

Soluzione di sistemi lineari con

metodo LU

Implementiamo il seguente confronto tra

metodo LU

e

backslash

.

f u n c t i o n t e s t _ m e t o d o _ L U w a r n i n g off ; % non s c r i v e ” w a r n i n g s ” f o r n = 5 : 5 : 2 0 A=g a l l e r y(’ c h e b v a n d ’, n ) ; b=r a n d( n , 1 ) ; condA=c o n d e s t( A ) ; % r i s o l u z i o n e c o n ” metodo LU ” t i c; x _ L U=m e t o d o _ L U ( A , b ) ; t _ m e t o d o _ L U=t o c; % tempo i m p i e g a t o % r i s o l u z i o n e c o n ” b a c k s l a s h ” t i c; x _ b a c k s l a s h=A\b ; t _ b a c k s l a s h=t o c; % tempo i m p i e g a t o % e r r o r e norma 2 s o l u z i o n e

err=norm( x_LU−x _ b a c k s l a s h ) /norm( x _ b a c k s l a s h ) ;

% e r r o r e r e l a t i v o s o l u z i o n e b a c k s l a s h

r e s i d u o _ b a c k s l a s h=norm( b−A∗ x_backslash ) /norm( b ) ;

% e r r o r e f a t t o r i z z a z i o n e LU

[ L , U , P ]=l u( A ) ; errLU=norm( P∗A−L∗U ) ;

(12)

Soluzione di sistemi lineari con

metodo LU

Il codice

mediante la gallery di Matlab, definisce una particolare matrice di Vandermonde di ordinene la assegna adAe di seguito un vettorebrandom, calcolando infine un approssimazione del numero di condizionamentocondAdella matriceA; calcola un approssimazionex LUsoluzione del sistema Ax = b con la routine

metodo LUe ”stima” il tempo impiegato per determinare l’approssimazione; calcola un approssimazionex backslashsoluzione del sistema Ax = b con il comandobackslashe ”stima” il tempo impiegato per determinare

l’approssimazione;

valuta l’errore relativoerrin norma 2, tra le due approssimazioni; valuta il residuo relativo

residuo backslash =kb − A ∗ x backslashk2 kbk2

(13)

Soluzione di sistemi lineari con

metodo LU

Otteniamo quali risultati

>> t e s t _ m e t o d o _ L U

n : 5 c o n d: 1 . 4 9 3 e+03 err LU : 3 . 1 6 5 e−16

err . LU vs b a c k s . : 0 . 0 0 0 e+00 res . r e l a t i v o : 4 . 5 0 9 e−15 t e m p o i m p i e g a t o : LU : 1 . 7 0 9 e−04 b a c k s l a s h : 7 . 1 9 1 e−05 n : 10 c o n d: 4 . 8 4 6 e+07 err LU : 7 . 2 9 5 e−16

err . LU vs b a c k s . : 0 . 0 0 0 e+00 res . r e l a t i v o : 1 . 4 8 6 e−02 t e m p o i m p i e g a t o : LU : 2 . 2 2 5 e−04 b a c k s l a s h : 2 . 8 0 2 e−04 >>

che mostrano che

i tempi di calcolo per risolvere problemi di piccola dimensione siano meno di millesimi di secondo;

(14)

Soluzione di sistemi lineari con

metodo LU

Partendo dalla demo precedente definiamo la routinetest metodo LU2per cui: utilizziamo il ciclo for: for n=200:200:1000invece difor n=5:5:20; sostituiamoA=gallery(’minij’,n);aA=gallery(’chebvand’,n). La gallery relativa aminijdefinisce la matrice A = (ai ,j)simmetrica e definita positivatale cheai ,j= min(i , j ).Lanciando tale routine, ricaviamo:

>> t e s t _ m e t o d o _ L U 2

n : 200 c o n d: 8 . 0 4 0 e+04 err LU : 0 . 0 0 0 e+00

err . LU vs b a c k s . : 5 . 8 1 9 e−16 res . r e l a t i v o : 3 . 8 9 0 e−14 t e m p o i m p i e g a t o : LU : 3 . 9 2 2 e−03 b a c k s l a s h : 1 . 9 4 4 e−03 n : 400 c o n d: 3 . 2 0 8 e+05 err LU : 0 . 0 0 0 e+00

(15)

Soluzione di sistemi lineari con

metodo LU

Dall’esperimento numerico su

minij

si vede che:

Le matrici questa volta

non sono piccole

, ma comunque il tempo di calcolo

e’ ancora nell’ordine dei centesimi/millesimi di secondo;

I

condizionamenti

delle matrici non sono piccoli, ma molto inferiori a quelli

visti nell’esempio precedente e i risultati ottenuti sono relativamente

accurati.

Le fattorizzazioni LU sono

molto accurate

.

Il metodo LU e il

backslash

di Matlab

non forniscono gli stessi risultati

ma sono comunque entrambi simili, per´

o questa volta il

backslash

sembra pi`

u rapido

.

Nonostante le matrici abbiano comunque condizionamenti rilevanti, le

(16)

Esercizi. La routine

metodo LU

e la soluzione di sistemi lineari

Esercizio (risolto)

Si scriva uno scripttest metodo LU3che

1 ponga n=100;

2 definisca, mediante un opportuno ciclo-for nella variabile delle righe e di seguito uno nella variabile delle colonne, contenente una opportuna istruzione

condizionale, la matrice A = (A(i , j )) ∈ Rn×nche ha per componenti

A(i , j ) = ( _i

j, 1 ≤ i ≤ j ≤ n j

i, 1 ≤ j ≤ i ≤ n

3 definisca, mediante un opportuno ciclo-for, il termine noto b = (b(i ))i∈ Rn×1 (vettore colonna)

bi =

−1, i dispari 1, i pari

Si osservi che per sapere se un numero k ´e pari si digitarem(k,2). Se il risultato ´

e 0 allora il numero ´e pari, altrimenti ´e dispari.

4 Si risolva Ax = b con la routinemetodo LU.

(17)

Esercizi. La routine

metodo LU

e la soluzione di sistemi lineari

La soluzione a quanto richiesto ´e lo scripttest metodo LU3definito da: f u n c t i o n t e s t _ m e t o d o _ L U 3 n =100; % d e f i n i z i o n e m a t r i c e A f o r i =1: n f o r j =1: n i f i <= j A ( i , j )=i / j ; e l s e A ( i , j )=j / i ; end end end % d e f i n i z i o n e t e r m i n e n o t o f o r k =1: n i f rem( k , 2 ) == 0%i n d i c e p a r i b ( i , 1 ) =+1; e l s e b ( i , 1 ) =−1; end end % s o l u z i o n e s i s t e m a l i n e a r e x=m e t o d o _ L U ( A , b ) ; % v a l u t a z i o n e r e s i d u o r e l a t i v o

err=norm( b−A∗x ) /norm( b ) ;

f p r i n t f(’ \n \ t r e s i d u o r e l a t i v o : %1.1 e \n ’, err ) ; Dal codice otteniamo