Convergence Rates

The Central Idea

Suppose a numerical approximation \(x_n\) approaches an exact value \(x^*\).

Define the error

Convergence asks whether

Convergence rate asks how fast that happens.

Convergence Is More Than Getting Closer

Two methods may both converge to the same answer but at very different speeds.

For example, one method may reduce error by a fixed fraction each step while another squares the error.

Those differences determine computational cost.

A General Error Model

Many iterative methods satisfy an asymptotic relation of the form

Here:

• \(p\) is the order of convergence;
• \(C\) is the asymptotic error constant.

Formal Order of Convergence

A sequence \(x_n\to x^*\) has order \(p\) if

for some finite positive constant \(C\).

Linear Convergence

Linear convergence corresponds to

with

Example: Linear Convergence

Suppose

Then the errors might behave like

Each step cuts the error approximately in half.

Bisection Is Linearly Convergent

Bisection halves the root-containing interval at each step.

The midpoint error is bounded by a quantity proportional to

Thus bisection has linear convergence.

Superlinear Convergence

A method is called superlinear when

The error reduction becomes increasingly dramatic as the iteration proceeds.

The Secant Method

Near a simple root, the secant method has convergence order

This is superlinear but slower than quadratic convergence.

Quadratic Convergence

Quadratic convergence means

Once the error is small, squaring it can reduce it extremely rapidly.

Example: Quadratic Error Reduction

Suppose approximately

Starting from

we obtain roughly

The number of correct digits can roughly double each step.

Newton's Method and Quadratic Convergence

Near a simple root and under appropriate smoothness assumptions, Newton's method satisfies

This is one reason Newton's method is extremely fast once it enters its local convergence region.

Cubic and Higher-Order Convergence

Some methods satisfy

with

These methods can converge very rapidly near the solution, although each iteration may be more expensive.

Sublinear Convergence

A method can converge more slowly than linearly.

For example,

approaches zero, but

This is sublinear behavior.

Asymptotic Behavior

Convergence order is usually an asymptotic concept.

A method may behave irregularly in early iterations and only later settle into the predicted relation

The Asymptotic Regime

The asymptotic regime is the range where the leading error term dominates higher-order terms.

Only in this regime should the theoretical convergence rate be expected to appear cleanly.

Pre-Asymptotic Behavior

Before entering the asymptotic regime:

• higher-order error terms may matter;
• the initial guess may be poor;
• nonlinear effects may dominate;
• transient behavior may obscure the eventual rate.

Convergence in a Mesh Parameter

Numerical differentiation, integration, and differential-equation methods are often analyzed by a discretization parameter \(h\).

A typical error model is

The method is then said to be order \(p\).

Halving the Step Size

If

then

Therefore,

Error-Reduction Factors

Common refinement factors are:

• first order: error decreases by about \(2\);
• second order: error decreases by about \(4\);
• third order: error decreases by about \(8\);
• fourth order: error decreases by about \(16\).

Observed Order of Accuracy

If exact errors are available,

then the observed order is

Example: Observed Order

Suppose

and

Then

The observed behavior is second order.

Observed Order Without the Exact Solution

Often the exact answer is unknown.

Suppose

Then differences between successive refinements can estimate \(p\).

Three-Level Order Estimate

With approximations

an observed order estimate is

Why Three Levels Work

Assume

Then

while

Their ratio is approximately

Richardson Extrapolation

The same error model can improve the approximation itself.

If

then

cancels the leading \(h^p\) error term.

Convergence of Numerical Differentiation

Standard finite-difference formulas have characteristic orders.

For example:

Thus forward difference is first order and central difference is second order.

Convergence of Numerical Integration

Composite quadrature rules also have characteristic rates:

and

Convergence of ODE Methods

Common global orders include:

• Euler: \(O(h)\);
• Heun or midpoint: \(O(h^2)\);
• classical RK4: \(O(h^4)\).

These rates describe global error on a fixed time interval under suitable smoothness and stability conditions.

Convergence of Iterative Linear Solvers

For an iteration

the error satisfies

Convergence is governed by powers of the iteration matrix \(T\).

Spectral Radius and Linear Convergence

If

the stationary iteration converges.

Asymptotically, the slowest-decaying mode often behaves like

A smaller spectral radius generally means faster linear convergence.

Convergence Factors

For linearly convergent iterations,

The constant \(C\) acts as an asymptotic convergence factor.

Smaller \(C\) means faster error reduction.

Digits Gained per Iteration

If a linearly convergent method reduces error by a factor \(C<1\), then the approximate number of decimal digits gained per iteration is

For \(C=0.1\), roughly one decimal digit is gained per iteration.

Efficiency Versus Order

A higher-order method may require more work per step.

Therefore, order alone does not determine efficiency.

A fair comparison considers:

• cost per iteration or step;
• number of function evaluations;
• memory requirements;
• stability restrictions;
• error reduction achieved.

