1
$\begingroup$

Suppose I know that $f(x_1)$ and $f(x_2)$ have opposite signs, so $f(x)=0$ has a root $x\in[x_1,x_2]$. Then using the false position method, I have a guess for the root $$x_3=\frac{f(x_2)x_1-f(x_1)x_2}{f(x_2)-f(x_1)},$$ and I can iterate on either $[x_1,x_3]$ or $[x_3,x_2]$ depending on the sign of $f(x_3)$.

Usually we terminate the process when $|f(x_n)|<\epsilon$ for some specified $\epsilon$.

How can I pick $\epsilon$ so that I am certain that my guess for the root $x_n$ is within $\delta$ of the true value of the root, i.e. $|x_n-x|<\delta$?

I am not sure how to pick such an $\epsilon$ when we don't even know the true value $x$ of the root. When $\delta$ is sufficiently small, something like $\epsilon=\delta f'(x)$ could work, but obviously this requires that you (a) know the true value of the root and (b) know the derivative of the function, two assumptions that are definitely not true in general.

$\endgroup$
2
$\begingroup$

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ and let us consider the problem of terminating an iterative method that is being used to solve the non-linear equation $$ f(x) = 0$$ It is vital we consider the underlying application and what is actually needed in order to satisfy the user.

  1. Suppose that the objective is to compute the square root of $\alpha>0$, then $f(x) = x^2- \alpha$ is a natural choice and a very natural objective is to compute $x$ such that $|x - \sqrt{\alpha}|<\delta$ where $\delta>0$ is chosen by the user. A bracketing method such as the bisection method or the false position method systematically shrinks a bracket which is certain to contain at least one root. Specifically, if $f(a)f(b)<0$ and $f$ is continuous in the interval $[a,b]$, then $f$ has a root $r \in (a,b)$. In the absence of any additional information our best estimate of $r$ is the midpoint, i.e., $$\mu = \frac{a+b}{2}$$ and the error is bounded by $$|r-\mu| < \frac{1}{2}|b-a|.$$ We should therefore terminate the iteration when $$|a-b| \leq 2 \delta.$$ It is entirely possible that the user is more interested in a small relative error. In this case we must of eliminate the possibility that $r=0$ is a root, but this is easy. If $ab>0$, then $r=0$ is not possible and the relative error can be bounded by $$\frac{|r-\mu|}{|r|} < \frac{\frac{1}{2}|a-b|}{\min\{|a|,|b|\}}.$$
  2. Suppose the objective is to compute the elevation $\theta$ needed to hit a target with a howitzer. Then $$f(\theta) = r(\theta) - d$$ is the natural choice. Here $r(\theta)$ is the range of the howitzer when fired with elevation $\theta$ and $d$ is the distance to the target. Let $$\theta_1, \theta_2, \dotsc, \theta_j $$ denote the approximations of $\theta$ produced by our solver. When should we terminate the iteration. For this application, tiny errors $\theta-\theta_j$ are utterly irrelevant. The crew manning the howitzer cannot make minute adjustments to the elevation anyway, because howitzers are heavy objects. The only thing that matters is the residual, i.e., the value $y = f(\theta_j)$. In this situation, it is proper to terminate the iteration when $$|f(\theta_j)| < \rho,$$ where $\rho$ is kill radius of the exploding shell.

In general, it is not viable to terminate the iteration when it appears to be stagnating, i.e., when $$|x_j - x_{j+1}| < \delta.$$ What is required to defeat this criteria in the context of the false position method? We need a continuous function $f$ and two points $a$ and $b$ such that $f(a)$ is large and negative and $f(b)$ is tiny and positive. The false position method will return an approximation $c$ which is very close to $b$. This is a major problem if there is only a single root $r \in (a,b)$ and $r$ is close to $a$. If we are using, say, Newton's method, then this criteria can be defeated by functions satisfying $$f(x) \approx e^{-\lambda x}, \quad f'(x) \approx -\lambda f(x)$$ where $\lambda>0$ because $$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \approx x_n + \frac{1}{\lambda} \rightarrow \infty, \quad n \rightarrow \infty, \quad n \in \mathbb{N}.$$

$\endgroup$
2
  • $\begingroup$ This is excellently clear. I think your $\tau$ should be $\delta$ though. $\endgroup$ – Verge Jan 20 at 14:47
  • $\begingroup$ @Verge. Thank you for your kind words. You are right about $\tau$. I have changed it to $\delta$. $\endgroup$ – Carl Christian Jan 20 at 15:13
