LU-decompositie

De LU-decompositie 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 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 gaat de decompositie over in:

$\, A = LU$.

Definities

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

$A = LU$,

waarin L en U respectievelijk de beneden (lower) en boven (upper) driehoeksmatrices zijn (beide van dezelfde grootte). Dit betekent dat L alleen nullen heeft boven de diagonaal en U alleen nullen onder de diagonaal.

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}.$

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 driehoekigematrices zijn en P de permutatiematrix is, een matrix van nullen en enen die in elke rij en elke kolom precies één element heeft dat gelijk is aan 1.

Toepassing

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

Ax = b,

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

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

PA = LU,

dan geldt,

A = P^-1LU.

Het op te lossen systeem is dus:

P^-1LUx = b.

We lossen op:

Ly = Pb,

Ux = y.

Dit zijn twee (makkelijk op te lossen) driehoekige matrixsystemen. We hebben nu opgelost:

Ux = L^-1Pb

Dus:

P^-1LUx = b.

Hiermee is het oorspronkelijke (mogelijk moeilijk op te lossen) systeem opgelost via het oplossen van 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}$.

Hier geldt dus dat een LU-compositie is te verkrijgen met P de identiteitsmatrix.

We kunnen nu de oorspronkelijke matrix vergelijking oplossen door eerst op te lossen Ly = Pb = b, en daarna Ux = y.

Het oplossen van Ly = b resulteert in y = (–9, –4, 5, 1). Nu rest het oplossen van Ux = y voor de onbekende oplossen en y als hiervoor. Dit geeft x = (3, 4, –6, –1). Dit is 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.

Zie ook

• Gauss-eliminatie
• Cholesky-decompositie
• QR-decompositie

Bronnen, noten en/of referenties David C. Lay; Linear Algebra and its Applications, Addison-Wesley, 2002. Charles F. van Loan; Introduction to Scientific Computing, Prentice-Hall, 2000.