Convergence Rate Versus Stability

A method can have high formal order but still fail if used outside its stability region.

Convergence analysis must therefore be interpreted together with stability.

Convergence Rate Versus Conditioning

A fast-converging algorithm does not fix an ill-conditioned problem.

The iteration may quickly converge to the accurate solution of a nearby problem, yet that nearby problem may have a substantially different exact answer.

Convergence Rate Versus Roundoff

Theoretical error models assume the discretization error dominates.

Eventually, floating-point rounding may create an error floor.

Further refinement can then stop improving the result.

The Error Plateau

A typical refinement sequence may show:

1. pre-asymptotic irregularity;
2. clean theoretical convergence;
3. roundoff-dominated stagnation;
4. possible deterioration under excessive refinement.

Log-Log Convergence Plots

If

then

A plot of \(\log E\) against \(\log h\) should therefore approach a straight line with slope

Why Log-Log Plots Are Useful

A log-log plot can reveal:

• whether power-law convergence is present;
• the approximate convergence order;
• the onset of asymptotic behavior;
• roundoff plateaus;
• unexpected implementation errors.

Convergence Tables

A useful convergence table records:

• step size or iteration number;
• numerical approximation;
• absolute error;
• error ratio;
• observed order.

Example Convergence Table

Suppose a second-order method produces errors:

Each halving of \(h\) reduces error by a factor of \(4\), consistent with

Order Reduction

A method may fail to achieve its theoretical order because assumptions are not satisfied.

Causes include:

• insufficient smoothness;
• singularities;
• poor boundary treatment;
• stiffness;
• inaccurate nonlinear solves;
• noise or roundoff;
• implementation errors.

Smoothness Requirements

High-order truncation formulas usually depend on higher derivatives.

If those derivatives do not exist or become very large, the expected order can degrade.

Mesh Refinement and Resolution

Convergence can fail to appear if the mesh is too coarse to resolve the dominant solution features.

Examples include:

• boundary layers;
• sharp peaks;
• rapid oscillations;
• thin fronts;
• localized singular behavior.

Relative Versus Absolute Convergence

Absolute error is

Relative error is

Near \(x^*=0\), relative error becomes difficult to interpret, so combined absolute and relative measures are useful.

Residual Convergence

Iterative solvers often monitor residuals rather than exact errors.

For

define

Residual reduction is useful, but conditioning determines how residual error translates into solution error.

Stopping Based on Convergence

An iterative algorithm may stop when

becomes sufficiently small.

But a small step does not automatically prove a small true error.

Stagnation

Floating-point arithmetic can eventually produce

even though the mathematical iteration has not reached the exact solution.

This is numerical stagnation rather than exact convergence.

Divergence

A sequence diverges if it fails to approach the intended solution.

Common symptoms include:

• growing errors;
• oscillation without contraction;
• unstable residuals;
• iterates leaving the valid domain.

Monotone and Oscillatory Convergence

Convergence does not require the approximation to approach from one side.

A sequence can oscillate around the solution while its error magnitude shrinks.

The convergence order concerns the size of the error, not necessarily its sign.

Convergence in Norm

For vectors or functions, convergence is measured with a norm:

The choice of norm determines which aspect of the error is being controlled.

Pointwise and Uniform Convergence

For function approximations \(p_n(x)\), pointwise convergence means

for each fixed \(x\).

Uniform convergence requires

Uniform convergence controls the worst-case error across the entire interval.

Convergence of Series Approximations

If

the truncated approximations

may converge at a rate governed by coefficient decay and function smoothness.

Spectral Convergence

For very smooth or analytic functions, some global basis methods can converge faster than any fixed algebraic power

This rapid behavior is often called spectral convergence.

Algebraic Versus Spectral Convergence

Algebraic convergence behaves like

or

Spectral convergence can decrease much faster when the target function has sufficient smoothness.

Convergence and Computational Complexity

Suppose a method has error

To achieve tolerance \(\varepsilon\), we need roughly

The convergence rate therefore directly affects computational cost.

Higher Order Can Reduce Required Resolution

If two methods have comparable constants and stability, a higher-order method can achieve a given tolerance with a larger step or coarser grid.

This can reduce the total number of evaluations dramatically.

But Error Constants Matter

Two methods of the same order can have different constants:

If \(C_1\ll C_2\), the first method can be substantially more accurate at the same resolution.

Comparing Methods Fairly

Do not compare convergence using only iteration count.

One iteration of one method may require much more work than another.

Compare error against:

• function evaluations;
• matrix-vector products;
• factorizations;
• wall-clock cost;
• memory;
• parallel resources.

A Reliable Convergence Study

1. Choose a problem with a known or highly accurate reference solution.
2. Run the method on a sequence of refined resolutions.
3. Measure error in a clearly defined norm.
4. Compute error ratios.
5. Estimate observed order.
6. Identify the asymptotic regime.
7. Watch for roundoff or noise plateaus.
8. Compare cost as well as order.

