QR-faktorigo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉ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.

Difino[redakti | redakti fonton]

Por kvadrata matrico[redakti | redakti fonton]

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[redakti | redakti fonton]

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:

 A = QR = Q \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
 = \begin{bmatrix} Q_1, Q_2 \end{bmatrix} \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
 = Q_1 R_1

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[redakti | redakti fonton]

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

Komputado de QR-malkomponaĵo[redakti | redakti fonton]

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-Schmidt[redakti | redakti fonton]

Konsideru la procezon de Gram-Schmidt aplikitan al kolumnoj de la matrico A= \begin{bmatrix} \mathbf{a}_1 & \cdots & \mathbf{a}_n \end{bmatrix}, kun ena produto \langle\mathbf{v},\mathbf{w}\rangle = \mathbf{v}^\top \mathbf{w} (aŭ \langle\mathbf{v},\mathbf{w}\rangle = \mathbf{v}^* \mathbf{w} por la kompleksa okazo).

Estu la projekcio:

\mathrm{proj}_{\mathbf{e}}\mathbf{a}
= \frac{\left\langle\mathbf{e},\mathbf{a}\right\rangle}{\left\langle\mathbf{e},\mathbf{e}\right\rangle}\mathbf{e}

tiam


 \mathbf{u}_1 = \mathbf{a}_1,
 \mathbf{e}_1 = {\mathbf{u}_1 \over \|\mathbf{u}_1\|}

 \mathbf{u}_2 = \mathbf{a}_2-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2,
 \mathbf{e}_2 = {\mathbf{u}_2 \over \|\mathbf{u}_2\|}

 \mathbf{u}_3 = \mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3,
 \mathbf{e}_3 = {\mathbf{u}_3 \over \|\mathbf{u}_3\|}
...

 \mathbf{u}_k = \mathbf{a}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k,
 \mathbf{e}_k = {\mathbf{u}_k\over\|\mathbf{u}_k\|}

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

 \mathbf{a}_1 = \langle\mathbf{e}_1,\mathbf{a}_1 \rangle \mathbf{e}_1
  \mathbf{a}_2 = \langle\mathbf{e}_1,\mathbf{a}_2 \rangle \mathbf{e}_1
 + \langle\mathbf{e}_2,\mathbf{a}_2 \rangle \mathbf{e}_2
  \mathbf{a}_3 = \langle\mathbf{e}_1,\mathbf{a}_3 \rangle \mathbf{e}_1
 + \langle\mathbf{e}_2,\mathbf{a}_3 \rangle \mathbf{e}_2
 + \langle\mathbf{e}_3,\mathbf{a}_3 \rangle \mathbf{e}_3
...
  \mathbf{a}_k = \sum_{j=1}^{k} \langle \mathbf{e}_j, \mathbf{a}_k \rangle \mathbf{e}_j

kie \langle\mathbf{e}_i,\mathbf{a}_i \rangle = \|\mathbf{u}_i\|. Ĉi tio povas esti skribita en matrica formo:

A = QR

kie:

Q = \left[ \mathbf{e}_1, \cdots, \mathbf{e}_n\right]
R = \begin{bmatrix}
\langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\
0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\
0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\
\vdots & \vdots & \vdots & \ddots \end{bmatrix}

Ekzemplo[redakti | redakti fonton]

Estu

A = \begin{bmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41
\end{bmatrix}

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


U =
\begin{bmatrix}
\mathbf u_1 & \mathbf u_2 & \mathbf u_3
\end{bmatrix}
=
\begin{bmatrix}
12 & -69 & -58/5 \\
6 & 158 & 6/5 \\
-4 & 30 & -33
\end{bmatrix}

Q =
\begin{bmatrix}
\frac{\mathbf u_1}{\|\mathbf u_1\|} &
\frac{\mathbf u_2}{\|\mathbf u_2\|} &
\frac{\mathbf u_3}{\|\mathbf u_3\|}
\end{bmatrix}
=
\begin{bmatrix}
 6/7 & -69/175 & -58/175 \\
 3/7 & 158/175 & 6/175 \\
 -2/7 & 6/35 & -33/35
\end{bmatrix}

Tial

A = QQTA = QR
 R = Q^{T}A =
\begin{bmatrix}
 14 & 21 & -14 \\
 0 & 175 & -70 \\
 0 & 0 & 35
\end{bmatrix}

Rilato al RQ-malkomponaĵo[redakti | redakti fonton]

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[redakti | redakti fonton]

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

 \alpha = - \mathrm{e}^{\mathrm{i} \arg x_1} \|\mathbf{x}\|

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

Tiam

\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1
\mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|}
Q = I - 2 \mathbf{v}\mathbf{v}^T

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

Q = I - (1+w)\mathbf{v}\mathbf{v}^H, kie w = \mathbf{x}^H\mathbf{v}\mathbf{/}\mathbf{v}^H\mathbf{x}
kie \mathbf{x}^H 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.

