LU-nedbrydning

I lineær algebra er LU-nedbrydning en metode til nedbrydning af en matrix som et produkt af en nedre trekantet matrix $L$ (som nedre , nedre på engelsk ) ved en øvre trekantmatrix $U$ (som øvre , højere). Denne nedbrydning bruges i numerisk analyse til at løse systemer med lineære ligninger .

Definition

Lad $A være$ en firkantet matrix . Vi siger, at $A$ indrømmer en nedbrydning LU, hvis der findes en nedre trekantet matrix dannet af 1 på den diagonale, bemærkede $L$ , og en øvre trekantet matrix, bemærket $U$ , som verificerer lighed

A = LU \;

Det er ikke altid rigtigt, at en matrix $A$ indrømmer en LU-nedbrydning. Imidlertid bliver nedbrydningen mulig i nogle tilfælde ved at permutere linier af $A.$ Vi opnår derefter en nedbrydning af formen

A = PLU \;

hvor $P$ er en permutationsmatrix .

Selvom LU- og PLU-nedbrydning fører til separate formler, refererer vi generelt til den ene eller den anden af disse nedbrydninger, når vi taler om LU-nedbrydningen.

Eksempel

Den symmetriske matrix

{\ displaystyle A = {\ begin {pmatrix} 2 & -1 & 0 \\ - 1 & 2 & -1 \\ 0 & -1 & 2 \\\ slut {pmatrix}}}

er beregnet som følger:

{\ displaystyle A = LU \ quad {\ text {with}} \ quad L = {\ begin {pmatrix} 1 & 0 & 0 \\ - 1/2 & 1 & 0 \\ 0 & -2 / 3 & 1 \\\ end {pmatrix}} \ quad {\ text {et}} \ quad U = {\ begin {pmatrix} 2 & -1 & 0 \\ 0 & 3/2 & -1 \\ 0 & 0 & 4 / 3 \\\ slutning {pmatrix}}}

Ansøgninger

Løs et system med lineære ligninger

Denne matrixfaktorisering gør det muligt at løse systemer med lineære ligninger, hvor de ukendte koefficienter er de samme, men med flere forskellige andet medlemmer. Det vil sige at bestemme vektoren $x$ af ukendte, der er knyttet til det andet medlem $b$ :

{\ displaystyle Axe = b}

Dette problem svarer derfor til opløsningen af

{\ displaystyle LUx = b}

som vi kan sætte, ved at stille , i formen: ${\ displaystyle Ux = y}$

{\ displaystyle Ly = b}

Vi finder komponenterne ved elementære erstatninger, siden først , derefter osv. $y$ ${\ displaystyle y_ {1} = b_ {1}}$ ${\ displaystyle y_ {2} = b_ {2} -L_ {21} y_ {1}}$

Dette trin kaldes nedstigning , da systemet løses ved at falde ned fra til . Det er stadig at beregne komponenterne i vektoren $x$ ved at løse det øvre trekantede system: $y_ {1}$ $y_n$

{\ displaystyle Ux = y}

hvilket gøres på en lignende måde, men ved først at beregne $x n$ :

x_n = \ frac {y_n} {U_ {nn}}

, etc. gå op (såkaldt opstigningsfase ).

Bemærk. - De trekantede matricer $L$ og $U$ kunne let have været inverteret ved hjælp af eliminering af Gauss-Jordan . Men hvis vi bare tæller antallet af operationer, som dette repræsenterer for et system med $n$ ligninger, finder vi, at den algoritmiske kompleksitet af beregningen af de inverse matricer er større, så hvis vi ønsker at løse dette system for forskellige $b$ , er det er mere interessant at udføre LU-nedbrydningen en gang for alle og at udføre nedstignings-opstigningserstatninger for de forskellige $bs$ snarere end at bruge Gauss-Jordan-eliminering flere gange. I de fleste publikationer med numerisk analyse , når matrixen $A$ er blevet faktoriseret i form af LU eller Cholesky ( jf. Infra , § Den symmetriske sag ), skriver man således ved misbrug $x = A -1 b for$ at betegne, at beregningen af $x$ kan udføres ved hjælp af denne nedstigningsmetode. Det forstås, at der absolut ikke er noget spørgsmål om at bruge algoritmen ved at beregne den inverse matrix $A -1$ af $A$ , hvilket ville være unødvendigt dyrt i beregningstiden.

Inverter en matrix

$L-$ og $U-$ matricerne kan bruges til at bestemme den inverse af en matrix. Computerprogrammer , der implementerer denne type beregning, bruger generelt denne metode.

Beregning af en determinant

Hvis $A$ er i form $LU$ og $PLU$ , er dens determinant let beregnes: . De tre determinanter for dette produkt er meget enkle at beregne (trekantede eller permutationsmatricer). $\ det (A) = \ det (P) \ det (L) \ det (U)$

Eksistens, unikhed

