Lösen von Regularisierten totalen Ausgleichsproblemen mit Hilfe von Eigenwertproblemen

In the first part of the thesis we review basic knowledge of regularized least squares problems and present a significant acceleration of an existing method for the solution of trust-region problems. In the second part we present the basic theory of total least squares (TLS) problems and give an overview of possible extensions. Regularization of TLS problems by truncation and bidiagonalization approaches are briefly covered. Several approaches for solving the Tikhonov TLS problem based on Newton’s method are mentioned, which lead to a converging sequence of linear systems. The emphasis of the thesis is on quadratically constrained TLS (RTLS) problems. Two different iterative concepts for the solution of the first-order condition are analyzed. The first iteration results in a sequence of quadratic problems while the second concept leads to a sequence of linear eigenvalue problems. For a fixed point iteration based on quadratic eigenvalue problems, i.e. the RTLSQEP method, the global convergence to the RTLS solution is proven. With the characterization of the rightmost eigenvalue of the QEPs the RTLS solution can be described via a generalized trust-region problem. The second concept has been studied in detail as well, i.e. the RTLSEVP method. To ensure convergence it was necessary to generalize the function g. The properties of this function have been heavily analyzed, which lead to a deeper understanding of the RTLS solution: It can also be characterized via the solution of a TLS problem. The RTLSQEP and RTLSEVP algorithm for solving the RTLS problem are shown to be very efficient when combined with iterative projection methods in the inner loop. Since a sequence of convergent problems has to be solved it turns out that the Nonlinear Arnoldi method is the method of choice, because it is able to recycle most of the information during the iterative process. The computational complexity of the proposed approaches is kept at the order of matrix-vector multiplications. We give a detailed description of an efficient implementation of the different parts of the algorithms. Two efficient algorithms for evaluating the L-curve at discrete points are presented. Since setting up the L-curve requires solving a sequence of RTLS problems the advantage of the Nonlinear Arnoldi method is even more apparent: Recycling the search space, not only within one RTLS problem but throughout the whole sequence.Im ersten Teil der Arbeit wird grundlegendes Wissen zur Regularisierung von linearen Ausgleichsproblemen rekapituliert. Weiterhin wird eine bestehende Methode zum Lösen von Trust-Region Problemen erheblich verbessert. Im zweiten Teil wird zunächst die Theorie der totalen Ausgleichsprobleme (TLS) aufgearbeitet und es wird ein Überblick über mögliche Erweiterungen gegeben. Danach wird die Regularisierung von TLS Problemen durch Abschneiden der SVD und mit Hilfe von Krylov-Methoden erörtert. Einige Methoden zum Lösen des Tikhonov TLS Problems werden diskutiert. Der Schwerpunkt der Dissertation sind quadratisch restringierte TLS (RTLS) Probleme. Es werden zwei iterative Verfahren zur Lösung der Bedingungen 1. Ordnung tiefgehend analysiert. Das erste Verfahren führt auf eine Folge von quadratischen Problemen und das zweite auf eine Folge von linearen Eigenwertaufgaben. Für die RTLSQEP Methode, eine Fixpunkt-Iteration basierend auf quadratischen Eigenwertaufgaben, wurde globale Konvergenz gegen die RTLS Lösung gezeigt. Durch die Charakterisierung der größten reellen Eigenwerte der QEPs kann die Lösung durch ein generalisiertes Trust-Region Problem beschrieben werden. Das zweite Verfahren ist die RTLSEVP Methode. Um Konvergenz zu gewährleisten wird eine Hilfsfunktion g eingeführt. Diese Funktion wurde detailliert untersucht, was zu einem weiteren Zusammenhang führt: die RTLS Lösung kann auch als spezielles TLS Problem charakterisiert werden. Die Algorithmen RTLSQEP und RTLSEVP zum Lösen von RTLS Problemen sind sehr effizient wenn sie mit iterativen Projektionsverfahren in der inneren Schleife kombiniert werden. Da eine Folge von konvergierenden Eigenwertproblemen gelöst werden muss, spielt der Aspekt der Wiederverwendung bereits gesammelter Information eine wichtige Rolle. Hierbei ist der Nichtlineare Arnoldi Algorithmus die Methode der Wahl, sie ermöglicht das Recycling des aufgebauten Suchraumes innerhalb des ganzen iterativen Prozesses. Die Komplexität der entwickelten Algorithmen ist von der Ordnung von Matrix-Vektor Multiplikationen, also auch geeignet für sehr große Probleme. Es wird eine effizienten Implementierung von allen Teilen der Algorithmen beschrieben und an Beispielen demonstriert. Abschließend werden zwei Methoden zum Erstellen einer RTLS L-Kurve vorgestellt mit dessen Hilfe der Regularisierungsparameter bestimmt werden kann. Das Aufstellen der L-Kurve erfordert das Lösen einer Folge von RTLS Problemen. Dabei wird der Vorteil des Nichtlinearen Arnoldis noch deutlicher: Die Wiederverwendung des Suchraumes, nicht nur innerhalb eines RTLS Problems sondern während der ganzen Folge