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?

  • $\begingroup$ Can you write down the system that you are optimizing? $\endgroup$
    – nicoguaro
    Commented Jan 28, 2019 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$ Commented Jan 28, 2019 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
    Commented Jan 28, 2019 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
    Commented Jan 28, 2019 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$ Commented Jan 28, 2019 at 23:25

1 Answer 1


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.

  • $\begingroup$ Is it possible to attach this problem from a different perspective like scaling variables to reduce the conditioning number of the resulting Hessian? $\endgroup$ Commented Jun 29, 2022 at 18:26
  • $\begingroup$ @MohamedAbdelhamid: Interesting question. I'm not sure that variable scaling is sufficiently powerful to get you there, but application of (say) the Buckingham-π theorem to non-dimensionalize is a good idea anyway. $\endgroup$
    – user14717
    Commented Jun 29, 2022 at 22:33

Your Answer

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

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