LU rozklad

LU rozklad matice je způsob, jak zapsat tuto matici jako součin dvou dalších matic, z nichž jedna (L z anglického lower) je v dolním trojúhelníkovém tvaru a má na celé hlavní diagonále číslo jedna a druhá (U z anglického upper) je v horním trojúhelníkovém tvaru a na hlavní diagonále má pouze nenulové prvky.

Definice

Mějme ${\displaystyle A}$ regulární čtvercovou matici nad libovolným tělesem, u které není třeba při Gaussově eliminaci prohazovat řádky. Pak existují také regulární matice ${\displaystyle L}$ a ${\displaystyle U}$, jsou určeny jednoznačně a platí pro ně následující tvrzení

• ${\displaystyle A=LU}$
• ${\displaystyle L}$ je dolní trojúhelníková matice s jedničkami na celé hlavní diagonále.
• ${\displaystyle U}$ je horní trojúhelníková matice s nenulovými prvky na hlavní diagonále.

Tomuto součinu říkáme LU rozklad matice ${\displaystyle A}$. ^[1]

Pokud nemáme matici ${\displaystyle A}$ takovou, u které není třeba prohazovat řádky, pak lze využít rozklad ${\displaystyle PA=LU}$, kde ${\displaystyle P}$ je permutační matice (taková, která vznikla z jednotkové postupnou záměnou sloupců). Taková matice nejdříve prohází řádky matice ${\displaystyle A}$ a zbytek rozkladu zůstane stejný. ^[2]

Využití

Během výpočtu soustavy ${\displaystyle Ax=b}$ může nastat situace, kdy se podařila najít dolní trojúhelníková matice ${\displaystyle L}$ i horní trojúhelníková matice ${\displaystyle U}$ tak, že ${\displaystyle A=LU}$.

Potom lze nahradit v této soustavě ${\displaystyle LU}$ za ${\displaystyle A}$ a označit ${\displaystyle Ux=y}$. Z toho plyne, že ${\displaystyle LUx=b\Leftrightarrow Ly=b}$ a ${\displaystyle Ux=y}$.

To je užitečně, pokud máme sérii výpočtů, ve které se pravá strana ${\displaystyle b}$ v jednotlivých případech mění, ale levá strana zůstává stejná. Toto řešení pomocí LU rozkladu je časově výhodnější než opakované počítání stejné soustavy.^[3]

Příklad

${\displaystyle \mathbf {A} ={\begin{pmatrix}{1}&{3}&{-2}\\{4}&{2}&{8}\\{-3}&{1}&{0}\\\end{pmatrix}}={\begin{pmatrix}{1}&{0}&{0}\\{0}&{1}&{0}\\{0}&{0}&{1}\\\end{pmatrix}}{\begin{pmatrix}{1}&{3}&{-2}\\{4}&{2}&{8}\\{-3}&{1}&{0}\\\end{pmatrix}}=}$

${\displaystyle ={\begin{pmatrix}{1}&{0}&{0}\\{4}&{1}&{0}\\{-3}&{0}&{1}\\\end{pmatrix}}{\begin{pmatrix}{1}&{3}&{-2}\\{0}&{-10}&{16}\\{0}&{10}&{-6}\\\end{pmatrix}}=}$

${\displaystyle ={\begin{pmatrix}{1}&{0}&{0}\\{4}&{1}&{0}\\{-3}&{-1}&{1}\\\end{pmatrix}}{\begin{pmatrix}{1}&{3}&{-2}\\{0}&{-10}&{16}\\{0}&{0}&{10}\\\end{pmatrix}}=\mathbf {LU} }$.^[4]

Odkazy

Reference

1. http://msekce.karlin.mff.cuni.cz/~sir/la/LinAlg/skripta.pdf
2. Archivovaná kopie. homel.vsb.cz [online]. [cit. 2016-03-13]. Dostupné v archivu pořízeném z originálu dne 2016-03-14. 
3. http://petr.olsak.net/bilin/lurozklad.pdf
4. http://ivankuckir.blogspot.cz/2010/09/lu-rozklad.html

Související články

• Matice
• Soustava lineárních rovnic
• QR rozklad
• Jordanův rozklad
• Regulární matice
• Lineární algebra
• Permutace

Externí odkazy

• Obrázky, zvuky či videa k tématu LU rozklad na Wikimedia Commons

Portály: Matematika