Fattorizzazione LU ed eliminazione gaussiana

Fattorizzazione LU ed eliminazione gaussiana

Alvise Sommariva Universit`a degli Studi di Padova

Introduzione

Problema. (Sistema lineare)

Sia A ∈ Rn×n una matrice a coeff. reali, b ∈ Rn un vettore

colonna e supponiamo di dover calcolare un vettore colonna

x∗∈ Rn _cosicch`e

A · x∗= b.

Nota.

Come `e noto questo problema ha soluzione unica x∗ se e solo se

det (A) 6= 0

Matrici di permutazione

Definizione (Matrice di permutazione)

Una matrice P si dice dipermutazione se si ottiene permutando

le righe della matrice identica I .

Esempio

In questo esempio, P `e ottenuta da I scambiando la prima riga con

Propriet`

a della matrice di permutazione

Nota.

Se P ∈ Rn×n si ottiene dalla matrice identica In∈ Rn×n

scambiando la i -sima riga con la j (i )-sima allora la matrice B = PA si ottiene da A scambiando la j (i )-sima riga con la i -sima.

La matrice P ∈ Rn×n `e unitaria cio`e PPT = PTP = In.

Essendo PPT = PTP = In, la matrice P `e invertibile e ha

inversa P−1 = PT. Ci`o implica che det(P) 6= 0.

1 Se A = BC per il teorema di Binet, allora

det(A) = det(B) det(C );

2 det(In) = 1; 3 det(P) = det(PT_). Quindi

Matrici triangolari

Definizione (Matrici triangolari)

Una matrice A = (ai ,j) si dice

triangolare superiore, se ai ,j = 0 per i > j ;

triangolare inferiore, se ai ,j = 0 per i < j .

Fattorizzazione LU

Problema. (Fattorizzazione LU)

Sia A ∈ Rn×n. Determinare,se esistono,

L = li ,j triangolare inferiore con elementi diagonali uguali a 1,

cio`e li ,i = 1,

U triangolare superiore, cosicch`e

A = LU.

Nota.

Fattorizzazione LU

Teorema (Fattorizzazione LU e submatrici principali)

Sia A ∈ Rn×n.

Si supponga che tutte le sottomatrici principali di testa A(k) = (ai ,j)i ,j =1,...,k, k = 1, . . . , n − 1 siano non singolari.

Allora esiste ed `e unica la fattorizzazione LU di A.

Nota. (Controesempio)

Non tutte le matrici posseggono la fattorizzazione LU. Un esempio

in cui non esistono tali L, U per cui A = LU `e la matrice

Fattorizzazione PA=LU

Teorema (Fattorizzazione PA=LU)

Sia A ∈ Rn×n. Allora esiste una matrice di permutazione P tale

che PA = LU. Di conseguenza

La fattorizzazione A = LU non `e sempre possibile.

La fattorizzazione PA = LU `e sempre possibile.

Nota. (Pivoting)

Per determinare la fattorizzazione PA = LU si usa una variante dell’algoritmo che determina A = LU (se esistente), ma che utilizza la tecnica del pivoting. Per dettagli, si veda [1, p.511], [2, p.172].

Nota. (Storia)

Il metodo di Gauss `e stato uno dei primi implementati su un

Fattorizzazione PA=LU in Matlab

Vediamo di seguito come eseguire la fattorizzazione PA = LU in Matlab.

>> h e l p l u

l u l u f a c t o r i z a t i o n .

[ L , U ] = l u( A ) stores an u p p e r t r i a n g u l a r m a t r i x in U and a ” p s y c h o l o g i c a l l y l o w e r t r i a n g u l a r m a t r i x ” ( i . e . a p r o d u c t of l o w e r

t r i a n g u l a r and p e r m u t a t i o n m a t r i c e s ) in L , so t h a t A = L∗U . A can be r e c t a n g u l a r .

[ L , U , P ] = l u( A ) r e t u r n s unit l o w e r t r i a n g u l a r m a t r i x L , u p p e r

