Inom linjär algebra är LU-faktorisering, ibland kallad LR-faktorisering, en matrisfaktorisering där en matris delas upp i en övertriangulär matris (om ursprungsmatrisen är kvadratisk) och en undertriangulär matris. LU-faktorisering används bland annat för att lösa linjära ekvationsystem med samma vänsterled.

DefinitionRedigera

För en matris   är LU-faktoriseringen

 

Om   är kvadratisk är även   (som blir en undertriangulär matris) och   (som blir en övertriangulär matris) kvadratiska. Om   inte är kvadratisk blir inte   kvadratisk (och då inte heller triangulär), men   blir kvadratisk och triangulär.

Ibland används en permutationsmatris   för att undvika fel på grund av den numeriska metoden, vilket kallas (partiell) pivotering. Matrisen skrivs då om på formen  

BeräkningRedigera

Med elementära matriserRedigera

Genom multiplikation med elementära matriser för radoperationer kan den kvadratiska matrisen   omvandlas till en övertriangulär matris   (i likhet med Gausselimination):

 

där   är en elementär matris, vilket ger

 

inverser till elementära matriser är lättberäknade (se artikeln om elementära matriser) och alla   kan uttryckas som undertriangulära matriser (och då även deras inverser), blir produkten av alla   en undertriangulär matris. Således kan   representeras av produkten av en över- och en undertriangulär matris.

ExempelRedigera

LU-faktorisering av

 

Genom gausselimination framgår att en övertriangulär matris   kan fås genom radadditioner:

 

Dessa radoperationer kan beskrivas som

  1. Subtrahera rad 1 från rad 2
  2. Addera rad 1 två gånger till rad 3

där radoperationerna kan representeras av elementära matriser enligt

 

vilka har Inverserna

 

Observera hur enkel inversberäkningen är. Det är bara att byta tecken på det nollskilda talet utanför diagonalen.   kan nu beräknas:

 

Observera att ordningen på matriserna kastas om vid inverteringen,

 .

Därmed är A LU-faktoriserad:

 

TillämpningarRedigera

EkvationssystemlösningRedigera

För en samling ekvationssystem   för vilka A är konstant men   varierar, lönar det sig att LU-faktorisera A, då ekvationssystemet kan lösas för en av de triangulära matriserna i taget. Först löses ekvationssystemet   och sedan ekvationssystemet  . Båda dessa ekvationssystem är lätta att lösa då vänsterleden representeras av triangulära matriser.

InversberäkningRedigera

  är  . En triangulär matris är lättare att invertera än en icke-triangulär, varför det är lättare att beräkna inversen genom LU-faktorisering. Datorprogram beräknar ofta matrisinverser genom LU-faktorisering.

DeterminantberäkningRedigera

Determinantberäkning är enkelt för en LU-faktoriserad matris, då determinanten för en triangulär matris är produkten av diagonalelementen och

 

Om   dessutom endast har ettor i diagonalen (som den ofta har, se till exempel beräkningsexemplet ovan), får vi att

 

Se ävenRedigera