Kurs:Numerik I/Lösung mit QS-Zerlegung

Einleitung

Diese Lernressoure zum Thema QS-Zerlegung kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Folien können in der Wiki2Reveal-Darstellung handschriftlich im Browser beschriftet werden.

Lösung mittels QS-Zerlegung

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\in {ℝ}^{n\times n}$ und
• erweiterten oberen Dreiecksmatrix $S\in {ℝ}^{n\times k}$

Lemma - QS-Zerlegung

Sei $A\in {ℝ}^{n\times k}$ mit $n\ge k$ und $\mathrm{Rang}(A)=k$ gegeben und $A=QS$ eine Zerlegung von $A$, wobei $Q\in {ℝ}^{n\times n}$ eine orthogonale und $S\in {ℝ}^{n\times k}$ eine Matrix der folgenden Gestalt ist mit $\mathrm{𝟎}:=(0)\in {ℝ}^{(n-k)\times k}$:

$S=\left(\begin{array}{c}R\\ \mathrm{𝟎}\end{array}\right)\in {ℝ}^{n\times k},R:=\left(\begin{array}{ccc}*& \dots & *\\ ⋮& \ddots & ⋮\\ 0& \dots & *\end{array}\right)\in {ℝ}^{k\times k},$

Dann gilt für die obere Dreiecksmatrix $R$:

(i) $\det (R)\ne 0$,

(ii) ${\mathrm{cond}}_2(A^{T}A)=({\mathrm{cond}}_2(R){)}^2$.

Beweis - QS-Zerlegungslemma

Der Beweis gliedert sich in folgende Schritte:

Beweisschritt 1 - Einsetzung

Da $Q$ eine orthogonale Matrix und $A=QS$ ist, gilt mit $(QS{)}^T=S^T{Q}^T$:

$A^{T}A=\underset{=A^T}{\underbrace{S^T{Q}^T}}\underset{=A}{\underbrace{QS}}=S^{T}S=\left(\begin{array}{cc}{R}^T& \mathrm{𝟎}\end{array}\right)\left(\begin{array}{c}R\\ \mathrm{𝟎}\end{array}\right)=R^{T}R.$

Dabei wurde u.a. verwendet, dass für orthogonale Matrizen $Q$ und $s\in {ℝ}^n$ gilt:

$(Qs{)}^{T}Qs=⟨Qs,Qs⟩=⟨s,s⟩=s^{T}s$

Beweisschritt 2 - Betrachtung des Ranges

Wegen $\mathrm{Rang}(A)=k$ ist nach Lemma 4.1 insbesondere

$0\ne \det (A^{T}A)=\det (R^{T}R)=(\det (R){)}^2$.

Damit gilt $det(A^{T}A)>0$ und $det(R)=0$ und (i) ist korrekt.

Beweisschritt 3 - Kondition der Matrix

Ferner erhält man durch die Gleichheit von $A^{T}A=R^{T}R$ aus Beweisschritt 1 die Gleichheit der Kondition

${\mathrm{cond}}_2(A^{T}A)={\mathrm{cond}}_2(R^{T}R).$

Damit kann man die Konditionszahl von $A^{T}A$ über die Konditionszahl der invertierbaren oberen Dreiecksmatrix $R$ berechnen.

Beweisschritt 4 - Kondition der Matrix

Wendet man nun Lemma für die Konditionszahl auf die reguläre obere Dreiecksmatrix $R$ an, erhält man:

${\mathrm{cond}}_2(R^{T}R)=({\mathrm{cond}}_2(R){)}^2.$

Beweisschritt 5 - Kondition der Matrix

Nach dem Lemma über Eigenwerte positiv definiter Matrizen und mit der Invertierbarkeit von $R$ sind die Eigenwerte der Matrix $R^{T}R$ positiv. Insgesamt erhält man mit Schritt 4 die Eigenschaft (ii) aus dem Lemma.

${\mathrm{cond}}_2(A^{T}A)={\mathrm{cond}}_2(R^{T}R)=({\mathrm{cond}}_2(R){)}^2$

q.e.d.

Bemerkung - Fehlerquadratprobleme

In dem obige Satz für die QS-Zerlegung wurde der maximale Spaltenrang $k$ der Matrix $A\in {ℝ}^{n\times k}$ mit $k\le n$ vorausgesetzt. Der folgende Satz gibt an, wie Fehlerquadratprobleme mittels einer QS-Zerlegung von $A$ gelöst werden können.

