LUdekomponering

LU-dekomponering, ofta kallad LU-decomposition, är en faktorisation av en kvadratisk tät matris A till produkten A = LU, där L är en nedre triangulär matris och U är en övre triangulär matris. I många konstruktioner har L en enhetsdiaginal och U bär sina diagonala element (varianten kallad Doolittle; Crout-varianten har i stället enhetsdiaginalen i U). Faktoriseringen gör det möjligt att lösa linjära system snabbare än vid direkt elimination.

I praktiken används ofta permutation av rader för att förbättra stabiliteten. Då skrivs faktoriseringen som P A = L U, där P är en permutationsmatris. Denna roterande effekt uppnås vanligen genom Gausseliminering med partiell pivotering och gör att man kan hantera fall där vissa pivoter skulle vara noll eller mycket små. Utan pivotering finns det matriser som inte har en LU-faktorisering.

Användning och beräkning: När LU-faktoriseringen är känd kan systemet Ax = b lösas genom två triangulära system: först L y = P b och sedan U x = y, med framåtsubstitution och bakåtsubstitution. Denna metod är särskilt effektiv när man ska lösa flera högerled, eftersom man återanvänder faktorerna L och U. Tidskomplexiteten för densamma är ungefär O(n^3) för täta matriser, och L och U kan lagras i samma minnesblock som A.

Exempel och tillämpningar: LU-dekomponering används vid beräkningar av determinanten (det(A) = det(P) det(L) det(U) = ± produkten av diagonala elementen i U), vid matrisinversion och som byggsten i många numeriska metoder för linjära system och preconditioner i iterative metoder. Relative begränsningar beror på numerisk stabilitet och pivoteringens behov.