Mehrdimensionale Taylorentwicklung
Bearbeiten
Ausgangsfunktion der Ausgleichsrechnung
Bearbeiten
Im Allgemeinen wurde aus der linearen Ausgleichsrechnung die folgende Gleichung hergeleitet
F
(
x
)
=
b
T
b
⏟
=
F
(
0
V
)
−
(
2
A
T
b
)
⏟
=
∇
F
(
0
V
)
T
x
+
1
2
(
(
2
A
T
A
)
⏟
H
F
(
0
V
)
x
)
T
x
{\displaystyle F(x)=\underbrace {b^{T}b} _{=F(0_{V})}-{\underbrace {(2A^{T}b)} _{=\nabla F(0_{V})}}^{T}x+{\frac {1}{2}}(\underbrace {(2A^{T}A)} _{H_{F}(0_{V})}x)^{T}x}
Mehrdimensionale Taylorentwicklung
Bearbeiten
Diese wird nun als mehrdimensionale Taylorentwicklung einer quadratischen Funktion
F
:
R
k
→
R
{\displaystyle F:\mathbb {R} ^{k}\to \mathbb {R} }
F
(
x
)
=
‖
b
‖
2
2
⏟
=
F
(
0
V
)
−
⟨
2
A
T
b
⏟
=
∇
F
(
0
V
)
,
x
⟩
+
1
2
⟨
(
2
A
T
A
)
⏟
H
F
(
0
V
)
x
,
x
⟩
{\displaystyle F(x)=\underbrace {\|b\|_{2}^{2}} _{=F(0_{V})}-\langle \underbrace {2A^{T}b} _{=\nabla F(0_{V})},x\rangle +{\frac {1}{2}}\langle \underbrace {(2A^{T}A)} _{H_{F}(0_{V})}x,x\rangle }
Wir betrachten nun die obige quadratische Funktion, wobei wir
Rang
(
A
)
=
k
{\displaystyle \operatorname {Rang} (A)=k}
F
{\displaystyle F}
im Entwicklungspunkt
x
0
:=
0
V
{\displaystyle x_{0}:=0_{V}}
Gradienten
∇
F
(
0
V
)
=
−
2
A
T
{\displaystyle \nabla F(0_{V})=-2A^{T}}
an der Stelle
x
{\displaystyle x}
Gradienten
∇
F
(
x
)
=
2
A
T
A
x
−
2
A
T
b
,
{\displaystyle \nabla F(x)=2A^{T}Ax-2A^{T}b,}
die Hesse-Matrix
H
F
(
x
)
=
2
A
T
A
.
{\displaystyle H_{F}(x)=2A^{T}A.}
Notwendige Bedingung, dass
x
∗
∈
R
k
{\displaystyle x^{*}\in \mathbb {R} ^{k}}
F
{\displaystyle F}
∇
F
(
x
∗
)
=
0
{\displaystyle \nabla F(x^{*})=0}
x
∗
{\displaystyle x^{*}}
Normalgleichungen
A
T
A
x
=
A
T
b
(Normalengleichung)
{\displaystyle A^{T}Ax=A^{T}b\quad {\mbox{ (Normalengleichung) }}}
erfüllt. Nach dem Lemma zur Lösbarkeit der Normalengleichung ist dabei die (von
x
{\displaystyle x}
∇
2
F
(
x
)
:=
H
F
(
x
)
{\displaystyle \nabla ^{2}F(x):=H_{F}(x)}
x
∗
{\displaystyle x^{*}}
F
{\displaystyle F}
Satz - Lösbarkeit der Normalengleichung
Bearbeiten
Sei
A
∈
R
n
×
k
{\displaystyle A\in \mathbb {R} ^{n\times k}}
n
≥
k
{\displaystyle n\geq k}
Rang
(
A
)
=
k
{\displaystyle \operatorname {Rang} (A)=k}
min
x
∈
R
k
‖
b
−
A
x
‖
2
{\displaystyle \min _{x\in \mathbb {R} ^{k}}\|b-Ax\|_{2}}
eine eindeutige Lösung
x
∗
∈
R
k
{\displaystyle x^{*}\in \mathbb {R} ^{k}}
A
T
A
x
=
A
T
b
.
{\displaystyle A^{T}Ax=A^{T}b.}
Bemerkung - Symmetrie der Matrix
Bearbeiten
Die Matrix
A
T
A
∈
R
k
×
k
{\displaystyle A^{T}A\in \mathbb {R} ^{k\times k}}
A
∈
R
n
×
k
{\displaystyle A\in \mathbb {R} ^{n\times k}}
n
≥
k
{\displaystyle n\geq k}
a
i
∈
R
n
{\displaystyle a_{i}\in \mathbb {R} ^{n}}
A
{\displaystyle A}
A
T
A
=
(
⟨
a
i
,
a
j
⟩
)
1
≤
i
,
j
≤
k
∈
R
k
×
k
{\displaystyle A^{T}A={\big (}\langle a_{i},a_{j}\rangle {\big )}_{1\leq i,j\leq k}\in \mathbb {R} ^{k\times k}}
Die Symmetrie des Skalarprodukte
⟨
x
,
y
⟩
=
⟨
y
,
x
⟩
{\displaystyle \langle x,y\rangle =\langle y,x\rangle }
x
,
y
∈
R
n
{\displaystyle x,y\in \mathbb {R} ^{n}}
Bemerkung - Gleichungssystem mit invertierbarer Matrix
Bearbeiten
Die Invertierbarkeit von Matrizen bzgl. Matrixmultiplation betrachtet auf einem Matrizenraum von quadratischen betrachten bzgl. einer inneren Verknüpfung.
A
∈
R
n
×
k
{\displaystyle A\in \mathbb {R} ^{n\times k}}
n
>
k
{\displaystyle n>k}
A
{\displaystyle A}
k
{\displaystyle k}
A
T
A
∈
R
k
×
k
{\displaystyle A^{T}A\in \mathbb {R} ^{k\times k}}
k
{\displaystyle k}
A
T
A
∈
R
k
×
k
{\displaystyle A^{T}A\in \mathbb {R} ^{k\times k}}
Normalengleichung ,
A
^
:=
A
T
A
∈
R
k
×
k
{\displaystyle {\widehat {A}}:=A^{T}A\in \mathbb {R} ^{k\times k}}
b
^
:=
A
T
b
∈
R
k
{\displaystyle {\widehat {b}}:=A^{T}b\in \mathbb {R} ^{k}}
x
∈
R
k
{\displaystyle x\in \mathbb {R} ^{k}}
A
^
x
=
b
^
{\displaystyle {\widehat {A}}x={\widehat {b}}}
x
=
A
^
−
1
b
^
=
(
A
T
A
)
−
1
A
T
b
{\displaystyle x={\widehat {A}}^{-1}{\widehat {b}}=(A^{T}A)^{-1}A^{T}b}
Wir betrachten dazu ein Beispiel der Ausgleichsrechnung.
Beispiel - Ausgleichsgerade 1
Bearbeiten
Wir betrachten den Fall der sog. Ausgleichsgeraden . Wenn die
y
j
{\displaystyle y_{j}}
(
j
=
1
,
…
,
n
)
{\displaystyle (j=1,\ldots ,n)}
n
≥
2
{\displaystyle n\geq 2}
v
1
(
t
)
:=
1
,
v
2
(
t
)
:=
t
{\displaystyle v_{1}(t):=1,\quad v_{2}(t):=t}
mit
k
=
2
{\displaystyle k=2}
Beispiel - Ausgleichsgerade - 2
Bearbeiten
Somit erhält man approximierende Funktion
z
{\displaystyle z}
z
(
x
,
t
)
:=
x
1
+
x
2
t
,
t
∈
R
{\displaystyle z(x,t):=x_{1}+x_{2}t,\quad t\in \mathbb {R} }
und die gesuchten optimalen Koeffizienten der Geradengleichung werden durch den Vektor
x
:=
(
x
1
,
x
2
)
∈
R
2
{\displaystyle x:=(x_{1},x_{2})\in \mathbb {R} ^{2}}
Beispiel - Daten zu Zeitpunkten - 3
Bearbeiten
Als Daten haben wir z.B. wieder Daten
y
i
{\displaystyle y_{i}}
t
i
{\displaystyle t_{i}}
b
:=
(
y
1
,
y
2
,
…
,
y
n
)
T
∈
R
n
,
d
:=
(
t
1
,
t
2
,
…
,
t
n
)
T
∈
R
n
{\displaystyle b:=(y_{1},y_{2},\ldots ,y_{n})^{T}\in \mathbb {R} ^{n},\quad d:=(t_{1},t_{2},\ldots ,t_{n})^{T}\in \mathbb {R} ^{n}}
und den Spaltenvektor
e
{\displaystyle e}
e
:=
(
1
,
1
,
…
,
1
)
T
∈
R
n
{\displaystyle e:=(1,1,\ldots ,1)^{T}\in \mathbb {R} ^{n}}
Beispiel - Definition der Matrix A - 4
Bearbeiten
Nun hat
A
∈
R
n
×
2
{\displaystyle A\in \mathbb {R} ^{n\times 2}}
A
=
(
e
d
)
{\displaystyle A={\begin{pmatrix}e&d\end{pmatrix}}}
e
{\displaystyle e}
d
=
(
t
1
,
…
,
t
n
)
{\displaystyle d=(t_{1},\ldots ,t_{n})}
Beispiel - Berechnung der symmetrischen Matrix - 5
Bearbeiten
Weiter ist dann
A
T
A
=
(
e
T
d
T
)
(
e
d
)
=
(
e
T
e
e
T
d
e
T
d
d
T
d
)
,
A
T
b
=
(
e
T
b
d
T
b
)
.
{\displaystyle A^{T}A={\begin{pmatrix}e^{T}\\d^{T}\end{pmatrix}}{\begin{pmatrix}e&d\end{pmatrix}}={\begin{pmatrix}e^{T}e&e^{T}d\\e^{T}d&d^{T}d\end{pmatrix}},\quad A^{T}b={\begin{pmatrix}e^{T}b\\d^{T}b\end{pmatrix}}.}
Da der Rang der Matrix
A
{\displaystyle A}
A
T
A
∈
R
2
×
2
{\displaystyle A^{T}A\in \mathbb {R} ^{2\times 2}}
Beispiel - Inverse Matrix zur symmetrischen Matrix - 6
Bearbeiten
Für eine symmetrische invertierbare Matrix
B
∈
R
2
×
2
{\displaystyle B\in \mathbb {R} ^{2\times 2}}
B
−
1
=
(
b
11
b
12
b
12
b
22
)
−
1
=
1
b
11
b
22
−
b
12
2
(
b
22
−
b
12
−
b
12
b
11
)
.
{\displaystyle B^{-1}={\begin{pmatrix}b_{11}&b_{12}\\b_{12}&b_{22}\end{pmatrix}}^{-1}={\frac {1}{b_{11}b_{22}-b_{12}^{2}}}{\begin{pmatrix}b_{22}&-b_{12}\\-b_{12}&b_{11}\end{pmatrix}}.}
Beispiel - Lösung der Normalengleichung - 7
Bearbeiten
Somit lautet die Lösung der Normalgleichungen
A
T
A
x
=
A
T
b
{\displaystyle A^{T}Ax=A^{T}b}
x
∗
:=
(
A
T
A
)
−
1
A
T
b
=
1
(
e
T
e
)
(
d
T
d
)
−
(
e
T
d
)
2
(
d
T
d
−
e
T
d
−
e
T
d
e
T
e
)
(
e
T
b
d
T
b
)
{\displaystyle x^{*}:=\left(A^{T}A\right)^{-1}A^{T}b={\frac {1}{(e^{T}e)(d^{T}d)-(e^{T}d)^{2}}}{\begin{pmatrix}d^{T}d&-e^{T}d\\-e^{T}d&e^{T}e\end{pmatrix}}{\begin{pmatrix}e^{T}b\\d^{T}b\end{pmatrix}}}
Beispiel - Berechnung der Lösung - 8
Bearbeiten
Durch algebraische Umformungen erhält man demzufolge
x
∗
=
1
(
e
T
e
)
(
d
T
d
)
−
(
e
T
d
)
2
(
(
d
T
d
)
(
e
T
b
)
−
(
d
T
b
)
(
e
T
d
)
(
e
T
e
)
(
d
T
b
)
−
(
e
T
d
)
(
e
T
b
)
)
.
{\displaystyle x^{*}={\frac {1}{(e^{T}e)(d^{T}d)-(e^{T}d)^{2}}}{\begin{pmatrix}\left(d^{T}d\right)\left(e^{T}b\right)-\left(d^{T}b\right)\left(e^{T}d\right)\\(e^{T}e)(d^{T}b)-(e^{T}d)(e^{T}b)\end{pmatrix}}.}
Beispiel - Berechnung von Termen in der Lösung - 9
Bearbeiten
Dabei hat man
e
T
e
=
n
,
e
T
d
=
∑
j
=
1
n
t
j
,
e
T
b
=
∑
j
=
1
n
y
j
,
d
T
d
=
∑
j
=
1
n
t
j
2
,
d
T
b
=
∑
j
=
1
n
t
j
y
j
.
{\displaystyle e^{T}e=n,\quad e^{T}d=\sum _{j=1}^{n}t_{j},\quad e^{T}b=\sum _{j=1}^{n}y_{j},\quad d^{T}d=\sum _{j=1}^{n}t_{j}^{2},\quad d^{T}b=\sum _{j=1}^{n}t_{j}y_{j}.}
Beispiel - Einsetzung von Termen in die Lösung - 10
Bearbeiten
Durch Einsetzen erhält man:
x
∗
=
1
n
⋅
(
∑
j
=
1
n
t
j
2
)
−
(
∑
j
=
1
n
t
j
)
2
(
(
∑
j
=
1
n
t
j
2
)
(
∑
j
=
1
n
y
j
)
−
(
∑
j
=
1
n
t
j
y
j
)
(
∑
j
=
1
n
t
j
)
n
(
∑
j
=
1
n
t
j
y
j
)
−
(
∑
j
=
1
n
t
j
)
(
∑
j
=
1
n
y
j
)
)
.
{\displaystyle x^{*}={\frac {1}{n\cdot \left(\sum _{j=1}^{n}t_{j}^{2}\right)-\left(\sum _{j=1}^{n}t_{j}\right)^{2}}}{\begin{pmatrix}\left(\sum _{j=1}^{n}t_{j}^{2}\right)\left(\sum _{j=1}^{n}y_{j}\right)-\left(\sum _{j=1}^{n}t_{j}y_{j}\right)\left(\sum _{j=1}^{n}t_{j}\right)\\n\left(\sum _{j=1}^{n}t_{j}y_{j}\right)-\left(\sum _{j=1}^{n}t_{j}\right)\left(\sum _{j=1}^{n}y_{j}\right)\end{pmatrix}}.}
Beispiel - Berechnung der Ausgleichsgerade für konkrete Wertepaare - 11
Bearbeiten
Beispielsweise für die
n
=
8
{\displaystyle n=8}
t
j
1
2
3
4
5
6
7
8
y
j
1.75
2.18
2.63
3.24
3.69
4.16
4.55
5.29
{\displaystyle {\begin{array}{|l||c|c|c|c|c|c|c|c|}\hline t_{j}&1&2&3&4&5&6&7&8\\\hline y_{j}&1.75&2.18&2.63&3.24&3.69&4.16&4.55&5.29\\\hline \end{array}}}
Beispiel - Berechnung von Termen in der Lösung - 12
Bearbeiten
Wendet man die obigen Überlegungen auf die Beispieldaten an, erhält man
∑
j
=
1
8
t
j
=
36
,
∑
j
=
1
8
y
j
=
27.49
,
∑
j
=
1
8
t
j
2
=
204
,
∑
j
=
1
8
t
j
y
j
=
144.54.
{\displaystyle \sum _{j=1}^{8}t_{j}=36,\quad \sum _{j=1}^{8}y_{j}=27.49,\quad \sum _{j=1}^{8}t_{j}^{2}=204,\quad \sum _{j=1}^{8}t_{j}y_{j}=144.54.}
Beispiel - Berechnung von Termen in der Lösung - 13
Bearbeiten
Über Einsetzung in die Vektordefinition von
x
∗
{\displaystyle x^{*}}
x
∗
=
1
8
⋅
204
−
36
2
(
204
⋅
27.49
−
36
⋅
144.54
8
⋅
144.54
−
36
⋅
27.49
)
=
(
1.203
929
0.496
071
)
.
{\displaystyle x^{*}={\frac {1}{8\cdot 204-36^{2}}}{\begin{pmatrix}204\cdot 27.49-36\cdot 144.54\\8\cdot 144.54-36\cdot 27.49\end{pmatrix}}={\begin{pmatrix}1.203\ 929\\0.496\ 071\end{pmatrix}}.}
Die Ausgleichsgerade zu den gegebenen Daten lautet folglich
z
(
x
∗
,
t
)
:=
1.203
929
+
0.496
071
t
,
t
∈
R
.
{\displaystyle z(x^{*},t):=1.203\ 929+0.496\ 071t,\quad t\in \mathbb {R} .}
Beispiel - Maximaler Fehler der Lösung - 14
Bearbeiten
Der maximale relative Fehler der
z
(
x
∗
,
t
j
)
{\displaystyle z(x^{*},t_{j})}
y
j
{\displaystyle y_{j}}
max
1
≤
j
≤
8
|
y
j
−
z
(
x
∗
,
t
j
)
|
|
z
(
x
∗
,
t
j
)
|
=
0.016
243
{\displaystyle \max _{1\leq j\leq 8}{\frac {|y_{j}-z(x^{*},t_{j})|}{|z(x^{*},t_{j})|}}=0.016\ 243}
bzw. ungefähr 1.6%.
Normalengleichung für höhere k
Bearbeiten
Für
k
>
2
{\displaystyle k>2}
Cholesky-Zerlegung lösen. Diese selbst ist, wie man zeigen kann, numerisch stabil. Leider ist das Ausgleichproblem selbst aber häufig schlecht konditioniert .
Vandermonde-Matrix - Ansatzfunktionen
Bearbeiten
Man betrachte z. B. die Matrix
A
{\displaystyle A}
Vandermonde-Matrix
n
=
k
{\displaystyle n=k}
A
:=
(
1
t
1
…
t
1
k
−
1
1
t
2
…
t
2
k
−
1
⋮
⋮
⋱
⋮
1
t
k
…
t
k
k
−
1
)
.
{\displaystyle A:={\begin{pmatrix}1&t_{1}&\ldots &t_{1}^{k-1}\\1&t_{2}&\ldots &t_{2}^{k-1}\\\vdots &\vdots &\ddots &\vdots \\1&t_{k}&\ldots &t_{k}^{k-1}\end{pmatrix}}.}
Einfluss auf die Konditionszahl
Bearbeiten
Für
t
∈
[
0
,
1
]
{\displaystyle t\in [0,1]}
t
r
−
1
{\displaystyle t^{r-1}}
t
r
{\displaystyle t^{r}}
r
{\displaystyle r}
r
{\displaystyle r}
(
r
+
1
)
{\displaystyle (r+1)}
A
{\displaystyle A}
r
{\displaystyle r}
große Kondition von
A
{\displaystyle A}
n
=
k
{\displaystyle n=k}
Lemma - Eigenwerte positiv definiter Matrizen
Bearbeiten
Sei
A
∈
R
n
×
n
{\displaystyle A\in \mathbb {R} ^{n\times n}}
Sei
λ
{\displaystyle \lambda }
A
∈
R
n
×
n
{\displaystyle A\in \mathbb {R} ^{n\times n}}
x
∈
R
n
{\displaystyle x\in \mathbb {R} ^{n}}
Eigenvektor . Dann gilt mit
x
≠
0
V
{\displaystyle x\not =0_{V}}
0
<
⟨
A
x
,
x
⟩
=
⟨
λ
⋅
x
,
x
⟩
=
λ
⋅
⟨
x
,
x
⟩
⏟
>
0
{\displaystyle 0<\langle Ax,x\rangle =\langle \lambda \cdot x,x\rangle =\lambda \cdot \underbrace {\langle x,x\rangle } _{>0}}
Damit ist auch
λ
>
0
{\displaystyle \lambda >0}
Bemerkung - Normalengleichung - Taylorentwicklung
Bearbeiten
Durch die Darstellung der Funktion
F
{\displaystyle F}
2
⋅
A
T
A
{\displaystyle 2\cdot A^{T}A}
Hesse-Matrix . Die
k
×
k
{\displaystyle k\times k}
A
T
A
{\displaystyle A^{T}A}
Rang
(
A
)
=
k
{\displaystyle \operatorname {Rang} (A)=k}
Bemerkung - positiv semidefinit
Bearbeiten
Die
k
×
k
{\displaystyle k\times k}
A
T
A
{\displaystyle A^{T}A}
Rang
(
A
)
<
k
{\displaystyle \operatorname {Rang} (A)<k}
positiv semidefinit , denn es gilt für alle
x
∈
R
k
∖
{
0
v
}
{\displaystyle x\in \mathbb {R} ^{k}\setminus \{0_{v}\}}
⟨
A
T
A
x
,
x
⟩
=
(
A
T
A
x
)
T
x
=
x
T
A
T
A
x
=
(
A
x
)
T
A
x
=
⟨
A
x
,
A
x
⟩
≥
0
{\displaystyle \langle A^{T}Ax,x\rangle =(A^{T}Ax)^{T}x=x^{T}A^{T}Ax=(Ax)^{T}Ax=\langle Ax,Ax\rangle \geq 0}
Lemma - Konditionszahl Normalengleichung
Bearbeiten
Für eine reguläre Matrix
A
∈
R
k
×
k
{\displaystyle A\in \mathbb {R} ^{k\times k}}
Konditionszahl
cond
2
(
A
T
A
)
=
(
cond
2
(
A
)
)
2
.
{\displaystyle \operatorname {cond} _{2}(A^{T}A)=(\operatorname {cond} _{2}(A))^{2}.}
Dabei bezeichnet der Index 2 an der Konditionszahl, dass die Euklidische Norm bzw.
l
2
{\displaystyle l_{2}}
Nach dem Lemma über Eigenwerte positiv definiter Matrix
B
∈
R
k
×
k
{\displaystyle B\in \mathbb {R} ^{k\times k}}
λ
i
:=
λ
i
(
B
)
>
0
{\displaystyle \lambda _{i}:=\lambda _{i}(B)>0}
(
i
=
1
,
…
,
k
)
{\displaystyle (i=1,\ldots ,k)}
Beweis 1 - Eigenwert der inversen Matrix
Bearbeiten
Weiter hat wegen
B
x
i
=
λ
i
x
i
⇔
B
−
1
x
i
=
1
λ
i
x
i
{\displaystyle Bx^{i}=\lambda _{i}x^{i}\Leftrightarrow B^{-1}x^{i}={\frac {1}{\lambda _{i}}}x^{i}}
für Eigenvektoren
x
i
{\displaystyle x^{i}}
1
λ
i
{\displaystyle {\frac {1}{\lambda _{i}}}}
(
i
=
1
,
…
,
k
)
{\displaystyle (i=1,\ldots ,k)}
Beweis 2 - Berechnung der Konditionszahl
Bearbeiten
Es gilt folglich nach Satz zur Berechnung der Konditionszahl erhält man:
cond
2
(
B
)
=
‖
B
‖
2
‖
B
−
1
‖
2
=
λ
m
a
x
λ
min
,
{\displaystyle \operatorname {cond} _{2}(B)=\|B\|_{2}\left\|B^{-1}\right\|_{2}={\frac {\lambda _{m}ax}{\lambda _{\min }}},}
cond
(
A
)
=
(
max
‖
x
‖
=
1
‖
A
x
‖
)
/
(
min
‖
x
‖
=
1
‖
A
x
‖
)
.
{\displaystyle \operatorname {cond} (A)=\left(\max _{\|x\|=1}\|Ax\|\right)/\left(\min _{\|x\|=1}\|Ax\|\right).}
wobei
λ
max
=
max
‖
x
‖
=
1
‖
A
x
‖
{\displaystyle \lambda _{\max }=\max _{\|x\|=1}\|Ax\|}
λ
min
=
min
‖
x
‖
=
1
‖
A
x
‖
{\displaystyle \lambda _{\min }=\min _{\|x\|=1}\|Ax\|}
B
{\displaystyle B}
Beweis 3 - Orthonormalbasis aus Eigenvektoren
Bearbeiten
Indem man
x
{\displaystyle x}
λ
min
‖
x
‖
2
2
≤
x
T
B
x
≤
λ
max
‖
x
‖
2
2
,
x
∈
R
k
{\displaystyle \lambda _{\min }\|x\|_{2}^{2}\leq x^{T}Bx\leq \lambda _{\max }\|x\|_{2}^{2},\quad x\in \mathbb {R} ^{k}}
beweisen, wobei offenbar Gleichheit in der ersten bzw. zweiten Ungleichung für einen zu
λ
min
{\displaystyle \lambda _{\min }}
λ
max
{\displaystyle \lambda _{\max }}
Beweis 4 - Orthonormalbasis aus Eigenvektoren
Bearbeiten
Folglich schließt man
λ
min
=
min
‖
x
‖
2
=
1
x
T
B
x
,
λ
max
=
max
‖
x
‖
2
=
1
x
T
B
x
.
{\displaystyle \lambda _{\min }=\min _{\|x\|_{2}=1}x^{T}Bx,\quad \lambda _{\max }=\max _{\|x\|_{2}=1}x^{T}Bx.}
Wendet man diese Ergebnisse auf das Lemma über Eigenwerte positiv definiter Matrizen auf die positiv definite Matrix
A
T
A
∈
R
k
×
k
{\displaystyle A^{T}A\in \mathbb {R} ^{k\times k}}
Beweis 5 - Satz zur Berechnung der Konditionszahl
Bearbeiten
so erhält man mit dem Satz zur Berechnung der Konditionszahl
cond
2
(
A
T
A
)
=
λ
max
(
A
T
A
)
λ
min
(
A
T
A
)
=
max
‖
x
‖
2
=
1
x
T
(
A
T
A
)
x
min
‖
x
‖
2
=
1
x
T
(
A
T
A
)
x
=
max
‖
x
‖
2
=
1
‖
A
x
‖
2
2
min
‖
x
‖
2
=
1
‖
A
x
‖
2
2
=
[
cond
2
(
A
)
]
2
.
{\displaystyle \operatorname {cond} _{2}(A^{T}A)={\frac {\lambda _{\max(}A^{T}A)}{\lambda _{\min(}A^{T}A)}}={\frac {\max \limits _{\|x\|_{2}=1}x^{T}(A^{T}A)x}{\min \limits _{\|x\|_{2}=1}x^{T}(A^{T}A)x}}={\frac {\max \limits _{\|x\|_{2}=1}\|Ax\|_{2}^{2}}{\min \limits _{\|x\|_{2}=1}\|Ax\|_{2}^{2}}}=[\operatorname {cond} _{2}(A)]^{2}.}
q.e.d.
Bemerkung - Cholesky-Zerlegung
Bearbeiten
Es ist daher große Vorsicht bei Anwendung der Cholesky-Zerlegung für die Lösung der Normalgleichungen geboten. Prinzipiell ist sie nur zu empfehlen, wenn große Residuen
b
i
−
(
A
x
)
i
{\displaystyle b_{i}-(Ax)_{i}}
(
i
=
1
,
…
,
n
)
{\displaystyle (i=1,\ldots ,n)}
![{\displaystyle t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31a5c18739ff04858eecc8fec2f53912c348e0e5)
![{\displaystyle \operatorname {cond} _{2}(A^{T}A)={\frac {\lambda _{\max(}A^{T}A)}{\lambda _{\min(}A^{T}A)}}={\frac {\max \limits _{\|x\|_{2}=1}x^{T}(A^{T}A)x}{\min \limits _{\|x\|_{2}=1}x^{T}(A^{T}A)x}}={\frac {\max \limits _{\|x\|_{2}=1}\|Ax\|_{2}^{2}}{\min \limits _{\|x\|_{2}=1}\|Ax\|_{2}^{2}}}=[\operatorname {cond} _{2}(A)]^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ce1e696bb0cf2f13159f6dc0f6dd32729a34925)
