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.
Inhoud |
[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:
- en
De matrix A is als volgt als LU-decompositie te schrijven:
- A = LU met en .
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
Bron(nen): |
|