Diese Lernressoure zum Thema QS-Zerlegung kann als Wiki2Reveal Folien Wiki2Reveal -Darstellung handschriftlich im Browser beschriftet werden.
Lösung mittels QS -Zerlegung
Bearbeiten
Für eine QS-Zerlegung stellen wir zunächst fest, dass sich eine Matrix mit maximalen Spaltenrang in ein Produkt von
einer orthogonalen quadratischen Matrix
Q
∈
R
n
×
n
{\displaystyle Q\in \mathbb {R} ^{n\times n}}
erweiterten oberen Dreiecksmatrix
S
∈
R
n
×
k
{\displaystyle S\in \mathbb {R} ^{n\times k}}
Lemma - QS-Zerlegung
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}
A
=
Q
S
{\displaystyle A=QS}
A
{\displaystyle A}
Q
∈
R
n
×
n
{\displaystyle Q\in \mathbb {R} ^{n\times n}}
orthogonale und
S
∈
R
n
×
k
{\displaystyle S\in \mathbb {R} ^{n\times k}}
0
:=
(
0
)
∈
R
(
n
−
k
)
×
k
{\displaystyle \mathbf {0} :=(0)\in \mathbb {R} ^{(n-k)\times k}}
S
=
(
R
0
)
∈
R
n
×
k
,
R
:=
(
∗
…
∗
⋮
⋱
⋮
0
…
∗
)
∈
R
k
×
k
,
{\displaystyle S={\begin{pmatrix}R\\\mathbf {0} \end{pmatrix}}\in \mathbb {R} ^{n\times k},R:={\begin{pmatrix}*&\ldots &*\\\vdots &\ddots &\vdots \\0&\ldots &*\end{pmatrix}}\in \mathbb {R} ^{k\times k},}
Dann gilt für die obere Dreiecksmatrix
R
{\displaystyle R}
(i)
det
(
R
)
≠
0
{\displaystyle \det(R)\neq 0}
(ii)
cond
2
(
A
T
A
)
=
(
cond
2
(
R
)
)
2
{\displaystyle \operatorname {cond} _{2}(A^{T}A)={\big (}\operatorname {cond} _{2}(R){\big )}^{2}}
Beweis - QS-Zerlegungslemma
Bearbeiten
Der Beweis gliedert sich in folgende Schritte:
Beweisschritt 1 - Einsetzung
Bearbeiten
Da
Q
{\displaystyle Q}
orthogonale Matrix und
A
=
Q
S
{\displaystyle A=QS}
(
Q
S
)
T
=
S
T
Q
T
{\displaystyle (QS)^{T}=S^{T}Q^{T}}
A
T
A
=
S
T
Q
T
⏟
=
A
T
Q
S
⏟
=
A
=
S
T
S
=
(
R
T
0
)
(
R
0
)
=
R
T
R
.
{\displaystyle A^{T}A=\underbrace {S^{T}Q^{T}} _{=A^{T}}\,\underbrace {QS} _{=A}=S^{T}S={\begin{pmatrix}R^{T}&\mathbf {0} \end{pmatrix}}{\begin{pmatrix}R\\\mathbf {0} \end{pmatrix}}=R^{T}R.}
Dabei wurde u.a. verwendet, dass für orthogonale Matrizen
Q
{\displaystyle Q}
s
∈
R
n
{\displaystyle s\in \mathbb {R} ^{n}}
(
Q
s
)
T
Q
s
=
⟨
Q
s
,
Q
s
⟩
=
⟨
s
,
s
⟩
=
s
T
s
{\displaystyle (Qs)^{T}Qs=\langle Qs,Qs\rangle =\langle s,s\rangle =s^{T}s}
Beweisschritt 2 - Betrachtung des Ranges
Bearbeiten
Wegen
Rang
(
A
)
=
k
{\displaystyle \operatorname {Rang} (A)=k}
0
≠
det
(
A
T
A
)
=
det
(
R
T
R
)
=
(
det
(
R
)
)
2
{\displaystyle 0\neq \det(A^{T}A)=\det(R^{T}R)={\big (}\det(R){\big )}^{2}}
Damit gilt
d
e
t
(
A
T
A
)
>
0
{\displaystyle det(A^{T}A)>0}
d
e
t
(
R
)
≠
0
{\displaystyle det(R)\not =0}
Beweisschritt 3 - Kondition der Matrix
Bearbeiten
Ferner erhält man durch die Gleichheit von
A
T
A
=
R
T
R
{\displaystyle A^{T}A=R^{T}R}
cond
2
(
A
T
A
)
=
cond
2
(
R
T
R
)
.
{\displaystyle \operatorname {cond} _{2}(A^{T}A)=\operatorname {cond} _{2}(R^{T}R).}
Damit kann man die Konditionszahl von
A
T
A
{\displaystyle A^{T}A}
Konditionszahl der invertierbaren oberen Dreiecksmatrix
R
{\displaystyle R}
Beweisschritt 4 - Kondition der Matrix
Bearbeiten
Wendet man nun Lemma für die Konditionszahl auf die reguläre obere Dreiecksmatrix
R
{\displaystyle R}
cond
2
(
R
T
R
)
=
(
cond
2
(
R
)
)
2
.
{\displaystyle \operatorname {cond} _{2}(R^{T}R)=(\operatorname {cond} _{2}(R))^{2}.}
Beweisschritt 5 - Kondition der Matrix
Bearbeiten
Nach dem Lemma über Eigenwerte positiv definiter Matrizen und mit der Invertierbarkeit von
R
{\displaystyle R}
R
T
R
{\displaystyle R^{T}R}
cond
2
(
A
T
A
)
=
cond
2
(
R
T
R
)
=
(
cond
2
(
R
)
)
2
{\displaystyle \operatorname {cond} _{2}(A^{T}A)=\operatorname {cond} _{2}(R^{T}R)={\big (}\operatorname {cond} _{2}(R){\big )}^{2}}
Bemerkung - Fehlerquadratprobleme
Bearbeiten
In dem obige Satz für die QS-Zerlegung wurde der maximale Spaltenrang
k
{\displaystyle k}
A
∈
R
n
×
k
{\displaystyle A\in \mathbb {R} ^{n\times k}}
k
≤
n
{\displaystyle k\leq n}
A
{\displaystyle A}
Voraussetzungen Es seien
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}
R
∈
R
k
×
k
{\displaystyle R\in \mathbb {R} ^{k\times k}}
Q
∈
R
n
×
n
{\displaystyle Q\in \mathbb {R} ^{n\times n}}
orthogonale Matrix und
S
∈
R
n
×
k
{\displaystyle S\in \mathbb {R} ^{n\times k}}
Lemma - QS-Zerlegung . Weiter sei der Vektor
Q
T
b
∈
R
n
{\displaystyle Q^{T}b\in \mathbb {R} ^{n}}
Q
T
b
=
(
y
(
1
)
y
(
2
)
)
∈
R
n
,
y
(
1
)
∈
R
k
,
y
(
2
)
∈
R
n
−
k
.
{\displaystyle Q^{T}b={\begin{pmatrix}y^{(1)}\\y^{(2)}\end{pmatrix}}\in \mathbb {R} ^{n},y^{(1)}\in \mathbb {R} ^{k},y^{(2)}\in \mathbb {R} ^{n-k}.}
Folgerung QS-Zerlegung
Bearbeiten
Dann ist der Vektor
x
∗
∈
R
k
{\displaystyle x^{*}\in \mathbb {R} ^{k}}
min
x
∈
R
k
‖
A
x
−
b
‖
2
,
{\displaystyle \min _{x\in \mathbb {R} ^{k}}\|Ax-b\|_{2},}
x
∗
{\displaystyle x^{*}}
R
x
=
y
(
1
)
{\displaystyle Rx=y^{(1)}}
‖
A
x
∗
−
b
‖
2
=
‖
y
(
2
)
‖
2
.
{\displaystyle \|Ax^{*}-b\|_{2}=\left\|y^{(2)}\right\|_{2}.}
Bemerkung QS-Zerlegung
Bearbeiten
Ziel des Lösungsverfahrens für ein gesuchtest
x
{\displaystyle x}
A
x
{\displaystyle Ax}
b
{\displaystyle b}
y
(
1
)
{\displaystyle y^{(1)}}
y
(
2
)
{\displaystyle y^{(2)}}
R
x
=
y
(
1
)
{\displaystyle Rx=y^{(1)}}
R
{\displaystyle R}
mit
y
(
2
)
{\displaystyle y^{(2)}}
‖
y
(
2
)
‖
2
{\displaystyle \|y^{(2)}\|_{2}}
A
x
{\displaystyle Ax}
b
{\displaystyle b}
‖
A
x
∗
−
b
‖
2
=
‖
y
(
2
)
‖
2
{\displaystyle \|Ax^{*}-b\|_{2}=\|y^{(2)}\|_{2}}
x
∗
{\displaystyle x^{*}}
Für einen beliebigen Vektor
v
∈
R
k
{\displaystyle v\in \mathbb {R} ^{k}}
Q
{\displaystyle Q}
‖
Q
v
‖
2
2
=
⟨
Q
v
,
Q
v
⟩
=
⟨
v
,
v
⟩
=
‖
v
‖
2
2
(
∗
)
{\displaystyle \|Qv\|_{2}^{2}=\langle Qv,Qv\rangle =\langle v,v\rangle =\|v\|_{2}^{2}\quad (\ast )}
Ferner gilt für orthogonale Matrizen
Q
T
Q
=
I
{\displaystyle Q^{T}Q=I}
I
{\displaystyle I}
Beweisschritt 1 - Anwendung QS-Zerlegung
Bearbeiten
unter Verwendung des QS-Zerlegungssatzes und der Ersetzung von
A
=
Q
S
{\displaystyle A=QS}
‖
b
−
A
x
∗
‖
2
2
=
‖
(
Q
Q
T
)
b
−
Q
S
x
‖
2
2
=
‖
Q
(
Q
T
b
−
S
x
⏟
=
v
)
‖
2
2
=
‖
Q
T
b
−
S
x
⏟
=
v
‖
2
2
mit QS-Zerlegungssatz
=
‖
(
y
1
y
2
)
−
(
R
0
)
x
‖
2
2
=
‖
y
(
1
)
−
R
x
‖
2
2
+
‖
y
(
2
)
‖
2
2
{\displaystyle {\begin{array}{rcl}\|b-Ax^{*}\|_{2}^{2}&=&\left\|(QQ^{T})b-QSx\right\|_{2}^{2}={\bigg \|}Q{\big (}\underbrace {Q^{T}b-Sx} _{=v}{\big )}{\bigg \|}_{2}^{2}\\&=&{\big \|}\underbrace {Q^{T}b-Sx} _{=v}{\big \|}_{2}^{2}{\mbox{ mit QS-Zerlegungssatz}}\\&=&\left\|{\begin{pmatrix}y^{1}\\y^{2}\end{pmatrix}}-{\begin{pmatrix}R\\\mathbf {0} \end{pmatrix}}x\right\|_{2}^{2}=\left\|y^{(1)}-Rx\right\|_{2}^{2}+\left\|y^{(2)}\right\|_{2}^{2}\\\end{array}}}
Beweisschritt 2 - Anwendung QS-Zerlegung
Bearbeiten
Daraus folgt für einen beliebigen Vektor
x
^
∈
R
k
{\displaystyle {\widehat {x}}\in \mathbb {R} ^{k}}
‖
A
x
^
−
b
‖
2
≥
min
x
∈
R
k
‖
A
x
−
b
‖
2
=
‖
y
(
2
)
‖
2
{\displaystyle \|A{\widehat {x}}-b\|_{2}\geq \min _{x\in \mathbb {R} ^{k}}\|Ax-b\|_{2}=\left\|y^{(2)}\right\|_{2}}
Beweisschritt 3 - Eindeutige Lösung QS-Zerlegung
Bearbeiten
Ferner gilt
‖
b
−
A
x
‖
2
=
‖
y
(
2
)
‖
2
⇔
‖
y
(
1
)
−
R
x
‖
2
=
0
⇔
R
x
=
y
(
1
)
.
{\displaystyle \|b-Ax\|_{2}=\left\|y^{(2)}\right\|_{2}\Leftrightarrow \left\|y^{(1)}-Rx\right\|_{2}=0\Leftrightarrow Rx=y^{(1)}.}
Damit ist alles gezeigt.
q.e.d.
Nach dem Satz und dem Lemma zur QS-Zerlegung besitzen das
l
2
{\displaystyle l_{2}}
A
x
{\displaystyle Ax}
l
2
{\displaystyle l_{2}}
R
x
=
y
1
{\displaystyle Rx=y^{1}}
Beispiel - QS-Zerlegung
Bearbeiten
Wir betrachten das Fehlerquadratproblem mit den Daten
A
:=
(
1
0
1
3
1
4
1
7
)
,
b
:=
(
1
2
6
4
)
.
{\displaystyle A:={\begin{pmatrix}1&0\\1&3\\1&4\\1&7\end{pmatrix}},\quad b:={\begin{pmatrix}1\\2\\6\\4\end{pmatrix}}.}
Beispielschritt 1 - gesuchter Vektor
Bearbeiten
Wir suchen nun eine Vektor
x
∗
∈
R
2
{\displaystyle x^{*}\in \mathbb {R} ^{2}}
‖
A
x
−
b
‖
2
{\displaystyle \|Ax-b\|_{2}}
A
x
{\displaystyle Ax}
b
{\displaystyle b}
Beispielschritt 2 - QS-Zerlegung
Bearbeiten
Der Spaltenrang von
A
{\displaystyle A}
A
{\displaystyle A}
A
{\displaystyle A}
Q
T
b
{\displaystyle Q^{T}b}
R
{\displaystyle R}
y
(
1
)
{\displaystyle y^{(1)}}
y
(
2
)
{\displaystyle y^{(2)}}
R
:=
(
−
2
−
7
0
−
5
)
,
y
(
1
)
:=
(
−
13
2
−
5
2
)
,
y
(
2
)
:=
(
99
34
−
5
34
)
.
{\displaystyle R:={\begin{pmatrix}-2&-7\\0&-5\end{pmatrix}},\quad y^{(1)}:={\begin{pmatrix}-{\frac {13}{2}}\\-{\frac {5}{2}}\end{pmatrix}},\quad y^{(2)}:={\begin{pmatrix}{\frac {99}{34}}\\-{\frac {5}{34}}\end{pmatrix}}.}
Beispielschritt 3 - Lösung für das Ausgleichsproblem
Bearbeiten
Die Lösung von
R
x
=
y
(
1
)
{\displaystyle Rx=y^{(1)}}
(
−
2
−
7
0
−
5
)
(
x
1
x
2
)
=
(
−
13
2
−
5
2
)
{\displaystyle {\begin{pmatrix}-2&-7\\0&-5\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}={\begin{pmatrix}-{\frac {13}{2}}\\-{\frac {5}{2}}\end{pmatrix}}}
lautet
x
∗
=
(
x
1
∗
,
x
2
∗
)
T
:=
(
3
2
,
1
2
)
T
.
{\displaystyle x^{*}=(x_{1}^{*},x_{2}^{*})^{T}:=\left({\frac {3}{2}},{\frac {1}{2}}\right)^{T}.}
Beispielschritt 4 - Approximationsfehler des Ausgleichsproblems
Bearbeiten
Der zugehörige Approximationsfehler in der Euklidischen Norm ist gegeben durch
‖
b
−
A
x
∗
‖
2
=
‖
y
2
‖
2
=
‖
(
99
34
−
5
34
)
‖
2
=
9826
34
=
17
34
34
=
1
2
34
≈
2.915.
{\displaystyle \|b-Ax^{*}\|_{2}=\left\|y^{2}\right\|_{2}=\left\|{\begin{pmatrix}{\frac {99}{34}}\\-{\frac {5}{34}}\end{pmatrix}}\right\|_{2}={\frac {\sqrt {9826}}{34}}={\frac {17{\sqrt {34}}}{34}}={\frac {1}{2}}{\sqrt {34}}\approx 2.915.}
Vergleich der Lösungswege bzgl. Zerlegung
Bearbeiten
Wir wollen nun die beiden beschriebenen Lösungswege für das
l
2
{\displaystyle l_{2}}
QS-Zerlegungssatz dargestellten Weg, vergleichen.
In beiden Fällen muss die rechte Seite
b
{\displaystyle b}
A
x
=
b
{\displaystyle Ax=b}
k
2
2
{\displaystyle {\frac {k^{2}}{2}}}
Daten für das Gleichungssystem
Bearbeiten
Der Lösungsvektor
x
∈
R
k
{\displaystyle x\in \mathbb {R} ^{k}}
k
≤
n
{\displaystyle k\leq n}
n
{\displaystyle n}
‖
A
x
−
b
‖
2
{\displaystyle \|Ax-b\|_{2}}
Berechnungsaufwand - Cholesky-Zerlegung
Bearbeiten
Im Fall der Lösung der Normalgleichungen benötigt man ferner zur Berechnung der symmetrischen Matrix
A
T
A
{\displaystyle A^{T}A}
1
2
n
k
2
{\displaystyle {\frac {1}{2}}nk^{2}}
1
6
k
3
{\displaystyle {\frac {1}{6}}k^{3}}
A
x
−
b
{\displaystyle Ax-b}
n
⋅
k
{\displaystyle n\cdot k}
1
2
n
⋅
k
2
+
1
6
⋅
k
3
+
n
⋅
k
{\displaystyle {\frac {1}{2}}n\cdot k^{2}+{\frac {1}{6}}\cdot k^{3}+n\cdot k}
wesentliche Rechenoperationen erfordern, das sind
∼
1
2
n
k
2
{\displaystyle \sim {\frac {1}{2}}nk^{2}}
n
≫
k
{\displaystyle n\gg k}
∼
2
3
n
3
{\displaystyle \sim {\frac {2}{3}}n^{3}}
n
≈
k
{\displaystyle n\approx k}
Berechnungsaufwand - QS-Zerlegung
Bearbeiten
Für das sich aus dem QS-Zerlegungssatz ergebende Vorgehen benötigt man über die Matrix-Vektor-Multiplikation und die Lösung eines Dreieckssystems hinaus nur die Berechnung der QS-Zerlegung von
A
{\displaystyle A}
Vergleich n nahe bei k
Bearbeiten
Wenn
n
{\displaystyle n}
k
{\displaystyle k}
n
≈
k
{\displaystyle n\approx k}
Vergleich n groß im Vergleich zu k
Bearbeiten
Ist
n
{\displaystyle n}
k
{\displaystyle k}
Berechnungsaufwand und Konditionszahl
Bearbeiten
Letzterem Nachteil der QS-Zerlegung steht jedoch entgegen, dass bei ihr nach Lemma 4.6 die Konditionszahl
κ
:=
[
cond
2
(
A
T
A
)
]
1
/
2
{\displaystyle \kappa :=\left[\operatorname {cond} _{2}\left(A^{T}A\right)\right]^{1/2}}
A
{\displaystyle A}
κ
:=
cond
2
(
A
)
{\displaystyle \kappa :=\operatorname {cond} _{2}(A)}
κ
2
{\displaystyle \kappa ^{2}}
Beispiel - Vergleich Konditionszahl
Bearbeiten
Es sei
n
:=
6
,
k
:=
5
{\displaystyle n:=6,k:=5}
A
∈
R
6
×
5
{\displaystyle A\in \mathbb {R} ^{6\times 5}}
ε
>
0
{\displaystyle \varepsilon >0}
A
:=
(
1
1
1
1
1
ε
ε
ε
ε
ε
)
.
{\displaystyle A:={\begin{pmatrix}1&1&1&1&1\\\varepsilon &&&&\\&\varepsilon &&&\\&&\varepsilon &&\\&&&\varepsilon &\\&&&&\varepsilon \end{pmatrix}}.}
Damit ergibt sich für die Berechnung von
A
T
A
{\displaystyle A^{T}A}
A
T
A
=
(
1
+
ε
2
1
1
1
1
1
1
+
ε
2
1
1
1
1
1
1
+
ε
2
1
1
1
1
1
1
+
ε
2
1
1
1
1
1
1
+
ε
2
)
.
{\displaystyle A^{T}A={\begin{pmatrix}1+\varepsilon ^{2}&1&1&1&1\\1&1+\varepsilon ^{2}&1&1&1\\1&1&1+\varepsilon ^{2}&1&1\\1&1&1&1+\varepsilon ^{2}&1\\1&1&1&1&1+\varepsilon ^{2}\end{pmatrix}}.}
Maschinengenauigkeit 1
Bearbeiten
Es seien nun
b
:=
10
{\displaystyle b:=10}
r
:=
10
{\displaystyle r:=10}
e
p
s
=
5
⋅
10
−
10
{\displaystyle eps=5\cdot 10^{-10}}
ε
:=
0.5
10
−
5
{\displaystyle \varepsilon :=0.5_{10}-5}
ε
2
=
.25
10
−
10
{\displaystyle \varepsilon ^{2}=.25_{10}-10}
ε
2
{\displaystyle \varepsilon ^{2}}
Maschinengenauigkeit 2
Bearbeiten
Dann erhält man Gleitkomma-Darstellung für
1
+
ε
2
{\displaystyle 1+\varepsilon ^{2}}
g
l
(
1
+
ε
2
)
=
1
,
g
l
(
A
T
A
)
=
(
a
i
j
)
{\displaystyle gl(1+\varepsilon ^{2})=1,\quad gl(A^{T}A)=(a_{ij})}
a
i
j
:=
1
{\displaystyle a_{ij}:=1}
(
i
,
j
=
1
,
…
,
5
)
{\displaystyle (i,j=1,\ldots ,5)}
Maschinengenauigkeit 3 - Invertierbarkeit
Bearbeiten
Die Matrix
g
l
(
A
T
A
)
{\displaystyle gl(A^{T}A)}
Man errechnet hier für die Konditionszahl :
cond
2
(
A
T
A
)
=
5
+
ε
2
ε
2
≈
2
10
+
11
,
{\displaystyle \operatorname {cond} _{2}(A^{T}A)={\frac {5+\varepsilon ^{2}}{\varepsilon ^{2}}}\approx 2_{10}+11,}
[
cond
2
(
A
T
A
)
]
1
/
2
=
[
5
+
ε
2
ε
2
]
1
/
2
≈
4.5
10
+
5.
{\displaystyle \left[\operatorname {cond} _{2}(A^{T}A)\right]^{1/2}=\left[{\frac {5+\varepsilon ^{2}}{\varepsilon ^{2}}}\right]^{1/2}\approx 4.5_{10}+5.}
![{\displaystyle \kappa :=\left[\operatorname {cond} _{2}\left(A^{T}A\right)\right]^{1/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f77f0c426d1161392ccb76ecad1f6ca3ba779c8e)
![{\displaystyle \left[\operatorname {cond} _{2}(A^{T}A)\right]^{1/2}=\left[{\frac {5+\varepsilon ^{2}}{\varepsilon ^{2}}}\right]^{1/2}\approx 4.5_{10}+5.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3ba9ad7d57a54d41bd1ce88ee16c4a631faeaf8)