LU rozklad - LU decomposition

v numerická analýza a lineární algebra, dolní Horní (LU) rozklad nebo faktorizace faktory a matice jako produkt nižší trojúhelníková matice a horní trojúhelníková matice. Produkt někdy zahrnuje a permutační matice také. Na rozklad LU lze pohlížet jako na maticovou formu Gaussova eliminace. Počítače obvykle řeší čtverec soustavy lineárních rovnic pomocí LU rozkladu a je to také klíčový krok při převrácení matice nebo výpočtu určující matice. Rozklad LU představil polský matematik Tadeusz Banachiewicz v roce 1938.^[1]

Definice

LDU rozklad a Walshova matice

Nechat A být čtvercová matice. An Faktorizace LU odkazuje na faktorizaci A, se správným uspořádáním řádků a / nebo sloupců nebo permutacemi, do dvou faktorů - dolní trojúhelníkové matice L a horní trojúhelníková matice U:

${displaystyle A = LU.}$

V dolní trojúhelníkové matici jsou všechny prvky nad úhlopříčkou nulové, v horní trojúhelníkové matici jsou všechny prvky pod úhlopříčkou nulové. Například pro matici 3 × 3 A, jeho rozklad LU vypadá takto:

${displaystyle {egin {bmatrix} a_ {11} & a_ {12} & a_ {13} a_ {21} & a_ {22} & a_ {23} a_ {31} & a_ {32} & a_ {33} end {bmatrix}} = {egin {bmatrix} l_ {11} & 0 & 0 l_ {21} & l_ {22} & 0 l_ {31} & l_ {32} & l_ {33} end {bmatrix}} {egin {bmatrix} u_ {11} & u_ { 12} & u_ {13} 0 & u_ {22} & u_ {23} 0 & 0 & u_ {33} end {bmatrix}}.}$

Bez řádného uspořádání nebo permutací v matici se nemusí faktorizace zhmotnit. Například je snadné to ověřit (rozšířením násobení matic) ${extstyle a_ {11} = l_ {11} u_ {11}}$. Li ${extstyle a_ {11} = 0}$, pak alespoň jeden z ${extstyle l_ {11}}$ a ${extstyle u_ {11}}$ musí být nula, z čehož vyplývá, že buď L nebo U je jednotné číslo. To je nemožné, pokud A je nonsingular (invertible). Toto je procesní problém. Lze jej odstranit jednoduchým přeuspořádáním řádků A takže první prvek permutované matice je nenulový. Stejný problém v dalších faktorizačních krocích lze odstranit stejným způsobem; viz základní postup níže.

Faktorizace LU s částečným otočením

Ukazuje se, že správná permutace v řádcích (nebo sloupcích) je dostatečná pro faktorizaci LU. Faktorizace LU s částečným otočením (LUP) často odkazuje na faktorizaci LU pouze s permutacemi řádků:

${displaystyle PA = LU,}$

kde L a U jsou opět spodní a horní trojúhelníkové matice a P je permutační matice, který, když se nechá vynásobit A, změní pořadí řádků A. Ukazuje se, že všechny čtvercové matice lze v této podobě rozložit,^[2] a faktorizace je v praxi numericky stabilní.^[3] Díky tomu je rozklad LUP v praxi užitečnou technikou.

Faktorizace LU s plným otočením

An Faktorizace LU s plným otočením zahrnuje permutace řádků i sloupců:

${displaystyle PAQ = LU,}$

kde L, U a P jsou definovány jako dříve a Q je permutační matice, která mění pořadí sloupců A.^[4]

LDU rozklad

An LDU rozklad je rozklad formy

${displaystyle A = LDU,}$

kde D je diagonální matice, a L a U jsou unitriangular matice, což znamená, že všechny položky na úhlopříčkách L a U jsou jedno.

Nahoře jsme to požadovali A být čtvercová matice, ale tyto rozklady lze všechny zobecnit i na obdélníkové matice. V tom případě, L a D jsou čtvercové matice, které mají stejný počet řádků jako A, a U má přesně stejné rozměry jako A. Horní trojúhelníkový by mělo být interpretováno jako mající pouze nulové položky pod hlavní úhlopříčkou, která začíná v levém horním rohu.

Příklad

