Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online course: Linear Algebra - Linear Systems of Equations - Approximation Problems

Normal Equation

[previous page] [next page] [table of contents][page overview]

For an $ m \times n$ matrix $ A$ , any solution $ x$ of the least squares problem $ \Vert Ax-b\Vert _2$ satisfies the normal equations

$\displaystyle A^{\operatorname t}Ax = A^{\operatorname t}b. $

\includegraphics[width=.4\moimagesize]{a_normalengleichungen}

Geometrically, this means that the residuum $ Ax-b$ is orthogonal to the columns of $ A$ , i.e. to the subspace $ \operatorname{im} A$ of $ \mathbb{R}^m$ . The solution is unique if rank $ A = n \leq m$ .

From

$\displaystyle \Vert A(x+ty)-b\Vert _2^2 \ge \Vert Ax-b\Vert _2^2 $

and

$\displaystyle (Ax-b)^{\operatorname t}y = y^{\operatorname t}(Ax-b),\quad \Delta = Ax-b $

it follows that

$\displaystyle 2ty^{\operatorname t}A^{\operatorname t}\Delta + t^2y^{\operatorname t}A^{\operatorname t}Ay\ge 0\, $

for all $ t\in\mathbb{R}$ and $ y\in\mathbb{R}^n$ . If we interpret the left-hand side of the inequality as a parabola with respect to $ t$ , then it follows from the non-negativity that

$\displaystyle y^{\operatorname t}(A^{\operatorname t}\Delta)=0\, . $

This holds for all vectors $ y$ only if the expression in parentheses is the zero vector.

For the example

$\displaystyle A = \left(\begin{array}{cc} 2 & 0 \\ 1 & 1 \\ 0 & 2 \end{array}\right), \quad b = \left(\begin{array}{c} 0 \\ 3 \\ 0 \end{array}\right) $

the normal equations

$\displaystyle \left(\begin{array}{cc} 5 & 1 \\ 1 & 5 \end{array}\right) \lef... ..._2 \end{array}\right) = \left(\begin{array}{c} 3 \\ 3 \end{array}\right) $

have the unique solution $ x = \left(\begin{array}{cc} \frac{1}{2} & \frac{1}{2} \end{array}\right)^{\operatorname t} $ . The error is $ \Delta = (\begin{array}{ccc} 1 & -2 & 1 \end{array})^{\operatorname t}$ .

If $ A$ has linearly dependent columns, as in the example

$\displaystyle A = \left(\begin{array}{cc} 2 & 2 \\ 1 & 1 \\ 0 & 0 \end{array... ...t), \quad b = \left(\begin{array}{c} 0 \\ 3 \\ 0 \end{array}\right)\, , $

then the normal equations are singular:

$\displaystyle \left(\begin{array}{cc} 5 & 5 \\ 5 & 5 \end{array}\right) \lef... ...end{array}\right) = \left(\begin{array}{c} 3 \\ 3 \end{array}\right)\, . $

In this case the solution

$\displaystyle x = \left(\begin{array}{c} \dfrac{3}{10}+t \\ [+2ex] \dfrac{3}{10}-t \end{array}\right),\quad t\in\mathbb{R}\, , $

is not unique, whereas the error $ \Delta = (\begin{array}{ccc} \frac{6}{5} & -\frac{12}{5} & 0 \end{array})^{\operatorname t}$ is.
  automatically generated 4/21/2005