LU-decompositie

De LU-decompositie van een matrix A is de decompositie van een matrix in een benedendriehoeksmatrix L, een bovendriehoeksmatrix U en een permutatiematrix P, zodanig dat:

PA = LU oftewel A = P^-1LU

Deze decompositie wordt gebruikt om systemen van lineaire vergelijkingen op te lossen.

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.

[bewerk] 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.

[bewerk] Voorbeeld

Stel dat we willen oplossen:

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

[bewerk] Testgeval voor computerprogrammas

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

[bewerk] Zie ook

Gauss-eliminatie
Cholesky-decompositie
QR-decompositie

[bewerk] Bronnen

Bron(nen):

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

Categorie: Lineaire algebra