In der geradlinigen Algebra ist eine QR Zergliederung (hat auch einen QR factorization genannt), einer Matrix eine Zergliederung einer Matrix in ein Produkt A=QR einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R. QR Zergliederung wird häufig verwendet, um das geradlinige kleinstes Quadratproblem zu lösen, und ist die Basis für einen besonderen eigenvalue Algorithmus, den QR Algorithmus.

Wenn A linear unabhängige Säulen hat (sagen Sie n Säulen), dann bilden die ersten n Säulen von Q eine orthonormale Basis für den Spaltenraum von A. Mehr spezifisch bilden die ersten k Säulen von Q eine orthonormale Basis für die Spanne der ersten k Säulen für irgendwelchen 1kn. Die Tatsache, dass jede Spalte k Eines einzigen von den ersten k Säulen von Q abhängt, ist für die Dreiecksform von R verantwortlich.

Definitionen

Quadratmatrix

Jede echte Quadratmatrix A kann als zersetzt werden

:

wo Q eine orthogonale Matrix ist (seine Säulen sind orthogonale Einheitsvektoren, die QQ = I bedeuten), und R ist eine obere Dreiecksmatrix (auch genannt richtige Dreiecksmatrix). Das verallgemeinert zu einer komplizierten Quadratmatrix A und einer einheitlichen Matrix Q. Wenn A invertible ist, dann ist der factorization einzigartig, wenn wir verlangen, dass die diagonalen Elemente von R positiv sind.

Rechteckige Matrix

Mehr allgemein können wir Faktor ein Komplex m×n Matrix A, mit der M  n, als das Produkt m×m einheitliche Matrix Q und m×n obere Dreiecksmatrix R. Als der Boden (m−n) Reihen m×n besteht obere Dreiecksmatrix völlig aus zeroes, es ist häufig für die Teilung R, oder sowohl R als auch Q nützlich:

:

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,

</Mathematik>

wo R eine n×n obere Dreiecksmatrix ist, ist Q m×n, Q ist m× (m&minus;n), und Q und Q beide haben orthogonale Säulen.

nennen Sie QR den dünnen QR factorization von A; Trefethen und Bau nennen das den reduzierten QR factorization.

Wenn A von der vollen Reihe n ist und wir verlangen, dass die diagonalen Elemente von R dann R positiv sind und Q einzigartig sind, aber in General Q ist nicht. R ist dann dem oberen Dreiecksfaktor der Zergliederung von Cholesky gleich (= AA, wenn A echt ist).

QL, RQ und LQ Zergliederungen

Analog können wir QL, RQ und LQ Zergliederungen mit L definieren eine niedrigere Dreiecksmatrix zu sein.

Die Computerwissenschaft der QR Zergliederung

Es gibt mehrere Methoden, für wirklich die QR Zergliederung, solcher als mittels des Prozesses des Gramms-Schmidt, der Wohnungsinhaber-Transformationen oder der Folgen von Givens zu schätzen. Jeder hat mehrere Vorteile und Nachteile.

Das Verwenden des Prozesses des Gramms-Schmidt

Denken Sie, dass der auf die Säulen der vollen Säule angewandte Prozess des Gramms-Schmidt Matrix, mit dem Skalarprodukt (oder für den komplizierten Fall) aufreiht.

Definieren Sie den Vorsprung:

:

\frac {\\left\langle\mathbf {e}, \mathbf {ein }\\right\rangle} {\\left\langle\mathbf {e}, \mathbf {e }\\right\rangle }\\mathbf {e }\

</Mathematik>

dann:

:

\begin {richten }\aus

\mathbf {u} _1 &= \mathbf {ein} _1,

& \mathbf {e} _1 &= {\\mathbf {u} _1 \over \| \mathbf {u} _1 \|} \\

\mathbf {u} _2 &= \mathbf {ein} _2-\mathrm {proj} _ {\\mathbf {e} _1 }\\, \mathbf {ein} _2,

& \mathbf {e} _2 &= {\\mathbf {u} _2 \over \| \mathbf {u} _2 \|} \\

\mathbf {u} _3 &= \mathbf {ein} _3-\mathrm {proj} _ {\\mathbf {e} _1 }\\, \mathbf {ein} _3-\mathrm {proj} _ {\\mathbf {e} _2 }\\, \mathbf {ein} _3,

