Kurs:Numerik I/Fixpunktiteration

Einleitung

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Einführung - mehrdimensionale Fixpunktiteration

Zunächst wird die Fixpunktiteration auf Funktionen $g:D\to D$ mit $D\subseteq \mathbb {R} ^{n}$ verallgemeinern, die bereits für $n=1$, $D=[a,b]$ und hinreichend glattes $g$ diskutiert wurde.

Fixpunktiteration

Für die Bestimmung eines Fixpunktes von $g$, d. h. eines Punktes $x^{(*)}\in \mathbb {R} ^{n}$ mit $g(x^{(*)})=x^{*}$, betrachten wir also die Iterationsvorschrift

$x^{(k+1)}:=g(x^{(k)}),\quad k=0,1,2,\ldots {\mbox{ (FPI)}}$

mit einem gegebenen Startwert $x^{(0)}\in K\subset \mathbb {R} ^{n}$.

Bemerkung 1 - Fixpunktiteration

Im Folgenden werden die Abkürzung (FPI) für Fixpunktiteration $x^{(k+1)}:=g(x^{(k)})$ verwenden.

Vollständigkeit des Grundraumes

Man zeigt in dem Beweis wieder, dass die Fixpunktiteration eine Cauchyfolge liefert. Die Vollständigkeit liefert dann, dass auch ein Grenzwert der Cauchyfolge in $x^{(*)}\in D\subset \mathbb {R} ^{n}$ existiert, d

Bemerkung 2 - Bezug zu Nullstellenverfahren

Für eine Selbstabbildung $g:D\to D$ mit $D\subseteq \mathbb {R} ^{n}$

Bemerkung 3 - Stetigkeit

Die Lipschitz-Stetigkeit ist eine besondere Form der Stetigkeit, die im eindimensionalen Fall ein Beschränktheit der Sekantensteigungen liefert. Ist $g:D\to D$ differenzierbar, so ist im eindimensionalen Fall die Ableitung $|g'(x)|\leq L$. Für den mehrdimensionalen Fall wird nun die Lipschitz-Stetigkeit definiert.

Definition - Lipschitz-stetig

Sei $D\subseteq \mathbb {R} ^{n}$ und $\|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{+}$ eine Norm auf dem $\mathbb {R} ^{n}$

• (Lipschitz-stetig) Eine Abbildung $g:D\to \mathbb {R} ^{n}$ heißt Lipschitz-stetig auf $D$ mit (Lipschitz-)Konstante $L>0$, wenn gilt: $\|g(x)-g(y)\|\leq L\|x-y\|,\quad x,y\in D\quad (LSS).$
• (Kontraktion) Eine Lipschitz-stetige Abbildung $g:D\to D$ mit Konstante $L>0$ heißt eine Kontraktion auf $D$, wenn $L<1$ ist.

Zusammenhang - partielle Ableitungen und Lipschitz-Stetigkeit

Sei nun speziell $g\in C^{1}(D,\mathbb {R} ^{n})$ für $D\subseteq \mathbb {R} ^{n}$, wobei wir damit eine Funktion $g:D\subseteq \mathbb {R} ^{n}\to \mathbb {R} ^{n}$ mit

$g(x)=(g_{1}(x),\ldots ,g_{n}(x))^{T},\quad x\in D$

und stetigen partiellen Ableitungen ${\frac {\partial g_{i}}{\partial x_{j}}}(x)$ $(i,j=1,\ldots ,n)$ für alle $x\in D$ meinen.

Bestimmung der Lipschitz-Konstante

Für ein solches $g$ kann man in der Praxis häufig eine Konstante $L$ aus der Definition kann mittels der partiellen Ableitungen von den Komponentenfunktionen $g_{i}$ bzw. der Jacobi-Matrix von $g$ bestimmt werden.

Jacobi-Matrix

Die Jacobi-Matrix ist mit $I:=\{1,\ldots ,n\}$ wie folgt definiert.

