Introduzione

Tutte e tre le fattorizzazioni di matrici discusse in questa sezione utilizzano le matrici triangolari, dove tutti gli elementi sopra o sotto la diagonale sono pari a zero. I sistemi di equazioni lineari che interessano matrici triangolari possono essere risolti facilmente e semplicemente utilizzando la sostituzione in avanti o all'indietro.

Fattorizzazione di Cholesky

La fattorizzazione di Cholesky esprime una matrice simmetrica come prodotto di una matrice triangolare e il suo trasposto

dove R è una matrice triangolare superiore.

Non tutte le matrici simmetriche possono essere fattorizzate in questo modo; le matrici che presentano questa fattorizzazione sono denominate come positive definite. Questo implica che tutti gli elementi della diagonale di A siano positivi e che gli elementi della contro-diagonale "non siano troppo grandi". Le matrici di Pascal rappresentano un esempio interessante. In tutto questo capitolo si è utilizzata una matrice Pascal 3x3 di esempio A. Passare momentaneamente a 6x6:

A = pascal(6)

A =
       1     1     1     1     1     1
       1     2     3     4     5     6
       1     3     6    10    15    21
       1     4    10    20    35    56
       1     5    15    35    70   126
       1     6    21    56   126   252

Gli elementi di A sono coefficienti binomiali. Ciascun elemento è la somma degli elementi vicini a nord e ovest. La fattorizzazione di Cholesky è

R = chol(A)

R =
     1     1     1     1     1     1
     0     1     2     3     4     5
     0     0     1     3     6    10
     0     0     0     1     4    10
     0     0     0     0     1     5
     0     0     0     0     0     1

Gli elementi sono di nuovo coefficienti binomiali. Il fatto che R'*R sia uguale a A dimostra un'identità che interessa somme di prodotti di coefficienti binomiali.

La fattorizzazione di Cholesky consente di sostituire il sistema lineare

con

Dato che l'operatore barra rovesciata riconosce i sistemi triangolari, questo può essere risolto rapidamente nell'ambiente di MATLAB^® con

