Decomposizione LU

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 o per JAMES IS INCREDIBLY DUMBcalcolare l'inversa di una matrice.

Definizione

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

${\displaystyle \mathbf {PA} =\mathbf {LU} }$ 

dove P è una matrice di permutazione, L è una matrice triangolare inferiore e U è una matrice triangolare superiore.

Idea principale

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

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

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

${\displaystyle \mathbf {U} \mathbf {x} =\mathbf {b} '}$ 

Poiché U è una matrice triangolare superiore, questo sistema di equazioni si può risolvere facilmente.

Durante la decomposizione LU sull'altra parte b non è trasformata e l' equazione di matrice può essere scritta come

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {L} \mathbf {U} \mathbf {x} =\mathbf {b} }$ 

così possiamo riusare la decomposizione se vogliamo risolvere la stessa equazione per un differente b.

Algoritmo

Applicando alle serie di trasformazioni elementari di matrice (cioè moltiplicazioni di A a sinistra) costruiamo 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 lista "trasformazioni elementari di matrice"). Supponiamo che T sia il prodotto di N trasformazioni T_N ... T₂ T₁=T, allora la matrice triangolare superiore è:

TA = T_N ... T₂ T₁A =: U .

L'inversa della matrice T è :

T ^-1 = T₁^-1 T₂^-1 ... 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, possiamo 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 T₂^-1 ... T_N^-1 =:L

è triangolare inferiore.

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

LU = T ^-1TA = A.

Applicazioni

Matrici inverse

Le matrici L e U possono essere usate per calcolare la matrice inversa. Il calcolo numerico di matrici inverse spesso usa questo approccio (sotto determinate condizioni) per risolvere il problema del calcolo dell'inversa di una data matrice A.

Voci correlate

• Analisi numerica
• Decomposizione di Cholesky
• Decomposizione di Crout