t r i a n g u l a r m a t r i x U , and p e r m u t a t i o n m a t r i x P so t h a t P∗A = L∗U . . . .

>>

Dall’help si capisce che

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

Fattorizzazione PA=LU in Matlab, esempio

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

>>% LA MATRICE E ’ SINGOLARE , RIGHE PROPORZIONALI ! !

>> d e t( A ) a n s = 6 . 6 6 1 3 e−16 >> [ L , U , P ]=l u( A ) L = 1 . 0 0 0 0 0 0 0 . 1 4 2 9 1 . 0 0 0 0 0 0 . 5 7 1 4 0 . 5 0 0 0 1 . 0 0 0 0 U = 7 . 0 0 0 0 8 . 0 0 0 0 9 . 0 0 0 0 0 0 . 8 5 7 1 1 . 7 1 4 3 0 0 0 . 0 0 0 0 P = 0 0 1 1 0 0 0 1 0 >>norm( P∗A−L∗U ) a n s = 0

Fattorizzazione di Cholesky A = LL

T

per matrici

simmetriche definite positive

Teorema (Fattorizzazione di Cholesky A = LLT per matrici simmetriche definite positive)

Sia A ∈ Rn×n una matrice

simmetrica, cio`e A = AT,

definita positiva, cio`e avente tutti gli n autovalori λk

strettamente positivi, cio`e λk > 0, per k = 1, . . . , n.

Allora esiste ed `e unica la fattorizzazione di Cholesky

A = LLT

con L = (li ,j) matrice triangolare inferiore con elementi principali

Fattorizzazione di Cholesky in Matlab, esempio

>> h e l p c h o l

c h o l C h o l e s k y f a c t o r i z a t i o n .

c h o l( A ) uses only the d i a g o n a l and u p p e r t r i a n g l e of A . The l o w e r t r i a n g l e is a s s u m e d to be the ( c o m p l e x c o n j u g a t e ) t r a n s p o s e of the u p p e r t r i a n g l e . If A is p o s i t i v e d e f i n i t e , t h e n R = c h o l( A ) p r o d u c e s an u p p e r t r i a n g u l a r R so t h a t R ’∗ R = A . If A is not p o s i t i v e d e f i n i t e , an e r r o r m e s s a g e is p r i n t e d . L = c h o l( A ,’ l o w e r ’) uses only the d i a g o n a l and the l o w e r t r i a n g l e of A to p r o d u c e a l o w e r t r i a n g u l a r L so t h a t L∗L ’ = A . If A is not p o s i t i v e d e f i n i t e , an e r r o r m e s s a g e is p r i n t e d . W h e n A is s p a r s e, t h i s s y n t a x of c h o l is t y p i c a l l y f a s t e r .

. . . >>

Una galleria di matrici la si pu`o trovare in Matlab con gallery

>> 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 , . . . ) t a k e s matname , a s t r i n g t h a t is the n a m e of a m a t r i x family , and the family ’ s i n p u t p a r a m e t e r s . See the l i s t i n g b e l o w f o r a v a i l a b l e m a t r i x f a m i l i e s . M o s t of the f u n c t i o n s t a k e an i n p u t a r g u m e n t t h a t s p e c i f i e s the o r d e r of the matrix , and u n l e s s o t h e r w i s e stated , r e t u r n a s i n g l e o u t p u t .

. . .

m i n i j S y m m e t r i c p o s i t i v e d e f i n i t e m a t r i x MIN ( i , j ) . . . .

Eliminazione Gaussiana

Si supponga di dover risolvere Ax = b con

A ∈ Rn×n, det(A) 6= 0 (cio`e A non singolare),

b ∈ Rn×1_{= R}n_.

x∗ unica soluzione del sistema lineare Ax = b, cio`e Ax∗= b.

Se PA = LU allora essendo det(P) 6= 0, abbiamo che

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

Posto y∗= Ux∗, da LUx∗= Pb abbiamo che y∗ `e la

