Preconditioned Newton methods for ill-posed problems
Vorkonditionierte Newton-Verfahren für schlecht gestellte Probleme
von Stefan Langer
Datum der mündl. Prüfung:2007-06-21
Erschienen:2007-09-05
Betreuer:Prof. Dr. Thorsten Hohage
Gutachter:Prof. Dr. Thorsten Hohage
Gutachter:Prof. Dr. Rainer Kreß
Dateien
Name:langer.pdf
Size:2.56Mb
Format:PDF
Description:Dissertation
Zusammenfassung
Englisch
We consider preconditioned regularized Newton methods tailored to the efficient solution of nonlinear large-scale exponentially ill-posed problems.In the first part of this thesis we investigate convergence and convergence rates of the iteratively regularized Gauss-Newton method under general source conditions both for an a-priori stopping rule and the discrepancy principle. The source condition determines the smoothness of the true solution of the given problem in an abstract setting. Dealing with large-scale ill-posed problems it is in general not realistic to assume that the regularized Newton equations can be solved exactly in each Newton step. Therefore, our convergence analysis includes the practically relevant case that the regularized Newton equations are solved only approximately and the Newton updates are computed by using these approximations.In a second part of this thesis we analyze the complexity of the iteratively regularized Gauss-Newton method assuming that the regularized Newton equations are solved by the conjugate gradient method. This analysis includes both mildly and severely ill-posed problems. As a measure of the complexity we count the number of operator evaluations of the Fréchet derivative and its adjoint at some given vectors. Following a common practice for linear ill-posed problems, we express the total complexity of the iteratively regularized Gauss-Newton method in terms of the noise level of the given data.To reduce the total complexity of these regularized Newton methods we consider spectral preconditioners to accelerate the convergence speed of the inner conjugate gradient iterations. We extend our complexity analysis to these preconditioned regularized Newton methods. This investigation gives us the possibility to compare the total complexity of non preconditioned regularized Newton methods and preconditioned ones. In particular we show the superiority of the latter ones in the case of exponentially ill-posed problems.Finally, in a third part we discuss the implementation of preconditioned iteratively regularized Gauss-Newton methods exploiting the close connection of the conjugate gradient method and Lanczos" method as well as the fast decay of the eigenvalues corresponding to the linearized operators in the regularized Newton equations. More precisely, we determine by Lanczos" method approximations to some of the extremal eigenvalues. These are used to construct spectral preconditioners for the following Newton steps. Developing updating techniques to keep the preconditioner efficient while performing Newton"s method the total complexity can be significantly reduced compared to the non preconditioned iteratively regularized Gauss-Newton method. Finally, we illustrate in numerical examples from inverse scattering theory the efficiency of the preconditioned regularized Newton methods compared to other regularized Newton methods.Weitere Sprachen
Wir betrachten vokonditionierte, regularisierte Newton Verfahren, die insbesondere zur effizienten Lösung nichtlinearer, schlecht gestellter Probleme geeignet sind.Im ersten Teil der Arbeit untersuchen wir das iterativ regularisierte Gauß-Newton Verfahren unter allgemeinen Quellbedingungen auf Konvergenz und Konvergenzraten für sowohl eine a-priori Abbruchbedingung als auch eine a-posteriori Abbruchbedingung. Die Quellbedingung bestimmt hierbei die Glätte der wahren Lösung des gegebenen Problems in einer abstrakten Formulierung. Unser besonderes Interesse liegt auf großen, schlecht gestellten Problemen, für die die regularisierten Newton Gleichungen im Allgemeinen nicht mehr exakt gelöst werden können. Daher umfaßt unsere Konvergenzanalysis den Fall, in dem die regularisierten Newton Gleichungen nur approximativ gelöst werden und die Iterierten des Newton Verfahrens mit diesen Approximationen berechnet werden.Im zweiten Teil der Arbeit analysieren wir den Aufwand des iterativ regularisierten Gauß-Newton Verfahrens unter der Voraussetzung, dass die regularisierten Newton Gleichungen durch das Verfahren der konjugierten Gradienten gelöst werden. Als Maß für den Aufwand dient hierbei die Anzahl der Operatorauswertungen der Fréchet Ableitung und ihrer Adjungierten angewendet auf Vektoren. Wie im Fall linearer schlecht gestellter Probleme üblich, drücken wir den Gesamtaufwand des Verfahrens durch das Rauschen in den gegebenen Daten aus.Um den Aufwand solcher regularisierten Newton Verfahren zu reduzieren, betrachten wir Spektralvorkonditionierer, die die Konvergenzgeschwindigkeit der inneren CG-Iteration erhöhen. Wir erweitern unsere Aufwandsanalyse auf die daraus resultierenden vorkonditionierten, regularisierten Newton Verfahren. Diese Untersuchung gestattet es uns, den Aufwand vorkonditionierter und nicht vorkonditionierter Newton Verfahren zu vergleichen. Insbesondere beweisen wir die Überlegenheit der vorkonditionierten Verfahren im Falle exponentiell schlecht gestellter Probleme.Zum Abschluß, in einem dritten Teil der Arbeit, diskutieren wir die praktische Umsetzung vorkonditionierter iterativ regularisierter Gauß-Newton Verfahren, wobei wir den engen Zusammenhang zwischen dem Verfahren der konjugierten Gradienten und dem Lanczos Verfahren ausnutzen, sowie das schnelle Abfallverhalten der Eigenwerte der in den Newton Gleichungen auftretenden linearen Operatoren, d.h. wir bestimmen mit dem Lanczos Verfahren Approximationen an die Eigenwerte, welche genutzt werden um in den folgenden Newton-Schritten einen Spektralvorkonditionierer für die innere CG-Iteration aufzustellen. Durch eine laufende Verbesserung des Spektralvorkonditionierers im Verlauf des Newton Verfahrens kann der gesamte Aufwand des Verfahrens deutlich reduziert werden. An numerischen Beispielen aus der inversen Streutheorie illustrieren wir die Effizienz der vorkonditionierten Newton Verfahren verglichen mit anderen regularisierten Newton Verfahren.