LU-faktorisering
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.
Definition
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äkning
Med elementära matriser
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
Då 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.
Exempel
LU-faktorisering av
Genom gausselimination framgår att en övertriangulär matris kan fås genom radadditioner:
Dessa radoperationer kan beskrivas som
- Subtrahera rad 1 från rad 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ämpningar
Ekvationssystemlösning
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äkning
Då ä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äkning
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 även
- Matrisfaktorisering