Faktorizujeme následující matici 2 na 2:

${displaystyle {egin {bmatrix} 4 & 3 6 & 3end {bmatrix}} = {egin {bmatrix} l_ {11} & 0 l_ {21} & l_ {22} end {bmatrix}} {egin {bmatrix} u_ {11} & u_ { 12} 0 & u_ {22} end {bmatrix}}.}$

Jedním ze způsobů, jak zjistit rozklad LU této jednoduché matice, je jednoduše vyřešit lineární rovnice kontrolou. Rozšíření násobení matice dává

${displaystyle {egin {aligned} l_ {11} cdot u_ {11} + 0cdot 0 & = 4 l_ {11} cdot u_ {12} + 0cdot u_ {22} & = 3 l_ {21} cdot u_ {11} + l_ {22} cdot 0 & = 6 l_ {21} cdot u_ {12} + l_ {22} cdot u_ {22} & = 3.end {zarovnáno}}}$

Tento systém rovnic je podurčeno. V tomto případě libovolné dva nenulové prvky L a U matice jsou parametry řešení a lze je libovolně nastavit na jakoukoli nenulovou hodnotu. Proto, aby bylo možné najít jedinečný rozklad LU, je nutné uvést určité omezení L a U matice. Například můžeme pohodlně vyžadovat spodní trojúhelníkovou matici L být jednotkovou trojúhelníkovou maticí (tj. nastavit všechny položky její hlavní úhlopříčky na jedničky). Pak má soustava rovnic následující řešení:

${displaystyle {egin {aligned} l_ {11} & = l_ {22} = 1 l_ {21} & = 1,5 u_ {11} & = 4 u_ {12} & = 3 u_ {22} & = -1,5 konec {zarovnáno}}}$

Dosazením těchto hodnot do výše uvedeného rozkladu LU se získá výtěžek

${displaystyle {egin {bmatrix} 4 & 3 6 & 3end {bmatrix}} = {egin {bmatrix} 1 & 0 1.5 & 1end {bmatrix}} {egin {bmatrix} 4 & 3 0 & -1.5end {bmatrix}}.}$

Existence a jedinečnost

Čtvercové matice

Libovolná čtvercová matice ${extstyle A}$ připouští LUP a PLU faktorizace.^[2] Li ${extstyle A}$ je invertibilní, pak připouští LU (nebo LDU) faktorizace kdyby a jen kdyby všechny jeho hlavní jistiny nezletilí jsou nenulové.^[5] Li ${extstyle A}$ je singulární matice hodnosti ${extstyle k}$, pak připouští LU faktorizace, je-li první ${extstyle k}$ přední hlavní nezletilí jsou nenulová, i když obrácení není pravdivé.^[6]

Pokud má čtvercová invertibilní matice znak LDU (faktorizace se všemi úhlopříčnými položkami L a U rovna 1), pak je faktorizace jedinečná.^[5] V takovém případě LU faktorizace je také jedinečná, pokud požadujeme úhlopříčku ${extstyle L}$ (nebo ${extstyle U}$) se skládá z těch.

Symetrické pozitivní určité matice

Li A je symetrický (nebo Hermitian, pokud A je komplexní) pozitivní určitý matice, můžeme věci uspořádat tak, aby U je konjugovat transponovat z L. To znamená, že můžeme psát A tak jako

${displaystyle A = LL ^ {*}.,}$

Tento rozklad se nazývá Choleský rozklad. Choleský rozklad vždy existuje a je jedinečný - za předpokladu, že matice je kladně definitivní. Výpočet Choleského rozkladu je navíc efektivnější a numericky stabilnější než výpočet některých dalších LU rozkladů.

Obecné matice

Pro (ne nutně invertibilní) matici nad jakýmkoli polem jsou známy přesné nezbytné a dostatečné podmínky, za kterých má faktorizaci LU. Podmínky jsou vyjádřeny v řadách určitých podmatric. Gaussovský eliminační algoritmus pro získání rozkladu LU byl také rozšířen na tento nejobecnější případ.^[7]

Algoritmy

Uzavřený vzorec

