LU-decompositie

De LU-decompositie of -factorisatie van een matrix A is de decompositie van een matrix in een benedendriehoeksmatrix L (Eng: Lower), een bovendriehoeksmatrix U (Eng:Upper) en een permutatiematrix P, zodanig dat:

$PA=LU$

oftewel

$A=P^{-1}LU$.

Deze decompositie wordt in de numerieke wiskunde gebruikt om systemen van lineaire vergelijkingen op te lossen of om de determinant van een matrix te berekenen.

Een stelling uit de lineaire algebra zegt dat er voor elke inverteerbare matrix A een LU-decompositie bestaat. Soms kan dit zelfs door

$P=I$, de identiteitsmatrix, te kiezen.

In dit geval heeft de decompositie de vorm:

$A=LU$.

Definities

Laat A een vierkante matrix zijn. Een LU-decompositie van A is een opsplitsing van A in de vorm

$A=LU$,

waarin L (lower) en U (upper) respectievelijk de beneden- en bovendriehoeksmatrices zijn (beide van dezelfde dimensie). Dit betekent dat boven de diagonaal van L en onder de diagonaal van U alleen nullen staan.

Voor een 3×3-matrix ziet dit er als volgt uit:

${\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{bmatrix}}={\begin{bmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\\\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}.$

Merk op dat er in de oorspronkelijke matrix 9 (of n×n) elementen zijn en in L en U samen 12 (of (n+1)×n). Deze redundantie kan men op verschillende wijzen wegwerken:

• In de methode van Doolittle zijn de diagonale elementen van L gelijk aan 1;
• In de methode van Crout zijn de diagonale elementen van U gelijk aan 1;
• In de methode van Cholesky, die gebruikt wordt voor symmetrische matrices, zijn de diagonale elementen van U gelijk aan die van L (U is daar de getransponeerde matrix van L).

In deze methoden worden L en U bekomen door een variatie op de Gauss-eliminatie.

Een LDU-decompositie is een decompositie van de vorm

$A=LDU$,

waarin D een diagonaalmatrix is en L en U driehoeksmatrices zijn waarvan alle elementen op de diagonalen gelijk zijn aan 1.

Een LUP-decompositie is een decompositie van de vorm

$A=LUP$,

waarin L en U opnieuw beneden- en boven driehoeksmatrices zijn en P een permutatiematrix is, een matrix van nullen en enen die in elke rij en elke kolom precies één element heeft dat gelijk is aan 1. De permutatiematrix is aanvankelijk de eenheidsmatrix. Tijdens de berekeningen is het soms nodig om twee rijen te verwisselen om deling door nul te vermijden. Dat gebeurt dan ook in de permutatiematrix, die bijhoudt welke rijen waar terechtkomen.

Toepassing

Stel dat we het stelsel lineaire vergelijkingen willen oplossen dat in termen van de matrix A wordt beschreven als:

Ax = b,

waarbij A een n×m-matrix is en een b een n-dimensionale vector.

Als L, U en P zodanig zijn dat de LU-decompositie van A voldoet aan

PA = LU,

dan geldt,

A = P⁻¹LU.

Het op te lossen systeem is dus:

P⁻¹LUx = b.

We lossen op:

Ly = Pb,

Ux = y.

Dit zijn twee relatief gemakkelijk op te lossen driehoekige matrixsystemen. Er geldt:

Ux = L⁻¹Pb

Dus:

P⁻¹LUx = b.

Hiermee is het oorspronkelijke, mogelijk moeilijk op te lossen, systeem teruggebracht tot twee eenvoudigere stelsels lineaire vergelijkingen.

Voorbeeld

Stel, we willen de vergelijking $Ax=b$ oplossen met $A$ en $b$ gegeven door:

$A={\begin{pmatrix}3&-7&-2&2\\-3&5&1&0\\6&-4&0&-5\\-9&5&-5&12\\\end{pmatrix}}$ en $b={\begin{pmatrix}-9\\5\\7\\11\\\end{pmatrix}}$

De matrix A is als volgt als LU-decompositie te schrijven:

A = LU met $L={\begin{pmatrix}1&0&0&0\\-1&1&0&0\\2&-5&1&0\\-3&8&3&1\\\end{pmatrix}}$ en $U={\begin{pmatrix}3&-7&-2&2\\0&-2&-1&2\\0&0&-1&1\\0&0&0&-1\\\end{pmatrix}}$.

Voor deze LU-decompositie is P de identiteitsmatrix.

We kunnen nu de oorspronkelijke matrixvergelijking terugbrengen tot de twee vergelijkingen Ly = Pb = b en Ux = y.

Het oplossen van Ly = b resulteert in y = (–9, –4, 5, 1) en de oplossing van Ux = y is x = (3, 4, –6, –1). x is tevens de oplossing van de oorspronkelijke matrixvergelijking.

Testgeval voor computerprogramma's

Een van de klassieke testgevallen voor computerprogramma's, die de LU-decompositie doen, is de Hilbert-matrix, die numerisch slecht geconditioneerd, maar wel zeker inverteerbaar is.

literatuur

• David C. Lay; Linear Algebra and its Applications, Addison-Wesley, 2002.
• Charles F. van Loan; Introduction to Scientific Computing, Prentice-Hall, 2000.