${\mathcal {J}}_{g}(x):=\left({\frac {\partial g_{i}}{\partial x_{j}}}(x)\right)_{i,j\in I}={\begin{pmatrix}{\frac {\partial g_{1}}{\partial x_{1}}}(x)&{\frac {\partial g_{1}}{\partial x_{2}}}(x)&\ldots &{\frac {\partial g_{1}}{\partial x_{n}}}(x)\\{\frac {\partial g_{2}}{\partial x_{1}}}(x)&{\frac {\partial g_{2}}{\partial x_{2}}}(x)&\ldots &{\frac {\partial g_{2}}{\partial x_{n}}}(x)\\\vdots &\vdots &\ddots &\vdots \\{\frac {\partial g_{n}}{\partial x_{1}}}(x)&{\frac {\partial g_{n}}{\partial x_{2}}}(x)&\ldots &{\frac {\partial g_{n}}{\partial x_{n}}}(x)\end{pmatrix}}\in \mathbb {R} ^{n\times n}$

gegeben ist.

Bemerkung - Lipschitz-Stetigkeit im eindimensionalen Fall

Im eindimensionalen reellwertigen Fall bedeutet Lipschitz-Stetigkeit für differenzierbare Funktionen $f:D\to \mathbb {R}$, dass die Ableitungen $f'(x_{o})$ betragsmäßig durch $L$ für alle $x_{o}\in D\subseteq \mathbb {R}$ beschränkt sind, d.h.:

$|f'(x_{o})|=\lim _{x\to x_{o}}\left|{\frac {f(x)-f(x_{o})}{x-x_{o}}}\right|\leq \lim _{x\to x_{o}}{\frac {L\cdot |x-x_{o}|}{|x-x_{o}|}}=L$

Für die Lipschitz-Stetigkeit ist natürlich die Differnzierbarkeit keine Voraussetzung.

Definition - konvexe Menge

Eine Menge $D\subseteq \mathbb {R} ^{n}$ heißt konvex, falls für je zwei Elemente $x,y\in D$ auch alle Konvexkombinationen von $x$ und $y$ zu $D$ gehört, d. h. falls

$x,y\in D,\quad t\in [0,1]\Rightarrow (1-t)\cdot x+t\cdot y\in D.$

Bemerkung - Mittelwertsatz der Differentialrechnung

Damit lässt sich bekanntlich das folgende Lemma aus dem Mittelwertsatz der Differentialrechnung ableiten (siehe auch Konvexkombination).

Lemma - Jacobi-Matrix - Lipschitz-Stetigkeit

Es sei $g\in {\mathcal {C}}^{2}(D,\mathbb {R} ^{n})$ für eine offene, konvexe Menge $D\subseteq \mathbb {R} ^{n}$ und für eine Konstante $L>0$ gelte

$\|{\mathcal {J}}_{g}(x)\|\leq L,\quad x\in D.$

Dann folgt die Abschätzung

$\|g(x)-g(y)\|\leq L\|x-y\|,\quad x,y\in D.$

Bemerkung

Zum oben angegebenen Zusammenhang zwischen Jacobi-Matrix und Lipschitz-Stetigkeit geben wir zunächst zwei Beispiele im eindimensionalen Fall an.

Beispiel 1 - eindimensionaler Definitionsbereich

Die Funktion $f(x):=x^{2}$ ist auf $[0,0.4]$ eine Kontraktion, denn es ist

$f([0,0.4])=[0,0.16]\subseteq [0,0.4]$

und mit $L:=\displaystyle \max _{x\in [0,0.4]}(2x)=0.8$

$\left|x^{2}-y^{2}\right|\leq 0.8|x-y|,\quad x,y\in [0,0.4].$

Beispiel 2 - eindimensionaler Definitionsbereich

Die Funktion $f(x):={\sqrt {x}}$ ist auf $[0,a]$ mit $a>0$ nicht Lipschitz-stetig, denn für $y=0$ hat man

