Descompunerea LU a unei matrice este factorizarea unei matrice pătrate date în două matrice triunghiulare, o matrice triunghiulară superioară și o matrice triunghiulară inferioară, astfel încât produsul acestor două matrice să dea matricea originală. A fost introdus de Alan Turing în 1948, care a creat și mașina Turing.

Metoda de descompunere LU de factorizare a unei matrice ca produs din două matrici triunghiulare are diverse aplicații, cum ar fi o soluție a unui sistem de ecuații, care în sine este o parte integrantă a multor aplicații, cum ar fi găsirea curentului într-un circuit și rezolvarea problemelor de sistem dinamic discret. ; aflarea inversului unei matrice și aflarea determinantului matricei.

Ce este descompunerea L U?

O matrice pătrată A poate fi descompusă în două matrice pătrate L și U astfel încât A = L U unde U este o matrice triunghiulară superioară formată ca urmare a aplicării metodei de eliminare Gauss pe A, iar L este o matrice triunghiulară inferioară cu elemente diagonale fiind egal cu 1.

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

regex în java

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

Astfel încât A = L U adică,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]

Aici valoarea lui l_{douăzeci și unu}, în_unsprezece, etc. pot fi comparate și găsite.

Ce este metoda de eliminare Gauss?

Eliminarea Gauss, cunoscută și sub denumirea de Eliminare Gauss-Iordan, este o metodă folosită în algebra liniară pentru a rezolva sisteme de ecuații liniare și pentru a găsi inversul unei matrice. Este numit după matematicianul Carl Friedrich Gauss și, de asemenea, matematicianul Wilhelm Jordan, care au contribuit semnificativ la dezvoltarea sa.

Conform metodei de eliminare Gauss:

1. Orice rând zero ar trebui să fie în partea de jos a matricei.
2. Prima intrare diferită de zero a fiecărui rând ar trebui să fie în partea dreaptă a primei intrări diferite de zero a rândului precedent. Această metodă reduce matricea la forma eșalonului rând.

Metoda de descompunere a LU

Pentru a fabrica orice matrice pătrată în două matrici triunghiulare, adică una este o matrice triunghiulară inferioară și cealaltă este o matrice triunghiulară superioară, putem folosi următorii pași.

• Având în vedere un set de ecuații liniare, mai întâi convertiți-le în forma matriceală A X = C unde A este matricea coeficienților, X este matricea variabilă și C este matricea numerelor din partea dreaptă a ecuațiilor.
• Acum, reduceți matricea de coeficienți A, adică matricea obținută din coeficienții variabilelor din toate ecuațiile date, astfel încât pentru „n” variabile să avem o matrice nXn, la forma eșalonului rând folosind metoda de eliminare Gauss. Matricea astfel obținută este U.
• Pentru a găsi L, avem două metode. Prima este să presupunem elementele rămase ca niște variabile artificiale, să faceți ecuații folosind A = L U și să le rezolvați pentru a găsi acele variabile artificiale. Cealaltă metodă este că elementele rămase sunt coeficienții multiplicatori din cauza cărora pozițiile respective au devenit zero în matricea U. (Această metodă este puțin dificil de înțeles prin cuvinte, dar ar fi clar în exemplul de mai jos)
• Acum, avem A (matricea coeficientului nXn), L (matricea nXn triunghiulară inferioară), U (matricea nXn triunghiulară superioară), X (matricea nX1 a variabilelor) și C (matricea nX1 a numerelor din dreapta). partea de mână a ecuațiilor).
• Sistemul de ecuații dat este A X = C. Înlocuim A = L U. Astfel, avem L U X = C. Punem Z = U X, unde Z este o matrice sau variabile artificiale și rezolvăm mai întâi pentru L Z = C și apoi rezolvăm pentru U X = Z pentru a găsi X sau valorile variabilelor, care a fost necesar.

Exemplu de descompunere LU

Rezolvați următorul sistem de ecuații folosind metoda de descompunere 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*}

Rezolvare: Aici avem 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}

și

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

astfel încât A X = C. Acum, luăm în considerare mai întâi

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

și convertiți-l în formă de eșalon de rând folosind metoda de eliminare Gauss. Deci, făcând

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

primim

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}

Acum, făcând

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

Primim

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

(Nu uitați să păstrați întotdeauna semnul ‘ – ‘ între ele, înlocuiți semnul ‘ + ‘ cu două semne ‘ – ‘) Prin urmare, obținem L =

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

și U =

protocolul udp

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

(observați că în matricea L,

l_{21} = 4

este de la (1),

l_{31} = 3

este de la (2) și

l_{32} = -2

este de la (3)) Acum presupunem Z

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

și rezolvați 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}

Deci avem

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

Rezolvând, obținem

z_1 = 1

,

z_2 = 2

și

z_3 = 5

. Acum, rezolvăm 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}

exemple de programe java

Prin urmare, primim

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Astfel, soluția sistemului dat de ecuații liniare este

x_1 = 1

,

x_2 = 0.5

,

x_3 = -0.5

și deci matricea X =

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

Exercițiu despre descompunerea LU

În descompunerea LU a matricei

| 2 2 |
| 4 9 |

, dacă elementele diagonale ale lui U sunt ambele 1, atunci intrarea diagonală inferioară l22 a lui L este (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Pentru soluție, vezi PORTA | GATE-CS-2015 (Setul 1) | Întrebarea 65 .

Întrebări frecvente despre descompunerea LU

Ce este metoda de descompunere a LU?

Descompunerea LU, prescurtare pentru descompunerea inferioară-superioară, este o tehnică de factorizare a matricei utilizată pentru a descompune o matrice pătrată în produsul unei matrice triunghiulare inferioară (L) și o matrice triunghiulară superioară (U). Este folosit în mod obișnuit pentru a simplifica rezolvarea sistemelor de ecuații liniare și calcularea determinanților.

De ce este unică descompunerea LU?

Descompunerea LU este unică deoarece oferă o modalitate de a factoriza o matrice pătrată A în matrice triunghiulară inferioară și superioară (L și U) în mod unic, permițând rezolvarea eficientă a sistemelor liniare și calcularea determinanților.

Cum se calculează descompunerea LU?

Descompunerea LU este calculată utilizând eliminarea gaussiană, în care transformați o matrice pătrată A în matrice triunghiulară inferioară (L) și superioară (U), efectuând operații pe rând, ținând evidența modificărilor din matrice separate. Acest proces este iterativ și continuă până când A este complet descompus. Metoda cu toți pașii pentru descompunerea LU este dată în articol.

Când descompunerea LU nu este posibilă?

Descompunerea LU poate să nu fie posibilă atunci când matricea A este singulară (neinversibilă) sau când necesită pivotare pentru stabilitate, dar elementul pivot devine zero, provocând diviziunea la zero în timpul procesului de descompunere.

Există alternative la descompunerea LU?

Da, alternative la descompunerea LU includ Descompunerea Cholesky pentru matrici definite pozitive simetrice, descompunere QR pentru matrice generale și metode bazate pe valori proprii, cum ar fi descompunerea spectrală și descompunerea cu valori singulare (SVD) pentru diferite operații și aplicații cu matrice.

Poate fi aplicată descompunerea LU la matrici non-pătrate?

Descompunerea LU este de obicei aplicată matricelor pătrate. Pentru matricele dreptunghiulare, descompunerea QR este mai frecvent utilizată. Cu toate acestea, variații precum descompunerea LUP pot gestiona și matrice dreptunghiulare, unde P este o matrice de permutare.