Pokud existuje faktorizace LDU a je jedinečná, existuje uzavřený (explicitní) vzorec pro prvky L, D, a U z hlediska poměrů determinantů určitých podmatric původní matice A.^[8] Zejména, ${extstyle D_ {1} = A_ {1,1}}$, a pro ${extstyle i = 2, ldots, n}$, ${extstyle D_ {i}}$ je poměr ${extstyle i}$-tá hlavní podmatice do ${extstyle (i-1)}$-tá hlavní submatice. Výpočet determinantů je výpočetně nákladné, takže tento výslovný vzorec se v praxi nepoužívá.

Použití Gaussovy eliminace

Následující algoritmus je v podstatě upravenou formou Gaussova eliminace. Výpočet rozkladu LU pomocí tohoto algoritmu vyžaduje ${displaystyle {frac {2} {3}} n ^ {3}}$ operace s plovoucí desetinnou čárkou, ignorování podmínek nižšího řádu. Částečný otočný přidá pouze kvadratický výraz; toto není případ úplného otočení.^[9]

Vzhledem k N × N matice ${displaystyle A = (a_ {i, j}) _ {1leq i, jleq N}}$, definovat ${displaystyle A ^ {(0)}: = A}$.

Eliminujeme maticové prvky pod hlavní úhlopříčkou v n-tý sloupec A^(n − 1) přidáním do i-tý řádek této matice n-tý řádek vynásobený

${displaystyle -l_ {i, n}: = - {frac {a_ {i, n} ^ {(n-1)}} {a_ {n, n} ^ {(n-1)}}}, quad i = n + 1, ldots, N.}$

Toho lze dosáhnout vynásobením A^(n − 1) doleva s dolní trojúhelníkovou maticí

${displaystyle L_ {n} = {egin {pmatrix} 1 &&&&& & ddots &&&& && 1 &&& && - l_ {n + 1, n} &&& && vdots && ddots & && - l_ {N, n} &&& 1end {pmatrix}},}$

toto je N X N matice identity s jeho n-tý sloupec nahrazený vektorem ${displaystyle {egin {pmatrix} 0 & cdots & 0 & 1 & -l_ {n + 1, n} & cdots & -l_ {N, n} end {pmatrix}} ^ {T}.}$

Jsme si stanovili

${displaystyle A ^ {(n)}: = L_ {n} A ^ {(n-1)}.}$

Po N - 1 krok, odstranili jsme všechny prvky matice pod hlavní úhlopříčkou, takže jsme získali horní trojúhelníkovou matici A^(N − 1). Najdeme rozklad

${displaystyle A = L_ {1} ^ {- 1} L_ {1} A ^ {(0)} = L_ {1} ^ {- 1} A ^ {(1)} = L_ {1} ^ {- 1 } L_ {2} ^ {- 1} L_ {2} A ^ {(1)} = L_ {1} ^ {- 1} L_ {2} ^ {- 1} A ^ {(2)} = dotsb = L_ {1} ^ {- 1} ldots L_ {N-1} ^ {- 1} A ^ {(N-1)}.}$

Označme horní trojúhelníkovou matici A^(N − 1) podle U, a ${extstyle L = L_ {1} ^ {- 1} ldots L_ {N-1} ^ {- 1}}$. Protože inverze spodní trojúhelníkové matice L_n je opět nižší trojúhelníková matice a násobení dvou dolních trojúhelníkových matic je opět nižší trojúhelníková matice, z toho vyplývá, že L je dolní trojúhelníková matice. Navíc je to vidět

${displaystyle L = {egin {pmatrix} 1 &&&&&& l {2,1} & ddots &&&& & ddots & 1 &&& vdots & dots & l_ {n + 1, n} & 1 && && vdots & ddots & ddots & l_ {N, 1} & dots & l_ {N , n} & dots & l_ {N, N-1} & 1end {pmatrix}}.}$

Získáváme ${displaystyle A = LU.}$

Je zřejmé, že aby tento algoritmus fungoval, je třeba ho mít ${displaystyle a_ {n, n} ^ {(n-1)} eq 0}$ v každém kroku (viz definice ${displaystyle l_ {i, n}}$). Pokud tento předpoklad v určitém okamžiku selže, je třeba provést výměnu n-tý řádek s dalším řádkem pod ním, než budete pokračovat. Proto obecně vypadá rozklad LU ${displaystyle P ^ {- 1} A = LU}$.

