Proofs: Chandrupatla's method

Correctness, termination and the acceptance test of Chandrupatla's method full

This proof shows: correctness, termination, convergence-rate.

Let $f$ be continuous on the interval $I$ between $x_0$ and $x_1$ with $f(x_0) f(x_1) \le 0$, let $w = |x_1 - x_0|$, and let $\delta \ge 0$. Write $t_l = (4u|x_m| + \delta/2)/|b - a|$ as in line L3 (in exact arithmetic take $u = 0$). Line numbers refer to the pseudocode on the main page.

Theorem 1 (invariant). At every test of line L3: $a$, $b$ lie in $I$, $f(a)$ and $f(b)$ are nonzero with opposite signs, and, after the first step, $c$ lies in $I$ outside the open interval between $a$ and $b$, on the side of $a$, with $f(c)$ nonzero and of the sign of $f(a)$. So a root lies strictly between $a$ and $b$, and a return at L3 with $f(x_m) \ne 0$ gives $|x_m - x^*| < |b - a| \le 2(4u|x_m| + \delta/2) = \delta + 8u|x_m|$.

Proof. L1 returns if $f$ vanishes at an end, so at the first test $f(a) f(b) < 0$. Suppose the claims hold and the pass does not return. Then $t_l < 1/2$ and L4 gives $t \in [t_l, 1 - t_l] \subset (0, 1)$, so $x = a + t(b - a)$ is strictly between $a$ and $b$, at distance at least $t_l |b - a|$ from each. If $f(x) = 0$, the next L3 returns $x$ (the implementation returns at once). Otherwise L6 and L7 replace the end of the same sign as $f(x)$ by $x$: if $f(x)$ has the sign of $f(a)$, the pair becomes $(x, b)$ and $c = $ old $a$; else the pair becomes $(x, \text{old } a)$ and $c = $ old $b$. In both cases $f$ has opposite signs at the new $a = x$ and new $b$, the discarded end $c$ has the sign of $f(x)$, and $c$ lies beyond $x$ as seen from the new $b$, because $x$ was between the old ends. The intermediate value theorem gives a root strictly between $a$ and $b$, and the error bound at the return is the stopping condition $t_l \ge 1/2$ rewritten. $\square$

Theorem 2 (termination). If $\delta > 0$, the loop returns after at most $\lceil 2w/\delta \rceil$ steps. For any $\delta \ge 0$ it stops after at most $K$ steps.

Proof. By the proof of Theorem 1 the new bracket is the part of the old one on one side of $x$, of length at most $(1 - t_l)|b - a| = |b - a| - 4u|x_m| - \delta/2 \le |b - a| - \delta/2$. Starting from width $w$, after $n$ steps without return the width is at most $w - n\delta/2$, and it is positive, so $n < 2w/\delta$. The cap $K$ bounds the loop in all cases. $\square$

Theorem 3 (the acceptance test). Let $a$, $b$, $c$ be distinct, with $c$ beyond $a$ as seen from $b$, and let $f_a$, $f_b$, $f_c$ be values with $f_a f_b < 0$, $f_c$ of the sign of $f_a$ and $f_c \ne f_a$. Put $\xi = (a - b)/(c - b)$ and $\Phi = (f_a - f_b)/(f_c - f_b)$. Let $P$ be the quadratic with $P(f_a) = a$, $P(f_b) = b$, $P(f_c) = c$. Then the test $\Phi^2 < \xi$ and $(1 - \Phi)^2 < 1 - \xi$ holds if and only if $\Phi < 1$ and $P'$ has no zero on the closed interval between $f_b$ and $f_c$. In that case $P$ is strictly monotone there and $P(0)$ lies strictly between $a$ and $b$.

Proof. By the position of $c$, $\xi \in (0, 1)$. Since $f_a - f_b$ and $f_c - f_b$ have the sign of $f_a$, $\Phi > 0$, and $\Phi \ne 1$ since $f_c \ne f_a$. If $\Phi > 1$, then $\Phi^2 > 1 > \xi$ and the test fails, so both sides of the equivalence are false. Take $\Phi \in (0, 1)$. Change variables to $v = (y - f_b)/(f_c - f_b)$ and $P = b + (c - b) W(v)$. Then $W$ is a quadratic with $W(0) = 0$, $W(1) = 1$ and $W(\Phi) = \xi$, so $W(v) = v + \kappa v(v - 1)$ with $\kappa = (\xi - \Phi)/(\Phi(\Phi - 1))$. The derivative $W'(v) = 1 + \kappa(2v - 1)$ is affine in $v$, so it has no zero on $[0, 1]$ if and only if $W'(0)$ and $W'(1)$ are nonzero with the same sign; their sum is 2, so the sign is positive. Since $\Phi(\Phi - 1) < 0$,

so $W'(0) > 0$ if and only if $\Phi^2 < \xi$, and $W'(1) > 0$ if and only if $(1 - \Phi)^2 < 1 - \xi$. This is the equivalence, as $P'$ is a nonzero multiple of $W'$. Under the test $W$ is strictly increasing on $[0, 1]$. The value $y = 0$ lies strictly between $f_b$ and $f_a$, that is $v_0 = -f_b/(f_c - f_b) \in (0, \Phi)$, and $W$ maps $(0, \Phi)$ onto $(0, \xi)$. So $P(0) = b + (c - b)W(v_0)$ lies strictly between $b$ and $b + (c - b)\xi = a$. $\square$

When $f_c = f_a$ the ratio $\Phi$ equals 1, the test fails, and L10 bisects, so the IQI formula, which divides by $f_c - f_a$, is never evaluated then.

The test is sufficient for monotonicity of $P$ between $f_b$ and $f_a$, which is all the step needs, but not necessary: in a random experiment with $a = 0$, $b = 1$, $c \in (-3, 0)$ and random values of the right signs, 5569 of 20000 cases passed the test and all of them gave a monotone $P$ on $[f_b, f_a]$, while 1372 more cases had $P$ monotone there but failed the test, because $P$ turned back between $f_a$ and $f_c$.

Remark (rate). In line L9, $a + t(b - a) = P(0)$, the inverse quadratic interpolation point; the L4 clamp changes it only when it lies within $t_l|b - a|$ of an end. So when the test accepts every step from some point on and the clamp is inactive, the iterates are those of inverse quadratic interpolation. For $f \in C^3$ near a simple root with $f'(x^*) \ne 0$, that iteration has order $q \approx 1.839$, the real root of $q^3 = q^2 + q + 1$ (Brent 1973, Chapter 3). This is a local statement. That the test eventually accepts every step is not proved here; it is observed on the smooth examples of the main page, where every step after the first was accepted.

In floating point the computed $\xi$, $\Phi$ and $t$ carry rounding errors, so Theorem 3 holds only up to rounding. Theorems 1 and 2 do not depend on it: whatever $t$ L9 computes, L4 clamps it into $[t_l, 1 - t_l]$, and the computed $x$ stays strictly inside since $t_l|b - a| \ge 4u|x_m|$ exceeds the rounding error of $a + t(b - a)$. If $t$ is NaN, min and max in Python return a clamp end, so the step is still inside.