LUdecomposities

LU-decompositie, ook wel LU-factorisatie genoemd, is een factorisatie van een vierkante matrix A in de vorm A = L U, waarbij L een lagere driehoeks matrix is en U een boven driehoeks matrix. In veel toepassingen wordt ook rekening gehouden met een rijpermute P, zodat P A = L U. Deze factorisatie maakt het mogelijk om lineaire systemen Ax = b efficiënt op te lossen door twee eenvoudige driehoeksystemen achter elkaar op te lossen: L y = P b en U x = y.

Bestaan en pivoting: Een LU-decompositie zonder rijpermatie bestaat niet voor alle matrices. Voor welk type matrices deze decompositie bestaat, geldt dat alle leidende hoofdminor’s niet-nul moeten zijn. In de praktijk is het gebruikelijk om rijpivoting toe te passen, waardoor men de PLU-decompositie verkrijgt: P A = L U. Pivoting verhoogt de numerieke stabiliteit en voorkomt grote foutgroei tijdens Gauss-eliminatie. Volledige pivotering (ook kolomrotatie) is mogelijk, maar meestal niet nodig.

Varianten: Er zijn verschillende conventies. Bij Doolittle heeft L een diagonaal met 1’en, bij Crout heeft U een diagonaal met 1’en. Deze keuzes wijzigen hoe de elementen van L en U worden geïnterpreteerd, maar de basisgrootte van de factorisatie blijft hetzelfde.

Toepassingen en eigenschappen: LU-decompositie wordt veel gebruikt bij het oplossen van systemen Ax = b, bij het bepalen van determinant en inverse van A, en bij het uitvoeren van numerieke lineaire algebra aan de hand van efficiënte back-substitutie. De rekentijd voor een volledige LU-decompositie is O(n^3) voor een n×n-matrix, wat aanzienlijk sneller is dan herhaalde Gauss-eliminatie zonder hergebruik van de factorisatie.