Mathematik für Faule: Effizientes Rechnen/QR-Zerlegung

Satz (Berechnung einer QR-Zerlegung):

Es sei eine Tabelle $A\in \mathbb {C} ^{n\times m}$ gegeben, deren Spalten vollaufspannend sind. Dann hat $A$ eine QR-Zerlegung, und die Anzahl Gleitkommaoperationen, die für die Berechnung erforderlich ist, hat $2m^{2}n$ als das höchste Monom.

Beweis: Wir zerlegen die Gleichung $A=QR$ wie folgt, wobei $B$ und $C$ etwa gleich viele Spalten haben sollen:

$A=:{\begin{pmatrix}B&C\end{pmatrix}}=\overbrace {\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}} ^{:=Q}\overbrace {\begin{pmatrix}R_{1}&R_{2}\\0&R_{3}\end{pmatrix}} ^{:=R}$.

Wir kennen hierbei $B$ und $C$, und wollen die Tabellen $Q_{1},Q_{2},R_{1},R_{2}$ und $R_{3}$ berechnen; hierbei sollen $R_{1}$ und $R_{3}$ superdiagonal und $Q_{1}$ und $Q_{2}$ orthogonal sein. Ausmultiplizieren liefert

$B=Q_{1}R_{1}$ und $C=Q_{1}R_{2}+Q_{2}R_{3}$.

Dann können $Q_{1}$ und $R_{1}$ rekursiv sofort berechnet werden. Nun betrachten wir den Term $Q_{1}R_{2}$. Aus der Definition der Tabellenmultiplikation folgt, dass alle Spalten dieser Tabelle im von den Spalten von $Q_{1}$ aufgespannten Raum liegen. Selbiges gilt für $Q_{2}R_{3}$ bezüglich $Q_{2}$; der von den Spalten von $Q_{2}$ aufgespannte Raum ist aber zum vorherigen (der von den Spalten von $Q_{1}$ aufgespannten) orthogonal. Daher berechnen wir mit der fehlerrobusten Projektion einfach die Projektion aller Spalten von $B$ auf diesen Raum. Wir erhalten dann $R_{2}=Q_{1}^{*}$ und können rekursiv auch $B-Q_{1}R_{2}$ zerlegen. Nachzählen der Operationen und Anwendung des Rekursionssatzes mit dem Schrumpffaktor $1/2$ liefert die zweite Behauptung. $\Box$