Least Squares Solution - Mathematics Department

Linear Algebra Grinshpan

Least Squares Solutions

Suppose that a linear system Ax = b is inconsistent. This is often the case when the number of equations exceeds the number of unknowns (an overdetermined linear system). If a tall matrix A and a vector b are randomly chosen, then Ax = b has no solution with probability 1.

In geometric terms, inconsistency means that b is not in the image of A. If so, it may still be reasonable to look for x such that y = Ax is as close to b as possible, i.e.,

Ax - b is a minimum.

In other words, we are interested in a vector x such that

Ax = proj im Ab.

Any such vector x is called a least squares solution to Ax = b, as it minimizes the sum of squares

Ax - b2 = ((Ax)k - bk)2.

k

For a consistent linear system, there is no difference between a least squares solution and a regular solution.

Consider the following derivation:

Ax = proj im Ab b - Ax im A

(b - Ax is normal to im A)

b - Ax is in ker A

A(b - Ax) = 0

AAx = Ab (normal equation).

Note that AA is a symmetric square matrix. If AA is invertible, and this is the case whenever A has trivial kernel, then the least squares solution is unique:

x = (AA)-1Ab.

Moreover,

Ax = A(AA)-1Ab,

so A(AA)-1A is the standard matrix of the orthogonal projection onto the image of A. If AA is not invertible, there are infinitely many least squares solutions. They all yield the same Ax.

Here are some supporting propositions and examples.

Proposition. Ax y = x Ay Proof. Exercise.

Proposition. (im A) = ker A Proof. Exercise.

Proposition. ker A = ker AA Proof. If Ax = 0, then AAx = 0. If AAx = 0, Ax2 = (Ax)Ax = xAAx = 0.

Proposition. im A = im AA Proof. im A = (ker A) = (ker AA) = ((im AA)) = im AA

Example. The linear system (11 11) (xx12) = (12) is inconsistent. The vector b = (12) is not on the line im A = span (11) . The associated normal equation is (22 22) (xx12) = (33) . The matrix AA = (22 22) is not invertible. The least squares solutions are x = (.15) + span (-11) . The orthogonal projection of b onto im A is Ax = (11..55) .

Example.

1 The linear system 1

1

1 1 0

(xx12)

=

0 1 1

is inconsistent.

0

1 1

The vector b = 1 is not in the plane im A = span 1 , 1 .

1

1 0

The associated normal equation is (32 22) (xx12) = (21) .

The matrix

AA = (32

22)

is invertible,

(AA)-1

=

1 2

(-22

-32) .

The least squares solution is unique, x = (-1.5) .

.5 The orthogonal projection of b onto im A is Ax = .5 .

1

.5 .5 0 The matrix of the orthogonal projection onto im A is A(AA)-1A = .5 .5 0 .

0 0 1

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

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

Google Online Preview   Download