TU Graz/ Forschung/ Fields of Expertise/

Quasi-Monte Carlo-Methoden: Theorie und Anwendungen

Präzise und rasche Simulationsergebnisse für zum Beispiel die Berechnung von finanziellen Risiken oder die optimale Dosierung für eine Strahlentherapie zu erzielen – dieser Herausforderung stellen sich Forschende im Field of Expertise Information, Communication & Computing der TU Graz. Die Forschenden arbeiten mit Quasi-Monte-Carlo-Methoden an komplexen Fragestellungen der mathematischen Wahrscheinlichkeitstheorie. Der Spezialforschungsbereich Quasi-Monte Carlo-Methoden: Theorie und Anwendungen wurde 2014 mit Teilprojekten in Linz, Graz, Salzburg und Wien mit einer Laufzeit von vier Jahren eingerichtet.

Anwendung der Methoden

Viele Fragestellungen in Physik, Technik, Wirtschaftswissenschaften, Medizin oder Biologie lassen sich durch mathematische Methoden nicht exakt beantworten, sondern können nur durch aufwendige Simulationstechniken näherungsweise gelöst werden. Mithilfe der Quasi-Monte-Carlo (QMC)-Methoden, vor allem aus den Bereichen Zahlentheorie, Algebra und Kombinatorik, wird für diese Simulationen eine subtil erzeugte Auswahl von Punkten getroffen, um schnell und präzise quantitative Informationen zu erzielen. Die Anwendungsbereiche reichen von Banken und Versicherungen über Physik bis zu Biologie und Medizin. Behandelt wird beispielsweise folgende Fragestellung: Wie, wo und mit welcher Intensität muss eine Strahlentherapie dosiert werden, um eine optimale Wirkung zu erzielen?

Monte Carlo – nicht nur ein Casino

Die Monte Carlo-Methode setzt bei der Simulation Zufallszahlen ein. Damit wird versucht, mit Hilfe der Wahrscheinlichkeitstheorie analytisch nicht oder nur aufwendig lösbare Probleme näherungsweise zu lösen. Eine Monte-Carlo-Simulation zeigt, welche Ergebnisse eine gewisse Handlung mit sich bringen könnte und wie hoch deren Eintrittswahrscheinlichkeit ist.

Diese Zufallszahlen beinhalten jedoch 3 Probleme:

  1. Wie kann man auf dem Computer wirklich zufällige Zahlenwerte erzeugen?
  2. Die Wahrscheinlichkeitstheorie liefert eine Größenordnung des Fehlers, die mit der Quadratwurzel der Anzahl der Punkte abnimmt. Also sind für eine Verbesserung des Fehlers um einen Faktor 10 hundert Mal so viele Punkte notwendig. Wie kann man diese Fehlerordnung verbessern?
  3. Die Ergebnisse, die man aus der Monte Carlo-Simulation erhält, sind mit hoher Wahrscheinlichkeit korrekt, aber nicht absolut sicher. Wie kann man korrekte Ergebnisse garantieren?

Zufall auf Abruf

Diese drei oben genannten Einschränkungen der Monte Carlo-Methode führten zur Entwicklung der Quasi-Monte Carlo-Methode. Dabei werden die Zahlen gezielt so ausgewählt, dass sie ähnlich gut oder besser funktionieren als Zufallszahlen. Die Stützstellen für das jeweilige numerische Verfahren werden ohne zufälligen Einfluss gewählt, aber nach Möglichkeit mit zumindest gleich guten Eigenschaften wie zufällige Punkte. Tatsächlich stellt sich bei den Konstruktionen solcher Punkte heraus, dass die Fehlerordnung 1/√N sogar auf log(N)^d/N verbessert werden kann; dabei steht d für die Dimension des zugrundeliegenden Bereichs.

Die QUASI-Monte Carlo-Methoden erreichen eine deutliche Verbesserung der Konvergenzordnung der Verfahren und ein garantiert korrektes Ergebnis im Gegensatz zur Monte Carlo-Methode, die auch an prinzipielle Grenzen stößt.

Eine Möglichkeit, gut verteilte Punkte zu erzielen, ist es, eine Gesamtenergie der Verteilung zu minimieren, siehe Abbildung 2.

Die Konstruktion von möglichst vielen, oft problemangepassten Quasi-Monte Carlo-Punktfolgen besonders für hohe Dimensionen, ist ein in Österreich schon seit Jahrzehnten stark vertretenes mathematisches Forschungsgebiet. Der Spezialforschungsbereich Quasi-Monte Carlo-Methoden: Theorie und Anwendungen bündelt die bisherigen Forschungsergebnisse, entwickelt  die Theorie weiter und wendet diese in praktischen Beispielen an.

