Modifizierte Block-Gram-Schmidt Orthogonalisierung

Betreuer/in:            Sabine Le Borne           
Dekanat/Institut:   Elektrotechnik, Informatik, Mathematik / Mathematik (E-10)           

E-Mail:   leborne@tuhh.de

Motivation: Orthogonalsierungsverfahren sind die Grundlage für viele stabile numerische Verfahren. Ein Beispiel ist die Lösung eines linearen Ausgleichsproblems “min ||Ax-b||_2” mit einer Rechtecksmatrix A, die mehr Zeilen als Spalten besitzt. Hier ist der Lösungsansatz über eine Orthogonalisierung von A insbesondere für große A dem Ansatz über die Normalengleichung vorzuziehen.
Eine Menge linear unabhängiger Vektoren lässt sich auf verschiedene Arten orthogonalisieren, z.B. über das Gram-Schmidt Verfahren oder durch Householder Transformationen. Formal erhält man eine sogenannte QR-Zerlegung A=QR mit orthogonaler Matrix Q und oberer Dreiecksmatrix R. Werden Algorithmen zu Orthogonalisierungsverfahren auf dem Rechner unter dem Einfluss von Rundungfehlern ausgeführt, kann die Orthogonalität zunehmend “verloren gehen”. Ziel ist die Entwicklung effizienter Orthogonalisierungsverfahren, die gegenüber Rundungsfehlern möglichst robust sind.

Methoden: In [1] wird ein Zusammenhang zwischen dem modifizierten Gram-Schmidt Verfahren und Householder Transformationen ausgenutzt, um Block-Varianten des modifizierten Gram-Schmidt Verfahrens herzuleiten. Die mathematische Äquivalenz dieser Verfahren kann über algebraische Umformungen gezeigt werden. Die Erkenntnisse über algebraischen Zusammenhänge wiederum können zur Herleitung neuer Varianten genutzt werden.

[1] J.L. Barlow. Block modified Gram-Schmidt algorithms and their analysis.
SIAM J. Matrix Anal. Appl. 40, 1257 – 1290 (2019)

Projektziele und Arbeitspakete:
– Durcharbeiten von [1], §1-§3, Ausarbeiten der fehlenden Zwischenschritte
– Implementierung der in [1] vorgeschlagenen (Block-)Orthogonalisierungsverfahren
– Untersuchung der (Block-)Orthogonalisierungsverfahren auf (Speicher- und Rechen-) Aufwand, sowohl für vollbesetzte als auch für schwachbesetzte Matrizen aus Anwendungen (z.B. Diskretisierungen von partiellen
Differentialgleichungen oder Interpolations-/Least-Squares-Matrizen zur Approximation mit radialen Basisfunktionen)
– Umfangreiche Tests und Dokumentation numerischer Ergebnisse im Hinblick auf den Einfluss von Rundungsfehlern auf die Genauigkeit der Ergebnisse sowie den Rechen- und Speicheraufwand der Algorithmen;

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.