& \mathbf {e} _3 &= {\\mathbf {u} _3 \over \| \mathbf {u} _3 \|} \\

& \vdots && \vdots \\

\mathbf {u} _k &= \mathbf {ein} _k-\sum_ {j=1} ^ {k-1 }\\mathrm {proj} _ {\\mathbf {e} _j }\\, \mathbf {ein} _k,

&\\mathbf {e} _k &= {\\mathbf {u} _k\over \|\mathbf {u} _k \| }\

\end {richten }\aus

</Mathematik>

Wir ordnen dann die Gleichungen oben um, so dass die s links mit der Tatsache sind, die Einheitsvektoren sind:

:\begin {richten }\aus

\mathbf {ein} _1 &= \langle\mathbf {e} _1, \mathbf _1 \rangle \mathbf {e} _1 \\

\mathbf {ein} _2 &= \langle\mathbf {e} _1, \mathbf _2 \rangle \mathbf {e} _1

+ \langle\mathbf {e} _2, \mathbf _2 \rangle \mathbf {e} _2 \\

\mathbf {ein} _3 &= \langle\mathbf {e} _1, \mathbf _3 \rangle \mathbf {e} _1

+ \langle\mathbf {e} _2, \mathbf _3 \rangle \mathbf {e} _2

+ \langle\mathbf {e} _3, \mathbf _3 \rangle \mathbf {e} _3 \\

&\\vdots \\

\mathbf {ein} _k &= \sum_ {j=1} ^ {k} \langle \mathbf {e} _j, \mathbf {ein} _k \rangle \mathbf {e} _j

\end {richten }\aus</Mathematik>

wo. Das kann in der Matrixform geschrieben werden:

:

wo:

:

R = \begin {pmatrix}

\langle\mathbf {e} _1, \mathbf {ein} _1\rangle & \langle\mathbf {e} _1, \mathbf {ein} _2\rangle & \langle\mathbf {e} _1, \mathbf {ein} _3\rangle & \ldots \\

0 & \langle\mathbf {e} _2, \mathbf {ein} _2\rangle & \langle\mathbf {e} _2, \mathbf {ein} _3\rangle & \ldots \\

0 & 0 & \langle\mathbf {e} _3, \mathbf {ein} _3\rangle & \ldots \\

\vdots & \vdots & \vdots & \ddots \end {pmatrix}. </Mathematik>

Beispiel

Denken Sie die Zergliederung von

:

\begin {pmatrix }\

12 &-51 & 4 \\

6 & 167 &-68 \\

- 4 & 24 &-41

\end {pmatrix }\

. </Mathematik>

Rufen Sie zurück, dass eine orthogonale Matrix das Eigentum hat

:

\begin {Matrix-}\

Q^ {T }\\, Q = ICH.

\end {Matrix-}\

</Mathematik>

Dann können wir mittels des Gramms-Schmidt wie folgt rechnen:

:

U =

\begin {pmatrix }\

\mathbf u_1 & \mathbf u_2 & \mathbf u_3

\end {pmatrix }\\begin {pmatrix }\

12 &-69 &-58/5 \\

6 & 158 & 6/5 \\

- 4 & 30 &-33

\end {pmatrix};

</Mathematik>:

Q =

\begin {pmatrix }\

\frac {\\mathbf u_1} {\\| \mathbf u_1 \|} &

\frac {\\mathbf u_2} {\\| \mathbf u_2 \|} &

\frac {\\mathbf u_3} {\\| \mathbf u_3 \| }\

\end {pmatrix }\\begin {pmatrix }\

6/7 &-69/175 &-58/175 \\

3/7 & 158/175 & 6/175 \\

- 2/7 & 6/35 &-33/35

\end {pmatrix}.

</Mathematik>

So haben wir

: \begin {Matrix-}\

Q^ {T} = Q^ {T} Q \, R = R;

\end {Matrix-}\</Mathematik>: \begin {Matrix-}\

R = Q^ {T} =

\end {Matrix-}\\begin {pmatrix }\

14 & 21 &-14 \\

0 & 175 &-70 \\

0 & 0 & 35

\end {pmatrix}.</Mathematik>

Beziehung zur RQ Zergliederung

Die RQ Zergliederung gestaltet eine Matrix ins Produkt einer oberen Dreiecksmatrix R (auch bekannt als mit dem Recht dreieckig) und einer orthogonalen Matrix Q um. Der einzige Unterschied zur QR Zergliederung ist die Ordnung dieser matrices.

