QR-faktorigo

(Alidirektita el RQ-malkomponaĵo)

En lineara algebro, QR-malkomponaĵoQR-faktorigo de matrico estas matrico malkomponaĵo de la matrico en ortan kaj dekstran triangulan matricojn. QR-malkomponaĵo estas ofte uzata por solvado de lineara problemo de plej malgrandaj kvadratoj, kaj estas la bazo por aparta ajgena algoritmo, la QR-algoritmo.

DifinoRedakti

Por kvadrata matricoRedakti

QR-malkomponaĵo de reela kvadrata matrico A estas malkomponaĵo de A kiel

A = QR

kie Q estas orta matrico (tio estas ke QTQ = I ) kaj R estas dekstra triangula matrico (ankaŭ nomata kiel supra triangula matrico).

Se A estas inversigebla matrico, tiam ĉi tiu faktorigo estas unika se postuli ke diagonalaj eroj de R estu pozitivaj.

Por kompleksa kvadrata matrico A, Q estas unita matrico Q (tio estas ke Q*Q = I ).

Por ne-kvadrata matricoRedakti

Pli ĝenerale, oni povas faktorigu kompleksan m×n-matricon A, kun m≥n, kiel produton de unita matrico Q de dimensioj m×m kaj supra triangula matrico R de dimensioj m×n. En la malsupro (m-n-linioj) la supra triangula matrico de dimensioj m×n konsistas plene el nuloj. Estas ofte utile dispartigi matricon R, aŭ ambaŭ R kaj Q:

 

kie R1 estas supra triangula matrico de dimensioj n×n, Q1 estas m×n, Q2 estas m×(m-n), kaj Q1 kaj Q2 ambaŭ havas ortajn kolumnojn.

La Q1R1 estas nomata la maldika QR-faktorigo de A. Se A estas de plena rango n kaj postuli, ke la diagonalaj eroj de R1 estu pozitivaj, tiam R1 kaj Q1 estas unikaj, sed ĝenerale Q2 ne estas unika. R1 estas tiam egala al la supra triangula faktoro de la malkomponaĵo de Cholesky de A*A (kio estas la samo kiel ATA se A estas reela).

QL-, RQ- kaj LQ-malkomponaĵojRedakti

Analoge, oni povas difini QL-, RQ- kaj LQ-malkomponaĵojn, kie L estas suba triangula matrico.

Komputado de QR-malkomponaĵoRedakti

Estas kelkaj manieroj por reale komputi la QR-malkomponaĵon, per la procezo de Gram-Schmidt, transformoj de Householderturnadoj de Givens. Ĉiu havas kelke da avantaĝoj kaj malavantaĝoj.

Procezo de Gram-SchmidtRedakti

Konsideru la procezon de Gram-Schmidt aplikitan al kolumnoj de la matrico  , kun ena produto   (aŭ   por la kompleksa okazo).

Estu la projekcio:

 

tiam

 
 
 
...
 

Oni tiam reordigu la ekvaciojn pli supre tiel ke la ai estu maldekstre, uzante tion ke la ei estas unuoblaj vektoroj:

 
 
 
...
 

kie  . Ĉi tio povas esti skribita en matrica formo:

A = QR

kie:

 
 

EkzemploRedakti

Estu

 

Oni povas kalkuli matricon Q per procezo de Gram-Schmidt:

 
 

Tial

A = QQTA = QR
 

Rilato al RQ-malkomponaĵoRedakti

La RQ-malkomponaĵo konvertas la matricon A en produton de supra triangula matrico R (ankaŭ konata kiel dekstra triangula) kaj orta matrico Q. La nura diferenco de QR-malkomponaĵo estas la ordo de ĉi tiuj matricoj.

QR-malkomponaĵo estas ortigo de Gram-Schmidt de kolumnoj de A, startigita de la unua kolumno.

RQ-malkomponaĵo estas ortigo de Gram-Schmidt de linioj de A, startigita de la lasta linio.

Uzo de reflektoj de HouseholderRedakti

Reflekto de Householder (aŭ transformo de Householder) estas transformo kiu prenas vektoron kaj reflektas ĝin ĉirkaŭ iu ebeno. Oni povas uzi ĉi tiun operacion por kalkuli la QR-faktorigon de m×n-matrico A kun m≥n.

Q povas esti uzata por reflekti vektoron en tia maniero ke ĉiuj koordinatoj krom unu nuliĝas.

Estu x ajna reela m-dimensia kolumna vektoro de A tia ke ||x|| = |α| por skalaro α. Se la algoritmo estas realigata per glitkoma aritmetiko, tiam α devus preni la kontraŭan signon de la unua koordinato de x por eviti malprofiton de signifeco. En la komplekso okazo

 

kaj anstataŭ transpono estas konjugita transpono en la konstruado de Q pli sube.

Tiam

 
 
 

kie e1 estas la vektoro (1, 0, ..., 0)T, ||·|| estas la eŭklida normo kaj I estas identa matrico de dimensio m×m

Aŭ, se A estas kompleksa

 , kie  
kie   estas la transpono kaj konjugito de x

Q estas matrico de Householder de dimensio m×m kaj

Qx = (α, 0, ..., 0)T

Ĉi tio povas esti uzata por laŭgrade konverti m×n-matricon A al supra triangula formo. Unue, oni multipliku A kun la matrico de Householder Q1 kiun oni ricevis kiam elekti la unua matrican kolumnon por x. Ĉi tio donas matricon Q1A kun nuloj en la maldekstra kolumno ĉie escepte de la unua linio.

 

