LU felbontás

A Wikipédiából, a szabad enciklopédiából

Az LU felbontás (ejtsd: el-ú-felbontás) egy olyan mátrixfelbontás, amely egy mátrixból alsó- és egy felső háromszögmátrixot készít, értsd: ilyen mátrixok szorzatára bontja. Az eredmény lehet még permutációmátrix is . Ezt a felbontást a numerikus analízis során lineáris egyenletrendszerek megoldásra és determináns számolására használhatjuk.

Az elnevezés a low(er) („alsó”) és up(per) (felső) angol határozószók kezdőbetűiből ered.

Definíciók[szerkesztés | forrásszöveg szerkesztése]

Legyen A egy kvadratikus mátrix, amelyre az LU felbontás a következő alakú:

 A = LU, \,

ahol L és U alsó és felső trianguláris mátrixok (azonos méretűek) . Ez azt jelenti, hogy az L mátrix főátlója felett illetve az U mátrix főátlója alatt csak nullák találhatók. Ez egy 3 \times 3 -as mátrixra így néz ki:

 
        \begin{bmatrix}
           a_{11} & a_{12} & a_{13} \\
           a_{21} & a_{22} & a_{23} \\
           a_{31} & a_{32} & a_{33} \\
        \end{bmatrix} =
      \begin{bmatrix}
           l_{11} & 0 & 0 \\
           l_{21} & l_{22} & 0 \\
           l_{31} & l_{32} & l_{33} \\
        \end{bmatrix}
        \begin{bmatrix}
           u_{11} & u_{12} & u_{13} \\
           0 & u_{22} & u_{23} \\
           0 & 0 & u_{33} \\
        \end{bmatrix}.

Egy LDU felbontás a következő formájú:

 A = LDU, \,

ahol D egy diagonális mátrix és L és U egység trianguláris mátrixok, ez azt jelenti, hogy a főátlóikban csak egyesek szerepelnek.

Egy LUP felbontás (vagy más néven LU felbontás részleges főelemkiválasztással) a következő formájú:

 A = LUP, \,

ahol L és U szintén alsó és felső trianguláris mátrixok és P egy permutációs mátrix,amely egy olyan négyzetes mátrix, amelynek minden sorában és oszlopában pontosan egy elem 1 és a többi mind 0.

Egy LU felbontás teljes pivotizálással (Trefethen és Bau) a következő formájú:

 PAQ = LU, \,

Létezés és egyértelműség[szerkesztés | forrásszöveg szerkesztése]

Egy invertálható mátrixnak akkor és csak akkor létezik LU felbontása, ha az első főátló nem tartalmaz nullát. Csak egy olyan felbontás létezik, ahol L (vagy U) főátlóiban egyesek vannak. A mátrixnak szintén csak egy LDU felbontása létezik azonos feltételek mellett.

Ha egy mátrix szinguláris,akkor létezik LU felbontása. Valójában, ha egy négyzetes mátrix rangja k akkor az LU felbontás akkor létezik, ha az első k főátló nem nulla, habár ez fordítva nem igaz.

A szükséges és elégséges feltételek teljesülése mellett nem szükséges invertálhatónak lennie egy mátrixnak, hogy létezzen LU felbontása.A feltételek teljesülése esetén az almátrixok rangja megegyezik. A Gauss-elimináció legáltalánosabb esete az LU felbontás.

Minden mátrixnak - négyzetes vagy sem - létezik LUP felbontása. L és P négyzetes mátrixok, de U olyan alakú mint A. A felső trianguláris mátrix főátlója felett csak nulla értékek szerepelhetnek, a bal felső saroktól kezdve. Az LUP felbontás akkor teljes, ha az U főátlója csak egyeseket tartalmaz.

Pozitív definit mátrixok[szerkesztés | forrásszöveg szerkesztése]

Ha egy A mátrix Hermite szimmetrikus és pozitív definit, akkor U mátrix L transzponáltja. Ebben az esetben A -t a következőképpen írhatjuk fel:

 A = L L^{*}. \,

Ezt a felbontást Cholesky-felbontásnak nevezzük. Mindig csak egy Cholesky-felbontás létezik. Továbbá, a Cholesky-felbontás kiszámítása hatékonyabb és numerikusan stabilabb mint az LU felbontás kiszámítása.