Satz - QS-Zerlegung

Voraussetzungen Es seien $A\in {ℝ}^{n\times k}$ mit $n\ge k$, $\mathrm{Rang}(A)=k$, $R\in {ℝ}^{k\times k}$ eine obere Dreiecksmatrix und $Q\in {ℝ}^{n\times n}$eine orthogonale Matrix und $S\in {ℝ}^{n\times k}$ gegeben wie in Lemma - QS-Zerlegung. Weiter sei der Vektor $Q^{T}b\in {ℝ}^n$ dargestellt in der Form

$Q^{T}b=\left(\begin{array}{c}{y}^{(1)}\\ y^{(2)}\end{array}\right)\in {ℝ}^n,y^{(1)}\in {ℝ}^k,y^{(2)}\in {ℝ}^{n-k}.$

Folgerung QS-Zerlegung

Dann ist der Vektor $x^{*}\in {ℝ}^k$ genau dann die eindeutige Lösung des linearen Ausgleichsproblems $\underset{x\in {ℝ}^k}{\min }\Vert Ax-b{\Vert }_2,$, wenn $x^{*}$ eindeutige die Lösung des Systems $Rx=y^{(1)}$ ist. Außerdem gilt für den Fehler $\Vert A{x}^{*}-b{\Vert }_2={\Vert y^{(2)}\Vert }_2.$

Bemerkung QS-Zerlegung

Ziel des Lösungsverfahrens für ein gesuchtest $x$ ist es, sich möglichst gut bzgl. der euklidschen Norm mit $Ax$ an den Vektor $b$ anzunähern. Die eindeutige Lösung des linearen Ausgleichsproblems liefert mit $y^{(1)}$ und $y^{(2)}$:

• $Rx=y^{(1)}$ ein Gleichungssystem mit einer einfach zu lösenden oberen Dreiecksmatrix $R$ und
• mit $y^{(2)}$ bzw. $\Vert y^{(2)}{\Vert }_2$ ein Maß für die minimale Abweichung von $Ax$ und $b$ über $\Vert A{x}^{*}-b{\Vert }_2=\Vert y^{(2)}{\Vert }_2$ bzgl. der Lösung $x^{*}$.

Beweis

Für einen beliebigen Vektor $v\in {ℝ}^k$ erhalten wir für eine orthogonale Matrix $Q$ eine längetreue Abbildung über:

$\Vert Qv{\Vert }_2^2=⟨Qv,Qv⟩=⟨v,v⟩=\Vert v{\Vert }_2^2(\ast )$

Ferner gilt für orthogonale Matrizen $Q^{T}Q=I$, wobei $I$ die Einheitsmatrix als neutrales Element der Matrixmultiplikation ist.

Beweisschritt 1 - Anwendung QS-Zerlegung

unter Verwendung des QS-Zerlegungssatzes und der Ersetzung von $A=QS$ erhält man:

$\begin{array}{ccc}\Vert b-A{x}^{*}{\Vert }_2^2& =& {\Vert (Q{Q}^T)b-QSx\Vert }_2^2=\Vert Q\left(\underset{=v}{\underbrace{Q^{T}b-Sx}}\right){\Vert }_2^2\\ & =& \Vert \underset{=v}{\underbrace{Q^{T}b-Sx}}{\Vert }_2^2\text{ mit QS-Zerlegungssatz}\\ & =& {\Vert \left(\begin{array}{c}{y}^1\\ y^2\end{array}\right)-\left(\begin{array}{c}R\\ \mathrm{𝟎}\end{array}\right)x\Vert }_2^2={\Vert y^{(1)}-Rx\Vert }_2^2+{\Vert y^{(2)}\Vert }_2^2\end{array}$

Beweisschritt 2 - Anwendung QS-Zerlegung

Daraus folgt für einen beliebigen Vektor $\hat{x}\in {ℝ}^k$

$\Vert A\hat{x}-b{\Vert }_2\ge \underset{x\in {ℝ}^k}{\min }\Vert Ax-b{\Vert }_2={\Vert y^{(2)}\Vert }_2$

Beweisschritt 3 - Eindeutige Lösung QS-Zerlegung

Ferner gilt

$\Vert b-Ax{\Vert }_2={\Vert y^{(2)}\Vert }_2\iff {\Vert y^{(1)}-Rx\Vert }_2=0\iff Rx=y^{(1)}.$

Damit ist alles gezeigt.

q.e.d.

Bemerkung

