Locating a zero
A numerical root is an approximation to a number satisfying . An iterative formula alone is not a convergence guarantee: one must specify the starting point and the hypotheses on . Different methods exchange guaranteed progress for speed, and a small function value is meaningful only relative to the local sensitivity of the inverse problem.
Definition 6.1.1
(Sign-changing bracket)
Let be continuous on . The interval is a bracket for if , that is, and are nonzero and have opposite signs.
The intermediate value theorem ensures at least one root in a bracket. Bisection evaluates at , stops if , and otherwise keeps the half interval whose endpoints have opposite signs, which is again a bracket.
Proposition 6.1.2
(Bisection error bound)
Let be a bracket for and let be the interval retained after halvings, with (if some midpoint is a root, the method stops there). Then contains a root, has length , and its midpoint is within of at least one root in .
Proof
(Halving keeps a bracket)
Each retained half has endpoints of opposite sign, so by induction is a bracket, and the intermediate value theorem puts a root in it. Each step halves the length, giving . A point of an interval of length is at distance at most from the midpoint, so the root in is within of its midpoint.
The assumptions guarantee existence and an error bound, not uniqueness. If is strictly monotone there is at most one root.
Worked example 6.1.3
(Three bisection steps for the square root of two)
For on we have and . The first midpoint has , so the retained interval is . The second midpoint has , leaving . The third midpoint is , with , so the next interval is . After two halvings the midpoint is within of the root; indeed and . After three halvings the bound is for the midpoint , whose true error is about .
Common mistake
(No sign change does not mean no root)
Bisection cannot detect a root solely from a sign change if the root has even multiplicity. For on we have , so is not a bracket, yet is a root. The sign test is a sufficient condition for a root, not a necessary one.
Fixed-point iteration
Rewrite the equation as and iterate . A fixed point of is a root of only if the chosen rearrangement establishes that equivalence on the domain in question. The contraction theorem provides a useful sufficient condition.
Definition 6.1.4
(Fixed point and contraction on an interval)
Let and . A point is a fixed point of if . The map is a contraction on with constant if and for every , where .
Theorem 6.1.5
(Contraction mapping on an interval)
Let be a contraction on with constant . Then there is a unique fixed point , and every iteration starting in converges to it. Moreover and .
Proof
(Geometric tail and Cauchy sequence)
The iterates remain in and successive differences satisfy . Summing the geometric tail shows that the iterates are Cauchy. Completeness of and closedness of give a limit . The Lipschitz inequality makes continuous, so . If is another fixed point, forces equality. Applying the contraction directly to and proves the first bound; summing the tail proves the second.
If is differentiable on the interior and continuous on , the mean value theorem supplies the Lipschitz bound whenever . The invariant interval is a separate condition.
Counterexample mode
A small derivative without an invariant interval
Claim: if on , then has a fixed point in . Take on . Then , but and , so maps outside itself. The equation gives , so there is no fixed point in . Even , with derivative one, has no fixed point on any interval. The repair is the hypothesis , which the contraction theorem requires in addition to the Lipschitz bound.
Turning successive steps into an error bound
The theorem's first estimate involves the unknown . For an implementable estimate, sum the remaining steps instead.
Proposition 6.1.6
(Computable fixed-point error bounds)
Under the contraction hypotheses on , for ,
Proof
(Summing the remaining steps)
Apply the contraction bound repeatedly to obtain for . The triangle inequality up to , followed by , gives the geometric tail, hence the first inequality. For the second, write and move the last term to the left.
The second formula is a bound in terms of the fixed-point residual ; it is not automatically a bound in terms of the original residual unless their relationship is known.
Worked example 6.1.7
(A computable certificate for a square root)
For , choose on . Since lies in , is increasing and . It is a contraction with , and its unique fixed point in is . Starting with gives and . The first bound certifies
The certificate is conservative: the actual error is about . It is valid without knowing the root's decimal expansion. This calculation assumes exact arithmetic; a rounded step and an approximate value of do not automatically give a rigorous machine-level enclosure.
Why a small step needs a contraction factor
The factor becomes large when is close to one. A step of size with a proved gives only a bound for the current error.
Common mistake
(A small step is not a small error)
Stopping when is tiny is not a certificate. The map has step size everywhere and has no fixed point. If the contraction hypotheses hold, one can stop at when is below a chosen absolute tolerance; otherwise the test has no such guarantee. Account separately for rounding when a rigorous computer certificate is required.
Local attraction and repulsion
A global invariant interval is useful when the starting value is uncertain. Near a known fixed point , there is a complementary local test.
Proposition 6.1.8
(Local attraction and repulsion)
Let be continuously differentiable in a neighborhood of with .
- If , there is a closed interval around that maps into itself and on which is a contraction; every start in converges to .
- If , no iteration with for all converges to .
Proof
(Continuity of the derivative at the fixed point)
Suppose . By continuity there is a closed interval on which . The mean value theorem gives for , so , and the same estimate for two points of shows that is a contraction there. The contraction theorem finishes the first case.
Suppose . Continuity gives on a smaller interval around , so by the mean value theorem for . If , the iterates eventually stay in , say from index on, and then with . These distances grow, contradicting .
The repulsion part does not describe where an orbit that leaves the interval will go.
Worked example 6.1.9
(Derivative one at the fixed point)
The case is inconclusive, not a proof of either behavior. Take and . For we have with , so the sign is kept and magnitudes decrease; they converge to a limit satisfying , hence . By contrast, gives for every nonzero start, so the magnitudes increase and cannot tend to zero. Both maps have and fixed point .
Quick check
(Let on , starting at . Show the interval is invariant, compute , bound using the latest step, and compare with the true error.)
Find the fixed point first.
Solution · Answer
and . The unique fixed point is ; and . The bound is , equal to the true error. This equality in one example does not make the general bound an exact error formula.
Newton's method
Linearizing at and setting the tangent approximation to zero gives
provided . Newton's method can converge much faster than bisection near a simple root, but the update may leave the original interval or encounter a zero derivative.
Definition 6.1.10
(Simple root and quadratic convergence)
A root of a differentiable is simple if . A sequence converges quadratically if there is a constant with for all large .
Worked example 6.1.11
(Newton iterates for the square root of two)
For and , the update is . Thus and . The errors are , and . The ratios and stay bounded, as quadratic convergence predicts; the number of correct digits roughly doubles. Check: , and , so the residual of is .
Concept lensAnalytic
Newton's method as a fixed-point iteration
Newton's update is the fixed-point iteration for , whose fixed points are the roots of . When and , differentiation gives , which vanishes at a simple root. The local attraction theorem then applies with a contraction constant that can be made as small as we wish near , which explains why Newton converges faster than any linear rate. For , and .
Theorem 6.1.12
(Local quadratic convergence of Newton's method)
Suppose on a neighborhood of a root , and . For a sufficiently close starting value, Newton iterates are well-defined and converge to , with for some constant .
Proof
(Taylor remainder and a shrinking neighborhood)
Shrink the neighborhood to a closed interval around on which and . Taylor's theorem expanded from to gives . Therefore the next error has magnitude at most with . Choosing the initial neighborhood small enough, with radius such that , makes each step satisfy ; the iterates stay in the neighborhood and decrease geometrically, so the squared-error bound applies at every step.
Proof X-ray
Where each hypothesis enters
The two constants have different sources. The condition and continuity of give a lower bound on a whole interval, which makes the division in the update legitimate and bounds . The assumption gives the upper bound for the Taylor remainder. The one non-obvious move is the choice of radius: the quadratic bound alone does not prevent the next point from lying outside the interval where and were measured. Requiring turns the quadratic inequality into , which keeps the orbit inside and closes the induction. Drop and no positive exists, so the argument has no constant .
The simple-root assumption matters: for , Newton gives , only linear convergence for nonzero starts. A poor start may fail even for a simple root.
Counterexample mode
Newton steps defined at every stage but no convergence
Claim: if at every step, Newton's method converges to a root. Take and . Then , , so . Next , , so . The iterates cycle forever, with nonzero derivatives at both points and function values and that never vanish. The real root is near . The repair is the local hypothesis of the theorem: convergence is guaranteed only from a start sufficiently close to a simple root.
The explorer continues the square-root example above from , the first iterate produced there from . Its independent bisection starts with of width : a midpoint error bound below needs nine halvings. The first practice question below instead starts with width and needs ten. The two-cycle and zero-derivative cases show why a Newton step is not a bracket certificate.
Common mistake
(A small residual is not a small root error)
If between and a root , the mean value theorem gives . When is small the bound can be large: has residual at zero despite root error one. A robust implementation checks a residual with an appropriate scale, a step size and an iteration limit; a maintained sign-changing bracket supplies an independent error certificate. Floating-point rounding may prevent either test from decreasing indefinitely.
Practice with solutions
Quick check
(How many bisection halvings on an initial interval of length guarantee its midpoint has error at most ?)
Use the midpoint bound .
Solution · Answer
The midpoint error is at most . Since and , ten halvings suffice and are the least certified by this bound.
Quick check
(Verify that maps into itself and is a contraction there. Identify its fixed point in that interval.)
Find the minimum of and the range of .
Solution · Answer
and has its minimum in the interval; hence , so it maps the interval into itself. Also increases from to , and has absolute value at most there. Its positive fixed point satisfies .
Quick check
(Apply Newton's method to and determine its convergence factor away from zero.)
Simplify .
Solution · Answer
For , , so convergence is linear with factor .