Beschreibung
Wir versuchen weiterhin ein Lineares Gleichungssystem zu lösen. Diesmal betrachten wir einen Algorithmus im Spezialfall, dass eine hermitesch, Positiv Definite Matrix ist.
Definition
Erweiterte QR-Zerlegung
Sei . Dann heißt eine erweiterte QR-Zerlegung von genau dann wenn unitär und in Stufenform (Lineare Algebra)
QR-Zerlegung
Sei und der Rang von , Dann heißt eine QR-Zerlegung von genau dann wenn Matrix mit orthonormalen Spalten und in Stufenform (Lineare Algebra)
Eigenschaften
Kondition
Seien , Invertierbare Matrix, Unitäre Matrix. Für die natürliche Matrixnorm und Kondition bezüglich der -Norm auf gilt dann:
\kappa_2(Q) &= 1 \\ \kappa_2(QA) &= \kappa_2(AQ) = \kappa_2(A)\end{align}$$ Q: Spektralkondition einer QR-Zerlegung: A: $\kappa_2(QA) = \kappa_2(A)$ <!--ID: 1673367847009--> ## Konstruktion mit Gram-Schmidt Sei $A$ eine Matrix mit den Spalten $a_i$. Wir wenden das [[Gram-Schmidt-Verfahren|Gram-Schmidt-Verfahren]] auf die Spalten $a_i$ an, um eine Orthogonalbasis $q_i$ zu erhalten. Durch Zusammensetzen Erhalten wir daraus $Q$. Durch Dokumentation der Gram-Schmidt-Schritte erhalten wir $R$. Sei $A = QR$ die erweiterte QR-Zerlegung und $A = \overline{QR}$ die QR-Zerlegung. D.h. $$\bar q_1 = a_1, \bar q_k = a_k - \sum_{i = 0, v_i \neq 0}^{k-1} \frac{\wink{x_k, v_i}}{\|v_i\|^2_2}v_i$$ Durch Weglassen aller $0$-Vektoren erhalten wir die $Q$-Vektoren der normalen QR-Zerlegung $q_1, ..., q_r$. Ist der Rang von $A$ voll, so berechnet $R$ sich nach Wikipedia durch: $$R = \begin{pmatrix} \langle q_1, a_1 \rangle & \langle q_1, a_2 \rangle &... & \langle q_1, a_n \rangle \\ & \langle q_2, a_2 \rangle & ... &\langle q_2, a_n \rangle\\ & & \ddots & \vdots \\ & & & \langle q_n, a_n \rangle \end{pmatrix}$$ *Problem: Sind die $x_k$ "fast" linear abhängig voneinander, so entsteht numerische Instabilität. Wo genau das passiert, kann ich allerdings nicht beurteilen.* Q: Formel für $Q$ für die QR-Zerlegung: A: $\bar q_1 = a_1, \bar q_k = a_k - \sum_{i = 0, v_i \neq 0}^{k-1} \frac{\langle x_k, v_i \rangle}{\|v_i\|^2_2}v_i$ Die $q_k$ errechen sich aus $\bar q_k$ aus Normierung. <!--ID: 1673367847804--> Q: Formel für $R$ für die QR-Zerlegung: A: $$R = \begin{pmatrix} \langle q_1, a_1 \rangle & \langle q_1, a_2 \rangle &... & \langle q_1, a_n \rangle \\ & \langle q_2, a_2 \rangle & ... &\langle q_2, q_n \rangle\\ & & \ddots & \vdots \\ & & & \langle q_n, a_n \rangle \end{pmatrix}$$ <!--ID: 1673367848567--> ## Eindeutigkeit Die QR-Zerlegung ist eindeutig. ## Konstruktion mit Householder-Spiegelungen Dieses Verfahren ist stabiler als Gram-Schmidt aber etwas inenffizienter. $\newcommand{\ges}[1]{\left\{ #1 \right\}}$ $\newcommand{\wink}[1]{\left\langle #1 \right\rangle}$ $\newcommand{\klam}[1]{\left( #1 \right)}$ $\newcommand{\R}{\mathbb R}$ $\newcommand{\inv}[1]{#1 ^{-1}}$