Why the usual theorem does not apply
Newton's method replaces a function by its tangent and takes the tangent's zero as the next approximation. At a simple root , a nonzero derivative makes the familiar local quadratic convergence theorem possible. At a multiple root the tangent is horizontal, and that theorem cannot simply be reused. The method may still converge, but usually at a different rate. Here all formulas describe exact real arithmetic; finite-precision function evaluation and stopping decisions require separate analysis.
Definition 2.4.1
(Root of multiplicity )
A root of has multiplicity (an integer, here ) if, on an open interval containing ,
where near . This factorization says more than merely : it specifies the first nonvanishing factor.
From now on assume such a factorization with . Write . The ordinary and multiplicity-corrected updates are respectively
These expressions are used only for with nonzero derivative. If the root is already known to have been reached, stop instead of evaluating .
Error identities and local convergence
Theorem 2.4.2
(The effect of multiplicity)
Under the assumptions above, sufficiently close to and with , both updates are defined and
For a sufficiently close initial point, either iteration converges to . If the ordinary iteration does not reach in finitely many steps, its successive error magnitudes satisfy
The corrected iteration has locally for some constant . The inequality is an upper bound: the corrected iteration can converge faster or terminate exactly in special cases.
Proof
(Canceling the common power of the error)
Differentiation gives . The bracket is nonzero in a sufficiently small neighborhood because it tends to . Canceling for proves both identities. The ordinary error multiplier tends to , a number strictly between zero and one. By continuity, on a smaller neighborhood its absolute value is bounded by a fixed ; therefore iterates remain in that neighborhood and . The multiplier limit then gives the stated error ratio, provided no error is zero.
For the corrected formula, continuity bounds above and away from zero locally, giving . Shrink the starting neighborhood so that and every subsequent iterate remains there; the errors then tend to zero. If an iterate equals , stop. Nothing in this local proof guarantees convergence from an arbitrary starting point.
Proof X-ray
Where each hypothesis enters
The proof has one algebraic move and two analytic ones. The algebraic move is the factorization of the derivative, : the same power that makes also divides , so the Newton quotient is a smooth multiple of even though both and vanish at . The condition is used twice: it keeps the bracket away from zero, so both updates are defined near , and it makes the ordinary multiplier tend to rather than to an indeterminate form.
The first analytic move turns a limit into a uniform bound. A multiplier that only tends to a number below one does not yet show that iterates stay near ; choosing a neighborhood on which its absolute value is at most makes that neighborhood map into itself, and only then can the bound be repeated to give . The second move, for the corrected update, uses the known value to cancel the first-order part of the numerator exactly, leaving . Continuity of near bounds that numerator, which supplies the constant . If the factor used differs from , the cancellation fails and a linear term survives.
The theorem predicts a rate that is easy to misread when an iteration is observed in practice.
Common mistake
(Convergence near a root is not evidence of quadratic convergence)
An ordinary Newton iteration that converges does not thereby have the quadratic rate known for simple roots. At a double root the error is asymptotically halved at each step, so about further steps are needed to reduce it by a factor of , since . A steady error ratio near is a symptom of multiplicity, not of a coding error, and it is the signal that suggests estimating .
Worked example: the correction in action
Worked example 2.4.3
(One ordinary and one corrected step at a double root)
Let and start at near . Here and . Since and , the quotient is and
Indeed, the exact corrected error map is wherever the denominator is nonzero; at it gives , as computed. Near zero the new error is approximately . The smaller first-step error in this example illustrates the theorem; it is not a claim that a correction improves every starting point globally. The function also has a distinct simple root at .
Worked example 2.4.4
(The ordinary error ratio tends to one half)
For the same function, , so for with
Hence , which tends to as , in agreement with the theorem. At the ratio is , giving as before. Since lies strictly between and for , every positive start gives positive errors that decrease, and successive ratios approach from above. The convergence is linear: the error is roughly halved per step, not squared.
An incorrect multiplicity and sensitive data
Suppose instead that an integer or real factor is used in . Its local error multiplier tends to . Thus a wrong factor generally leaves a linear term; local contraction follows from this argument only when , or . A factor outside that interval is not justified by the contraction argument, and the endpoint cases need separate analysis.
Worked example 2.4.5
(The endpoint factor produces a two-cycle)
Take , so and , and use . For , , so
From the iterates are : the error magnitude never changes and the sequence does not converge. The multiplier is exactly , the boundary of the contraction interval, which is why the endpoint cases had to be excluded. With instead, , an oscillating but convergent sequence with multiplier .
Common mistake
(A guessed multiplicity can damage a simple root)
Doubling the Newton step because a root “might be double” is not harmless. For the simple root of (so ), the step with gives , the same two-cycle as above, whereas ordinary Newton would have reached in one step. The correction is justified only when the multiplicity is known or has been estimated reliably.
Counterexample mode
A small residual need not mean a comparably small root error
For the value at is only , although the distance to the root is . A residual is measured in function-value units and cannot by itself certify the same numerical error in . Moreover, replacing the equation by moves the roots to for , while has no real roots. A fast method for the unperturbed equation does not remove this sensitivity to changes in the problem.
Practice with solutions
Quick check
(For , derive the ordinary and the corrected Newton updates.)
Solution · Answer
Away from , . Ordinary Newton gives , so the error is multiplied by exactly . The corrected update with gives in one step. Stop there, because the next quotient is undefined.
Quick check
(A root has multiplicity . What limiting error multiplier results from using the factor ?)
Solution · Answer
It is . The absolute value is below one, so the local contraction argument applies, but the convergence is linear: this is not the quadratic cancellation obtained with .
Quick check
(For , compute the corrected step from .)
Solution · Answer
The exact map gives . Thus the error falls from to in this step, close to the predicted .
Quick check
(Does a residual prove for and ?)
Solution · Answer
No. It only implies for this particular function; attains that bound. A useful residual-to-error conversion needs additional information about the function near the root.