PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
normal equations (Definition)

Normal Equations

We consider the problem $ Ax \approx b$ , where $ A$ is an $ m \times n$ matrix with $ m \ge n$ rank $ (A)=n$, $ b$ is an $ m \times 1$ vector, and $ x$ is the $ n \times 1$ vector to be determined.

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

$\displaystyle \vert\vert Ax-b\vert\vert _2 = \vert\vert r\vert\vert _2 = \left[ \sum_{i=1}^m r_i^2 \right]^{1/2}$

or the square


$\displaystyle F(x)$ $\displaystyle =$ $\displaystyle \frac{1}{2} \vert\vert Ax-b\vert\vert _2^2 = \frac{1}{2}(Ax-b)^T (Ax-b)$  
  $\displaystyle =$ $\displaystyle \frac{1}{2}(x^TA^TAx -2x^TA^Tb + b^Tb)$  

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

$\displaystyle \nabla F(x) =0$   or$\displaystyle \frac{\partial F}{\partial x_i} = 0 (i=1,\ldots,n) $

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

$\displaystyle A^TAx = A^T b $

The solution $ x=(A^TA)^{-1}A^Tb$ is usually computed with the following algorithm: First (the lower triangular portion of) the symmetric matrix $ A^TA$ is computed, then its Cholesky decomposition $ LL^T$. Thereafter one solves $ Ly=A^Tb$ for $ y$ and finally $ x$ is computed from $ L^Tx=y$.

Unfortunately $ A^TA$ is often ill-conditioned and strongly influenced by roundoff errors (see [Golub89]). Other methods which do not compute $ A^TA$ and solve $ Ax \approx b$ directly are QR decomposition and singular value decomposition.

References



"normal equations" is owned by akrowne.
(view preamble)

View style:

Log in to rate this entry.
(view current ratings)

Cross-references: singular value decomposition, QR decomposition, ill-conditioned, Cholesky decomposition, symmetric matrix, lower triangular, algorithm, solution, equations, necessary, differentiable function, square, residual, norm, approximation, least squares, vector, rank, matrix
There are 4 references to this entry.

This is version 3 of normal equations, born on 2001-12-25, modified 2002-11-13.
Object id is 1144, canonical name is NormalEquations.
Accessed 8651 times total.

Classification:
AMS MSC65-00 (Numerical analysis :: General reference works )
 15-00 (Linear and multilinear algebra; matrix theory :: General reference works )

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)