www.wikidata.de-de.nina.az

QR Zerlegung Die oder QR Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Num

QR-Zerlegung

Die QR-Zerlegung oder QR-Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Man bezeichnet damit die Zerlegung einer Matrix in das Produkt

zweier anderer Matrizen, wobei eine orthogonale bzw. unitäre Matrix und eine obere Dreiecksmatrix ist. Die QR-Zerlegung ist ein Spezialfall der Iwasawa-Zerlegung.

Eine solche Zerlegung existiert stets und kann mit verschiedenen Algorithmen berechnet werden. Die bekanntesten davon sind

Das letztere wird üblicherweise in der linearen Algebra benutzt, ist aber in seiner Standardform numerisch instabil. Man kann das Verfahren aber erweitern und numerisch stabilisieren.

Definition Bearbeiten

Jede reelle Matrix , besitzt eine (fast – siehe weiter unten) eindeutige reduzierte QR-Zerlegung

als Produkt einer in den Spalten orthogonalen Matrix und einer oberen Dreiecksmatrix .

Diese Lösung ist erweiterbar zu einer vollständigen QR-Zerlegung

indem man mit weiteren orthogonalen Spalten zu einer quadratischen -Matrix erweitert, und an unten Nullzeilen anfügt, so dass als Matrixprodukt eine -Matrix entsteht:

Die QR-Zerlegung ist eindeutig für und , wenn man die Vorzeichen der Diagonalelemente von vorgibt – üblicherweise wählt man alle positiv.

Anmerkungen: Eine reelle Matrix heißt orthogonal, wenn das Matrixprodukt mit ihrer transponierten Matrix die Einheitsmatrix ergibt, also ist. Im allgemeineren Fall einer komplexen Matrix ist die Matrix eine unitäre Matrix, das heißt, das Matrixprodukt mit ihrer adjungierten Matrix ergibt die Einheitsmatrix , also .

Beispiel Bearbeiten

Für die reelle Matrix ergibt sich die QR-Zerlegung

denn es gilt:

Anwendung Bearbeiten

Die QR-Zerlegung spielt in vielen Verfahren der numerischen Mathematik eine wichtige Rolle, beispielsweise um eine orthogonale oder unitäre Basis zu bestimmen oder um lineare Ausgleichsprobleme zu behandeln. Sie ist integraler Bestandteil des QR-Algorithmus und der Unterraumiteration zur Berechnung von Eigenwerten einer Matrix.

Lösung regulärer oder überbestimmter Gleichungssysteme Bearbeiten

Um die Lösung eines linearen Gleichungssystems mit Matrix von vollem Rang zu bestimmen, sind folgende drei Schritte durchzuführen:

  1. Bestimme eine QR-Zerlegung der Matrix .
  2. Berechne , üblicherweise unter Benutzung der Faktorisierung von aus Schritt 1.
  3. Löse durch Rückwärtseinsetzen.

Für ist dies eine Alternative zur LR-Zerlegung, sie hat den doppelten Aufwand der LR-Zerlegung, ist aber möglicherweise numerisch stabiler.

Im Fall gibt es im Gleichungssystem mehr Gleichungen als Variablen und es liegt ein überbestimmtes Gleichungssystem vor. Hier wird durch Lösung des Ausgleichproblems nach der Methode der kleinsten Quadrate (s. auch Regressionsanalyse) bestimmt:

In diesem Fall ist die Moore-Penrose-Pseudoinverse von und für die berechnete Kleinste-Quadrate-Lösung gilt die Beziehung , die die übliche Darstellung des regulären Falls verallgemeinert.

Lösung unterbestimmter Gleichungssysteme Bearbeiten

Für hat die Matrix einen nichttrivialen Kern. Bei vollem Rang von bilden die Lösungen des Gleichungssystems daher einen affinen Unterraum. Diejenige Lösung mit kleinster Norm liegt im orthogonalen Komplement des Kerns und man bekommt sie mit Hilfe einer QR-Zerlegung von :

  1. Bestimme eine QR-Zerlegung der Matrix .
  2. Löse durch Vorwärtseinsetzen.
  3. Berechne .

Auch hier ist wieder die Moore-Penrose-Pseudoinverse von und für die berechnete Lösung kleinster Norm gilt die Beziehung .