QR Zergliederung ist Gramm-Schmidt orthogonalization von Säulen von A, der aus der ersten Säule angefangen ist.

RQ Zergliederung ist Gramm-Schmidt orthogonalization von Reihen von A, der von der letzten Reihe angefangen ist.

Das Verwenden des Wohnungsinhaber-Nachdenkens

Ein Wohnungsinhaber-Nachdenken (oder Wohnungsinhaber-Transformation) ist eine Transformation, die einen Vektoren nimmt und es über ein Flugzeug oder Hyperflugzeug widerspiegelt. Wir können diese Operation verwenden, um den QR factorization einer m-by-n Matrix mit der M  n zu berechnen.

Q kann verwendet werden, um einen Vektoren auf solche Art und Weise zu widerspiegeln, dass alle Koordinaten, aber man verschwindet.

Lassen Sie, eine willkürliche echte M dimensionaler Spaltenvektor von solchen dass || = | α | für einen Skalar α zu sein. Wenn der Algorithmus mit der Fließkommaarithmetik durchgeführt wird, dann sollte α das entgegengesetzte Zeichen als die k-th Koordinate dessen bekommen, wo die Türangel-Koordinate sein soll, nach der alle Einträge 0 in der oberen Enddreiecksform von MatrixA sind, um Verlust der Bedeutung zu vermeiden. Im komplizierten Fall, Satz

:

und Ersatz-Umstellung durch die verbundene Umstellung im Aufbau von Q unten.

Dann, wo der Vektor (1,0..., 0), || ist · || ist die Euklidische Norm und ist eine M-für-M-Identitätsmatrix, setzen Sie

:::

Oder, wenn komplizierter ist

: wo

: wo das verbundene ist, stellen (transjugate) von um

ist eine M-für-M-Wohnungsinhaber-Matrix und

:

Das kann verwendet werden, um eine m-by-n Matrix in die obere Dreiecksform allmählich umzugestalten. Erstens multiplizieren wir mit der Wohnungsinhaber-Matrix Q wir herrschen vor, wenn wir die erste Matrixsäule für x wählen. Das läuft auf einen Matrix-QA mit Nullen in der linken Säule (abgesehen von der ersten Reihe) hinaus.

:

\alpha_1&\star&\dots&\star \\

0 & & & \\

\vdots & &' & \\

0 & & & \end {bmatrix} </Mathematik>

Das kann für A&prime wiederholt werden; (erhalten bei QA durch das Löschen der ersten Reihe und der ersten Säule), auf eine Wohnungsinhaber-Matrix Q&prime hinauslaufend;. bemerken Sie das Q&prime; ist kleiner als Q. Da wir wollen, dass es wirklich auf QA statt A&prime funktioniert; wir müssen es zum verlassenen oberen ausbreiten, 1, oder im Allgemeinen ausfüllend:

:

I_ {k-1} & 0 \\

0 & Q_k '\end {pmatrix}. </Mathematik>

Nach Wiederholungen dieses Prozesses,

:

ist eine obere Dreiecksmatrix. Also, mit

:

ist eine QR Zergliederung dessen.

Diese Methode hat größere numerische Stabilität als die Methode des Gramms-Schmidt oben.

Der folgende Tisch gibt die Zahl von Operationen im k-th Schritt der QR-Zergliederung durch die Wohnungsinhaber-Transformation, eine Quadratmatrix mit der Größe n annehmend.

Diese Zahlen über die Schritte (für eine Quadratmatrix der Größe n) summierend, wird die Kompliziertheit des Algorithmus (in Bezug auf Punkt-Multiplikationen schwimmen zu lassen), durch gegeben

:

Beispiel

Lassen Sie uns die Zergliederung von berechnen

: 12 &-51 & 4 \\6 & 167 &-68 \\

- 4 & 24 &-41 \end {pmatrix}. </Mathematik>

Erstens müssen wir ein Nachdenken finden, das die erste Säule der Matrix A, Vektor zu umgestaltet

Jetzt,

:

und

:

Hier,

: und

Deshalb

: und, und dann

::

1 &-3 & 2 \\

- 3 & 9 &-6 \\

2 &-6 & 4

\end {pmatrix} </Mathematik>

:

6/7 & 3/7 &-2/7 \\

3/7 &-2/7 & 6/7 \\

