I am doing some image processing involving solving a system of linear equations. I am getting some errors and bits of the image looks corrupted. I would like to know what is the most stable way to solve these systems (I don't care how much cpu it takes to compute). It should try to avoid roundoff, catastrophic cancellation, etc.

What would be the most robust algorithm for this?

  • $\begingroup$ Rather than trying to invert $A$ you can try to invert $A + \lambda I$ for some small value of $\lambda$. The the idea is to pad the diagonal enough so that $A$ is much more well-conditioned. There are various algorithms to determine optimal values of $\lambda$, but in practice adding a small $0.001-0.01$ amount should work fine. $\endgroup$ Aug 7, 2015 at 22:02
  • $\begingroup$ I am not inverting it at all. I was using guassian elimination. But its ok anyways, I found out how to fix my problem using the more stable quadratic formula here it.uom.gr/teaching/linearalgebra/NumericalRecipiesInC/c5-6.pdf $\endgroup$
    – omega
    Aug 8, 2015 at 5:11
  • 1
    $\begingroup$ Use a library rather than writing the code yourself. $\endgroup$ Aug 8, 2015 at 7:53
  • $\begingroup$ @omega Have you tried the LU factorization approach? You can increase the stability of the procedure with pivoting and more so if you use what's called "complete pivoting". If you're interested I can outline the procedure as an answer. I think it is what you're looking for. $\endgroup$ Aug 15, 2015 at 13:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.