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?

Improve this question
$\endgroup$
8
  • $\begingroup$ Can you write down the system that you are optimizing? $\endgroup$
    – nicoguaro ♦
    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$
    – computational_scientist
    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
    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
    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$
    – Brian Borchers
    Jan 28, 2019 at 23:25

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Mohamed Abdelhamid
    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
    Jun 29, 2022 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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