Ugrás a tartalomhoz

LU felbontás

Ellenőrzött
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átrixot egy alsó- és egy felső háromszögmátrix szorzatára bontja. 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]

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

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 -as mátrixra így néz ki:

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

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

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

Létezés és egyértelműség

[szerkesztés]

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]

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:

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]

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

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átrix főátlójának minden eleme egy. Ebben az esetben az egyenletrendszer megoldása a következő:

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

Ritkán kitöltött (sparse) mátrix felbontása

[szerkesztés]

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átrix 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]

Lineáris egyenletrendszer megoldása

[szerkesztés]

Legyen adott a következő egyenlet

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 egyenletet y-ra.
  2. Aztán oldjuk meg az 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 mátrix

[szerkesztés]

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

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

Determináns

[szerkesztés]

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

Jegyzetek

[szerkesztés]

Források

[szerkesztés]

További információk

[szerkesztés]