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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 65-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)