Zum Inhalt springen

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

Aus Wikibooks

Satz (Berechnung einer QR-Zerlegung):

Es sei eine Tabelle gegeben, deren Spalten vollaufspannend sind. Dann hat eine QR-Zerlegung, und die Anzahl Gleitkommaoperationen, die für die Berechnung erforderlich ist, hat als das höchste Monom.

Beweis: Wir zerlegen die Gleichung wie folgt, wobei und etwa gleich viele Spalten haben sollen:

.

Wir kennen hierbei und , und wollen die Tabellen und berechnen; hierbei sollen und superdiagonal und und orthogonal sein. Ausmultiplizieren liefert

und .

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