decomposizione LU

In algebra lineare , la decomposizione LU è un metodo per scomporre una matrice come prodotto di una matrice triangolare inferiore $L$ (come inferiore , inferiore in inglese ) per una matrice triangolare superiore $U$ (come superiore , superiore). Questa scomposizione viene utilizzata nell'analisi numerica per risolvere sistemi di equazioni lineari .

Definizione

Sia $A$ una matrice quadrata . Diciamo che $A$ ammette una scomposizione LU se esiste una matrice triangolare inferiore formata da 1 sulla diagonale, indicata $L$ , e una matrice triangolare superiore, indicata $U$ , che verificano l'uguaglianza

A = LU \;

Non è sempre vero che una matrice $A$ ammette una scomposizione LU. Tuttavia in alcuni casi, permutando le linee di $A$ , la scomposizione diventa possibile. Otteniamo quindi una scomposizione della forma

A = PLU \;

dove $P$ è una matrice di permutazione .

Sebbene le scomposizioni LU e PLU portino a formule separate, generalmente quando si parla di scomposizione LU ci riferiamo all'una o all'altra di queste scomposizioni.

Esempio

La matrice simmetrica

{\ displaystyle A = {\ begin {pmatrix} 2 & -1 & 0 \\ - 1 & 2 & -1 \\ 0 & -1 & 2 \\\ end {pmatrix}}}

è scomposto come segue:

{\ displaystyle A = LU \ quad {\ text {with}} \ quad L = {\ begin {pmatrix} 1 & 0 & 0 \\ - 1/2 & 1 & 0 \\ 0 & -2 / 3 & 1 \\\ end {pmatrix}} \ quad { \ text {et}} \ quad U = {\ begin {pmatrix} 2 & -1 & 0 \\ 0 & 3/2 & -1 \\ 0 & 0 & 4 /3 \\\ fine {pmatrix}}}

Applicazioni

Risolvi un sistema di equazioni lineari

Questa fattorizzazione di matrici consente di risolvere sistemi di equazioni lineari in cui i coefficienti delle incognite sono gli stessi, ma con diversi secondi membri diversi. Vale a dire per determinare il vettore $x$ di incognite associato al secondo membro $b$ :

{\ stile di visualizzazione Ax = b}

Questo problema è quindi equivalente alla risoluzione di

{\ displaystyle LUx = b}

che possiamo mettere, ponendo , nella forma: ${\ displaystyle Ux = y}$

{\ displaystyle Ly = b}

Troviamo le componenti di per sostituzioni elementari, poiché prima , poi , ecc. $sì$ ${\ stile di visualizzazione y_ {1} = b_ {1}}$ ${\ displaystyle y_ {2} = b_ {2} -L_ {21} y_ {1}}$

Questo passaggio è chiamato discesa , poiché il sistema si risolve scendendo da a . Resta da calcolare le componenti del vettore $x$ risolvendo il sistema triangolare superiore: $s_ {1}$ $y_n$

{\ displaystyle Ux = y}

che si fa in modo simile, ma calcolando prima $x n$ :

x_n = \ frac {y_n} {U_ {nn}}

, eccetera. salendo (cosiddetta fase di salita ).

Nota. - Le matrici triangolari $L$ e $U$ avrebbero potuto essere facilmente invertite utilizzando l' eliminazione di Gauss-Jordan . Ma se contiamo semplicemente il numero di operazioni che questo rappresenta per un sistema con $n$ equazioni, troveremo che la complessità algoritmica del calcolo delle matrici inverse è maggiore, per cui se vogliamo risolvere questo sistema per vari $b$ , è più interessante eseguire la scomposizione LU una volta per tutte ed eseguire le sostituzioni discesa-salita per le diverse $bs$ piuttosto che utilizzare più volte l'eliminazione di Gauss-Jordan. Così, nella maggior parte delle pubblicazioni di analisi numerica , quando la matrice $A$ è stata fattorizzata nella forma di LU o di Cholesky ( cfr. infra , § Il caso simmetrico ), si scrive abusando $x = A -1 b$ per significare che il calcolo di $x$ può essere fatto con questo metodo di discesa-ascesa. Resta inteso che non si tratta assolutamente di utilizzare l'algoritmo calcolando la matrice inversa $A -1$ di $A$ , che sarebbe inutilmente costoso in termini di tempo di calcolo.

Invertire una matrice

Le matrici $L$ e $U$ possono essere utilizzate per determinare l'inversa di una matrice. I programmi per computer che implementano questo tipo di calcolo generalmente utilizzano questo metodo.

Calcolo di un determinante

Se $A$ è nella forma $LU$ e $PLU$ , il suo determinante è facilmente calcolabile: . I tre determinanti di questo prodotto sono molto semplici da calcolare (matrici triangolari o di permutazione). $\ det (A) = \ det (P) \ det (L) \ det (U)$

Esistenza, unicità

Per ogni matrice quadrata esiste una decomposizione $PLU$ . Per una matrice invertibile, la decomposizione LU esiste se e solo se tutti i principali sottomatrici di ordine 1 a $n -1$ sono invertibili. [Per una matrice quadrata di rango r <n, esistono condizioni sufficienti analoghe.] Se tutte le sotto-matrici principali di ordine da 1 a $n$ sono invertibili, è anche unica.

Calcolo della decomposizione

Idea principale

