Study Guides / Lineare Algebra / Übungsstunde 9
ÜBUNGSSTUNDE 9 · ETH ZURICH · HS19 · linalg

Skalarprodukt, Gram-Schmidt und QR-Zerlegung

Bilinearform, Skalarprodukt, Orthogonalbasis (ONB), orthogonale Projektion, Gram-Schmidt-Verfahren, QR-Zerlegung

SB
Steven Battilana Quant · ex-ETH

Skalarprodukt

Definition

Eine Abbildung B:En×En→E, (v,w)↦B(v,w)B: \mathbb{E}^n \times \mathbb{E}^n \to \mathbb{E},\, (v,w) \mapsto B(v,w) heisst Bilinearform (BLF) auf En\mathbb{E}^n, falls die Linearität in beiden Argumenten erfüllt ist: ∀u,v,w∈En, ∀λ∈E\forall u,v,w \in \mathbb{E}^n,\,\forall \lambda \in \mathbb{E}:

  • B(u+v,w)=B(u,w)+B(v,w),B(λu,v)=λB(u,v)B(u+v,w) = B(u,w) + B(v,w),\quad B(\lambda u, v) = \lambda B(u,v)
  • B(u,v+w)=B(u,v)+B(u,w),B(u,λv)=λB(u,v)B(u,v+w) = B(u,v) + B(u,w),\quad B(u, \lambda v) = \lambda B(u,v).
Definition

Sei BB eine BLF, die auf R\mathbb{R} abbildet. BB heisst symmetrisch, falls B(v,w)=B(w,v)B(v,w) = B(w,v) und alternierend, falls B(v,w)=−B(w,v)B(v,w) = -B(w,v), für ∀v,w∈En\forall v,w \in \mathbb{E}^n.

Definition

Eine Abbildung B:En×En→E, (v,w)↦B(v,w)B: \mathbb{E}^n \times \mathbb{E}^n \to \mathbb{E},\, (v,w) \mapsto B(v,w) heisst sesquilinear auf En\mathbb{E}^n, falls die Linearität im zweiten Argument erfüllt ist und im ersten Argument semilinear ist: ∀u,v,w∈En, ∀λ∈E\forall u,v,w \in \mathbb{E}^n,\,\forall \lambda \in \mathbb{E}:

  • B(u+v,w)=B(u,w)+B(v,w),B(λu,v)=λ‾B(u,v)B(u+v,w) = B(u,w) + B(v,w),\quad B(\lambda u, v) = \boldsymbol{\overline{\lambda}} B(u,v)
  • B(u,v+w)=B(u,v)+B(u,w),B(u,λv)=λB(u,v)B(u,v+w) = B(u,v) + B(u,w),\quad B(u, \lambda v) = \lambda B(u,v).
Definition

Eine Sesquilinearform BB, die auf C\mathbb{C} abbildet, heisst hermitesch, falls B(v,w)=B(w,v)‾B(v,w) = \overline{B(w,v)}.

Definition

Eine Sesquilinearform BB heisst positiv definit, wenn

B(v,v)>0fu¨r jedes v∈En mit v≠0.B(v,v) > 0 \quad \text{für jedes } v \in \mathbb{E}^n \text{ mit } v \neq 0.
Bemerkung

Eine symmetrische, positiv definite BLF heisst euklidisches Skalarprodukt.

Definition

Ein Skalarprodukt ist eine Abbildung ⟨⋅,⋅⟩:En×En→E,(v,w)↦⟨v,w⟩=∑k=1nvk‾wk\langle \cdot,\cdot \rangle: \mathbb{E}^n \times \mathbb{E}^n \to \mathbb{E}, (v,w) \mapsto \langle v,w \rangle = \sum_{k=1}^n \overline{v_k}w_k so dass: ∀u,v,w∈En, ∀λ∈E\forall u,v,w \in \mathbb{E}^n,\,\forall \lambda \in \mathbb{E}:

  1. ⟨v+λw,u⟩=⟨v,u⟩+λ‾⟨w,u⟩\langle v+ \lambda w,u \rangle = \langle v,u \rangle + \overline{\lambda} \langle w,u \rangle (Bilinearität bzw. Sesquilinearität)
  2. ⟨v,w⟩=⟨w,v⟩‾\langle v,w \rangle = \overline{ \langle w,v \rangle } (Symmetrie bzw. hermitesch)
  3. ⟨v,v⟩≥0\langle v,v \rangle \geq 0 (positiv semidefinit)
  4. ⟨v,v⟩≥0\langle v,v \rangle \geq 0 und ⟨v,v⟩=0⇔v=0\langle v,v \rangle = 0 \Leftrightarrow v = 0 (positiv definit)
