Regula falsi

Remarks

Clause 1: the chord has values of opposite signs at $a_k$ and $b_k$, so its zero $c_k$ lies strictly between them. The update keeps a sign change, and the intermediate value theorem gives a zero in each bracket. Clause 2: by convexity the chord lies above the graph, so $f(c_k) < 0$ and $c_k$ always replaces the left endpoint. Then $c_{k+1} = g(c_k)$ with $g(x) = x - f(x)(b - x)/(f(b) - f(x))$. The increasing bounded sequence $(c_k)$ has a limit, which is a fixed point of $g$, hence $r$, and the error ratio tends to $g'(r)$. So under the hypotheses of clause 2 the method converges only linearly, see rate of convergence, and the bracket width $b - c_k$ does not tend to $0$. Example: for $f(x) = x^2 - 2$ on $[1, 2]$, $c_0 = 4/3$, $c_1 = 7/5$, $c_2 = 24/17 \approx 1.41176$, increasing to $\sqrt{2}$ with $b = 2$ fixed, and the limit ratio is $1 - 2\sqrt{2}(2 - \sqrt{2})/2 = 3 - 2\sqrt{2} \approx 0.17$. The other cases of fixed sign of $f''$ and of $f(a)$ follow by replacing $f(x)$ by $-f(x)$ or by $f(-x)$; then the other endpoint stays fixed.

Going deeper

For a student

Regula falsi is a bracketing root-finding algorithm like the bisection method, and it uses the same chord formula as the secant method. The secant method uses the two most recent points instead of the two bracketing ones; it loses the guarantee of a bracket but converges superlinearly near a simple zero. The fixed-endpoint problem of clause 2 led to modified versions such as the Illinois algorithm. It halves the stored function value at an endpoint that stays fixed twice in a row.