Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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 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.

share|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. 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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.