2.6 Least squares solution of equations

Back

Suppose AX = B represents a system of linear equations with real coe±-

cients which may be inconsistent, because of the possibility of experimental

errors in determining A or B. For example, the system

x = 1

y = 2

x + y = 3:001

is inconsistent.

It can be proved that the associated system AtAX = AtB is always

consistent and that any solution of this system minimizes the sum r2

1 +: : :+

r2

m , where r1; : : : ; rm (the residuals) are de¯ned by

ri = ai1x1 + : : : + ainxn ¡ bi;

for i = 1; : : : ;m. The equations represented by AtAX = AtB are called the

normal equations corresponding to the system AX = B and any solution

of the system of normal equations is called a least squares solution of the

original system.

EXAMPLE 2.6.1 Find a least squares solution of the above inconsistent

system.

Solution. Here A =

2

4

1 0

0 1

1 1

3

5 ; X =

·

x

y

¸

; B =

2

4

1

2

3:001

3

5.

Then AtA =

·

1 0 1

0 1 1

¸ 2

4

1 0

0 1

1 1

3

5 =

·

2 1

1 2

¸

.

Also AtB =

·

1 0 1

0 1 1

¸ 2

4

1

2

3:001

3

5 =

·

4:001

5:001

¸

.

So the normal equations are

2x + y = 4:001

x + 2y = 5:001

which have the unique solution

x =

3:001

3

; y =

6:001

3

:

48 CHAPTER 2. MATRICES

EXAMPLE 2.6.2 Points (x1; y1); : : : ; (xn; yn) are experimentally deter-

mined and should lie on a line y = mx + c. Find a least squares solution to

the problem.

Solution. The points have to satisfy

mx1 + c = y1

...

mxn + c = yn;

or Ax = B, where

A =

2

64

x1 1

...

...

xn 1

3

75

; X =

·

m

c

¸

; B =

2

64

y1

...

yn

3

75

:

The normal equations are given by (AtA)X = AtB. Here

AtA =

·

x1 : : : xn

1 : : : 1

¸

2

64

x1 1

...

...

xn 1

3

75

=

·

x2

1 + : : : + x2

n x1 + : : : + xn

x1 + : : : + xn n

¸

Also

AtB =

·

x1 : : : xn

1 : : : 1

¸

2

64

y1

...

yn

3

75

=

·

x1y1 + : : : + xnyn

y1 + : : : + yn

¸

:

It is not di±cult to prove that

¢ = det (AtA) =

X

1·i<j·n

(xi ¡ xj)2;

which is positive unless x1 = : : : = xn. Hence if not all of x1; : : : ; xn are

equal, AtA is non{singular and the normal equations have a unique solution.

This can be shown to be

m =

1

¢

X

1·i<j·n

(xi ¡ xj)(yi ¡ yj); c =

1

¢

X

1·i<j·n

(xiyj ¡ xjyi)(xi ¡ xj):

REMARK 2.6.1 The matrix AtA is symmetric.

2.7. PROBLEMS 49

Навигация