Nach dem Satz und dem Lemma zur QS-Zerlegung besitzen das $l_2$-Approximationsproblem, wobei man versucht $Ax$ in der $l_2$-Norm möglichst gut anzunähern, eine eindeutige Lösung. Dies ist äquivalent zu der eindeutigen Lösbarkeit des Systems $Rx=y^1$. Abschließend geben wir zu dem letzten Satz noch ein Beispiel.

Beispiel - QS-Zerlegung

Wir betrachten das Fehlerquadratproblem mit den Daten

$A:=\left(\begin{array}{cc}1& 0\\ 1& 3\\ 1& 4\\ 1& 7\end{array}\right),b:=\left(\begin{array}{c}1\\ 2\\ 6\\ 4\end{array}\right).$

Beispielschritt 1 - gesuchter Vektor

Wir suchen nun eine Vektor $x^{*}\in {ℝ}^2$, der den Abstand $\Vert Ax-b{\Vert }_2$ zwischen $Ax$ und $b$ minimiert.

Beispielschritt 2 - QS-Zerlegung

Der Spaltenrang von $A$ ist 2, da die beiden Spalten von $A$ nicht linear abhängig sind. Nun liefert die QS-Zerlegung von $A$ mit gleichzeitiger Berechnung von $Q^{T}b$ die folgende obere Dreiecksmatrix $R$ und die folgenden Vektoren $y^{(1)}$ und $y^{(2)}$:

$R:=\left(\begin{array}{cc}-2& -7\\ 0& -5\end{array}\right),y^{(1)}:=\left(\begin{array}{c}-\frac{13}{2}\\ -\frac{5}{2}\end{array}\right),y^{(2)}:=\left(\begin{array}{c}\frac{99}{34}\\ -\frac{5}{34}\end{array}\right).$

Beispielschritt 3 - Lösung für das Ausgleichsproblem

Die Lösung von $Rx=y^{(1)}$ bzw.

$\left(\begin{array}{cc}-2& -7\\ 0& -5\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)=\left(\begin{array}{c}-\frac{13}{2}\\ -\frac{5}{2}\end{array}\right)$

lautet

$x^{*}=(x_1^{*},x_2^{*}{)}^T:={(\frac{3}{2},\frac{1}{2})}^T.$

Beispielschritt 4 - Approximationsfehler des Ausgleichsproblems

Der zugehörige Approximationsfehler in der Euklidischen Norm ist gegeben durch

$\Vert b-A{x}^{*}{\Vert }_2={\Vert y^2\Vert }_2={\Vert \left(\begin{array}{c}\frac{99}{34}\\ -\frac{5}{34}\end{array}\right)\Vert }_2=\frac{\sqrt{9826}}{34}=\frac{17\sqrt{34}}{34}=\frac{1}{2}\sqrt{34}\approx 2.915.$

Vergleich der Lösungswege bzgl. Zerlegung

Wir wollen nun die beiden beschriebenen Lösungswege für das $l_2$-Problem, die Lösung der Normalgleichungen mittels Cholesky-Zerlegung und die Lösung über den in QS-Zerlegungssatz dargestellten Weg, vergleichen.

Gemeinsamkeiten

In beiden Fällen muss die rechte Seite $b$ des Systems $Ax=b$ von links mit einer Matrix multipliziert werden. Weiter sind bei der Cholesky-Zerlegung zwei und bei dem Weg über die QS-Zerlegung ein gestaffeltes lineares Gleichungssystem zu lösen. Da die Lösung eines solchen Systems nur etwa $\frac{k^2}{2}$ Multiplikationen und Divisionen erfordert, vernachlässigen wir hier diesen zusätzlichen Aufwand bei der Cholesky-Zerlegung.

Daten für das Gleichungssystem

Der Lösungsvektor $x\in {ℝ}^k$ hat in der Regel eine feste Dimension $k\le n$ während $n$ die Anzahl der Gleichungen für Daten angibt, die bzgl. $\Vert Ax-b{\Vert }_2$ in der euklidischen Norm minimiert werden soll.

Berechnungsaufwand - Cholesky-Zerlegung

Im Fall der Lösung der Normalgleichungen benötigt man ferner zur Berechnung der symmetrischen Matrix $A^{T}A$ etwa $\frac{1}{2}n{k}^2$ und für die Cholesky-Zerlegung etwa $\frac{1}{6}{k}^3$ wesentliche Rechenoperationen. Daneben erfordert die Berechnung des Residuenvektors $Ax-b$ weitere $n\cdot k$ Multiplikationen, so dass die zuletzt genannten Teilaufgaben zusammen ungefähr

