Bisection vs Secant: Counting Steps to a Root
Take $f(x) = x^3 - 2x - 5$, which has a single real root $r \approx 2.0945514815$, and the bracket $[2, 3]$, where $f(2) = -1$ and $f(3) = 16$. You want the root without using $f'$.
(a) Bisection halves the bracket each step. How many bisection steps are needed before the bracket width is at most $10^{-6}$?
(b) Run the secant method from $x_0 = 2$, $x_1 = 3$. What is the first new iterate $x_2$?
(c) Keep iterating the secant method. Counting each new iterate $x_2, x_3, \dots$ as one step, after how many steps is $|x_k - r| < 10^{-6}$ for the first time?
(d) False position (regula falsi) also takes the zero of the chord through the two bracket endpoints, but then replaces whichever endpoint keeps the sign change. What happens when you run it on $[2, 3]$, and how fast does it converge?
Hints
- After $n$ halvings the bracket has width $(3 - 2)/2^n$. Which power of $2$ is the first to exceed $10^6$?
- The secant update is $x_{k+1} = x_k - f(x_k)\,\dfrac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}$. With $f(2) = -1$ and $f(3) = 16$ the first step is a one-line fraction; after that, track $|x_k - r|$ and watch the number of correct digits grow by a factor of about $1.6$ per step.
- For false position, look at the sign of $f''$ on $[2, 3]$. When $f$ is increasing and convex, where does every chord cross the axis relative to the root?
Worked Solution
How to Think About It: All three methods only evaluate $f$, so compare them by how fast the error shrinks per evaluation. Bisection is pure bookkeeping: the width halves each step. The secant method replaces $f'$ in Newton's step by the slope of the chord through the last two iterates, which gives superlinear convergence once you are close. False position uses the same chord but keeps a bracket, and the bracket rule can freeze one endpoint.
Quick Estimate: $2^{10} \approx 10^3$, so $2^{20} \approx 10^6$: about $20$ bisection steps. The secant error starts near $10^{-1}$ and its exponent grows by a factor of about $1.6$ per step ($10^{-1.5}, 10^{-2}, 10^{-3.5}, 10^{-5.5}, 10^{-9.5}$ is the right shape), so about $5$ steps.
Formal Solution:
*Step 1 -- Bisection count (a).* After $n$ steps the bracket width is $(3 - 2)/2^n = 2^{-n}$. We need $2^{-n} \le 10^{-6}$, i.e. $n \ge \log_2 10^6 \approx 19.93$. Since $2^{19} = 524{,}288 < 10^6 \le 2^{20} = 1{,}048{,}576$, the answer is $n = 20$. (Running it gives the final bracket $[2.0945511, 2.0945520]$, which contains $r$.)
*Step 2 -- First secant step (b).* $$x_2 = x_1 - f(x_1)\,\frac{x_1 - x_0}{f(x_1) - f(x_0)} = 3 - 16 \cdot \frac{3 - 2}{16 - (-1)} = 3 - \frac{16}{17} = \frac{35}{17} \approx 2.0588.$$
*Step 3 -- Secant iterates (c).* Continuing with the last two points each time:
| step | iterate | $x_k$ | $\lvert x_k - r\rvert$ | |---|---|---|---| | 1 | $x_2$ | $2.0588235294$ | $3.6 \times 10^{-2}$ | | 2 | $x_3$ | $2.0812636598$ | $1.3 \times 10^{-2}$ | | 3 | $x_4$ | $2.0948241461$ | $2.7 \times 10^{-4}$ | | 4 | $x_5$ | $2.0945494310$ | $2.1 \times 10^{-6}$ | | 5 | $x_6$ | $2.0945514812$ | $3.1 \times 10^{-10}$ |
Step 4 is still just above $10^{-6}$; step 5 is the first one below it. So the secant method needs $5$ new function evaluations where bisection needs $20$. The pattern matches the theory: near a simple root $e_{k+1} \approx \left|\frac{f''(r)}{2f'(r)}\right| e_k e_{k-1}$, which gives order $\phi = (1 + \sqrt5)/2 \approx 1.618$.
*Step 4 -- False position (d).* On $[2, 3]$, $f'(x) = 3x^2 - 2 > 0$ and $f''(x) = 6x > 0$: $f$ is increasing and convex, so every chord between a point left of $r$ and the point $(3, 16)$ lies above the graph and crosses the axis to the left of $r$. Each new point therefore has $f < 0$ and replaces the left endpoint; the right endpoint $3$ is never replaced. The first two points coincide with the secant iterates ($2.0588$, $2.0813$), but after that the chord always pivots on $(3, 16)$ instead of on the latest point: the next errors are $4.9 \times 10^{-3}$ and $1.8 \times 10^{-3}$, against $2.7 \times 10^{-4}$ and $2.1 \times 10^{-6}$ for the secant method.
With $b = 3$ fixed, the error ratio tends to $$\frac{e_{k+1}}{e_k} \to 1 - \frac{f'(r)\,(3 - r)}{f(3)} = 1 - \frac{11.161 \times 0.9054}{16} \approx 0.368.$$ So convergence is linear (order $1$), and the bracket width tends to $3 - r \approx 0.905$ instead of $0$. Here the rate happens to beat bisection's $0.5$, but it is nowhere near the secant method, and with a less favourable endpoint it can be far slower than bisection. The Illinois variant (halve the stored $f$ value of an endpoint that stays put twice) or Brent's method fixes this.
Answer: (a) $20$ steps. (b) $x_2 = 35/17 \approx 2.0588$. (c) $5$ steps ($|x_6 - r| \approx 3 \times 10^{-10}$, while $|x_5 - r| \approx 2 \times 10^{-6}$). (d) Because $f$ is convex and increasing on the bracket, the endpoint $3$ is never replaced; the bracket width stalls near $0.905$ and the error shrinks linearly by a factor of about $0.37$ per step.
Intuition
Count function evaluations, not cleverness. Bisection gains exactly one binary digit per evaluation, so a $10^{-6}$ tolerance on a unit bracket costs $20$ of them no matter how nice $f$ is. The secant method reuses the last two values to build a slope, and near a simple root the number of correct digits multiplies by about $\phi \approx 1.618$ each step: here $5$ new evaluations take the error from $0.09$ to $3 \times 10^{-10}$. False position looks like a safe secant method but, on a convex function, one endpoint never moves, the bracket never collapses and the speed drops back to linear. That failure is why practical solvers (Illinois, Brent) modify the stuck endpoint or mix in bisection and interpolation steps.