next up previous
Next: About this document ...

Chapter 3.4 O.N. vectors and the Gram-Schmidt Process

$A \in {I\!\!R}^{ n \times n }$ , and $\{ e_1 , \cdots , e_n \}$

then $[A e_1 , A e_2 , \cdots , A e_n ]$

A ej : the j-th column of A

(eiT A : the i-th row of A )

$Ax : span \{ A_1 , \cdots , A_n \} , A_i ~column~vectors~of~A .$

$x^T A :span \{ a_1 ,\cdots , a_n \} , a_j ~row~vectors~of~A .$

[Def] $Q \in {I\!\!R}^{ n \times m }$ , $n \geq m$ is called isometric $\Leftrightarrow Q^T Q = I_m$

( $Q Q^T = I \ne Q ~~is~isometric$ )

i.e. the column vectors are O.N.

$A \in {I\!\!R}^{ n \times m } , n \geq m $, then $A = \hat Q \hat R $ where $ \hat Q \in {I\!\!R}^{ n \times m }$

$\hat R \in {I\!\!R}^{ m \times m }$ and $ \hat Q $ is isometric .

<Proof> A = QR , Q $\in {I\!\!R}^{ n \times n }$ , $R \in {I\!\!R}^{ n \times m }~~$ $n \geq m$where $Q = [ \hat Q , \hat Q ] $ , R = $\left [ \matrix{ \hat R \cr 0 \cr } \right ]$ $\Rightarrow A = QR =$ $\left [ \matrix{ \hat Q , \hat Q } \right ]$ $\left [ \matrix{ \hat R \cr 0 \cr } \right ]$ = $\hat Q \hat R + \hat Q 0 $ = $\hat Q \hat R$

Gram-Schmidt

$\{ v_1 , v_2 ,\cdots , v_m \} \leftrightarrow
\{ g_1 , g_2 , \cdots , g_m \} , g_i$ : O.N.vectors

Exercise : P168 Ex3.4.1 Ex3.4.3 Gram-Schmidt process $\{ v_1 , \cdots , v_m \}$ is a basis

$\Rightarrow \{ g_1 , g_2 , \cdots , g_n \}$ orthonormal basis

such procsee is called Gram-Schmidt orthonomalization .

$v_1 \rightarrow g_1 = {{ v_1 } \over {\Vert v_1 \Vert}}$