Literatur Bearbeiten

  • Martin Hermann: Numerische Mathematik, Band 2: Analytische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065765-4.
  • Gene H. Golub and Charles F. van Loan: Matrix Computations. 3. Auflage. The Johns Hopkins University Press, Baltimore and London 1996.
  • G. W. Stewart: Matrix Algorithms, Vol. 1: Basic Decompositions. Society for Industrial and Applied Mathematics, Philadelphia 1998.
  • Lloyd N. Trefethen and David Bau, III: Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia 1997.

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die QR Zerlegung oder QR Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Numerik Man bezeichnet damit die Zerlegung einer Matrix A displaystyle A in das Produkt A Q R displaystyle A Q cdot R zweier anderer Matrizen wobei Q displaystyle Q eine orthogonale bzw unitare Matrix und R displaystyle R eine obere Dreiecksmatrix ist Die QR Zerlegung ist ein Spezialfall der Iwasawa Zerlegung Eine solche Zerlegung existiert stets und kann mit verschiedenen Algorithmen berechnet werden Die bekanntesten davon sind Householdertransformationen Givens Rotationen Gram Schmidtsches Orthogonalisierungsverfahren Das letztere wird ublicherweise in der linearen Algebra benutzt ist aber in seiner Standardform numerisch instabil Man kann das Verfahren aber erweitern und numerisch stabilisieren Inhaltsverzeichnis 1 Definition 1 1 Beispiel 2 Anwendung 2 1 Losung regularer oder uberbestimmter Gleichungssysteme 2 2 Losung unterbestimmter Gleichungssysteme 3 Literatur 4 WeblinksDefinition BearbeitenJede reelle Matrix A R m n displaystyle A in mathbb R m times n nbsp m n displaystyle m geq n nbsp besitzt eine fast siehe weiter unten eindeutige reduzierte QR Zerlegung A Q R displaystyle A hat Q cdot hat R nbsp als Produkt einer in den Spalten orthogonalen Matrix Q R m n displaystyle hat Q in mathbb R m times n nbsp und einer oberen Dreiecksmatrix R R n n displaystyle hat R in mathbb R n times n nbsp Diese Losung ist erweiterbar zu einer vollstandigen QR Zerlegung A Q R displaystyle A Q cdot R nbsp indem man Q displaystyle hat Q nbsp mit weiteren orthogonalen Spalten Q displaystyle tilde Q nbsp zu einer quadratischen m m displaystyle m times m nbsp Matrix erweitert und an R displaystyle hat R nbsp unten Nullzeilen anfugt so dass als Matrixprodukt eine m n displaystyle m times n nbsp Matrix entsteht Q R Q Q R 0 Q R displaystyle Q cdot R begin pmatrix hat Q amp tilde Q end pmatrix cdot begin pmatrix hat R 0 end pmatrix hat Q cdot hat R nbsp Die QR Zerlegung ist eindeutig fur m n displaystyle m geq n nbsp und Rang A n displaystyle operatorname Rang A n nbsp wenn man die Vorzeichen der Diagonalelemente von R R displaystyle R hat R nbsp vorgibt ublicherweise wahlt man alle positiv Anmerkungen Eine reelle Matrix Q displaystyle Q nbsp heisst orthogonal wenn das Matrixprodukt mit ihrer transponierten Matrix Q T displaystyle Q T nbsp die Einheitsmatrix I displaystyle I nbsp ergibt also Q T Q I displaystyle Q T Q I nbsp ist Im allgemeineren Fall einer komplexen Matrix A displaystyle A nbsp ist die Matrix Q displaystyle Q nbsp eine unitare Matrix das heisst das Matrixprodukt mit ihrer adjungierten Matrix Q H Q T Q T displaystyle Q H overline Q T overline Q T nbsp ergibt die Einheitsmatrix I displaystyle I nbsp also Q H Q I displaystyle Q H Q I nbsp Beispiel Bearbeiten Fur die reelle Matrix A 12 51 4 6 167 68 4 24 41 displaystyle A begin pmatrix 12 amp 51 amp 4 6 amp 167 amp 68 4 amp 24 amp 41 end pmatrix nbsp ergibt sich die QR Zerlegung Q 6 7 69 175 58 175 3 7 158 175 6 175 2 7 6 35 33 35 displaystyle Q begin pmatrix 6 7 amp 69 175 amp 58 175 3 7 amp 158 175 amp 6 175 2 7 amp 6 35 amp 33 35 end pmatrix nbsp R 14 21 14 0 175 70 0 0 35 displaystyle R begin pmatrix 14 amp 21 amp 14 0 amp 175 amp 70 0 amp 0 amp 35 end pmatrix nbsp denn es gilt Q R 6 7 69 175 58 175 3 7 158 175 6 175 2 7 6 35 33 35 14 21 14 0 175 70 0 0 35 12 51 4 6 167 68 4 24 41 A displaystyle QR begin pmatrix 6 7 amp 69 175 amp 58 175 3 7 amp 158 175 amp 6 175 2 7 amp 6 35 amp 33 35 end pmatrix begin pmatrix 14 amp 21 amp 14 0 amp 175 amp 70 0 amp 0 amp 35 end pmatrix begin pmatrix 12 amp 51 amp 4 6 amp 167 amp 68 4 amp 24 amp 41 end pmatrix A nbsp Anwendung BearbeitenDie QR Zerlegung spielt in vielen Verfahren der numerischen Mathematik eine wichtige Rolle beispielsweise um eine orthogonale oder unitare Basis zu bestimmen oder um lineare Ausgleichsprobleme zu behandeln Sie ist integraler Bestandteil des QR Algorithmus und der Unterraumiteration zur Berechnung von Eigenwerten einer Matrix Losung regularer oder uberbestimmter Gleichungssysteme Bearbeiten Um die Losung x R n displaystyle x in mathbb R n nbsp eines linearen Gleichungssystems A x b displaystyle Ax b nbsp mit Matrix A R m n m n displaystyle A in mathbb R m times n m geq n nbsp von vollem Rang zu bestimmen sind folgende drei Schritte durchzufuhren Bestimme eine QR Zerlegung der Matrix A displaystyle A nbsp Berechne z Q T b R n displaystyle z Q T b in mathbb R n nbsp ublicherweise unter Benutzung der Faktorisierung von Q displaystyle Q nbsp aus Schritt 1 Lose R x z displaystyle Rx z nbsp durch Ruckwartseinsetzen Fur m n displaystyle m n nbsp ist dies eine Alternative zur LR Zerlegung sie hat den doppelten Aufwand der LR Zerlegung ist aber moglicherweise numerisch stabiler Im Fall m gt n displaystyle m gt n nbsp gibt es im Gleichungssystem mehr Gleichungen als Variablen und es liegt ein uberbestimmtes Gleichungssystem vor Hier wird x displaystyle x nbsp durch Losung des Ausgleichproblems nach der Methode der kleinsten Quadrate s auch Regressionsanalyse bestimmt Minimiere A x b 2 j 1 m k 1 n a j k x k b j 2 displaystyle Ax b 2 sum j 1 m left sum k 1 n a jk x k b j right 2 nbsp In diesem Fall ist A R Q T displaystyle A R Q T nbsp die Moore Penrose Pseudoinverse von A displaystyle A nbsp und fur die berechnete Kleinste Quadrate Losung x displaystyle x nbsp gilt die Beziehung x A b displaystyle x A b nbsp die die ubliche Darstellung x A 1 b displaystyle x A 1 b nbsp des regularen Falls m n displaystyle m n nbsp verallgemeinert Losung unterbestimmter Gleichungssysteme Bearbeiten Fur m lt n displaystyle m lt n nbsp hat die Matrix A displaystyle A nbsp einen nichttrivialen Kern Bei vollem Rang von A displaystyle A nbsp bilden die Losungen des Gleichungssystems A x b displaystyle Ax b nbsp daher einen affinen Unterraum Diejenige Losung mit kleinster Norm liegt im orthogonalen Komplement des Kerns und man bekommt sie mit Hilfe einer QR Zerlegung von A T displaystyle A T nbsp Bestimme eine QR Zerlegung der Matrix A T Q R displaystyle A T QR nbsp Lose R T z b R m displaystyle R T z b in mathbb R m nbsp durch Vorwartseinsetzen Berechne x Q z R n displaystyle x Qz in mathbb R n nbsp Auch hier ist wieder A Q R T displaystyle A Q R T nbsp die Moore Penrose Pseudoinverse von A displaystyle A nbsp und fur die berechnete Losung kleinster Norm gilt die Beziehung x A b displaystyle x A b nbsp Literatur BearbeitenMartin Hermann Numerische Mathematik Band 2 Analytische Probleme 4 uberarbeitete und erweiterte Auflage Walter de Gruyter Verlag Berlin und Boston 2020 ISBN 978 3 11 065765 4 Gene H Golub and Charles F van Loan Matrix Computations 3 Auflage The Johns Hopkins University Press Baltimore and London 1996 G W Stewart Matrix Algorithms Vol 1 Basic Decompositions Society for Industrial and Applied Mathematics Philadelphia 1998 Lloyd N Trefethen and David Bau III Numerical Linear Algebra Society for Industrial and Applied Mathematics Philadelphia 1997 Weblinks BearbeitenQR Zerlegungs Rechner Berechnet die QR Zerlegung einer Matrix mittels Householdertransformation LP QR Zerlegung fur lineare Ausgleichsprobleme Georg August Universitat Gottingen taramath Online Tool zur Berechnung der QR Zerlegung reeller Matrizen Abgerufen von https de wikipedia org w index php title QR Zerlegung amp oldid 233131233