soluzione del sistema triangolare inferiore Ly∗= Pb.

Una volta ottenuto y∗, essendo Ux∗ = y∗,x∗ `e la soluzione

Eliminazione Gaussiana

Questa osservazione suggerisce il seguente metodo per risolvere Ax = b con A non singolare.

Metodo (Eliminazione gaussiana)

Si determini la fattorizzazione PA = LU di A ∈ Rn×n (costo

computazionale O(n3_/3)).

Si determini la fattorizzazione c = Pb.

Si risolva il sistema triangolare inferiore Ly = c (costo

computazionale O(n2/2)).

Si risolva il sistema triangolare superiore Ux = y (costo

Eliminazione Gaussiana, esempio in Matlab

>> A=g a l l e r y(’ m i n i j ’, 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 >> x_sol=ones ( 5 , 1 ) ; >> b=A∗x_sol b = 5 9 12 14 15 >>% Ho un s i s t e m a Ax=b c o n s o l u z i o n e x s o l =[1 1 1 1 1 ] ’ .

>>% APPROSSIMO LA SOLUZIONE COL METODO DI ELIMINAZIONE GAUSSIANA .

>> [ 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 ; % Ax=b a l l o r a PAx=Pb . Pongo Pb=c e r i s o l v o PAx=c .

Eliminazione Gaussiana: A = LU o PA = LU?

Problema.

Se

PA = LU `e ottenuta col metodo di pivoting per colonne

implementato dal Matlab,

esiste pure la fattorizzazione A = LU,

quale delle due `e da preferire?

Per questioni di stabilit`a `e da preferire il metodo tramite pivoting

Eliminazione Gaussiana: A = LU o PA = LU?

Esempio (Matrice di Hankel)

Sia H(n)∈ Rn×n _{lamatrice di Hankeldi ordine n, i cui elementi}

sono definiti come segue H_{i ,n+k−i}(n) =



2k se k > 0 21/(2−k) se k ≤ 0

con i = 1, . . . , n, k = i + 1 − n, . . . , i . La matrice H(n)`e invertibile.

Sia x∗ = [1, . . . , 1] ∈ Rn×1 e b = Ax . Ovviamente x∗ `e l’unica

soluzione di Ax = b.

Sia xLU _{la soluzione ottenuta con il metodo di Eliminazione}

gaussiana senza permutazione.

Sia xLUP la soluzione ottenuta con il metodo di Eliminazione

Eliminazione Gaussiana: A = LU o PA = LU?

eLU= kx∗− xLUk2= q Pn k=1(xk∗− xkLU)2. eLUP = kx∗− xLUPk2= q Pn k=1(xk∗− xkLUP)2. Si verifica sperimentalmente che

n eLU eLUP n eLU eLUP

1 0.00e + 00 0.00e + 00 13 1.14e − 09 1.18e − 11

2 1.11e − 16 8.88e − 16 14 9.34e − 09 1.26e − 11

3 4.22e − 15 3.00e − 15 15 3.96e − 08 4.11e − 11

4 4.22e − 15 4.55e − 15 16 2.36e − 07 6.78e − 11

5 1.31e − 14 1.58e − 14 17 2.10e − 06 3.23e − 10

6 3.48e − 13 2.60e − 14 18 1.18e − 05 3.09e − 10

7 1.24e − 13 3.73e − 14 19 4.10e − 05 5.63e − 10

8 1.39e − 12 1.59e − 13 20 1.67e − 04 1.26e − 09

9 7.13e − 12 6.02e − 13 21 4.39e − 04 3.22e − 09

10 1.05e − 11 3.41e − 13 22 2.16e − 02 3.80e − 09

11 1.56e − 11 9.58e − 13 23 2.97e − 02 1.03e − 08

Eliminazione Gaussiana con A simmetrica definita positiva

Si supponga di dover risolvere Ax = b con

A ∈ Rn×n, simmetrica e definita positiva.

b ∈ Rn×1_{= R}n_.

x∗ unica soluzione del sistema lineare Ax = b, cio`e Ax∗= b.