$\left|{\sqrt {x}}-{\sqrt {0}}\right|={\sqrt {x}}={\frac {1}{\sqrt {x}}}(x-0)={\frac {1}{\sqrt {x}}}|x-0|,\quad x\in (0,a]$

und $\lim _{x\to 0}(1/{\sqrt {x}})=\infty$.

Beispiel - Aufgabe 3 - mehrdimensionaler Definitionsbereich

Der Definitionsbereich $D:=[-1,+1]\times [-1,+1]\times [-1,+1]=[-1,+1]^{3}\subset \mathbb {R} ^{3}$ und der Funktion $g:D\to D$ mit

$g(x_{1},x_{2},x_{3}):=\left({\frac {x_{1}^{2}+x_{3}^{2}}{10}},{\frac {x_{2}+x_{3}}{5}},{\frac {x_{3}^{2}}{5}}\right)$

Bestimmen Sie die Lipschitz-Konstante $L>0$. Überprüfen Sie, ob die Abbildung $g:D\to D$ eine Kontraktion mit $L<1$ ist?

Bemerkung - Banachsche Fixpunktsatz

Der folgende sog. Banachsche Fixpunktsatz gibt an, dass die Fixpunktiteration (FPI) konvergiert, und zwar für allgemeines $n$ und ohne Differenzierbarkeitsforderungen an $g$, wobei als Startvektor alle Elemente $x^{(0)}\in D\subset \mathbb {R} ^{n}$ des Definitionsbereiches $D$ von $g$ zugelassen sind.

Bemerkung - Eindeutigkeit des Fixpunkt

Überdies liefert die Kontraktionseigenschaft unter den genannten Voraussetzungen die Existenz eines eindeutigen Fixpunktes. Die geforderte Kontraktionseigenschaft für die Iterationsfunktion $g$ ist allerdings eine relativ starke Voraussetzung.

Satz - Banachscher Fixpunktsatz

Sei $D\subseteq \mathbb {R} ^{n}$ abgeschlossen und die Abbildung $g:D\to D$ bezüglich der Vektornorm $\|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{o}^{+}$ eine Kontraktion mit Konstante $L\in (0,1)$. Dann gilt:

• (BF1) $g$ besitzt genau einen Fixpunkt $x^{*}\in D$.
• (BF2) Für jeden Startpunkt $x^{(0)}\in D$ liefert die Fixpunktiteration $x^{(k+1)}=g(x^{(k)}),\quad k=0,1,\ldots$ eine Folge $(x^{(k)})_{k\in \mathbb {N} _{o}}$ in $D$, welche gegen $x^{*}$ konvergiert und
• (BF3) $\left\|x^{(k)}-x^{(*)}\right\|\leq {\frac {L}{1-L}}\left\|x^{(k)}-x^{(k-1)}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|,$ für $k=1,2,\ldots .$

Beweis - Banachscher Fixpunktsatz

Zunächst wird die Eindeutigkeit des Fixpunktes durch Widerspruch und Anwendung der Kontraktionseigenschaft gezeigt.

Beweis (BF1) Eindeutigkeit Fixpunkt

Annahme: Es existieren zwei Fixpunkte $x^{*},y^{*}\in D$ Fixpunkte von $g$, so gilt

$\|x^{*}-y^{*}\|=\|g(x^{*})-g(y^{*})\|\leq L\cdot \|x^{*}-y^{*}\|$

Beweisschritt (BF1.1) Eindeutigkeit Fixpunkt

Weil $x^{*}\not =y^{*}$ nach Annahme gilt, erhält man $\|x^{*}-y^{*}\|>0$. Man erhält durch Division der obigen Gleichung durch $\|x^{*}-y^{*}\|$ einen Widerspruch mit $L\geq 1$, da nach Voraussetzung $g:D\to D$ ein Kontraktion mit $0<L<1$ ist.

Beweisschritt (BF1.2) Eindeutigkeit Fixpunkt

