Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can you give an example which shows that loss of information can occur in forming the normal equations. How is accuracy improved using iterative improvement?

Thank you

share|cite|improve this question
up vote 2 down vote accepted

Forming the normal equations doesn't lose any information. However solving them is more prone to numerical error because the condition number of $A^T A$ can be the square of the condition number of $A$.

If you look at Section 1.5 of there is a simple example that illustrates the problem. Choose $f=(1,-1)^T$ and try the problem in Matlab/Octave. Computing $A^{-1}f$ produces $(0,-1)^T$ which is good, but solving $(A^T A)^{-1}A^T f$ produces a warning and the result $(3.8320,2.8340)^T$.

The matrix in question is $A=\begin{bmatrix}1+10^{-8} & -1 \\ -1 & 1\end{bmatrix}$. $\kappa(A) \approx 4 \cdot 10^8$, $\kappa(A^TA) \approx 1.0648 \cdot 10^{17}$.

To answer the iterative accuracy improvement question, you need to indicate what iterative method you are using.

share|cite|improve this answer
In my experience one of the best ways to avoid the large condition number of $A^TA$ is to use the QR decomposition of $A$. – user7530 Jan 1 '13 at 22:28
Yes, I think QR would be a good approach in absence of other information. – copper.hat Jan 1 '13 at 22:33
Hey copper, the link is broken. If add "-2009" to the end it gets somewhere, but not sure where to find your example. – adam W Mar 8 '13 at 22:56
@adamW: Looks like I didn't copy the link correctly in the first place. Section 1.5 – copper.hat Mar 8 '13 at 23:58
OK, works now, thank you. – adam W Mar 9 '13 at 1:07

iirc, if you try to fit a polynomial of degree n at equally spaced points, you get a Hilbert matrix of size n, which rapidly becomes badly ill-conditioned as n increases.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.