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

DefinitionRedigera

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äkningRedigera

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

Genom Gram-SchmidtRedigera

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:

 

 -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 HouseholderreflektionerRedigera

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 .

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ämpningarRedigera

Minsta kvadrat-lösningarRedigera

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ärdenRedigera

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 ävenRedigera

  Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.