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.


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:


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


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.


  • Originally from The Data Analysis Briefbook (

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