2
$\begingroup$

Is it a good criterion to stop iterative methods for solving non-linear equations, such as Newton-Raphson and good Broyden's methods, when $|x_k-x_{k-1}|<|x_k|\,reltol + abstol$ OR when $|f_k|<tolfun$, or should it be when $|x_k-x_{k-1}|<|x_k|\,reltol + abstol$ AND when $|f_k|<tolfun$?

Until now, I was using the first criterion, but recently I had a problem using the Broyden's method in a continuation algorithm: when trying to obtain the next point of the curve, $\{x_k\}$ converged to a value $x^*$ although the residual was already too big. Is this because the stopping criterion I was using was not good enough, or is it just because there might be a bifurcation at that point?

| cite | improve this question | |
$\endgroup$
  • 2
    $\begingroup$ It can happen in principle that the condition on $f$ will never be satisfied, if, for example, $|f'(x_*)|u > \mathit{tolfun}$ ($u$—unit roundoff). $\endgroup$ – Kirill Apr 10 '17 at 22:49
  • $\begingroup$ Thank you for your answer, @Kirill. I'm looking now for a practical example of this. Trying $f=K*(ln(x)-y_0)$ with $K=1e8$, a random $y0$ and $tolfun=1e-100$, Newton-Raphson succeeds. Could you please suggest me another function to try? $\endgroup$ – Manu Apr 11 '17 at 9:37
  • 2
    $\begingroup$ I just tried your example with $K=10^8, y_0=0.1$, and the root $x_0 = 1.1051709180756475$ (in double precision) has the property that $f(x_0)\approx -1.25\times 10^{-8}$, but $f(x_0+\epsilon)\approx 6.94\times 10^{-9}$, where $x_0+\epsilon$ is the next double-precision floating-point number immediately after $x_0$. So there are no such numbers for which $|f|<10^{-9}$. I think it's also possible to come up with easy polynomial examples by, e.g., taking characteristic polynomials of random integer matrices. $\endgroup$ – Kirill Apr 11 '17 at 19:48
  • $\begingroup$ Thank you @Kirill, I have tried your example and Newton does not converge now if we impose $|f|<10^{-9}$. I think I am getting it. If the slope of $f(x)$ is too high at the root, it can be imposible to reach the desired tolerance since we cannot move along $x$ in a continuous way, but in jumps of value $\epsilon$, so that, when passing the root, $|f(x)|$ jumps from one value higher than $tolfun$ to another one higher that $tolfun$ as well. $\endgroup$ – Manu Apr 12 '17 at 9:12
5
$\begingroup$

It can happen in principle that the condition on $f$ will never be satisfied, if, for example, $|f'(x_*)|u>\mathit{tolfun}$, where $u$ is the unit roundoff.

When I tried your example with $K=10^8,y_0=0.1$, and the root $x_0=1.1051709180756475$ (in double precision) has the property that $f(x_0)≈−1.25×10^{−8}$, but $f(x_0+\epsilon)≈6.94×10^{−9}$, where $x_0+\epsilon$ is the next double-precision floating-point number immediately after $x_0$. So there are no such numbers for which $|f|<10^{-9}$. I think it's also possible to come up with easy polynomial examples by, e.g., taking characteristic polynomials of random integer matrices.

In general, the relationship between the residual of the equation $f(x)=0$ and the error $x-x_*$ depends on the function itself. You know that asymptotically both $f(x)$ and $x-x_*$ will converge to zero, but to derive a bound of the true error $x-x_*$ from the residual $f(x)$ requires making assumptions on $f$. If you know the value of $|f'(x_*)|$, then you know that $|x-x_*|\approx |f(x)|/|f'(x_*)|$. In the multivariate case, the inequality instead says that $$\|f(x)\|\|J\|^{-1} \lesssim \|x-x_*\| \lesssim \|f(x)\|\|J^{-1}\|,$$ so you need at least to know the condition of the Jacobian to convert the residual to an error estimate (see Higham's Accuracy and Stability of Numerical Algorithms, 25.5).

All of the above is before you start analyzing the numerical stability of evaluating $f$ near a root. You gave an example of essentially a linear function, but for a typical more complicated function, you wouldn't be able to evaluate $f$ accurately to full machine precision near a root at all, which will also limit how small $f$ can possibly get.

| cite | improve this answer | |
$\endgroup$

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.