LU felbontás

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

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

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

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=LL^{*}.\,$

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

${\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átrix 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

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

Lineáris egyenletrendszer megoldása

Legyen adott a következő egyenlet

$Ax=LUx=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 mátrix

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

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

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

Determináns

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}.$

Források

• Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics (1997). ISBN 978-0-89871-361-9 
• Introduction to Algorithms. MIT Press and McGraw-Hill (2001). ISBN 978-0-262-03293-3 
• Matrix Computations, 3rd, Johns Hopkins (1996). ISBN 978-0-8018-5414-9 .
• Matrix Analysis. Cambridge University Press (1985). ISBN 0-521-38632-2 . See Section 3.5.
• The Theory of Matrices in Numerical Analysis (1975) .
• Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix. Sablon:Arxiv (1997) .
• LU Decomposition and Its Applications, Numerical Recipes in FORTRAN: The Art of Scientific Computing [archivált változat], 2nd, Cambridge University Press, 34–42. o. (1992). Hozzáférés ideje: 2009. március 29. [archiválás ideje: 2009. szeptember 6.]  Archiválva 2009. szeptember 6-i dátummal a Wayback Machine-ben

További információk

• LU decomposition on MathWorld.
• LU decomposition on Math-Linux.
• LAPACK is a collection of FORTRAN subroutines for solving dense linear algebra problems
• ALGLIB includes a partial port of the LAPACK to C++, C#, Delphi, etc.
• Online Matrix Calculator performs LU decomposition
• LU decomposition at Holistic Numerical Methods Institute
• Module for LU Factorization with Pivoting
• LU Decomposition by Ed Pegg, Jr., The Wolfram Demonstrations Project, 2007.