Numerical solution of differential equations

Each individual Euler step commits a small local error of size $O(h^2)$ from truncating the Taylor series after the linear term, but these local errors can compound over the roughly $(T-t_0)/h$ steps needed to reach a fixed time $T$. The theorem shows the compounding is mild: the Lipschitz condition prevents small local mistakes from being amplified faster than exponentially, so the global error drops to first order, $O(h)$, in the step size — one order worse than the local error, which is the typical pattern for one-step methods.

Write the local error committed in one step as the difference between the exact solution advanced by Taylor expansion and the Euler update. Taylor's theorem gives $y(t_{n+1}) = y(t_n) + h f(t_n, y(t_n)) + \frac{h^2}{2} y''(\xi_n)$ for some $\xi_n$ between $t_n$ and $t_{n+1}$, so the local truncation error is $\tau_n = \frac{h^2}{2} y''(\xi_n)$, bounded by $\frac{h^2 M}{2}$ using the assumption $|y''(t) | \le M$.

Subtract the Euler update $y_{n+1} = y_n + h f(t_n, y_n)$ from this exact Taylor expansion. Writing $e_n = y(t_n) - y_n$, the difference of the two right-hand sides gives $e_{n+1} = e_n + h\left[f(t_n, y(t_n)) - f(t_n, y_n)\right] + \tau_n$. The Lipschitz condition bounds the bracketed term by $L|e_n|$, so $|e_{n+1}| \le (1+hL)|e_n| + \frac{h^2 M}{2}$.

Since $e_0 = 0$ (the starting value is exact), unrolling this recursion by induction gives $|e_n| \le \frac{h^2M}{2}\sum_{k=0}^{n-1}(1+hL)^k = \frac{hM}{2L}\left[(1+hL)^n - 1\right]$, using the geometric-series identity. Finally, $(1+hL)^n \le e^{Lhn} = e^{L(t_n-t_0)}$ because $1+x\le e^x$ for all real $x$, which turns the bound into $|e_n| \le \frac{hM}{2L}\left(e^{L(t_n-t_0)}-1\right)$ — exactly the claimed inequality, and manifestly $O(h)$ for fixed $t_n$.

RK4 evaluates the slope four times per step at cleverly chosen intermediate points instead of once, and averages them with weights $1,2,2,1$ (out of $6$). This extra work buys three more orders of accuracy compared to Euler's method: matching the Taylor expansion of the true solution through the $h^4$ term, instead of stopping after the linear term.

Expand each stage in a Taylor series around $(t_n, y_n)$. Since $k_1=f(t_n,y_n)=y'(t_n)$, and $k_2, k_3$ evaluate $f$ at the midpoint using $y_n$ shifted by half a step in the direction of an earlier stage, substituting the chain rule for $y'=f$, $y''=f_t+f_yf$, and $y'''=f_{tt}+2f_{ty}f+f_{yy}f^2+f_y(f_t+f_yf)$ into each $k_i$ produces four polynomials in $h$ agreeing with $y'(t_n), y''(t_n), y'''(t_n)$ up to the orders that each stage can see.

Forming the weighted combination $\frac{1}{6}(k_1+2k_2+2k_3+k_4)$ and multiplying by $h$, the coefficients of $h^1, h^2, h^3$ and $h^4$ in this sum are exactly the coefficients of the Taylor expansion $y(t_n+h) = y(t_n) + hy'(t_n) + \frac{h^2}{2}y''(t_n) + \frac{h^3}{6}y'''(t_n) + \frac{h^4}{24}y^{(4)}(t_n) + \cdots$ through the $h^4$ term — this is precisely the classical set of order conditions that the coefficients $c=(0,\frac12,\frac12,1)$ and $b=(\frac16,\frac13,\frac13,\frac16)$ of the RK4 tableau were chosen to satisfy.

Because the two series agree through $h^4$, the first term where they can differ is the $O(h^5)$ term, so the local truncation error is $O(h^5)$ per step. As in the Euler case, telescoping these local errors over the $n\approx (T-t_0)/h$ steps needed to reach a fixed time using the Lipschitz condition on $f$ loses exactly one power of $h$, giving a global error of $O(h^4)$.