Chapter 3 Orthoginal Matrices and the Least-Squares Problem

[Def] Q is orthogonal matrix if QQT = I ( QT = Q-1)

Note : If Q orthogonal

< gi , gj > = are row ( column ) vectors of Q .
is a inner product if

1. < x , y > = < y , x >
2. < x + y , z > = < x , z > + < y , z >
3. = < x . y > + < x , z >
4. < x , x > 0 ( < x , x > = 0 < x = 0 >

Example : < x , y > = xT y = yT x

= < x , x > = xT x ( because If  x = < x1 , x2 , ... , xn >

= x21 + x22 + ... , x2n )

Cauchy Schwartz Inequality :

( )

The angle of two vector x,y satisfy =

i.e. =

Least-Square Problems :

Example :
over-determinate
Least Square Problem :

Find the best answer xT , satisfy b - A xT minimal .

Note : use A=QR can solve Least Square Solution xT of Ax=b .

[Thm] A=QR

where Q : Orthogonal R : upper triangular

Use A = QR to solve the system of AX = b :

STEP 1. QRx = b
STEP 2. Rx = QTb
STEP 3. Let   QT b = d
STEP 4. Solve  Rx = d   by  the backward subsitution.

In MATLAB , A = QR

>> [ Q , R ] = qr(A)

: Rotator is an orthogonal matrix

Q orthogonal =

[Lemma]

< Qx , Qy > = < x , y >

< Qx , Qy > = (Qy)T (Qx) = yT ( QT Q ) x = yT x = < x , y >

when   x=y < Qx , Qy > = < x , x >

Qx 22

Least-Square Problem :

= = ( If A=QR )

A is nonsingular

column vectors are l.I. .

row vectors are l.I. .

Rotator :

Q =

(Q-1 = ) = QT = =

then , cos = ? , sin = ?

x1 sin = x2 cos

cos = , sin =

( because must be satisfy + = 1 ) Given matrix :

=

i th   j th    column C = S =

Reflectors : (Picture:)

Reflectors : Q

If P = u uT    = 1    P2 = P ( projection )

1. Pu = -u

because   Pu = u uT u = u
2. Pv = v

Pv = u ( ut v ) = 0

Let   Q = I - 2P    Q2 = I  ( idempotent )

then , Qu = I(u) - 2P(u) = u - 2u = -u and QV = I(v) - 2P(v) = v - 0 = v

so satisfy Reflector i.e. Q = I - 2 u uT ( Householder transformation )

Note : u uT is the rank 1 matrix .

Q = I - r u uT , u has no limitation = 1   r =

[Thm] = , ! Q orthogonal s.t. Qx = y .

Example : A = = QR
We hope to find QT , x , QT . A = R   ( A=QR )
Q =

P147 Figure 3.4

1. x = +
[ Note : ]
2. Q = I - r u uT  ,  r =

u1 = ( x - y )
[ In the analysis of QR . x : the column vector of the origin A . y : the column vector of the origin R ]

reduction u =
Q = I - 2 u uT

x - y =

so   u = , =

Q = -

Example :

A = = QR
Q = I - 2 =
-
= =

QT . A = =
u = x - y = - =

=
A = QR

1. Use Rotator ( Jacobi matrix ) Q =
2. Reflector : Q = I - 2 u uT ( Orthogonal projector )
3. Gram-Schmidt Orthonomalization