LU-nedbrytning

LU-nedbrytning ( LU-nedbrytning , LU-faktorisering ) är en representation av en matris som en produkt av två matriser , där är en nedre triangulär matris och är en övre triangulär matris. $A$ $A=LU$ $L$ $U$

LU-sönderdelningen används för att lösa linjära ekvationssystem , invertera matriser och beräkna determinanten . En LU-sönderdelning existerar endast om matrisen är inverterbar och alla ledande (hörn) huvudsakliga minorer i matrisen är icke degenererade [1] . $A$ $A$

Denna metod är en av varianterna av Gauss-metoden .

Applikationer

Lösa system av linjära ekvationer

Den resulterande LU-nedbrytningen av matrisen (matrisen av koefficienter för systemet) kan användas för att lösa en familj av system av linjära ekvationer med olika vektorer på höger sida [2] : $A$ $b$

ax=b

Om LU-sönderdelningen av matrisen , , är känd , kan det ursprungliga systemet skrivas som $A$ $A=LU$

LUx=b.

Detta system kan lösas i två steg. Det första steget är att lösa systemet

Ly=b.

Eftersom det är en lägre triangulär matris löses detta system direkt genom direkt substitution . $L$

I det andra steget är systemet löst

x=y.

Eftersom det är en övre triangulär matris löses detta system direkt genom backsubstitution . $U$

Matrisinversion

Matrisinversion motsvarar att lösa ett linjärt system $A$

AX=I

där är en okänd matris, är identitetsmatrisen. Lösningen på detta system är en omvänd matris . $X$ $jag$ $X$ $A^{{-1}}$

Systemet kan lösas med LU-sönderdelningsmetoden som beskrivs ovan.

Beräkna determinanten för en matris

Med tanke på LU-nedbrytningen av matrisen , $A$

A=LU

vi kan direkt beräkna dess determinant ,

\det(A)=\det(LU)=\det(L)\det(U)=\left(\prod _{{i=1}}^{n}L_{{ii}}\right)\ vänster(\prod _{{i=1}}^{n}U_{{ii}}\right)

var är storleken på matrisen och är de diagonala elementen i matriserna och . $n$ $A$ $L_{{ii}}$ $U_{{ii}}$ $L$ $U$

Härledning av formeln

Baserat på tillämpningsomfånget kan LU-nedbrytningen endast tillämpas på en icke-singular matris, därför kommer vi i det följande att anta att matrisen är icke- singular. $A$

Eftersom både i den första raden av matrisen och i den första kolumnen i matrisen , alla element, utom möjligen det första, är lika med noll, har vi $L$ $U$

a_{{11}}=l_{{11}}u_{{11}}

Om , då eller . I det första fallet består den första raden av matrisen helt och hållet av nollor , i det andra, den första kolumnen i matrisen . Därför, eller är degenererad, och därmed är degenererad , vilket leder till en motsägelse. Således, om , så har den icke-singulära matrisen ingen LU-sönderdelning. $a_{{11}}=0$ $l_{{11}}=0$ $u_{{11}}=0$ $L$ $U$ $L$ $U$ $A$ $a_{{11}}=0$ $A$

Låt , sedan och . Eftersom L och U definieras till att multiplicera U med en konstant och dividera L med samma konstant, kan vi kräva att . Samtidigt . $a_{{11}}\neq 0$ $l_{{11}}\neq 0$ $u_{{11}}\neq 0$ $l_{{11}}=1$ $u_{{11}}=a_{{11}}$

Dela upp matrisen A i celler:

