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)

*
||||*^{2}_{2 } = [ *b*_{i } - a_{ij }x_{j } ] ^{2} = f(x_{1 }, ...
, x_{n }).
The **min-max solution**
minimizes *||||*_{}, i.e.,
the component of the residual vector.

*
*max * ( * | *r*_{1 } | *, ..., * | *r*_{n } | *).
*
The minimun value for (10)
is obtained when * (x*_{1 }, ..., x_{n })
satisfies

*
f (x*_{1 }, ..., x_{n }) =

<=> | (*f / x*_{j })* = 0 , j = 1, ..., n* |

<=> | * 2* [ *b*_{i } - a_{ij }x_{j } ] *a*_{ij } = 0, j = 1,
..., n |

<=> | *a*_{ij } [ *b*_{i } - a_{ij }x_{j } ] * = 0, j = 1,
..., n* |

<=> | *A*^{T} ( - A) = |

(11)

*
A*^{T}A = A^{T}

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

Exercises: E59

Previous section

Contents

Next section