A Reliable Iteration-Rate Workflow

1. Define the exact or reference solution.
2. Compute \(e_n=x_n-x^*\).
3. Examine \(|e_{n+1}|/|e_n|\).
4. Test higher powers \(|e_n|^p\) when superlinear behavior is expected.
5. Estimate the asymptotic constant \(C\).
6. Separate early transients from asymptotic behavior.

A Reliable Grid-Rate Workflow

1. Compute with \(h\), \(h/2\), and \(h/4\).
2. Compare at the same physical locations or output quantity.
3. Measure errors or solution differences consistently.
4. Compute \(p_{\text{obs}}\).
5. Repeat refinement until the rate stabilizes.
6. Stop before roundoff or unresolved singular behavior dominates.

Common Error: Claiming Convergence from Two Numbers

Two improving approximations do not establish an asymptotic convergence rate.

Use several refinement levels and look for a stable pattern.

Common Error: Ignoring the Asymptotic Regime

The theoretical order may not appear on coarse grids or early iterations.

Estimate convergence only after the leading error term dominates.

Common Error: Ignoring Roundoff

Very fine refinement can push the computation past the discretization-dominated regime.

Error may then stagnate or increase even though the mathematical method is convergent.

Common Error: Comparing Different Error Measures

An \(L^2\) error, maximum error, residual norm, and relative error answer different questions.

Convergence tables should use the same measure across all resolutions.

Common Error: Confusing Iteration Count with Accuracy

More iterations do not guarantee useful progress if the method has stagnated, diverged, or reached a roundoff floor.

Common Error: Ignoring Work per Iteration

Quadratic convergence can be attractive, but if each iteration is extremely expensive, another method may be more efficient overall.

Common Error: Assuming Formal Order Is Always Observed

Theoretical order depends on assumptions such as smoothness, consistency, and stability.

Numerical experiments should verify the rate rather than merely assume it.

Example: First-Order Refinement

Suppose a method produces

and

Then

Example: Fourth-Order Refinement

Suppose

and

The ratio is

Therefore,

Example: Linear Iteration Factor

Suppose

The method is linearly convergent with factor

Each iteration removes about \(80\%\) of the current error.

Practice 1: Linear Convergence

If

what type of convergence is this?

Practice 2: Quadratic Convergence

If

and approximately

estimate \(|e_{n+1}|\).

Practice 3: Error Reduction

A second-order method uses step \(h\). By what factor should the leading error decrease when \(h\) is halved?

Practice 4: Observed Order

Suppose

Estimate the observed order.

Practice 5: Richardson Extrapolation

Write the Richardson formula for a method with leading error \(O(h^2)\).

Practice 6: Secant Order

What is the approximate order of convergence of the secant method?

Practice 7: RK4 Refinement

Classical RK4 has fourth-order global error. Approximately how much should the error decrease when the step size is halved?

Practice 8: Spectral Radius

A stationary iteration has

What does this indicate about asymptotic linear convergence?

Practice 9: Error Plateau

What numerical effect commonly causes error to stop decreasing under extremely fine refinement?

Practice 10: Log-Log Slope

If a log-log plot of error versus \(h\) has slope approximately \(3\), what is the observed convergence order?

Practice Answers

Practice 1

Since the error is multiplied by an approximately fixed factor less than \(1\), the convergence is

Practice 2

Practice 3

Practice 4

Practice 5

Practice 6

Practice 7

Practice 8

The iteration is convergent because

The asymptotic error is expected to decay roughly like

in the slowest mode.

Practice 9

Floating-point roundoff and cancellation commonly create an error floor or plateau.

Practice 10

What to Remember

Convergence rate describes how rapidly numerical error decreases.

is the standard iterative error model.

• linear convergence has \(p=1\) with a fixed reduction factor below \(1\);
• superlinear convergence has increasingly strong error reduction;
• quadratic convergence satisfies \(e_{n+1}\approx Ce_n^2\);
• the secant method has order about \(1.618\);
• Newton's method is often quadratic near a simple root;
• grid-based methods often satisfy \(E(h)\approx Ch^p\);
• halving \(h\) reduces leading error by about \(2^p\);
• observed order can be estimated from error ratios or three refinement levels;
• Richardson extrapolation uses the known order to cancel leading error;
• formal order appears only in the asymptotic regime;
• roundoff, instability, insufficient smoothness, and poor resolution can reduce or hide the theoretical rate;
• method efficiency depends on cost as well as convergence order.

Where We Go Next

Convergence rates tell us how error changes when resolution or iteration count is increased. The final step is to use that information dynamically: estimate error during the computation and automatically allocate more effort only where it is needed.

The next lesson, Adaptive and Error-Controlled Methods, develops local error estimation, tolerance scaling, step acceptance and rejection, adaptive grids, refinement indicators, embedded methods, and reliable stopping logic across numerical algorithms.