QR-faktorisering

Inom linjär algebra är QR-faktorisering en matrisfaktorisering av en (reell) matris i en ortogonal matris och en triangulär matris.

Definition
En QR-faktorisering av en reell kvadratisk matris  kan uttryckas:

För en ortogonal matris  och en övertriangulär matris . 
Om  istället är komplex är  en unitär matris.

Detta kan generaliseras till att  är en matris av format  där , då  är en ortogonal (unitär) matris med format  och  är en övertriangulär matris med format .

Beräkning
Det finns flera sätt att beräkna QR-faktoriseringen av en matris. Det vanligaste sättet är genom Gram-Schmidts ortogonaliseringsprocess.

Genom Gram-Schmidt
Om matrisen  har kolonnvektorerna  som är linjärt oberoende, kan man genom Gram-Schmidts ortogonaliseringsprocess bestämma vektorer  som är ortogonala. De gamla -vektorerna kan nu skrivas som linjärkombinationer av de nya -vektorerna:

Om vi nu placerar våra -värden i en matris, , och de ortogonala vektorerna i en annan matris, , kan vi uttrycka den gamla matrisen  som produkten av dessa:

Då -vektorerna är ortogonala är  ortogonal (unitär om vektorerna är komplexa). 

För att få -värdena kan man lösa dem ur ortogonaliseringsprocessen man gör, eller så använder man sig av faktumet att:

Så att  kan beräknas genom en enkel matrismultiplikation ( står för det hermiteska konjugatet till , som i det reella fallet är samma sak som transponat).

Med Householderreflektioner
En Householdertransformation är en linjär avbildning som reflekterar en vektor i ett hyperplan. Detta kan användas till att QR-faktorisera en matris. Denna metod är numeriskt stabilare än Gram-Schmidt-metoden och har en tidskomplexitet på .

För beräkningen tas speciella Householdertransformationer fram. Man utgår från en vektor  och tar ett tal a så att . Om QR-faktoriseringen görs med flyttalsberäkningar och vektorn är reell bör a väljas med motsatt tecken från första elementet i vektorn , om vektorn är komplex bör a väljas genom:

Sedan konstrueras Householdertransformationen Q på följande sätt ( är vektorn ):

För att QR-faktorisera m×n-matrisen A, konstruerar man en Householdertransformation Q1 enligt ovan från första kolonnen i A. Man får då

Man kan sedan konstruera en ny Householdertransformation  från första kolonnen i  ( fås genom att plocka bort första kolonnen och första raden i ). Eftersom man vill verka på matrisen  och inte  så tar man matrisen  och fyller ut den. För ett generellt steg i QR-faktoriseringen får man matrisen:

Vid multiplikation med Q2 fås alltså en matris  som är lika stor som A. Ur denna matris läser man ut  som är två steg mindre än A, tar den första kolonnen och konstruerar  varur man konstruerar Q3 enligt ovan.

Sedan upprepas detta  steg, då man fått

där R är övertriangulär och

är en unitär matris (eftersom Householdertransformationer är unitära). Alltså är  en QR-faktorisering av A.

Tillämpningar

Minsta kvadrat-lösningar
Om man ska hitta minsta kvadrat-lösningen till ett ekvationssystem givet av ekvationen  förenklas detta om  är QR-faktoriserad. Lösningen ges i vanliga fall av

Om  ger vänsterledet

och högerledet

så att ekvationen blir

som är ett väldigt lättlöst ekvationsysstem eftersom  är triangulär.

Determinanter, egenvärden och singulärvärden
Om A är en kvadratisk matris av storlek n som är QR-faktoriserad, , då det ur räknelagarna för determinanten att

Eftersom Q är unitär är , vilket ger:

där  är värdena i R:s diagonal. Då man även vet att determinanten av A är produkten av A:s egenvärden följer det att

där  är A:s egenvärden.

Man kan generalisera resonemanget ovan till att gälla matriser A som inte är kvadratiska, då man från egenskaper hos singulärvärdesfaktoriseringen får att:

där  är A:s singulärvärden.

Se även
Matrisfaktorisering

Matrisalgebra