„LU felbontás” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
→Definíciók: a parciális pivotálást magyarítottam részleges főelemkiválasztásra |
Nincs szerkesztési összefoglaló |
||
1. sor:
Az '''LU felbontás''' (ejtsd: el-ú-felbontás) egy olyan [[mátrixfelbontás]], amely egy [[mátrix (matematika)|mátrix]]
Az elnevezés a '''l'''ow(er) („alsó”) és '''u'''p(per) (felső) angol határozószók kezdőbetűiből ered.
8. sor:
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 <math>3 \times 3</math> -as mátrixra így néz ki:
:<math>
\begin{bmatrix}
a_{11} & a_{12} & a_{13} \\
41. sor:
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.
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.
48. sor:
== 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''
:<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.
72. sor:
:<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
:<math>l_{21} = 1.5</math>
:<math>u_{11} = 4</math>
78. sor:
:<math>u_{22} = -1.5.</math>
Visszahelyettesítve a kapott értékeket a fenti LU felbontásba:
:<math>
\begin{bmatrix}
4 & 3 \\
95. sor:
== 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
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.
111. sor:
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
Az ''L'' és ''U'' mátrixok segítségével [[Mátrix inverzió|
:<math>
A^{-1} = U^{-1}L^{-1}. \,
</math>
=== 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>
132. sor:
== Források ==
* {{Cite book | 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}}
* {{Cite book | 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
* {{cite book | 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}}.
* {{cite book | first1=Roger A. | last1=Horn | first2=Charles R. | last2=Johnson | year=1985 | title=Matrix Analysis | publisher=Cambridge University Press | isbn=0-521-38632-2
* {{cite book | first1=Alston | last1=Householder | year=1975| title=The Theory of Matrices in Numerical Analysis
* {{cite book | 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}}
* {{Cite book | 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}}
| |||