# least square problem normal equations

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

-

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 http://www.cs.ubc.ca/~rbridson/courses/542g-fall-2008/notes-oct1.pdf 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.

-
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. cs.ubc.ca/~rbridson/courses/542g-fall-2008/notes-oct1.pdf 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.

-