Absolute error from root in false position method 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.
 A: 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.

*

*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|\}}.$$

*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}.$$
A: 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.

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:

*

*Try the usual false position twice.


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


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


*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.
A: 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$$