For enhver firkantet matrix er der en $PLU-$ nedbrydning . For en inverterbar matrix eksisterer LU-nedbrydningen, hvis og kun hvis alle hovedundermatricer i rækkefølge 1 til $n -1$ er inverterbare. [For en firkantet matrix af rang r <n er der analoge tilstrækkelige betingelser.] Hvis alle de vigtigste undermatricer i rækkefølge 1 til $n$ er inverterbare, er det endda unikt.

Beregning af nedbrydning

Hoved ide

LU-nedbrydning er en særlig form for Gauss-Jordan-eliminering. Vi omdanner matrix $A$ til en øvre trekantet matrix $U$ ved at eliminere elementerne under diagonalen. Elimineringer udføres kolonne efter kolonne startende fra venstre multiplicerer $A$ med venstre med en lavere trekantet matrix.

Algoritme

Givet en matrix af dimension $N \ gange N$

{\ displaystyle A = (a_ {i, j}) _ {1 \ leq i, j \ leq N}}

definerer vi

A ^ {(0)}: = A \;

og vi vil bygge matricerne iterativt med det mål, at matrixen har sine første n kolonner med nul koefficienter under diagonalen. ${\ displaystyle A ^ {(1)}, ..., A ^ {(n)}, ..., A ^ {(N-1)}}$ $A ^ {{(n)}}$

Enten matricen , vi konstruere matricen således: overvejer den n th kolonne , vi fjerne de elementer, der diagonal ved tilsætning til i te række af denne matrix, den n 'te række multipliceret med ${\ displaystyle A ^ {(n-1)}}$ $A ^ {{(n)}}$ ${\ displaystyle A ^ {(n-1)}}$

{\ displaystyle -l_ {i, n}: = - {\ frac {a_ {i, n} ^ {(n-1)}} {a_ {n, n} ^ {(n-1)}}}}

til . Dette kan gøres ved at gange med venstre $A$ $($ $n$ $-1)$ med den nederste trekantede matrix $i = n + 1, \ ldots, N$

{\ displaystyle L_ {n} = {\ begin {pmatrix} 1 &&&&& 0 \\ & \ ddots &&&& \\ && 1 &&& \\ && - l_ {n + 1, n} & \ ddots && \\ && \ vdots && \ ddots & \ \ 0 && - l_ {N, n} &&& 1 \\\ end {pmatrix}}.}

A ^ {(n)}: = L_n A ^ {(n-1)}. \;

Efter $N -1-$ iterationer har vi fjernet alle elementer under diagonalen, derfor har vi nu en øvre trekantet matrix $A ( N -1)$ .

Vi får nedbrydningen

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)} = \ ldots = L_ {1} ^ {- 1} \ ldots L_ {N-1} ^ {- 1} A ^ {(N-1)}.

Betegn med $U$ , den øverste trekantede matrix $A ( N -1)$ . og . Ved at vide, at det omvendte af en lavere trekantet matrix også er en lavere trekantet matrix, og at produktet af to nedre trekantede matricer stadig er en lavere trekantet matrix, er $L$ derfor en lavere trekantet matrix. Vi får $A = LU$ , og $L = L_ {1} ^ {- 1} \ ldots L_ {N-1} ^ {- 1}$

{\ displaystyle L = {\ begin {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} & 1 \ end {pmatrix }}.}

I betragtning af algoritmen er det nødvendigt, at ved hver iteration (se definitionen af $l$ ${$ $i$ $,$ $n$ $}$ ). Hvis der under beregningen, dette scenario skulle ske, må vi vende n th række med en anden for at fortsætte (det er altid muligt at finde en ikke-nul element i den kolonne, der er et problem, fordi matricen er invertibel). Dette er grunden til, at LU-nedbrydningen generelt skrives som $P$ $-1$ $A$ $=$ $LU$ . $a_ {n, n} ^ {(n-1)} \ neq0$

Den symmetriske sag

Hvis matrixen $A$ er en symmetrisk matrix , findes der en nedbrydning kendt som Crout-faktorisering $A = LDL ^ {\ mathrm T}$ hvor $L$ er en lavere trekantet matrix, hvis diagonale kun inkluderer 1'er, $L T$ er transponeringen af $L$ , og $D$ er en diagonal matrix.
Hvis matrixen A er symmetrisk positiv bestemt , findes der en enklere nedbrydning, givet ved metoden ifølge Cholesky $A = LL ^ {\ mathrm T}$ hvor $L$ er en trekantet matrix, der er lavere end positiv diagonal, og $L T er$ dens transponering .

Noter og referencer

Til demonstrationen, jf. Ciarlet, kap. 4, §4.3

PG Ciarlet, Introduktion til numerisk matrixanalyse og optimering , red. Masson, koll. “Matematik. Appl. til kandidatuddannelsen ”,1985( genoptryk 2001) ( ISBN 2-225-68893-1 )

Se også

eksterne links

Undergraduate digital analysis kursus (2010) af R. Herbin, University of Aix-Marseille
Vejledning Hvorfor fungerer LU-dekomponeringsalgoritmen?

Relaterede artikler