QR-faktorigo

En lineara algebro, QR-malkomponaĵo aŭ QR-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 ejgena algoritmo, la QR-algoritmo.

 Difino 

 Por kvadrata matrico 

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 matrico 

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ĵoj 

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

 Komputado de QR-malkomponaĵo 

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

 Procezo de Gram-Schmidt 

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 = QRkie:





 Ekzemplo 

Estu


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




Tial
 A = QQTA = QR 

 Rilato al RQ-malkomponaĵo 

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 Householder 

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×mAŭ, se A estas kompleksa

 , kie 
 kie  estas la transpono kaj konjugito de xQ 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. Notu, 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 ... Q2Q1Aestas 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



 Ekzemplo 

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 Givens 

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.

 Ekzemplo 

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=QTA aŭ A=QR estas la QR-malkomponaĵo.

 Ligo al determinanto aŭ produto de ejgenoj 

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 ejgenoj



kie λi estas ejgenoj de A.

Oni povas etendi la pli supre donitajn propraĵojn al ne-kvadrata kompleksa matrico Aper anstataŭo de ejgenoj 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 ejgenoj de ili povas esti malsamaj. Tamen, se A estas kvadrata,



 Elekto de kondukaj kolumnoj 

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

 AP = QR aŭ A = QRPTElekto 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ŭ 

 Polusa malkomponaĵo
 Ejgena malkomponaĵo
 Spektra malkomponaĵo
 Matrica malkomponaĵo

 Eksteraj ligiloj 
 .
 Reta matrica kalkulilo  Plenumas QR-malkomponaĵon de matricoj.
 uzanto-manlibro de LAPACK kun detaloj pri kalkulado de la QR-malkomponaĵo
 Detaloj kaj ekzemploj de proceduroj pot kalkuli QR-malkomponaĵon 
 biblioteko de proceduroj ALGLIB

Kategorio:Cifereca lineara algebro
Kategorio:Matrica teorio