Se A = LLT allora abbiamo che

Ax∗= b ⇔ LLTx∗ = b.

Posto y∗= LTx∗, da L ∗ y∗ = LLTx∗= b abbiamo che y∗ `e

la soluzione del sistema triangolare inferiore Ly∗= b.

Una volta ottenuto y∗, essendo LTx∗= y∗,x∗ `e la soluzione

Eliminazione Gaussiana con A simmetrica definita positiva

Questa osservazione suggerisce il seguente metodo per risolvere Ax = b con A simmetrica e definita positiva.

Metodo (Eliminazione gaussiana se A simmetrica e definita positiva)

Si determini la fattorizzazione A = LLT di A ∈ Rn×n (costo

computazionale O(n3/6)).

Si risolva il sistema triangolare inferiore Ly = c (costo

computazionale O(n2/2)).

Si risolva il sistema triangolare superiore LT_{x = y (costo}

Eliminazione Gaussiana, esempio in Matlab

>> A=g a l l e r y(’ m i n i j ’, 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 >> (e i g( A ) ) ’ a n s = 0 . 2 7 1 6 0 . 3 5 3 3 0 . 5 8 3 0 1 . 4 4 8 7 1 2 . 3 4 3 5 >> % A e ’ s i m m e t r i c a d e f i n i t a p o s i t i v a .

>> x_sol=ones ( 5 , 1 ) ; b=A∗x_sol ;

>>% Ho un s i s t e m a Ax=b c o n s o l u z i o n e x s o l =[1 1 1 1 1 ] ’ .

>>% APPROSSIMO LA SOLUZIONE COL METODO DI ELIMINAZIONE GAUSSIANA VIA CHOLESKY .

Esercizi

Esercizio

Implementare una routine Matlab

flag = issymm(A).

che calcolando gli autovalori di una matrice A, stabilisca se A `

e simmetrica definita positiva (se flag=1 allora `e simmetrica

definita positiva altrimenti non lo `e) .

Nota: per vedere che `e simmetrica basta notare che ci`o `e vero

se

Esercizi

Esercizio

Implementare una routine Matlab

x = linear solver(A, b).

che

calcoli la soluzione x∗ mediante l’eliminazione gaussiana via fattorizzazione di Cholesky se A `e simmetrica e definita positiva,

altrimenti

si effettui PA = LU ove U = (ui ,j) e osservato che

det(A) = det(P) det(U) = ±

n

Y

k=1

uk,k

si verifichi se A `e o meno singolare;

se A `e non singolare, si determini la soluzione x∗con

Esercizi

Esercizio

Testare il codice precedente per risolvere il problema Ax = b dove

A = gallery(0poisson0, 20); b = ones(size(A, 1));

Testare che soluzione x ottenuta coincida con quella fornita dal Matlab via

x sol = A\b;

A tal proposito testare che

norm(x − x sol);

Esercizi

Esercizio (Facoltativo)

Si scarichino i files solve linear LUP.m, solve linear LUP.m, hankel matrix.m, dalla directory del corso.

La chiamata

x = solve linear LU(A, b);

risolve il sistema Ax = b mediante Eliminazione Gaussiana via fattorizzazione A = LU (se esiste!).

La chiamata

x = solve linear LUP(A, b);

Esercizi

La chiamata

A = hankel matrix(n)

produce una matrice di Hankel A ∈ Rn×n.

Sia b = Ax dove

A=hankel matrix(20); x=ones(20,1); b=A*x;

Si risolva il problema Ax = b mediante solve linear LU e sia x1 la soluzione ottenuta.

Si risolva il problema Ax = b mediante solve linear LUP e sia x2 la soluzione ottenuta.

Si calcolino gli errori norm(x-x1) e norm(x-x2). I risultati

Bibliografia

K.E. Atkinson An introduction to Numerical Analysis, Wiley, (1989).