Back to the on-screen lesson ·
Why the global order is one lower than the local one, what the Lipschitz condition is holding up, and why the theorem's limit is one the arithmetic never reaches.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to distinguish local truncation error from global error and derive the relation between them, prove convergence from consistency and a Lipschitz condition, name the stages and orders of the standard methods, and find the step size at which rounding error takes over.
You can take a step with Euler's method, Heun's method and the classical Runge-Kutta method, and you know that halving the step improves the answer by a factor that depends on the method. This lesson proves that factor, and names the hypothesis without which it is not true at all.
A one-step method is $y_{n+1} = y_n + h\Phi(t_n, y_n, h)$, with $\Phi$ the increment function. The local truncation error is what one step of the method does to the exact solution; the global error is $y(t_n) - y_n$ at a fixed time. A method is consistent of order $p$ when the local error is $O(h^{p+1})$, and convergent of order $p$ when the global error is $O(h^{p})$. $\Phi$ is Lipschitz in $y$ when it changes by at most $L$ times any change in $y$.
A method's local truncation error measures one step applied to the exact solution: $O(h^{p+1})$ for a method of order $p$, and it is found by expanding both the method and the solution in $h$ and comparing. The global error is what anybody cares about, and it is not the same thing. Reaching a fixed time $T$ takes $T/h$ steps, so if the errors merely added the total would be $\dfrac{T}{h} \times h^{p+1} = Th^{p}$: one power lower, lost to the number of steps rather than to the method. But they do not merely add — each error made is carried forward by every subsequent step, and could be amplified. The Lipschitz condition is what forbids that amplification from running away: it gives $|e_{n+1}| \le (1 + hL)|e_n| + Ch^{p+1}$, a linear recurrence whose solution over a fixed interval is
$$|e_n| \;\le\; \frac{Ch^{p}}{L}\left(e^{LT} - 1\right).$$
Consistency alone says nothing about the answer; the Lipschitz condition alone says nothing about accuracy; together they give convergence of order $p$. Two things in that bound are worth reading. The constant grows like $e^{LT}$, so a long integration of a problem whose solutions separate really does lose accuracy exponentially, and no method repairs it. And the theorem is about $h \to 0$ in exact arithmetic — in finite precision the rounding error grows as $h$ shrinks, so the total error has a floor that a smaller step cannot pass.
Another way: steps
Another way: picture
Plot the global error against the step size on log-log axes. The theorem is the straight line of slope $p$ on the right of the picture, and it is only half of it: on the left the line turns and climbs with slope $-1$ as rounding error takes over. The lowest point of the V is the best step there is, and the convergence theorem describes the descent towards it while saying nothing about the climb.
The local order is quoted as the method's order, and a factor of $h$ goes missing. The classical Runge-Kutta method has local error $O(h^{5})$ and is called fourth order, and the number anybody measures is the four. The second mistake is treating the convergence theorem as a promise that a smaller step is a better answer. It is a statement about a limit the arithmetic never reaches: past the balance point, halving the step doubles the rounding error and leaves the truncation error too small to matter, so the total goes up.
Euler: $y_{n+1} = y_n + hf$. The exact advance is $y + hy' + \tfrac{h^{2}}{2}y'' + \cdots$.
Compare term by term.
The first mismatch is the $h^{2}$ term, so the local error is $O(h^{2})$ and the method is first order.
One power lost to the step count.
$y' = y^{2}$, $y(0) = 1$: the solution is $\dfrac{1}{1 - t}$ and blows up at $t = 1$.
No global Lipschitz constant.
Any convergence statement holds only on an interval before the blow-up, where $f$ is Lipschitz on the relevant region.
The hypothesis is local.
Reaching a fixed time takes $O(1/h)$ steps.
Multiplying: $\dfrac{1}{h} \times h^{4} = h^{3}$.
So it is a third-order method, and halving the step should divide the error by about eight — which is the check to run on any implementation.
A one-step method has local truncation error $O(h^{3})$ on each step. What is the order of its global error at a fixed final time?
Answer:
Euler's method has global order $1$, Heun's has $2$ and the classical Runge-Kutta method has $4$. Give the exponent of $h$ in each one's local truncation error.
| Global order | Exponent in the local error | |
|---|---|---|
| Euler's method | 1 | |
| Heun's method | 2 | |
| The classical Runge-Kutta method | 4 |
Match each explicit Runge-Kutta method to its number of stages and its order.
| One stage, order one | Two stages, order two | Four stages, order four | Six stages, not five | |
|---|---|---|---|---|
| Euler's method | ||||
| Heun's method | ||||
| The classical Runge-Kutta method | ||||
| A method of order five |
Put the five steps of proving that a consistent one-step method converges into order.
Number the steps in order (write the number in the box):
A method of order $3$ is run in double precision, where each step's rounding contributes about $10^{-16}$. The global truncation error behaves like $h^{3}$ and the accumulated rounding error like $\dfrac{10^{-16}}{h}$. About how many correct digits can the best step size reach?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Build the argument that a consistent one-step method with a Lipschitz increment function converges at the same order.
This task has no paper form; do it on a device.
You can relate local and global error and prove convergence from the two hypotheses. Say in your own words why a smaller step is not always a better answer.
8. Your turn: the global order of a method with local error $O(h^{4})$, step 3