Stopping Newton Iteration Using Residuals and Steps

Why Stopping Newton's Method Requires Care

Newton's method produces a sequence of approximations to a root, but an algorithm needs a rule for deciding when to stop. Two common signals are the residual, the value of the function at the current iterate, and the step, the change from one iterate to the next. Both are useful, but neither automatically equals the error in the computed root.

The distinction matters because root error is measured against an actual root, while a residual and a step are quantities calculated from the current iteration. Taylor expansion explains how these quantities are related, and derivative bounds show when that relationship can provide a reliable error estimate.

Residuals and Root Error

Definition: Let \(f(\alpha)=0\), where \(\alpha\) is a root of \(f\). At a point \(x\), the residual is \(f(x)\), and the absolute root error relative to \(\alpha\) is \(|x-\alpha|\).

Suppose \(f\) is continuous on the interval between \(x\) and \(\alpha\), differentiable in its interior, and \(f(\alpha)=0\). The mean value theorem gives a point \(\xi\) between \(x\) and \(\alpha\) such that

f(x)-f(\alpha)=f'(\xi)(x-\alpha).

Since \(f(\alpha)=0\), this becomes \(|f(x)|=|f'(\xi)|\,|x-\alpha|\). Thus the residual can indicate the error only when the derivative is also controlled on the interval to the root.

Theorem: If \(|f'(t)|\ge m>0\) throughout the interval between \(x\) and a root \(\alpha\), then \(|x-\alpha|\le |f(x)|/m\). If instead \(|f'(t)|\le M\) throughout that interval, then \(|x-\alpha|\ge |f(x)|/M\).

The direction of each inequality is important. A lower bound on the derivative's magnitude gives an upper bound on the error. An upper bound on the derivative's magnitude gives a lower bound on the error. The theorem requires the bound to hold all along the interval between the approximation and the root; knowing only the derivative at \(x\) is not enough.

Worked Example: A Small Residual with a Large Error

Let \(f(x)=0.001(x-2)\), whose root is \(\alpha=2\), and consider \(x=0\). The residual is

f(0)=0.001(0-2)=-0.002, \qquad |f(0)|=0.002.

The derivative is \(f'(x)=0.001\) everywhere, so we can use \(m=0.001\). The theorem gives

|0-2|\le \frac{0.002}{0.001}=2.

Direct substitution gives the exact error \(|0-2|=2\), so the bound is attained. The residual is small, but the error is 2. Checking the root confirms \(f(2)=0.001(2-2)=0\). In this example, the small residual cannot be interpreted as a small error without accounting for the small derivative.

Worked Example: A Large Residual Need Not Mean a Large Error

Let \(g(x)=1000(x-2)\), with root \(\alpha=2\), and again take \(x=0\). Then

g(0)=1000(0-2)=-2000, \qquad |g(0)|=2000, \qquad |g'(x)|=1000.

Using the derivative upper bound \(M=1000\) yields the lower bound

|0-2|\ge \frac{2000}{1000}=2.

The exact error is 2, and \(g(2)=1000(2-2)=0\). Here a large residual accompanies an error of only 2 because the derivative is large. A small residual can coexist with a large error when the derivative is small; a large residual can coexist with a moderate error when the derivative is large.

The Newton Step and the Residual

For a differentiable function, Newton's iteration is defined by

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}, \qquad f'(x_n)\ne 0.

Write \(s_n=x_{n+1}-x_n\) for the signed step. Rearranging the iteration gives an exact identity, not an approximation:

s_n=-\frac{f(x_n)}{f'(x_n)}, \qquad f(x_n)=-f'(x_n)s_n.

Therefore a small step means that the residual divided by the derivative at the current iterate is small. It does not, by itself, show that either the residual or the root error is small: a large derivative can produce a small step even when the residual is not small. Conversely, a small residual can produce a sizable step if the derivative is small.

Worked Example: Residuals and Steps in Newton's Method

Apply Newton's method to \(f(x)=x^2-2\), starting at \(x_0=1\). The derivative is \(f'(x)=2x\). At the initial iterate,

f(x_0)=1^2-2=-1, \qquad f'(x_0)=2, \qquad s_0=-\frac{-1}{2}=\frac12.

Thus \(x_1=x_0+s_0=1+\frac12=\frac32\). Check the residual at this iterate:

f(x_1)=\left(\frac32\right)^2-2 =\frac94-\frac84=\frac14.

Now \(f'(x_1)=2(\frac32)=3\), so the next step is

s_1=-\frac{f(x_1)}{f'(x_1)} =-\frac{1/4}{3} =-\frac1{12}, \qquad x_2=x_1+s_1=\frac32-\frac1{12}=\frac{17}{12}.

Substitution checks the new residual:

f(x_2)=\left(\frac{17}{12}\right)^2-2 =\frac{289}{144}-\frac{288}{144} =\frac1{144}.

The exact step identity also checks: \(-f(x_1)/f'(x_1)=-1/12=s_1\). The residual has decreased from \(1/4\) to \(1/144\), and the second step has magnitude \(1/12\). These values show progress, but by themselves they do not certify a particular error bound unless derivative information between the iterate and the root is available.

Why Newton Steps Often Estimate the Error Near a Root

For a simple root \(\alpha\), meaning \(f(\alpha)=0\) and \(f'(\alpha)\ne0\), Taylor expansion explains why a Newton step often has magnitude close to the current root error when the iterate is sufficiently near \(\alpha\). A useful bound makes the conditions explicit.

Theorem: Suppose \(f\) is twice continuously differentiable on an interval containing \(x\) and a root \(\alpha\). Suppose \(|f'(t)|\ge m>0\) and \(|f''(t)|\le M\) throughout that interval. If \(x_+=x-f(x)/f'(x)\), then \(|x_+-\alpha|\le \frac{M}{2m}|x-\alpha|^2\).

This result controls the error after one Newton update. Its proof also identifies why the step can resemble the current error.

Expand at the current iterate.
Taylor's theorem applied between \(x\) and \(\alpha\) gives \(0=f(\alpha)=f(x)+f'(x)(\alpha-x)+R\), where \(|R|\le \frac{M}{2}|\alpha-x|^2\).

Use the Newton update.
Rearranging the Taylor equation gives \(f(x)/f'(x)=x-\alpha-R/f'(x)\). Hence \(x_+=x-f(x)/f'(x)=\alpha+R/f'(x)\).

Apply the derivative bound.
Since \(|f'(x)|\ge m\), \(|x_+-\alpha|=|R/f'(x)|\le \frac{M}{2m}|x-\alpha|^2\), as claimed.

Under these assumptions, the next error is bounded by a constant times the square of the current error. Also, because \(x_+-x=-(x-\alpha)+(x_+-\alpha)\), the signed step equals the negative of the current error plus the next error. When the next error is much smaller, the step magnitude is therefore close to \(|x-\alpha|\). This is a local conclusion: it depends on being in a region where the stated derivative bounds hold and Newton's update is defined.

How a Small Step Can Be Misleading

A small Newton step is not a universal certificate of accuracy. The exact formula \(s_n=-f(x_n)/f'(x_n)\) shows one reason: a very large derivative can make the quotient small even if the point is far from a root. The following example has a unique root and makes this limitation explicit.

Worked Example: A Tiny First Step Far from the Root

For \(x\ge0\), define \(h(x)=-1+x+0.001(1-e^{-10^9x})\), and start Newton's method at \(x_0=0\). Its derivative is \(h'(x)=1+10^6e^{-10^9x}\), which is positive for all \(x\ge0\). Thus \(h\) is strictly increasing. Also,

h(0)=-1, \qquad h(0.9)=-0.1+0.001(1-e^{-900000})<-0.099<0, \qquad h(1.1)=0.1+0.001(1-e^{-1100000000})>0.

Continuity and strict increase show that there is exactly one root \(\alpha\), and it lies between \(0.9\) and \(1.1\). At the initial point, \(h'(0)=1+10^6=1000001\), so the first Newton step is

s_0=-\frac{h(0)}{h'(0)} =\frac{1}{1000001} <0.000001, \qquad x_1=\frac{1}{1000001}.

Yet \(\alpha>0.9\), so \(|x_1-\alpha|>0.9-\frac{1}{1000001}>0.899999\). The first step is less than one millionth, while the error relative to the unique root exceeds \(0.899999\). The derivative is extremely large at the starting point, which makes the Newton quotient small. Checking the defining iteration confirms \(x_1=x_0-h(0)/h'(0)\). This example shows why a step-size test, without conditions on the function and the iteration's location, cannot certify root accuracy.

Practical Stopping Tests and Common Mistakes

A residual test and a step test answer different questions. A residual test asks whether \(f(x_n)\) is small. A step test asks whether the latest Newton update changed the iterate much. To turn either into an error statement requires additional information, such as a derivative bound on an interval known to contain a root.

Test or information	What it can establish	What it cannot establish alone
\(\|f(x_n)\|\) is small	The function value at the iterate is small.	That \(\|x_n-\alpha\|\) is small without a suitable lower bound on \(\|f'\|\).
\(\|s_n\|\) is small	The current Newton correction is small.	That the iterate is close to a root without further local information.
\(\|f'(t)\|\ge m>0\) between \(x_n\) and \(\alpha\)	\(\|x_n-\alpha\|\le \|f(x_n)\|/m\).	A bound of this type if the derivative lower bound is known only at \(x_n\).
\(\|f'(t)\|\le M\) between \(x_n\) and \(\alpha\)	\(\|x_n-\alpha\|\ge \|f(x_n)\|/M\).	An upper bound on the error.

A common mistake is to treat the residual itself as the error. For the first linear example, the incorrect calculation would be “\(|f(0)|=0.002\), so the root error is \(0.002\).” That conclusion does not follow. The correction is to use the derivative information: \(|f'(x)|=0.001\), and the mean value theorem gives the exact error \(|f(0)|/0.001=2\).

In computation, it is often sensible to monitor both residual and step, and to require that they remain small rather than stopping because only one is small. When an error tolerance must be guaranteed, use a justified derivative bound or another validated error estimate. Also check that the iteration has not failed because \(f'(x_n)=0\), that the iterates remain in the region where the assumptions hold, and that the computed quantities are meaningful at the precision being used.

Key takeaway: Residuals and steps are informative diagnostics, not automatic error certificates. Taylor reasoning explains their local relationship to root error; derivative bounds and appropriate interval information determine whether that relationship supports a reliable stopping decision.

Check Your Understanding

Use the definitions and results above to answer the following questions.

If \(|f'(t)|\ge 4\) between \(x\) and a root \(\alpha\), and \(|f(x)|=0.02\), what upper bound does the mean value theorem give for \(|x-\alpha|\)?
Why does an upper bound on \(|f'|\), rather than a lower bound, give a lower bound on the root error?
Write the exact relation between the Newton step \(s_n\), residual \(f(x_n)\), and derivative \(f'(x_n)\).
What assumptions are needed for the displayed quadratic bound on the error after a Newton update?
Give one reason a small step can occur even when the current iterate is not close to a root.