LU-faktorisering

Från Wikipedia
Hoppa till: navigering, sök

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

Definition[redigera | redigera wikitext]

För en matris är LU-faktoriseringen

Om är kvadratisk är även (som blir en nedåt triangulär matris) och (som blir en uppåt triangulä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[redigera | redigera wikitext]

Med elementära matriser[redigera | redigera wikitext]

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.

Exempel[redigera | redigera wikitext]

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ämpningar[redigera | redigera wikitext]

Ekvationssystemlösning[redigera | redigera wikitext]

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[redigera | redigera wikitext]

ä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[redigera | redigera wikitext]

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[redigera | redigera wikitext]