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 $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 $L$ a $U$, jsou určeny jednoznačně a platí pro ně následující tvrzení

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

Tomuto součinu říkáme LU rozklad matice $A$.

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

Využití

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

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

To je užitečně, pokud máme sérii výpočtů, ve které se pravá strana $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.

Příklad

$𝐀=\left(\begin{array}{ccc}1& 3& -2\\ 4& 2& 8\\ -3& 1& 0\end{array}\right)=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& 3& -2\\ 4& 2& 8\\ -3& 1& 0\end{array}\right)=$

$=\left(\begin{array}{ccc}1& 0& 0\\ 4& 1& 0\\ -3& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& 3& -2\\ 0& -10& 16\\ 0& 10& -6\end{array}\right)=$

$=\left(\begin{array}{ccc}1& 0& 0\\ 4& 1& 0\\ -3& -1& 1\end{array}\right)\left(\begin{array}{ccc}1& 3& -2\\ 0& -10& 16\\ 0& 0& 10\end{array}\right)=𝐋𝐔$.

Odkazy

Související články

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

Externí odkazy

• Šablona:Commonscat