LU-faktorisering

Inom linjär algebra är LU-faktorisering, ibland kallat LR-faktorisering, en matrisfaktorisering där man delar upp en matris i en uppåt triangulär matris (om ursprungsmatrisen är kvadratisk) och en nedåt triangulär matris. LU-faktorisering används för att lösa linjära ekvationsystem med samma vänsterled snabbare.

Definition

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

$A = LU$

Om $A$ är kvadratisk är även $L$ (som blir en nedåt triangulär matris) och $U$ (som blir en uppåt triangulä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, detta 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 radadditioner kan den kvadratiska matrisen $A$ omvandlas till en övertriangulär matris $U$ (i grund och botten samma sak som Gausselimination). Vi har alltså att:

$E_n...E_2E_1A = U \,$

Där $E_k$ är en elementär matris. Detta ger att:

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

Då inversen 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. Och alltså har $A$ uttryckts som produkten av en över- och en undertriangulär matris.

Exempel

Följande matris ska LU-faktoriseras:

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

Genom Gausselimination ser vi att en övertriangulär matris $U$ kan fås genom radadditioner:

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

Dessa radoperationer kan beskrivas som:

1. Dra 1 av rad 1 från rad 2
2. Lägg 2 av rad 1 till rad 3

Där varje kan uttryckas som en elementär matris:

$E_1 = \begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} ,E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 2 & 0 & 1 \end{pmatrix}$

Som ger inverser:

$E_1^{-1} \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} ,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å talet utanför diagonalen. Nu kan vi beräkna vårt $L$:

$L = E_2^{-1} E_1^{-1} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ -2 & 0 & 1 \end{pmatrix}$

Observera att ordningen på matriserna kastas om när man tar invers, $(E_1 E_2)^{-1} = E_2^{-1} E_1^{-1}$.

A är nu LU-faktoriserad:

$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

Om man har en samling ekvationsystem $A\mathbf{x_k} = \mathbf{b_k}$ där man vill hitta $\mathbf{x_k}$ till respektive $\mathbf{b_k}$, men $A$ är samma i alla ekvationsystemen, lönar det sig att LU-faktorisera, då man löser ekvationssystemet för en av de triangulära matriserna i taget, det går till som så att man löser ekvationsystemet $L\mathbf{y} = \mathbf{b_k}$ och sedan ekvationsystemet $U\mathbf{x_k} = \mathbf{y}$. Båda dessa ekvationsystem är lätta att lösa då vänsterledet representeras av en triangulär matris.

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 matris, så det är lättare att beräkna inversen genom LU-faktorisering. Datorprogram beräknar ofta matrisinverser genom LU-faktorisering.

Determinantberäkning

Determinantberäkning är väldigt 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