Egyszerű példa[szerkesztés | forrásszöveg szerkesztése]

 
        \begin{bmatrix}
           4 & 3 \\
           6 & 3 \\
        \end{bmatrix} =
      \begin{bmatrix}
           l_{11} & 0 \\
           l_{21} & l_{22} \\
        \end{bmatrix}
        \begin{bmatrix}
           u_{11} & u_{12} \\
           0 & u_{22} \\
        \end{bmatrix}.

Egyik módja a LU felbontás megtalálásának, hogy egyszerűen megoldjuk a lineáris egyenletrendszereket:

l_{11} \cdot u_{11} + 0 \cdot 0 = 4
l_{11} \cdot u_{12} + 0 \cdot u_{22} = 3
l_{21}\cdot u_{11} + l_{22} \cdot 0 = 6
l_{21}\cdot u_{12} + l_{22} \cdot u_{22} = 3.

Ez a rendszer nem egyértelműen meghatározott. L és U mátrixok nem nulla elemei csak paraméterei a megoldásnak, tetszőleges más nem nulla elemre módosíthatók. Annak érdekében, hogy meghatározhassunk egy egyértelmű LU felbontást, néhány megkötést kell tennünk. Tegyük fel, hogy az alsó trianguláris mártix főátlójának minden eleme egy. Ebben az esetben az egyenletrendszer megoldása a következő:

l_{21} = 1.5
u_{11} = 4
u_{12} = 3
u_{22} = -1.5.

Visszahelyettesítve a kapott értékeket a fenti LU felbontásba:

 
        \begin{bmatrix}
           4 & 3 \\
           6 & 3 \\
        \end{bmatrix} =
      \begin{bmatrix}
           1 & 0 \\
           1.5 & 1 \\
        \end{bmatrix}
        \begin{bmatrix}
           4 & 3 \\
           0 & -1.5 \\
        \end{bmatrix}.

Ritkán kitöltött (sparse) mátrix felbontása[szerkesztés | forrásszöveg szerkesztése]

Ez az eljárás lehetővé teszi, hogy faktorizáljunk nagy méretű ritkán kitöltött (sparse) mátrixokat. Az eljárás megpróbálja megtalálni L és U zéró elemeit. Ideális esetben egy számítás műveletigényét a nem zéró elemek száma határozza meg, nem a mártix mérete.

Ez az eljárás az oszlopok és sorok felcserélhetőségét használja ki a kitöltés minimalizálására.

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

Lineáris egyenletrendszer megoldása[szerkesztés | forrásszöveg szerkesztése]

Legyen adott a következő egyenlet

A x = L U x = b \,

keressük az egyenlet megoldásait adott A és b esetén. A megoldást két logikai lépéssel végezzük:

  1. Először oldjuk meg az  Ly = b egyenletet y-ra.
  2. Aztán oldjuk meg az  Ux = y egyenletet x-re.

L és U trianguláris mátrixok (alsó és felső), így az egyenleteket akár behelyettesítéssel is megoldhatjuk, Gauss-elimináció nélkül is (az LU felbontás akár számítógéppel is végezhető). Ez a módszer gyorsabban eredményre vezet, mint a Gauss-elimináció olyan esetekben, amikor a mátrixegyenletet többször, különböző b-k esetén kell megoldani, mivel az LU felbontást csak egyszer kell elvégeznünk, a Gauss-eliminációt pedig minden b esetén újra kell számolnunk.

Inverz matrix[szerkesztés | forrásszöveg szerkesztése]

Az L és U mátrixok segítségével matrixok inverze kiszámítható:


A^{-1} = U^{-1}L^{-1}. \,

Mártixokat invertáló számítógépes eljárások gyakran alkalmazzák ezt a módszert.

Determináns[szerkesztés | forrásszöveg szerkesztése]

Az LU felbontás mátrix determinánsának gyors kiszámítására is alkalmas, mivel det(A) = det(L) det(U). Trianguláris mátrix determinánsa pedig a főátlóban levő elemek szorzataként áll elő, így

 \det(A) = \det(L) \det(U) = \prod_{i=1}^n u_{ii}.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

Kapcsolódó linkek[szerkesztés | forrásszöveg szerkesztése]