Also erhält man, dass $x^{*}=y^{*}$ gilt und $g$ höchstens einen Fixpunkt besitzt.

Beweis (BF2) Konvergenz für beliebige Startpunkte

Sei nun der Startvektor $x^{(0)}\in D$ beliebig gewählt und $(x^{(k)})_{k\in \mathbb {N} _{o}}$ bezeichne die damit durch die Fixpunktiteration (FPI) erzeugte Folge.

Beweis (BF2.1) Konvergenz für beliebige Startpunkte

Für $x^{(k)}\in D$ ist nach (FPI) und $g:D\to D$ offenbar auch $g(x^{(k)})=x^{(k+1)}$ in $D$, so dass $x^{(k)}\in D$ für $k\in \mathbb {N} _{0})$ und der Lipschitz-Stetigkeit wie folgt abgeschätzt werden kann.

Beweis (BF2.2) Konvergenz für beliebige Startpunkte

Man erhält somit für $g(x^{(k)})=x^{(k+1)}$ und $g(x^{(k-1)})=x^{(k)}$ folgende Abschätzung:

$\|x^{(k+1)}-x^{(k)}\|=\|g(x^{(k)})-g(x^{(k-1)})\|\leq L\|x^{(k)}-x^{(k-1)}\|,\quad k\in \mathbb {N} _{0},$

Beweis (BF2.3) Konvergenz für beliebige Startpunkte

Wiederholt man diese Abschätzung mit $g(x^{(k-2)})=x^{(k-1)}$ ergibt sich: :$L\cdot \|x^{(k)}-x^{(k)}\|=L\|g(x^{(k-1)})-g(x^{(k-2)})\|\leq L^{2}\|x^{(k-1)}-x^{(k-2)}\|$.

Beweis (BF2.4) Konvergenz für beliebige Startpunkte

Durch rekursive Anwendung bis zu den Folgengliedern $x^{(0)},x^{(1)}\in D$ erhält man

$\|x^{(k+1)}-x^{(k)}\|\leq L^{k}\|x^{(1)}-x^{(0)}\|$.

Damit kann man nun den Abstand zweier aufeinanderfolgender Folgenglieder $\|x^{(k+1)}-x^{(k)}\|$ gegen eine Potenz der Lipschitz-Konstante und dem Abstand der ersten beiden Folgenglieder abschätzen.

Beweis (BF2.5) Geometrische Reihe

Zur Vorbereitung der Cauchy-Folgeneigenschaft wird nun der Abstand von beliebigen Folgengliedern $\|x^{(k+n)}-x^{(k)}\|$ mit $n\in \mathbb {N}$ nach oben abgeschätzt. Da Potenzen der Form $L^{k}$ nutzt man den Grenzwert der geometrischen Reihe für diese Zweck mit:

$\sum _{k=0}^{\infty }L^{k}={\frac {1}{1-L.}}$

Beweis (BF2.6) Dreiecksungleichung und telekopierende Summe

Man ergänzt Nullvektoren $0_{V}=x^{(k+i)}-x^{(k+i)}$ und erzeugt damit eine teleskopierende Summe von Differenzen und schätzt diese mit Dreieckungleichung nach oben ab. Dies erfolgt, um die Abschätzung (BF2.4) für den Abstand von zwei aufeinander folgenden Folgenglieder $\|x^{(k+i+1)}-x^{(k+i)}\|$ nach oben abschätzen zu können.

Beweis (BF2.7) Dreiecksungleichung und telekopierende Summe

Die vorhergehenden Überlegungen liefern die folgenden Abschätzungen für $k,n\in \mathbb {N} _{0}$:

${\begin{array}{l}\|x^{(k+n)}-x^{(k)}\|=\|x^{k+n}+\underbrace {x^{(k+1)}-x^{(k+1)}} _{=0_{V}}-x^{(k)}\|\\=\left\|\left(x^{(k+1)}-x^{(k)}\right)+\left(x^{(k+2)}-x^{(k+1)}\right)+\ldots +\left(x^{(k+n)}-x^{(k+n-1)}\right)\right\|\\\leq \left\|x^{(k+1)}-x^{(k)}\right\|+\left\|x^{(k+2)}-x^{(k+1)}\right\|+\ldots +\left\|x^{(k+n)}-x^{(k+n-1)}\right\|\\\leq \left\|x^{(k+1)}-x^{(k)}\right\|+L\left\|x^{(k+1)}-x^{(k)}\right\|+\ldots +L^{n-1}\left\|x^{(k+1)}-x^{(k)}\right\|\\=\left\|x^{(k+1)}-x^{(k)}\right\|\cdot \displaystyle \sum _{k=0}^{n-1}L^{k}\leq \left\|x^{(k+1)}-x^{(k)}\right\|\cdot \underbrace {\sum _{k=0}^{\infty }L^{k}} _{={\frac {1}{1-L}}}\end{array}}$

Beweis (BF2.8) Abschätzung von aufeinander folgenden Folgengliedern

Mit (BF2.4) kann man nun zwei aufeinander folgende Folgenglieder gegen den Abstand von den ersten beiden Folgengliedern abschätzen und man erhält mit (BF2.7) für $k,n\in \mathbb {N} _{0}$:

${\begin{array}{rcl}\|x^{(k+n)}-x^{(k)}\|&\leq &\left\|x^{(k+1)}-x^{(k)}\right\|\cdot {\frac {1}{1-L}}\\&\leq &\underbrace {L^{k}\cdot \left\|x^{(1)}-x^{(0)}\right\|} _{(BF2.4)}\cdot {\frac {1}{1-L}}\end{array}}$

Beweis (BF2.9) Abschätzung für Cauchy-Folge

Also gilt für alle $k,n\in \mathbb {N} _{0}$

$\left\|x^{(k+n)}-x^{(k)}\right\|\leq {\frac {L}{1-L}}\left\|x^{(k)}-x^{(k-1)}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|$

Demnach ist die Folge $\left(x^{(k)}\right)_{k\in \mathbb {N} _{0}}$ eine Cauchy-Folge.

Beweis (BF2.10) Begründung Cauchy-Folge

Da $(L^{k})_{k\in \mathbb {N} }$ mit $0<L<1$ eine Nullfolge ist wählt man für ein beliebiges $\varepsilon >0$ das $k_{\varepsilon }\in \mathbb {N}$ so, dass folgende Ungleichung gilt:

$L^{k_{\varepsilon }}<{\frac {\varepsilon \cdot (1-L)}{\left\|x^{(1)}-x^{(0)}\right\|}}$

Beweis (BF2.11) Begründung Cauchy-Folge

Dies liefert für alle $k,n\in \mathbb {N} _{0}$ mit $k\geq k_{\varepsilon }$ die Eigenschaft:

$\left\|x^{(k+n)}-x^{(k)}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|\leq \underbrace {{\frac {L^{k_{\varepsilon }}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|} _{<\varepsilon }<\varepsilon$

Beweis (BF2.12) Vollständigkeit und Cauchy-Folge

Da der Vektorraum $\mathbb {R} ^{n}$ vollständig ist und $D\subset \mathbb {R} ^{n}$ eine abgeschlossene Teilmenge von $\mathbb {R} ^{n}$ ist, existiert ein Grenzwert $x^{*}\in \mathbb {R} ^{n}$ und dieser liegt mit der Abgeschlossenheit von $D$ auch in $D$. Liegt der Grenz

Beweis (BF3) - Konvergenz

Mit der Abschätzung (BF2.9) erhält man für alle $k,n\in \mathbb {N} _{0}$

$\left\|x^{(k+n)}-x^{(k)}\right\|\leq {\frac {L}{1-L}}\left\|x^{(k)}-x^{(k-1)}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|$

Damit gilt die Aussage für alle $n\in \mathbb {N}$ un die Ungleichung "$\leq$" bleibt erhalten beim Grenzübergang „$n\to \infty$“.

Beweis (BF3.1) - Konvergenz

Mit der Abschätzung (BF2.9) erhält man für alle $k,n\in \mathbb {N} _{0}$

$\left\|x^{*}-x^{(k)}\right\|\leq {\frac {L}{1-L}}\left\|x^{(k)}-x^{(k-1)}\right\|\leq {\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|$

Bemerkung (BF3.2)

Wenn nun einer solcher Grenzwert $x^{*}\in D$ und eindeutig ist für eine Kontraktion $g$ ist und nach Voraussetzung (Lipschitz-)stetig ist, kommte man die Abschätzung in (BF3) mit (BF3.1) für die Fixpunktiteration auch auf den Grenzwert $x^{*}$ der Fixpunktinteration übertragen. Der Grenzübergang „$n\to \infty$“ in (BF3.1) liefert schließlich die Abschätzung (BF3).

q.e.d.

Konvergenzgeschwindigkeit

Man beachte, dass man unter den Voraussetzungen des Banachschen Fixpunktsatzes mindestens lineare Konvergenz für die Fixpunktiteration hat, denn dann gilt

$\left\|x^{k+1}-x^{*}\right\|=\left\|g(x^{k})-g(x^{*})\right\|\leq L\left\|x^{k}-x^{*}\right\|,\quad k\in \mathbb {N} _{0},$

wobei $L\in (0,1)$ ist.

Konvergenzgeschwindigkeit

Der Ausdruck

${\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|$

in (BF2) kann, nachdem $x^{1}$ berechnet wurde, für jedes $k\in \mathbb {N}$ vor Beginn der Iteration bestimmt werden.

a-priori-Fehlerabschätzung

Er ermöglicht eine a priori Fehlerabschätzung für den Approximationsfehler $\left\|x^{k}-x^{*}\right\|$. Weiter hat man wegen $L\in (0,1)$ für eine Abbruchschranke $\varepsilon >0$

${\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|\leq \varepsilon \Leftrightarrow k\log(L)\leq \log \left({\frac {(1-L)\varepsilon }{\|x^{(1)}-x^{(0)}\|}}\right)\Leftrightarrow k\geq a$

mit

$a:=\log \left({\frac {(1-L)\varepsilon }{\|x^{(1)}-x^{(0)}\|}}\right)/\log(L),$

so dass mit (5.21) folgt:

$k\geq a\mathbb {R} ightarrow\left\|x^{(k+1)}-x^{*}\right\|\leq \varepsilon .$

Praktisch ist also spätestens in Schritt $k:=k(\varepsilon )$ mit

(5.22) $k(\varepsilon )=\lceil a\rceil$

die Fehlerabschätzung $\left\|x^{k}-x^{*}\right\|\leq \varepsilon$ erfüllt, wobei $\lceil a\rceil$ die kleinste ganze Zahl $\geq a$ bezeichnet.

Der mittlere Ausdruck in (5.20) kann im $k$-ten Iterationsschritt bestimmt werden und erlaubt eine a posteriori Fehlerabschätzung für den Approximationsfehler $\left\|x^{k}-x^{*}\right\|$. Praktisch wird für eine gegebene Schranke $\varepsilon >0$ in Schritt $k:=k(\varepsilon )$ abgebrochen, wenn erstmalig

${\frac {L}{1-L}}\left\|x^{k}-x^{k-1}\right\|\leq \varepsilon$

erfüllt ist. In diesem Fall genügt $x^{k}$ der Fehlerabschätzung $\left\|x^{k}-x^{*}\right\|\leq \varepsilon$.

Wir geben dazu ein Beispiel.

Beispiel 5.16

Es sei

$f(x):=x-e^{-x},\quad x\in \mathbb {R} .$

Dann hat man

$f(x^{*})=0$ für $x^{*}\approx 0.567\ 143\ 29.$

Diese Nullstelle $x^{*}$ soll nun approximativ berechnet werden. Mit

$g(x):=e^{-x},\quad x\in \mathbb {R}$

gilt offenbar

$g(x^{*})=x^{*}\Leftrightarrow f(x^{*})=0,$

so dass wir dazu die Fixpunktiteration $x_{k+1}=g(x_{k})$ mit der Iterationsfunktion $g$ anwenden wollen.

Dafür müssen wir zunächst die Voraussetzungen von Satz 5.15 überprüfen. Auf dem Intervall $D:=[0.5,0.69]$ ist $g$ monoton fallend und somit

$g(D)=[e^{-0.69},e^{-0.5}]\subseteq [0.5,0.61]\subseteq D$

sowie

$L:=\max _{x\in [0.5,0.69]}|g'(x)|=\max _{x\in [0.5,0.69]}e^{-x}=e^{-1/2}\approx 0.606\ 531.$

Also ist $g$ eine Kontraktion. Die folgende Tabelle liefert für den Startwert $x_{0}:=0.55$ ausgewählte Iterierte des Verfahrens:

${\begin{array}{c|c||c|c||c|c}k&x_{k}&k&x_{k}&k&x_{k}\\\hline &&\vdots &\vdots &\vdots &\vdots \\0&0.550\ 000\ 00&10&0.567\ 083\ 94&20&0.567\ 143\ 09\\1&0.576\ 949\ 81&11&0.567\ 176\ 95&21&0.567\ 143\ 40\\2&0.561\ 608\ 77&12&0.567\ 124\ 20&22&0.567\ 143\ 23\\3&0.570\ 290\ 86&13&0.567\ 154\ 12&23&0.567\ 143\ 32\\4&0.565\ 360\ 97&14&0.567\ 137\ 15&24&0.567\ 143\ 27\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \end{array}}$

Die Situation soll nun für $k=12$ genauer betrachtet werden. Die Fehlerabschätzung (5.20) liefert in diesem Fall

${\frac {L^{12}}{1-L}}|x_{1}-x_{0}|={\frac {0.606\ 531^{12}}{1-0.606\ 531}}0.026\ 949\ 81=1.70\cdot 10^{-4},$

${\frac {L}{1-L}}|x_{12}-x_{11}|={\frac {0.606\ 531}{1-0.606\ 531}}0.000\ 052\ 75=8.13\cdot 10^{-5}.$

Der tatsächliche Fehler

$|x_{12}-x^{*}|\approx 1.91\cdot 10^{-5}$

wird also durch die a posteriori Abschätzung um etwa den Faktor 4 und durch die a priori Abschätzung um etwa den Faktor 9 überschätzt.

Praktisches Vorgehen

Das praktische Vorgehen soll nun für die spezielle Fehlerschranke $\varepsilon =0.007\ 6$ illustriert werden. Der (üblicherweise unbekannte) Approximationsfehler unterschreitet diese Schranke bereits für $k=2$, denn man hat $|x_{2}-x^{*}|\approx 0.005\ 5\leq \varepsilon$. Die a posteriori Abschätzung liefert dagegen für $k=4$

$|x_{4}-x^{*}|\leq {\frac {e^{-1/2}}{1-e^{-1/2}}}|0.565\ 360\ 97-0.570\ 290\ 86|=0.007\ 599\leq \varepsilon ,$

also $k(\varepsilon ):=4$ als Stoppzahl, während die a priori Abschätzung in (5.22) mit

$a=\log \left({\frac {(1-L)\varepsilon }{\|x^{1}-x^{0}\|}}\right)/\log(L)=\log \left({\frac {\left(1-e^{-1/2}\right)0.007\ 6}{0.576\ 949\ 81-0.55}}\right)/\log(e^{-1/2})\approx 4.397$

die Vorhersage $k(\varepsilon ):=5$ macht.

Siehe auch

• Konvexkombination

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Fixpunktiteration
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.