Všimněte si, že rozklad získaný tímto postupem je a Rozklad doolittle: hlavní úhlopříčka L se skládá pouze z 1s. Pokud by se postupovalo odstraněním prvků výše hlavní úhlopříčka přidáním násobků sloupce (namísto odstranění prvků níže úhlopříčka přidáním násobků řádky), získali bychom a Crout rozklad, kde hlavní úhlopříčka U je z 1s.

Další (ekvivalentní) způsob výroby Croutova rozkladu dané matice A je získat Doolittleův rozklad transpozice A. Opravdu, pokud ${extstyle A ^ {T} = L_ {0} U_ {0}}$ je rozklad LU získaný pomocí algoritmu uvedeného v této části, poté pomocí ${extstyle L = U_ {0} ^ {T}}$ a ${extstyle U = L_ {0} ^ {T}}$, máme to ${displaystyle A = LU}$ je Croutův rozklad.

Rekurzí

Cormen a kol.^[10] popsat rekurzivní algoritmus pro rozklad LUP.

Vzhledem k tomu, matice A, nechť P₁ být permutační maticí takovou

${displaystyle P_ {1} A = left ({egin {array} {c | ccc} a && w ^ {T} & hline &&& v && A '& &&& end {array}} ight)}$,

kde ${extstyle aeq 0}$, pokud je v prvním sloupci nenulová položka A; nebo vzít P₁ jinak je to matice identity. Teď nech ${extstyle c = 1 / a}$, pokud ${extstyle aeq 0}$; nebo ${extstyle c = 0}$ v opačném případě. My máme

${displaystyle P_ {1} A = left ({egin {array} {c | ccc} 1 && 0 & hline &&& cv && I_ {n-1} & &&& end {array}} ight) left ({egin {array} {c | c} a & w ^ {T} hline & 0 & A'-cvw ^ {T} & end {array}} ight)}$.

Nyní můžeme rekurzivně najít rozklad LUP ${extstyle P '(A'-cvw ^ {T}) = L'U'}$. Nechat ${extstyle v '= P'v}$. Proto

${displaystyle left ({egin {array} {c | ccc} 1 && 0 & hline &&& 0 && P '& &&& end {array}} ight) P_ {1} A = left ({egin {array} {c | ccc} 1 && 0 & hline &&& cv '&& L' & &&& end {array}} ight) left ({egin {array} {c | ccc} a && w ^ {T} & hline &&& 0 && U '& &&& end {array}} ight)}$,

což je rozklad LUP A.

Randomizovaný algoritmus

Je možné najít aproximaci nízké úrovně na rozklad LU pomocí randomizovaného algoritmu. Vzhledem k vstupní matici ${extstyle A}$ a požadované nízké hodnocení ${extstyle k}$, randomizovaná LU vrací permutační matice ${extstyle P, Q}$ a spodní / horní lichoběžníkové matice ${extstyle L, U}$ velikosti ${extstyle mi im k}$ a ${extstyle k imes n}$ respektive takové, že s vysokou pravděpodobností ${extstyle Vert PAQ-LUVert _ {2} leq Csigma _ {k + 1}}$, kde ${extstyle C}$ je konstanta, která závisí na parametrech algoritmu a ${extstyle sigma _ {k + 1}}$ je ${extstyle (k + 1)}$th singulární hodnota vstupní matice ${extstyle A}$.^[11]

Teoretická složitost

Pokud dvě matice objednávky n lze časově znásobit M(n), kde M(n) ≥ n^A pro některé A > 2, pak lze vypočítat rozklad LU v čase O (M(n)).^[12] To například znamená, že O (n^2.376) Algoritmus existuje na základě Coppersmith – Winogradův algoritmus.

Rozložení řídké matice

Byly vyvinuty speciální algoritmy pro faktorizaci velkých řídké matice. Tyto algoritmy se pokoušejí najít řídké faktory L a U. V ideálním případě je cena výpočtu určena spíše počtem nenulových položek než velikostí matice.

Tyto algoritmy využívají svobodu výměny řádků a sloupců k minimalizaci vyplňování (položky, které se během provádění algoritmu mění z počáteční nula na nenulovou hodnotu).

Obecné zacházení s objednávkami, které minimalizují vyplnění, lze vyřešit pomocí teorie grafů.

Aplikace

Řešení lineárních rovnic

Vzhledem k systému lineárních rovnic v maticové formě

${displaystyle Ax = b,}$

chceme vyřešit rovnici pro X, vzhledem k tomu A a b. Předpokládejme, že jsme již získali rozklad LUP A takhle ${extstyle PA = LU}$, tak ${extstyle LUx = Pb}$.

V tomto případě se řešení provádí ve dvou logických krocích:

1. Nejprve vyřešíme rovnici ${extstyle Ly = Pb}$ pro y.
2. Zadruhé, řešíme rovnici ${extstyle Ux = y}$ pro X.

V obou případech máme co do činění s trojúhelníkovými maticemi (L a U), který lze vyřešit přímo pomocí střídání dopředu a dozadu bez použití Gaussova eliminace proces (pro výpočet souboru však tento proces nebo ekvivalent potřebujeme LU samotný rozklad).

Výše uvedený postup lze opakovaně použít k řešení rovnice několikrát pro různé b. V tomto případě je rychlejší (a pohodlnější) provést rozklad LU matice A jednou a poté vyřešte trojúhelníkové matice pro různé bspíše než pokaždé použít Gaussovu eliminaci. Matice L a U dalo by se říci, že „zakódovali“ Gaussův eliminační proces.

Cena řešení soustavy lineárních rovnic je přibližně ${extstyle {frac {2} {3}} n ^ {3}}$ operace s plovoucí desetinnou čárkou, pokud je matice ${extstyle A}$ má velikost ${extstyle n}$. Díky tomu je dvakrát rychlejší než založené na algoritmech QR rozklad, který stojí asi ${extstyle {frac {4} {3}} n ^ {3}}$ operace s plovoucí desetinnou čárkou, když Odrazy majitelů domů Jsou používány. Z tohoto důvodu je obvykle preferován rozklad LU.^[13]

Obrácení matice

Při řešení soustav rovnic b se obvykle považuje za vektor s délkou rovnou výšce matice A. V maticové inverzi však místo vektoru b, máme matici B, kde B je n-podle-str matice, takže se snažíme najít matici X (také a n-podle-str matice):

${displaystyle AX = LUX = B.}$

K řešení pro každý sloupec matice můžeme použít stejný algoritmus, který jsme uvedli dříve X. Nyní předpokládejme, že B je matice identity velikosti n. Z toho by vyplynulo, že výsledek X musí být inverzní k A.^[14]

Výpočet determinantu

Vzhledem k rozkladu LUP ${extstyle A = P ^ {- 1} LU}$ čtvercové matice A, determinant A lze vypočítat přímo jako

${displaystyle det (A) = det (P ^ {- 1}) det (L) det (U) = (- 1) ^ {S} vlevo (prod _ {i = 1} ^ {n} l_ {ii} ight) left (prod _ {i = 1} ^ {n} u_ {ii} ight).}$

Druhá rovnice vyplývá ze skutečnosti, že determinant trojúhelníkové matice je jednoduše součinem jejích diagonálních záznamů a že determinant permutační matice je roven (−1)^S kde S je počet výměn řádků v rozkladu.

V případě rozkladu LU s plným otočením, ${extstyle det (A)}$ také se rovná pravé straně výše uvedené rovnice, pokud to dovolíme S je celkový počet výměn řádků a sloupců.

Stejná metoda snadno platí pro rozklad LU nastavením P rovná matici identity.

Příklady kódu C.

/ * INPUT: A - pole ukazatelů na řádky čtvercové matice mající rozměr N * Tol - malé číslo tolerance pro detekci selhání, když je matice téměř zdegenerovaná * VÝSTUP: Matice A je změněna, obsahuje kopii obou matic L-E a U jako A = (L-E) + U tak, že P * A = L * U. * Permutační matice není uložena jako matice, ale v celočíselném vektoru P o velikosti N + 1  * obsahující indexy sloupců, kde má permutační matice „1“. Poslední prvek P [N] = S + N,  * kde S je počet výměn řádků potřebných pro výpočet determinantu, det (P) = (- 1) ^ S  */int LUPDecompose(dvojnásobek **A, int N, dvojnásobek Tol, int *P) {    int i, j, k, imax;     dvojnásobek max, *ptr, absA;    pro (i = 0; i <= N; i++)        P[i] = i; // Matice permutace jednotek, P [N] inicializovaná pomocí N    pro (i = 0; i < N; i++) {        max = 0.0;        imax = i;        pro (k = i; k < N; k++)            -li ((absA = báječné(A[k][i])) > max) {                 max = absA;                imax = k;            }        -li (max < Tol) vrátit se 0; // selhání, matice je zdegenerovaná        -li (imax != i) {            // otočný P            j = P[i];            P[i] = P[imax];            P[imax] = j;            // otočné řádky A            ptr = A[i];            A[i] = A[imax];            A[imax] = ptr;            // počítání čepů počínaje od N (pro determinant)            P[N]++;        }        pro (j = i + 1; j < N; j++) {            A[j][i] /= A[i][i];            pro (k = i + 1; k < N; k++)                A[j][k] -= A[j][i] * A[i][k];        }    }    vrátit se 1;  // rozklad hotový }/ * VSTUP: A, P vyplněno LUPDecompose; b - rhs vektor; N - rozměr * VÝSTUP: x - vektor řešení A * x = b */prázdnota LUPSolve(dvojnásobek **A, int *P, dvojnásobek *b, int N, dvojnásobek *X) {    pro (int i = 0; i < N; i++) {        X[i] = b[P[i]];        pro (int k = 0; k < i; k++)            X[i] -= A[i][k] * X[k];    }    pro (int i = N - 1; i >= 0; i--) {        pro (int k = i + 1; k < N; k++)            X[i] -= A[i][k] * X[k];        X[i] /= A[i][i];    }}/ * VSTUP: A, P vyplněno LUPDecompose; N - rozměr * VÝSTUP: IA je inverzní k počáteční matici */prázdnota LUPInvertovat(dvojnásobek **A, int *P, int N, dvojnásobek **IA) {      pro (int j = 0; j < N; j++) {        pro (int i = 0; i < N; i++) {            IA[i][j] = P[i] == j ? 1.0 : 0.0            pro (int k = 0; k < i; k++)                IA[i][j] -= A[i][k] * IA[k][j];        }        pro (int i = N - 1; i >= 0; i--) {            pro (int k = i + 1; k < N; k++)                IA[i][j] -= A[i][k] * IA[k][j];            IA[i][j] /= A[i][i];        }    }}/ * VSTUP: A, P vyplněno LUPDecompose; N - rozměr.  * OUTPUT: Funkce vrací determinant počáteční matice */dvojnásobek LUPDeterminant(dvojnásobek **A, int *P, int N) {    dvojnásobek det = A[0][0];    pro (int i = 1; i < N; i++)        det *= A[i][i];    vrátit se (P[N] - N) % 2 == 0 ? det : -det}

Příklady kódu C #

    veřejnost třída SystemOfLinearEquations    {        veřejnost dvojnásobek[] SolveUsingLU(dvojnásobek[,] matice, dvojnásobek[] pravý díl, int n)        {            // rozklad matice            dvojnásobek[,] lu = Nový dvojnásobek[n, n];            dvojnásobek součet = 0;            pro (int i = 0; i < n; i++)            {                pro (int j = i; j < n; j++)                {                    součet = 0;                    pro (int k = 0; k < i; k++)                        součet += lu[i, k] * lu[k, j];                    lu[i, j] = matice[i, j] - součet;                }                pro (int j = i + 1; j < n; j++)                {                    součet = 0;                    pro (int k = 0; k < i; k++)                        součet += lu[j, k] * lu[k, i];                    lu[j, i] = (1 / lu[i, i]) * (matice[j, i] - součet);                }            }                        // lu = L + U-I            // najít řešení Ly = b            dvojnásobek[] y = Nový dvojnásobek[n];            pro (int i = 0; i < n; i++)            {                součet = 0;                pro (int k = 0; k < i; k++)                    součet += lu[i, k] * y[k];                y[i] = pravý díl[i] - součet;            }            // najít řešení Ux = y            dvojnásobek[] X = Nový dvojnásobek[n];            pro (int i = n - 1; i >= 0; i--)            {                součet = 0;                pro (int k = i + 1; k < n; k++)                    součet += lu[i, k] * X[k];                X[i] = (1 / lu[i, i]) * (y[i] - součet);            }            vrátit se X;        }    }

Příklady kódu MATLAB

funkceX =SolveLinearSystem(A, b)n = délka(b);    X = nuly(n, 1);    y = nuly(n, 1);    % rozkladu matice, Doolittleova metoda    pro i = 1: 1: n        pro j = 1: 1: (i - 1)            alfa = A(i,j);            pro k = 1: 1: (j - 1)                alfa = alfa - A(i,k)*A(k,j);            konecA (i, j) = alfa / A (j, j);        konecpro j = i: 1: n            alfa = A(i,j);            pro k = 1: 1: (i - 1)                alfa = alfa - A(i,k)*A(k,j);            konecA (i, j) = alfa;        koneckonec    % A = L + U-I    % najít řešení Ly = b    pro i = 1: 1: n        alfa = 0;        pro k = 1: 1: i            alfa = alfa + A(i,k)*y(k);        konecy (i) = b (i) - alfa;    konec% najít řešení Ux = y    pro i = n: (- 1): 1        alfa = 0;        pro k = (i + 1): 1: n            alfa = alfa + A(i,k)*X(k);        konecx (i) = (y (i) - alfa) / A (i, i);    konec konec

Viz také

• Blokovat rozklad LU
• Bruhatův rozklad
• Choleský rozklad
• Neúplná faktorizace LU
• Redukce LU
• Maticový rozklad
• QR rozklad

Poznámky

Reference

• Bunch, James R .; Hopcroft, Johne (1974), „Trojúhelníková faktorizace a inverze rychlým množením matic“, Matematika výpočtu, 28 (125): 231–236, doi:10.2307/2005828, ISSN  0025-5718, JSTOR  2005828.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Úvod do algoritmů, MIT Press a McGraw-Hill, ISBN  978-0-262-03293-3.
• Golub, Gene H.; Van Loan, Charles F. (1996), Maticové výpočty (3. vyd.), Baltimore: Johns Hopkins, ISBN  978-0-8018-5414-9.
• Horn, Roger A .; Johnson, Charles R. (1985), Maticová analýza, Cambridge University Press, ISBN  978-0-521-38632-6. Viz část 3.5. N − 1
• Householder, Alston S. (1975), Teorie matic v numerické analýze, New York: Dover Publications, PAN  0378371.
• Okunev, Pavel; Johnson, Charles R. (1997), Nezbytné a dostatečné podmínky pro existenci LU faktorizace libovolné matice, arXiv:math.NA/0506382.
• Poole, David (2006), Lineární algebra: moderní úvod (2. vyd.), Kanada: Thomson Brooks / Cole, ISBN  978-0-534-99845-5.
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 2.3“, Numerické recepty: Umění vědecké práce na počítači (3. vyd.), New York: Cambridge University Press, ISBN  978-0-521-88068-8.
• Trefethen, Lloyd N.; Bau, David (1997), Numerická lineární algebra, Philadelphia: Společnost pro průmyslovou a aplikovanou matematiku, ISBN  978-0-89871-361-9.

externí odkazy

Reference

• LU rozklad na MathWorld.
• LU rozklad na Matematický Linux.
• LU rozklad na Holistický institut numerických metod
• Faktorizace matice LU. Reference MATLAB.

Počítačový kód

• LAPACK je sbírka podprogramů FORTRAN pro řešení problémů husté lineární algebry
• ALGLIB zahrnuje částečný port LAPACKu do C ++, C #, Delphi atd.
• C ++ kód Prof. J. Loomis, University of Dayton
• Kód C., Matematická zdrojová knihovna
• LU v X10
• [1] Lu v C ++ Anil Pedgaonkar
• Randomizovaný kód LU MATLAB

Online zdroje

• WebApp popisně řeší systémy lineárních rovnic s LU Decomposition
• Maticová kalkulačka, bluebit.gr
• LU Decomposition Tool, uni-bonn.de
• Rozpad LU podle Ed Pegg, Jr., Demonstrační projekt Wolfram, 2007.