V lineární algebře je rozklad LU metodou rozkladu matice jako produktu dolní trojúhelníkové matice L (jako nižší , nižší v angličtině ) horní trojúhelníkovou maticí U (jako horní , vyšší). Tento rozklad se používá v numerické analýze k řešení systémů lineárních rovnic .
Nechť A je čtvercová matice . Říkáme, že A připouští rozklad LU, pokud existuje dolní trojúhelníková matice tvořená 1 na diagonále, označená L , a horní trojúhelníková matice, označená U , která ověřuje rovnost
Není vždy pravda, že matice A připouští rozklad LU. V některých případech je však permutací linií A možný rozklad. Poté získáme rozklad formy
kde P je permutační matice .
Ačkoli rozklady LU a PLU vedou k samostatným vzorcům, obecně když mluvíme o rozkladu LU, máme na mysli jeden nebo druhý z těchto rozkladů.
Symetrická matice
se započítává takto:
.Tato maticová faktorizace umožňuje řešit systémy lineárních rovnic, kde koeficienty neznámých jsou stejné, ale s několika různými druhými členy. To znamená určit vektor x neznámých asociovaných s druhým členem b :
.Tento problém je tedy ekvivalentní rozlišení
které můžeme dát pózováním ve formě:
.Složky najdeme elementárními substitucemi, protože nejdříve , potom atd.
Tento krok se nazývá sestup , protože systém je řešen sestupem z do . Zbývá vypočítat složky vektoru x řešením horního trojúhelníkového systému:
,což se provádí podobným způsobem, ale nejprve výpočtem x n :
, atd. stoupání (tzv. výstupová fáze ).Poznámka. - Trojúhelníkové matice L a U mohly být snadno invertovány použitím eliminace Gauss-Jordan . Pokud ale jednoduše spočítáme počet operací, které to představuje pro systém s n rovnicemi, zjistíme, že algoritmická složitost výpočtu inverzních matic je větší, takže pokud chceme tento systém vyřešit pro různé b , je zajímavější provést rozklad LU jednou provždy a provést substituce sestupu a výstupu pro různé bs, spíše než několikrát použít Gauss-Jordanovu eliminaci. Tedy, ve většině publikací numerické analýzy , kdy matice byl faktorizovaná ve formě LU nebo Choleského ( viz níže , § Symetrický případ ), jeden zápisy od zneužívání x = A -1 b znamenat, že při výpočtu x lze provést touto metodou sestup-výstup. Rozumí se, že neexistuje absolutně žádná otázka použití algoritmu výpočtem inverzní matice A −1 z A , což by bylo v době výpočtu zbytečně nákladné.
Matice L a U lze použít k určení inverze matice. Počítačové programy, které implementují tento typ výpočtu, obecně používají tuto metodu.
Pokud je ve tvaru LU a PLU , její determinant je snadno vypočítat: . Tři determinanty tohoto produktu se vypočítávají velmi snadno (trojúhelníkové nebo permutační matice).
Pro jakoukoli čtvercovou matici existuje rozklad PLU . U invertibilní matice existuje rozklad LU právě tehdy, pokud jsou všechny hlavní dílčí matice řádu 1 až n -1 invertovatelné. [Pro čtvercovou matici hodnosti r <n existují obdobné dostatečné podmínky.] Pokud jsou všechny hlavní dílčí matice řádů 1 až n invertovatelné, je to dokonce jedinečné.
Rozpad LU je zvláštní formou eliminace Gauss-Jordan. Transformujeme matici A na horní trojúhelníkovou matici U odstraněním prvků pod úhlopříčkou. Eliminace se provádí sloupec za sloupcem, počínaje zleva, vynásobením A doleva spodní trojúhelníkovou maticí.
Vzhledem k matici dimenze
definujeme
a budeme matice sestavovat iterativně, s cílem, aby matice měla prvních n sloupců nulových koeficientů pod úhlopříčkou.
Buď matici , postavíme matici následovně: s ohledem na n- tý sloupec , eliminujeme prvky pod úhlopříčkou přidáním do i- té řady této matice, n- tý řádek vynásobený
pro . Toho lze dosáhnout vynásobením levého A ( n -1) dolní trojúhelníkovou maticí
Po N - 1 iteracích jsme odstranili všechny prvky pod úhlopříčkou, proto nyní máme horní trojúhelníkovou matici A ( N –1) .
Dostaneme rozklad
Označme U , horní trojúhelníkovou matici A ( N -1) . a . S vědomím, že inverzní funkce dolní trojúhelníkové matice je také nižší trojúhelníková matice a že produktem dvou dolních trojúhelníkových matic je stále nižší trojúhelníková matice, je L tedy nižší trojúhelníková matice. Dostaneme A = LU a
Z pohledu algoritmu je nutné, aby při každé iteraci (viz definice l { i , n } ). Pokud by během výpočtu došlo k tomuto scénáři, musíme pro pokračování převrátit n- tý řádek jiným řádkem (vždy je možné najít nenulový prvek sloupce, který je problémem, protože matice je invertovatelná). To je důvod, proč se rozklad LU obecně píše jako P −1 A = LU .