LEAST SQUARES and NORMAL EQUATIONS Background - Washington State University

LEAST SQUARES and NORMAL EQUATIONS

Background

? Overdetermined Linear systems: consider Ax = b if A is m ? n, x is n ? 1, b is m ? 1 with m > n. The linear system is inconsistent if no x satisfies all equations. Note: too many equations, not enough unknowns. Examples: a) An overdetermined 4x2 system x1 + 2x2 = 1 2x1 + 2x2 = 2 x1 - x2 = -1 2x1 + x2 = 2

b)

Fitting line to data

? The least squares solution: the x that minimizes

||r||2 = ||Ax - b||2 =

mn

1/2

aijxj - bi 2

i=1 j=1

2

LS and NORMAL EQUATIONS ? Geometric least squares solution x?: Ax? - b should be orthogonal to all Ax.

? Algebraic least squares solution: consider ||Ax - b||22 = ||A(x? + e) - b||22.

3

LEAST SQUARES, NORMAL EQUATIONS

The Normal Equations ? The normal equations are AT Ax = AT b. ? If rank(A) = n the normal equations have a unique solution x?. ? Example

? SE and RM SE: with r = Ax? - b

squared error

SE = ||r||22 = r12 + r22 + ? ? ? + rm2 ;

root mean squared error RM SE =

m i=1

ri2/m

=

SE/m.

4

LEAST SQUARES CONTINUED Data Fitting and Linear Models

? Fitting data to straight line: given data {(ti, yi)}mi=1, find the line y(t) = a + bt "closest" to the data points.

"Least Squares" line minimizes sum of squared errors.

5

LEAST SQUARES CONTINUED

Example: t = [6.8 7 7.1 7.2 7.4], y = [.8 1.2 .9 .9 1.5]

Straight Line Data Fit 1.5

1.4

1.3

1.2

1.1

1

0.9

0.8

0.7

6.5

6.6

6.7

6.8

6.9

7

7.1

7.2

7.3

7.4

7.5

Matlab

t = [6.8 7 7.1 7.2 7.4]'; y = [.8 1.2 .9 .9 1.5]';

A = [ones(5,1) t]; p = (A'*A)\(A'*y);

tp = [6.8:.01:7.4]; plot(tp,p(1)+p(2)*tp,t,y,'*')

disp(norm(A*p-y)/sqrt(5))

0.18439

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download