Den Forschenden auf der Spur

Die Forschenden der TU Graz entwickeln die Quasi-Monte Carlo-Methoden weiter. Sie

  • erzeugen, erforschen und analysieren Verteilungseigenschaften von endlichen oder unendlichen Punktmengen in verschiedenen Räumen.
  • entwickeln, erforschen und analysieren geeignete theoretische Modelle für die Anwendung von QMC-Methoden, inkl. Fehlerabschätzungen.
  • setzen die theoretischen Modelle und Algorithmen für die Erzeugung der Quasi-Zufalls-Punktmengen effizient um – in Form hochentwickelter Software.
  • wenden die entwickelten theoretischen Quasi-Monte Carlo-Methoden in praktischen Bereichen wie zum Beispiel der Finanzmathematik konkret an.
  • diskutieren und veröffentlichen die erzielten Ergebnisse und die Performance der QMC-Methoden.
Bildquelle: Peter Grabner

Abbildung 1:
Diese Punktverteilung in der Grafik stellt die Abstände der Punkte von der Quasi-Monte Carlo-Methode zueinander dar. Ein Großteil der Punkte ist ziemlich regelmäßig, die roten Stellen zeigen größere Löcher (Unregelmäßigkeiten). Solche kleinen Unregelmäßigkeiten lassen sich auch in der Quasi-Monte Carlo-Methode nicht vermeiden.

Bildquelle: Peter Grabner
Peter Grabner, Projektleiter

So einfach die Frage klingt Wie verteilt man eine große Anzahl von Punkten auf einer Kugeloberfläche?, so komplex ist die Suche nach korrekten und brauchbaren Antworten. Schön ist, dass diese rein theoretischen Fragestellungen in verschiedenen Wissenschaften praktisch angewendet werden. Zum Beispiel für die gute Auswahl der Messpunkte in der Computertomographie oder für die optimale Verteilung von geographischen Messstationen.

 

Bildquelle: Robert Tichy
Robert Tichy, Projektleiter

Quasi-Monte Carlo Verfahren stellen ein modernes Arbeitsgebiet im Spannungsfeld zwischen reiner und angewandter Mathematik dar. Wir verwenden tiefliegende Methoden aus Analysis, Zahlentheorie und Wahrscheinlichkeitstheorie, um leistungsfähige Algorithmen zu entwickeln und zu analysieren. Das führt zu spannender Teamarbeit mit jungen Kolleginnen und Kollegen und interessanten Anwendungen, etwa bei der Berechnung von fairen Preisen von komplizierten Finanzprodukten.

Quasi-Monte Carlo Potenzial, Bildquelle: Peter Grabner

Abbildung 2:
Die Bilder zeigen zwei Ergebnisse dieser Methode und das zugehörige Potential. Wenn man die Anzahl der Punkte erhöht, wird das Potential immer flacher, die Spitzen werden kleiner.

Arbeitsgruppe Quasi-Monte Carlo-Methoden, Bildquelle: TU Graz/Institut für Analysis und Zahlentheorie

Das Team vom Institut für Analysis und Zahlentheorie:
1. Reihe Maria Rita Iacò
2. Reihe von links: Wöden Kusner, Jonas Ziefle
3. Reihe von links: Johann Brauchart, Peter Grabner
4. Reihe Robert Tichy

Kontakt

Institut für Analysis und Zahlentheorie
Steyrergasse 30/II
8010 Graz

Peter GRABNER
Univ.-Prof. Dipl.-Ing. Dr.techn.
Projektleiter
Tel.: +43 316 873 7124 
peter.grabnernoSpam@tugraz.at

Robert TICHY
O.Univ.-Prof. Dr.phil.
Projektleiter
Tel.: +43 316 873 7120
tichynoSpam@tugraz.at

Bildquelle: Grabner – TU Graz

Abstandsfunktion einer Punktverteilung

Zusammenarbeit macht erfolgreich

Um die Forschungsziele zu erreichen, kooperieren die Forschenden des Bereichs Quasi-Monte Carlo-Methoden: Theorie und Anwendungen im Field of Expertise Information, Communication & Computing der TU Graz national und international mit zahlreichen Forschungseinrichtungen.

 

Internationale Kooperationen

  • École polytechnique fédérale de Lausanne
  • ETH Zürich, CH
  • Karlsruher Institut für Technologie (KIT), D
  • Rutgers University
  • University of New South Wales, Sydney
  • Vanderbilt University, Nashville, TN

Nationale Kooperationen

  • Institut für Finanzmathematik und Angewandte Zahlentheorie, Johannes Kepler Universität Linz
  • Institut für Diskrete Mathematik und Geometrie, TU Wien
  • Fachbereich Mathematik, Universität Salzburg