normal equations

We consider the problem Axb , where A is an m×n matrix with mn rank (A)=n, b is an m×1 vector, and x is the n×1 vector to be determined.

The sign stands for the least squares approximation, i.e. a minimization of the norm of the residual r=Ax-b.

||Ax-b||2=||r||2=[i=1mri2]1/2

or the square

F(x) = 12||Ax-b||22=12(Ax-b)T(Ax-b)
= 12(xTATAx-2xTATb+bTb)

i.e. a differentiable function of x. The necessary condition for a minimum is:

F(x)=0orFxi=0(i=1,,n)

These equations are called the normal equations , which become in our case:

ATAx=ATb

The solution x=(ATA)-1ATb is usually computed with the following algorithm: First (the lower triangular portion of) the symmetric matrixMathworldPlanetmath ATA is computed, then its Cholesky decompositionMathworldPlanetmath LLT. Thereafter one solves Ly=ATb for y and finally x is computed from LTx=y.

Unfortunately ATA is often ill-conditioned and strongly influenced by roundoff errors (see [Golub89]). Other methods which do not compute ATA and solve Axb directly are QR decompositionMathworldPlanetmath and singular value decompositionMathworldPlanetmath.

References

  • Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)

Title normal equations
Canonical name NormalEquations
Date of creation 2013-03-22 12:04:28
Last modified on 2013-03-22 12:04:28
Owner akrowne (2)
Last modified by akrowne (2)
Numerical id 7
Author akrowne (2)
Entry type Definition
Classification msc 65-00
Classification msc 15-00