ELITE NETZWERK BAYERN

English  Sprachen Icon  |  Gebärdensprache  |  Leichte Sprache  |  Kontakt


Forschungsarbeit

Schnelle und stabile Algorithmen:
Ein Verfahren zur Inversion von Laplace-Transformierten

Von Benedict Dingfelder (12.02.2014)

Das Zeitalter der Computer ist zugleich ein Zeitalter der Mathematik. Die schnelle maschinelle Berechnung möglichst exakter Ergebnisse ist eine Herausforderung, mit der sich die mathematische Teildisziplin der Numerik beschäftigt. Sie ist das wesentliche Werkzeug, wenn analytische Methoden versagen, also keine expliziten Lösungsausdrücke existieren und nur approximative Lösungen gefunden werden können. Manche Probleme sind von vornherein für den Computer nur sehr schwierig zu lösen. Der Mathematiker spricht von einem schlecht konditionierten Problem. Allerdings lassen sich manche schlecht konditionierte Probleme in äquivalente, besser konditionierte Probleme überführen.

An einen Algorithmus, der ein gegebenes Problem löst, stellen wir verschiedene Anforderungen. Einerseits sind wir an einer hohen Konvergenzgeschwindigkeit interessiert, also dass wir mit geringem rechnerischen und somit auch zeitlichen Aufwand ein Ergebnis erhalten, das - bezogen auf die Eingabedaten – nahe an der tatsächlichen Lösung des Problems liegt. Andererseits fordern wir die Stabilität des Verfahrens. Das bedeutet, dass (für gut konditionierte Probleme) kleine Fehler in der Eingabe auch nur in kleinen Änderungen in der Ausgabe resultieren. Beispielsweise sind physikalische Messungen immer mit einem gewissen Fehler behaftet. Haben wir einen instabilen Algorithmus, so ist das resultierende Ergebnis entweder mit einem großen Fehler behaftet oder sogar vollkommen unbrauchbar. Konvergenzgeschwindigkeit und Stabilität sind demnach offensichtliche Anforderungen, die wir an einen Algorithmus stellen. 

Für die Forschungsarbeit, die ich hier in einem groben Abriss präsentieren möchte, habe ich mit Prof. André Weideman von der University of Stellenbosch in Südafrika zusammengearbeitet. Zu Beginn des Projekts habe ich Prof. Weideman für drei Wochen in Stellenbosch besucht, woraus auch darüber hinausgehend eine intensive Zusammenarbeit entstanden ist. Wir haben uns mit dem Problem der inversen Laplace-Transformation befasst. Anwendungen hiervon finden sich unter anderem in der Simulation physikalischer Prozesse am Computer. Die Laplace-Transformation und ihre Inversion sind ein mächtiges Werkzeug zur Lösung linearer Differentialgleichungssysteme mit konstanten Koeffizienten. Beide Operationen sind Grundbestandteile des Werkzeugkastens der mathematischen Naturwissenschaften, weshalb sie ein breites Anwendungsspektrum besitzen. Daher möchte ich die Anwendungsgebiete so allgemein wie möglich halten. 

Im Wesentlichen entspricht die inverse Laplace-Transformation der Auswertung eines komplexwertigen Integrals entlang einer Geraden - einer sogenannten Bromwich-Linie - in der Ebene der komplexen Zahlen. Um das Integral numerisch auszuwerten, werden sogenannte Quadraturformeln benutzt. Die numerische Quadratur entlang der Bromwich-Linie ist jedoch schlecht konditioniert. In diesem Fall lässt sich das Problem der schlechten Konditionierung durch einen mathematischen Trick teilweise umgehen. 

Setzen wir beispielsweise voraus, dass der Integrand lediglich für Zahlen kleiner 0 Definitionslücken besitzt (Mathematik: Der Integrand ist holomorph im Gebiet ℂ\ℝ-), so liefert die Integration entlang der Bromwich-Linie dasselbe Ergebnis wie die Integration entlang eines anderen Weges, der der Linie in einem gewissen Sinne ähnelt (Mathematik: Beide Wege sind zueinander homolog). Einen solchen anderen Weg hat A. Talbot 1979 vorgeschlagen [1].  Allerdings existieren in seiner Definition insgesamt drei frei zu wählende Parameter. Hier beginnt nun unsere Arbeit. Diese Parameter müssen dergestalt gewählt werden, dass die numerische Integration entlang des so entstehenden Weges eine hohe Konvergenzgeschwindigkeit aufweist und stabil erfolgt. 

[Bildunterschrift / Subline]: Abb. 1: Schlecht (links) und gut (rechts) konditionierte Talbot-Integrationswege für eine wachsende Anzahl an Auswertungspunkten.

Um eine maximale Konvergenzgeschwindigkeit zu erhalten, haben wir zunächst einen zusätzlichen Freiheitsgrad in den von Talbot vorgeschlagenen Weg eingeführt. Optimieren wir diese nun insgesamt vier Freiheitsgrade lediglich hinsichtlich der Konvergenzgeschwindigkeit, so ergeben sich Wege, entlang derer die Integration für große Anzahlen an Auswertungspunkten schlecht konditioniert ist. In Abbildung 1 erkennen wir das im linken Teilbild daran, dass sich die Integrationswege in den roten, schlecht konditionierten Bereich bewegen. Pflegen wir diese Beobachtung in die Theorie ein, können wir diese Bewegung verhindern und erhalten Wege, die sich entsprechend dem rechten Teilbild von Abbildung 1 verhalten, also auch für große Anzahlen an Quadraturpunkten gut konditioniert bleiben. In diesen Optimierungsschritten steckt viel mathematische Arbeit, auf deren Darstellung ich an dieser Stelle verzichte. Details können in [2] gefunden werden.

Die Anzahl exakter Ziffern im Endergebnis hängt linear mit der Anzahl dafür benötigter Quadraturpunkte zusammen. Wollen wir also doppelt so viele exakte Ziffern, benötigen wir auch doppelt so viele Auswertungspunkte. Falls wir ein Ergebnis bestimmen müssen, dessen erste 5 bzw. 10 Ziffern exakt sind, so benötigen wir lediglich 9 bzw. 17 Auswertungspunkte in der Quadraturformel! Insgesamt haben wir einen schnellen und stabilen Algorithmus entwickelt, dessen Fehler exponentiell in der Anzahl der Auswertungspunkte fällt. 

[1] Talbot, A. 1979. The accurate numerical inversion of Laplace transforms. J. Inst. Math. Appl. 23, 1, 97–120.

[2] Dingfelder, B., Weideman, J.A.C. 2013. An improved Talbot method for numerical Laplace transform inversion, arxiv.org/abs/1304.2505


Wissenschaftlicher Werdegang
  • 2009-2011
  • Student (B.Sc.) der Mathematik mit Nebenfach Informatik an der Technischen Universität München
  • 2011-2012
  • Abschluss im Elite-Teilstudiengang Bachelor Mathematik im Rahmen des TopMath- Programms
  • seit 2012
  • Promotionsstudium mit parallelem Honours Master im Rahmen des TopMath-Programms an der Technischen Universität München

Preise und Auszeichnungen
  • * Stipendiat der „Studienstiftung des deutschen Volkes
  • * TopMath Presentation Award
  • * Stipendiat des „Max-Weber Programms“ des Freistaats Bayern
  • * Stipendiat des „e-fellows.net- Netzwerks“


Publikationen
  • * Dingfelder, B., Weideman, J.A.C. 2013. An improved Talbot method for numerical Laplace transform inversion, http://arxiv.org/abs/1304.2505