La decomposizione LU è una forma particolare di eliminazione di Gauss-Jordan. Trasformiamo la matrice $A$ in una matrice triangolare superiore $U$ eliminando gli elementi sotto la diagonale. Le eliminazioni si fanno colonna dopo colonna, partendo da sinistra, moltiplicando $A$ per sinistra con una matrice triangolare inferiore.

Algoritmo

Data una matrice di dimensione $N \ volte N$

{\ displaystyle A = (a_ {i, j}) _ {1 \ leq i, j \ leq N}}

noi definiamo

A ^ {(0)}: = A \;

e costruiremo le matrici in modo iterativo, con l'obiettivo che la matrice abbia le sue prime n colonne di coefficienti zero sotto la diagonale. ${\ displaystyle A ^ {(1)}, ..., A ^ {(n)}, ..., A ^ {(N-1)}}$ $A ^ {{(n)}}$

O la matrice , costruiamo la matrice come segue: considerando l' n- esima colonna di , eliminiamo gli elementi sotto la diagonale aggiungendo alla i- esima riga di questa matrice, l' n- esima riga moltiplicata per ${\ stile di visualizzazione A ^ {(n-1)}}$ $A ^ {{(n)}}$ ${\ stile di visualizzazione A ^ {(n-1)}}$

{\ displaystyle -l_ {i, n}: = - {\ frac {a_ {i, n} ^ {(n-1)}} {a_ {n, n} ^ {(n-1)}}}}

per . Questo può essere fatto moltiplicando per la sinistra $A$ $($ $n$ $-1)$ con la matrice triangolare inferiore $i = n + 1, \ ldot, N$

{\ displaystyle L_ {n} = {\ begin {pmatrix} 1 &&&&& 0 \\ & \ ddots &&&& \\ && 1 &&& \\ && - l_ {n + 1, n} & \ ddots && \\ && \ vdots && \ ddots & \ \ 0 && - l_ {N, n} &&& 1 \\\ end {pmatrix}}.}

A ^ {(n)}: = L_n A ^ {(n-1)}. \;

Dopo $N - 1$ iterazioni, abbiamo rimosso tutti gli elementi al di sotto della diagonale, quindi ora abbiamo una matrice triangolare superiore $A ( N -1)$ .

Otteniamo la decomposizione

A = L_ {1} ^ {- 1} L_ {1} A ^ {(0)} = L_ {1} ^ {- 1} A ^ {(1)} = L_ {1} ^ {- 1} L_ {2} ^ {- 1} L_ {2} A ^ {(1)} = L_ {1} ^ {- 1} L_ {2} ^ {- 1} A ^ {(2)} = \ ldots = L_ {1} ^ {- 1} \ ldots L_ {N-1} ^ {- 1} A ^ {(N-1)}.

Indichiamo con $U$ , la matrice triangolare superiore $A ( N -1)$ . e . Sapendo che l'inversa di una matrice triangolare inferiore è anche una matrice triangolare inferiore e che il prodotto di due matrici triangolari inferiori è ancora una matrice triangolare inferiore, $L$ è quindi una matrice triangolare inferiore. Otteniamo $A = LU$ e $L = L_ {1} ^ {- 1} \ lpunti L_ {N-1} ^ {- 1}$

{\ displaystyle L = {\ begin {pmatrix} 1 &&&&& \\ l_ {2,1} & \ ddots &&&& \\ & \ ddots & 1 &&& \\\ vdots & \ punti & l_ {n + 1, n} & 1 && \\ && \ vdots & \ ddots & \ ddots & \\ l_ {N, 1} & \ punti & l_ {N, n} & \ punti & l_ {N, N-1} & 1 \ end {pmatrix }}.}

In vista dell'algoritmo, è necessario che ad ogni iterazione (si veda la definizione di $l$ ${$ $i$ $,$ $n$ $}$ ). Se, durante il calcolo, questo scenario dovesse verificarsi, dobbiamo invertire la n ° fila con un altro per continuare (è sempre possibile trovare un elemento diverso da zero della colonna che è un problema perché la matrice è invertibile). Questo è il motivo per cui la scomposizione LU è generalmente scritta come $P$ $-1$ $A$ $=$ $LU$ . $a_ {n, n} ^ {(n-1)} \ neq0$

Il caso simmetrico

Se la matrice $A$ è una matrice simmetrica , esiste una scomposizione nota come fattorizzazione di Crout $A = LDL ^ {\ mathrm T}$ dove $L$ è una matrice triangolare inferiore la cui diagonale include solo 1, $L T$ è la trasposta di $L$ e $D$ è una matrice diagonale.
Se la matrice A è simmetrica definita positiva , esiste una scomposizione più semplice, data dal metodo di Cholesky $A = LL ^ {\ mathrm T}$ dove $L$ è una matrice triangolare minore della diagonale positiva e $L T la$ sua trasposta .

Note e riferimenti

Per la dimostrazione, cf. Ciarlet, cap. 4, §4.3

PG Ciarlet, Introduzione all'analisi e all'ottimizzazione di matrici numeriche , ed. Massone, coll. "Matematica. Appl. per la laurea magistrale”,1985( ristampa 2001) ( ISBN 2-225-68893-1 )

Vedi anche

link esterno

Corso di laurea in analisi digitale (2010) di R. Herbin, Università di Aix-Marseille
Tutorial Perché l'algoritmo di decomposizione LU funziona?