Diese Seite kann als Wiki2Reveal Folien
Bearbeiten
Zunächst wird die Fixpunktiteration auf Funktionen
g
:
D
→
D
{\displaystyle g:D\to D}
D
⊆
R
n
{\displaystyle D\subseteq \mathbb {R} ^{n}}
n
=
1
{\displaystyle n=1}
D
=
[
a
,
b
]
{\displaystyle D=[a,b]}
g
{\displaystyle g}
Für die Bestimmung eines Fixpunktes von
g
{\displaystyle g}
x
(
∗
)
∈
R
n
{\displaystyle x^{(*)}\in \mathbb {R} ^{n}}
g
(
x
(
∗
)
)
=
x
∗
{\displaystyle g(x^{(*)})=x^{*}}
x
(
k
+
1
)
:=
g
(
x
(
k
)
)
,
k
=
0
,
1
,
2
,
…
(FPI)
{\displaystyle x^{(k+1)}:=g(x^{(k)}),\quad k=0,1,2,\ldots {\mbox{ (FPI)}}}
mit einem gegebenen Startwert
x
(
0
)
∈
K
⊂
R
n
{\displaystyle x^{(0)}\in K\subset \mathbb {R} ^{n}}
Im Folgenden werden die Abkürzung (FPI) für Fixpunktiteration
x
(
k
+
1
)
:=
g
(
x
(
k
)
)
{\displaystyle x^{(k+1)}:=g(x^{(k)})}
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
(
∗
)
∈
D
⊂
R
n
{\displaystyle x^{(*)}\in D\subset \mathbb {R} ^{n}}
Bemerkung 2 - Bezug zu Nullstellenverfahren
Bearbeiten
Für eine Selbstabbildung
g
:
D
→
D
{\displaystyle g:D\to D}
D
⊆
R
n
{\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
g
:
D
→
D
{\displaystyle g:D\to D}
|
g
′
(
x
)
|
≤
L
{\displaystyle |g'(x)|\leq L}
Sei
D
⊆
R
n
{\displaystyle D\subseteq \mathbb {R} ^{n}}
‖
⋅
‖
:
R
n
→
R
+
{\displaystyle \|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{+}}
R
n
{\displaystyle \mathbb {R} ^{n}}
(Lipschitz-stetig) Eine Abbildung
g
:
D
→
R
n
{\displaystyle g:D\to \mathbb {R} ^{n}}
Lipschitz-stetig auf
D
{\displaystyle D}
L
>
0
{\displaystyle L>0}
‖
g
(
x
)
−
g
(
y
)
‖
≤
L
‖
x
−
y
‖
,
x
,
y
∈
D
(
L
S
S
)
.
{\displaystyle \|g(x)-g(y)\|\leq L\|x-y\|,\quad x,y\in D\quad (LSS).}
(Kontraktion) Eine Lipschitz-stetige Abbildung
g
:
D
→
D
{\displaystyle g:D\to D}
L
>
0
{\displaystyle L>0}
Kontraktion auf
D
{\displaystyle D}
L
<
1
{\displaystyle L<1}
Zusammenhang - partielle Ableitungen und Lipschitz-Stetigkeit
Bearbeiten
Sei nun speziell
g
∈
C
1
(
D
,
R
n
)
{\displaystyle g\in C^{1}(D,\mathbb {R} ^{n})}
D
⊆
R
n
{\displaystyle D\subseteq \mathbb {R} ^{n}}
g
:
D
⊆
R
n
→
R
n
{\displaystyle g:D\subseteq \mathbb {R} ^{n}\to \mathbb {R} ^{n}}
g
(
x
)
=
(
g
1
(
x
)
,
…
,
g
n
(
x
)
)
T
,
x
∈
D
{\displaystyle g(x)=(g_{1}(x),\ldots ,g_{n}(x))^{T},\quad x\in D}
und stetigen partiellen Ableitungen
∂
g
i
∂
x
j
(
x
)
{\displaystyle {\frac {\partial g_{i}}{\partial x_{j}}}(x)}
(
i
,
j
=
1
,
…
,
n
)
{\displaystyle (i,j=1,\ldots ,n)}
x
∈
D
{\displaystyle x\in D}
Für ein solches
g
{\displaystyle g}
L
{\displaystyle L}
g
i
{\displaystyle g_{i}}
g
{\displaystyle g}
Die Jacobi-Matrix ist mit
I
:=
{
1
,
…
,
n
}
{\displaystyle I:=\{1,\ldots ,n\}}
J
g
(
x
)
:=
(
∂
g
i
∂
x
j
(
x
)
)
i
,
j
∈
I
=
(
∂
g
1
∂
x
1
(
x
)
∂
g
1
∂
x
2
(
x
)
…
∂
g
1
∂
x
n
(
x
)
∂
g
2
∂
x
1
(
x
)
∂
g
2
∂
x
2
(
x
)
…
∂
g
2
∂
x
n
(
x
)
⋮
⋮
⋱
⋮
∂
g
n
∂
x
1
(
x
)
∂
g
n
∂
x
2
(
x
)
…
∂
g
n
∂
x
n
(
x
)
)
∈
R
n
×
n
{\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.
Bemerkung - Lipschitz-Stetigkeit im eindimensionalen Fall
Bearbeiten
Im eindimensionalen reellwertigen Fall bedeutet Lipschitz-Stetigkeit für differenzierbare Funktionen
f
:
D
→
R
{\displaystyle f:D\to \mathbb {R} }
f
′
(
x
o
)
{\displaystyle f'(x_{o})}
L
{\displaystyle L}
x
o
∈
D
⊆
R
{\displaystyle x_{o}\in D\subseteq \mathbb {R} }
|
f
′
(
x
o
)
|
=
lim
x
→
x
o
|
f
(
x
)
−
f
(
x
o
)
x
−
x
o
|
≤
lim
x
→
x
o
L
⋅
|
x
−
x
o
|
|
x
−
x
o
|
=
L
{\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
D
⊆
R
n
{\displaystyle D\subseteq \mathbb {R} ^{n}}
konvex , falls für je zwei Elemente
x
,
y
∈
D
{\displaystyle x,y\in D}
Konvexkombinationen von
x
{\displaystyle x}
y
{\displaystyle y}
D
{\displaystyle D}
x
,
y
∈
D
,
t
∈
[
0
,
1
]
⇒
(
1
−
t
)
⋅
x
+
t
⋅
y
∈
D
.
{\displaystyle x,y\in D,\quad t\in [0,1]\Rightarrow (1-t)\cdot x+t\cdot y\in D.}
Bemerkung - Mittelwertsatz der Differentialrechnung
Bearbeiten
Damit lässt sich bekanntlich das folgende Lemma aus dem Mittelwertsatz der Differentialrechnung ableiten (siehe auch Konvexkombination ).
Lemma - Jacobi-Matrix - Lipschitz-Stetigkeit
Bearbeiten
Es sei
g
∈
C
2
(
D
,
R
n
)
{\displaystyle g\in {\mathcal {C}}^{2}(D,\mathbb {R} ^{n})}
D
⊆
R
n
{\displaystyle D\subseteq \mathbb {R} ^{n}}
L
>
0
{\displaystyle L>0}
‖
J
g
(
x
)
‖
≤
L
,
x
∈
D
.
{\displaystyle \|{\mathcal {J}}_{g}(x)\|\leq L,\quad x\in D.}
Dann folgt die Abschätzung
‖
g
(
x
)
−
g
(
y
)
‖
≤
L
‖
x
−
y
‖
,
x
,
y
∈
D
.
{\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.
Beispiel 1 - eindimensionaler Definitionsbereich
Bearbeiten
Die Funktion
f
(
x
)
:=
x
2
{\displaystyle f(x):=x^{2}}
[
0
,
0.4
]
{\displaystyle [0,0.4]}
f
(
[
0
,
0.4
]
)
=
[
0
,
0.16
]
⊆
[
0
,
0.4
]
{\displaystyle f([0,0.4])=[0,0.16]\subseteq [0,0.4]}
und mit
L
:=
max
x
∈
[
0
,
0.4
]
(
2
x
)
=
0.8
{\displaystyle L:=\displaystyle \max _{x\in [0,0.4]}(2x)=0.8}
|
x
2
−
y
2
|
≤
0.8
|
x
−
y
|
,
x
,
y
∈
[
0
,
0.4
]
.
{\displaystyle \left|x^{2}-y^{2}\right|\leq 0.8|x-y|,\quad x,y\in [0,0.4].}
Beispiel 2 - eindimensionaler Definitionsbereich
Bearbeiten
Die Funktion
f
(
x
)
:=
x
{\displaystyle f(x):={\sqrt {x}}}
[
0
,
a
]
{\displaystyle [0,a]}
a
>
0
{\displaystyle a>0}
y
=
0
{\displaystyle y=0}
|
x
−
0
|
=
x
=
1
x
(
x
−
0
)
=
1
x
|
x
−
0
|
,
x
∈
(
0
,
a
]
{\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
lim
x
→
0
(
1
/
x
)
=
∞
{\displaystyle \lim _{x\to 0}(1/{\sqrt {x}})=\infty }
Beispiel - Aufgabe 3 - mehrdimensionaler Definitionsbereich
Bearbeiten
Der Definitionsbereich
D
:=
[
−
1
,
+
1
]
×
[
−
1
,
+
1
]
×
[
−
1
,
+
1
]
=
[
−
1
,
+
1
]
3
⊂
R
3
{\displaystyle D:=[-1,+1]\times [-1,+1]\times [-1,+1]=[-1,+1]^{3}\subset \mathbb {R} ^{3}}
g
:
D
→
D
{\displaystyle g:D\to D}
g
(
x
1
,
x
2
,
x
3
)
:=
(
x
1
2
+
x
3
2
10
,
x
2
+
x
3
5
,
x
3
2
5
)
{\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
L
>
0
{\displaystyle L>0}
g
:
D
→
D
{\displaystyle g:D\to D}
L
<
1
{\displaystyle L<1}
Der folgende sog. Banachsche Fixpunktsatz gibt an, dass die Fixpunktiteration (FPI) konvergiert, und zwar für allgemeines
n
{\displaystyle n}
g
{\displaystyle g}
x
(
0
)
∈
D
⊂
R
n
{\displaystyle x^{(0)}\in D\subset \mathbb {R} ^{n}}
D
{\displaystyle D}
g
{\displaystyle g}
Überdies liefert die Kontraktionseigenschaft unter den genannten Voraussetzungen die Existenz eines eindeutigen Fixpunktes. Die geforderte Kontraktionseigenschaft für die Iterationsfunktion
g
{\displaystyle g}
Sei
D
⊆
R
n
{\displaystyle D\subseteq \mathbb {R} ^{n}}
g
:
D
→
D
{\displaystyle g:D\to D}
‖
⋅
‖
:
R
n
→
R
o
+
{\displaystyle \|\cdot \|:\mathbb {R} ^{n}\to \mathbb {R} _{o}^{+}}
L
∈
(
0
,
1
)
{\displaystyle L\in (0,1)}
(BF1)
g
{\displaystyle g}
x
∗
∈
D
{\displaystyle x^{*}\in D}
(BF2) Für jeden Startpunkt
x
(
0
)
∈
D
{\displaystyle x^{(0)}\in D}
x
(
k
+
1
)
=
g
(
x
(
k
)
)
,
k
=
0
,
1
,
…
{\displaystyle x^{(k+1)}=g(x^{(k)}),\quad k=0,1,\ldots }
(
x
(
k
)
)
k
∈
N
o
{\displaystyle (x^{(k)})_{k\in \mathbb {N} _{o}}}
D
{\displaystyle D}
x
∗
{\displaystyle x^{*}}
(BF3)
‖
x
(
k
)
−
x
(
∗
)
‖
≤
L
1
−
L
‖
x
(
k
)
−
x
(
k
−
1
)
‖
≤
L
k
1
−
L
‖
x
(
1
)
−
x
(
0
)
‖
,
{\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\|,}
k
=
1
,
2
,
…
.
{\displaystyle k=1,2,\ldots .}
Zunächst wird die Eindeutigkeit des Fixpunktes durch Widerspruch und Anwendung der Kontraktionseigenschaft gezeigt.
Annahme: Es existieren zwei Fixpunkte
x
∗
,
y
∗
∈
D
{\displaystyle x^{*},y^{*}\in D}
g
{\displaystyle g}
‖
x
∗
−
y
∗
‖
=
‖
g
(
x
∗
)
−
g
(
y
∗
)
‖
≤
L
⋅
‖
x
∗
−
y
∗
‖
{\displaystyle \|x^{*}-y^{*}\|=\|g(x^{*})-g(y^{*})\|\leq L\cdot \|x^{*}-y^{*}\|}
Bearbeiten
Weil
x
∗
≠
y
∗
{\displaystyle x^{*}\not =y^{*}}
‖
x
∗
−
y
∗
‖
>
0
{\displaystyle \|x^{*}-y^{*}\|>0}
‖
x
∗
−
y
∗
‖
{\displaystyle \|x^{*}-y^{*}\|}
L
≥
1
{\displaystyle L\geq 1}
g
:
D
→
D
{\displaystyle g:D\to D}
0
<
L
<
1
{\displaystyle 0<L<1}
Bearbeiten
Also erhält man, dass
x
∗
=
y
∗
{\displaystyle x^{*}=y^{*}}
g
{\displaystyle g}
Bearbeiten
Sei nun der Startvektor
x
(
0
)
∈
D
{\displaystyle x^{(0)}\in D}
(
x
(
k
)
)
k
∈
N
o
{\displaystyle (x^{(k)})_{k\in \mathbb {N} _{o}}}
Bearbeiten
Für
x
(
k
)
∈
D
{\displaystyle x^{(k)}\in D}
g
:
D
→
D
{\displaystyle g:D\to D}
g
(
x
(
k
)
)
=
x
(
k
+
1
)
{\displaystyle g(x^{(k)})=x^{(k+1)}}
D
{\displaystyle D}
x
(
k
)
∈
D
{\displaystyle x^{(k)}\in D}
k
∈
N
0
)
{\displaystyle k\in \mathbb {N} _{0})}
Bearbeiten
Man erhält somit für
g
(
x
(
k
)
)
=
x
(
k
+
1
)
{\displaystyle g(x^{(k)})=x^{(k+1)}}
g
(
x
(
k
−
1
)
)
=
x
(
k
)
{\displaystyle g(x^{(k-1)})=x^{(k)}}
‖
x
(
k
+
1
)
−
x
(
k
)
‖
=
‖
g
(
x
(
k
)
)
−
g
(
x
(
k
−
1
)
)
‖
≤
L
‖
x
(
k
)
−
x
(
k
−
1
)
‖
,
k
∈
N
0
,
{\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},}
Bearbeiten
Wiederholt man diese Abschätzung mit
g
(
x
(
k
−
2
)
)
=
x
(
k
−
1
)
{\displaystyle g(x^{(k-2)})=x^{(k-1)}}
L
⋅
‖
x
(
k
)
−
x
(
k
)
‖
=
L
‖
g
(
x
(
k
−
1
)
)
−
g
(
x
(
k
−
2
)
)
‖
≤
L
2
‖
x
(
k
−
1
)
−
x
(
k
−
2
)
‖
{\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)}\|}
Bearbeiten
Durch rekursive Anwendung bis zu den Folgengliedern
x
(
0
)
,
x
(
1
)
∈
D
{\displaystyle x^{(0)},x^{(1)}\in D}
‖
x
(
k
+
1
)
−
x
(
k
)
‖
≤
L
k
‖
x
(
1
)
−
x
(
0
)
‖
{\displaystyle \|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
)
‖
{\displaystyle \|x^{(k+1)}-x^{(k)}\|}
Zur Vorbereitung der Cauchy-Folgeneigenschaft wird nun der Abstand von beliebigen Folgengliedern
‖
x
(
k
+
n
)
−
x
(
k
)
‖
{\displaystyle \|x^{(k+n)}-x^{(k)}\|}
n
∈
N
{\displaystyle n\in \mathbb {N} }
L
k
{\displaystyle L^{k}}
∑
k
=
0
∞
L
k
=
1
1
−
L
.
{\displaystyle \sum _{k=0}^{\infty }L^{k}={\frac {1}{1-L.}}}
Bearbeiten
Man ergänzt Nullvektoren
0
V
=
x
(
k
+
i
)
−
x
(
k
+
i
)
{\displaystyle 0_{V}=x^{(k+i)}-x^{(k+i)}}
‖
x
(
k
+
i
+
1
)
−
x
(
k
+
i
)
‖
{\displaystyle \|x^{(k+i+1)}-x^{(k+i)}\|}
Bearbeiten
Die vorhergehenden Überlegungen liefern die folgenden Abschätzungen für
k
,
n
∈
N
0
{\displaystyle k,n\in \mathbb {N} _{0}}
‖
x
(
k
+
n
)
−
x
(
k
)
‖
=
‖
x
k
+
n
+
x
(
k
+
1
)
−
x
(
k
+
1
)
⏟
=
0
V
−
x
(
k
)
‖
=
‖
(
x
(
k
+
1
)
−
x
(
k
)
)
+
(
x
(
k
+
2
)
−
x
(
k
+
1
)
)
+
…
+
(
x
(
k
+
n
)
−
x
(
k
+
n
−
1
)
)
‖
≤
‖
x
(
k
+
1
)
−
x
(
k
)
‖
+
‖
x
(
k
+
2
)
−
x
(
k
+
1
)
‖
+
…
+
‖
x
(
k
+
n
)
−
x
(
k
+
n
−
1
)
‖
≤
‖
x
(
k
+
1
)
−
x
(
k
)
‖
+
L
‖
x
(
k
+
1
)
−
x
(
k
)
‖
+
…
+
L
n
−
1
‖
x
(
k
+
1
)
−
x
(
k
)
‖
=
‖
x
(
k
+
1
)
−
x
(
k
)
‖
⋅
∑
k
=
0
n
−
1
L
k
≤
‖
x
(
k
+
1
)
−
x
(
k
)
‖
⋅
∑
k
=
0
∞
L
k
⏟
=
1
1
−
L
{\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}}}
Bearbeiten
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
∈
N
0
{\displaystyle k,n\in \mathbb {N} _{0}}
‖
x
(
k
+
n
)
−
x
(
k
)
‖
≤
‖
x
(
k
+
1
)
−
x
(
k
)
‖
⋅
1
1
−
L
≤
L
k
⋅
‖
x
(
1
)
−
x
(
0
)
‖
⏟
(
B
F
2.4
)
⋅
1
1
−
L
{\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}}}
Bearbeiten
Also gilt für alle
k
,
n
∈
N
0
{\displaystyle k,n\in \mathbb {N} _{0}}
‖
x
(
k
+
n
)
−
x
(
k
)
‖
≤
L
1
−
L
‖
x
(
k
)
−
x
(
k
−
1
)
‖
≤
L
k
1
−
L
‖
x
(
1
)
−
x
(
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
(
x
(
k
)
)
k
∈
N
0
{\displaystyle \left(x^{(k)}\right)_{k\in \mathbb {N} _{0}}}
Bearbeiten
Da
(
L
k
)
k
∈
N
{\displaystyle (L^{k})_{k\in \mathbb {N} }}
0
<
L
<
1
{\displaystyle 0<L<1}
ε
>
0
{\displaystyle \varepsilon >0}
k
ε
∈
N
{\displaystyle k_{\varepsilon }\in \mathbb {N} }
L
k
ε
<
ε
⋅
(
1
−
L
)
‖
x
(
1
)
−
x
(
0
)
‖
{\displaystyle L^{k_{\varepsilon }}<{\frac {\varepsilon \cdot (1-L)}{\left\|x^{(1)}-x^{(0)}\right\|}}}
Bearbeiten
Dies liefert für alle
k
,
n
∈
N
0
{\displaystyle k,n\in \mathbb {N} _{0}}
k
≥
k
ε
{\displaystyle k\geq k_{\varepsilon }}
‖
x
(
k
+
n
)
−
x
(
k
)
‖
≤
L
k
1
−
L
‖
x
(
1
)
−
x
(
0
)
‖
≤
L
k
ε
1
−
L
‖
x
(
1
)
−
x
(
0
)
‖
⏟
<
ε
<
ε
{\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 }
Bearbeiten
Da der Vektorraum
R
n
{\displaystyle \mathbb {R} ^{n}}
D
⊂
R
n
{\displaystyle D\subset \mathbb {R} ^{n}}
R
n
{\displaystyle \mathbb {R} ^{n}}
x
∗
∈
R
n
{\displaystyle x^{*}\in \mathbb {R} ^{n}}
D
{\displaystyle D}
D
{\displaystyle D}
Mit der Abschätzung (BF2.9) erhält man für alle
k
,
n
∈
N
0
{\displaystyle k,n\in \mathbb {N} _{0}}
‖
x
(
k
+
n
)
−
x
(
k
)
‖
≤
L
1
−
L
‖
x
(
k
)
−
x
(
k
−
1
)
‖
≤
L
k
1
−
L
‖
x
(
1
)
−
x
(
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
n
∈
N
{\displaystyle n\in \mathbb {N} }
≤
{\displaystyle \leq }
n
→
∞
{\displaystyle n\to \infty }
Mit der Abschätzung (BF2.9) erhält man für alle
k
,
n
∈
N
0
{\displaystyle k,n\in \mathbb {N} _{0}}
‖
x
∗
−
x
(
k
)
‖
≤
L
1
−
L
‖
x
(
k
)
−
x
(
k
−
1
)
‖
≤
L
k
1
−
L
‖
x
(
1
)
−
x
(
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
x
∗
∈
D
{\displaystyle x^{*}\in D}
g
{\displaystyle g}
x
∗
{\displaystyle x^{*}}
n
→
∞
{\displaystyle n\to \infty }
q.e.d.
Man beachte, dass man unter den Voraussetzungen des Banachschen Fixpunktsatzes mindestens lineare Konvergenz für die Fixpunktiteration hat, denn dann gilt
‖
x
k
+
1
−
x
∗
‖
=
‖
g
(
x
k
)
−
g
(
x
∗
)
‖
≤
L
‖
x
k
−
x
∗
‖
,
k
∈
N
0
,
{\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
L
∈
(
0
,
1
)
{\displaystyle L\in (0,1)}
Der Ausdruck
L
k
1
−
L
‖
x
(
1
)
−
x
(
0
)
‖
{\displaystyle {\frac {L^{k}}{1-L}}\left\|x^{(1)}-x^{(0)}\right\|}
in (BF2) kann, nachdem
x
1
{\displaystyle x^{1}}
k
∈
N
{\displaystyle k\in \mathbb {N} }
Er ermöglicht eine a priori Fehlerabschätzung für den Approximationsfehler
‖
x
k
−
x
∗
‖
{\displaystyle \left\|x^{k}-x^{*}\right\|}
L
∈
(
0
,
1
)
{\displaystyle L\in (0,1)}
ε
>
0
{\displaystyle \varepsilon >0}
L
k
1
−
L
‖
x
(
1
)
−
x
(
0
)
‖
≤
ε
⇔
k
log
(
L
)
≤
log
(
(
1
−
L
)
ε
‖
x
(
1
)
−
x
(
0
)
‖
)
⇔
k
≥
a
{\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
a
:=
log
(
(
1
−
L
)
ε
‖
x
(
1
)
−
x
(
0
)
‖
)
/
log
(
L
)
,
{\displaystyle a:=\log \left({\frac {(1-L)\varepsilon }{\|x^{(1)}-x^{(0)}\|}}\right)/\log(L),}
so dass mit (5.21) folgt:
k
≥
a
R
i
g
h
t
a
r
r
o
w
‖
x
(
k
+
1
)
−
x
∗
‖
≤
ε
.
{\displaystyle k\geq a\mathbb {R} ightarrow\left\|x^{(k+1)}-x^{*}\right\|\leq \varepsilon .}
Praktisch ist also spätestens in Schritt
k
:=
k
(
ε
)
{\displaystyle k:=k(\varepsilon )}
(5.22)
k
(
ε
)
=
⌈
a
⌉
{\displaystyle k(\varepsilon )=\lceil a\rceil }
die Fehlerabschätzung
‖
x
k
−
x
∗
‖
≤
ε
{\displaystyle \left\|x^{k}-x^{*}\right\|\leq \varepsilon }
⌈
a
⌉
{\displaystyle \lceil a\rceil }
≥
a
{\displaystyle \geq a}
Der mittlere Ausdruck in (5.20) kann im
k
{\displaystyle k}
‖
x
k
−
x
∗
‖
{\displaystyle \left\|x^{k}-x^{*}\right\|}
ε
>
0
{\displaystyle \varepsilon >0}
k
:=
k
(
ε
)
{\displaystyle k:=k(\varepsilon )}
L
1
−
L
‖
x
k
−
x
k
−
1
‖
≤
ε
{\displaystyle {\frac {L}{1-L}}\left\|x^{k}-x^{k-1}\right\|\leq \varepsilon }
erfüllt ist. In diesem Fall genügt
x
k
{\displaystyle x^{k}}
‖
x
k
−
x
∗
‖
≤
ε
{\displaystyle \left\|x^{k}-x^{*}\right\|\leq \varepsilon }
Wir geben dazu ein Beispiel.
Es sei
f
(
x
)
:=
x
−
e
−
x
,
x
∈
R
.
{\displaystyle f(x):=x-e^{-x},\quad x\in \mathbb {R} .}
Dann hat man
f
(
x
∗
)
=
0
{\displaystyle f(x^{*})=0}
x
∗
≈
0.567
143
29.
{\displaystyle x^{*}\approx 0.567\ 143\ 29.}
Diese Nullstelle
x
∗
{\displaystyle x^{*}}
g
(
x
)
:=
e
−
x
,
x
∈
R
{\displaystyle g(x):=e^{-x},\quad x\in \mathbb {R} }
gilt offenbar
g
(
x
∗
)
=
x
∗
⇔
f
(
x
∗
)
=
0
,
{\displaystyle g(x^{*})=x^{*}\Leftrightarrow f(x^{*})=0,}
so dass wir dazu die Fixpunktiteration
x
k
+
1
=
g
(
x
k
)
{\displaystyle x_{k+1}=g(x_{k})}
g
{\displaystyle g}
Dafür müssen wir zunächst die Voraussetzungen von Satz 5.15 überprüfen. Auf dem Intervall
D
:=
[
0.5
,
0.69
]
{\displaystyle D:=[0.5,0.69]}
g
{\displaystyle g}
g
(
D
)
=
[
e
−
0.69
,
e
−
0.5
]
⊆
[
0.5
,
0.61
]
⊆
D
{\displaystyle g(D)=[e^{-0.69},e^{-0.5}]\subseteq [0.5,0.61]\subseteq D}
sowie
L
:=
max
x
∈
[
0.5
,
0.69
]
|
g
′
(
x
)
|
=
max
x
∈
[
0.5
,
0.69
]
e
−
x
=
e
−
1
/
2
≈
0.606
531.
{\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
g
{\displaystyle g}
x
0
:=
0.55
{\displaystyle x_{0}:=0.55}
k
x
k
k
x
k
k
x
k
⋮
⋮
⋮
⋮
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
⋮
⋮
⋮
⋮
⋮
⋮
{\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
k
=
12
{\displaystyle k=12}
L
12
1
−
L
|
x
1
−
x
0
|
=
0.606
531
12
1
−
0.606
531
0.026
949
81
=
1.70
⋅
10
−
4
,
{\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},}
L
1
−
L
|
x
12
−
x
11
|
=
0.606
531
1
−
0.606
531
0.000
052
75
=
8.13
⋅
10
−
5
.
{\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
|
x
12
−
x
∗
|
≈
1.91
⋅
10
−
5
{\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
ε
=
0.007
6
{\displaystyle \varepsilon =0.007\ 6}
k
=
2
{\displaystyle k=2}
|
x
2
−
x
∗
|
≈
0.005
5
≤
ε
{\displaystyle |x_{2}-x^{*}|\approx 0.005\ 5\leq \varepsilon }
k
=
4
{\displaystyle k=4}
|
x
4
−
x
∗
|
≤
e
−
1
/
2
1
−
e
−
1
/
2
|
0.565
360
97
−
0.570
290
86
|
=
0.007
599
≤
ε
,
{\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
k
(
ε
)
:=
4
{\displaystyle k(\varepsilon ):=4}
a
=
log
(
(
1
−
L
)
ε
‖
x
1
−
x
0
‖
)
/
log
(
L
)
=
log
(
(
1
−
e
−
1
/
2
)
0.007
6
0.576
949
81
−
0.55
)
/
log
(
e
−
1
/
2
)
≈
4.397
{\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
k
(
ε
)
:=
5
{\displaystyle k(\varepsilon ):=5}
![{\displaystyle D=[a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d13519eb61083d06f01094987d2f7243de12aaa3)
![{\displaystyle x,y\in D,\quad t\in [0,1]\Rightarrow (1-t)\cdot x+t\cdot y\in D.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c1e86a4a0b36c4c8141a50e566ae2ef432100d0)
![{\displaystyle [0,0.4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6602c299ab60ec5c04ecd1f0ba203fe8d614ed23)
![{\displaystyle f([0,0.4])=[0,0.16]\subseteq [0,0.4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6798ad6000a33d2e2e9e10085cb92f65b8c601a7)
![{\displaystyle L:=\displaystyle \max _{x\in [0,0.4]}(2x)=0.8}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7f701f9ace900460ebfb5b40fbff5e5c76f5463)
![{\displaystyle \left|x^{2}-y^{2}\right|\leq 0.8|x-y|,\quad x,y\in [0,0.4].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62996a1d71f32de7a8c67d72f4d15430c43fafa3)
![{\displaystyle [0,a]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63d050b0ffe6cc6f635808b9a013366a60e6d0c0)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17a9f07a48df2631acae02d940713cd6cba13cf0)
![{\displaystyle D:=[-1,+1]\times [-1,+1]\times [-1,+1]=[-1,+1]^{3}\subset \mathbb {R} ^{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e34c5a4c0af79e2a999751da4cd7d9bdff257866)
![{\displaystyle D:=[0.5,0.69]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/319518bc2ea9a80ce21f47be142e7de8012e0827)
![{\displaystyle g(D)=[e^{-0.69},e^{-0.5}]\subseteq [0.5,0.61]\subseteq D}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d13cefbb6ec498dda687d17d6e2867011d96fbb)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd0eba99345cb9109b701881167be4c92bfa1f91)