Definition

Die Länge oder euklidische Norm eines Vektors x∈Enx \in \mathbb{E}^n ist die nichtnegative reelle Zahl ∥x∥\left\lVert x \right\rVert definiert durch

∥x∥:=⟨x,x⟩=xHx=∑k=1n∣xk∣2.\left\lVert x \right\rVert := \sqrt{\langle x,x \rangle} = \sqrt{x^Hx} = \sqrt{\sum_{k=1}^n |x_k|^2}.
Bemerkung

Seien x,y∈Rnx,y \in \mathbb{R}^n und α∈[0,π]\alpha \in [0, \pi] der Winkel zwischen xx und yy, dann gilt:

⟨x,y⟩=∥x∥∥y∥cos⁡(α).\langle x,y \rangle = \left\lVert x \right\rVert \left\lVert y \right\rVert \cos(\alpha).
Definition

Sei B={bi}i∈I\mathcal{B} = \{b_i\}_{i \in I} eine Basis von VV, ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle Skalarprodukt auf VV.

  • B\mathcal{B} heisst orthogonal ⇔⟨bk,bl⟩=0,∀k≠l\quad \Leftrightarrow \quad \langle b_k,b_l \rangle = 0, \forall k \neq l
    In Worten: Basisvektoren "stehen ⊥\perp aufeinander".
  • B\mathcal{B} heisst orthonormal (ONB) ⇔⟨bk,bl⟩=δkl={1,k=l0,k≠l\quad \Leftrightarrow \quad \langle b_k,b_l \rangle = \delta_{kl} = \begin{cases} 1, \quad k = l\\ 0, \quad k \neq l \end{cases}
    In Worten: Basisvektoren "stehen ⊥\perp aufeinander" und haben Länge 11.
Bemerkung

Sei VV ein Vektorraum mit Skalarprodukt ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle, B={bi}i∈I\mathcal{B} = \{b_i\}_{i \in I} Basis von VV. Per Definition von Basis kann man jedes v∈Vv \in V schreiben als v=∑i∈Iαibiv = \sum_{i \in I} \alpha_i b_i. Falls B\mathcal{B} eine ONB ist, so ist αi=⟨bi,v⟩,  ∀i∈I\alpha_i = \langle b_i, v \rangle, \,\, \forall i \in I,
⇒\Rightarrow \quad Koordinaten von vv bezüglich B\mathcal{B} sind ⟨bi,v⟩\langle b_i, v \rangle.

Das äussere Produkt und die orthogonale Projektion

Bemerkung
  • innere Produkt: ∀x,y∈En:⟨x,y⟩=xHy∈E\forall x,y \in \mathbb{E}^n: \quad \langle x,y \rangle = x^Hy \in \mathbb{E}
  • äussere Produkt: ∀x∈Em,∀y∈En:xyH∈Em×n\forall x \in \mathbb{E}^m, \forall y \in \mathbb{E}^n: \quad xy^H \in \mathbb{E}^{m \times n}
Satz

Die orthogonale Projektion PYxP_Yx von x∈Enx \in \mathbb{E}^n auf die durch yy und Ursprung induzierte Gerade ist:

PYx:=1∥y∥2yyHx=uuHx mit u:=y∥y∥P_Yx := \frac{1}{\left\lVert y \right\rVert^2} yy^Hx = uu^Hx \text{ mit } u := \frac{y}{\left\lVert y \right\rVert}
  1. y-Richtung: PYx=αy,  α∈E\quad P_Yx = \alpha y,\,\, \alpha \in \mathbb{E}
    (PYxP_Yx ist ein Punkt auf yy).
  2. x-Richtung: (x−PYx)⊥y\quad (x-P_Yx) \perp y.
Bemerkung Projektionsmatrix
  • PYx:=1∥y∥2yyHx=uuHx mit u:=y∥y∥P_Yx := \frac{1}{\left\lVert y \right\rVert^2} yy^Hx = uu^Hx \text{ mit } u := \frac{y}{\left\lVert y \right\rVert}
  • PYH=PYP_Y^H = P_Y (symmetrisch/hermitesch)
  • PY2=PYP_Y^2 = P_Y (idempotent; dies ist eine alternative Definition von einer Projektion)

Gram-Schmidt Verfahren

Satz

Zu jedem Vektorraum endlicher oder zumindest abzählbarer Dimension existiert eine ONB. (d.h. ist konstruierbar mit Gram-Schmidt)

Algorithmus Gram-Schmidt Verfahren
  1. Sei VV ein euklidischer/unitärer Vektorraum mit dim(V)=n<∞\text{dim}(V) = n \lt \infty
  2. Gegeben: W=span{v1,...,vm}⊂V,  {vi}i=1mW = \text{span}\{v_1, ..., v_m\} \subset V, \,\, \{v_i\}_{i=1}^m Basis von WW ist linear unabhängig
  3. Gesucht 1: w1,...,wmw_1, ..., w_m so dass W=span{w1,...,wm}W = \text{span}\{w_1, ..., w_m\} und {wi}i=1m\{w_i\}_{i=1}^{\boldsymbol{m}} ONB von WW ist orthonormal
  4. Gesucht 2: w1,...,wm,wm+1,...,wnw_1, ..., w_m, w_{m+1}, ..., w_n so dass V=span{w1,...,wn}V = \text{span}\{w_1, ..., w_n\} und {wi}i=1n\{w_i\}_{i=1}^{\boldsymbol{n}} ONB von VV ist orthonormal.
  5. w1=v1∥v1∥w_1 = \frac{v_1}{\left\lVert v_1 \right\rVert} mit ∥v1∥=⟨v1,v1⟩⇒W(1)={w1}\left\lVert v_1 \right\rVert = \sqrt{ \langle v_1, v_1 \rangle } \quad \Rightarrow W^{(1)} = \{w_1\}
  6. für k∈{2,...,m}k \in \{2, ..., m\}
  7. Setze v:=vkv := v_k (es gilt vk∈W∖span{W(k−1)}v_k \in W \setminus \text{span}\{ W^{(k-1)}\})
  8. wk′=v−∑i=1k−1⟨v,wi⟩wi=v−⟨v,w1⟩w1−...−⟨v,wk−1⟩wk−1w_k' = v - \sum\limits_{i=1}^{k-1} \langle v, w_i \rangle w_i = v - \langle v, w_1 \rangle w_1 - ... - \langle v, w_{k-1} \rangle w_{k-1}
  9. wk=wk′∥wk′∥w_k = \frac{w_k'}{\left\lVert w_k' \right\rVert} mit ∥wk′∥=⟨wk′,wk′⟩\left\lVert w_k' \right\rVert = \sqrt{ \langle w_k', w_k' \rangle }
  10. W(k)=W(k−1)∪{wk}={w1,...,wk}W^{(k)} = W^{(k-1)} \cup \{w_k\} = \{w_1, ..., w_k\}
  11. W(m)W^{(m)} ist eine ONB für WW.
  12. Falls man W(m)W^{(m)} zu einer ONB von VV erweitern will:
  13. Für k∈{m+1,...,n}k \in \{m+1, ..., n\}
  14. Wähle v∈V∖span{W(k−1)}v \in V \setminus \text{span}\{W^{(k-1)}\}
  15. wk′=v−∑i=1k−1⟨v,wi⟩wiw_k' = v - \sum\limits_{i=1}^{k-1} \langle v, w_i \rangle w_i
  16. wk=wk′∥wk′∥w_k = \frac{w_k'}{\left\lVert w_k' \right\rVert} mit ∥wk′∥=⟨wk′,wk′⟩\left\lVert w_k' \right\rVert = \sqrt{ \langle w_k', w_k' \rangle }
  17. W(k)=W(k−1)∪{wk}W^{(k)} = W^{(k-1)} \cup \{w_k\}
  18. W(n)W^{(n)} ist eine ONB für VV.
Beispiel 1

Gegeben: Vektorraum P2\mathcal{P}_2 über R\mathbb{R} mit Skalarprodukt ⟨p,q⟩P=∫−11p(t)q(t)dt\langle p,q \rangle_\mathcal{P} = \int\limits_{-1}^1 p(t)q(t) dt und Monombasis B={1,t,t2}\mathcal{B} = \{1, t, t^2\}. Hier: V=W=P2V=W=\mathcal{P}_2
Gesucht: Eine ONB die bezüglich ⟨⋅,⋅⟩P\langle \cdot, \cdot \rangle_\mathcal{P} orthogonal ist ⇒\quad \Rightarrow \quad wir müssen 1,t,t21,t,t^2 bezüglich ⟨⋅,⋅⟩P\langle \cdot, \cdot \rangle_\mathcal{P} orthonormieren.

Lösung anzeigenLösung ausblenden

1.

w1=1∥1∥P=12,weil∥1∥P=∫−111dt=2w_1 = \frac{1}{\left\lVert 1 \right\rVert_\mathcal{P}} = \frac{1}{\sqrt{2}}, \quad \text{weil} \quad \left\lVert 1 \right\rVert_\mathcal{P} = \sqrt{\int_{-1}^1 1 dt} = \sqrt{2}⇒W(1)={12}\Rightarrow W^{(1)} = \left\{\frac{1}{\sqrt{2}}\right\}

2. k=2:k=2:

w2′=t−⟨t,12⟩12=t−12∫−11t⋅12dt=t−12[122t2]−11=t−0=t\begin{aligned} w_2' &= t - \langle t, \frac{1}{\sqrt{2}} \rangle \frac{1}{\sqrt{2}}\\ &= t - \frac{1}{\sqrt{2}} \int_{-1}^1 t \cdot \frac{1}{\sqrt{2}} dt\\ &= t - \frac{1}{\sqrt{2}} \left [ \frac{1}{2\sqrt{2}}t^2 \right ]_{-1}^1\\ &= t - 0\\ &= t \end{aligned}w2=t∥t∥P=32tweil∥t∥P=∫−11t2dt=[13t3]−11=23w_2 = \frac{t}{\left\lVert t \right\rVert_\mathcal{P}} = \sqrt{\frac{3}{2}} t \quad \text{weil} \quad \quad \left\lVert t \right\rVert_\mathcal{P} = \sqrt{\int_{-1}^1 t^2 dt} = \sqrt{\left[ \frac{1}{3} t^3 \right]_{-1}^1} = \sqrt{\frac{2}{3}}W(2)={12,32t}W^{(2)} = \left \{ \frac{1}{\sqrt{2}}, \sqrt{\frac{3}{2}} t \right\}

3. k=3:k=3:

w3′=t2−⟨t2,12⟩12−⟨t2,32t⟩32t=t2−12∫−1112⋅t2dt−32t∫−1132t⋅t2dt=t2−12[132t3]−11−32t[3214t4]−11=t2−13−0=t2−13\begin{aligned} w_3' &= t^2 - \langle t^2, \frac{1}{\sqrt{2}} \rangle \frac{1}{\sqrt{2}} - \langle t^2, \sqrt{\frac{3}{2}} t \rangle \sqrt{\frac{3}{2}} t\\ &= t^2 - \frac{1}{\sqrt{2}} \int_{-1}^1 \frac{1}{\sqrt{2}} \cdot t^2 dt - \sqrt{\frac{3}{2}} t \int_{-1}^1 \sqrt{\frac{3}{2}} t \cdot t^2 dt\\ &= t^2 - \frac{1}{\sqrt{2}} \left[ \frac{1}{3\sqrt{2}} t^3 \right]_{-1}^1 - \sqrt{\frac{3}{2}} t \left[ \sqrt{\frac{3}{2}} \frac{1}{4} t^4 \right]_{-1}^1\\ &= t^2 - \frac{1}{3} - 0\\ &= t^2 - \frac{1}{3} \end{aligned}w3=w3′∥w3′∥P=458(t2−13)weil∥w3′∥P=∫−11(t2−13)2dt=[t55−2t39+t9]−11=845w_3 = \frac{w_3'}{\left\lVert w_3' \right\rVert_\mathcal{P}} = \sqrt{\frac{45}{8}} (t^2 - \frac{1}{3}) \quad \text{weil} \quad \left\lVert w_3' \right\rVert_\mathcal{P} = \sqrt{\int_{-1}^1 (t^2 - \frac{1}{3})^2 dt} = \sqrt{\left[ \frac{t^5}{5} - \frac{2t^3}{9} + \frac{t}{9} \right]_{-1}^1} = \sqrt{\frac{8}{45}}W(3)={12,32t,458(t2−13)} ist ONB fu¨r P2.W^{(3)} = \left\{ \frac{1}{\sqrt{2}}, \sqrt{\frac{3}{2}} t, \sqrt{\frac{45}{8}} (t^2 - \frac{1}{3}) \right\} \quad \text{ ist ONB für } \mathcal{P}_2.

QR-Zerlegung

Bemerkung

Sei A∈Em×nA \in \mathbb{E}^{m \times n}. Angenommen rang(A)=n≤m\text{rang}(A) = n \leq m (voller Rang). Dann existiert eine orthogonale/unitäre Matrix Q=(Q1∣Q2)Q = (Q_1 | Q_2) mit Q∈Em×m,  Q1∈Em×n,  Q2∈Em×(m−n)Q \in \mathbb{E}^{m \times m}, \,\, Q_1 \in \mathbb{E}^{m \times n}, \,\, Q_2 \in \mathbb{E}^{m \times (m - n)} und es existiert eine rechte Dreiecksmatrix R1∈En×nR_1 \in \mathbb{E}^{n \times n} und mit 0∈E(m−n)×n\boldsymbol{0} \in \mathbb{E}^{(m-n) \times n}, so dass

A=Q⋅(R10)=:QRA = Q \cdot \left(\begin{array}{c} R_1\\ \hline \boldsymbol{0} \end{array}\right) =: QR
Bemerkung

Da R=(R10)R = \left(\begin{array}{c} R_1\\ \hline \boldsymbol{0} \end{array}\right), ist A=QR=Q1R1A= QR = Q_1R_1.

Bemerkung Zusammenhang QR-Zerlegung und kleinste Quadrate

Für das Residuum rr gilt r=y−∑i=1n⟨qi,y⟩qir = y - \sum \limits_{i=1}^n \langle q_i, y \rangle q_i, wobei {qi}i=1n\{q_i\}_{i=1}^n die Spalten von Q1Q_1 bezeichnet.

Bemerkung

Falls das betrachtete Skalarprodukt das Standard-Skalarprodukt ist, gilt:

Q1HQ1=𝟙Ax=y⟺A=Q1R1Q1R1x=y⇔R1x=Q1Hy⇔x=R1−1Q1Hy\begin{aligned} Q_1^HQ_1 = \text{𝟙}\\ Ax = y &\stackrel{A=Q_1R_1}{\Longleftrightarrow} Q_1R_1x = y\\ &\Leftrightarrow R_1x = Q_1^Hy\\ &\Leftrightarrow x = R_1^{-1}Q_1^Hy \end{aligned}

Für ein anderes Skalarprodukt ergibt sich eine andere Formel für xx!

Algorithmus QR-Zerlegung
  1. Gegeben: A∈Em×n,  m>n,  ⟨⋅,⋅⟩A \in \mathbb{E}^{m \times n}, \,\, m > n, \,\, \langle \cdot, \cdot \rangle ein Skalarprodukt
  2. Gesucht: Q1,R1Q_1, R_1, so dass A=Q1R1A = Q_1R_1.
  3. Q1: Seien a1,...,ana_1, ..., a_n Spalten von AA. Wende Gram-Schmidt Verfahren bezüglich ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle auf {ai}i=1n\{a_i\}_{i=1}^n an. Das liefert dann {q1,...,qn}\{q_1, ..., q_n\}.
  4. ⇒(q1∣...∣qn)=Q1∈Em×n\Rightarrow (q_1 | ... | q_n) = Q_1 \in \mathbb{E}^{m \times n}
  5. R1:
  6. 1. rij={0,i>j⟨qi,aj⟩,i<j∥qi~∥=⟨qi~,qi~⟩,i=j\displaystyle r_{ij} = \begin{cases} 0, & i>j\\ \langle q_i, a_j \rangle, & i \lt j\\ \left\lVert \widetilde{q_i} \right\rVert = \sqrt{\langle \widetilde{q_i},\widetilde{q_i} \rangle}, & i=j \end{cases}
  7. wobei qi~\widetilde{q_i} den ii-ten orthogonalisierten, aber noch nicht normierten Vektor bezeichnet.
  8. 2. R1=(rij)1≤i,j≤nR_1 = (r_{ij})_{1 \leq i,j \leq n}
Beispiel 2

Gegeben:

A=(01132−2),⇒m=3>2=n,y=(224)A = \begin{pmatrix} 0 & 1\\ 1 & 3\\ 2 & -2 \end{pmatrix}, \quad \Rightarrow \quad m=3 > 2=n, \quad y = \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}

Gesucht: Bestimme mit Hilfe der QR-Zerlegung x=(x1,x2)Tx = (x_1, x_2)^T, so dass ∥r∥22=∥y−Ax∥22\left\lVert r \right\rVert_2^2 = \left\lVert y - Ax \right\rVert_2^2 minimal ist bezüglich dem Standard-Skalarprodukt ⟨x,y⟩=xHy\langle x,y \rangle = x^Hy.

Lösung anzeigenLösung ausblenden

(Q1)

q1=a1∥a1∥=15(012)q2~=a2−⟨q1,a2⟩q1=(13−2)−1515⟨(012),(13−2)⟩(012)=(13−2)−15⋅(−1)⋅(012)=(1165−85)=15(516−8)q2=q2~∥q2~∥=155345(516−8)=1345(516−8)⇒Q1=(05345151634525−8345)\begin{aligned} q_1 &= \frac{a_1}{\left\lVert a_1 \right\rVert} = \frac{1}{\sqrt{5}} \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix}\\ \widetilde{q_2} &= a_2 - \langle q_1, a_2 \rangle q_1\\ &= \begin{pmatrix} 1\\ 3\\ -2 \end{pmatrix} - \frac{1}{\sqrt{5}} \frac{1}{\sqrt{5}} \langle \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix}, \begin{pmatrix} 1\\ 3\\ -2 \end{pmatrix} \rangle \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix}\\ &= \begin{pmatrix} 1\\ 3\\ -2 \end{pmatrix} - \frac{1}{5} \cdot (-1) \cdot \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix}\\ &= \begin{pmatrix} 1\\ \frac{16}{5}\\ -\frac{8}{5} \end{pmatrix}\\ &= \frac{1}{5} \begin{pmatrix} 5\\ 16\\ -8 \end{pmatrix}\\ q_2 &= \frac{\widetilde{q_2}}{\left\lVert \widetilde{q_2} \right\rVert} = \frac{1}{5} \frac{5}{\sqrt{345}} \begin{pmatrix} 5\\ 16\\ -8 \end{pmatrix} = \frac{1}{\sqrt{345}} \begin{pmatrix} 5\\ 16\\ -8 \end{pmatrix}\\ \Rightarrow \quad Q_1 &= \begin{pmatrix} 0 & \frac{5}{\sqrt{345}}\\ \frac{1}{\sqrt{5}} & \frac{16}{\sqrt{345}}\\ \frac{2}{\sqrt{5}} & \frac{-8}{\sqrt{345}} \end{pmatrix} \end{aligned}

