Skip to content

Convergence of a numerical method

Distinguish approaching a solution from merely stopping, read quadratic convergence in exact Newton iterates, and separate iteration error from grid and rounding error.

Convergence of a numerical method means that its approximations approach the intended mathematical solution as the relevant computational limit is taken. For an iterative solver, that limit is usually an increasing number of iterations. For a discretisation, it is usually a shrinking grid spacing or time step.

A bond-yield solver can stop changing its answer without having found the yield. A pricing grid can be solved very accurately while still being too coarse. Convergence is therefore a claim about a specified target and a specified limiting process, rather than a synonym for “the program finished.”

What is approaching what?

In root-finding, let x∗x^* be the desired root and xkx_k the approximation after kk iterations. Convergence means
lim⁡k→∞Ek=0,Ek=∣xk−x∗∣.\lim_{k\to\infty} E_k=0, \qquad E_k=\lvert x_k-x^*\rvert.

For vectors, replace the absolute value by a stated norm. A maximum-component error and an average squared error answer different questions; the norm and units belong in a convergence report.

For a finite-difference method, write the approximation as uhu_h, where hh measures grid spacing. After defining how the numerical and exact solutions are compared, convergence means ∥uh−u∥→0\lVert u_h-u\rVert\to0 as h→0h\to0. Other error sources must also be controlled: refining the spatial grid alone need not remove time-stepping or boundary-truncation error. A converged inner solver delivers the solution of the discretised equations; grid convergence asks whether those equations approximate the continuous problem. Driscoll and Braun’s finite-difference discussion develops the grid-spacing interpretation.

Watching an error square itself

Consider the dimensionless equation f(x)=x2−2=0f(x)=x^2-2=0, with target x∗=2x^*=\sqrt{2}. Newton–Raphson gives
xk+1=12(xk+2xk).x_{k+1}=\frac{1}{2}\left(x_k+\frac{2}{x_k}\right).

Starting at x0=3/2x_0=3/2, the first iterates can be kept as exact fractions:

Iteration kkExact iterate xkx_kAbsolute error EkE_k, rounded
03/23/28.579×10−28.579\times10^{-2}
117/1217/122.453×10−32.453\times10^{-3}
2577/408577/4082.124×10−62.124\times10^{-6}
3665857/470832665857/4708321.595×10−121.595\times10^{-12}

The falling errors suggest a rate; algebra identifies it. With the signed error ek=xk−2e_k=x_k-\sqrt{2},

ek+1=xk2+2−22 xk2xk=ek22xk.e_{k+1} =\frac{x_k^2+2-2\sqrt{2}\,x_k}{2x_k} =\frac{e_k^2}{2x_k}.

Here every iterate stays above 2\sqrt{2} and below its predecessor. Its positive limit must satisfy x=(x+2/x)/2x=(x+2/x)/2, so it is 2\sqrt{2}. Consequently,

Ek+1Ek2⟶122≈0.353553.\frac{E_{k+1}}{E_k^2}\longrightarrow\frac{1}{2\sqrt{2}}\approx0.353553.
This is quadratic convergence: once the error is small, the next error is roughly a constant times its square. It explains the rough doubling of correct digits near the solution.
Exact Newton errors reach 8.99e-25 at step 4, while binary64 stagnates near 1.25e-16.
Exact Newton errors reach 8.99e-25 at step 4, while binary64 stagnates near 1.25e-16.
Original deterministic calculation: exact rational Newton iterates compared with the update (x+2/x)/2(x+2/x)/2 evaluated in IEEE binary64. Errors use a separately checked high-precision square-root reference; the exact-arithmetic curve is shown only through step 4.

Rate, domain and arithmetic are separate claims

Linear convergence typically has Ek+1/Ek→qE_{k+1}/E_k\to q with 0<q<10<q<1: each iteration removes a roughly fixed fraction of the remaining error. Quadratic convergence has Ek+1/Ek2→CE_{k+1}/E_k^2\to C with 0<C<∞0<C<\infty. For bisection with a continuous function and reliable endpoint signs, the retained bracket width halves per step; its midpoint error is bounded by half that width. This is linear contraction. These rates describe eventual behaviour; early iterations of other methods need not follow their asymptotic rate. An error that decreases at every step is not required for convergence either.
For a sufficiently smooth function with a simple root, Newton’s quadratic convergence is a local result: the starting guess must be sufficiently close. It is not a promise from every initial value. A zero derivative can make a step undefined, and an iteration may leave the admissible domain or approach a different root. NIST §3.8 states the local result and distinguishes simple from multiple roots.
The same word “order” is also used for grid error. If E(h)≈Ch2E(h)\approx Ch^2 in the asymptotic regime, halving hh cuts that error by about four. This is second-order grid accuracy; it does not mean the iterative relation Ek+1≈CEk2E_{k+1}\approx CE_k^2. Specify which variable is changing before interpreting a convergence rate.
Finally, the ideal limit usually assumes exact arithmetic. In the figure, the binary64 calculation eventually repeats the same stored value. The step is zero although the forward error remains about 1.25×10−161.25\times10^{-16}. Extra iterations cannot recover the exact-arithmetic error of about 8.99×10−258.99\times10^{-25} at step 4. Floating-point arithmetic places a practical floor on this example; other problems may stagnate much earlier through rounding, poor conditioning or inaccurate function evaluations. The Python floating-point guide explains why stored values and displayed decimals differ.

Deciding when an answer is adequate

In a real calculation, x∗x^* is usually unknown. Three observable checks help, but have different meanings:

  • A small step ∣xk+1−xk∣\lvert x_{k+1}-x_k\rvert measures movement. It can signal convergence or stagnation.
  • A small residual ∣f(xk)∣\lvert f(x_k)\rvert measures how well the equation is satisfied. It is not automatically a bound on error in xkx_k.
  • An error certificate, when available, translates those observations into a guarantee. For a scalar differentiable ff, if ∣f′(x)∣≥m>0\lvert f'(x)\rvert\ge m>0 throughout the interval joining xkx_k to the root, the mean value theorem gives ∣xk−x∗∣≤∣f(xk)∣/m\lvert x_k-x^*\rvert\le\lvert f(x_k)\rvert/m.
For an implied-volatility equation, the residual is a price difference while the unknown is volatility. Dividing by the local price sensitivity gives a first-order volatility-error estimate near a simple root; a rigorous bound needs control of that sensitivity over an interval. Low vega can make a small pricing residual compatible with a much larger volatility error. This is where numerical conditioning enters the stopping decision.

Choose numerical tolerances in the units of the quantity that matters, monitor failure as well as success, and retain an iteration cap. A finite table of improving values supports a convergence diagnosis; it does not prove the limiting claim for every allowed input.

For the finance applications behind both limits, SelfMadeQuant’s Root-Finding and Numerical Integration applies iteration to bond yield and discretisation to expectations. The full lesson requires membership; the linked outline and introduction are public.

Sources

Last updated
  • numerical methods
  • convergence
  • newton raphson
  • error analysis
  • floating point
Keep connecting the ideas
← Back to the glossaryBack to top ↑