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

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:$\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)=\left(\begin{array}{ccc}1& 0& 0\\ l_{21}& 1& 0\\ l_{31}& l_{32}& 1\end{array}\right)\left(\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right)$.

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^{\prime }}_{m-1}*...*{L^{\prime }}_2*{L^{\prime }}_1{)}^{-1}$

${L^{\prime }}_k$ bakoitza honakoa delarik:

${L^{\prime }}_k$ = $P_{m-1}*...*P_{k+1}*L_k*{P^{-1}}_{k+1}*...*{P^{-1}}_{m-1}$

Hori hala da ${L^{\prime }}_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

Ekuazio-sistemen ebazpena

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:

$\{\begin{array}{ccccccc}x& +& y& +& z& =& 2\\ 5x& +& 4y& +& 3z& =& 4\\ 2x& +& y& +& 2z& =& 1\end{array}$Sistemari matrize-forma emanez honakoa dugu:

$A\overline{x}=\overline{b}⟹\left(\begin{array}{ccc}1& 1& 1\\ 5& 4& 3\\ 2& 1& 2\end{array}\right)\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\left(\begin{array}{c}2\\ 4\\ 1\end{array}\right)$

Eta hura garatuz, oinarrizko matrizeak erabiliz:

$(A|b)=\left(\begin{array}{ccc}1& 1& 1\\ 5& 4& 3\\ 2& 1& 2\end{array}\right|\begin{array}{c}2\\ 4\\ 1\end{array})=E_{21}(-5)\left(\begin{array}{ccc}1& 1& 1\\ 0& -1& -2\\ 2& 1& 2\end{array}\right|\begin{array}{c}2\\ -6\\ 1\end{array})=E_{31}(-2)\left(\begin{array}{ccc}1& 1& 1\\ 0& -1& -2\\ 0& -1& 0\end{array}\right|\begin{array}{c}2\\ -6\\ -3\end{array})=E_{32}(-1)\left(\begin{array}{ccc}1& 1& 1\\ 0& -1& -2\\ 0& 0& 2\end{array}\right|\begin{array}{c}2\\ -6\\ 3\end{array})=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{array}{ccc}1& 0& 0\\ -5& 1& 0\\ 3& -1& 1\end{array}\right)$

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

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

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

$A=L\cdot U=\left(\begin{array}{ccc}1& 0& 0\\ 5& 1& 0\\ 2& 1& 1\end{array}\right)\left(\begin{array}{ccc}1& 1& 1\\ 0& -1& -2\\ 0& 0& 2\end{array}\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 $\overline{c}$ gai-askeen zutabe-matrizea berreskuratu behar dugu eta honakoa gogoratu:

$U\overline{x}=\overline{c}$

Beraz, matrizeak ekuazio-sistema gisa adierazita:

$\{\begin{array}{ccccccc}x& +& y& +& z& =& 2\\ & & -1y& +& -2z& =& -6\\ & & & & 2z& =& 3\end{array}$

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

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

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

Alderantzizko matrizearen kalkulua

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

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

Zenbait programa informatiko formula horretan oinarritzen dira.