Q_1A = \begin{bmatrix}
 \alpha_1&\star&\dots&\star\\
 0 & & & \\
 \vdots & & A' & \\
 0 & & & \end{bmatrix}

Ĉ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:

Q_k = \begin{bmatrix}
 I_{k-1} & 0\\
 0 & Q_k'\end{bmatrix}

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

R = Qt ... Q2Q1A

estas supra triangula matrico. Do kun

 Q = Q_1^T Q_2^T \cdots Q_t^T

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 2(n-k+1)^2
adicio  (n-k+1)^2+(n-k+1)(n-k)+2
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

\frac{2}{3}n^3+n^2+\frac{1}{3}n-2=O(n^3)

Ekzemplo[redakti | redakti fonton]

Estu same kiel supre

A = \begin{bmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41
\end{bmatrix}

Unue, oni bezonas trovi reflekton kiu konvertas la unuan kolumnon de matrico A, vektoron \mathbf{a}_1 = \begin{bmatrix}12 \\ 6 \\ -4 \end{bmatrix}, al \|\mathbf{a}_1\| \mathrm{e}_1 = \begin{bmatrix}14 \\ 0 \\ 0 \end{bmatrix}

Do

\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1

kaj

\mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|}

Ĉi tie,

α=14 kaj \mathbf{x} = \mathbf{a}_1 = \begin{bmatrix}12 \\ 6 \\ -4 \end{bmatrix}

Pro tio

\mathbf{u} = \begin{bmatrix} -2 \\ 6 \\ -4 \end{bmatrix}=2\begin{bmatrix} -1 \\ 3 \\ -2 \end{bmatrix} kaj \mathbf{v} = {1 \over \sqrt{14}}\begin{bmatrix} -1, 3 \\ -2 \end{bmatrix}, kaj tiam
Q_1 = I - {2 \over \sqrt{14} \sqrt{14}} \begin{bmatrix} -1 \\ 3 \\ -2 \end{bmatrix}\begin{bmatrix} -1 & 3 & -2 \end{bmatrix}
 = I - {1 \over 7}\begin{bmatrix}
1 & -3 & 2 \\
-3 & 9 & -6 \\
2 & -6 & 4
\end{bmatrix}
 = \begin{bmatrix}
6/7 & 3/7 & -2/7 \\
3/7 &-2/7 & 6/7 \\
-2/7 & 6/7 & 3/7 \\
\end{bmatrix}

Tiam

Q_1A = \begin{bmatrix}
14 & 21 & -14 \\
0 & -49 & -14 \\
0 & 168 & -77 \end{bmatrix}

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

A' = M_{11} = \begin{bmatrix}
-49 & -14 \\
168 & -77 \end{bmatrix}

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

Q_2 = \begin{bmatrix}
1 & 0 & 0 \\
0 & -7/25 & 24/25 \\
0 & 24/25 & 7/25 \end{bmatrix}

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

Nun

Q=Q_1^T Q_2^T=\begin{bmatrix}
6/7 & -69/175 & 58/175\\
3/7 & 158/175 & -6/175 \\
-2/7 & 6/35 & 33/35
\end{bmatrix}
R=Q_2Q_1A=Q^T A=\begin{bmatrix}
14 & 21 & -14 \\
0 & 175 & -70 \\
0 & 0 & -35
\end{bmatrix}

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

Uzo de turnadoj de Givens[redakti | redakti fonton]

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[redakti | redakti fonton]

Estu la same kiel pli supre

A = \begin{bmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41
\end{bmatrix}

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 \theta = \arctan\left({-4 \over 6}\right). Oni kreas matricon de la orta turnado de Givens:

G_1 = \begin{bmatrix}
1 & 0 & 0 \\
0 & \cos(\theta) & \sin(\theta) \\
0 & -\sin(\theta) & \cos(\theta)
\end{bmatrix} \approx \begin{bmatrix}
1 & 0 & 0 \\
0 & 0,83205 & -0,55470 \\
0 & 0,55470 & 0,83205
\end{bmatrix}

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

G_1A \approx \begin{bmatrix}
12 & -51 & 4 \\
7,21110 & 125,6396 & -33,83671 \\
0 & 112,6041 & -71,83368
\end{bmatrix}

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 ajgenoj[redakti | redakti fonton]

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,

|\det(A)|=|\det(R)|=\Big|\prod_{i}r_{ii}\Big|

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

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

\Big|\prod_{i} r_{ii}\Big|=\Big|\prod_{i} \lambda_{i}\Big|

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:

A = Q \begin{bmatrix}R \\ O \end{bmatrix}

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

\Big|\prod_{i} r_{ii}\Big| = \prod_{i} \sigma_{i}

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,

 {\prod_{i} \sigma_{i}} = \Big|{\prod_{i} \lambda_{i}}\Big|

Elekto de kondukaj kolumnoj[redakti | redakti fonton]

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 | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]