LU-faktorisering

Inom linjär algebra är LU-faktorisering, ibland kallad LR-faktorisering, en matrisfaktorisering där en matris delas upp i en övertriangulär matris (om ursprungsmatrisen är kvadratisk) och en undertriangulär matris. LU-faktorisering används bland annat för att lösa linjära ekvationsystem med samma vänsterled.

Definition

För en matris $A$ är LU-faktoriseringen

$A=LU$

Om $A$ är kvadratisk är även $L$ (som blir en undertriangulär matris) och $U$ (som blir en övertriangulär matris) kvadratiska. Om $A$ inte är kvadratisk blir inte $U$ kvadratisk (och då inte heller triangulär), men $L$ blir kvadratisk och triangulär.

Ibland används en permutationsmatris $P$ för att undvika fel på grund av den numeriska metoden, vilket kallas (partiell) pivotering. Matrisen skrivs då om på formen $PA=LR$

Beräkning

Med elementära matriser

Genom multiplikation med elementära matriser för radoperationer kan den kvadratiska matrisen $A$ omvandlas till en övertriangulär matris $U$ (i likhet med Gausselimination):

$E_n...E_2{E}_{1}A=U$

där $E_k$ är en elementär matris, vilket ger

$A=(E_n...E_2{E}_1{)}^{-1}U\Rightarrow A=E_1^{-1}{E}_2^{-1}...E_n^{-1}U$

Då inverser till elementära matriser är lättberäknade (se artikeln om elementära matriser) och alla $E_k$ kan uttryckas som undertriangulära matriser (och då även deras inverser), blir produkten av alla $E_k$ en undertriangulär matris. Således kan $A$ representeras av produkten av en över- och en undertriangulär matris.

Exempel

LU-faktorisering av

$A=\left(\begin{array}{ccc}1& -1& 3\\ 1& 1& 7\\ -2& 2& -1\end{array}\right)$

Genom gausselimination framgår att en övertriangulär matris $U$ kan fås genom radadditioner:

$U=\left(\begin{array}{ccc}1& -1& 3\\ 0& 2& 4\\ 0& 0& 5\end{array}\right)$

Dessa radoperationer kan beskrivas som

1. Subtrahera rad 1 från rad 2
2. Addera rad 1 två gånger till rad 3

där radoperationerna kan representeras av elementära matriser enligt

$E_1=\left(\begin{array}{ccc}1& 0& 0\\ -1& 1& 0\\ 0& 0& 1\end{array}\right),E_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 2& 0& 1\end{array}\right)$

vilka har Inverserna

$E_1^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}\right),E_2^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -2& 0& 1\end{array}\right)$

Observera hur enkel inversberäkningen är. Det är bara att byta tecken på det nollskilda talet utanför diagonalen. $L$ kan nu beräknas:

$L=E_1^{-1}{E}_2^{-1}=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ -2& 0& 1\end{array}\right)=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ -2& 0& 1\end{array}\right)$

Observera att ordningen på matriserna kastas om vid inverteringen,

$(E_2{E}_1{)}^{-1}=E_1^{-1}{E}_2^{-1}$.

Därmed är A LU-faktoriserad:

$A=LU=\left(\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ -2& 0& 1\end{array}\right)\left(\begin{array}{ccc}1& -1& 3\\ 0& 2& 4\\ 0& 0& 5\end{array}\right)$

Tillämpningar

Ekvationssystemlösning

För en samling ekvationssystem $A{𝐱}_{𝐤}={𝐛}_{𝐤}$ för vilka A är konstant men ${𝐛}_{𝐤}$ varierar, lönar det sig att LU-faktorisera A, då ekvationssystemet kan lösas för en av de triangulära matriserna i taget. Först löses ekvationssystemet $L𝐲={𝐛}_{𝐤}$ och sedan ekvationssystemet $U{𝐱}_{𝐤}=𝐲$. Båda dessa ekvationssystem är lätta att lösa då vänsterleden representeras av triangulära matriser.

Inversberäkning

Då $A=LU$ är $A^{-1}=U^{-1}{L}^{-1}$. En triangulär matris är lättare att invertera än en icke-triangulär, varför det är lättare att beräkna inversen genom LU-faktorisering. Datorprogram beräknar ofta matrisinverser genom LU-faktorisering.

Determinantberäkning

Determinantberäkning är enkelt för en LU-faktoriserad matris, då determinanten för en triangulär matris är produkten av diagonalelementen och

$\det A=\det L\det U$

Om $L$ dessutom endast har ettor i diagonalen (som den ofta har, se till exempel beräkningsexemplet ovan), får vi att

$\det A=\det U=\prod _{i=1}^n{u}_{ii}$

Se även

• Matrisfaktorisering