„LU felbontás” változatai közötti eltérés
| [ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
portál |
bővítés |
||
35. sor:
:<math> PAQ = LU, \, </math>
== Létezés és
Egy [[invertálható mátrix]]nak 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.
49. sor:
:<math> A = L L^{*}. \, </math>
Ezt a felbontást [[Cholesky-felbontás]]nak 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==
:<math>
\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}.
</math>
Egyik módja a LU felbontás megtalálásának, hogy egyszerűen megoldjuk a lineáris egyenletrendszereket:
:<math>l_{11} \cdot u_{11} + 0 \cdot 0 = 4</math>
:<math>l_{11} \cdot u_{12} + 0 \cdot u_{22} = 3</math>
:<math>l_{21}\cdot u_{11} + l_{22} \cdot 0 = 6</math>
:<math>l_{21}\cdot u_{12} + l_{22} \cdot u_{22} = 3.</math>
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ő:
:<math>l_{21} = 1.5</math>
:<math>u_{11} = 4</math>
:<math>u_{12} = 3</math>
:<math>u_{22} = -1.5.</math>
Visszahelyettesítve a kapott értékeket a fenti LU felbontásba:
:<math>
\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}.
</math>
== 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á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 ==
=== Lineáris egyenletrendszer megoldása ===
Legyen adott a következő egyenlet
:<math>A x = L U x = b \,</math>
keressük az egyenlet megoldásait adott ''A'' és ''b''esetén. A megoldást két logikai lépéssel végezzük:
# Először oldjuk meg az <math> Ly = b </math> for ''y'' egyenletet
# Aztán oldjuk meg az <math> Ux = y </math> for ''x'' egyenletet.
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 ===
Az ''L'' és ''U'' mátrixok segítségével [[Mátrix inverzió |matrixok inverze]] kiszámítható:
:<math>
A^{-1} = U^{-1}L^{-1}. \,
</math>
Mártixokat 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
:<math> \det(A) = \det(L) \det(U) = \prod_{i=1}^n u_{ii}. </math>
==Lásd még==
*[[Cholesky felbontás]]
*[[Invertálható mátrix]]
==Források==
{{reflist}}
* {{Citation | last1=Bau III | first1=David | last2=Trefethen | first2=Lloyd N. | author2-link=Lloyd Nicholas Trefethen | title=Numerical linear algebra | publisher=Society for Industrial and Applied Mathematics | location=Philadelphia | isbn=978-0-89871-361-9 | year=1997}}
* {{Citation | last1=Cormen | first1=Thomas H. | author1-link=Thomas H. Cormen | last2=Leiserson | first2=Charles E. | author2-link=Charles E. Leiserson | last3=Rivest | first3=Ronald L. | author3-link=Ronald L. Rivest | last4=Stein | first4=Clifford | author4-link=Clifford Stein | title=[[Introduction to Algorithms]] | publisher=MIT Press and McGraw-Hill | isbn=978-0-262-03293-3 | year=2001 }}
* {{citation | first1=Gene H. | last1=Golub | author1-link=Gene H. Golub | first2=Charles F. | last2=Van Loan | author2-link=Charles F. Van Loan | year=1996 | title=Matrix Computations | edition=3rd | publisher=Johns Hopkins | place=Baltimore | isbn=978-0-8018-5414-9}}.
* {{citation | first1=Roger A. | last1=Horn | first2=Charles R. | last2=Johnson | year=1985 | title=Matrix Analysis | publisher=Cambridge University Press | isbn=0-521-38632-2 }}. See Section 3.5.
* {{citation | first1=Alston | last1=Householder | year=1975| title=The Theory of Matrices in Numerical Analysis }}.
* {{citation | first1=Pavel | last1=Okunev | first2=Charles | last2=Johnson | year=1997| title=Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix | id={{arxiv|archive=math.NA|id=0506382}} }}.
* {{Citation | last1=Press | first1=William H. | last2=Flannery | first2=Brian P. | last3=Teukolsky | first3=Saul A. | author3-link=Saul Teukolsky | last4=Vetterling | first4=William T. | title=Numerical Recipes in FORTRAN: The Art of Scientific Computing | url=http://www.mpi-hd.mpg.de/astrophysik/HEA/internal/Numerical_Recipes/f2-3.pdf | publisher=[[Cambridge University Press]] | edition=2nd | year=1992 | chapter=LU Decomposition and Its Applications | pages=34–42}}
==Kapcsolódó linkek==
* [http://mathworld.wolfram.com/LUDecomposition.html LU decomposition] on ''MathWorld''.
* [http://www.math-linux.com/spip.php?article51 LU decomposition] on ''Math-Linux''.
*[http://eigen.tuxfamily.org Eigen] is a C++ template library for linear algebra: vectors, matrices, and related algorithms.
*[http://www.netlib.org/lapack/ LAPACK] is a collection of FORTRAN subroutines for solving dense linear algebra problems
*[http://www.alglib.net/ ALGLIB] includes a partial port of the LAPACK to C++, C#, Delphi, etc.
*[http://www.bluebit.gr/matrix-calculator/ Online Matrix Calculator] performs LU decomposition
*[http://numericalmethods.eng.usf.edu/topics/lu_decomposition.html LU decomposition] at ''Holistic Numerical Methods Institute''
*[http://math.fullerton.edu/mathews/n2003/LUFactorMod.html Module for LU Factorization with Pivoting]
*[http://demonstrations.wolfram.com/LUDecomposition/ LU Decomposition] by [[Ed Pegg, Jr.]], [[The Wolfram Demonstrations Project]], 2007.
[[de:Gaußsches Eliminationsverfahren#LR-Zerlegung]]
[[es:Factorización LU]]
[[eo:LU malkomponaĵo]]
[[fr:Décomposition LU]]
[[is:LU-þáttun]]
[[it:Decomposizione LU]]
[[nl:LU-decompositie]]
[[ja:LU分解]]
[[pl:Metoda LU]]
[[pt:Decomposição LU]]
[[ru:LU-разложение]]
[[fi:LU-hajotelma]]
[[sv:LU-faktorisering]]
[[uk:LU розклад матриці]]
[[zh:LU分解]]
{{Portál|matematika}}
| |||