Geometrie numerischer Algorithmen

Prof. Peter Bürgisser, Sommersemester 2009


Termine

Vorlesung (V2)
Do 09:15 - 10:45       D1.320  Peter Bürgisser

Beginn Vorlesung
Do 23. April

Aktuelles


Inhalt der Vorlesung

Die Laufzeit vieler iterativer numerischer Algorithmen wird von der Konditionszahl der Eingabe des Berechnungsproblems dominiert, einer kritischen Grösse, welche misst, wie sensitiv die Lösung von der Eingabe abhängt. Dies trifft zu auf iterative Verfahren der linearen Algebra, auf innere Punkt-Methoden der linearen und konvexen Optimierung, sowie Homotopieverfahren zur Lösung polynomialer Gleichungssysteme.

Um die Qualität dieser numerischen Algorithmen theoretisch zu beurteilen, kann eine Analyse ihrer Laufzeit für zufällige Eingaben vorgenommen werden. Dies läuft dann auf eine entsprechende probabilistische Analyse ihrer Konditionszahl zurück. Neben der klassischen average case Analyse ist heute vor allem die geglätte Analyse interessant.

In vielen Fällen ist die Konditionszahl einer Eingabe umgekehrt proportional zur ihrer Distanz zur Menge der ''schlecht gestellten'' Eingaben in einer geeigneten Metrik. Diese Einsicht erlaubt eine Analyse von Konditionszahlen mittels geometrischer Methoden.

Im Wintersemester 07/08 habe ich eine Einführung in diese Thematik angeboten. Diese Veranstaltung soll nun weitergeführt werden. Grössere Teile der Vorlesung werden im wesentlichen unabhängig von der Einführung im WS 07/08 sein, sodass ein Neueinstieg möglich ist. Ferner wird für die Vorlesung im WS 07/08 ein Skript zur Verfügung gestellt werden.

Die Vorlesung soll an forschungsnahe Themen heranführen.

Stichworte
Konditionszahlen für lineare Programmierung,
konditionsbasierte Analyse einer inneren Punktmethode,
Homotopieverfahren zur Lösung polynomialer Gleichungssysteme.
Hörerkreis
ma6
Vorkenntnisse
Analysis III
Von Vorteil sind Kenntnisse in Differentialgeometrie, Numerik und evtl. Optimierung

Literaturangaben