LUdecompositie

LU-decompositie is een factorisatie van een vierkante matrix A in het product van een lagere driehoeksmatrix L en een boven driehoeksmatrix U, zodanig dat A = LU. Bij sommige conventies heeft L een eenheidsdiagonaal (Doolittle), bij andere heeft U een eenheidsdiagonaal (Crout). Vaak worden L en U in één opslagmatrix geplaatst, waarbij onder de diagonaal L en erboven U wordt opgeslagen.

Bestaan en voorwaarden: zonder rij-omzettingen bestaat een LU-decompositie als alle leidende hoofdminors niet nul zijn; dit komt overeen met het feit dat Gaussische eliminatie zonder nul-pivots kan doorgaan. Met gedeeltelijke pivoting bestaat er voor elke vierkante invertibele matrix A een permutatiematrix P zodat PA = LU. Voor singuliere matrices kan dergelijke factorisatie ontbreken.

Berekening en toepassingen: LU ontstaat via Gaussische eliminatie. Om Ax = b op te lossen, los je eerst Ly = b en daarna Ux = y op (door voortgezette substitutie). De rekensnelheid is O(n^3) en L en U kunnen in één matrix worden opgeslagen: onder de diagonaal L, erboven U.

Varianten en stabiliteit: De Doolittle-variant heeft eenheidsdiagonaal in L, Crout heeft eenheidsdiagonaal in U. Pivoting verhoogt de stabiliteit: partiële pivoting wisselt rijen zodat de pivots groter zijn; volledige pivoting kan ook kolommen verwisselen.

Toepassingen: oplosser voor lineaire systemen, berekenen van determinanten, inversie van matrices en in vele numerieke algoritmes. LU-decompositie is een basistechniek in lineaire algebra en wetenschappelijke berekeningen.