Kurs:Numerik I/Fixpunktiteration

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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.

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

${\displaystyle |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.

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

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

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

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

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

Dann folgt die Abschätzung

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

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

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

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

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

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

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

${\displaystyle \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 ${\displaystyle \lim _{x\to 0}(1/{\sqrt {x}})=\infty }$.

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

${\displaystyle 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 ${\displaystyle L>0}$. Überprüfen Sie, ob die Abbildung ${\displaystyle g:D\to D}$ eine Kontraktion mit ${\displaystyle L<1}$ ist?

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

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

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

• (BF1) ${\displaystyle g}$ besitzt genau einen Fixpunkt ${\displaystyle x^{*}\in D}$.
• (BF2) Für jeden Startpunkt ${\displaystyle x^{(0)}\in D}$ liefert die Fixpunktiteration ${\displaystyle x^{(k+1)}=g(x^{(k)}),\quad k=0,1,\ldots }$ eine Folge ${\displaystyle (x^{(k)})_{k\in \mathbb {N} _{o}}}$ in ${\displaystyle D}$, welche gegen ${\displaystyle x^{*}}$ konvergiert und
• (BF3) ${\displaystyle \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 ${\displaystyle k=1,2,\ldots .}$

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

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

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

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

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

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

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

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

${\displaystyle \|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},}$

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

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

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

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

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

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

Man ergänzt Nullvektoren ${\displaystyle 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 ${\displaystyle \|x^{(k+i+1)}-x^{(k+i)}\|}$ nach oben abschätzen zu können.

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

${\displaystyle {\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}}}$

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 ${\displaystyle k,n\in \mathbb {N} _{0}}$:

${\displaystyle {\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}}}$

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

${\displaystyle \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 ${\displaystyle \left(x^{(k)}\right)_{k\in \mathbb {N} _{0}}}$ eine Cauchy-Folge.

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

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

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

${\displaystyle \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 }$

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

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

${\displaystyle \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 ${\displaystyle n\in \mathbb {N} }$ un die Ungleichung "${\displaystyle \leq }$" bleibt erhalten beim Grenzübergang „${\displaystyle n\to \infty }$“.

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

${\displaystyle \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\|}$

Wenn nun einer solcher Grenzwert ${\displaystyle x^{*}\in D}$ und eindeutig ist für eine Kontraktion ${\displaystyle 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 ${\displaystyle x^{*}}$ der Fixpunktinteration übertragen. Der Grenzübergang „${\displaystyle n\to \infty }$“ in (BF3.1) liefert schließlich die Abschätzung (BF3).

q.e.d.

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

${\displaystyle \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 ${\displaystyle L\in (0,1)}$ ist.

Der Ausdruck

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

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

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

${\displaystyle {\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

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

so dass mit (5.21) folgt:

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

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

(5.22) ${\displaystyle k(\varepsilon )=\lceil a\rceil }$

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

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

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

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

Wir geben dazu ein Beispiel.

Es sei

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

Dann hat man

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

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

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

gilt offenbar

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

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

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

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

sowie

${\displaystyle 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 ${\displaystyle g}$ eine Kontraktion. Die folgende Tabelle liefert für den Startwert ${\displaystyle x_{0}:=0.55}$ ausgewählte Iterierte des Verfahrens:

${\displaystyle {\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 ${\displaystyle k=12}$ genauer betrachtet werden. Die Fehlerabschätzung (5.20) liefert in diesem Fall

${\displaystyle {\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},}$

${\displaystyle {\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

${\displaystyle |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.

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

${\displaystyle |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 ${\displaystyle k(\varepsilon ):=4}$ als Stoppzahl, während die a priori Abschätzung in (5.22) mit

${\displaystyle 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 ${\displaystyle k(\varepsilon ):=5}$ macht.

• Konvexkombination

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

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.