La scomposizione LU di una matrice è la fattorizzazione di una data matrice quadrata in due matrici triangolari, una matrice triangolare superiore e una matrice triangolare inferiore, in modo tale che il prodotto di queste due matrici dia la matrice originale. Fu introdotto da Alan Turing nel 1948, ideatore anche della macchina di Turing.

Il metodo di decomposizione LU per fattorizzare una matrice come prodotto di due matrici triangolari ha varie applicazioni come la soluzione di un sistema di equazioni, che a sua volta è parte integrante di molte applicazioni come la ricerca di corrente in un circuito e la soluzione di problemi di sistemi dinamici discreti ; trovare l'inversa di una matrice e trovare il determinante della matrice.

Cos'è la decomposizione L U?

Una matrice quadrata A può essere scomposta in due matrici quadrate L e U tali che A = L U dove U è una matrice triangolare superiore formata come risultato dell'applicazione del metodo di eliminazione di Gauss su A, e L è una matrice triangolare inferiore con elementi diagonali che sono pari a 1.

Per A =egin{bmatrix} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{bmatrix} .

js stringa multilinea

Abbiamo L = egin{bmatrix} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 1 end{bmatrix} e U =egin{bmatrix} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{bmatrix} ;

Tale che A = L U cioè,left[egin{array}{lll} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{array} ight]=left[egin{array}{lll} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 0 end{array} ight] cdot left[egin{array}{ccc} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{array} ight]

Qui il valore di l_ventuno, In_undici, ecc. possono essere confrontati e trovati.

Cos'è il metodo di eliminazione di Gauss?

L'eliminazione gaussiana, nota anche come eliminazione Gauss-Jordan, è un metodo utilizzato in algebra lineare per risolvere sistemi di equazioni lineari e per trovare l'inverso di una matrice. Prende il nome dal matematico Carl Friedrich Gauss e anche dal matematico Wilhelm Jordan, che diedero un contributo significativo al suo sviluppo.

Secondo il metodo di eliminazione di Gauss:

1. Qualsiasi riga zero dovrebbe trovarsi nella parte inferiore della matrice.
2. La prima voce diversa da zero di ciascuna riga dovrebbe trovarsi sul lato destro della prima voce diversa da zero della riga precedente. Questo metodo riduce la matrice alla forma a scaglioni di righe.

Metodo di decomposizione LU

Per fabbricare qualsiasi matrice quadrata in due matrici triangolari, ovvero una è una matrice triangolare inferiore e l'altra è una matrice triangolare superiore, possiamo utilizzare i seguenti passaggi.

• Dato un insieme di equazioni lineari, convertile prima nella forma matriciale A X = C dove A è la matrice dei coefficienti, X è la matrice delle variabili e C è la matrice dei numeri sul lato destro delle equazioni.
• Ora, riduci la matrice dei coefficienti A, ovvero la matrice ottenuta dai coefficienti delle variabili in tutte le equazioni date in modo tale che per 'n' variabili abbiamo una matrice nXn, alla forma a scaglioni usando il metodo di eliminazione di Gauss. La matrice così ottenuta è U.
• Per trovare L abbiamo due metodi. Il primo è assumere gli elementi rimanenti come variabili artificiali, creare equazioni utilizzando A = L U e risolverle per trovare quelle variabili artificiali. L'altro metodo è che gli elementi rimanenti siano i coefficienti moltiplicatori per cui le rispettive posizioni diventano zero nella matrice U. (Questo metodo è un po' complicato da comprendere a parole, ma risulterebbe chiaro nell'esempio seguente)
• Ora abbiamo A (la matrice dei coefficienti nXn), L (la matrice triangolare inferiore nXn), U (la matrice triangolare superiore nXn), X (la matrice di variabili nX1) e C (la matrice di numeri nX1 a destra). lato destro delle equazioni).
• Il sistema di equazioni dato è A X = C. Sostituiamo A = L U. Quindi, abbiamo L U X = C. Mettiamo Z = U X, dove Z è una matrice o variabili artificiali e risolviamo prima L Z = C e poi risolviamo per U X = Z per trovare X o i valori delle variabili, che era richiesto.

Esempio di scomposizione LU

Risolvi il seguente sistema di equazioni utilizzando il metodo di decomposizione LU:

egin{equation*} x_1 + x_2 + x_3 = 1 end{equation*} egin{equation*} 4x_1 + 3x_2 – x_3 = 6 end{equation*} egin{equation*} 3x_1 + 5x_2 + 3x_3 = 4 end{equation*}

