FixpunktIteration

Fixpunktiteration, auch Fixpunktverfahren genannt, ist ein einfaches numerisches Verfahren zur Lösung von Gleichungen der Form x = g(x). Ausgehend von einer Startschätzung x0 erzeugt man eine Folge durch x_{k+1} = g(x_k). Ist der Fixpunkt x* von g existiert, finden sich unter passenden Bedingungen alle Folgenglieder gegen x*.

Konvergenzbedingungen: Reicht eine Kontraktion von g auf einem Intervall I, d. h. es existiert 0 ≤ q < 1, so dass |g(x) − g(y)| ≤ q|x − y| für alle x,y in I. Dann existiert eindeutig ein Fixpunkt x* in I, und x_k konvergiert für jedes x0 in I gegen x*. Die Konvergenz ist linear mit dem Fehlerabschätzungsmaß |x_{k+1} − x*| ≤ q|x_k − x*|. Eine häufig verwendete hinreichende Bedingung ist, dass g differentiierbar ist und |g'(x)| ≤ q < 1 in I (Evaluation über den Mittelwertsatz).

Vorgehen und Varianten: Wähle eine Funktion g, die einen Fixpunkt bildet, und halte x0 innerhalb des Intervalls I. Iteriere x_{k+1} = g(x_k). Zur Verbesserung der Konvergenz kann eine Relaxation mit x_{k+1} = x_k + λ(g(x_k) − x_k) verwendet werden, mit 0 < λ ≤ 2.

Beispiel: Lösen von x = cos x. Mit g(x) = cos x und Startwert x0 = 1 konvergiert die Folge gegen x* ≈ 0,739085.

Relation zu anderen Methoden: Newtons Methode kann als spezielles Fixpunkt-Verfahren mit g(x) = x − f(x)/f'(x) betrachtet werden und erreicht oft schnellere Konvergenz. Fixpunktiteration ist einfacher, aber stark abhängig von der Wahl von g und kann divergieren, wenn die Kontraktionseigenschaft nicht erfüllt ist.

Anwendungen: Lösen nichtlinearer Gleichungen, Diskretisierung von Gleichungssystemen (Picard-Iterationen) und als Baustein in verschiedenen numerischen Verfahren.