Ĉi tio povas ripetiĝi por A′ (ricevita de Q1A per forviŝo de la unua linio kaj unua kolumno), rezultante en matrico de Householder Q′2. Noto ke Q′2 estas pli malgranda ol Q1. Pro tio ke oni bezonas ke ĝi reale al operaciu sur Q1A anstataŭ A′ oni bezonas elvolvi ĝin al la supro-maldekstro, enspacante per ero 1, aŭ ĝenerale per unua matrico:

 

Post t ripetoj de ĉi tiu procezo kie t = min(m-1, n),

R = Qt ... Q2Q1A

estas supra triangula matrico. Do kun

 

A = QR estas QR-malkomponaĵo de A.

Ĉi tiu maniero havas pli grandan nombran stabilecon ol la maniero de Gram-Schmidt pli supre priskribita.

La kvanto de operacioj en la k-a paŝo de la QR-malkomponigado per la transformo de Householder de kvadrata n×n-matrico estas

Operacio Kvanto
multipliko  
adicio  
divido 1
kvadrata radiko 1

Sumante ĉi tiujn nombrojn tra la (n-1) paŝoj por kvadrata matrico de amplekso n, la komplekseco de la algoritmo (laŭ la glit-komaj multiplikoj) estas

 

EkzemploRedakti

Estu same kiel supre

 

Unue, oni bezonas trovi reflekton kiu konvertas la unuan kolumnon de matrico A, vektoron  , al  

Do

 

kaj

 

Ĉi tie,

α=14 kaj  

Pro tio

  kaj  , kaj tiam
 
 
 

Tiam

 

do oni jam havas preskaŭ triangulan matricon. Nun nur bezonatas nuligi la (3, 2)-elementon (de valoro 168).

Prenu la (1, 1)-minoron, kaj tiam apliku la procezon denove al

 

Per la sama maniero kiel pli supre, oni ricevas la matricon de la transformo de Householder

 

post aldono de valoro 1 je supro-maldekstro por havi taŭgan amplekson de la matrico por la sekva paŝo.

Nun

 
 

La matrico Q estas orta kaj R estas supra triangula, do A = QR estas la postulita QR-malkomponaĵo.

Uzo de turnadoj de GivensRedakti

QR-malkomponaĵo povas ankaŭ esti komputita per serio de turnadoj de Givens. Ĉiu turnado nuligas eron sub la diagonalo de la matrico, formante laŭgrade la matricon R. La kunmeto de ĉiuj turnadoj de Givens formas la ortan matricon Q.

En praktiko, turnadoj de Givens ne estas reale plenumataj per konstruado de la tuta matrico kaj faro de matrica multipliko. Turnada proceduro de Givens estas uzata anstataŭe, kiu faras la ekvivalenton de la multipliko de matrico de Givens enhavanta multajn nulojn, sen la superflua laboro. La turnada proceduro de Givens estas utila en situacioj, en kiuj estas nur relative malmultaj nenulaj nediagonalaj eroj, kaj ĝi estas pli facile paraleligebla ol transformoj de Householder.

EkzemploRedakti

Estu la same kiel pli supre

 

Unue, oni bezonas formi turnadan matricon kiu nuligas la plej malsupro-maldekstran eron, a31 = -4. Oni formas ĉi tiu matricon G1 uzante la turnadon de Givens. Oni unue turnas la vektoron (6, -4) al punkto laŭ la x-akso. Ĉi tiu vektoro havas angulon  . Oni kreas matricon de la orta turnado de Givens:

 

La produto G1A havas nulon en la 3,1-ero:

 

Konsiderante ĉi tiun matricon, oni povas simile formi matricojn de Givens G2 kaj poste G3, kiuj nuligas la sub-diagonalajn erojn 2, 1 kaj 3, 2 respektive, formante triangulan matricon R. Tiam R = G3G2G1A kaj do la orta matrico QT estas formata per produto de ĉiuj matricoj de Givens QT = G3G2G1 kaj R=QTAA=QR estas la QR-malkomponaĵo.

Ligo al determinanto aŭ produto de ajgenojRedakti

Oni povas uzi QR-malkomponaĵon por trovi la absolutan valoron de la determinanto de kvadrata matrico. Supozu ke matrico estas malkomponita kiel A=QR. Tiam

det(A)=det(Q)det(R)

Pro tio ke Q estas unita, |det(Q)|=1. Tial,

 

kie rii estas la elementoj en la ĉefdiagonalo de R.

Plu, ĉar la determinanto egalas al produto de la ajgenoj

 

kie λi estas ajgenoj de A.

Oni povas etendi la pli supre donitajn propraĵojn al ne-kvadrata kompleksa matrico A per anstataŭo de ajgenoj per singularaj valoroj.

Estu QR-malkomponaĵo de ne-kvadrata matrico A:

 

kie O estas nula matrico kaj Q estas unita matrico, Q*Q = I.

De la propraĵoj de singulara valora malkomponaĵo kaj determinanto de matrico

 

kie σi estas singularaj valoroj de A.

Singularaj valoroj de A kaj R estas identaj, kvankam la kompleksaj ajgenoj de ili povas esti malsamaj. Tamen, se A estas kvadrata,

 

Elekto de kondukaj kolumnojRedakti

QR-malkomponaĵo kun elekto de kondukaj kolumnoj enhavas ankaŭ la permutan matricon P:

AP = QRA = QRPT

Elekto de kondukaj kolumnoj estas utila se A estas proksima al havo de ne plena rango, aŭ estas suspektata ĉi tia. Ĝi povas ankaŭ plibonigi nombran akuratecon. P estas kutime elektata tiel, ke la diagonalaj eroj de R estas ne-pligrandiĝantaj:

|r11| ≥ |r22| ≥ ... ≥ |rnn|

Ĉi tio povas esti uzata por nombre trovi rangon de A je pli malgranda komputa kosto ol singulara valora malkomponaĵo.

Vidu ankaŭRedakti

Eksteraj ligilojRedakti