1
$\begingroup$

A more robust criteria for termination which does not have the issues you point out would be to use an estimate of the derivative, since we expect to have

$$f(x_n)\approx f'(x)(x_n-x),\quad|x_n-x|\approx\left|\frac{f(x_n)}{f'(x)}\right|,\quad f'(x)\approx\frac{f(a)-f(b)}{a-b}\tag{1, 2, 3}$$

where $a<x<b$. As you may notice, this simply ends up becoming the estimate

$$|x_n-x|\approx|x_n-x_{n+1}|\tag4$$

as Claude Leibovici mentions.

Another strategy would be to instead use a better estimate of the slope. Instead of using the endpoints of your interval, of which one side is very inaccurate, you could instead use the last two computed points, replacing $f'(x)$ with

$$f'(x)\approx\frac{f(x_{n+1})-f(x_n)}{x_{n+1}-x_n}\tag5$$

which, in the case of twice differentiable functions with non-vanishing second derivative at the root, can be shown to lead to an overestimate of the absolute error (which is desirable).

Below a graphical demonstration of this is shown. As can be seen, every iteration of false position gives a point on the right of the root. Likewise, if you estimate the slope using the last two computed points, you get an estimate of the root on the left side. The difference between the last computed point and this one is an upper bound on the absolute error.

enter image description here

Hence one can conclude that in most instances one should eventually have

$$|x_{n+1}-x|\stackrel<\simeq\left|\frac{f(x_{n+1})}{f(x_{n+1})-f(x_n)}(x_{n+1}-x_n)\right|\tag6$$

This approach is not flawless however, as it can easily lead to premature termination. Early on one may have the last two computed points be nearly vertical, or even pointing in the wrong direction. A much safer strategy would then be to use an anti-stalling method, such as the Illinois method, or along the lines of what was presented so far in this answer:

  1. Try the usual false position twice.

  2. Try using $(5)$ to compute the next estimate of the root instead of the usual false position.

  3. Use bisection if the previous step gives an estimate outside of your current bounds or if the length of the bracketing fails to halve.

  4. Repeat steps 1, 2, and 3 until your bracketing interval is sufficiently small.

In this way you can be certain that your bracketing interval shrinks and that the estimated absolute error is always an over-estimate of the real absolute error.

$\endgroup$
2
  • $\begingroup$ This is similar to an idea that I had -- I think once you get sufficiently close to the root, then (for simple roots that aren't inflection points) the function is either locally convex or concave, increasing or decreasing. We can use this to get a good $\epsilon$, e.g. if $f$ is convex and increasing in an interval $[a,b]$ around the root, then I think taking $\epsilon=|f(a+\delta)-f(a)|$ works? $\endgroup$ – Verge Jan 20 at 16:46
  • $\begingroup$ Using the estimations $(1)$ and $(5)$ gives $$|f(x)|\approx\left|\frac{f(x_{n+1})-f(x_n)}{x_{n+1}-x_n}\right|\delta$$ as the desired criteria for termination, but I would not really suggest this. It's usually better to follow a procedure such as what I mention at the end of my answer and measure $|a-b|$ directly instead. $\endgroup$ – Simply Beautiful Art Jan 20 at 21:08
0
$\begingroup$

You wrote :

Usually we terminate the process when $|f(x_n)|<\epsilon$ for some specified $\epsilon$.

This is not a convergence test. If it was, multiply any function by $10^{-999}$ and any point would be a solution according tho this test.

What you must use to end the process (and you almost wrote it) is $$|x_{n+1}-x_n| \leq \epsilon$$

$\endgroup$
4
  • $\begingroup$ Thanks -- your comment makes a lot of sense, not sure why my source defines the termination criterion as $|f(x_n)|$ being small enough. I guess my question still stands -- how do we pick $\epsilon$ to guarantee that we are within $\delta$ from the true value? $\endgroup$ – Verge Jan 20 at 9:06
  • $\begingroup$ @Verge. You cannot conceive how many times I saw this mistake, including in textbooks. $\endgroup$ – Claude Leibovici Jan 20 at 9:19
  • $\begingroup$ @Verge. There are applications where it is perfectly correct to terminate when the absolute value of residual is small. Stagnation does not imply that we are close to a root. I have added an answer that illustrates these matters. $\endgroup$ – Carl Christian Jan 20 at 14:05
  • $\begingroup$ @CarlChristian. Thanks for having addressed the problem of stagnation. Cheers :-) and (+1). $\endgroup$ – Claude Leibovici Jan 20 at 14:09

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.