5.5. overdetermined system, least squares method

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 ||||₂ = || - A||₂ , i.e., the square sum of errors:

(10)

||||²₂ = [ b_i - a_ij x_j ] ² = f(x₁ , ... , x_n ).

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

The minimun value for (10) is obtained when (x₁ , ..., x_n ) satisfies

f (x₁ , ..., x_n ) =

<=>	(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)

A^TA = A^T

<=>      = (A^TA) ^{- 1}A^T,

if (A^TA) ^{- 1} ( <=> the n columns of A linearly independent). The matrix = (A^TA) ^{- 1}A^T 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