- 2/7 & 6/7 & 3/7 \\

\end {pmatrix}. </Mathematik>

Beobachten Sie jetzt:

:

14 & 21 &-14 \\

0 &-49 &-14 \\

0 & 168 &-77 \end {pmatrix}, </Mathematik>

so haben wir bereits fast eine Dreiecksmatrix. Wir brauchen nur zur Null (3, 2) Zugang.

Nehmen Sie (1, 1) gering, und dann wenden Sie den Prozess wieder auf an

:

- 49 &-14 \\

168 &-77 \end {pmatrix}. </Mathematik>

Durch dieselbe Methode wie oben erhalten wir die Matrix der Wohnungsinhaber-Transformation

:

1 & 0 & 0 \\

0 &-7/25 & 24/25 \\

0 & 24/25 & 7/25 \end {pmatrix} </Mathematik>

nach dem Durchführen einer direkten Summe mit 1, um sich zu überzeugen, arbeitet der nächste Schritt im Prozess richtig.

Jetzt finden wir

:

6/7 &-69/175 & 58/175 \\

3/7 & 158/175 &-6/175 \\

- 2/7 & 6/35 & 33/35 \end {pmatrix} </Mathematik>

Dann

:

- 0.8571 & 0.3110 &-0.4106 \\

- 0.4286 &-0.8728 & 0.2335 \\

- 0.2857 & 0.3761 & 0.8814 \end {pmatrix} </Mathematik>

:

- 14 &-8.4286 &-2.0000 \\

0 &-187.1976 &-35.1241 \\

0 & 0 &-32.1761

\end {pmatrix}. </Mathematik>

Die Matrix Q ist orthogonal, und R ist dreieckig ober, so = ist QR die erforderliche QR-Zergliederung.

Das Verwenden Givens Folgen

QR Zergliederungen können auch mit einer Reihe von Folgen von Givens geschätzt werden. Jede Folge Nullen ein Element in der Subdiagonale der Matrix, die R Matrix bildend. Die Verkettung aller Folgen von Givens bildet die orthogonale Q Matrix.

In der Praxis werden Folgen von Givens durch das Gebäude einer ganzen Matrix und das Tun einer Matrixmultiplikation nicht wirklich durchgeführt. Ein Givens Folge-Verfahren wird stattdessen verwendet, der die Entsprechung von der spärlichen Matrixmultiplikation von Givens ohne die Extraarbeit tut, die spärlichen Elemente zu behandeln. Das Givens Folge-Verfahren ist in Situationen nützlich, wo nur relativ wenige von diagonalen Elementen zeroed sein müssen, und leichter parallelized sind als Wohnungsinhaber-Transformationen.

Beispiel

Lassen Sie uns die Zergliederung von berechnen: 12 &-51 & 4 \\6 & 167 &-68 \\- 4 & 24 &-41 \end {pmatrix}. </Mathematik>

Erstens müssen wir eine Folge-Matrix bilden, die Null das tiefste linke Element wird. Wir bilden diese Matrix mit der Folge-Methode von Givens, und nennen die Matrix. Wir werden zuerst den Vektoren rotieren lassen, um entlang der X Achse hinzuweisen. Dieser Vektor hat einen Winkel. Wir schaffen die orthogonale Folge-Matrix von Givens:

:1 & 0 & 0 \\

0 & \cos (\theta) &-\sin (\theta) \\

0 & \sin (\theta) & \cos (\theta)

\end {pmatrix} </Mathematik>:1 & 0 & 0 \\

0 & 0.83205 &-0.55470 \\

0 & 0.55470 & 0.83205

\end {pmatrix} </Mathematik>

Und das Ergebnis dessen hat jetzt eine Null im Element.

:12 &-51 & 4 \\

7.21110 & 125.6396 &-33.83671 \\

0 & 112.6041 &-71.83368

\end {pmatrix} </Mathematik>

Wir können Givens matrices ähnlich bilden und, der Null die subdiagonalen Elemente wird und, eine Dreiecksmatrix bildend. Die orthogonale Matrix wird von der Verkettung ganzen Givens matrices gebildet. So haben wir

G_3G_2G_1A = Q^TA = R </Mathematik>, und die QR Zergliederung ist.

Verbindung zu einer Determinante oder einem Produkt von eigenvalues

Wir können QR Zergliederung verwenden, um den absoluten Wert der Determinante einer Quadratmatrix zu finden. Nehmen Sie an, dass eine Matrix als zersetzt wird. Dann haben wir

