4
$\begingroup$

I often used the Newton-Raphson method in material calculation, where I had to solve a small set of nonlinear equations (size=1..5). In most cases, it worked. However, convergence failure is often encountered in extreme cases, e.g., oscillation and divergence. The question is, given the set of equations and an initial starting point, is there a way to analyze the existence of the solution?

$\endgroup$
3
  • 3
    $\begingroup$ I believe what you want to ask is whether it's possible to know in advance if the method would converge, right? Or are you truly asking how to determine when a solution exists? $\endgroup$
    – Rigel
    Commented May 22 at 12:12
  • $\begingroup$ @Rigel good question. I would say the latter one, that if the solution exists. $\endgroup$
    – kstn
    Commented May 22 at 12:22
  • $\begingroup$ A good reference on Newton methods is the book "Newton Methods for Nonlinear Problems" by P. Deuflhard. $\endgroup$
    – Laurent90
    Commented May 28 at 15:35

3 Answers 3

7
$\begingroup$

The convergence of Newton’s method implies the existence of a root, but the function and the initial guess must satisfy some conditions to guarantee local convergence of Newton’s method. Local convergence of Newton's method (which implies the existence of a root) is guaranteed by the Kantorovich Theorem. The assumptions are a bit technical, but they are standard in the analysis of Newton's method. The form of the assumptions and precise statement of the theorem vary between sources and here I state something similar to that found in Kelley, 1995.

Assumption 1

There exist constants $\beta$, $\eta$, $\bar{r}$, and $\gamma$ with $\beta\eta\gamma \leq \frac{1}{2}$ and $x_0\in\mathbb{R}^n$ such that

  1. $F$ is differentiable at $x_0$, and $$ \|F'(x_0)^{-1}\| \leq \beta, \ \text{and } \|F'(x_0)^{-1}F(x_0)\|\leq \eta. $$
  2. $F'$ is Lipschitz continuous with Lipschitz constant $\gamma$ in a ball of radius $\bar{r} \geq r_-$ about $x_0$ where $$ r_- = \frac{1 - \sqrt{1 - 2\beta\eta\gamma}}{\beta\gamma}. $$

In English, these assumptions state, roughly:

  1. The root of the linear approximation to $F$ ant $x_0$ is unique and the root of the linear approximation at $x_0$ is not too far away from $x_0$.

  2. The higher derivatives of $F$ are sufficiently well-behaved in a neighborhood about $x_0$ so that the first point remains true when we do the same procedure at the root of the linear approximation.

Indeed, it is remarkable that the existence of a root and precise error estimates of Newton’s method and various modifications can be guaranteed by simple estimates on $F$ and its first few derivatives.

The statement of the theorem is then

Theorem (Kantorovich)

Let Assumption 1 hold and let $\beta\eta\gamma \leq \frac{1}{2}$ and define $\mathcal{B}_0 = \{x\in\mathbb{R}^n:\|x-x_0\|\leq r_-\}$. Then there is a unique root $x^*$ of $F$ in $\mathcal{B}_0$, the Newton iteration with $x_0$ as the initial iterate converges to $x^*$, and the iterates $x_k \in \mathcal{B}_0$ for all $k$. Furthermore, $x^*$ is the unique root of $F$ in the ball of radius $$ r = \min\left\{\bar{r}, \frac{1+\sqrt{1 - 2\beta\eta\gamma}}{\beta\gamma}\right\} $$ about $x_0$ and the errors $e_k$ satisfy the estimate $$ \|e_k\| \leq \frac{(2\beta\eta\gamma)^{2^k}}{2^k \beta\gamma}. $$ That is, Newton's method converges quadratically.

In practice, you can rarely guarantee a priori that these assumptions are met, but they work to provide a quantitative measure of what "local" means for the local convergence of Newton's method and how this locality is influenced by, e.g., near-singularity of $F'$ or large second derivatives. The most practical ways of maximizing your chances of converging are to reduce the conditioning of your problem via rescaling or something or to simply have better initial guesses. Obviously "just guess closer to the correct answer" is somewhat circular advice, but if the system of equations correspond to a problem for which there is some existing domain knowledge then this can be leveraged for better initialization. For example, initializing at parameter values from literature or values predicted by reduced models or models with missing physics can be surprisingly effective. There are some fields where this is frowned upon (CFD comes to mind) for biasing results, but it is effective if you are having problems even converging in the first place.

Kelley, C. T., Iterative methods for linear and nonlinear equations, Frontiers in Applied Mathematics. 16. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. xiii, 165 p. (1995). ZBL0832.65046.

$\endgroup$
3
$\begingroup$

In addition to the damped Newton or trust region method, for small problem sizes you might find Smale's alpha theory or the general subject of numerical certification worth looking into. What Smale did was show that, in some circumstances, it's possible to tell if you're in the quadratic convergence basin for Newton's method at a particular point based on the magnitudes of the function and its higher derivatives. This gives a sufficient but not necessary condition, so it can work but it's not a full equivalence.

$\endgroup$
2
$\begingroup$

You probably want to give the damped Newton method a try: instead of taking full steps ($x_{k+1} = x_k + d_k$, where $d_k$ is the Newton step), find $\alpha \in (0, 1]$ such that $x_k + \alpha d_k$ sufficiently reduces the norm of the equations. See here on slide 11: https://www.stat.cmu.edu/~ryantibs/convexopt-S15/lectures/14-newton.pdf

$\endgroup$

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.