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: 
        \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^TLU. 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:

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

 
        U\bar x = \bar c 

Beraz, matrizeak ekuazio-sistema gisa adierazita:

    \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:     x = \frac{-5}{2},     y = 3 eta     z = \frac{3}{2}.

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

# Lehenik,  Ly = b  ebatzi, y aldagaia ateraz.
# 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.

## Kanpo estekak