Unit 6: Convergence & Error Analysis for Initial Value Problems

1. General One-Step Numerical Integrator

Any autonomous or non-autonomous one-step method can be expressed in the canonical form:

where $\Phi: [t_0, T] \times \mathbb{R}^d \times [0, h_0] \to \mathbb{R}^d$ is the continuous increment function.

2. Formal Definitions of Error and Consistency

Let $y(t)$ denote the exact analytical solution of the IVP $y' = f(t, y), y(t_0) = y_0$.

Definition 1: Local Truncation Error (LTE)

The local truncation error $d_{n+1}$ (or residual defect) is the error introduced in a single step starting from the exact trajectory:

The local truncation error per unit step is defined by:

Definition 2: Consistency

A numerical method is said to be consistent with the ODE if the local truncation error per unit step vanishes as $h \to 0$:

Since $\lim_{h \to 0} \frac{y(t_{n+1}) - y(t_n)}{h} = y'(t_n) = f(t_n, y(t_n))$, consistency is mathematically equivalent to:

Definition 3: Order of Consistency

A numerical method has order of consistency $p$ if there exists a constant $C > 0$ such that:

as $h \to 0$ for all sufficiently smooth solutions $y(t)$.

3. Global Truncation Error (GTE)

Definition 4: Global Error

The true global error at grid point $t_n = t_0 + n h$ is the accumulated difference:

A numerical method is convergent of order $p$ if:

The fundamental question of numerical analysis: Under what mathematical conditions does local consistency of order $p$ ($\tau = \mathcal{O}(h^p)$) guarantee global convergence of order $p$ ($\|e_n\| = \mathcal{O}(h^p)$)?

1. The Discrete Gronwall Inequality

The fundamental analytical tool for proving convergence in difference equations is the discrete analog of the Gronwall-Bellman inequality.

Lemma (Discrete Gronwall Inequality): Let $\{z_n\}_{n=0}^N$ be a sequence of non-negative real numbers satisfying:

where $A > 0$ and $B \ge 0$. Then:

Proof:

Unrolling the recursion:

Summing the geometric progression $\sum_{k=0}^{n-1} (1 + A)^k = \frac{(1 + A)^n - 1}{A}$:

Using the elementary inequality $1 + A \le e^A$ for all $A \ge 0$, we have $(1 + A)^n \le e^{n A}$. Substituting this yields the result. $\blacksquare$

2. The Global Convergence Theorem

Theorem (Convergence of One-Step Methods): Consider the IVP $y' = f(t, y), y(t_0) = y_0$ on $[t_0, T]$. Assume:

1. The increment function $\Phi(t, y; h)$ is Lipschitz continuous in $y$ with Lipschitz constant $L_\Phi$:

1. The method is consistent of order $p$: $\|\tau_n(h)\| \le C h^p$.
2. The initial error satisfies $\|e_0\| = \|y(t_0) - y_0\| \le C_0 h^p$.

Then the global truncation error satisfies:

for all $n \le N = (T - t_0)/h$.

Proof:

By definition of the numerical method and exact solution:

Subtracting the numerical scheme from the exact expansion:

Applying the triangle inequality and Lipschitz property of $\Phi$:

Set $z_n = \|e_n\|$, $A = h L_\Phi$, and $B = C h^{p+1}$ in the Discrete Gronwall Lemma:

Since $n h = t_n - t_0$:

As $h \to 0$, $\|e_n\| \to 0$ uniformly on $[t_0, T]$. This proves unconditional global convergence of order $p$. $\blacksquare$

1. Interplay of Truncation Error and Round-Off Error

In finite-precision floating-point arithmetic (IEEE 754), each evaluation of the increment function introduces a round-off error $\epsilon_n \in \mathbb{R}^d$, bounded by machine epsilon:

The actual computed sequence $\{\tilde{y}_n\}$ satisfies:

The total computational error $\tilde{e}_n = y(t_n) - \tilde{y}_n$ combines truncation error and floating-point round-off:

Applying Gronwall's inequality:

2. The Optimal Step Size Trade-Off

The total error bound as a function of step size $h$ is:

• For large $h$, truncation error $C_1 h^p$ dominates.
• For small $h$, round-off error $\frac{C_2 \epsilon_{\text{mach}}}{h}$ blows up as $\mathcal{O}(h^{-1})$ due to accumulation across $N = \mathcal{O}(h^{-1})$ steps!

Minimizing Total Error:

Differentiating $\mathcal{E}(h)$ with respect to $h$ and equating to zero:

| Method | Order $p$ | Scaling of $h_{\text{opt}}$ | Approximate $h_{\text{opt}}$ (Double Prec.) | | :--- | :--- | :--- | :--- | | Forward Euler | $p = 1$ | $\sim \sqrt{\epsilon_{\text{mach}}}$ | $\sim 10^{-8}$ | | Heun / RK2 | $p = 2$ | $\sim \epsilon_{\text{mach}}^{1/3}$ | $\sim 10^{-5.3}$ | | Classical RK4 | $p = 4$ | $\sim \epsilon_{\text{mach}}^{1/5}$ | $\sim 10^{-3.2}$ |

This confirms why higher-order methods are so computationally superior: RK4 reaches near-machine accuracy with step sizes around $10^{-3}$, while Euler would require $10^8$ steps and suffer devastating round-off accumulation.

1. Step Doubling (Richardson Extrapolation)

To dynamically adapt $h$ to maintain a user-specified tolerance $\text{TOL}$, we need an accurate local error estimate $E_n \approx d_{n+1}$. In step doubling:

1. Take one step of size $2h$ from $t_n$ to get $y^{(1)}$.
2. Take two steps of size $h$ from $t_n$ to get $y^{(2)}$.

Assuming order $p$, the local errors satisfy:

Subtracting the two solutions isolates the local error:

Cost: Requires $3$ times the work per accepted step!

2. Embedded Runge-Kutta Pairs (Fehlberg, Dormand-Prince)

Erwin Fehlberg (1969) realized that two Runge-Kutta methods of orders $p$ and $p+1$ (or $p$ and $p-1$) can be constructed that share the exact same stage evaluations $\{k_i\}$:

The local truncation error estimate is computed for zero additional function evaluations:

The Adaptive Step-Size Update Law:

If $E_{n+1} \le \text{TOL}$, the step is accepted. If $E_{n+1} > \text{TOL}$, the step is rejected and repeated. In either case, the optimal next step size $h_{\text{new}}$ is governed by the asymptotic scaling $E \propto h^{p+1}$:

where $S \approx 0.85 - 0.90$ is a conservative safety factor, and $\text{fac}_{\min} \approx 0.2, \text{fac}_{\max} \approx 5.0$ prevent erratic step fluctuations.