LU-decompositie

Uit Wikipedia, de vrije encyclopedie

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

[bewerk] Definities

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

$A = LU, \,$

waar L en U respectievelijk de beneden (lower) en boven (upper) driehoeks matrices zijn (beiden van dezelfde grootte). Dit betekent dat L alleen nullen heeft boven de diagonaal en dat U alleen nullen heeft onder de diagonaal.

Voor een $3 \times 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,$

waar D een diagonaalmatrix is en waar L en U eenheids driehoeksmatrices zijn, wat inhoudt dat alle elementen op de diagonalen van L en U gelijk zijn aan één.

Een LUP decomposition is een decompositie van de vorm

$\, A = LUP,$

waar L en U opnieuw de beneden- en boven driehoekigematrices zijn en waar 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 één.

[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, noten en/of referenties

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.

Categorie: Lineaire algebra

See also ebooksgratis.com: no banners, no cookies, totally FREE.

LU-decompositie

Uit Wikipedia, de vrije encyclopedie

Inhoud

[bewerk] Definities

[bewerk] Toepassing

[bewerk] Voorbeeld

[bewerk] Testgeval voor computerprogrammas

[bewerk] Zie ook

[bewerk] Bronnen, noten en/of referenties

Views

Navigatie

Informatie

Zoeken

in andere talen