LU rozklad matice je rozklad dané čtvercové matice na dvě trojúhelníkové matice, jednu horní trojúhelníkovou matici a jednu dolní trojúhelníkovou matici tak, že součin těchto dvou matic dává původní matici. Byl představen Alanem Turingem v roce 1948, který také vytvořil Turingův stroj.

Metoda rozkladu LU faktorizace matice jako součinu dvou trojúhelníkových matic má různé aplikace, jako je řešení soustavy rovnic, která sama o sobě je nedílnou součástí mnoha aplikací, jako je hledání proudu v obvodu a řešení problémů diskrétních dynamických systémů ; nalezení inverze matice a nalezení determinantu matice.

Co je rozklad L U?

Čtvercovou matici A lze rozložit na dvě čtvercové matice L a U tak, že A = L U, kde U je horní trojúhelníková matice vytvořená jako výsledek aplikace Gaussovy eliminační metody na A a L je spodní trojúhelníková matice s diagonálními prvky. rovný 1.

Pro A =egin{bmatrix} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{bmatrix} .

programování struct pole c

Máme L = egin{bmatrix} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 1 end{bmatrix} a U =egin{bmatrix} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{bmatrix} ;

Tak, že A = L U, tj.left[egin{array}{lll} a_{11} & a_{12} & a_{13} a_{21} & a_{22} & a_{23} a_{31} & a_{32} & a_{33} end{array} ight]=left[egin{array}{lll} 1 & 0 & 0 l_{21} & 1 & 0 l_{31} & l_{32} & 0 end{array} ight] cdot left[egin{array}{ccc} u_{11} & u_{12} & u_{13} 0 & u_{22} & u_{23} 0 & 0 & u_{33} end{array} ight]

Zde je hodnota l_{dvacet jedna}, v_jedenáct, atd. lze porovnat a najít.

Co je Gaussova eliminační metoda?

Gaussova eliminace, také známá jako Gauss-Jordan Elimination, je metoda používaná v lineární algebře k řešení soustav lineárních rovnic a k nalezení inverzní matice. Je pojmenován po matematikovi Carlu Friedrichu Gaussovi a také matematikovi Wilhelmu Jordanovi, kteří se významně zasloužili o jeho rozvoj.

Podle Gaussovy eliminační metody:

1. Jakýkoli nulový řádek by měl být ve spodní části matice.
2. První nenulový záznam každého řádku by měl být na pravé straně prvního nenulového záznamu předchozího řádku. Tato metoda redukuje matici do tvaru řádků.

Metoda rozkladu LU

Chcete-li libovolnou čtvercovou matici rozdělit na dvě trojúhelníkové matice, tj. jedna je spodní trojúhelníková matice a druhá je horní trojúhelníková matice, můžeme použít následující kroky.

• Danou sadu lineárních rovnic je nejprve převeďte do maticového tvaru A X = C, kde A je matice koeficientů, X je proměnná matice a C je matice čísel na pravé straně rovnic.
• Nyní redukujeme matici koeficientů A, tedy matici získanou z koeficientů proměnných ve všech daných rovnicích tak, že pro ‚n‘ proměnných máme matici nXn, na řádkový tvar pomocí Gaussovy eliminační metody. Takto získaná matrice je U.
• K nalezení L máme dvě metody. Prvním z nich je převzít zbývající prvky jako nějaké umělé proměnné, vytvořit rovnice pomocí A = L U a vyřešit je, abyste tyto umělé proměnné našli. Druhá metoda spočívá v tom, že zbývající prvky jsou multiplikační koeficienty, díky kterým se příslušné pozice v U matici staly nulovými. (Tato metoda je trochu složitější na pochopení slovy, ale v níže uvedeném příkladu by to bylo jasné)
• Nyní máme A (matice koeficientů nXn), L (matice dolního trojúhelníku nXn), U (matice horního trojúhelníku nXn), X (matice proměnných nX1) a C (matice čísel nX1 vpravo- ruční strana rovnic).
• Daná soustava rovnic je A X = C. Dosadíme A = L U. Máme tedy L U X = C. Položíme Z = U X, kde Z je matice nebo umělé proměnné a nejprve vyřešíme pro L Z = C a poté vyřešíme pro U X = Z najít X nebo hodnoty proměnných, což bylo požadováno.

Příklad rozkladu LU

Vyřešte následující soustavu rovnic pomocí metody LU Decomposition:

egin{equation*} x_1 + x_2 + x_3 = 1 end{equation*} egin{equation*} 4x_1 + 3x_2 – x_3 = 6 end{equation*} egin{equation*} 3x_1 + 5x_2 + 3x_3 = 4 end{equation*}

Řešení: Zde máme A =

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} , X = egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

a

C = egin{bmatrix} 1 6 4 end{bmatrix}

