Algebra lineare numerica

Algebra lineare numerica

Alvise Sommariva

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

Introduzione

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

colonna e supponiamo di dover calcolare un vettore colonna x∗

∈ Rn _{cosicch`eA · x}∗

= b.

Come `e noto questo problema ha soluzione unica x∗

se e solo se det (A) 6= 0 (matrice non singolare). Ci porremo di seguito in queste ipotesi.

Introdurremo due famiglie di metodi, quelli diretti che calcolano la soluzione x∗

Eliminazione gaussiana: esempio.

Risolvere il sistema lineare

1 · x1+ 2 · x2+ 1 · x3+ 4 · x4 = 13

2 · x1+ 0 · x2+ 4 · x3+ 3 · x4 = 28

4 · x1+ 2 · x2+ 2 · x3+ 1 · x4 = 20

−3 · x1+ 1 · x2+ 3 · x3+ 2 · x4= 6

utilizzando esclusivamente le seguenti regole, che modificano il sistema lineare da risolvere ma non le sue soluzioni:

◮ Scambi di righe;

◮ Moltiplicazioni di righe per una costante;

Eliminazione gaussiana: esempio.

Posti A=     1 2 1 4 2 0 4 3 4 2 2 1 −3 1 3 2     , b =     13 28 20 6    

risolviamo il sistema lineare Ax = b con il metodo dell’eliminazione gaussiana. Consideriamo pure la matrice aumentata A(1)_{aug = (a}(1)_{j ,k}):

Eliminazione gaussiana: esempio.

Siano mk,1 = a(1)k,1/a (1)

1,1 i cosidetti moltiplicatori. L’elemento

a_1,1(1)6= 0 `e detto pivot. m1,1 = 1 m_2,1 = 2 m3,1 = 4 m4,1 = −3     1 2 1 4 13 2 0 4 3 28 4 2 2 1 20 −3 1 3 2 6     .

Per k = 2, 3, 4, moltiplichiamo la prima riga per −mk,1 e

sommiamo il risultato alla k-sima riga. Abbiamo:

Eliminazione gaussiana: esempio.

Siano mk,2 = a(2)k,2/a (2) 2,2 (k > 2) i moltiplicatori . L’elemento a (2) 2,2 `e un pivot. m2,2= 1 m3,2= 1.5 m4,2= −1.75     1 2 1 4 13 0 −4 2 −5 2 0 −6 −2 −15 −32 0 7 6 14 45     .

Per k = 3, 4, moltiplichiamo la seconda riga per −mk,2 e

sommiamo il risultato alla k-sima riga. Abbiamo:

Eliminazione gaussiana: esempio.

Siano m4,3 = a(3)4,3/a (3) 3,3 ilmoltiplicatore. L’elemento a (3) 3,3 6= 0 `e un pivot. m3,3= 1 m4,3= −1.9     1 2 1 4 13 0 −4 2 −5 2 0 −6 −2 −15 −32 0 7 6 14 45     .

Per k = 3, 4, moltiplichiamo la terza riga per −mk,3 e sommiamo il

risultato alla k-sima riga. Abbiamo:

Eliminazione gaussiana: esempio.

In virt`u delle operazioni utilizzate, il sistema lineare 1 · x1+ 2 · x2+ 1 · x3+ 4 · x4 = 13

2 · x1+ 0 · x2+ 4 · x3+ 3 · x4 = 28

4 · x1+ 2 · x2+ 2 · x3+ 1 · x4 = 20

−3 · x1+ 1 · x2+ 3 · x3+ 2 · x4= 6

ha quindi le stesse soluzioni del sistema lineare 1 · x1+ 2 · x2+ 1 · x3+ 4 · x4 = 13

0 · x1+ −4 · x2+ 2 · x3+ −5 · x4 = 2

0 · x1+ 0 · x2−5 · x3−7.5 · x4 = −35

0 · x1+ 0 · x2+ 0 · x3−9 · x4 = −18

che si risolve facilmente tramite sostituzione all’indietro (si calcola facilmente dall’ultima eqz. x4 = 2, si sostituisce tale valore alla

penultima eqz. e si ottiene x3= 4, si sostituiscono tali x3, x4 alla

seconda eqz. e si ottiene x2= −1, , si sostituiscono tali x2, x3, x4

Fattorizzazione LU

Il proposito `e di rivedere questo algoritmo dal punto di vista matriciale. La matrice iniziale A=     1 2 1 4 2 0 4 3 4 2 2 1 −3 1 3 2    

si scrive come prodotto A = LU di due matrici quadrate L, U con ◮ L= (l_{i ,j}) matricetriangolare inferiore, cio`e l_{i ,j} = 0 se i < j,

con la propriet`a cheli ,i = 1.

Fattorizzazione LU

Introduciamo la routine fattLU: f u n c t i o n B = fattLU ( A ) n=s i z e( A , 1 ) ; f o r k=1:n−1 A( k +1:n , k )=A ( k +1:n , k ) / A ( k , k ) ; f o r j=k +1:n , f o r s=k +1: n

A_{( s , j )=A ( s , j )−A ( s , k ) ∗A ( k , j ) ;} end

end end B=A ;

Esegue, se esiste, la fattorizzazione LU della matrice,

Fattorizzazione LU

>> A=[1 2 1 4 ; 2 0 4 3 ; 4 2 2 1 ; −3 1 3 2 ] ; >> B = fattLU ( A ) B = 1 . 0 0 0 0 2 . 0 0 0 0 1 . 0 0 0 0 4 . 0 0 0 0 2 . 0 0 0 0 −4.0000 2 . 0 0 0 0 −5.0000 4 . 0 0 0 0 1 . 5 0 0 0 −5.0000 −7.5000 −3.0000 −1.7500 −1.9000 −9.0000 >>

Fattorizzazione LU

Usando il comando triu che estrae la parte triangolare superiore della matrice: >> U=t r i u( B ) U = 1 . 0 0 0 0 2 . 0 0 0 0 1 . 0 0 0 0 4 . 0 0 0 0 0 −4.0000 2 . 0 0 0 0 −5.0000 0 0 −5.0000 −7.5000 0 0 0 −9.0000 >> L=B−U+e y e(s i z e( B ) ) L = 1 . 0 0 0 0 0 0 0 2 . 0 0 0 0 1 . 0 0 0 0 0 0 4 . 0 0 0 0 1 . 5 0 0 0 1 . 0 0 0 0 0 −3.0000 −1.7500 −1.9000 1 . 0 0 0 0 >> _{norm( A−L ∗U )}

Fattorizzazione LU

Se A = LU allora, posto y := Ux abbiamo Ly = LUx = Ax = b

Questo `e un sistema triangolare inferiore che pu`o essere agevolmente risolto con il metodo della sostituzione in avanti

y∗ k = bk−P_{j <k}lk,jy_j∗ lk,k , y∗ 1 = b1/l1,1

Una volta ottenuto y∗

, osservato che Ux = y∗

con un metodo simile, detto di sostituzione all’indietrosi ricava la soluzione x∗

: x∗ k = y∗ k − P j >kuk,jxj∗ uk,k , x∗ n = y ∗ n/un,n

Fattorizzazione LU

Alcuni problemi:

◮ Non `e detto esista la fattorizzazione LU di una matrice A. Ad esempio, come si vede subito con facili conti, la matrice

A=

 0 1 1 0



non `e fattorizzabile LU.

◮ La presenza di moltiplicatori m_{i ,j} grandi pu`o causare errori nella risoluzione del sistema lineare.

◮ Il calcolo dei moltiplicatori m

s,k = a(k)s,k/a (k)

k,k, visto in

Matrice di permutazione

Una matrice P si dice di permutazione se ha per ogni riga e colonna una sola componente non nulla ed uguale a 1. Alcune propriet`a

◮ P−1 = PT.

Eliminazione gaussiana: esempio.

Cerchiamo l’elemento pi`u grande in modulo della prima colonna di A (che supponiamo invertibile)

    1 2 1 4 2 0 4 3 4 2 2 1 −3 1 3 2     .

e scambiamo la riga corrispondente (la prima riga viene scambiata con la terza). Otteniamo cos`ı

Eliminazione gaussiana: esempio.

Siano mk,1 = a(1)k,1/a (1)

1,1 i cosidetti moltiplicatori. L’elemento a1,1 `e

detto pivot. Per k = 2, 3, 4, moltiplichiamo la prima riga per −mk,1 e sommiamo il risultato alla k-sima riga. Abbiamo:

m1,1 = 1 m_2,1 = 0.5 m3,1 = 0.25 m4,1 = −0.75     4 2 2 1 0 −1 3 2.5 0 1.5 0.5 3, 75 0 2.5 4.5 2.75     .

Eliminazione gaussiana: esempio.

Partiamo da:     4 2 2 1 0 −1 3 2.5 0 1.5 0.5 3, 75 0 2.5 4.5 2.75     .

Osserviamo che se la matrice `e non singolare, l’elemento di massimo modulo della seconda colonna con indice di riga ≥ 2 `e non nullo (altrimenti avrei due colonne proporzionali e la matrice sarebbe singolare). Scambiamo la seconda riga con l’indice di riga per cui si ottiene tale massimo (quarta riga). Abbiamo cos`ı

Eliminazione gaussiana: esempio.

I moltiplicatori mk,2 = a(2)_k,2/a(2)2,2 della matrice sono

m3,2 = 1.5/2.5 = −0.6, m4,2= −1/2.5 = −0.4. m2,2 = 1 m_3,2 = −0.6 m4,2 = −0.4     4 2 2 1 0 2.5 4.5 2.75 0 1.5 0.5 3, 75 0 −1 3 2.5     .

Per k = 3, 4, moltiplichiamo la seconda riga per −mk,1 e

Eliminazione gaussiana: esempio.

Con le stesse idee, per quanto riguarda la terza colonna, scambiamo la quarta riga con la terza e abbiamo

A(3)=     4 2 2 1 0 2.5 4.5 2.75 0 0 4.8 3.6 0 0 −2.2 2.1     . Il moltiplicatore `e m4,3 = −2.2/4.8 ≈ −0.4583. Per k = 4,

moltiplichiamo la terza riga per −m4,3 e sommiamo il risultato alla

quarta riga. Abbiamo la matrice triangolare superiore U = A(4):

Eliminazione gaussiana: esempio.

◮ Abbiamo scambiato la prima riga con la terza. ◮ Abbiamo scambiato la seconda riga con la quarta. ◮ Abbiamo scambiato la terza riga con la quarta.

Quindi `e come scambiare la prima riga con la terza, la seconda con la quarta, la terza con la seconda e la quarta con la prima. Cos`ı

P =     0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0     .

Fattorizzazione LU in Matlab/Octave

Fattorizzazione LU

Vediamo cosa fa Matlab/Octave.

Si dimostra che ogni matrice invertibile A ∈ Rn×n _{`e fattorizzabile}

come

P · A= L · U dove

◮ P `e una matrice di permutazione.

◮ L= (l_{i ,j}) `e una matricetriangolare inferiore, cio`e l_{i ,j} = 0 se i < j, con la propriet`a cheli ,i = 1.

◮ U = (u_{i ,j}) `e una matricetriangolare superiore, cio`e l_{i ,j} = 0 se i > j.

Quindi se PA = LU e P−₁

Fattorizzazione LU

Se PA = LU e Ax = b, allora LUx = PAx = Pb e quindi posto y = Ux, prima si risolve con la sostituzione all’indietro Ly = Pb e quindi, se y∗

Fattorizzazione LU di una matrice A non invertibile