Kurs:Numerik I/Orthonormalisierungsverfahren

Einleitung

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Einführung - Orthogonalisierungsverfahren

In diesem Abschnitt soll für eine gegebene Matrix $A\in {ℝ}^{n\times k}$ mit $1\le k\le n$ eine Zerlegung der Form

$A=QS$

bestimmt werden, wobei $Q\in {ℝ}^{n\times n}$ eine orthogonale Matrix ist und $S\in {ℝ}^{n\times n}$ eine um Nullzeilen ergänzte obere Dreiecksmatrix ist,

Orthogonale Matrix

Eine orthogonole eine reguläre (invertierbare) Matrix mit der Eigenschaft

$Q^{-1}=Q^T$

Wenn man nun das Matrixprodukt $Q^{-1}\cdot Q=Q^T\cdot Q=E_n$ berechnet, dann bilden die Spaltenvektoren $(q_1,\dots ,q_n)$ Orthonormalbasis vom ${ℝ}^n$ mit:

$Q^T\cdot Q=\left(\begin{array}{cccc}⟨q_1,q_1⟩& ⟨q_1,q_2⟩& \cdots & ⟨q_1,q_n⟩\\ ⟨q_2,q_1⟩& ⟨q_2,q_2⟩& \cdots & ⟨q_2,q_n⟩\\ ⋮& \ddots & \cdots & ⋮\\ ⟨q_n,q_1⟩& ⟨q_n,q_2⟩& \cdots & ⟨q_n,q_n⟩\end{array}\right)$.

Orthonormal Vektoren und Einheitsmatrix

• Die Orthogonalität der Spaltenvektoren $(q_1,\dots ,q_n)$ führt zu der Eigenschaft $⟨q_j,q_k⟩=0$ für $j=k$.
• Die Normalisierung der Basisvektoren $q_k\in {ℝ}^n$ führt zu der Eigenschaft $\Vert q_k\Vert =1$ und damit auch $\Vert q_k{\Vert }^2=⟨q_k,q_k⟩=1$, was den Diagonalelementen der Matrix $Q^T\cdot Q=E_n$ entspricht.

Um Nullzeilen ergänzte obere Dreieckmatrix

In der Zerlegung $A=QS$ ist $S$ mit einer oberen Dreiecksmatrix $R$, die wie folgt mit Nullzeilen ergänzt wird:

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

Im Fall $n=k$ ist demnach insbesondere $S=R$.

Ziel der QR/QS Zerlegung

Wie wir zeigen wollen, ermöglicht eine solche QR- bzw. QS-Zerlegung von $A$ sowohl die stabile Lösung linearer Gleichungssysteme $Ax=b$ als auch die stabile Lösung von Ausgleichsproblemen

$\underset{x\in {ℝ}^k}{\min }\Vert b-Ax{\Vert }_2.$

Dafür benötigen wir einige Eigenschaften orthogonaler Matrizen.

Elementare Eigenschaften orthogonaler Matrizen

In der Geometrie der Ebene kennt man die Kongruenzabbildungen, bei denen die Bilder von Strecken wieder Strecken der gleichen Länge abgebildet. Kongruenzabbildungen, wie Geradenspiegelungen sind dabei längentreu und winkeltreu, d.h. unter der Abbildung bleiben Winkel zwischen Strecken und die Länge von Strecken unverändert (invariant). Orthogonale Matrizen besitzen als Abbildung die Eigenschaft der Längeninvarianz.

Lemma - Längeninvarianz/Isometrie für orthogonale Matrizen

Sei $Q\in {ℝ}^{n\times n}$ eine orthogonale Matrix. Dann ist auch $Q^T$ eine orthogonale Matrix und es gilt

$\Vert Qx{\Vert }_2=\Vert x{\Vert }_2={\Vert Q^{T}x\Vert }_2,x\in {ℝ}^n.$

Bemerkung

Eine orthogonal Matrix kann man als Abbildung von ${ℝ}^n$ nach ${ℝ}^n$ auffassen. Eine orthogonal Matrix verändert dabei die Länge des Vektors nicht in der Euklidischen Norm $\Vert \cdot {\Vert }_2$. Der Begriff der Isometrie ist dabei allgemein für metrische Räumen definiert. Ein zentrische Streckung $Z_{\lambda }$ mit einem Streckungsfaktor $\lambda \notin \{+1,-1\}$ ist z.B. keine Isometrie, da unter der Abbildung der Bildvektor $Z_{\lambda }(x)$ die $|\lambda |$-fache Länge von $x$ besitzt.

Beweis

Der Beweis erfolgt in zwei Schritten:

