Why combine two ideas?
Bisection spends one function evaluation per step and shrinks a sign-changing interval predictably. A secant line uses the values at two points to predict where the graph meets the axis; it can be much more accurate when the graph is nearly straight. But an extrapolated secant iterate may leave the region of interest, and even an interpolated secant point need not shrink a bracket efficiently. We will use the secant line to propose a point, but accept it only if it makes definite progress on the interval. The safeguard supplies the proof; the secant proposal is an opportunity, not a promise of a faster rate.
A precise algorithm
Assume is continuous, , and . Work in exact arithmetic for the theorem. At the beginning of step , write and suppose the endpoint values have opposite signs. The secant line through and meets the horizontal axis at
Opposite signs make the denominator nonzero and put strictly inside the bracket. Nevertheless, it may be arbitrarily close to an endpoint. Fix with . If lies in the central interval , set ; otherwise set . Evaluate . If it is zero, return exactly. Otherwise retain the subinterval whose endpoint values have opposite signs, reusing the value on the next step.
For an absolute tolerance , one possible stopping rule checks before proposing the next point. On success return the midpoint and the bracket. In implementation, check for endpoint roots before requiring strict opposite signs. The algorithm certifies a result only by returning an exact zero, including an endpoint zero, or by meeting the width condition. Any other exit is uncertified.
Theorem 2.2.1
(Existence, contraction and termination)
Under the hypotheses above, unless an exact zero is encountered, every retained interval is a sign-changing bracket containing at least one zero, and
The midpoint returned by the width rule is at distance at most from every root in the final bracket. The algorithm terminates after at most steps, either at an exact zero or with the width certificate, for any integer satisfying . The guarantee is existence and accuracy for a root in the final bracket, not uniqueness or a count of all roots.
Proof and implementation choices
Proof
(A bracket that keeps its zero and shrinks geometrically)
The intermediate value theorem gives a zero in the initial bracket. At each step the chosen is strictly inside it. If its function value is nonzero, exactly one endpoint has the opposite sign, so the retained interval again has opposite endpoint signs. Continuity gives a zero in that interval.
The accepted point is always in the central interval: a rejected secant point is replaced by the midpoint, which is central because . Both possible new lengths are therefore at most . Induction gives the displayed bound. Since , some finite meets the width condition. Every point of the final bracket lies within half its width of the midpoint, proving the error statement. If the iteration were continued indefinitely without a tolerance or an exact zero, the nested closed brackets would converge to a common point, which is a zero by continuity; no monotonicity or differentiability is needed.
Proof X-ray
The invariant does two different jobs
Two hypotheses carry the argument, and each enters at one identifiable point. Continuity is used only through the intermediate value theorem, applied afresh to every retained bracket: the sign test chooses the piece whose endpoints still have opposite signs, and continuity turns that sign pattern into a zero. The restriction is used only to show that the fallback midpoint itself passes the central test; for the central interval would be empty.
The key move is that the acceptance test makes the length bound independent of where the secant line lands. Whichever point is used, it lies at distance at least from both endpoints, so either retained piece has length at most . Termination is then a fact about a geometric sequence, and the error claim uses only that the midpoint is within half the width of every point of the bracket. Nothing about the secant formula, differentiability or simplicity of the root is needed. The two halves of the invariant are not interchangeable: a shrinking interval need not contain a zero, while a sign-changing interval need not shrink to a point, as the false-position example below shows.
The certificate in the theorem is attached to a specific returned point.
Common mistake
(Reporting the last evaluated point instead of the midpoint)
When the width rule fires after at least one step, the last evaluated point is an endpoint of the final bracket, because the retained piece always has as one end. A root in the bracket may lie the full width away from it. Reporting with tolerance therefore overstates the accuracy by up to a factor of two; the certified distance bound belongs to the midpoint.
A simple exact-arithmetic procedure is:
solve(f, a, b, epsilon, theta):
require a < b, epsilon > 0, 0 < theta <= 1/2
evaluate fa=f(a), fb=f(b)
if fa=0 return exact a; if fb=0 return exact b
require fa and fb to have opposite signs
while (b-a)/2 > epsilon:
s = a - fa*(b-a)/(fb-fa)
if a+theta*(b-a) <= s <= b-theta*(b-a): x=s
else: x=(a+b)/2
evaluate fx=f(x)
if fx=0 return exact x
if fx and fa have opposite signs: b=x; fb=fx
else: a=x; fa=fx
return midpoint (a+b)/2 and bracket [a,b]
The strict bracket hypothesis justifies the last else in exact arithmetic. In an implementation compare signs without multiplying values, since multiplication can overflow or underflow. Detect nonfinite or failed evaluations and a rounded proposal or midpoint equal to an endpoint; return a failure or an explicitly uncertified result if progress is impossible. A floating-point zero may reflect underflow rather than an exact mathematical zero. The proof requires reliable signs and arithmetic; a validated floating-point certificate needs bounds for evaluation and rounding as well. A maximum-iteration exit is not a successful width certificate unless the width condition is actually met.
Common mistake
(Testing opposite signs with a product)
The test fa*fb < 0 looks equivalent to opposite signs, but in IEEE double precision the product of and is , which underflows to . The comparison with then reports no sign change, and a valid bracket is rejected. In the other direction, two values near have a product that overflows. Compare the signs of the two values directly.
A worked trace
Worked example 2.2.2
(A useful secant followed by a rejected one)
Let , and . Endpoint values are and , so , inside . Since , retain . The next secant proposal is , but the central interval is ; is too close to the left endpoint. Bisect instead at , where , and retain . Its midpoint is within absolute distance of the root in the bracket. The exact root is , but the bound did not require knowing it.
The worst-case bound after these two steps is for the length, while the actual length is . The guarantee is intentionally conservative; it covers every continuous function satisfying the sign hypothesis.
Worked example 2.2.3
(The safeguard can reject an exact proposal)
Let on , with and . For an affine function the secant line is the graph itself, so every proposal equals the root . The endpoint values are and , giving , but the central interval is , so the proposal is rejected. The midpoint has , and is retained. The next proposal is again , outside ; the midpoint has , leaving . Now the central interval is , the proposal is accepted, and , so the algorithm returns the exact zero. The half-widths all exceeded , so the loop never stopped on width. This edge case shows the cost of the safeguard: it ignores even a perfect proposal when the proposal lies too close to an endpoint, and pays with bisection steps.
Worked example 2.2.4
(Several roots in the initial bracket)
Let on , with . The bracket contains the three roots , and . Since and ,
which lies outside the central interval . The midpoint has , opposite to , so is retained. The next proposal is
outside ; the midpoint has , so is retained. Only the root remains in the bracket. The theorem promised a root in the final bracket, and the run has already discarded and : the method certifies one root, not all of them.
What the safeguard prevents
Counterexample mode
A sign bracket can stagnate under false position
Take on . The ordinary false-position method always replaces one endpoint by the secant zero, with no central test. Its right endpoint remains , while its left endpoint follows
Indeed, if , then and . Moreover , so . The bracket length tends to , not , even though the secant proposals converge to the root. Thus preserving signs does not by itself certify a midpoint to arbitrary accuracy. For any fixed , our central test rejects a proposal at distance strictly less than from either endpoint; the contraction theorem prevents this kind of stagnation regardless of the trajectory.
Local secant behavior and its limits
The unconstrained secant method uses the two most recent iterates, not necessarily the two bracket endpoints. If and , its next iterate is
Suppose near a simple root (so and ), and distinct iterates converge to without hitting it. The interpolation remainder for the line through , evaluated at , and the mean value theorem for its slope give, for large ,
Here the second derivative is bounded and the secant slope is bounded away from zero near . In particular, dividing by shows the ratio of successive errors tends to zero. This is a conditional local statement: it assumes the iterates exist and converge. It does not establish global convergence, nor does it automatically give that rate for our safeguarded bracket algorithm, which may take bisection steps. A zero denominator makes the unconstrained formula undefined; for instance with starting points and gives equal values.
Concept lensStructural
Three objects to keep separate
The last secant point is an approximation. A sign-changing interval is an existence certificate under continuity. Its half-width is always a location bound; it meets a prescribed tolerance once the bracket is sufficiently small. Neither a small residual nor a small change between proposals alone proves the width claim.
Exercises and solutions
Quick check
(With , and , find the smallest nonnegative integer for which the theorem guarantees the width rule.)
Solution · Answer
We need . At , ; at , . Thus suffices under this worst-case estimate; a particular run may stop earlier.
Quick check
(For on with , verify the first two proposals and retained brackets in the worked trace. Why is the second proposal rejected?)
Solution · Answer
The first secant zero lies in and is accepted; gives . The next proposal is , below the central interval , so it is too close to the left endpoint. The fallback has positive value, giving .
Quick check
(Does on satisfy the theorem? Does on satisfy its strict sign hypothesis?)
Solution · Answer
No in both cases. The first function is not defined or continuous at zero and has no zero on the interval, although its endpoint values have opposite signs. The second is continuous and has root , but both endpoint values are positive; strict sign change is sufficient, not necessary, for a root.
Quick check
(In exact arithmetic a bracket is . State a valid midpoint error bound. If is also small, does that alone certify a better bound?)
Solution · Answer
The midpoint is , and every root in the bracket lies within of it. A residual is measured in units of ; without a quantitative lower slope bound or other additional information it gives no improved distance bound. For example, rescaling a function makes its residual arbitrarily small without moving its roots.