Diese Seite kann als Wiki2Reveal Folien
Einführung - mehrdimensionale Fixpunktiteration
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}}
Bemerkung 1 - Fixpunktiteration
Bearbeiten
Im Folgenden werden die Abkürzung (FPI) für Fixpunktiteration
x
(
k
+
1
)
:=
g
(
x
(
k
)
)
{\displaystyle x^{(k+1)}:=g(x^{(k)})}
Vollständigkeit des Grundraumes
Bearbeiten
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}}
Bemerkung 3 - Stetigkeit
Bearbeiten
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}
Definition - Lipschitz-stetig
Bearbeiten
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}
Bestimmung der Lipschitz-Konstante
Bearbeiten
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.
Definition - konvexe Menge
Bearbeiten
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}
Bemerkung - Banachsche Fixpunktsatz
Bearbeiten
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}
Bemerkung - Eindeutigkeit des Fixpunkt
Bearbeiten
Überdies liefert die Kontraktionseigenschaft unter den genannten Voraussetzungen die Existenz eines eindeutigen Fixpunktes. Die geforderte Kontraktionseigenschaft für die Iterationsfunktion
g
{\displaystyle g}
Satz - Banachscher Fixpunktsatz
Bearbeiten
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 .}
Beweis - Banachscher Fixpunktsatz
Bearbeiten
Zunächst wird die Eindeutigkeit des Fixpunktes durch Widerspruch und Anwendung der Kontraktionseigenschaft gezeigt.
Beweis (BF1) Eindeutigkeit Fixpunkt
Bearbeiten
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^{*}\|}
Beweisschritt (BF1.1) Eindeutigkeit Fixpunkt
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}
Beweisschritt (BF1.2) Eindeutigkeit Fixpunkt
Bearbeiten
Also erhält man, dass
x
∗
=
y
∗
{\displaystyle x^{*}=y^{*}}
g
{\displaystyle g}
Beweis (BF2) Konvergenz für beliebige Startpunkte
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}}}
Beweis (BF2.1) Konvergenz für beliebige Startpunkte
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})}
Beweis (BF2.2) Konvergenz für beliebige Startpunkte
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},}
Beweis (BF2.3) Konvergenz für beliebige Startpunkte
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)}\|}
Beweis (BF2.4) Konvergenz für beliebige Startpunkte
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)}\|}
Beweis (BF2.5) Geometrische Reihe
Bearbeiten
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.}}}
Beweis (BF2.6) Dreiecksungleichung und telekopierende Summe
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)}\|}
Beweis (BF2.7) Dreiecksungleichung und telekopierende Summe
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}}}
Beweis (BF2.8) Abschätzung von aufeinander folgenden Folgengliedern
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}}}
Beweis (BF2.9) Abschätzung für Cauchy-Folge
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}}}
Beweis (BF2.10) Begründung Cauchy-Folge
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\|}}}
Beweis (BF2.11) Begründung Cauchy-Folge
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 }
Beweis (BF2.12) Vollständigkeit und Cauchy-Folge
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}
Beweis (BF3) - Konvergenz
Bearbeiten
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 }
Beweis (BF3.1) - Konvergenz
Bearbeiten
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.
Konvergenzgeschwindigkeit
Bearbeiten
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)}
Konvergenzgeschwindigkeit
Bearbeiten
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} }
a-priori-Fehlerabschätzung
Bearbeiten
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.
Praktisches Vorgehen
Bearbeiten
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)