$\frac{1}{2}n\cdot k^2+\frac{1}{6}\cdot k^3+n\cdot k$

wesentliche Rechenoperationen erfordern, das sind

$\sim \frac{1}{2}n{k}^2$ für $n\gg k$ und $\sim \frac{2}{3}{n}^3$ für $n\approx k$.

Berechnungsaufwand - QS-Zerlegung

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$.

Vergleich n nahe bei k

Wenn $n$ nahe bei $k$ liegt ($n\approx k$) benötigen im Vergleich der beiden Verfahren demnach für beide Wege etwa gleich viele wesentliche Rechenoperationen.

Vergleich n groß im Vergleich zu k

Ist $n$ sehr groß im Vergleich zu $k$ müssen über den Weg der QS-Zerlegung etwa doppelt so viele wesentliche Rechenoperationen durchgeführt werden, wie der Lösung über die Normalgleichungen (Cholesky).

Berechnungsaufwand und Konditionszahl

Letzterem Nachteil der QS-Zerlegung steht jedoch entgegen, dass bei ihr nach Lemma 4.6 die Konditionszahl $\kappa :={\left[{\mathrm{cond}}_2\left(A^{T}A\right)\right]}^{1/2}$ bzw. für quadratisches $A$ (vgl. Satz 4.5) die Zahl $\kappa :={\mathrm{cond}}_2(A)$ den Rundungsfehlereinfluss bei der Lösung des Dreieckssystems bestimmt, während dies bei dem Weg über die Normalgleichungen die Zahl ${\kappa }^2$ ist. Wir geben dazu ein (allerdings etwas extremes) Beispiel:

Beispiel - Vergleich Konditionszahl

Es sei $n:=6,k:=5$ und $A\in {ℝ}^{6\times 5}$ mit einem $\epsilon >0$ gegeben durch

$A:=\left(\begin{array}{ccccc}1& 1& 1& 1& 1\\ \epsilon & & & & \\ & \epsilon & & & \\ & & \epsilon & & \\ & & & \epsilon & \\ & & & & \epsilon \end{array}\right).$

Berechnung von A^TA

Damit ergibt sich für die Berechnung von $A^{T}A$:

$A^{T}A=\left(\begin{array}{ccccc}1+{\epsilon }^2& 1& 1& 1& 1\\ 1& 1+{\epsilon }^2& 1& 1& 1\\ 1& 1& 1+{\epsilon }^2& 1& 1\\ 1& 1& 1& 1+{\epsilon }^2& 1\\ 1& 1& 1& 1& 1+{\epsilon }^2\end{array}\right).$

Maschinengenauigkeit 1

Es seien nun $b:=10$ und $r:=10$ die Basis und Mantissenlänge des verwendeten Computers, so dass $eps=5\cdot 10^{-10}$ die zugehörige Maschinengenauigkeit ist. Weiter sei $\epsilon :=0.5_{10}-5$ und damit ${\epsilon }^2=.25_{10}-10$. Damit liegt ${\epsilon }^2$ unterhalb der zugehörigen Maschinengenauigkeit und wird als 0 gespeichert.

Maschinengenauigkeit 2

Dann erhält man Gleitkomma-Darstellung für $1+{\epsilon }^2$

$gl(1+{\epsilon }^2)=1,gl(A^{T}A)=(a_{ij})$ mit $a_{ij}:=1$ $(i,j=1,\dots ,5)$.

Maschinengenauigkeit 3 - Invertierbarkeit

Die Matrix $gl(A^{T}A)$ hat offenbar den Rang 1 und ist singulär.

Konditionszahl 4

Man errechnet hier für die Konditionszahl:

${\mathrm{cond}}_2(A^{T}A)=\frac{5+{\epsilon }^2}{{\epsilon }^2}\approx 2_{10}+11,$

${[{\mathrm{cond}}_2(A^{T}A)]}^{1/2}={\left[\frac{5+{\epsilon }^2}{{\epsilon }^2}\right]}^{1/2}\approx 4.5_{10}+5.$

Siehe auch

• Dreiecksmatrix
• orthogonale Matrix
• Konditionszahl
• Lemma - Eigenwerte positiv definiter Matrizen
• Lemma - Konditionszahl Normalengleichung

Seiteninformation

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

Wiki2Reveal

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/L%C3%B6sung%20mit%20QS-Zerlegung
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.