x = R\(R'\b)

Se A è nxn, la complessità di calcolo di chol(A) è O(n³), ma la complessità delle successive soluzioni con barra retroversa è solo O(n²).

Fattorizzazione LU

La fattorizzazione LU, o eliminazione gaussiana, esprime una qualsiasi matrice quadrata A come prodotto di una permutazione di una matrice triangolare inferiore e una matrice triangolare superiore

dove L è una permutazione di una matrice triangolare inferiore con elementi uno sulla sua diagonale e U è una matrice triangolare superiore.

Le permutazioni sono necessarie per motivi sia teorici che di calcolo. Non è possibile esprimere la matrice

come prodotto di matrici triangolari senza scambiarne le due righe. Benché la matrice

sia esprimibile come prodotto di matrici triangolari, quando ε è piccolo, gli elementi nei fattori sono grandi e amplificano gli errori; quindi, benché non strettamente necessarie, le permutazioni sono consigliabili. La pivotazione parziale garantisce che gli elementi di L siano limitati da uno in magnitudine e che gli elementi di U non siano molto più grandi di quelli in A.

Ad esempio:

[L,U] = lu(B)

L =
    1.0000         0         0
    0.3750    0.5441    1.0000
    0.5000    1.0000         0

U =
    8.0000    1.0000    6.0000
         0    8.5000   -1.0000
         0         0    5.2941

La fattorizzazione LU di A consente di risolvere rapidamente il sistema lineare

A*x = b

con

x = U\(L\b)

Determinanti e inverse sono calcolate dalla fattorizzazione LU con

det(A) = det(L)*det(U)

e

inv(A) = inv(U)*inv(L)

È anche possibile calcolare le determinanti con det(A) = prod(diag(U)), anche se i segni delle determinanti possono essere invertiti.

Fattorizzazione QR

Una matrice ortogonale, o una matrice con colonne ortonormali, è una matrice reale con colonne tutte di lunghezza unitaria e perpendicolari l'una con l'altra. Se Q è ortogonale, allora

dove I è la matrice di identità.

Le matrici ortogonali più semplici sono rotazioni di coordinate bidimensionali:

Per le matrici complesse, il termine corrispondente è unitaria. Le matrici ortogonali e unitarie sono utili nel calcolo numerico perché conservano la lunghezza, conservano gli angoli e non amplificano gli errori.

La fattorizzazione ortogonale, o QR, esprime una qualsiasi matrice rettangolare come prodotto di una matrice ortogonale o unitaria e di una matrice triangolare superiore. È inoltre possibile effettuare una permutazione di colonna:

oppure

dove Q è ortogonale o unitario, R è un triangolo superiore e P è una permutazione.

Vi sono quattro varianti della fattorizzazione QR: complete o economy size e con o senza permutazioni di colonne.

I sistemi lineari sovradeterminati interessano una matrice rettangolare con più righe che colonne, cioè mxn con m > n. La fattorizzazione QR a piene dimensioni produce un quadrato ortogonale Q, mxm e un triangolo superiore rettangolare R,mxn:

C=gallery('uniformdata',[5 4], 0);
[Q,R] = qr(C)

Q =

    0.6191    0.1406   -0.1899   -0.5058    0.5522
    0.1506    0.4084    0.5034    0.5974    0.4475
    0.3954   -0.5564    0.6869   -0.1478   -0.2008
    0.3167    0.6676    0.1351   -0.1729   -0.6370
    0.5808   -0.2410   -0.4695    0.5792   -0.2207


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648
         0         0         0         0

In molti casi, le ultime colonne m – n di Q non sono necessarie perché vengono moltiplicate per gli zeri nella parte inferiore di R. La fattorizzazione QR economy size produce un rettangolo Q mxn con colonne ortonormali e un quadrato triangolare superiore R nxn. Per l'esempio 5x4 non si tratta di un vantaggio importante, mentre per le matrici più grandi e molto rettangolari il risparmio in termini di tempo e memoria può essere decisamente notevole:

[Q,R] = qr(C,0)	
Q =

    0.6191    0.1406   -0.1899   -0.5058
    0.1506    0.4084    0.5034    0.5974
    0.3954   -0.5564    0.6869   -0.1478
    0.3167    0.6676    0.1351   -0.1729
    0.5808   -0.2410   -0.4695    0.5792


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648

Contrariamente alla fattorizzazione LU, la fattorizzazione QR non richiede pivotazione o permutazioni. Ma una permutazione opzionale delle colonne, attivata dalla presenza di un terzo argomento di output, è utile per la rilevazione di singolarità o di carenze di rango. In qualsiasi passaggio della fattorizzazione, viene usata come base la colonna delle restanti matrici non sottoposte a fattorizzazione con la norma più grande. Questo garantisce che gli elementi diagonali di R si presentino in ordine decrescente e che eventuali dipendenze lineari tra le colonne vengano quasi certamente rivelate da un esame di questi elementi. Per il breve esempio qui riportato, la seconda colonna di C presenta una norma maggiore della prima, quindi le due colonne vengono scambiate:

[Q,R,P] = qr(C)

Q =
   -0.3522    0.8398   -0.4131
   -0.7044   -0.5285   -0.4739
   -0.6163    0.1241    0.7777

R =
  -11.3578   -8.2762
         0    7.2460
         0         0

P =
     0     1
     1     0

Quando le permutazioni economy size e di colonna vengono combinate, il terzo argomento di output è un vettore di permutazione, non una matrice di permutazione:

[Q,R,p] = qr(C,0)

Q =
   -0.3522    0.8398
   -0.7044   -0.5285
   -0.6163    0.1241

R =
  -11.3578   -8.2762
         0    7.2460


p =
     2     1

La fattorizzazione QR trasforma un sistema lineare sovradeterminato in un sistema triangolare equivalente. L'espressione

norm(A*x - b)

è uguale a

norm(Q*R*x - b)

La moltiplicazione con matrici ortogonali osserva la norma euclidea, quindi questa espressione è anche uguale a

norm(R*x - y)

dove y = Q'*b. Poiché le ultime righe m-n di R sono degli zeri, questa espressione si suddivide in due parti:

norm(R(1:n,1:n)*x - y(1:n))

e

norm(y(n+1:m))

Quando A presenta un rank pieno, è possibile risolverlo per x in modo che la prima di queste espressioni sia zero. La seconda espressione dà poi la norma del residuo. Quando A non presenta un rango completo, la struttura triangolare di R consente di trovare una soluzione di base per il problema con minimi quadrati.

Uso del calcolo multithread per la fattorizzazione

Il software MATLAB supporta il calcolo multithread per diverse funzioni numeriche dell'algebra lineare e orientate agli elementi. Queste funzioni vengono eseguite automaticamente su più thread. Per una maggior rapidità di esecuzione di una funzione o espressione su più CPU, occorre soddisfare una serie di condizioni:

lu e qr mostrano un notevole aumento della velocità sugli array a doppia precisione (nell'ordine di 10.000 elementi).