7
$\begingroup$

It is well-known that Newton's method can converge quadratically, if initial guess is close enough and if the arising linear systems are solved accurately.

I am applying Newton's method to highly ill-conditioned systems (with condition number around $10^{14}$). I am sure that my Hessian is computed correctly, however I never obtain quadratic convergence.

I assume that the problem comes from the inability to solve linear systems with sufficient accuracy (I am using LU decomposition with iterative refinement).

Does anybody know about any reference, which discusses how speed of convergence of Newton's method depends on accuracy of the obtained correction?

$\endgroup$
  • $\begingroup$ Can you write down the system that you are optimizing? $\endgroup$ – nicoguaro Jan 28 at 16:54
  • $\begingroup$ I am minimizing total potential energy of nonlinear/non-convex orthotropic-elasticity model of shell discretized by subdivision finite elements $\endgroup$ – computational_scientist Jan 28 at 18:55
  • $\begingroup$ I would say that rather than an insufficient precision of the LSE solution your problem are the possible other local optima of your problem. Especially if you are using LU with iterative refinement. $\endgroup$ – Nox Jan 28 at 19:22
  • $\begingroup$ BTW, how did you compute your condition number? Sometimes you might get a number spat out of a condition number estimation that just means "reallll big!" 10^14 sounds like it's one of those numbers. $\endgroup$ – user14717 Jan 28 at 21:26
  • 1
    $\begingroup$ The asymptotic quadratic convergence of Newton's method also requires that the Jacobian be non-singular at the root. Since your matrix is very badly conditioned, this condition isn't being met. $\endgroup$ – Brian Borchers Jan 28 at 23:25
7
$\begingroup$

Yes: See Higham's book "Accuracy And Stability of Numerical Algorithms", second edition, chapter 25: Nonlinear Systems and Newton's Method.

In particular, see the section on the "limiting residual" in terms of a condition number for the Jacobian. It may well be that since your system is ill-conditioned, that you quickly hit the limiting residual and your iteration meanders aimlessly. I would try long double or quad precision, if that's available.

Note: Higham's treatment of this subject is very advanced. It may be advisable to first read Corless's "A Graduate Introduction to Numerical Methods", section 3.2.1, The Condition Number of A Root, which treats conditioning of the 1D rootfinding problem, along with a discussion of the 1D Newton's method.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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