La descomposició LU d'una matriu és la factorització d'una matriu quadrada donada en dues matrius triangulars, una matriu triangular superior i una matriu triangular inferior, de manera que el producte d'aquestes dues matrius dóna la matriu original. Va ser introduït per Alan Turing el 1948, que també va crear la màquina de Turing.

El mètode de descomposició LU de factoritzar una matriu com a producte de dues matrius triangulars té diverses aplicacions, com ara la solució d'un sistema d'equacions, que és part integral de moltes aplicacions, com ara trobar corrent en un circuit i resoldre problemes de sistemes dinàmics discrets. ; trobar la inversa d'una matriu i trobar el determinant de la matriu.

Què és la descomposició de L U?

Una matriu quadrada A es pot descompondre en dues matrius quadrades L i U de manera que A = L U on U és una matriu triangular superior formada com a resultat d'aplicar el mètode d'eliminació de Gauss a A, i L és una matriu triangular inferior amb elements diagonals. igual 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} .

creació de llistes en java

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

Tal que A = L U és a dir,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]

Aquí el valor de l₂₁, en₁₁, etc. es poden comparar i trobar.

Què és el mètode d'eliminació de Gauss?

L'eliminació de Gauss, també coneguda com a eliminació de Gauss-Jordan, és un mètode utilitzat en àlgebra lineal per resoldre sistemes d'equacions lineals i trobar la inversa d'una matriu. Porta el nom del matemàtic Carl Friedrich Gauss i també del matemàtic Wilhelm Jordan, que van fer contribucions importants al seu desenvolupament.

Segons el mètode d'eliminació de Gauss:

1. Qualsevol fila zero hauria d'estar a la part inferior de la matriu.
2. La primera entrada diferent de zero de cada fila hauria d'estar a la dreta de la primera entrada diferent de zero de la fila anterior. Aquest mètode redueix la matriu a la forma d'escalons de fila.

Mètode de descomposició LU

Per fabricar qualsevol matriu quadrada en dues matrius triangulars, és a dir, una és una matriu triangular inferior i l'altra és una matriu triangular superior, podem utilitzar els passos següents.

• Donat un conjunt d'equacions lineals, primer convertiu-les a la forma matricial A X = C on A és la matriu de coeficients, X és la matriu variable i C és la matriu de nombres del costat dret de les equacions.
• Ara, reduïu la matriu de coeficients A, és a dir, la matriu obtinguda a partir dels coeficients de variables de totes les equacions donades de manera que per a 'n' variables tinguem una matriu nXn, a la forma d'escalons de fila mitjançant el mètode d'eliminació de Gauss. La matriu així obtinguda és U.
• Per trobar L, tenim dos mètodes. El primer és assumir els elements restants com a variables artificials, fer equacions amb A = L U i resoldre-les per trobar aquestes variables artificials. L'altre mètode és que els elements restants són els coeficients multiplicadors a causa dels quals les posicions respectives es van convertir en zero a la matriu U. (Aquest mètode és una mica complicat d'entendre amb paraules, però quedaria clar a l'exemple següent)
• Ara, tenim A (la matriu de coeficients nXn), L (la matriu triangular inferior de nXn), U (la matriu triangular superior de nXn), X (la matriu de variables nX1) i C (la matriu nX1 de nombres a la dreta). costat de les equacions).
• El sistema d'equacions donat és A X = C. Substituïm A = L U. Així, tenim L U X = C. Posem Z = U X, on Z és una matriu o variables artificials i resolem per L Z = C primer i després resolem per U X = Z per trobar X o els valors de les variables, que era necessari.

Exemple de descomposició LU

Resol el següent sistema d'equacions mitjançant el mètode de descomposició 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*}

Solució: aquí tenim 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}

tal que A X = C. Ara, primer considerem

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

i convertiu-lo en forma d'escaló de fila mitjançant el mètode d'eliminació de Gauss. Per tant, fent

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

obtenim

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}

Ara, fent

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

Obtenim

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

(Recordeu de mantenir sempre el signe '-' entremig, substituïu el signe '+' per dos signes '-') Per tant, obtenim L =

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

i U =

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

(observeu que a la matriu L,

l_{21} = 4

és de (1),

l_{31} = 3

és de (2) i

generador de cadenes java

l_{32} = -2

és de (3)) Ara suposem Z

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

i resol 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}

Així doncs, tenim

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

Solucionant, aconseguim

z_1 = 1

,

z_2 = 2

i

z_3 = 5

. Ara, resolem 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}

Per tant, aconseguim

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Per tant, la solució del sistema d'equacions lineals donat és

x_1 = 1

cadena java a int

,

x_2 = 0.5

,

x_3 = -0.5

i per tant la matriu X =

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

Exercici sobre descomposició LU

En la descomposició LU de la matriu

| 2 2 |
| 4 9 |

, si els elements diagonals de U són tots dos 1, aleshores l'entrada diagonal inferior l22 de L és (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Per a la solució, vegeu PORTA | GATE-CS-2015 (Conjunt 1) | Pregunta 65 .

Preguntes freqüents sobre la descomposició de LU

Què és el mètode de descomposició LU?

La descomposició LU, abreviatura de descomposició inferior-superior, és una tècnica de factorització de matrius utilitzada per descompondre una matriu quadrada en el producte d'una matriu triangular inferior (L) i una matriu triangular superior (U). S'utilitza habitualment per simplificar la resolució de sistemes d'equacions lineals i el càlcul de determinants.

Per què la descomposició de LU és única?

La descomposició LU és única perquè proporciona una manera de factoritzar una matriu quadrada A en matrius triangulars inferior i superior (L i U) de manera única, permetent la resolució eficient de sistemes lineals i el càlcul de determinants.

Com es calcula la descomposició de LU?

La descomposició LU es calcula mitjançant l'eliminació gaussiana, on transformeu una matriu quadrada A en matrius triangulars inferiors (L) i superiors (U) realitzant operacions de files mentre feu un seguiment dels canvis en matrius separades. Aquest procés és iteratiu i continua fins que A es descomposa completament. El mètode amb tots els passos per a la descomposició de LU es mostra a l'article.

Quan la descomposició de LU no és possible?

La descomposició LU pot no ser possible quan la matriu A és singular (no invertible) o quan requereix pivotar per a l'estabilitat, però l'element de pivot es converteix en zero, provocant la divisió per zero durant el procés de descomposició.

Hi ha alternatives a la descomposició de LU?

Sí, les alternatives a la descomposició de LU inclouen Descomposició de Cholesky per a matrius definides positives simètriques, descomposició QR per a matrius generals i mètodes basats en valors propis com la descomposició espectral i la descomposició de valor singular (SVD) per a diverses operacions i aplicacions de matrius.

Es pot aplicar la descomposició LU a matrius no quadrades?

La descomposició LU s'aplica normalment a matrius quadrades. Per a les matrius rectangulars, la descomposició QR s'utilitza més habitualment. Tanmateix, variacions com la descomposició LUP també poden gestionar matrius rectangulars, on P és una matriu de permutació.