KKKQ1223

ENGINEERING MATHEMATICS
(LINEAR ALGEBRA)

• BEST APPROXIMATION; LEAST SQUARES

• LEAST SQUARES FITTING TO DATA
BEST APPROXIMATION
LEAST SQUARES SOLUTIONS OF LINEAR SYSTEM

 Solved linear system that cannot be solved exactly and for which an approximate solution needed.

why? caused by measurement error

Ax = b inconsistent
in the coefficients of A.
(m equations &
n unknowns)
want to find x no exact solution
is possible

You can think Ax as an solution?

approximation to b and
b  Ax as the error in that look for a vector x that comes
Approximation or least as “close as possible” – minimizes b  Ax
squares error.
least square solution least square error
vector
BEST APPROXIMATION
BEST APPROXIMATION

THEOREM 6.4.1 BEST APPROXIMATION THEOREM

If W is a finite-dimensional subspace of an inner product space V, and if b is a vector in V, then
projW b is the best approximation to b from W in the sense that

b  projW b  b  w

for every vector w in W that is different from projW b .

BEST APPROXIMATION
LEAST SQUARE SOLUTIONS OF LINEAR SYSTEMS

THEOREM 6.4.2
For every linear system Ax = b, the associated normal system

AT Ax  AT b

is consistent, and all solutions of the above equation are least squares solutions of Ax = b. Moreover, if W is the
column space of A, and x is any least squares solutions of Ax = b, then the orthogonal projection b on W is

projW b  Ax
BEST APPROXIMATION
LEAST SQUARE SOLUTIONS OF LINEAR SYSTEMS

 AT Ax  AT bis called the normal equation of the normal system associated with Ax = b.
 If a linear system is consistent, then its exact solutions are the same as its least square solutions, in which case the
error is zero.
BEST APPROXIMATION
UNIQUENESS OF LEAST SQUARES SOLUTIONS

 In general, least squares solution of linear systems are not unique.

THEOREM 6.4.3

If A is an m x n matrix, then the following are equivalent.

(a) A has linearly independent column vectors.

(b) ATA is invertible.
 BEST APPROXIMATION
UNIQUENESS OF LEAST SQUARES SOLUTIONS

THEOREM 6.4.4

If A is an m x n matrix with linearly independent column vectors, then for every m x 1 matrix b, the linear system
Ax = b has a unique least squares solution. This solution is given by


x A A T
 1
AT b
Moreover, if W is the column space of A, then the orthogonal projection of b on W is

projW b  Ax  A A  T
 1
AT b
BEST APPROXIMATION
EXAMPLE 1

(a) Find all least square solutions of the linear system

3 z  x  4
y  5z  1
6x  2z  3
x yz 4
(b) Find the error vector and the error.
 Solution
(a) Express the system in the matrix form, Ax  b :
1 0 3  4 
0 1 5  x 1
A  
, x  y , b   
6 0 2   3
   z   
  1  1  1 4
1 0 3  4 
1 0 6 1   38 1 16  1 0 6 1   18 
0 1 5 1  
AT A  0 1 0 1     1 2 6 , 
A b  0 1 0 1
T    3
6 0 2   3  
 3 5 2 1   16 6 39   3 5 2 1   19 
 1 1 1 4

the normal system AT Ax  AT b

38 1 16   x  18 
 1 2 6   y    3
    
16 6 39   z  19 
 Solving this system yields a unique least squares solution;

x  0.0736, y  5.4002, z  1.2878

(b) The error vector is

 4   1 0 3   0.06306 
 1   0 1 5   0.0736   0.0388 
b  Ax        5.4002    
 3   6 0 2    0.01698
     1.2878   
4
    1 1 1   0.0388 

b  Ax  0.085298
BEST APPROXIMATION
EXAMPLE 2

Find the orthogonal projection of u on the subspace of R3 spanned by the vectors v1 and
v2 .

u = (1, 2, 3); v1 = (2, 1, 0), v2 = (-1, 1, 0)

 Solution
The subspace W of R3 spanned by v1 , and v 2 is the column space of the matrix
 2 1
A  1 1 
 0 0 

Thus, Ax  u
 2 1 1 
1 1   x    2
   y  
 0 0     3 

so,
 2 1 1 
 2 1 0    5 1  2 1 0     4
A A
T
  1 1  , A u
T
  2   
 1 1 0   0 0   1 2   1 1 0   3  1 
   
The normal system A Ax  A u is
T T

 5 1  x   4 
 1 2   y    1 
    
Solving this system yields
 x  1
x  
 y  1

so,
 2 1 1 

1
projW u  Ax  1 1      2 
1
 0 0    0 

or projW u   1, 2, 0 
 BEST APPROXIMATION
THE ROLE OF QR-DECOMPOSITION IN LEAST SQUARES PROBLEMS

*Both formulas in Theorem 6.4.4 are not well suited for numerical computation.

THEOREM 6.4.5

If A is an m x n matrix with linearly independent column vectors, and if A = QR is a QR-decomposition of A (see

Theorem 6.3.7), then for each b in Rm the system Ax = b has a unique least squares solution given by

x  R 1QT b
BEST APPROXIMATION
ORTHOGONAL PROJECTIONS ON SUBSPACE OF Rm

DEFINITION 1

If W is a subspace of Rm , then the linear transformation P:R m

Wmaps each vector x in Rm into its
that
orthogonal projection projW x in W is called the orthogonal projection of Rm on W.

• To find the orthogonal projections on subspace of Rm which is the transformation P on the definition above is
following the first formula in Theorem 6.4.4,

 P  A A A
T 1
AT
where A is constructed using any basis for W as its column vectors.
BEST APPROXIMATION
MORE ON THE EQUIVALENCE THEOREM

There is one additional equivalence statement added up to existing equivalence theorem.

Please refer page 365 & 366 for the theorem.
 LEAST SQUARE FITTING TO DATA
THEOREM 6.5.1 Uniqueness of the Least Squares Solution

Let (x1, y1), (x2, y2), …, (xn, yn) be a set of two or more data points, not all lying on a vertical line, and let
1 x1   y1 
1 x2  y 
M  and y   2 
   
   
1 xn   yn 
a * 
Then there is a unique least squares straight line fit y toa *the
 bdata
*
x points. Moreover, v   *
b 
is given by the formula 
v*  M T M  1 T
Mwhich
y express the fact that v = v* is the unique solution of the normal
equations
M T Mv  M T y
 LEAST SQUARE FITTING TO DATA
LEAST SQUARE FIT OF A POLYNOMIAL

Polynomial of fixed degree m, y  a0  a1 x    atom xnmpoints (x1, y1), (x2, y2), …, (xn, yn)

Substituting these n values of x and y into the above polynomial yields n equations,
y1  a0  a1 x1    am x1m
y2  a0  a1 x2    am x2m
v  M M
*
 T
 1
M Ty

    a * 
yn  a0  a1 xn    am xnm M T Mv  M T y v   *
b 
or in matrix form, y = Mv where
 y1  1 x1 x12  x1m   a1 
y    a 
 2  1 x2 x22  x2m 
y , M , v 2
       
     
y
 n 1 xn xn2  xnm   am 
 LEAST SQUARE FITTING TO DATA
The solution of the normal equations
M T Mv  M T y
determine the coefficients of the polynomial, and the vector v minimizes

y  Mv

If MTM is invertible, then the normal equations have a unique solution v = v*, which is given by


v*  M T M  1
M Ty
LEAST SQUARE FITTING TO DATA
EXAMPLE 3
LEAST SQUARE FITTING TO DATA
EXAMPLE 4
LEAST SQUARE FITTING TO DATA