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.

Definizioa[aldatu | aldatu iturburu kodea]

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

$3\times 3$ motako matrizeentzat honakoa dugu: ${\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:

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

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

$L$ zein den jakin nahi badugu, honakoa egin behar da:

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

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

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

Hori hala da ${L'}_{k}$ $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: $A=P^{T}LU$ . Permutazio matrizea alderantzikagarria da eta bere alderantzikoa bere iraulia ere bada.

Aplikazioak eta adibideak[aldatu | aldatu iturburu kodea]

Ekuazio-sistemen ebazpena[aldatu | aldatu iturburu kodea]

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:

$\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:

$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:

$(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:

$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:

$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:

$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 ${\bar {c}}$ gai-askeen zutabe-matrizea berreskuratu behar dugu eta honakoa gogoratu: