Iterationsmatrix

Iterationsmatrix

Die Fixpunktiteration ist ein in der Mathematik gebräuchliches iteratives Verfahren zur näherungsweisen Bestimmung der Nullstellen einer Funktion f auf einem bestimmten Intervall [a,b]. Die Gleichung muss dazu zuerst in eine Fixpunktgleichung, also eine Gleichung der Form

\varphi(x) = x

umgeformt werden.

Inhaltsverzeichnis

Allgemein

Jedes Fixpunktverfahren hat die Form

x_{k+1} = \varphi(x_k), k = 0, 1, ...

Mit jeder weiteren Iteration soll sich xk+1 der exakten Lösung x* annähern. Das Ziel ist, die Iterationsvorschrift \varphi so zu konstruieren, dass sie genau einen Fixpunkt x* besitzt, dass also schließlich gilt:

x^* = \varphi(x^*).

Die Konvergenz von Fixpunktiterationen wird mittels des banachschen Fixpunktsatzes untersucht. In vielen Fällen divergiert die Iteration auch, so dass kein Fixpunkt ermittelt werden kann. Die Konvergenz hängt außer von der Funktion insbesondere vom gewählten Startwert der Iteration ab.

Lineare Fixpunktverfahren

Konstruktionsidee

Eine wichtige Art der Fixpunktiteration sind die Splitting-Verfahren. Für Fixpunkt-Probleme der Art Ax = b, wobei A eine nicht-singuläre quadratische Matrix und b ein Vektor ist, zerlegt man die Matrix A mit Hilfe einer nicht-singulären n×n-Matrix B in

A = B + (AB)

und erhält so eine Fixpunktgleichung.

Damit folgt

Ax = b
(B + (AB))x = b
Bx + (AB)x = b
\Rightarrow x = B^{-1}b - B^{-1}(A-B)x = (E - B^{-1}A)x + B^{-1}b; E ist die Einheitsmatrix.

Jetzt ist das lineare Gleichungssystem Ax = b äquivalent zu der Fixpunktaufgabe

x = (E - B^{-1}A)x + B^{-1}b = \varphi(x).

Man erhält für den vorgegebenen Startvektor x0 folgendes Iterationsverfahren

xk + 1 = (EB − 1A)xk + B − 1b, k = 0, 1, ...

und die zugehörige Iterationsmatrix lautet: E - B-1A.

Konvergenz

Aus dem banachschen Fixpunktsatz und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor x0 konvergieren, falls der Spektralradius der Iterationsmatrix

ρ(EB − 1A) = maxi | λi(EB − 1A) | < 1.

ρ(EB − 1A) sollte möglichst klein sein, da dadurch die Konvergenzgeschwindigkeit bestimmt wird.

Spezielle Verfahren

Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren:

Bemerkungen

Iterationsverfahren der Form xk + 1 = Mxk + v, k = 0, 1, ... sind

  • linear, d.h. xk+1 hängt linear nur von xk ab,
  • stationär, d.h. M und v sind unabhängig von der Schrittnummer der Iteration,
  • einstufig, d.h. nur der letzte und nicht noch weitere Näherungsvektoren werden verwendet.

Nichtlineare Gleichungen

Das Newton-Verfahren kann als Fixpunktiteration betrachtet werden. Allgemein wird die Konvergenz mit Hilfe des banachschen Fixpunktsatzes sichergestellt, die betrachtete Funktion muss also insbesondere im betrachteten Gebiet eine Kontraktion sein.


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Einzelschrittverfahren — In der numerischen Mathematik ist das Gauß Seidel Verfahren oder Einzelschrittverfahren, (nach Carl Friedrich Gauß und Ludwig Seidel) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es ist, wie das Jacobi Verfahren und …   Deutsch Wikipedia

  • Fixpunktiteration — grafische Darstellung der eindimensionalen Fixpunktiteration Fixpunktiteration ist ein in der Mathematik gebräuchliches iteratives Verfahren zur näherungsweisen Bestimmung der Nullstellen einer Funktion f auf einem bestimmten Intervall [a,b]. Die …   Deutsch Wikipedia

  • Fixpunktverfahren — Die Fixpunktiteration ist ein in der Mathematik gebräuchliches iteratives Verfahren zur näherungsweisen Bestimmung der Nullstellen einer Funktion f auf einem bestimmten Intervall [a,b]. Die Gleichung muss dazu zuerst in eine Fixpunktgleichung,… …   Deutsch Wikipedia

  • Gauss-Seidel-Algorithmus — In der numerischen Mathematik ist das Gauß Seidel Verfahren oder Einzelschrittverfahren, (nach Carl Friedrich Gauß und Ludwig Seidel) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es ist, wie das Jacobi Verfahren und …   Deutsch Wikipedia

  • Gauß-Seidel-Verfahren — In der numerischen Mathematik ist das Gauß Seidel Verfahren oder Einzelschrittverfahren, (nach Carl Friedrich Gauß und Ludwig Seidel) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es ist, wie das Jacobi Verfahren und …   Deutsch Wikipedia

  • Gesamtschrittverfahren — In der numerischen Mathematik ist das Jacobi Verfahren, auch Gesamtschrittverfahren genannt, (benannt nach Carl Gustav Jakob Jacobi) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen Ax = b. Es ist, wie das Gauß Seidel… …   Deutsch Wikipedia

  • Jacobi-Verfahren — In der numerischen Mathematik ist das Jacobi Verfahren, auch Gesamtschrittverfahren genannt, ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen Ax = b. Es ist, wie das Gauß Seidel Verfahren und das SOR Verfahren, ein… …   Deutsch Wikipedia

  • Jacobiverfahren — In der numerischen Mathematik ist das Jacobi Verfahren, auch Gesamtschrittverfahren genannt, (benannt nach Carl Gustav Jakob Jacobi) ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen Ax = b. Es ist, wie das Gauß Seidel… …   Deutsch Wikipedia

  • Richardson-Iteration — Das Richardson Verfahren ist in der numerischen Mathematik ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es zählt wie das Gauß Seidel Verfahren zur Klasse der Splitting Verfahren. Als iteratives Verfahren nähert es… …   Deutsch Wikipedia

  • Richardson-Verfahren — Das Richardson Verfahren ist in der numerischen Mathematik ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es zählt wie das Gauß Seidel Verfahren zur Klasse der Splitting Verfahren. Als iteratives Verfahren nähert es… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”