Previous section

5.5. overdetermined system, least squares method

The linear system of equations

A =

where A is an m x n matrix with m > n, i.e., there are more equations than unknowns, usually does not have solutions. (A for all ). When this is the case, we want to find an such that the residual vector

= - A

is, in some sense, as small as possible.

The solution given be the least squares method minimizes ||||2 = || - A||2 , i.e., the square sum of errors:

(10)

||||22 = [ bi - aij xj ] 2 = f(x1 , ... , xn ).

The min-max solution minimizes ||||, i.e., the component of the residual vector.

max ( | r1 | , ..., | rn | ).

The minimun value for (10) is obtained when (x1 , ..., xn ) satisfies

f (x1 , ..., xn ) =

<=> (f / xj ) = 0  , j = 1, ..., n
<=> 2 [ bi - aij xj ] aij = 0,    j = 1, ..., n
<=> aij [ bi - aij xj ] = 0,    j = 1, ..., n
<=> AT ( - A) =

(11)

ATA = AT

<=>      = (ATA) - 1AT,

if (ATA) - 1 ( <=> the n columns of A linearly independent). The matrix = (ATA) - 1AT is called the pseudo inverse of A.

In practise, the least squares solution is obtained by solving the linear system (11) of n equations in n unknowns.

Example 1: Least squares method


Exercises: E59
Previous section
Contents
Next section