A={\begin{pmatrix}a_{{11}}&w^{T}\\v&A'\\\end{pmatrix}}

där har dimensioner respektive , , . $v,w^{T},A'$ $(N-1)\ gånger 1$ $1\ gånger (N-1)$ $(N-1)\times (N-1)$

På liknande sätt delar vi in i celler i matrisen och : $L$ $U$

L={\begin{pmatrix}1&0\\v_{l}&L'\\\end{pmatrix)),\ U={\begin{pmatrix}a_{11}&w_{u}^{T} \\0&U'\\\end{pmatrix}}.

Ekvationen tar formen $A=LU$

w^{T}=w_{u}^{T},

v=a_{11}v_{l},

A'=v_{l}w_{u}^{T}+L'U'.

När vi löser ekvationssystemet för , , , , får vi: ${\displaystyle v_{l))$ ${\displaystyle w_{u))$ $L'$ $U'$

w_{u}=w,

v_{l}=v/a_{11},

L'U'=A'-vw^{T}/a_{11}.

Äntligen har vi:

L={\begin{pmatrix}1&0\\v/a_{11}&L'\\\end{pmatrix)),

U={\begin{pmatrix}a_{11}&w^{T}\\0&U'\\\end{pmatrix)),

L'U'=A'-vw^{T}/a_{11}.

Så vi har reducerat LU-sönderdelningen av storleksmatrisen till LU-sönderdelningen av storleksmatrisen . $N\ gånger N$ $(N-1)\times (N-1)$

Uttrycket kallas Schur-komplementet av elementet i matrisen A [1] . $A'-vw^{T}/a_{{11}}$ $a_{11}$

Algoritm

En av algoritmerna för att beräkna LU-sönderdelningen visas nedan. [3]

Vi kommer att använda följande notation för matriselement: , , , ; och de diagonala elementen i matrisen : , . $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $i,j=1\prickar n$ $L$ $l_{{ii}}=1$ $i=1\prickar n$

Du kan hitta matriserna och enligt följande (stegen bör utföras strikt i ordning, eftersom följande element hittas med de föregående): $L$ $U$

Slinga i från 1 till n
1. Slinga j från 1 till n
  1. uij =0, lij = 0
  2. l ii =1
Slinga i från 1 till n
1. Slinga j från 1 till n
  1. Om jag<=j: ${\displaystyle u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}*u_{kj))$
  2. Om i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}l_{ik}*u_{kj})/u_{jj))$

Som ett resultat får vi matriser - och . $L$ $U$

Se även

Anteckningar

↑ 1 2 E. E. Tyrtyshnikov. Matrisanalys och linjär algebra. — 2004-2005.
↑ Levitin, 2006 .
↑ Verzhbitsky V.M. Grunderna i numeriska metoder. Lärobok för gymnasieskolor. - Högre skola, 2002. - S. 63-64. — ISBN 5-06-004020-8 .

Litteratur

Ortega J. Introduktion till parallella och vektormetoder för att lösa linjära system. — M .: Mir, 1991. — 376 sid. — ISBN 5-03-001941-3 .
Levitin A. V. Algoritmer. Introduktion till utveckling och analys - M. : Williams , 2006. - 576 sid. — ISBN 978-5-8459-0987-9

Vektorer och matriser

Vektorer

Grundläggande koncept	Vektor i geometri Grund Ortogonal grund Vektorkoordinater Kolinearitet Ortogonalitet Linjärt beroende Kolumnutrymme
Typer av vektorer	Enhet vektor Axiell vektor isotrop vektor Vanligt Kolinearitet Noll vektor Radie vektor Egenvektor
Operationer på vektorer	Skalär produkt vektor produkt blandad produkt Pseudoskalär produkt Dubbelkorsprodukt
Utrymmestyper	vektor utrymme affint utrymme Euklidiskt utrymme Pseudo-euklidiskt utrymme Normerat utrymme Minkowski utrymme

matriser

Grundläggande koncept	Matrismultiplikation Transponerad matris Hermitisk konjugatmatris Symmetrisk matris invers matris Eget värde Karakteristiskt polynom för en matris
Specialmatriser	Identitetsmatris Noll matris Diagonal matris lambda matris
Matrisnedbrytningar	LU-nedbrytning Cholesky nedbrytning QR-sönderdelning LUP-nedbrytning singulärvärdesfaktorisering Spektral nedbrytning av en matris

Övrig