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 L, una matrice triangolare superiore U e una matrice di permutazione P. 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 sorgente]

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

PA = LU

dove P è una matrice di permutazione, L è una matrice triangolare inferiore a diagonale unitaria (l_{ii} = 1, \forall i) e U è una matrice triangolare superiore.

Idea principale[modifica | modifica sorgente]

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

\mathbf{A} \mathbf{x} = \mathbf{b}

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

U x = b'

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

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

A x = L U x = b

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

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 P, ed il sistema diventa:

\begin{cases}
Ly=Pb\\
Ux=y
\end{cases}

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

Algoritmo[modifica | modifica sorgente]

Applicando delle serie di trasformazioni elementari di matrice (cioè moltiplicazioni di A a sinistra) si costruisce una matrice triangolare superiore U che parte da A. 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 T sia il prodotto di N trasformazioni T_N \dots T_2 T_1=T, allora la matrice triangolare superiore è:

TA=T_N\dots T_2 T_1 A =\colon U

L'inversa della matrice T è:

T^{-1}=T_1^{-1}T_2^{-1}\dots T_N^{-1}

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

T^{-1}=T_1^{-1}T_2^{-1}\dots T_N^{-1}=\colon L

è triangolare inferiore.

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

LU=T^{-1}TA=A

Applicazioni[modifica | modifica sorgente]

Matrici inverse[modifica | modifica sorgente]

La fattorizzazione PA = LU viene anche usata per calcolare la matrice inversa di A. Infatti:

PA = LU \Rightarrow A = P^{-1}LU

da cui:

A^{-1} = (P^{-1}LU)^{-1} = U^{-1}L^{-1}P

Determinante[modifica | modifica sorgente]

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

A = P^{-1}LU \Rightarrow \det(A) = \det(P^{-1}LU)

quindi per il teorema di Binet:

\det(A) = \det(P^{-1})\det(L)\det(U)

Sapendo che il determinante di una matrice di permutazione vale 1 se questa corrisponde ad un numero pari di permutazioni, -1 altrimenti, e che \det A^{-1} = \frac{1}{\det A}, si ottiene che:

\det(A) = (-1)^S\det(L)\det(U)

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

\det(A)=\left(-1\right)^{S}\prod_{i=1}^{n}{u_{ii}l_{ii}}

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

\det(A)=\left(-1\right)^{S}\prod_{i=1}^{n}u_{ii}

dove S indica il numero di scambi di riga effettuati nel processo (indicati nella matrice P[In che modo?]) ed i termini u_{ij} e l_{ij} indicano il termine in riga i e colonna j rispettivamente delle matrici U e L.

Bibliografia[modifica | modifica sorgente]

  • (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 sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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