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 ${\displaystyle A}$ är LU-faktoriseringen

${\displaystyle A=LU}$

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

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

Beräkning

Med elementära matriser

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

${\displaystyle E_{n}...E_{2}E_{1}A=U\,}$

där ${\displaystyle E_{k}}$ är en elementär matris, vilket ger

${\displaystyle A=(E_{n}...E_{2}E_{1})^{-1}U\quad \Rightarrow \quad 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 ${\displaystyle E_{k}}$ kan uttryckas som undertriangulära matriser (och då även deras inverser), blir produkten av alla ${\displaystyle E_{k}}$ en undertriangulär matris. Således kan ${\displaystyle A}$ representeras av produkten av en över- och en undertriangulär matris.

Exempel

LU-faktorisering av

${\displaystyle A={\begin{pmatrix}1&-1&3\\1&1&7\\-2&2&-1\end{pmatrix}}}$

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

${\displaystyle U={\begin{pmatrix}1&-1&3\\0&2&4\\0&0&5\end{pmatrix}}}$

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

${\displaystyle E_{1}={\begin{pmatrix}1&0&0\\-1&1&0\\0&0&1\end{pmatrix}},\quad E_{2}={\begin{pmatrix}1&0&0\\0&1&0\\2&0&1\end{pmatrix}}}$

vilka har Inverserna

${\displaystyle E_{1}^{-1}={\begin{pmatrix}1&0&0\\1&1&0\\0&0&1\end{pmatrix}},\quad E_{2}^{-1}={\begin{pmatrix}1&0&0\\0&1&0\\-2&0&1\end{pmatrix}}}$

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

${\displaystyle L=E_{1}^{-1}E_{2}^{-1}={\begin{pmatrix}1&0&0\\1&1&0\\0&0&1\end{pmatrix}}{\begin{pmatrix}1&0&0\\0&1&0\\-2&0&1\end{pmatrix}}={\begin{pmatrix}1&0&0\\1&1&0\\-2&0&1\end{pmatrix}}}$

Observera att ordningen på matriserna kastas om vid inverteringen,

${\displaystyle (E_{2}E_{1})^{-1}=E_{1}^{-1}E_{2}^{-1}}$.

Därmed är A LU-faktoriserad:

${\displaystyle A=LU={\begin{pmatrix}1&0&0\\1&1&0\\-2&0&1\end{pmatrix}}{\begin{pmatrix}1&-1&3\\0&2&4\\0&0&5\end{pmatrix}}}$

Tillämpningar

Ekvationssystemlösning

För en samling ekvationssystem ${\displaystyle A\mathbf {x_{k}} =\mathbf {b_{k}} }$ för vilka A är konstant men ${\displaystyle \mathbf {b_{k}} }$ 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 ${\displaystyle L\mathbf {y} =\mathbf {b_{k}} }$ och sedan ekvationssystemet ${\displaystyle U\mathbf {x_{k}} =\mathbf {y} }$. Båda dessa ekvationssystem är lätta att lösa då vänsterleden representeras av triangulära matriser.

Inversberäkning

Då ${\displaystyle A=LU}$ är ${\displaystyle 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

${\displaystyle \det {A}=\det {L}\det {U}\,}$

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

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

Se även

• Matrisfaktorisering