tak, že A X = C. Nyní nejprve uvažujme

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix}

a převeďte jej do tvaru řady pomocí Gaussovy eliminační metody. Takže tím, že dělám

egin{equation} R_2 o R_2 – 4R_1 end{equation} egin{equation} R_3 o R_3 – 3R_1 end{equation}

dostaneme

egin{bmatrix} 1 & 1 & 1 4 & 3 & -1 3 & 5 & 3 end{bmatrix} sim

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 2 & 0 end{bmatrix}

Teď tím, že děláš

egin{equation} R_3 o R_3 – (-2)R_2 end{equation}

Dostaneme

sim egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(Nezapomeňte mezi tím vždy ponechat znak „–“, znak „+“ nahradit dvěma znaky „–“) Dostaneme tedy L =

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix}

a U =

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix}

(všimněte si, že v matici L,

l_{21} = 4

je z (1),

l_{31} = 3

je z (2) a

l_{32} = -2

je z (3)) Nyní předpokládáme Z

= egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

a vyřešit L Z = C.

egin{bmatrix} 1 & 0 & 0 4 & 1 & 0 3 & -2 & 1 end{bmatrix} egin{bmatrix} z_1 z_2 z_3 end{bmatrix}

= egin{bmatrix} 1 6 4 end{bmatrix}

Takže máme

z_1 = 1 ,

4z_1 + z_2 = 6 ,

3z_1 – 2z_2 + z_3 = 4 .

k algoritmu nejbližšího souseda

Řešení, dostáváme

z_1 = 1

,

z_2 = 2

a

z_3 = 5

. Nyní řešíme U X = Z

egin{bmatrix} 1 & 1 & 1 0 & -1 & -5 0 & 0 & -10 end{bmatrix} egin{bmatrix} x_1 x_2 x_3 end{bmatrix}

= egin{bmatrix} 1 2 5 end{bmatrix}

Proto dostáváme

x_1 + x_2 + x_3 = 1 ,

-x_2 – 5x_3 = 2

,

-10x_3 = 5 .

Řešením dané soustavy lineárních rovnic je tedy

x_1 = 1

,

java n-tice

x_2 = 0.5

,

x_3 = -0.5

a odtud matice X =

egin{bmatrix} 1 0.5 -0.5 end{bmatrix}

Cvičení o rozkladu LU

V LU rozkladu matice

| 2 2 |
| 4 9 |

, pokud jsou diagonální prvky U oba 1, pak spodní diagonální vstup l22 z L je (GATE CS 2015) (A) 4 (B) 5 (C) 6 (D) 7

Řešení viz BRÁNA | GATE-CS-2015 (Sada 1) | Otázka 65 .

Nejčastější dotazy týkající se rozkladu LU

Co je metoda rozkladu LU?

LU rozklad, zkratka pro Lower-Upper decomposition, je maticová faktorizační technika používaná k rozdělení čtvercové matice na součin spodní trojúhelníkové matice (L) a horní trojúhelníkové matice (U). Běžně se používá ke zjednodušení řešení systémů lineárních rovnic a výpočtu determinantů.

Proč je rozklad LU jedinečný?

Rozklad LU je jedinečný, protože poskytuje způsob, jak jedinečně faktorizovat čtvercovou matici A na nižší a horní trojúhelníkové matice (L a U), což umožňuje efektivní řešení lineárních systémů a výpočet determinantů.

Jak se počítá rozklad LU?

Rozklad LU se vypočítává pomocí Gaussovy eliminace, kde transformujete čtvercovou matici A na dolní (L) a horní (U) trojúhelníkovou matici prováděním řádkových operací, přičemž sledujete změny v samostatných maticích. Tento proces je iterativní a pokračuje, dokud se A plně nerozloží. Metoda se všemi kroky pro rozklad LU je uvedena v článku.

Když rozklad LU není možný?

Rozklad LU nemusí být možný, když je matice A singulární (neinvertibilní) nebo když vyžaduje otáčení pro stabilitu, ale prvek pivotu se stane nulou, což způsobí dělení nulou během procesu rozkladu.

Existují nějaké alternativy k rozkladu LU?

Ano, alternativy k rozkladu LU zahrnují Choleský rozklad pro symetrické pozitivně definitní matice, QR rozklad pro obecné matice a metody založené na vlastních hodnotách, jako je spektrální rozklad a rozklad singulární hodnoty (SVD) pro různé maticové operace a aplikace.

Lze LU rozklad aplikovat na nečtvercové matice?

Rozklad LU se typicky aplikuje na čtvercové matice. U pravoúhlých matic se častěji používá QR rozklad. Variace jako rozklad LUP však zvládnou i pravoúhlé matice, kde P je permutační matice.