(R1)

r11=∥a1∥=5r22=∥q2~∥=(1515⟨(516−8),(516−8)⟩)12=(125(25+256+64))12=3455\begin{aligned} r_{11} &= \left\lVert a_1 \right\rVert = \sqrt{5}\\ r_{22} &= \left\lVert \widetilde{q_2} \right\rVert = \left( \frac{1}{5}\frac{1}{5} \langle \begin{pmatrix} 5\\ 16\\ -8 \end{pmatrix}, \begin{pmatrix} 5\\ 16\\ -8 \end{pmatrix} \rangle \right)^\frac{1}{2} = \left( \frac{1}{25} (25+256+64) \right)^\frac{1}{2} = \frac{\sqrt{345}}{5} \end{aligned}r12=⟨q1,a2⟩=15⟨(012),(13−2)⟩=−15r_{12} = \langle q_1, a_2 \rangle = \frac{1}{\sqrt{5}} \langle \begin{pmatrix} 0\\ 1\\ 2 \end{pmatrix}, \begin{pmatrix} 1\\ 3\\ -2 \end{pmatrix} \rangle = -\frac{1}{\sqrt{5}}r21=0⇒R1=(5−1503455)⇒A=Q1R1\begin{aligned} r_{21} = 0\\ &\Rightarrow \quad R_1 = \begin{pmatrix} \sqrt{5} & -\frac{1}{\sqrt{5}}\\ 0 & \frac{\sqrt{345}}{5} \end{pmatrix}\\ &\Rightarrow \quad A = Q_1 R_1 \end{aligned}Ax=y⇒Q1R1x=y⇔R1x=Q1Ty⇔x=R1−1Q1TyR1−1=5345(34551505)Q1T=(01525534516345−8345)\begin{aligned} Ax = y &\Rightarrow Q_1 R_1x = y\\ &\Leftrightarrow R_1x = Q_1^Ty\\ &\Leftrightarrow x = R_1^{-1} Q_1^Ty\\ R_1^{-1} &= \frac{\sqrt{5}}{\sqrt{345}} \begin{pmatrix} \frac{\sqrt{345}}{5} & \frac{1}{\sqrt{5}}\\ 0 & \sqrt{5} \end{pmatrix}\\ Q_1^T &= \begin{pmatrix} 0 & \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}}\\ \frac{5}{\sqrt{345}} & \frac{16}{\sqrt{345}} & \frac{-8}{\sqrt{345}} \end{pmatrix} \end{aligned}x=5345(34551505)(01525534516345−8345)(224)x = \frac{\sqrt{5}}{\sqrt{345}} \begin{pmatrix} \frac{\sqrt{345}}{5} & \frac{1}{\sqrt{5}}\\ 0 & \sqrt{5} \end{pmatrix} \begin{pmatrix} 0 & \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}}\\ \frac{5}{\sqrt{345}} & \frac{16}{\sqrt{345}} & \frac{-8}{\sqrt{345}} \end{pmatrix} \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}=(5345853451303452534580345−40345)(224)=1345(5851302580−40)(224)=169(11726516−8)(224)=169(2+34+10410+32−32)=169(14010)\begin{aligned} &= \begin{pmatrix} \frac{5}{345} & \frac{85}{345} & \frac{130}{345}\\ \frac{25}{345} & \frac{80}{345} & -\frac{40}{345} \end{pmatrix} \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}\\ &= \frac{1}{345} \begin{pmatrix} 5 & 85 & 130\\ 25 & 80 & -40 \end{pmatrix} \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}\\ &= \frac{1}{69} \begin{pmatrix} 1 & 17 & 26\\ 5 & 16 & -8 \end{pmatrix} \begin{pmatrix} 2\\ 2\\ 4 \end{pmatrix}\\ &= \frac{1}{69} \begin{pmatrix} 2 + 34 + 104\\ 10 + 32 - 32 \end{pmatrix}\\ &= \frac{1}{69} \begin{pmatrix} 140\\ 10 \end{pmatrix} \end{aligned}
Korollar 10.10 Eigenwerte werden später definiert