$\left \{
\matrix{ {\~ g}_2 = v_2 - < v_2 , g_1 > \cdot g_1 \cr
{g_2} = {{{\~ g}_2} \over {\Vert g_2} \Vert} \cr }
\right $

$\left \{
\matrix{ {\~ g}_3 =
v_3 - < v_3 , g_2 > \cdot g_2 - < v_3 , g_1 > \cdot g_1 \cr
{g_3} = {{{\~ g}_3} \over {\Vert g_3} \Vert} \cr } \right $

In general

$\left \{
\matrix{ {\~ g}_k = v_k - \sum^{ k - 1 }_{ i = 1 } < v_k , g_j > g_j \cr
g_k ={ {{\~ g}_k } \over {\Vert g_k \Vert}} \cr } \right $ $\Rightarrow$ $v_k = \sum_{j=1} r_{jk} g_j + r_{kk} g_k $,

Let $ r_{kk} = \Vert {\~ g}_k \Vert , j=k$

Let rjk = < vk , gj > , j < k

$V=[ v_1 , v_2 ,\cdots , v_n ]$ = $[ g_1 , g_2 , \cdots , g_n ]$ $\left [ \matrix{ r_{11}& r_{12} & \cdots & r_{1n} \cr
0 & r_{22} & \cdots & r_{2n} \cr 0 & 0 & \ddots & \vdots \cr
0 & 0 & 0 & r_{nn} \cr } \right ] $

vi are the column vextors of V

$\left \{ \matrix{ r_{jk} = < v_k , g_j > \cr
r_{kk} = \Vert {\~ g}_k \Vert \cr } \right $

1. Subspace : $\varphi \subset {I\!\!R}^n $ is subspace of ${I\!\!R}^n$

if $\varphi \ne 0 $ and $\left \{
\matrix{ u,v \in \varphi \Rightarrow u + v \in \varphi \cr
cu \in \varphi , c \in I\!\!R \cr} \right $

2. Linear Independent 3. Span $\{ v_1 , v_2 , \cdots , v_n \}$ = $< v_1 , v_2 , \cdots , v_n >$ $\left \{ \matrix{ < v_1 > = < g_1 > \cr
< v_1 , v_2 > = < g_1 , g_2 > \cr \vdots \cr
< v_1 , \cdots , v_n > = < g_1 , \cdots , g_n > \cr } \right $

If $< v_1 , v_2 , \cdots , v_m >$ = $< w_1 , w_2 , \cdots , w_m >$

$\Rightarrow < v_1 , v_2 , \cdots , v_m , u >$ = $< w_1 , w_2 , \cdots , w_m , u >$

$\varphi \subset {I\!\!R}^n $ subspace of ${I\!\!R}^n$

${\varphi}^{\bot} = \{ x \in {I\!\!R}^n \vert ( x , y ) = 0 ,
\forall y \in \varphi \}$ is the orthogonal complement of $\varphi$ .

Note : 1. $\varphi^{\bot} $ is also a subspace of ${I\!\!R}^n$ . 2. $\varphi = < g_1 , g_2 , \cdots , g_k > $ $\Rightarrow {\varphi}^{\bot} < g_{k+1} , \cdots , g_n > g_i $ are the O.N. vectors .

[Thm] $ \varphi \in {I\!\!R}^n$ subspace of ${I\!\!R}^n$ , then ${I\!\!R}^n = \varphi \oplus {\varphi}^{\bot} $

( i.e. $\Rightarrow$ if $x \in {I\!\!R}^n $ , then $ x = \rho + {\rho}^{\bot}$,where $\rho \in \varphi , \rho \in {\varphi}^{\bot} $

moreever , $\varphi \cap {\rho}^{\bot} = \{ 0 \} $ )

<Proof> $\varphi = < v_1 , \cdots , v_m > = < g_1 , \cdots , g_m >$

${I\!\!R}^n$ = $< v_1 , \cdots , v_m , v_{m+1} , \cdots , v_n >$ = $< g_1 , \cdots , g_m , g_{m+1} , \cdots , g_n > $

and $< v_{m+1} , \cdots , v_n >$ = $< g_{m+1} , \cdots , g_n > $

$\varphi$ = $< g_1 , \cdots , g_m >$ = $< g_{m+1} , \cdots , g_n > = {\varphi}^{\bot} $

$\Rightarrow x = \rho + {\rho}^{\bot}$

$\varphi \cap {\varphi}^{\bot} = \{ 0 \}
\par\Rightarrow {I\!\!R}^n = \varphi \oplus {\varphi}^{\bot}$

$A : {I\!\!R}^m \rightarrow {I\!\!R}^n ( A \in {I\!\!R}^{n \times m} )$

N(A) = null space of $ A = \{ x \vert Ax = 0 \} \subset {I\!\!R}^m$

R(A) = range of $A = \{ Ax \vert x \in {I\!\!R}^m \} \subset {I\!\!R}^n $ [Thm] $A : {I\!\!R}^m \rightarrow {I\!\!R}^n ( A \in {I\!\!R}^{n \times m}) ~~x \in {I\!\!R}^m , y \in {I\!\!R}^n$ then < nx , y > = < x , AT y >

$\Rightarrow$ yT A x = (AT y)T x

[Thm] $R {(A)}^{\bot} = N( A^T ) $

[Thm] ${I\!\!R}^m = R(A) \oplus N( A^T )$

${I\!\!R}^n = R( A^T ) \oplus N(A) $

[Thm] If A is symmetric , ${I\!\!R}^n = N(A) \oplus R(A) $

$\varphi \subset {I\!\!R}^n $

${\varphi}^{\bot} = \{ x \vert ( x , y ) = 0 , \forall y \in \varphi \}$

If $A \in {I\!\!R}^{ n \times m } $ ( i.e. $A : {I\!\!R}^m \rightarrow {I\!\!R}^n $)

Range : R(A) = $\{ Ax \vert x \in {I\!\!R}^m \} \subset {I\!\!R}^n $

Null space : N(A) = $\{ x \in {I\!\!R}^m \vert Ax = 0 \} \subset {I\!\!R}^m $

<Proof of $R {(A)}^{\bot} = N( A^T ) $>

$( \Rightarrow ) $ If $ y \in R{(A)}^T \Rightarrow ( Ax , y ) = 0 \Rightarrow ( x , A^T y ) = 0 $ for all x

$ \Rightarrow A^T y = 0 \Rightarrow y \in N( A^T )$

In particular $= {\Vert A^T y \Vert}^2_2 = ( A^T y , A^T y ) = 0 $

i.e. $R {(A)}^{\bot} < N( A^T ) $

$( \Leftarrow ) $ If $ y \in N( A^T ) \Rightarrow A^T y = 0 \Rightarrow ( x , A^T y ) = 0
\par\Rightarrow ( Ax , y ) = 0 \Rightarrow y \in R{(A)}^{\bot}$

i.e. $N( A^T ) \subset R {(A)}^T $

[Lemma] ${\varphi}^{\bot \bot} = \varphi $

[Thm] $R( A^T ) = N {(A)}^{\bot}$

<Proof> Because $R {(A)}^{\bot} = N( A^T )
\par\Rightarrow R{( A^T )}^{\bot} = N( A^{TT} ) = N(A)
\par\Rightarrow {[ R{( A^T )}^{\bot} ]}^{\bot} = {[ N(A) ]^{\bot}} $

$\left \{
\eqalign{ {I\!\!R}^n = R(A) \oplus N( A^T ) \cr
{I\!\!R}^m = R( A^T ) \oplus N(A) \cr
}
\right $

Note : nullity (T) + range (T) = dim S

( If T : S $\rightarrow$ S linear transformation )

Exercise : 3.5.7

$\left \{
\matrix{ The ~colume~space~ = R(A) \cr
The ~row~space~of~A~ = N {(A)}^{\bot}
}
\right $ $\Rightarrow \left \{
\matrix{ R {(A)}^{\bot} = N (A^T) \cr
N {(A)}^{\bot} = R (A^T) \cr
}
\right \}$ ( because column space A = row space of AT )

$\S$ The Discrete Least-Square Problem

If $A \in {I\!\!R}^{n \times m} , n > m$

$\Vert b - Ay \Vert = {min}_{ w \in {I\!\!R}^n } \Vert b - Aw \Vert $

[Thm] ( Pythagorean Thm. )

${\Vert u + v \Vert}^2 =
{\Vert u \Vert}^2 + {\Vert v \Vert}^2$ if ( u ,v ) = 0

<Proof> ${\Vert u + v \Vert}^2 = < u + v , u + v >$ = < u , u > + < u , v > + < v , u > + < v , v > = ${\Vert u \Vert}^2 + {\Vert v \Vert}^2 $

Note : The Least-Square Error $b - Ay \in R {(A)}^2 $

[Thm] If $\varphi \in {I\!\!R}^n , b \in {I\!\!R}^n $ , then $\exists y \in \varphi$

such that ${\Vert b - y \Vert}_2 =
{min}_{ s \in \varphi } {\Vert b - s \Vert}_2$

where y is the unique element in $\varphi$

such that $ b - y \in {\varphi}^{\bot} $

( i.e. y is the orthogonal projection of b into $\varphi$ )

[Cor] Let $A \in {I\!\!R}^{ n \times m } $ . Then ${\Vert b - Ax \Vert}_2$ = ${min}_{w \in {I\!\!R}^m} {\Vert b - Aw \Vert}_2
\par\Leftrightarrow b - Ax \in R {(A)}^{\bot}$

<Proof> ${I\!\!R}^n = \varphi \oplus {\varphi}^{\bot} $

b = y + z , where $y \in \varphi , z \in {\varphi}^{\bot} $

$b - y = z \in {\varphi}^{\bot}$ ${I\!\!R}^n = \varphi \oplus {\varphi}^{\bot} $

b = y + z uniquelly , with $y \in \varphi , z \in {\varphi}^{\bot} $ and $b - y = z \in {\varphi}^{\bot}$

If $w \in \varphi$ s.t. $b = w + ( b - w ) \Rightarrow w = y $

$( {\Vert b - y \Vert}_2 = {min}_{s \in \varphi} {\vert b - s \vert}_2 )$

consider b - s = ( b - y ) + ( y - s ) , where $ s \in \varphi , y \in \varphi $

$\Rightarrow$ ${\Vert b - s \Vert}^2_2$ = ${\Vert b - y \Vert}^2_2 + {\Vert y - s \Vert}^2_2$

$\Rightarrow$ ${\Vert b - s \Vert}_2 $ is $min \Leftrightarrow y = s $

i.e. $\Vert b - y \Vert = {min}_{s \in \varphi } \Vert b - s \Vert$

$ Ax = b . A \in {I\!\!R}^{n \times m} , n > m$

$\Leftrightarrow$ $b - Ax \in R {(A)}^{\bot} = N( A^T ) $

$\Leftrightarrow$ AT ( b - Ax ) = 0

$\Leftrightarrow$ AT A x = AT b ( normal equation )

Note : $ A^T A \in {I\!\!R}^{ m \times m}$

Note : 1. Solving L.S. Problems Ax = b , $A \in {I\!\!R}^{ n \times m } $ is the same to solving normal equation AT A x = AT b . 2. AT A i. symmetry . ii. nonneqative defined ( Positive semidefined $x^T B x \geq 0$ ). 3. If A is full rank ( i.e. rank A = m ) , then AT A is positive define $\Rightarrow$ Chelosky Decomposition ( on AT A ) to solve the ( AT A ) x = AT b

The way of solving Least Square Solution :

1. QR 2. Cholesky 3, A $\backslash$ b

1. (AT A)T = AT ATT = AT A2. nonnegative defined

$\forall x \ne 0 , x^T (A^T A) x \geq 0$ $\Rightarrow {\Vert Ax \Vert}^2_2 \geq 0$3. <Proof> A is full rank , AT A is nonsingular . If $(A^T A) x = 0 \Rightarrow x = 0$ for all $x \ne 0 , x^T (A^T A) x > 0 .$

$\S$ The Continuous Least Square Problem

Discrete ${\Vert b - Ax \Vert}_2 = min \Vert b - Aw \Vert$

Continuous ${\Vert f - \phi \Vert}_2 = min \Vert f - \psi \Vert $

$\Rightarrow f - \phi \in {\varphi}^{\bot} , \phi \in \varphi
(unique)
\Rightarrow < f - \phi , \psi > = 0 , \forall \psi \in \varphi$

Inner Product :

$< x , y > = \sum^n_{i=1} x_i y_i = y^T x $

$ < f , g > = \int f(x) g(x) dx$

2-norm

${\Vert x \Vert}^2_2 = < x , x > =
\sum^n_{i=1} x^2_i ( {\Vert \cdot \Vert}_{l_2} )$
${\Vert f \Vert}^2_2 = < f , f > =
\int 1^2 dx ( {\Vert \cdot \Vert}_{L_2} )$

${\Vert f - \phi \Vert}_2 = min \Vert f - \psi \Vert $

$\Rightarrow f - \phi \in {\varphi}^{\bot} , \phi \in \varphi (unique)$

$\Rightarrow < f - \phi , \psi > = 0 , \forall \psi \in \varphi$

If $\{ {\phi}_1 , \cdots , {\phi}_m \}$ are basis of $\varphi$ .

$\Rightarrow < f - \sum^m_{i=1} c_i {\phi}_i , {\phi}_i > = 0$ , $i = 1 , 2 , \cdots , m , \phi = \sum c_i {\phi}_i$

$\Rightarrow < f , {\phi}_i > = < \sum^m_{i=1} c_i {\phi}_i , {\phi}_i >$ , $i = 1 , 2 , \cdots , m $

( m equations )

$c_1 < {\phi}_1 , {\phi}_1 > + c_2 < {\phi}_2 , {\phi}_1 >$ , $\cdots , c_m < {\phi}_m , {\phi}_1 > = < f , {\phi}_1 >$

$c_1 < {\phi}_1 , {\phi}_2 > + c_2 < {\phi}_2 , {\phi}_2 >$ , $\cdots , c_m < {\phi}_m , {\phi}_2 > = < f , {\phi}_2 >$


\begin{displaymath}\vdots\end{displaymath}

$c_1 < {\phi}_1 , {\phi}_m > + c_2 < {\phi}_2 , {\phi}_m >$ , $\cdots , c_m < {\phi}_m , {\phi}_m > = < f , {\phi}_m >$

cx = d

c = $\left [ \matrix{ < {\phi}_1 , {\phi}_1 > , < {\phi}_2 , {\phi}_1 > ,
\cdots , <...
...> , < {\phi}_2 , {\phi}_m > , \cdots ,
< {\phi}_m , {\phi}_m > \cr } \right ] $

$\left [
\matrix{ c_1 \cr c_2 \cr \vdots \cr c_m \cr }
\right ] =
\left [
\matrix{ < f , {\phi}_1 > \cr
\vdots \cr
< f , {\phi}_m > \cr
}
\right ]$

Note : c is 1. Symmetry . 2. Positive defined .



 
next up previous
Next: About this document ...

1998-08-14