• Man zeigt, dass auch die transponierte Matrix eine orthogonale Matrix ist.
• Man zeigt die Längeninvarianz unter Darstellung des Skalarproduktes als Matrixmultiplikation (d.h. $⟨x,y⟩=x^T\cdot y$, wobei $x,y\in {ℝ}^{n\times 1}$ als Spaltenvektoren aufgefasst werden und $x^T\cdot y$ als Matrizenprodukt einer $1\times n$-Matrix $x^T$ und einer $n\times 1$-Matrix $y$ ist.

Beweis 1 - inverse Matrix - orthogonale Matrix

Wegen

$(Q^T{)}^{-1}=(Q^{-1}{)}^{-1}=Q=(Q^T{)}^T$

ist auch $Q^T$ eine orthogonale Matrix.

Beweis 2 - Umformungen in einer Matrixmultiplikation

Des Weiteren hat man für $Q$

$\Vert Qx{\Vert }_2^2=(Qx{)}^{T}Qx=x^T{Q}^{T}Qx=x^T{Q}^{-1}Qx=x^{T}x=\Vert x{\Vert }_2^2$

und somit auch ${\Vert Q^{T}x\Vert }_2=\Vert x{\Vert }_2$ für die orthogonale Matrix $Q^T$.

q.e.d.

Bermerkung

Die Eigenschaft der Längentreue der durch $Q$ und $Q^T$ definierten linearen Abbildungen bezeichnet man auch als isometrisch bezüglich der Euklidischen Norm, bzw. als Isometrie.

Lemma - Euklidische Norm und Determinante orthogonaler Matrizen

Für die Operatornorm $\Vert \cdot {\Vert }_2:{ℝ}^{n\times n}\to {ℝ}_0^{+}$ einer linearen Abbildung und für die Determinante orthogonaler Matrizen gilt:

• (i) $\Vert Q{\Vert }_2={\Vert Q^T\Vert }_2=1$,
• (ii) $|\det (Q)|=|\det (Q^T)|=1$.

Beweis - Euklidische Norm und Determinante orthogonaler Matrizen

Der Beweis gliedert sich in zwei Teilaussagen

• (i) zur Operatornorm für lineare Abbildung und
• (ii) zur Determinate von orthogonalen Matrizen.

Beweis (i) Längeninvarianz/Isometrie

Wenn man das Lemma Längeninvarianz bzw. Isometrie für orthogonale Matrizen auf $Q$ und $Q^T$ anwendet, erhält man die Aussage (i) über die Definition der Operatornorm mit:

$\begin{array}{ccc}\Vert Q{\Vert }_2& :=& \underset{\Vert x{\Vert }_2=1}{\max }\Vert Qx{\Vert }_2\\ & \stackrel{IsometrieQ}{=}& \underset{\Vert x{\Vert }_2=1}{\max }\underset{=1}{\underbrace{\Vert x{\Vert }_2}}\\ & \stackrel{Isometrie{Q}^T}{=}& \underset{\Vert x{\Vert }_2=1}{\max }{\Vert Q^{T}x\Vert }_2=1\end{array}$

Beweis (ii) Längeninvarianz/Isometrie

Mit der Einheitsmatrix $E_n\in {ℝ}^{n\times n}$ und der Multiplikativität der Determinanten $\det (A\cdot B)=\det (A)\cdot \det (B)$ folgt die Aussage (ii) über die Eigenschaft, dass die transponierte Matrix $Q^T$ multiplikativ invers zu der Matrix $Q$ ist.

$\begin{array}{ccc}1& =& \det (E_n)=\det (Q\cdot Q^T)=\det (Q)\cdot \det (Q^T)\\ & =& [\det (Q){]}^2={[\det (Q^T)]}^2.\end{array}$

Dabei geht in die Gleichungskette ein, dass die Determinante der transponierten Matrix und der Matrix selbst gleich sind. q.e.d.

Korollar - Konditionszahl orthogonaler Matrizen

Seien $A\in {ℝ}^{n\times n}$ eine reguläre und $Q\in {ℝ}^{n\times n}$ eine orthogonale Matrix. Dann gilt für die Konditionszahl

${\mathrm{cond}}_2(QA)={\mathrm{cond}}_2(A).$

Beweis

Der Beweis gliedert sich in die folgenden Teile:

• Verwendung der Längeninvarianz/Isometrie für orthogonale Abbildungen

Beweis 1 - Längeninvarianz orthogonaler Abbildungen

Nach Lemma zur Längeninvarianz/Isometrie für orthogonale Abbildungen gilt $\Vert Qy{\Vert }_2=\Vert Ay{\Vert }_2$ für alle $y\in {ℝ}^n$. Mit $y:=Ax\in {ℝ}^n$ erhält man

$\Vert (Q\cdot A)\cdot x{\Vert }_2=\Vert Q\cdot (A\cdot x){\Vert }_2=\Vert Ax{\Vert }_2$

für $x\in {ℝ}^n$ und somit

Beweis 2 - Längeninvarianz orthogonaler Abbildungen

$\Vert A{\Vert }_2=\underset{\Vert x{\Vert }_2=1}{\max }\Vert Ax{\Vert }_2=\underset{\Vert x{\Vert }_2=1}{\max }\Vert QAx\Vert 2=\Vert QA{\Vert }_2.$

Weiter gilt mit Lemma 3.24 (i)

${\Vert A^{-1}\Vert }_2={\Vert A^{-1}{Q}^{T}Q\Vert }_2\le {\Vert A^{-1}{Q}^T\Vert }_2\Vert Q{\Vert }_2={\Vert A^{-1}{Q}^T\Vert }_2\le {\Vert A^{-1}\Vert }_2{\Vert Q^T\Vert }_2={\Vert A^{-1}\Vert }_2$

und folglich $\Vert A^{-1}{\Vert }_2={\Vert A^{-1}{Q}^T\Vert }_2$. Damit ergibt sich

${\mathrm{cond}}_2(QA)=\Vert QA{\Vert }_2{\Vert A^{-1}{Q}^{-1}\Vert }_2=\Vert QA{\Vert }_2{\Vert A^{-1}{Q}^T\Vert }_2=\Vert A{\Vert }_2{\Vert A^{-1}\Vert }_2={\mathrm{cond}}_2(A).$

q.e.d.

Multiplikation einer quadratischen Matrix $A$ von links mit einer orthogonalen Matrix führt also auf eine Matrix mit derselben Kondition wie $A$. Weiter gilt:

Lemma - Produkt orthogonaler Matrizen

Seien $Q_1,Q_2\in {ℝ}^{n\times n}$ orthogonale Matrizen. Dann ist auch $Q_1{Q}_2$ eine orthogonale Matrix.

Beweis.

Die Aussage des Lemma folgt aus

$(Q_1{Q}_2{)}^{-1}=Q_2^{-1}{Q}_1^{-1}=Q_2^T{Q}_1^T=(Q_1{Q}_2{)}^T.$

q.e.d.

3.4.2 Lösung linearer Gleichungssysteme mittels QR-Zerlegung

Wir betrachten nun wieder die Lösung eines linearen Gleichungssystems $Ax=b$ für eine reguläre Matrix $A\in {ℝ}^{n\times n}$ und beliebige rechte Seite $b\in {ℝ}^n$ und gehen davon aus, dass eine Zerlegung der Form $A=QR$ von $A$ mit einer orthogonalen Matrix $Q\in {ℝ}^{n\times n}$ und einer oberen Dreiecksmatrix $R\in {ℝ}^{n\times n}$ gegeben ist (vgl. (3.37) - (3.39)). Wegen Lemma 3.24 gilt offenbar

$\det (A)\ne 0\iff \det (R)\ne 0.$

Weiter hat man die Äquivalenzen

$Ax=b\iff QRx=b\iff Rx=Q^{T}b$

und mit Korollar 3.25 die Beziehungen

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

D. h., das Gleichungssystem $Ax=b$ ist äquivalent zu dem gestaffelten Gleichungssystem $Rx=Q^{T}b$, wobei die Matrix $R$ bezüglich der Spektralnorm keine schlechtere Kondition als $A$ aufweist und gemäß 3.40 ${\Vert Q^{T}b\Vert }_2=\Vert b{\Vert }_2$ gilt.

3.4.3 QR-Zerlegung mittels Gram-Schmidt-Orthogonalisierung

Es sei nun $A\in {ℝ}^{n\times n}$ eine quadratische Matrix mit $\det (A)\ne 0$ und es seien eine orthogonale Matrix $Q\in {ℝ}^{n\times n}$ und eine obere Dreiecksmatrix $R\in {ℝ}^{n\times n}$ gesucht, so dass

(3.41) $A=QR$

gilt. Schreiben wir $A,Q$ und $R$ mit Vektoren $a^j,q^j\in {ℝ}^n$ in der Form

$A=\left(\begin{array}{ccc}{a}^1& ...& a^n\end{array}\right),Q=\left(\begin{array}{ccc}{q}^1& ...& q^n\end{array}\right),R=\left(\begin{array}{ccc}{r}_{11}& ...& r_{1n}\\ & \ddots & ⋮\\ & & r_{nn}\end{array}\right),$

so ist die Gleichung (3.41) offenbar äquivalent mit den Gleichungen

(3.42) $a^j=\sum _{i=1}^j{r}_{ij}{q}^i,j=1,...,n,$

wobei $r_{ij}=0$ für $i>j$ berücksichtigt wurde. Dabei sind die $a^j$ $(j=1,...,n)$ linear unabhängig und die $q^j$ $(j=1,...,n)$ wegen der Orthogonalität von $Q$ paarweise orthonormal und damit auch linear unabhängig. Die Gleichungen (3.42) implizieren somit für $1\le s\le n$

(3.43) $\mathrm{span}\{a^1,...,a^s\}=\mathrm{span}\{q^1,...,q^s\}.$

Folglich suchen wir eine orthogonale Basis $\{q^1,...,q^n\}$ des ${ℝ}^n$, für welche die Gleichungen (3.42) erfüllt sind. Wir wollen im Folgenden zeigen, dass man eine solche durch Orthogonalisierung der $a^j$ $(j=1,...,n)$ mittels des aus der Linearen Algebra bekannten Gram-Schmidt-Orthonormierungsverfahrens erhält.

Sind $a^j$ $(j=1,...,n)$ die gegebenen Spalten von $A$, welche nach Voraussetzung eines Basis des ${ℝ}^n$ bilden, so lautet für diese das Gram-Schmidt-Orthonormierungsverfahren, wobei wir die durch das Verfahren erzeugten Vektoren gleich mit $q^j$ bezeichnen:

(3.44) ${\hat{q}}^j:=aj-\sum _{i=1}^{j-1}[(a^j{)}^T{q}^i]q^i,q^j:=\frac{{\hat{q}}^j}{\Vert {\hat{q}}^j{\Vert }_2},j=1,2,...,n.$

Bekanntlich gilt für die so erzeugten Vektoren $q^j$ $(j=1,...,n)$ die Identität (3.43) und sind diese paarweise orthonormal.

Aus den Gleichungen (3.44) leitet man unmittelbar die folgenden Gleichungen her:

$a^j={\Vert {\hat{q}}^j\Vert }_2{q}^j+\sum _{i=1}^{j-1}[(a^j{)}^T{q}^i]q^i,j=1,2,...,n.$

Wie ein Vergleich mit den Gleichungen (3.42) zeigt, erhält man demnach die gewünschte QR-Faktorisierung von $A$ für die Matrix $Q$ mit den durch das Gram-Schmidt-Verfahren erzeugten Vektoren $q^j$ $(j=1,...,n)$ und die obere Dreiecksmatrix $R$, welche folgende Elemente hat:

$r_{ij}:=(a^j{)}^T{q}^i,i=1,...,j-1,r_{jj}:={\Vert {\hat{q}}^j\Vert }_2(j=1,...,n).$

Der hier beschriebene Orthogonalisierungsprozess ist aber unter Umständen nicht gutartig, etwa für $\Vert {\hat{q}}^j{\Vert }_2\ll 1$ und damit $r_{jj}\ll 1$ (s. Beispiel 3.4 in Band 1 von Quarteroni/Sacco/Saleri und S. 177 bei Stoer). Mit wachsendem $j$ kann die Orthogonalität immer stärker verloren gehen. Deshalb werden zumeist andere Methoden, wie die im folgenden Abschnitt dargestellte, zur QR-Faktorisierung von $A$ herangezogen.

3.4.4 QS-Zerlegung mittels Householder-Transformationen

Sei nun allgemeiner $A\in {ℝ}^{n\times k}$ mit $1\le k\le n$ gegeben. Gegenstand dieses Abschnitts ist die Bestimmung einer Zerlegung der Form $A=QS$ mit einer orthogonalen Matrix $Q\in {ℝ}^{n\times n}$ und einer im Fall $n>k$ nichtquadratischen Matrix $S\in {ℝ}^{n\times k}$ wie in (3.39) mittels sog. Householder-Transformationen. In diesem Zusammenhang zeigen wir zunächst:

Lemma 3.27

Es sei $\omega \in {ℝ}^n$ ein Vektor mit $\Vert \omega {\Vert }_2=1$ und $\mathscr{H}\in {ℝ}^{n\times n}$ die Matrix

(3.45) $\mathscr{H}:=I-2\omega {\omega }^T.$

Dann gilt

(3.46) ${\mathscr{H}}^T=\mathscr{H}$ ($\mathscr{H}$ ist symmetrisch),

(3.47) ${\mathscr{H}}^2=I$ ($\mathscr{H}$ ist involutorisch),

(3.48) ${\mathscr{H}}^T\mathscr{H}=I$ ($\mathscr{H}$ ist orthogonal).

Beweis.

Die Beziehungen (3.46) und (3.47) ergeben sich aus

${\mathscr{H}}^T=I-2(\omega {\omega }^T{)}^T=I-2\omega {\omega }^T=\mathscr{H},$

${\mathscr{H}}^2=(I-2\omega {\omega }^T)(I-2\omega {\omega }^T)=I-2\omega {\omega }^T-2\omega {\omega }^T+4\omega \underset{=1}{\underbrace{({\omega }^T\omega )}}{\omega }^T=I.$

Die Identität (3.48) folgt aus (3.46) und (3.47).

q.e.d.

Eine Matrix vom Typ $\mathscr{H}$ (3.45) für ein $\omega \in {ℝ}^n$ mit $\Vert \omega {\Vert }_2=1$ nennen wir Householder-Matrix und eine lineare Abbildung

$h:{ℝ}^n\to {ℝ}^n,h(x):=\mathscr{H}x$

mit einer Householder-Matrix $\mathscr{H}\in {ℝ}^{n\times n}$ bezeichnen wir als Householder-Transformation.

Householder-Matrizen kann man dazu verwenden, einen Block von Komponenten eines gegebenen Vektors $x$ (durch Multiplikation mit einer solchen Matrix von links) zu Null zu setzen. Will man insbesondere alle Komponenten von $x$ außer der $m$-ten Komponente Null setzen, so muss man den Vektor $\omega$ zur Konstruktion von $\mathscr{H}$ so wählen, wie er im folgenden Lemma angegeben wird. Dabei ist wieder mit $e^m\in {ℝ}^n$ die $m$-te Spalte von $I\in {ℝ}^{n\times n}$ gemeint.

Lemma 3.28

Gegeben sei $x\in {ℝ}^n\setminus \{0\}$ mit $x\notin \mathrm{span}\{e^m\}$. Weiter sei

(3.49) $\omega :=\frac{x+\sigma e^m}{\Vert x+\sigma e^m{\Vert }_2}$

mit

(3.50) $\sigma :=\pm \Vert x{\Vert }_2.$

Dann hat man $\Vert \omega {\Vert }_2=1$ und für $\mathscr{H}:=I-2\omega {\omega }^T$

(3.51) $\mathscr{H}x=-\sigma e^m.$

Beweis.

Wegen $x\notin \mathrm{span}\{e^m\}$ ist der Nenner in (3.49) ungleich Null und damit $\omega$ in (3.49) wohldefiniert. Offenbar ist $\Vert \omega {\Vert }_2=1$. Ferner gilt

$\Vert x+\sigma e^m{\Vert }_2^2=\Vert x{\Vert }_2^2+2\sigma (e^m{)}^{T}x+{\sigma }^2=2\Vert x{\Vert }_2^2+2\sigma (e^m{)}^{T}x=2(x+\sigma e^m{)}^{T}x$

und damit

$2{\omega }^{T}x=\frac{2(x+\sigma e^m{)}^{T}x}{\Vert x+\sigma e^m{\Vert }_2}=\Vert x+\sigma e^m{\Vert }_2.$

Zusammen mit (3.49) gelangt man zu der Darstellung

$\mathscr{H}x=(I-2\omega {\omega }^T)x=x-\Vert x+\sigma e^m{\Vert }_2\omega =x-(x+\sigma e^m)=-\sigma e^m.$

Bemerkung 3.29

Zur Vermeidung von Stellenauslöschungen bei der Berechnung von (3.50) ist es offenbar sinnvoll, $\sigma :=\mathrm{sgn}(x_m)\Vert x{\Vert }_2$ zu wählen, wobei $x_m$ die $m$-te Komponente von $x$ bezeichnet.

Wir geben ein Beispiel.

Beispiel 3.30

Sei $x:=(1,1,1,1{)}^T$ und $m:=3$. Dann errechnen wir $\Vert x{\Vert }_2=2$ und setzen wir somit $\sigma :=\mathrm{sgn}(x_3)\Vert x{\Vert }_2=2$ sowie

$\omega :=\frac{x+\sigma e^m}{\Vert x+\sigma e^m{\Vert }_2}=\frac{1}{2\sqrt{3}}(1,1,3,1{)}^T.$

Es ergibt sich

$2\omega {\omega }^T=\frac{1}{6}\left(\begin{array}{c}1\\ 1\\ 3\\ 1\end{array}\right)(1,1,3,1)=\frac{1}{6}\left(\begin{array}{cccc}1& 1& 3& 1\\ 1& 1& 3& 1\\ 3& 3& 9& 3\\ 1& 1& 3& 1\end{array}\right)$

und demnach

$\mathscr{H}:=I-2\omega {\omega }^T=\frac{1}{6}\left(\begin{array}{cccc}5& -1& -3& -1\\ -1& 5& -3& -1\\ -3& -3& -3& -3\\ -1& -1& -3& 5\end{array}\right),\mathscr{H}x=\left(\begin{array}{c}0\\ 0\\ -2\\ 0\end{array}\right).$

---

Will man für ein $k\ge 1$ die Komponenten $x_i$ $(i=1,...,k-1)$ von $x\in {ℝ}^n$ unverändert lassen und gleichzeitig $x_i=0$ $(i=k+1,...,n)$ erreichen, bekommt man dies, indem man $x$ von links mit der Transformationsmatrix

$P_k:=\left(\begin{array}{cc}{I}_{k-1}& 0\\ 0& {\mathscr{H}}_k\end{array}\right)$

multipliziert. Dabei ist $I_{\ell }$ die $(\ell \times \ell )$-Einheitsmatrix und ${\mathscr{H}}_k$ die $(n-k+1)\times (n-k+1)$-Householder-Matrix der Form

${\mathscr{H}}_k:=I_{n-(k-1)}-2{\omega }^k({\omega }^k{)}^T,{\omega }^k:=\frac{x^{n-k+1}+{\sigma }_k{e}^{n-k+1,1}}{\Vert x^{n-k+1}+{\sigma }_k{e}^{n-k+1,1}{\Vert }_2},{\sigma }_k:=\pm {\Vert x^{n-k+1}\Vert }_2,$

welche mit dem aus den letzten $n-k+1$ Komponenten von $x$ bestehenden Vektor $x^{n-k+1}\in {ℝ}^{n-k+1}$ und der ersten Spalte $e^{n-k+1,1}\in {ℝ}^{n-k+1}$ der Einheitsmatrix $I_{n-k+1}$ gebildet wird. Denn ist $x^{k-1}\in {ℝ}^{k-1}$ der aus den ersten $k-1$ Komponenten von $x$ bestehende Vektor, so hat man nach Lemma 3.28

$P_{k}x=\left(\begin{array}{cc}{I}_k& 0\\ 0& {\mathscr{H}}_k\end{array}\right)\left(\begin{array}{c}{x}^{k-1}\\ x^{n-k+1}\end{array}\right)=\left(\begin{array}{c}{x}^{k-1}\\ {\mathscr{H}}_k{x}^{n-k+1}\end{array}\right)=\left(\begin{array}{c}{x}^{k-1}\\ {\sigma }_k{e}^{n-k+1,1}\end{array}\right).$

Nun ist klar, wie man eine Matrix $A\in {ℝ}^{n\times k}$ in die Form $QS$ mit einer orthogonalen Matrix $Q\in R^{n\times n}$ und eine Matrix $S\in {ℝ}^{n\times k}$ der Gestalt (3.39) zerlegen kann. Ausgehend von $A^{(1)}:=A$ werden sukzessive Matrizen der Form

(3.52) $A^{(j)}:=\left(\begin{array}{cccccc}{a}_{11}^{(j)}& ...& ...& ...& ...& a_{1k}^{(j)}\\ & \ddots & & & & ⋮\\ & & a_{j-1,j-1}^{(j)}& ...& ...& a_{j-1,k}^{(j)}\\ & & & a_{jj}^{(j)}& ...& a_{jk}^{(j)}\\ & & & ⋮& \ddots & ⋮\\ & & & a_{nj}^{(j)}& ...& a_{nk}^{(j)}\end{array}\right)\in {ℝ}^{n\times k},j=2,...,k+1$

bestimmt, so dass dann schließlich $S:=A^{(k+1)}$ die gewünschte Gestalt hat. Die Matrizen in (3.52) werden dabei sukzessive durch Transformationen der Form

(3.53) $A^{(j+1)}:={𝒫}^{(j)}{A}^{(j)},{𝒫}^{(j)}:=\left(\begin{array}{cc}{I}_{j-1}& 0\\ 0& {\mathscr{H}}^{(j)}\end{array}\right)$

mit Householder-Matrizen

${\mathscr{H}}^{(j)}:=I_{n-(j-1)}-2{\omega }^{(j)}({\omega }^{(j)}{)}^T$

erzeugt, wobei ${\omega }^{(j)}\in {ℝ}^{n-(j-1)}$ mit

${\hat{a}}^{(j)}:=(a_{jj}^{(j)},...,a_{nj}^{(j)}{)}^T$

so zu wählen ist, dass mit einem ${\sigma }_j\in ℝ$

${\mathscr{H}}^{(j)}\hat{a}(j)=-{\sigma }_j{e}^{n-(j-1),1}$

gilt. Im Fall ${\hat{a}}^{(j)}\notin \mathrm{span}\{e^{n-(j-1),1}\}$ erreicht man dies gemäß Lemma 3.28 mit

${\omega }^{(j)}:=\frac{{\hat{a}}^{(j)}+{\sigma }_j{e}^{n-(j-1),1}}{\Vert {\hat{a}}^{(j)}+{\sigma }_j{e}^{n-(j-1),1}{\Vert }_2},{\sigma }_j:=\mathrm{sgn}({\hat{a}}_1^{(j)}){\Vert {\hat{a}}^{(j)}\Vert }_2.$

Im selteneren Fall ${\hat{a}}^{(j)}\in \mathrm{span}\{e^{n-(j-1),1}\}$ kann man offenbar ${\mathscr{H}}^{(j)}:=I_{n-(j-1)}$ bzw. ${𝒫}^{(j)}:=I$ in (3.53) wählen. Nach Lemma 3.27 sind dann die Matrizen ${\mathscr{H}}^{(1)},...,{\mathscr{H}}^{(k)}$ und damit die Matrizen ${𝒫}^{(1)},...,{𝒫}^{(k)}$ orthogonal und symmetrisch, so dass man wegen

$A^{(1)}=A,$

$A^{(2)}={𝒫}^{(1)}{A}^{(1)}={𝒫}^{(1)}A,$

$A^{(3)}={𝒫}^{(2)}{A}^{(2)}={𝒫}^{(2)}{𝒫}^{(1)}A,$

$⋮$

$A^{(k+1)}={𝒫}^{(k)}{A}^{(k)}={𝒫}^{(k)}{𝒫}^{(k-1)}\cdots {𝒫}^{(1)}A$

mit

$S:={𝒫}^{(k)}{𝒫}^{(k-1)}\cdots {𝒫}^{(1)}A,Q:={𝒫}^{(1)}{𝒫}^{(2)}\cdots {𝒫}^{(k)}$

wegen (3.47) die gewünschte Zerlegung $A=QS$ erhält. Gemäß Lemma 3.26 ist $Q$ tatsächlich eine orthogonale Matrix.

Man beachte, dass man $Q$ für die Lösung des Gleichungssystems $Ax=b$ mit $n=k$ (sowie für die des Ausgleichsproblems in Abschnitt 4.3) gar nicht benötigt, sondern nur den Vektor $Q^{T}b$. Wegen ${\left({𝒫}^{(j)}\right)}^T={𝒫}^{(j)}$ ist dabei

$Q^T={\left({𝒫}^{(k)}\right)}^T{\left({𝒫}^{(k-1)}\right)}^T\cdots {\left({𝒫}^{(1)}\right)}^T={𝒫}^{(k)}{𝒫}^{(k-1)}\cdots {𝒫}^{(1)},$

so dass man mit $b$ wie mit $A$ verfahren kann:

$b^{(1)}:=b,$

$b^{(2)}:={𝒫}^{(1)}{b}^{(1)}={𝒫}^{(1)}b,$

$b^{(3)}:={𝒫}^{(2)}{b}^{(2)}={𝒫}^{(2)}{𝒫}^{(1)}b,$

$⋮$

$b^{(k+1)}:={𝒫}^{(k)}{b}^{(k)}{𝒫}^{(k)}{𝒫}^{(k-1)}\cdots {𝒫}^{(1)}b=Q^{T}b.$

Man beachte, dass mit

$B^{(j)}:=\left(\begin{array}{ccc}{a}_{jj}^{(j)}& ...& a_{jk}^{(j)}\\ ⋮& \ddots & ⋮\\ a_{nj}^{(j)}& ...& a_{nk}^{(j)}\end{array}\right)$

gemäß (3.52) und (3.53)

$A^{(j+1)}=\left(\begin{array}{cc}{I}_{j-1}& 0\\ 0& {\mathscr{H}}^{(j)}\end{array}\right)\left(\begin{array}{cc}\mathrm{\#}& *\\ 0& B^{(j)}\end{array}\right)=\left(\begin{array}{cc}\mathrm{\#}& *\\ 0& {\mathscr{H}}^{(j)}{B}^{(j)}\end{array}\right)$

gilt, also wie beim Gauß-Algorithmus nur die verbleibende Restmatrix $B^{(j)}$ in $A^{(j)}$ und analog der verbleibende Anteil der rechten Seite zu transformieren ist. Weiter sei gesagt, dass Householder-Transformationsmatrizen niemals explizit durch Matrixmultiplikation gebildet werden sollten. Denn eine Matrixmultiplikation $\mathscr{H}B$ mit $\mathscr{H}\in {ℝ}^{m\times m}$ und $B\in {ℝ}^{m\times \ell }$ kostet $𝒪(m^2\ell )$ Multiplikationen. Die benötigten Matrixmultiplikationen für $\mathscr{H}:=I-2\omega {\omega }^T$ berechne man daher wie folgt:

(3.54) $\mathscr{H}B=(I-2\omega {\omega }^T)B=B-\omega v^T,v^T:=2{\omega }^{T}B.$

Zunächst ermittele man also den Vektor $v$ und dann "aufdatiere" man die Matrix $B$. Für ein solches Vorgehen benötigt man nur $2m\ell$ Multiplikationen.

Bemerkung 3.31

Will man die Vektoren ${\omega }^{(j)}$ aufbewahren, weil man z. B. ein Gleichungssystem $Ax=b$ mit derselben Matrix und verschiedenen rechten Seiten zu lösen hat, so kann man für jedes $j\in \{1,...,k\}$ das Diagonalelement $a_{jj}^{(j+1)}$ zunächst gesondert speichern und anschließend den Vektor ${\omega }^{(j)}$ in der $j$-ten Spalte der Matrix $A^{(j+1)}$ eintragen (s. Beispiel 3.32). Auf diese Weise spart man Speicherplatz, was bei sehr großen Matrizen relevant ist.

Beispiel 3.32

Man berechne eine QS-Zerlegung von $A$ und $Q^{T}b$ für

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

Wir setzen $A^{(1)}:=A$ und $b^{(1)}:=b$ und bekommen zunächst

${\hat{a}}^{(1)}:=(1,1,1,1{)}^T,{\Vert {\hat{a}}^{(1)}\Vert }_2=2,{\sigma }_1=\mathrm{sgn}(1)\cdot 2=2.$

Damit folgt

${\tilde{\omega }}^{(1)}:={\hat{a}}^{(1)}+{\sigma }_1{e}^{4,1}=(1,1,1,1{)}^T+2(1,0,0,0{)}^T=(3,1,1,1{)}^T,$

${\Vert {\tilde{\omega }}^{(1)}\Vert }_2=2\sqrt{3},$

${\omega }^{(1)}:=\frac{{\tilde{\omega }}^{(1)}}{{\Vert {\tilde{\omega }}^{(1)}\Vert }_2}=\frac{1}{2\sqrt{3}}(3,1,1,1{)}^T.$

Für ${\mathscr{H}}^{(1)}:=I-2{\omega }^{(1)}({\omega }^{(1)}{)}^T$ benötigt man nun die Produkte ${\mathscr{H}}^{(1)}{A}^{(1)}$ und ${\mathscr{H}}^{(1)}{b}^{(1)}$, die man analog zu (3.54) berechnet. Es ist

${\left(v^{(1)}\right)}^T:=2{\left({\omega }^{(1)}\right)}^T{A}^{(1)}=\frac{1}{\sqrt{3}}\left(\begin{array}{cccc}3& 1& 1& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ 1& 3\\ 1& 4\\ 1& 7\end{array}\right)=\frac{1}{\sqrt{3}}\left(\begin{array}{cc}6& 14\end{array}\right),$

${\left(u^{(1)}\right)}^T:=2{\left({\omega }^{(1)}\right)}^T{b}^{(1)}=\frac{1}{\sqrt{3}}\left(\begin{array}{cccc}3& 1& 1& 1\end{array}\right)\left(\begin{array}{c}1\\ 2\\ 6\\ 4\end{array}\right)=\frac{15}{\sqrt{3}}$

und demnach

${\omega }^{(1)}{\left(v^{(1)}\right)}^T=\frac{1}{6}\left(\begin{array}{c}3\\ 1\\ 1\\ 1\end{array}\right)\left(\begin{array}{cc}6& 14\end{array}\right)=\left(\begin{array}{cc}3& 7\\ 1& 7/3\\ 1& 7/3\\ 1& 7/3\end{array}\right),$

${\omega }^{(1)}{\left(u^{(1)}\right)}^T=\frac{15}{6}\left(\begin{array}{c}3\\ 1\\ 1\\ 1\end{array}\right)=\left(\begin{array}{c}15/2\\ 5/2\\ 5/2\\ 5/2\end{array}\right).$

Demzufolge ergibt sich

$A^{(2)}:={\mathscr{H}}^{(1)}{A}^{(1)}=A^{(1)}-{\omega }^{(1)}{\left(v^{(1)}\right)}^T=\left(\begin{array}{cc}-2& -7\\ 0& 2/3\\ 0& 5/3\\ 0& 14/3\end{array}\right),$

$b^{(2)}:={\mathscr{H}}^{(1)}{b}^{(1)}=b^{(1)}-{\omega }^{(1)}{\left(u^{(1)}\right)}^T=\left(\begin{array}{c}-13/2\\ -1/2\\ 7/2\\ 3/2\end{array}\right).$

Wollte man den Vektor ${\omega }^{(1)}$ aufbewahren, um damit zu einem späteren Zeitpunkt die Zerlegung von $A$ wieder erzeugen zu können, so legt man einen Arbeitsvektor $d\in {ℝ}^2$ an, setzt man $d_1:=a_{11}^{(2)}=-2$ und trägt man ${\omega }^{(1)}$ in die erste Spalte von $A^{(2)}$ ein, so dass sich ergibt:

${\hat{A}}^{(2)}:=\left(\begin{array}{cc}\frac{1}{2}\sqrt{3}& -7\\ \frac{1}{6}\sqrt{3}& 2/3\\ \frac{1}{6}\sqrt{3}& 5/3\\ \frac{1}{6}\sqrt{3}& 14/3\end{array}\right)$

In der Praxis kann man $A^{(2)}$ und auch ${\hat{A}}^{(2)}$ wieder $A$ nennen, da man $A$ selbst nicht mehr benötigt.

Nun verfährt man analog mit der Restmatrix bzw. dem Restvektor

${\tilde{A}}^{(2)}:=\left(\begin{array}{c}2/3\\ 5/3\\ 14/3\end{array}\right),{\tilde{b}}^{(2)}:=\left(\begin{array}{c}-1/2\\ 7/2\\ 3/2\end{array}\right).$

Man bekommt

${\hat{a}}^{(2)}:={(\frac{2}{3},\frac{5}{3},\frac{14}{3})}^T,{\Vert {\hat{a}}^{(2)}\Vert }_2=5,{\sigma }_2=\mathrm{sgn}\left(\frac{2}{3}\right)\cdot 5=5,$

${\tilde{\omega }}^{(2)}:={\hat{a}}^{(2)}+{\sigma }_2{e}^{3,1}={(\frac{2}{3},\frac{5}{3},\frac{14}{3})}^T+5(1,0,0{)}^T={(\frac{17}{3},\frac{5}{3},\frac{14}{3})}^T,$

${\Vert {\tilde{\omega }}^{(2)}\Vert }_2=\frac{\sqrt{510}}{3},$

${\omega }^{(2)}:=\frac{{\tilde{\omega }}^{(2)}}{{\Vert {\tilde{\omega }}^{(2)}\Vert }_2}=\frac{1}{\sqrt{510}}(17,5,14{)}^T,$

${\left(v^{(2)}\right)}^T:=2{\left({\omega }^{(2)}\right)}^T{\tilde{A}}^{(2)}=\frac{2}{\sqrt{510}}\left(\begin{array}{ccc}17& 5& 14\end{array}\right)\left(\begin{array}{c}2/3\\ 5/3\\ 14/3\end{array}\right)=\frac{510}{3\sqrt{510}},$

${\left(u^{(2)}\right)}^T:=2{\left({\omega }^{(2)}\right)}^T{\tilde{b}}^{(1)}=\frac{1}{\sqrt{510}}\left(\begin{array}{ccc}17& 5& 14\end{array}\right)\left(\begin{array}{c}-1\\ 7\\ 3\end{array}\right)=\frac{60}{\sqrt{510}},$

${\mathscr{H}}^{(2)}{\tilde{A}}^{(2)}={\tilde{A}}^{(2)}-{\omega }^{(2)}{\left(v^{(2)}\right)}^T=\left(\begin{array}{c}2/3\\ 5/3\\ 14/3\end{array}\right)-\frac{1}{3}\left(\begin{array}{c}17\\ 5\\ 14\end{array}\right)=\left(\begin{array}{c}-5\\ 0\\ 0\end{array}\right),$

${\mathscr{H}}^{(2)}{\tilde{b}}^{(2)}={\tilde{b}}^{(2)}-{\omega }^{(2)}{\left(u^{(2)}\right)}^T=\left(\begin{array}{c}-1/2\\ 7/2\\ 3/2\end{array}\right)-\frac{60}{510}\left(\begin{array}{c}17\\ 5\\ 14\end{array}\right)=\left(\begin{array}{c}-5/2\\ 99/34\\ -5/34\end{array}\right).$

Damit ergibt sich nun

$S:=A^{(3)}=\left(\begin{array}{cc}-2& -7\\ 0& -5\\ 0& 0\\ 0& 0\end{array}\right),R:=\left(\begin{array}{cc}-2& -7\\ 0& -5\end{array}\right),Q^{T}b=b^{(3)}:=\left(\begin{array}{c}-13/2\\ -5/2\\ 99/34\\ -5/34\end{array}\right).$

Will man die ${\omega }^{(j)}$ wiederverwenden, so bilde man mit ${\hat{A}}^{(2)}$ und dem oben definierten $d_1$

${\hat{A}}^{(3)}=\left(\begin{array}{cc}\frac{1}{2}\sqrt{3}& -7\\ \frac{1}{6}\sqrt{3}& \frac{1}{\sqrt{510}}17\\ \frac{1}{6}\sqrt{3}& \frac{1}{\sqrt{510}}5\\ \frac{1}{6}\sqrt{3}& \frac{1}{\sqrt{510}}14\end{array}\right),d:=\left(\begin{array}{c}-2\\ -5\end{array}\right).$

Aus ${\hat{A}}^{(3)}$ und $d$ könnte man $R$ in offensichtlicher Weise gewinnen.

---

Man kann sich überlegen, dass eine QS-Zerlegung von $A\in {ℝ}^{n\times k}$ mittels Householder-Transformationen etwa

$2[\frac{k^3}{3}+(n-k)\frac{k^2}{2}]$

Multiplikationen benötigt, also

(3.55) $\sim n{k}^2$ für $n\gg k$ und $\sim \frac{2}{3}{n}^3$ für $n\approx k$

und damit bei quadratischen Matrizen etwa doppelt so viele wesentliche Rechenoperationen wie der Gauß-Algorithmus. Neben dem Einsatz für die bereits besprochene stabile Lösung von linearen Gleichungssystemen werden wir im nächsten Abschnitt eine weitere wichtige Anwendung einer solchen QS-Zerlegung geben.

Siehe auch

• normalisierte Gleitkomma-Darstellung
• Lösung linearer Gleichungssysteme - (Foliensatz)
• Zerlegung PA = LR - (Foliensatz)

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/Orthonormalisierungsverfahren
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.