LU faktorizazio

Aljebra linealean, LU faktorizazioa edo LU deskonposaketa (ingelesezko Lower-Upper-etik) matrize bat faktorizatzeko modu bat da, zeinak emaitza gisa bi matrize ematen dituen: bata behe-triangeluarra eta bestea goi-triangeluarra. Faktorizazio modu hau gehienbat ekuazio-sistemak eraginkorrago ebazteko erabiltzen da, edo alderantzizko matrizeak aurkitzeko, besteak beste. LU faktorizazioa burutzeko oinarrizko matrizeak erabili ohi dira.

Izan bedi ${\displaystyle A}$ matrize alderantzikagarri bat (ez balitz baliteke emaitza desberdinak egotea). Jakina da ${\displaystyle A=LU}$ dela, non ${\displaystyle L}$ eta ${\displaystyle U}$ matrize behe- eta goi-triangeluarrak diren hurrenez hurren.

${\displaystyle 3\times 3}$ motako matrizeentzat honakoa dugu:${\displaystyle {\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{pmatrix}={\begin{pmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\\\end{pmatrix}{\begin{pmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{pmatrix}$.

Bestalde, PLU deskonposaketak honako itxura du:

${\displaystyle L_{m-1}P_{m-1}...L_{2}P_{2}L_{1}P_{1}A=U}$

Non ${\displaystyle L_{m-1}...L_{1}$ matrize behe-triangeluarrak diren, ${\displaystyle P_{m-1}...P_{1}$ permutazio-matrizeak eta ${\displaystyle U}$ matrize goi-triangeluarra.

${\displaystyle L}$ zein den jakin nahi badugu, honakoa egin behar da:

${\displaystyle L=({L'}_{m-1}*...*{L'}_{2}*{L'}_{1})^{-1}$

${\displaystyle {L'}_{k}$ bakoitza honakoa delarik:

${\displaystyle {L'}_{k}$ = ${\displaystyle {P}_{m-1}*...*{P}_{k+1}*{L}_{k}*{P^{-1}_{k+1}*...*{P^{-1}_{m-1}$

Hori hala da ${\displaystyle {L'}_{k}$ ${\displaystyle L_{k}$-ren berdina delako, baina azpidiagonaleko elementuak permutatuta dituela. Permutazio matrizea alderantzikagarria da eta bere alderantzikoa bere iraulia ere bada.

Faktorizazio modu hau ikusteko beste modu bat honakoa da: ${\displaystyle A=P^{T}LU}$. Permutazio matrizea alderantzikagarria da eta bere alderantzikoa bere iraulia ere bada.

LU faktorizazioak ekuazio-sistemen ebazpena erraztu dezake, ekuazio edo ezezagun ugariko sistemetan. Hartarako, Gauss-Jordanen metodoa gogoratzea komeni da lehenik.

Izan bedi honako ekuazio-sistema:

${\displaystyle \left\{\begin{array}{rcrcrcr}\,x&+&\,y&+&\,z&=&2\\5\,x&+&4\,y&+&3\,z&=&4\\2\,x&+&\,y&+&2\,z&=&1\end{array}\right.}$Sistemari matrize-forma emanez honakoa dugu:

${\displaystyle A{\bar {x}={\bar {b}\Longrightarrow {\begin{pmatrix}1&1&1\\5&4&3\\2&1&2\\\end{pmatrix}{\begin{pmatrix}x\\y\\z\\\end{pmatrix}={\begin{pmatrix}2\\4\\1\\\end{pmatrix}$

Eta hura garatuz, oinarrizko matrizeak erabiliz:

${\displaystyle (A|b)=\left({\begin{matrix}1&1&1\\5&4&3\\2&1&2\end{matrix}\right|\left.{\begin{matrix}2\\4\\1\end{matrix}\right)=E_{21}(-5)\left({\begin{matrix}1&1&1\\0&-1&-2\\2&1&2\end{matrix}\right|\left.{\begin{matrix}2\\-6\\1\end{matrix}\right)=E_{31}(-2)\left({\begin{matrix}1&1&1\\0&-1&-2\\0&-1&0\end{matrix}\right|\left.{\begin{matrix}2\\-6\\-3\end{matrix}\right)=E_{32}(-1)\left({\begin{matrix}1&1&1\\0&-1&-2\\0&0&2\end{matrix}\right|\left.{\begin{matrix}2\\-6\\3\end{matrix}\right)=U}$

Jakina denez L^-1 matrizea erabilitako oinarrizko matrize guztien arteko biderketa dela:

${\displaystyle L^{-1}=E_{21}(-5)\cdot E_{31}(-2)\cdot E_{32}(-1)=\left({\begin{matrix}1&0&0\\-5&1&0\\3&-1&1\end{matrix}\right)}$

Haren alderantzizkoa izango da L matrizea, zeina kalkulatzeko oinarrizko matrizeen propietateak erabil daitezkeen:

${\displaystyle L=(L^{-1})^{-1}=\left({\begin{matrix}1&0&0\\5&1&0\\2&1&1\end{matrix}\right)}$

Beraz, ateratako L eta U matrizeen arteko biderketa izango da A matrizearen LU faktorizazioa:

${\displaystyle A=L\cdot U=\left({\begin{matrix}1&0&0\\5&1&0\\2&1&1\end{matrix}\right)\left({\begin{matrix}1&1&1\\0&-1&-2\\0&0&2\end{matrix}\right)}$

Definizioan esan bezala, goiko adierazpenean ikus daiteke L eta U matrizea triangeluarrak direla, lehena behe-triangeluarra eta bigarrena goi-triangeluarra. Behin LU faktorizazioa edukita, interesgarria izan daiteke haren U osagaia erabiltzea ekuazio-sistema ebazteko, izan ere, matrizea forma triangeluarrekoa izanda, ekuazio-sistema berehalakoa bihurtzen da. Hartarako U kalkulatu bitartean eskuratu dugun ${\displaystyle {\bar {c}$ gai-askeen zutabe-matrizea berreskuratu behar dugu eta honakoa gogoratu:

${\displaystyle U{\bar {x}={\bar {c}$

Beraz, matrizeak ekuazio-sistema gisa adierazita:

${\displaystyle \left\{\begin{array}{rcrcrcr}\,x&+&\,y&+&\,z&=&2\\\,&&-1\,y&+&-2\,z&=&-6\\\,&&\,&&2\,z&=&3\end{array}\right.}$

Eta ekuazio-sistema hori berehalakoa da: ${\displaystyle x={\frac {-5}{2}$, ${\displaystyle y=3}$ eta ${\displaystyle z={\frac {3}{2}$.

LU faktorizazioari errendimendu handiagoa ateratzeko, ekuazio sistema honela ere ebatz daiteke:

1. Lehenik, ${\displaystyle Ly=b}$ ebatzi, ${\displaystyle y}$ aldagaia ateraz.
2. Ondoren, ${\displaystyle Ux=y}$ ebatzi, ${\displaystyle x}$ aldagaia ateraz.

Alderantzizko matrizeak kalkula daitezke LU faktorizazioa erabiliz, honako formula jarraituz:

${\displaystyle A^{-1}=U^{-1}L^{-1}P}$

Zenbait programa informatiko formula horretan oinarritzen dira.