Motivation
A root of is a number for which . Exact symbolic expressions are often unavailable or inconvenient, but numerical approximations can still be useful if accompanied by an error assessment. A graph suggests a location; it does not establish that a zero exists or that the computed digits are reliable. We first retain a bracket that certifies existence, then study an iteration that can converge much faster when its local assumptions hold.
Bisection and its guarantee
Suppose is continuous on and . The intermediate value theorem gives at least one root in . Let . If , stop. Otherwise choose the half-interval whose endpoints have opposite signs, and repeat. At every step continuity and the sign change preserve the existence of at least one root in the retained interval. There may be several roots initially; the method does not identify all of them.
After halvings, the interval length is . Its midpoint satisfies
for any root in the retained interval. This is an absolute error bound, obtained because the farthest point of the interval from its midpoint is half its length. Thus to guarantee error at most , it suffices to choose with . This ideal proof assumes exact signs and arithmetic. In computation, rounding can affect signs and eventually make the midpoint coincide with an endpoint; a robust implementation must account for this.
Worked example 2.1.1
(Bisection)
Take on . The midpoint has positive function value, so retain . Then has negative value, giving ; next has negative value, giving . The final midpoint is within of a root in that interval. No derivative was required.
A sign change is sufficient, not necessary. For on , both endpoint values are positive even though is a root. Conversely, a sign change without continuity is insufficient: changes sign across zero but has no zero there and is not continuous on the interval.
Newton iteration
At a current estimate with , replace the graph locally by its tangent line . Setting that line to zero gives
Worked example 2.1.2
(Newton iteration)
For and , this gives and . These are close to , but fast convergence is a local conclusion, not a promise for every starting point.
Theorem 2.1.3
(Local quadratic convergence)
Suppose is twice continuously differentiable near a root , and . For a starting value sufficiently close to , Newton iterates are defined, remain in that neighborhood and converge to ; moreover for some constant .
Proof
(Taylor remainder and an invariant neighborhood)
Write . Because is continuous and , there are and such that on and on . Let , , and choose if and otherwise.
Suppose . Then , so and is defined. Taylor's theorem, applied from to , yields
for a point between and , hence in . Dividing by and using the Newton formula gives
By induction, every iterate starting with is defined, stays in , and satisfies . The inequality is the quadratic bound. The constants and neighborhood depend on and ; the theorem does not provide a global starting rule.
Proof X-ray
How the neighborhood is chosen
Each hypothesis is spent once. Twice continuous differentiability gives the Taylor remainder with a point and, by continuity on a compact interval, the finite number . The condition is used only to keep near , so that the denominator is both nonzero and controlled. Together they produce one constant .
The non-obvious move is the choice . The quadratic identity alone says nothing about convergence, since can exceed when is large. Inside the ball of radius , however, , which does two jobs at once: it keeps the next iterate in the ball, where the constants remain valid, and it forces geometric decrease. Only after convergence is known does the bound read as quadratic convergence. If , then must shrink with the neighborhood, is not bounded, and the argument cannot start.
The starting point matters as much as the root. For the Newton map sends to and back to , so the iteration cycles and need not converge at all when it does not start close enough.
Counterexample mode
At a double root the quadratic bound fails
A tempting claim is that Newton's method converges quadratically near every root of a smooth function. Take , which is smooth with root but has . For ,
If held for all large , then , which is impossible because . The convergence is only linear. The repaired statement is the theorem as stated: the root must be simple, . For this particular , whose root is known to be double, the modified step lands on at once.
Stopping and safeguarding
A small step can signal convergence but can also result from rounding or a poor scaling of the problem. A small residual is useful only in conjunction with sensitivity. For example has residual at , although the root error is . If throughout the interval between and a root , the mean value theorem gives . Without such information the residual alone does not supply that error bound.
Common mistake
(Reading the Newton step as the error)
Near a simple root the step agrees with the error to leading order, which is why it is often used for stopping. Near a multiple root it does not. For at , the step is , while the error is . Without a derivative bound or a bracket, a small step is evidence, not a certificate.
One practical strategy keeps a continuous sign-changing bracket and accepts a Newton step only when it stays safely inside; otherwise it bisects. Update the bracket using the sign at the accepted point. A specific implementation must define the acceptance test and stopping rules, but preserving the bracket keeps a useful certificate while allowing fast steps.
A fixed-point viewpoint
Theorem 2.1.4
(Contraction and fixed points)
Newton's formula is a fixed-point iteration with wherever the denominator is nonzero. More generally, if is differentiable on a closed interval , maps into itself and satisfies throughout , then every iteration starting in converges to the unique fixed point there.
Proof
(Geometric decrease of successive steps)
The mean value theorem yields . Thus successive differences decrease geometrically, their sum is finite, and the iterates form a Cauchy sequence in the closed interval. Continuity gives a fixed point; applying the same inequality to two fixed points proves uniqueness.
This condition is sufficient, not necessary. It also establishes a fixed point of ; one must check that this fixed point solves the original equation. For Newton's map near a simple root, , which is consistent with rapid local convergence. At points where vanishes, however, the map is undefined, so the preceding theorem cannot be applied across such a point.
As an example, solving can be written as . On , maps the interval into itself, and . The fixed-point theorem therefore certifies convergence from any starting point in that particular interval. This conclusion uses more information than merely observing a few apparently successful iterates.
In several variables the derivative becomes a Jacobian matrix, and the local theorem survives with an invertible Jacobian at the root.
A path to generalization
Newton's method for systems
In several variables the derivative becomes a Jacobian matrix, and the local theorem survives with an invertible Jacobian at the root.
For , the step solves the linear system and sets ; no inverse is formed. If is twice continuously differentiable near a root with invertible, the same argument works in norms: a bound on replaces , a bound on second derivatives replaces , and near . Brackets, however, have no direct analogue in several variables.
Root sensitivity and multiple roots
Suppose , , and we replace the equation by , with a small constant perturbation . If the perturbed root is , Taylor expansion gives approximately zero, so . A small derivative magnifies a vertical perturbation. This is an absolute sensitivity statement: rescaling the function also rescales , so the units and perturbation model must be specified.
At a multiple root, the response can be much more dramatic. For , changing the equation to with produces roots . Changing it to produces no real roots. A small vertical perturbation can therefore change both root location and the number of real roots. This does not contradict Newton's quadratic convergence theorem, whose hypothesis fails at zero.
Comparing convergence rates
An error sequence converges linearly to zero when, for example, eventually for some . It converges quadratically when eventually. Once a quadratic iteration is close enough, the number of correct digits can grow rapidly; a linear method gains a roughly fixed number of digits per iteration. These descriptions concern asymptotic error, not necessarily cost per step. Newton requires a derivative evaluation and can fail far from the root, while bisection uses a bracket and gives a simple worst-case bound.
Worked example 2.1.5
(Newton error)
For , starting at , the first Newton iterate is . The next two are and . The exact error identity follows by substituting the iteration and simplifying. Since the positive iterates are bounded away from zero, the squared error explains the rapid convergence in this example. Notice that the initial iterate may lie on the other side of the root from the later iterates; a Newton sequence does not generally maintain a bracket by itself.
Bisection as a proof of convergence
The retained closed intervals are nested, their lengths tend to zero, and each contains a root by the intermediate value theorem. Their endpoints consequently approach a common limit. Continuity gives a zero at this limit: for example, the endpoint function values retain opposite signs, and if the limit value were strictly positive or negative, continuity would force both nearby endpoints to have that same sign. Thus the existence argument and the shrinking interval together explain convergence; an interval-length calculation alone would not prove that its limit is a root without the preserved sign and continuity.
A posteriori error and a stopping example
An a priori bound is chosen before the calculation, as in the bisection count. An a posteriori bound uses information available after an iterate has been computed. If a continuous bracket has been retained, its midpoint has error at most relative to every root within that bracket. The statement is independent of how many safe Newton steps were taken. By contrast, the Newton correction alone is not generally a rigorous error bound; it is based on a tangent approximation.
Consider on and suppose a computation gives . On this interval , so the mean value theorem gives . Here , and the bound is . The exact error is smaller, but the bound follows without knowing the exact decimal expansion. The derivative lower bound must hold between the approximate point and the root. A derivative measured only at the point is not enough.
A stopping procedure should specify both the desired absolute or relative tolerance and what is being bounded. A bracket width addresses absolute root error. A residual tolerance may be more convenient when units or scales vary, but it needs a sensitivity estimate to imply root accuracy. Near zero an absolute tolerance matters even when a relative criterion is also used. Finally, iterations must have a maximum count or stagnation check to avoid endlessly repeating a floating-point value; such a stop should report failure to meet the requested guarantee rather than label the result accurate.
Common mistake
(Strict increase does not require a positive derivative everywhere)
For in the last exercise below, vanishes at zero, so the stronger assertion everywhere is false. Nevertheless the factorization proves strict increase directly. Conversely, a nonnegative derivative alone permits a function to be constant on an interval; strict increase needs an additional argument.
Existence, uniqueness, convergence, and the numerical accuracy of an iterate are four different claims, each with its own hypotheses.
Summary
A continuous sign-changing bracket proves existence and controls midpoint error by its width. It does not prove uniqueness, and it can miss a root that does not change sign. Newton's tangent iteration often converges quadratically near a simple root, but its derivative and starting-point assumptions are essential. A safeguarded method can use a bracket to protect Newton steps while retaining the possibility of fast local progress.
To assess a reported root, first identify the certificate: a bracket, a residual combined with a derivative bound, or a separately justified a posteriori estimate. The value of depends on the scale of , while the distance to a root depends also on the slope. Hence replacing by a nonzero multiple does not change its roots but changes a raw residual. A stopping rule must account for this distinction and for finite-precision stagnation.
A further subtlety is that finding one root does not settle a global question about all roots. After bisection identifies a root in one interval, other roots may lie outside it or even inside the original interval. To count roots, additional information such as monotonicity or a separate root-counting theorem is needed. A numerical graph sampled at finitely many points cannot rule out unobserved oscillations between samples.
Exercises
Quick check
(Starting with for , how many bisections guarantee midpoint error at most ?)
Use the bound .
Solution · Answer
Require . Since , suffices; does not under this bound.
Quick check
(Apply one Newton step to from .)
Here .
Solution · Answer
.
Quick check
(Why does a bracket with equal endpoint signs not prove that no root exists?)
Think of a root at which does not change sign.
Solution · Answer
A function can touch the axis without changing sign, as does on ; two crossings can also leave equal endpoint signs.
Quick check
(Let on . Show that the interval contains exactly one real root, then take two bisection steps. Is the midpoint of the final bracket necessarily the exact root? Explain which information establishes uniqueness.)
Existence and uniqueness need different arguments.
Solution · Answer
The function is continuous and its endpoint values have opposite signs. It is strictly increasing on the real line, because whenever ; hence the root is unique. The first midpoint is , at which , so the method stops immediately and no second step is needed. The exact hit is a special feature of this example, not a general guarantee. Without monotonicity, the initial sign change alone guarantees at least one root but not exactly one.