Study Guides / Linear Algebra / Exercise session 9
EXERCISE SESSION 9 · ETH ZURICH · HS19 · linalg

Inner Product, Gram-Schmidt and QR Decomposition

Bilinear form, inner product, orthogonal basis (ONB), orthogonal projection, Gram–Schmidt process, QR decomposition

SB
Steven Battilana Quant · ex-ETH

Inner Product

Definition

A map 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) is called a bilinear form (BLF) on En\mathbb{E}^n if it is linear in both arguments: ∀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

Let BB be a BLF mapping to R\mathbb{R}. BB is called symmetric if B(v,w)=B(w,v)B(v,w) = B(w,v) and alternating if B(v,w)=−B(w,v)B(v,w) = -B(w,v), for ∀v,w∈En\forall v,w \in \mathbb{E}^n.

Definition

A map 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) is called sesquilinear on En\mathbb{E}^n if it is linear in the second argument and semilinear in the first argument: ∀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

A sesquilinear form BB mapping to C\mathbb{C} is called Hermitian if B(v,w)=B(w,v)‾B(v,w) = \overline{B(w,v)}.

Definition

A sesquilinear form BB is called positive definite if

B(v,v)>0for every v∈En with v≠0.B(v,v) > 0 \quad \text{for every } v \in \mathbb{E}^n \text{ with } v \neq 0.
Remark

A symmetric, positive definite BLF is called a Euclidean inner product.

Definition

An inner product is a map ⟨⋅,⋅⟩: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 such that: ∀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 (bilinearity or sesquilinearity)
  2. ⟨v,w⟩=⟨w,v⟩‾\langle v,w \rangle = \overline{ \langle w,v \rangle } (symmetry or Hermitian)
  3. ⟨v,v⟩≥0\langle v,v \rangle \geq 0 (positive semidefinite)
  4. ⟨v,v⟩≥0\langle v,v \rangle \geq 0 and ⟨v,v⟩=0⇔v=0\langle v,v \rangle = 0 \Leftrightarrow v = 0 (positive definite)
Definition

The length or Euclidean norm of a vector x∈Enx \in \mathbb{E}^n is the non-negative real number ∥x∥\left\lVert x \right\rVert defined by

∥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}.
Remark

Let x,y∈Rnx,y \in \mathbb{R}^n and α∈[0,π]\alpha \in [0, \pi] the angle between xx and yy, then:

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

Let B={bi}i∈I\mathcal{B} = \{b_i\}_{i \in I} be a basis of VV, ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle an inner product on VV.

  • B\mathcal{B} is called orthogonal ⇔⟨bk,bl⟩=0,∀k≠l\quad \Leftrightarrow \quad \langle b_k,b_l \rangle = 0, \forall k \neq l
    In words: the basis vectors "are ⊥\perp to each other".
  • B\mathcal{B} is called 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 words: the basis vectors "are ⊥\perp to each other" and have length 11.
Remark

Let VV be a vector space with inner product ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle, B={bi}i∈I\mathcal{B} = \{b_i\}_{i \in I} a basis of VV. By the definition of a basis, you can write every v∈Vv \in V as v=∑i∈Iαibiv = \sum_{i \in I} \alpha_i b_i. If B\mathcal{B} is an ONB, then αi=⟨bi,v⟩,  ∀i∈I\alpha_i = \langle b_i, v \rangle, \,\, \forall i \in I,
⇒\Rightarrow \quad the coordinates of vv with respect to B\mathcal{B} are ⟨bi,v⟩\langle b_i, v \rangle.

The Outer Product and the Orthogonal Projection

Remark
  • inner product: ∀x,y∈En:⟨x,y⟩=xHy∈E\forall x,y \in \mathbb{E}^n: \quad \langle x,y \rangle = x^Hy \in \mathbb{E}
  • outer product: ∀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

The orthogonal projection PYxP_Yx of x∈Enx \in \mathbb{E}^n onto the line through the origin spanned by yy is:

PYx:=1∥y∥2yyHx=uuHx with u:=y∥y∥P_Yx := \frac{1}{\left\lVert y \right\rVert^2} yy^Hx = uu^Hx \text{ with } u := \frac{y}{\left\lVert y \right\rVert}
  1. y-direction: PYx=αy,  α∈E\quad P_Yx = \alpha y,\,\, \alpha \in \mathbb{E}
    (PYxP_Yx is a point on yy).
  2. x-direction: (x−PYx)⊥y\quad (x-P_Yx) \perp y.
Remark projection matrix
  • PYx:=1∥y∥2yyHx=uuHx with u:=y∥y∥P_Yx := \frac{1}{\left\lVert y \right\rVert^2} yy^Hx = uu^Hx \text{ with } u := \frac{y}{\left\lVert y \right\rVert}
  • PYH=PYP_Y^H = P_Y (symmetric/Hermitian)
  • PY2=PYP_Y^2 = P_Y (idempotent; this is an alternative definition of a projection)

Gram-Schmidt Process

Satz

Every vector space of finite or at least countable dimension has an ONB. (i.e. it can be constructed with Gram-Schmidt)

