Why Newton Iterations Need a Stopping Rule
Newton’s method generates a sequence of approximations to a root. In practice, we need a decision rule for when to stop calculating. Two natural quantities are the distance between consecutive approximations and the value of the function at the current approximation. These are useful diagnostics, but neither one, by itself, certifies that the current approximation is close to a root.
That distinction matters because the iteration can move very little while still being far from a root, or the function value can be small simply because the function is scaled to have small values. A reliable stopping decision considers what each test measures, what it leaves unmeasured, and whether additional information about the function is available.
Two Quantities to Monitor
Let \(f\) be differentiable, and suppose Newton’s method is being applied starting from \(x_0\). As long as \(f'(x_n)\ne 0\), the next iterate is defined by the Newton update.
The successive-step size at iteration \(n\) is the magnitude of the change just made. The residual at \(x_n\) is the function value \(f(x_n)\); when measuring its size, we use its absolute value.
The Newton formula gives an exact relationship between these two quantities and the derivative at the current iterate:
Thus, the step size is not a second independent measurement of the function value: it is the residual size divided by the magnitude of the derivative. If the derivative is large, a substantial residual can produce a small step. If the derivative is small, even a small residual can produce a large step.
Absolute and Relative Tests
An absolute step test stops when \(s_n\) is below a chosen step tolerance. An absolute residual test stops when \(|f(x_n)|\) is below a chosen residual tolerance. The tolerances need not be the same: step size has the units of \(x\), while residual size has the units of \(f(x)\). Their numerical values should be selected with the application and desired accuracy in mind.
A relative test scales the quantity being checked against the size of the values involved. For example, a step test might require the step to be small compared with the current iterate. One common form is:
where \(\tau_{\mathrm{abs}}\) and \(\tau_{\mathrm{rel}}\) are nonnegative tolerances. This form combines an absolute tolerance, which remains meaningful near zero, with a relative tolerance, which scales with the size of the iterate. The precise test used should always be stated; “the step is small” is not a complete stopping rule.
A residual test can likewise compare \(|f(x_n)|\) with a chosen absolute tolerance, or scale it when the problem supplies a meaningful reference size for function values. A relative residual is not automatically meaningful if there is no natural scale or if the reference value is zero.
Worked Example: Checking Both Tests for a Square-Root Problem
Apply Newton’s method to \(f(x)=x^2-2\), starting at \(x_0=1.5\). The derivative is \(f'(x)=2x\), so the iteration is \(x_{n+1}=(x_n+2/x_n)/2\). Compute three updates, then check the step and residual at \(x_3\).
Worked Example: Checking Both Tests for a Square-Root Problem
At \(x_0=1.5=3/2\), the first update is:
At \(x_1=17/12\), the next update is:
The third update is:
The step at this update is the difference between \(x_3\) and \(x_2\):
To check the residual without relying only on rounded iterates, use the exact fraction for \(x_2\): \(f(x_2)=1/166464\approx 0.000006007\). The residual at \(x_3\), evaluated from its exact fraction, is approximately \(0.00000000000451\). Thus, with a step tolerance of \(0.00001\) and a residual tolerance of \(0.00000001\), both tests pass at \(x_3\). As a final check, \(x_3\) is approximately \(1.594\times 10^{-12}\) away from \(\sqrt{2}\), so it is indeed very close to the root in this example.
This example shows how to report both checks separately. Passing them is useful evidence, but the closeness of this particular approximation also depends on the behavior of this particular function near its root.
Why a Small Step Does Not Guarantee a Small Root Error
Consider \(f(x)=e^{20x}-1\), which has the root \(r=0\). Starting at \(x_0=1\), the Newton step is small compared with the distance from the iterate to the root.
Worked Example: A Small Step Far from the Root
At \(x_0=1\), the function value is \(e^{20}-1\), and its derivative is \(20e^{20}\). Therefore the Newton update is:
The step size is:
But the root is \(0\), so the root error at the starting point is \(|x_0-r|=1\). Even after the update, the error is \(|x_1-r|\approx 0.95\). A step tolerance of \(0.05\) would accept this update, although the new iterate remains far from the root. Meanwhile, the residual at \(x_0\) is \(e^{20}-1\), approximately \(485165194\), which is certainly not small. The residual check warns that the small step does not indicate a small root error here.
The reason is visible in the update formula: when \(|f'(x_n)|\) is large, dividing by it can make \(s_n\) small even when \(|f(x_n)|\) is large. A small change in one iteration describes the movement of the method, not directly the distance to a root.
Why a Small Residual Does Not Guarantee a Small Root Error
Residual size can also be misleading. Multiplying a function by a small nonzero constant leaves its roots unchanged, but multiplies every residual by that constant. Therefore, without information about the scale and derivative of the function, an arbitrarily small residual can occur far from the root.
Worked Example: A Tiny Residual with a Large Root Error
Let \(f(x)=0.000001(x-1000)\), whose root is \(r=1000\). At \(x_0=0\), the residual is:
A residual tolerance of \(0.01\) would pass, yet the root error is:
The derivative is the constant \(f'(x)=0.000001\). The Newton step is \(f(0)/f'(0)=-1000\), so the update gives \(x_1=0-(-1000)=1000\), the exact root. This large step reveals why the small residual alone was not evidence of a nearby root. The example also shows that the residual depends on the scale of the function, whereas the root does not.
A Condition That Converts Residual into an Error Bound
A residual can give a rigorous bound on root error when the derivative is known not to become too small between the iterate and a root. The justification follows directly from the Mean Value Theorem.
To justify the bound, apply the Mean Value Theorem to \(f\) on the interval with endpoints \(x\) and \(r\). Since \(f(r)=0\), there is a point \(\xi\) between them such that \(f(x)-f(r)=f'(\xi)(x-r)\). Taking absolute values and using the assumed derivative lower bound gives the desired result.
The condition must hold on the whole interval between \(x\) and the root, not merely at \(x\). In the scaled linear example, \(m=0.000001\), so the bound at \(x=0\) is \(0.001/0.000001=1000\). It correctly fails to certify a small error.
Combining the Checks in Practice
For a Newton computation, record the current iterate, the step just taken, and the residual at the current iterate. A practical stopping policy often requires both quantities to meet their tolerances, rather than stopping as soon as either one passes. This guards against the two kinds of misleading behavior illustrated above, although it is not a proof of accuracy without further conditions.
At the current iterate, verify that \(f'(x_n)\ne 0\) before computing the Newton step.
Compute \(s_n=|x_{n+1}-x_n|\) and compare it with the stated absolute or combined absolute-relative step tolerance.
Compute \(|f(x_{n+1})|\) at the new iterate and compare it with the stated residual tolerance.
If both tests pass, report that fact. Claim a specific root-error bound only if a suitable derivative bound or other justified error estimate is available.
Be precise about the indexing: \(s_n\) measures the move from \(x_n\) to \(x_{n+1}\), whereas \(f(x_n)\) is the residual before that move. When assessing the newly computed iterate \(x_{n+1}\), evaluate its residual \(f(x_{n+1})\), not the residual from the preceding iterate. Also state whether your tolerances are absolute, relative, or combined.
Common Mistake: Treating the Newton Correction as the Error
A tempting but incorrect calculation is to identify the Newton correction with the distance to the root. For the exponential example, one might reason: “The correction is about \(0.05\), so the root must be within \(0.05\).” That conclusion does not follow. The correction is \(|f(x_n)|/|f'(x_n)|\), while the actual root error is \(|x_n-r|\). They are different quantities.
To correct the reasoning, report the step only as the size of the latest update. Use the residual as a separate diagnostic, and use a theorem with its conditions checked if a root-error guarantee is needed. In particular, a derivative lower bound on the interval to a root yields the residual-based bound proved above; the Newton step alone does not.
Check Your Understanding
Answer each question using the definitions and conditions from this tutorial.
- For a Newton update, express the step size in terms of the residual and derivative at the current iterate.
- Why can a small step occur even when the current iterate is far from a root?
- Explain how rescaling a function can make its residual small without changing its root.
- State the derivative condition that allows a residual to bound root error, and give the resulting inequality.
- When checking a newly computed iterate \(x_{n+1}\), which residual should be evaluated?