:

Da Q einheitlich ist. So,

:

wo die Einträge auf der Diagonale von R sind.

Außerdem, weil die Determinante dem Produkt des eigenvalues gleichkommt, haben wir

:

wo eigenvalues dessen sind.

Wir können die obengenannten Eigenschaften zur komplizierten Nichtquadratmatrix erweitern

durch das Einführen der Definition der QR-Zergliederung für die komplizierte Nichtquadratmatrix

und das Ersetzen eigenvalues mit einzigartigen Werten.

Nehmen Sie eine QR Zergliederung für eine Nichtquadratmatrix A an:

:

wo eine Nullmatrix ist und eine einheitliche Matrix ist.

Von den Eigenschaften von SVD und der Determinante der Matrix haben wir

:

wo einzigartige Werte dessen sind.

Bemerken Sie, dass die einzigartigen Werte dessen und identisch sind, obwohl der Komplex eigenvalues ihrer verschieden sein kann.

Jedoch, wenn A quadratisch ist, hält er das

:

{\\prod_ {ich} \sigma_ {ich}} = \Big | {\\prod_ {ich} \lambda_ {ich} }\\Groß |.

</Mathematik>

Schließlich QR Zergliederung kann effizient verwendet werden, um ein Produkt von eigenvalues oder einzigartige Werte der Matrix zu berechnen.

Spaltenpivotisierung

Die QR Zergliederung mit der Spaltenpivotisierung führt eine Versetzungsmatrix P ein:

:

Spaltenpivotisierung ist nützlich, wenn A (fast) Reihe unzulänglich ist, oder verdächtigt wird, so zu sein. Es kann auch numerische Genauigkeit verbessern. P wird gewöhnlich gewählt, so dass die diagonalen Elemente von R nichtzunehmen:

. Das kann verwendet werden, um die (numerische) Reihe an niedrigeren rechenbetonten Kosten zu finden als eine einzigartige Wertzergliederung, die Basis von QR so genannten Reihe offenbarenden Algorithmen bildend.

Das Verwenden für die Lösung geradliniger umgekehrter Probleme

Im Vergleich zum direkten Matrixgegenteil sind umgekehrte Lösungen mit der QR Zergliederung, wie gezeigt, durch ihre verminderten Bedingungsanzahlen [Parker, Geophysikalische Umgekehrte Theorie, Ch1.13] mehr numerisch stabil.

Um zu beheben, das underdetermined geradlinige Problem, wo die Matrix A Dimensionen zuerst hat, finden Sie den QR factorization vom Umstellen von A:, wo Q eine orthogonale Matrix ist (d. h.). und R hat eine spezielle Form:. Hier ist eine richtige Quadratdreiecksmatrix, und die Nullmatrix hat Dimension. Nach einer Algebra kann es gezeigt werden, dass die Lösung des umgekehrten Problems als ausgedrückt werden kann:

x = Q

\begin {bmatrix }\

(R_1^T) ^ {-1} b \\

0

\end {bmatrix}

</Mathematik>

wo durch die Beseitigung von Gaussian gefunden wird.

Um eine Lösung von, zu finden das überentschlossene Problem, das die Norm zuerst minimiert, finden Sie den QR factorization von A:. Die Lösung kann dann als ausgedrückt werden, wo und dasselbe wie zuvor sind, aber ist jetzt eine Vorsprung-Matrix, die einen Vektoren in darin kartografisch darstellt.

Siehe auch

• Polare Zergliederung
• Zergliederung von Eigenvalue
• Geisterhafte Zergliederung
• Matrixzergliederung
• Produkt von Zappa-Szép

.

• . Abschnitt 2.8.

.

Links

• Online-Matrixrechenmaschine Führt QR Zergliederung von matrices Durch.
• LAPACK Benutzerhandbuch gibt Details von Unterprogrammen, um die QR Zergliederung zu berechnen
• Benutzerhandbuch von Mathematica gibt Details und Beispiele von Routinen, um QR Zergliederung zu berechnen
• ALGLIB schließt einen teilweisen Hafen des LAPACK zu C ++, C#, Delphi usw. ein.
• Eigen:: QR Schließt C ++ Durchführung der QR Zergliederung Ein.
• Darin enthält eine offene Quelldurchführung der QR Zergliederung in C ++.