Algorithm Gram-Schmidt process
  1. Let VV be a Euclidean/unitary vector space with dim(V)=n<∞\text{dim}(V) = n \lt \infty
  2. Given: W=span{v1,...,vm}⊂V,  {vi}i=1mW = \text{span}\{v_1, ..., v_m\} \subset V, \,\, \{v_i\}_{i=1}^m basis of WW is linearly independent
  3. Wanted 1: w1,...,wmw_1, ..., w_m such that W=span{w1,...,wm}W = \text{span}\{w_1, ..., w_m\} and {wi}i=1m\{w_i\}_{i=1}^{\boldsymbol{m}} ONB of WW is orthonormal
  4. Wanted 2: w1,...,wm,wm+1,...,wnw_1, ..., w_m, w_{m+1}, ..., w_n such that V=span{w1,...,wn}V = \text{span}\{w_1, ..., w_n\} and {wi}i=1n\{w_i\}_{i=1}^{\boldsymbol{n}} ONB of VV is orthonormal.
  5. w1=v1∥v1∥w_1 = \frac{v_1}{\left\lVert v_1 \right\rVert} with ∥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. for k∈{2,...,m}k \in \{2, ..., m\}
  7. Set v:=vkv := v_k (we have 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} with ∥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)} is an ONB of WW.
  12. If you want to extend W(m)W^{(m)} to an ONB of VV:
  13. For k∈{m+1,...,n}k \in \{m+1, ..., n\}
  14. Choose 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} with ∥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)} is an ONB of VV.
Example 1

Given: the vector space P2\mathcal{P}_2 over R\mathbb{R} with inner product ⟨p,q⟩P=∫−11p(t)q(t)dt\langle p,q \rangle_\mathcal{P} = \int\limits_{-1}^1 p(t)q(t) dt and monomial basis B={1,t,t2}\mathcal{B} = \{1, t, t^2\}. Here: V=W=P2V=W=\mathcal{P}_2
Wanted: an ONB that is orthogonal with respect to ⟨⋅,⋅⟩P\langle \cdot, \cdot \rangle_\mathcal{P} ⇒\quad \Rightarrow \quad we have to orthonormalise 1,t,t21,t,t^2 with respect to ⟨⋅,⋅⟩P\langle \cdot, \cdot \rangle_\mathcal{P}.

Show solutionHide solution

1.

w1=1∥1∥P=12,because∥1∥P=∫−111dt=2w_1 = \frac{1}{\left\lVert 1 \right\rVert_\mathcal{P}} = \frac{1}{\sqrt{2}}, \quad \text{because} \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=32tbecause∥t∥P=∫−11t2dt=[13t3]−11=23w_2 = \frac{t}{\left\lVert t \right\rVert_\mathcal{P}} = \sqrt{\frac{3}{2}} t \quad \text{because} \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)because∥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{because} \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)} is an ONB of 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{ is an ONB of } \mathcal{P}_2.

QR Decomposition

Remark

Let A∈Em×nA \in \mathbb{E}^{m \times n}. Assume rank(A)=n≤m\text{rank}(A) = n \leq m (full rank). Then there exists an orthogonal/unitary matrix Q=(Q1∣Q2)Q = (Q_1 | Q_2) with 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)} and there exists an upper triangular matrix R1∈En×nR_1 \in \mathbb{E}^{n \times n}, and with 0∈E(m−n)×n\boldsymbol{0} \in \mathbb{E}^{(m-n) \times n}, such that

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

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

Remark connection between QR decomposition and least squares

For the residual rr we have r=y−∑i=1n⟨qi,y⟩qir = y - \sum \limits_{i=1}^n \langle q_i, y \rangle q_i, where {qi}i=1n\{q_i\}_{i=1}^n denotes the columns of Q1Q_1.

Remark

If the inner product under consideration is the standard inner product, then:

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}

A different inner product gives a different formula for xx!

Algorithm QR decomposition
  1. Given: A∈Em×n,  m>n,  ⟨⋅,⋅⟩A \in \mathbb{E}^{m \times n}, \,\, m > n, \,\, \langle \cdot, \cdot \rangle an inner product
  2. Wanted: Q1,R1Q_1, R_1, such that A=Q1R1A = Q_1R_1.
  3. Q1: Let a1,...,ana_1, ..., a_n be the columns of AA. Apply the Gram-Schmidt process with respect to ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle to {ai}i=1n\{a_i\}_{i=1}^n. This gives you {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. where qi~\widetilde{q_i} denotes the ii-th orthogonalised but not yet normalised vector.
  8. 2. R1=(rij)1≤i,j≤nR_1 = (r_{ij})_{1 \leq i,j \leq n}
Example 2

Given:

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}

Wanted: use the QR decomposition to determine x=(x1,x2)Tx = (x_1, x_2)^T such that ∥r∥22=∥y−Ax∥22\left\lVert r \right\rVert_2^2 = \left\lVert y - Ax \right\rVert_2^2 is minimal with respect to the standard inner product ⟨x,y⟩=xHy\langle x,y \rangle = x^Hy.

Show solutionHide solution

(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}
Corollary 10.10 eigenvalues are defined later

The 2-norm condition number (condition for short) of a matrix A∈En×nA \in \mathbb{E}^{n \times n} is given by

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

where ω\omega is the eigenvalue of AA (holds for symmetric/Hermitian regular AA).

In particular, the condition number is always greater than or equal to 1.

Remark

We always want the condition to be as small as possible, because then the implementation is numerically most stable, i.e. a large condition is bad and undesirable.

Remark

The QR decomposition is unique for m≥nm \geq n and rank(A)=n\text{rank}(A) = n if you fix the signs of the diagonal entries of the triangular matrix.

Remark normal equations vs. QR decomposition

Normal equations

Pro:

  • "nice" to compute by hand
  • AHAA^HA is Hermitian positive definite ⇒\Rightarrow can be exploited for the Cholesky decomposition

Con:

  • If AA is ill-conditioned, AHAA^HA is quadratically ill-conditioned. ⇒\Rightarrow Cholesky delivers useless results (rounding errors massively amplified, implementation unstable)

QR decomposition

Pro:

  • can be implemented in a numerically stable way (the method depends less on the condition)
  • QQ is the projection of the columns of AA

Con:

  • "ugly" to compute by hand (square roots)