Die 2-Norm-Konditionszahl (kurz: Kondition) einer Matrix A∈En×nA \in \mathbb{E}^{n \times n} ist gegeben durch

κ2=max⁡{∣ω∣}min⁡{∣ω∣},\kappa_2 = \frac{\max \{ |\omega| \}}{\min \{ |\omega| \}},

wobei ω\omega der Eigenwert von AA ist (gilt für symmetrische/hermitesche reguläre AA).

Insbesondere ist die Konditionszahl immer grösser oder gleich 1.

Bemerkung

Wir möchten immer eine möglichst kleine Kondition haben, da dann die Implementierung numerisch am stabilsten ist, d.h. grosse Kondition ist schlecht und unerwünscht.

Bemerkung

Die QR-Zerlegung ist für m≥nm \geq n und Rang(A)=n\text{Rang}(A) = n eindeutig, wenn man die Vorzeichen der Diagonalelemente von der Dreiecksmatrix vorgibt.

Bemerkung Normalengleichung vs. QR-Zerlegung

Normalengleichung

Pro:

  • "schön" um von Hand zu rechnen
  • AHAA^HA ist hermitesch positiv definit ⇒\Rightarrow kann für Cholesky-Zerlegung ausgenutzt werden

Con:

  • Wenn AA schlecht konditioniert ist, ist AHAA^HA quadratisch schlecht konditioniert. ⇒\Rightarrow Cholesky liefert unbrauchbare Resultate (Rundungsfehler massiv verstärkt, Implementierung instabil)

QR-Zerlegung

Pro:

  • kann numerisch stabil implementiert werden (Verfahren hängt weniger von der Kondition ab)
  • QQ ist Projektion der Spalten von AA

Con:

  • "hässlich", um von Hand zu rechnen (Wurzeln)