Soluzione: qui abbiamo A =

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} , X = egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

E

C = egin{bmatrix} 1 6 4 end{bmatrix}

tale che A X = C. Ora consideriamo prima

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix}

e convertirlo in forma di scaglione di righe utilizzando il metodo di eliminazione di Gauss. Quindi, facendo

egin{equation} R_2 o R_2 – 4R_1 end{equation} egin{equation} R_3 o R_3 – 3R_1 end{equation}

noi abbiamo

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} sim

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 2 & 0 end{bmatrix}

Ora, facendo

egin{equation} R_3 o R_3 – (-2)R_2 end{equation}

Noi abbiamo

sim egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(Ricordati di mantenere sempre il segno ‘ – ‘ in mezzo, sostituire il segno ‘ + ‘ con due segni ‘ – ‘) Quindi, otteniamo L =

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix}

e U =

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(notare che nella matrice L,

java switch int

l_{21} = 4

proviene da (1),

l_{31} = 3

è da (2) e

l_{32} = -2

proviene da (3)) Ora assumiamo Z

= egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

e risolvi L Z = C.

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix} egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

= egin{bmatrix} 1 6 4 end{bmatrix}

Quindi, abbiamo

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

Risolvendo, otteniamo

z_1 = 1

,

z_2 = 2

E

z_3 = 5

. Ora risolviamo U X = Z

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix} egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

= egin{bmatrix} 1 2 5 end{bmatrix}

Pertanto, otteniamo

casuale in c

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Pertanto, la soluzione del dato sistema di equazioni lineari è

x_1 = 1

,

x_2 = 0.5

,

x_3 = -0.5

e quindi la matrice X =

egin{bmatrix} 1 0.5 -0.5 end{bmatrix}

Esercizio sulla scomposizione LU

Nella scomposizione LU della matrice

| 2 2 |
| 4 9 |

, se gli elementi diagonali di U sono entrambi 1, allora la voce diagonale inferiore l22 di L è (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Per la soluzione, vedere CANCELLO | GATE-CS-2015 (Set 1) | Domanda 65 .

Domande frequenti sulla decomposizione LU

Qual è il metodo di scomposizione LU?

La decomposizione LU, abbreviazione di Lower-Upper decomposition, è una tecnica di fattorizzazione della matrice utilizzata per scomporre una matrice quadrata nel prodotto di una matrice triangolare inferiore (L) e una matrice triangolare superiore (U). È comunemente impiegato per semplificare la risoluzione di sistemi di equazioni lineari e il calcolo dei determinanti.

Perché la scomposizione LU è unica?

La scomposizione LU è unica perché fornisce un modo per fattorizzare una matrice quadrata A in matrici triangolari inferiore e superiore (L e U) in modo univoco, consentendo la risoluzione efficiente di sistemi lineari e il calcolo dei determinanti.

Come viene calcolata la scomposizione LU?

La scomposizione LU viene calcolata utilizzando l'eliminazione gaussiana, in cui si trasforma una matrice quadrata A in matrici triangolari inferiore (L) e superiore (U) eseguendo operazioni sulle righe tenendo traccia delle modifiche nelle matrici separate. Questo processo è iterativo e continua finché A non è completamente scomposto. Il metodo con tutti i passaggi per la scomposizione della LU è riportato nell'articolo.

Quando la scomposizione LU non è possibile?

La decomposizione LU potrebbe non essere possibile quando la matrice A è singolare (non invertibile) o quando richiede la rotazione per stabilità, ma l'elemento pivot diventa zero, causando la divisione per zero durante il processo di decomposizione.

Esistono alternative alla scomposizione LU?

Sì, le alternative alla scomposizione LU includono Decomposizione di Cholesky per matrici definite positive simmetriche, decomposizione QR per matrici generali e metodi basati sugli autovalori come la decomposizione spettrale e la decomposizione in valori singolari (SVD) per varie operazioni e applicazioni sulle matrici.

La scomposizione LU può essere applicata a matrici non quadrate?

La scomposizione LU viene generalmente applicata alle matrici quadrate. Per le matrici rettangolari, è più comunemente utilizzata la scomposizione QR. Tuttavia, variazioni come la scomposizione LUP possono gestire anche matrici rettangolari, dove P è una matrice di permutazione.