LeoMath

Introduction to differential equations · Section 4 of 4

Numerical solutions

Euler and RK4: step size, error and the connection to Taylor expansion.

about 7 min

Start from a problem

Problem

The pendulum equation θ′′+gLsin⁡θ=0 has no elementary closed-form solution. Yet we still want to know what θ(t) looks like and to draw its curve.

We need a method that computes an approximate solution using only the four arithmetic operations, and we must be able to estimate its error and know when it breaks down.

Observe

Choose "Pendulum": θ′′+γθ′+gLsin⁡θ=0. This equation has no elementary closed-form solution. Yet the experiment draws a curve: it is computed step by step. Increase the step h: the red Euler curve drifts away from the blue RK4 curve and may even diverge. Switch back to "Exponential growth", which has an exact solution, and watch the end-point errors of the two methods as h changes: halving h roughly halves Euler's error and divides RK4's by about 16.

Interactive experimentNumerical ODE explorer
Equation
θ′′+γθ′+gLsin⁡θ=0
Time series
Phase portrait
MethodNo closed-form solution for these parameters; numerical solutions only.

What did you observe?Play first, then answer. Read the explanation only after you have thought it through.

  1. 1.For “Exponential growth”, halve the step h. By what factor does each method's end-point error shrink?
  2. 2.Push h to its maximum. Does Euler's curve still look exponential? Which step goes wrong?
  3. 3.In “Damped oscillator”, increase γ. What does the phase portrait turn into? And once γ exceeds ω?
Conjecture

y′=f(t,y) tells us the current slope. From (tn,yn), walk a short step h along that slope to get the next approximate point. Smaller steps are more accurate, but how the error shrinks with h depends on how refined our "one step" is, and that should be computable with a Taylor expansion.

Definitions

Definition 4.1Euler's method
yn+1=yn+hf(tn,yn),tn+1=tn+h.
Definition 4.2Local truncation error and global error

The local truncation error is the difference between one step taken from the exact value y(tn) and y(tn+1). The global error is |yN−y(T)| after N=T/h steps. A method with global error O(hp) has order p.

Derivation: the order of Euler's method

Proposition 4.1Euler's method is first order

Local truncation error O(h2), global error O(h).

Proof

Taylor-expand the exact solution: y(tn+h)=y(tn)+hy′(tn)+h22y′′(ξ)=y(tn)+hf(tn,y(tn))+O(h2). An Euler step is exactly the first two terms, so the local error is O(h2).

Global error: let en=yn−y(tn), let f be L-Lipschitz in y, and let the local error be at most Ch2. Then

|en+1|≤|en|+h|f(tn,yn)−f(tn,y(tn))|+Ch2≤(1+hL)|en|+Ch2.

Iterating, |eN|≤Ch2∑k=0N−1(1+hL)k≤Ch2⋅(1+hL)N−1hL≤ChL(eLT−1), using (1+hL)N≤ehLN=eLT. So the global error is O(h): N steps each committing O(h2) accumulate to O(h).

Higher order: Runge–Kutta

Euler uses only the slope at the left end of each step. Better: sample several slopes inside the step and average them with weights.

Definition 4.3Classical fourth-order Runge–Kutta (RK4)
k1=f(tn,yn),k2=f(tn+h2, yn+h2k1),k3=f(tn+h2, yn+h2k2),k4=f(tn+h, yn+hk3),yn+1=yn+h6(k1+2k2+2k3+k4).
Theorem 4.2RK4 is fourth order

Local truncation error O(h5), global error O(h4).

Proof

The full proof expands k1,…,k4 to order h4 and compares term by term with the expansion of y(tn+h); it is long. We prove a special case that carries the idea: f=f(t) independent of y. Then k1=f(tn), k2=k3=f(tn+h2), k4=f(tn+h), and

yn+1−yn=h6[f(tn)+4f(tn+h2)+f(tn+h)],

which is Simpson's rule, while y(tn+1)−y(tn)=∫tntn+1f. Simpson's rule is exact for cubics with error −h52880f(4)(ξ), i.e. O(h5). The general case has the same conclusion with a messier expansion. The global O(h4) follows from the local error by the same accumulation argument as for Euler.

This is where "halve h, divide the error by 16" comes from: (h/2)4=h4/16.

Theorem: why large steps diverge

Proposition 4.3Stability of Euler's method

For y′=λy with λ<0, Euler gives yn=(1+hλ)ny0. The true solution decays to 0; the numerical one decays iff |1+hλ|<1, i.e. h<2|λ|.

Proof

Substitute: yn+1=yn+hλyn=(1+hλ)yn.

Beyond h=2/|λ| the factor (1+hλ)n oscillates and grows, bearing no relation to the true solution. This explains the divergence of the Euler curve at large steps. Such "stiff" problems call for implicit methods, a topic of Numerical analysis.

Common mistake

Halving the step only halves Euler's error; making h tiny does not compensate for a low-order method, it just adds work and rounding error. And with h too large Euler diverges. Accuracy (order) and stability (a ceiling on h) are separate concerns; both matter.

Application

ApplicationEquations without closed-form solutions

The pendulum, the three-body problem, the Lorenz system, almost every realistic physical model: numerical solution is the only option. The pendulum curve in the experiment is RK4 with step h and four function evaluations per step. The number of steps is N=T/h; trading accuracy against work is the daily business of scientific computing.

Remark

Numerical methods are not "approximate mathematics". They have theorems of their own: order, convergence and stability are precise, provable statements. Every letter in Euler's global bound ChL(eLT−1) has a meaning, and it honestly tells you the error grows exponentially with T: the further the forecast, the less reliable.

Exercises

0 of 2 done

1
Apply Euler's method with h=0.5 to y′=y, y(0)=1 for two steps. What approximation of y(1) results?

Enter the exact value; a fraction such as 1/3 is fine.

2
RK4 has global error O(h4). Halving the step size divides the error by roughly
Answer to exercise 2

Discussion

Found a mistake, have a question or a suggestion? You can also write to 620026600@qq.com

No comments yet. Share your understanding, ask a question, or point out an error on this page.

Log in to join the discussion