Decomposizione LU

Da Wikipedia, l'enciclopedia libera.

In algebra lineare una decomposizione LU, o decomposizione LUP o decomposizione di Doolittle è una fattorizzazione di una matrice in una matrice triangolare inferiore , una matrice triangolare superiore e una matrice di permutazione . Questa decomposizione è usata in analisi numerica per risolvere un sistema di equazioni lineari, per calcolare l'inversa di una matrice o per calcolare il determinante di una matrice.

Definizione[modifica | modifica wikitesto]

Sia una matrice invertibile. Allora può essere decomposta come:

dove è una matrice di permutazione, è una matrice triangolare inferiore a diagonale unitaria () e è una matrice triangolare superiore.

Idea principale[modifica | modifica wikitesto]

La decomposizione è simile all'algoritmo di Gauss. Nell'eliminazione gaussiana si prova a risolvere l'equazione matriciale:

Il processo di eliminazione produce una matrice triangolare superiore e trasforma il vettore in

Poiché è una matrice triangolare superiore, questo sistema di equazioni si può risolvere facilmente tramite sostituzione all'indietro.

Durante la decomposizione , però, non è trasformato e l'equazione può essere scritta come:

così si può riusare la decomposizione se si vuole risolvere lo stesso sistema per un differente .

Nel caso più generale, nel quale la fattorizzazione della matrice comprende anche l'utilizzo di scambi di riga nella matrice, viene introdotta anche una matrice di permutazione , ed il sistema diventa:

La risoluzione di questo sistema permette la determinazione del vettore cercato.

Algoritmo[modifica | modifica wikitesto]

Applicando delle serie di trasformazioni elementari di matrice (cioè moltiplicazioni di a sinistra) si costruisce una matrice triangolare superiore che parte da . Questo metodo è chiamato metodo di Gauss. Queste trasformazioni elementari di matrice sono tutte delle trasformazioni lineari di tipo combinatorio (il terzo tipo elencato nella voce "Matrice elementare"). Si supponga che sia il prodotto di N trasformazioni , allora la matrice triangolare superiore è:

L'inversa della matrice è:

Come l'algoritmo di Gauss usa solo la terza forma dei tre tipi di trasformazioni elementari di matrice rendendo triangolare superiore, si può dedurre che tutte le sono triangolari inferiori (vedi trasformazioni elementari di matrice). Essendo un prodotto di anche:

è triangolare inferiore.

Si ha quindi la decomposizione della matrice nel prodotto di e :

Applicazioni[modifica | modifica wikitesto]

Matrici inverse[modifica | modifica wikitesto]

La fattorizzazione viene anche usata per calcolare la matrice inversa di . Infatti:

da cui:

Determinante[modifica | modifica wikitesto]

Un altro utilizzo di questa decomposizione è per il calcolo del determinante della matrice . Infatti:

quindi per il teorema di Binet:

Sapendo che il determinante di una matrice di permutazione vale se questa corrisponde ad un numero pari di permutazioni, altrimenti, e che , si ottiene che:

Sapendo poi che il determinante di una matrice triangolare è dato dal prodotto dei termini sulla sua diagonale principale, si ha che:

ma sapendo anche che i termini sulla diagonale principale di sono tutti , quindi si può infine concludere:

dove indica il numero di scambi di riga effettuati nel processo (implicitamente indicati nella matrice ) ed i termini e indicano il termine in riga e colonna rispettivamente delle matrici e .

Bibliografia[modifica | modifica wikitesto]

  • (EN) Bunch, James R.; Hopcroft, John (1974), "Triangular factorization and inversion by fast matrix multiplication", Mathematics of Computation 28: 231–236, ISSN 0025-5718.
  • (EN) Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3.
  • (EN) Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
  • (EN) Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 0-521-38632-2. See Section 3.5.
  • (EN) Householder, Alston S. (1975), The Theory of Matrices in Numerical Analysis, New York: Dover Publications, MR 0378371.
  • (EN) Okunev, Pavel; Johnson, Charles R. (1997), Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, arXiv:math.NA/0506382.
  • (EN) Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Canada: Thomson Brooks/Cole, ISBN 0-534-99845-3.
  • (EN) Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.3", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8.
  • (EN) Trefethen, Lloyd N.; Bau, David (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica