Flow Lab

Syllabus / Module 4: Numerical Methods for ODEs — The Theory

Lesson 4.3

Runge–Kutta Methods & Butcher Tableaux

Deriving RK2, the classical RK4, the Butcher tableau notation, order conditions, and why RK4 is the workhorse.

Written byClaude Sonnet

🌊
Why this matters for simulation: RK3/RK4 are standard for time-stepping advection in CFD and for tracing particles.

By the end of this lesson you can…

  • Derive the one-parameter family of two-stage methods by Taylor matching and name midpoint, Heun and Ralston in it.
  • Write an explicit Runge–Kutta method as a Butcher tableau, apply the row-sum rule, and turn any tableau into a stepper.
  • Check the order conditions through order 4 from a tableau and say how many conditions each order adds.
  • Show that RK4's amplification factor is the degree-4 Taylor polynomial of the exponential and compute its stability limit.
  • Compare methods by function evaluations at fixed accuracy, apply RK4 to a vector system, and say what it does not fix.
On this page
·
  1. Sample the slope more than once
  2. The RK2 family by Taylor matching
  3. Classical RK4
  4. Butcher tableaux
  5. Order conditions
  6. Cost against accuracy
  7. RK4 for systems
  8. What RK4 does not fix
  9. Exercise: a generic Runge–Kutta stepper
  10. Problems
  11. Key Takeaways

You have coded RK4 and RK45. This lesson is the why: where the weights 16,13,13,16\tfrac16, \tfrac13, \tfrac13, \tfrac16 come from, what a method must satisfy to earn the label “fourth order”, and what you get per function evaluation. In a fluid or flight code one evaluation of ff sweeps a whole grid, so evaluations are the currency.

It builds on 4.1 Local Error, Global Error & Order (order, log-log slopes) and 4.2 The Euler Family: Forward, Backward, Heun & Midpoint, where Heun and midpoint and their amplification factors R(z)R(z) were derived and are not repeated. Ahead are 4.4 Adaptive Step Size & RK45 (choosing hh automatically) and 4.5 Stability Regions & Stiffness (what no explicit tableau fixes).

▶ Video Sampling the slope several times, the RK2 family by Taylor matching, RK4 as Simpson's rule for slopes, Butcher tableaux, order conditions, and cost against accuracycaptions only
Transcript
  1. Euler uses one slope, from the start of the step. Here it is zero, so Euler stays at 1.0 while the exact answer falls to 0.8. A Runge Kutta method samples several slopes inside the step and steps along their weighted average.
  2. Two stages, the second reached by an Euler step of alpha h. Taylor matching gives b one plus b two equals one, b two alpha equals one half: a one-parameter family. Ralston's alpha, two thirds, zeroes the D squared f error term. The f y D f term, one sixth, survives for every alpha, since sum b A c is zero with two stages.
  3. Classical RK4 on this equation, h one half. Slopes: zero at the start; minus 0.5 at the midpoint, reached along k one; minus 0.3828, along k two; minus 0.6538 at the end, along k three. Weights one, two, two, one over six land at 0.79838, error 1.62 times ten to the minus 3. Euler 1.0, Heun 0.75, Kutta's RK3 0.8125; exact 0.8.
  4. A Butcher tableau holds the whole method: stage times c, the matrix A, weights b. Row three reads: stage three uses half of k two, nothing else. Stages look only backward, so the diagonal and above are zero. Each c is its row sum, because time is one more unknown.
  5. Each order condition is one equation in b, c and A. New conditions per order are 1, 1, 2, 4, running totals 1, 2, 4, 8. Counting rooted trees by computer gives 9 and 20 new at orders five and six, totals 17 and 37.
  6. Which tableau meets which conditions? Euler one of eight; midpoint, Heun and Ralston reach order two; Kutta's RK3 order three; RK4 and three eighths meet all eight. Heun's nodes with Ralston's weights miss sum b c by plus 0.25: order one.
  7. Halving the step from 20 to 40 to 80 measures the orders. Euler 1.07 then 1.03. Midpoint 2.05, Heun and Ralston 2.04, then 2.02 for all three. RK3 3.18, 3.10. RK4 4.04, 4.02. Three eighths 4.05, 4.02.
  8. Cost: evaluations to reach error one in ten thousand. Euler 693. Midpoint 106, Ralston 122, Heun 150. RK3 takes 13 steps of 3 stages, 39. RK4 takes 9 steps of 4, 36, as does three eighths: 19 times fewer than Euler.
  9. RK4's R of z is the degree four Taylor polynomial of e to the z. Size of R at most one holds on the real axis down to minus 2.7853 for RK4, minus 2.5127 for RK3, minus 2 for Euler and Heun; on the imaginary axis, to 2.8284 for RK4, 1.7321 for RK3, and nowhere for Euler and Heun.
  10. Systems need no new idea. Rotation, x prime y, y prime minus x, h one half: one RK4 step from one, zero lands at 0.87760, minus 0.47917; exact is 0.87758, minus 0.47943. The landing is inside the circle, length 0.99989, because a step scales length by the size of R of i h, squared 0.99979.
  11. RK4 does not fix stiffness. On y prime equals minus 305 y, stability alone needs 153 steps for Euler, 153 for Heun, 306 evaluations, 122 for RK3, 366, 110 for RK4, 440. At 110 steps R is 0.98122 and the amplitude 0.1242, against the exact 3.47 times ten to the minus 133.
  12. Nor energy drift. A pendulum from one radian, to time 1000, changes energy by minus 0.12292 at h 0.5 and minus 4.578 times ten to the minus 5 at h 0.1. For small swings it is the rotation, shrunk each step by the size of R of i h. The size here is measured, not derived.
  13. Recap: several slopes per step; two stages cannot reach order three; the tableau is the method; conditions total 1, 2, 4, 8. RK4 needs 36 evaluations where Euler needs 693; stiffness and drift remain. Next: adaptive RK45, stability, symplectic.

Sample the slope more than once

Euler walks along the slope at the start of the step, which is wrong almost everywhere in it. A Runge–Kutta method takes several trial slopes inside the step, each at a point reached with slopes already found, and steps with a weighted average. With ss stages:

ki=f(tn+cih,  yn+h∑j=1i−1aijkj),yn+1=yn+h∑i=1sbiki.k_i = f\Big(t_n + c_i h,\; y_n + h\sum_{j=1}^{i-1} a_{ij}k_j\Big), \qquad y_{n+1} = y_n + h\sum_{i=1}^{s} b_i k_i .

Stage ii asks for the slope at time tn+ciht_n + c_i h, at the point reached by walking with a mix of the earlier slopes. Explicit means aija_{ij} exists only for j<ij \lt i, so each kik_i needs only earlier ones. The numbers ci,aij,bic_i, a_{ij}, b_i define the method, and ss stages cost ss evaluations of ff per step.

The RK2 family by Taylor matching

Take two stages, k1=f(t,y)k_1 = f(t,y) and k2=f(t+αh, y+αh k1)k_2 = f(t + \alpha h,\ y + \alpha h\,k_1), and yn+1=yn+h(b1k1+b2k2)y_{n+1} = y_n + h(b_1 k_1 + b_2 k_2). The unknowns are α,b1,b2\alpha, b_1, b_2. Match the Taylor series in hh of one step started on the exact curve. Write ft,fyf_t, f_y for partial derivatives, Df=ft+ffyDf = f_t + f f_y for the derivative of ff along the solution, and D2f=ftt+2ffty+f2fyyD^2f = f_{tt} + 2f f_{ty} + f^2 f_{yy}. The exact solution has y′=fy' = f, y′′=Dfy'' = Df, and differentiating once more, y′′′=D2f+fy Dfy''' = D^2f + f_y\,Df. So

y(t+h)−y=hf+h22 Df+h36(D2f+fy Df)+O(h4).y(t+h) - y = h f + \tfrac{h^2}{2}\,Df + \tfrac{h^3}{6}\big(D^2 f + f_y\,Df\big) + O(h^4).

For the method, expand k2k_2 in two variables about (t,y)(t,y) with displacement (αh, αhf)(\alpha h,\ \alpha h f):

k2=f+αh Df+α2h22 D2f+O(h3),yn+1−y=h(b1+b2) f+h2b2α Df+h32b2α2 D2f+O(h4).k_2 = f + \alpha h\,Df + \tfrac{\alpha^2h^2}{2}\,D^2f + O(h^3), \qquad y_{n+1} - y = h(b_1 + b_2)\,f + h^2 b_2\alpha\,Df + \tfrac{h^3}{2}b_2\alpha^2\,D^2f + O(h^4).

Equate the hh and h2h^2 terms:

b1+b2=1,b2 α=12.b_1 + b_2 = 1, \qquad b_2\,\alpha = \tfrac12 .

Two equations, three unknowns: a one-parameter family, b2=12αb_2 = \tfrac{1}{2\alpha}, b1=1−12αb_1 = 1 - \tfrac{1}{2\alpha}, every member of order 2. The h3h^3 terms do not match, and the local error is

(16−α4) D2f+16 fy Df(coefficients of h3).\Big(\tfrac16 - \tfrac{\alpha}{4}\Big)\,D^2 f + \tfrac16\, f_y\,Df \quad\text{(coefficients of } h^3\text{)}.
α\alpha(b1,b2)(b_1, b_2)methodcoefficient of D2fD^2 f
12\tfrac12(0,1)(0, 1)midpoint+124+\tfrac1{24}
23\tfrac23(14,34)(\tfrac14, \tfrac34)Ralston00
11(12,12)(\tfrac12, \tfrac12)Heun−112-\tfrac1{12}

(These match 4.2 The Euler Family: Forward, Backward, Heun & Midpoint once y′′′y''' is split as above.) Two things follow. First, α=23\alpha = \tfrac23 kills the D2fD^2 f term, which is Ralston’s choice; the fyDff_y Df term has no α\alpha and survives in every member. (That Ralston minimised a bound on the error constants is how I remember his 1962 criterion; I have not derived it.) Second, two stages cannot give order 3: the fyDff_y Df term needs a stage that feeds a derivative of a slope into the next slope, and one earlier slope cannot do that. In tableau language, ∑b A c=16\sum b\,A\,c = \tfrac16 (below) is zero for two stages, because the only nonzero a21a_{21} multiplies c1=0c_1 = 0.

Classical RK4

The four-stage method everyone codes:

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).\begin{aligned} k_1 &= f(t_n, y_n), & k_2 &= f\big(t_n + \tfrac h2,\ y_n + \tfrac h2 k_1\big),\\ k_3 &= f\big(t_n + \tfrac h2,\ y_n + \tfrac h2 k_2\big), & k_4 &= f\big(t_n + h,\ y_n + h k_3\big), \end{aligned} \qquad y_{n+1} = y_n + \tfrac h6\,(k_1 + 2k_2 + 2k_3 + k_4).

Read it as three repairs: k2k_2 is the midpoint slope reached by an Euler half step; k3k_3 repeats it using k2k_2 for the half step, a better point; k4k_4 is the end slope, reached along k3k_3. When ff depends on tt only, k2=k3k_2 = k_3 and the update is h6(g(t)+4g(t+h2)+g(t+h))\tfrac h6\big(g(t) + 4g(t+\tfrac h2) + g(t+h)\big): Simpson’s rule. RK4 is Simpson’s rule extended to the case where the slope depends on where you are.

Worked example. One step of y′=−2ty2y' = -2ty^2, y(0)=1y(0) = 1, h=0.5h = 0.5. The exact solution is 1/(1+t2)1/(1+t^2), so y(0.5)=0.8y(0.5) = 0.8. Stage by stage, each evaluation at the point named:

  • k1=f(0,1)=0k_1 = f(0, 1) = 0.
  • k2=f(0.25, 1+0.25⋅0)=−0.5⋅1=−0.5k_2 = f(0.25,\ 1 + 0.25\cdot 0) = -0.5\cdot 1 = -0.5.
  • k3=f(0.25, 1+0.25⋅(−0.5)=0.875)=−0.5⋅0.765625=−0.3828125k_3 = f(0.25,\ 1 + 0.25\cdot(-0.5) = 0.875) = -0.5\cdot 0.765625 = -0.3828125.
  • k4=f(0.5, 1+0.5⋅(−0.3828125)=0.80859375)=−1⋅0.653824=−0.6538239k_4 = f(0.5,\ 1 + 0.5\cdot(-0.3828125) = 0.80859375) = -1\cdot 0.653824 = -0.6538239.
y1=1+0.56(0−1−0.765625−0.6538239)=0.7983793.y_1 = 1 + \tfrac{0.5}{6}\big(0 - 1 - 0.765625 - 0.6538239\big) = 0.7983793 .

The error is 1.62×10−31.62\times10^{-3}. On this step Euler gives 1.01.0, Heun 0.750.75, Kutta’s third-order method 0.81250.8125 (errors 0.20.2, 0.050.05, 0.01250.0125). The sim below starts on this step.

Butcher tableaux

All the numbers of a method fit in a small table, John Butcher’s notation. Put the stage times cic_i down the left, the weights aija_{ij} in the middle (row ii says how much of each earlier slope stage ii uses), and the final weights bib_i along the bottom. For RK4:

0121212012100116131316\begin{array}{c|cccc} 0 & & & & \\ \tfrac12 & \tfrac12 & & & \\ \tfrac12 & 0 & \tfrac12 & & \\ 1 & 0 & 0 & 1 & \\ \hline & \tfrac16 & \tfrac13 & \tfrac13 & \tfrac16 \end{array}

Think of AA as a bookkeeping table of slopes: row 3 reads “stage 3 uses half of k2k_2 and nothing else”. Stages look only backward, so the diagonal and above are zero. The tableau alone distinguishes one method from another. (An implicit method has nonzero entries on and above the diagonal: 4.5 Stability Regions & Stiffness.)

The row-sum rule. Each cic_i equals the sum of its row of AA:

ci=∑jaij.c_i = \sum_{j} a_{ij}.

The reason: treat time as one more unknown with t′=1t' = 1. Its stage value is tn+h∑jaijt_n + h\sum_j a_{ij}, and that must equal the stage time tn+ciht_n + c_i h fed to ff, or the method would treat f(t,y)f(t,y) and the autonomous system (t,y)′=(1,f)(t, y)' = (1, f) differently. Block A of the cell below holds the tableaux of Euler, midpoint, Heun, Ralston, Kutta’s RK3 and the 3/8 rule, and checks the rule on each.

Order conditions

Each Taylor term of the exact solution (a product of derivatives of ff) must be matched by the method, and each gives one equation in bb, cc, AA. Through order 4 (write AcAc for the vector with entries ∑jaijcj\sum_j a_{ij}c_j):

orderconditions
1∑bi=1\sum b_i = 1
2∑bici=12\sum b_i c_i = \tfrac12
3∑bici2=13\sum b_i c_i^2 = \tfrac13, ∑bi(Ac)i=16\quad \sum b_i (Ac)_i = \tfrac16
4∑bici3=14\sum b_i c_i^3 = \tfrac14,  ∑bici(Ac)i=18\ \sum b_i c_i (Ac)_i = \tfrac18,  ∑bi(Ac2)i=112\ \sum b_i (Ac^2)_i = \tfrac1{12},  ∑bi(A Ac)i=124\ \sum b_i (A\,Ac)_i = \tfrac1{24}

Gently: AcAc is “stage ii‘s mix of earlier stage times”; A AcA\,Ac applies the mix twice. No ff appears. A method has order pp when every condition through order pp holds, and then (4.1 Local Error, Global Error & Order) the global error scales as hph^p.

How many? New conditions per order are 1,1,2,41, 1, 2, 4, running totals 1,2,4,81, 2, 4, 8. In the standard theory (quoted from memory) each condition belongs to one rooted tree, a picture of how derivatives of ff nest. Block B counts rooted trees by computer: 1,1,2,41, 1, 2, 4 for orders 1 to 4, exactly the conditions tabulated, then 9,209, 20 for orders 5 and 6, totals 1,2,4,8,17,371, 2, 4, 8, 17, 37.

🐍 PythonTableaux, order conditions, trees, R(z), orders by halving, work, a vector system
⌘/Ctrl + Enter

Block A prints the signed misses (left side minus right side). Computed orders (checked through order 4): Euler 11; midpoint, Heun and Ralston 22; Kutta’s RK3 33 (it misses two order-4 conditions, by +0.0417+0.0417 and −0.0417-0.0417); RK4 and the 3/8 rule 44. Ralston meets ∑bc2=13\sum bc^2 = \tfrac13 but misses ∑bAc\sum bAc by −0.1667-0.1667. The last row, Heun’s nodes with Ralston’s weights, misses ∑bc=12\sum bc = \tfrac12 by 0.250.25: order 1, though the row sums are fine. Block D confirms by running, halving hh from N=20N = 20 to 4040 to 8080: observed orders 1.07,1.031.07, 1.03 (Euler), 2.042.04 to 2.052.05 then 2.022.02 (midpoint, Heun, Ralston), 3.18,3.103.18, 3.10 (RK3), 4.04,4.024.04, 4.02 (RK4).

◆ Interactive Tableau lab: stages of one step as slope samples, a live order check, and a convergence plot

Loading simulation…

Things to try:

  1. RK4 at h=0.5h = 0.5 on the first equation reproduces the worked example: landing value 0.7983790.798379, error 1.62×10−31.62\times10^{-3}.
  2. Choose the RK2 family and drag α\alpha: the order stays 22 and, on the second and third equations, the one-step error moves (on the first, k1=0k_1 = 0 and every α\alpha lands on 0.750.75). Here ∑bc2=α/2\sum bc^2 = \alpha/2, which meets 13\tfrac13 only at α=23\alpha = \tfrac23 (set 0.670.67, read 0.335000.33500).
  3. Heun and midpoint land together on the first equation (0.750.75 at h=0.5h = 0.5, since k1=0k_1 = 0) and apart on the others.

Cost against accuracy

Orders 1 to 4 need 1,2,3,41, 2, 3, 4 evaluations per step. An order-pp method has error about ChpC h^p, so a tolerance needs h≈(tol/C)1/ph \approx (\text{tol}/C)^{1/p} and about sT/hsT/h evaluations. Block D finds the steps for error 10−410^{-4} at T=5T = 5 on y′=y(1−y)y' = y(1-y), y(0)=0.1y(0) = 0.1:

methodstepsevaluations
Euler693693693693
midpoint5353106106
Ralston6161122122
Heun7575150150
Kutta RK313133939
RK4993636

RK4 at 36 evaluations beats Euler at 693 by a factor of 19. Within order 2 the constants matter: midpoint beats Ralston and Heun here, so Ralston’s choice is a statement about one error coefficient, not every problem.

Why stop at 4? Butcher’s barrier, as I remember it (not derived or checked here): an explicit method has order at most ss for s≤4s \le 4 stages, but order 5 needs 6 stages, order 6 needs 7, order 7 needs 9 and order 8 needs 11. So no explicit 5-stage method has order 5. Block B shows the pressure: order 5 has 1717 conditions, while 55 stages leave only 1515 free numbers (entries of bb and AA) against 2121 for six. Counting proves nothing, but it shows why extra stages stop paying.

The amplification factor. On y′=λyy' = \lambda y each stage is a number times λy\lambda y; with z=hλz = h\lambda, RK4 gives k1=λyk_1 = \lambda y, k2=λy (1+z2)k_2 = \lambda y\,(1 + \tfrac z2), k3=λy (1+z2+z24)k_3 = \lambda y\,(1 + \tfrac z2 + \tfrac{z^2}{4}), k4=λy (1+z+z22+z34)k_4 = \lambda y\,(1 + z + \tfrac{z^2}{2} + \tfrac{z^3}{4}). Then

R(z)=1+z6(6+3z+z2+z34)=1+z+z22+z36+z424.R(z) = 1 + \tfrac z6\Big(6 + 3z + z^2 + \tfrac{z^3}{4}\Big) = 1 + z + \tfrac{z^2}{2} + \tfrac{z^3}{6} + \tfrac{z^4}{24}.

That is exactly the degree-4 Taylor polynomial of eze^z: the four coefficients are the order conditions ∑b=1\sum b = 1, ∑bc=12\sum bc = \tfrac12, ∑bAc=16\sum bAc = \tfrac16, ∑bAAc=124\sum bAAc = \tfrac1{24} in disguise (in general R(z)=1+∑kzk bTAk−11R(z) = 1 + \sum_k z^k\, b^{\mathsf T}A^{k-1}\mathbf 1, which block C evaluates for four tableaux). It is also a degree-4 polynomial, so it must exceed 11 in size for large ∣z∣\lvert z\rvert. Block C finds where ∣R∣=1\lvert R\rvert = 1 on the negative real axis: −2-2 (Euler and Heun), −2.5127-2.5127 (Kutta’s RK3) and −2.7853-2.7853 (RK4). So RK4 is stable for h≤2.7853/∣λ∣h \le 2.7853/\lvert\lambda\rvert, only 39%39\% better than Euler despite four times the work. On the imaginary axis (pure oscillation, z=iyz = iy) Euler and Heun are unstable for every y>0y \gt 0, RK3 is stable up to 1.73211.7321 and RK4 up to 2.82842.8284.

RK4 for systems

Only yy and each kik_i become vectors; the weights apply componentwise. Take x′=y, y′=−xx' = y,\ y' = -x from (1,0)(1, 0), h=0.5h = 0.5, whose exact solution rotates: (cos⁡0.5, −sin⁡0.5)=(0.8775826, −0.4794255)(\cos 0.5,\ -\sin 0.5) = (0.8775826,\ -0.4794255). Each stage is a pair:

  • k1=(0,−1)k_1 = (0, -1).
  • k2k_2 at (1,0)+0.25 k1=(1,−0.25)(1, 0) + 0.25\,k_1 = (1, -0.25): slope (−0.25,−1)(-0.25, -1).
  • k3k_3 at (1,0)+0.25 k2=(0.9375,−0.25)(1, 0) + 0.25\,k_2 = (0.9375, -0.25): slope (−0.25,−0.9375)(-0.25, -0.9375).
  • k4k_4 at (1,0)+0.5 k3=(0.875,−0.46875)(1, 0) + 0.5\,k_3 = (0.875, -0.46875): slope (−0.46875,−0.875)(-0.46875, -0.875).

The update 0.56(k1+2k2+2k3+k4)\tfrac{0.5}{6}\big(k_1 + 2k_2 + 2k_3 + k_4\big), componentwise, adds (−0.1223958, −0.4791667)(-0.1223958,\ -0.4791667), so y1=(0.8776042, −0.4791667)y_1 = (0.8776042,\ -0.4791667), matching block E. The landing point is slightly inside the circle: its length is 0.99989490.9998949, not 11. That is not an accident. A step multiplies the length by ∣R(ih)∣\lvert R(ih)\rvert, where ∣R(ih)∣2=(1−h22+h424)2+(h−h36)2=1−h672+h8576\lvert R(ih)\rvert^2 = (1 - \tfrac{h^2}{2} + \tfrac{h^4}{24})^2 + (h - \tfrac{h^3}{6})^2 = 1 - \tfrac{h^6}{72} + \tfrac{h^8}{576}, below 11 for 0<h<2.830 \lt h \lt 2.83 (the imaginary limit of block C). At h=0.5h = 0.5 this is 0.99978980.9997898, whose square root is the 0.99989490.9998949 above.

Each step shrinks the oscillation a little. For small swings a pendulum is this rotation (sin⁡θ≈θ\sin\theta \approx \theta), so the shrinking is a loss of energy. Block E runs the full pendulum θ′′=−sin⁡θ\theta'' = -\sin\theta from 11 rad, at rest, to T=1000T = 1000 (I have not derived the size of the drift at that amplitude). The energy 12θ′2−cos⁡θ\tfrac12\theta'^2 - \cos\theta changes by −0.1229-0.1229 at h=0.5h = 0.5 and by −4.578×10−5-4.578\times10^{-5} at h=0.1h = 0.1. That drift is systematic, not noise.

What RK4 does not fix

  • Stiffness. The limit h<2.7853/∣λ∣h \lt 2.7853/\lvert\lambda\rvert comes from the fastest decaying mode however smooth the solution is (Problem 3 prices it). The cure is an implicit method (4.5 Stability Regions & Stiffness).
  • Energy drift. For oscillations the drift above comes from ∣R(ih)∣<1\lvert R(ih)\rvert \lt 1. A different family of steppers keeps energy bounded for oscillators and orbits (4.7 Energy & Symplectic Integrators).
  • Choosing hh. Order says how error scales, not which hh meets a tolerance; two tableaux sharing stages estimate it: 4.4 Adaptive Step Size & RK45.
✅ Concept check

Someone keeps Heun's nodes c = (0, 1), a21 = 1 but uses Ralston's weights b = (1/4, 3/4). The weights still sum to 1. What is the order?

✅ Concept check

You integrate a pendulum with RK4 at h = 0.5 and the energy slowly falls over thousands of steps. What is the correct explanation?

✅ Concept check

How many order conditions must an explicit Runge-Kutta tableau satisfy to have order 5 (orders 1 to 5 together)? Block B counts rooted trees.

Exercise: a generic Runge–Kutta stepper

Write one stepper that takes a tableau as data and works for vector states, then measure orders by halving hh. The last test uses a tableau that looks like Heun’s but is only first order.

🧪 Coding exerciseExercise: a stepper driven by a Butcher tableau, and orders by halving h
⌘/Ctrl + Enter

Problems

✏️ Pen & paperIs this tableau third order?●○○

A three-stage method has c=(0,13,23)c = (0, \tfrac13, \tfrac23), a21=13a_{21} = \tfrac13, a31=0a_{31} = 0, a32=23a_{32} = \tfrac23, b=(14,0,34)b = (\tfrac14, 0, \tfrac34).

  1. Check the row-sum rule.
  2. Check the order conditions through order 3, then test the single order-4 condition ∑bc3=14\sum bc^3 = \tfrac14. What is the order?
  3. Stage 2 has weight b2=0b_2 = 0. Why is it still needed?
Show worked solution
  1. Row 2: a21=13=c2a_{21} = \tfrac13 = c_2. Row 3: 0+23=c30 + \tfrac23 = c_3. Both hold.
  2. ∑b=14+0+34=1\sum b = \tfrac14 + 0 + \tfrac34 = 1. ∑bc=34⋅23=12\sum bc = \tfrac34\cdot\tfrac23 = \tfrac12. ∑bc2=34⋅49=13\sum bc^2 = \tfrac34\cdot\tfrac49 = \tfrac13. Next (Ac)3=a32c2=29(Ac)_3 = a_{32}c_2 = \tfrac29 and the other entries are 00, so ∑bAc=34⋅29=16\sum bAc = \tfrac34\cdot\tfrac29 = \tfrac16. All hold: order at least 3. For order 4, ∑bc3=34⋅827=29\sum bc^3 = \tfrac34\cdot\tfrac8{27} = \tfrac29, but it must be 14\tfrac14: the miss is 29−14=−136=−0.0278\tfrac29 - \tfrac14 = -\tfrac1{36} = -0.0278. So the order is exactly 3.
  3. k2k_2 is not in the final sum, but k3k_3 is evaluated at y+h⋅23k2y + h\cdot\tfrac23 k_2; the condition ∑bAc=16\sum bAc = \tfrac16 depends on stage 2 through a32a_{32}.
✏️ Pen & paperThe two-stage family at alpha = 3/4●●○

Take the RK2 family member with α=34\alpha = \tfrac34.

  1. Find b1,b2b_1, b_2 and write the tableau.
  2. Find the coefficient of D2fD^2 f in the local error.
  3. Apply one step with h=1h = 1 to y′=3t2y' = 3t^2, y(0)=0y(0) = 0 (exact y(1)=1y(1) = 1). For this equation fy=0f_y = 0 and D2f=ftt=6D^2 f = f_{tt} = 6. Check the error against part 2.
  4. Which α\alpha makes this step exact?
Show worked solution
  1. b2=12α=23b_2 = \tfrac1{2\alpha} = \tfrac23, b1=13b_1 = \tfrac13. Tableau: c=(0,34)c = (0, \tfrac34), a21=34a_{21} = \tfrac34, b=(13,23)b = (\tfrac13, \tfrac23).
  2. 16−316=8−948=−148\tfrac16 - \tfrac3{16} = \tfrac{8 - 9}{48} = -\tfrac1{48}.
  3. k1=f(0,0)=0k_1 = f(0, 0) = 0, k2=f(34,0)=3⋅916=2716k_2 = f(\tfrac34, 0) = 3\cdot\tfrac9{16} = \tfrac{27}{16}, y1=23⋅2716=98=1.125y_1 = \tfrac23\cdot\tfrac{27}{16} = \tfrac98 = 1.125. The error (exact minus numerical) is −0.125-0.125; part 2 predicts −148⋅6=−18-\tfrac1{48}\cdot 6 = -\tfrac18, an exact match since fy=0f_y = 0 and the expansion terminates.
  4. Exactness needs 3b2α2=13b_2\alpha^2 = 1 with b2α=12b_2\alpha = \tfrac12, so α=23\alpha = \tfrac23 (Ralston), the member that kills the D2fD^2 f term.
✏️ Pen & paperWhen stability, not accuracy, sets h●●○

Advance the fast mode y′=−305 yy' = -305\,y over [0,1][0, 1] in NN equal steps. Ignore accuracy; only require ∣R(z)∣<1\lvert R(z)\rvert \lt 1 with z=−305/Nz = -305/N, using the real stability limits 22 (Euler, Heun), 2.51272.5127 (Kutta’s RK3), 2.78532.7853 (RK4) from block C.

  1. Find the smallest NN and the number of evaluations of ff for each of the four methods.
  2. For RK4 at that NN, find R(z)R(z), then the amplitude after NN steps, and compare with the exact e−305e^{-305}.
  3. What do the results say about higher order on this mode?
Show worked solution
  1. Need N>305/limitN \gt 305/\text{limit}. Euler and Heun: 152.5152.5, so N=153N = 153; evaluations 153153 and 2×153=3062\times153 = 306. RK3: 121.4121.4, N=122N = 122, evaluations 366366. RK4: 109.5109.5, N=110N = 110, evaluations 440440.
  2. z=−305/110=−2.7727z = -305/110 = -2.7727, R=0.9812R = 0.9812 (from 1+z+z22+z36+z4241 + z + \tfrac{z^2}{2} + \tfrac{z^3}{6} + \tfrac{z^4}{24}). After 110110 steps the amplitude is 0.9812110=0.1240.9812^{110} = 0.124, while the exact solution is e−305=3.5×10−133e^{-305} = 3.5\times10^{-133}. (Euler at N=153N = 153 gives R=−0.9935R = -0.9935 and amplitude 0.3670.367.)
  3. Stability forces the step, so extra order buys nothing: RK4 needs 440440 evaluations against Euler’s 153153, and every method leaves 0.10.1 to 0.40.4 of a mode that should have vanished. The remedy is an implicit method (4.5 Stability Regions & Stiffness).

Key Takeaways

  • A Runge–Kutta step samples the slope at several stage points, each reached with earlier slopes, and steps with a weighted average; ss stages cost ss evaluations of ff.
  • Taylor matching of two stages gives b1+b2=1b_1 + b_2 = 1, b2α=12b_2\alpha = \tfrac12: one parameter, containing midpoint (12\tfrac12), Ralston (23\tfrac23) and Heun (11). Two stages cannot reach order 3.
  • A Butcher tableau (c,A,b)(c, A, b) is the whole method; the row-sum rule ci=∑jaijc_i = \sum_j a_{ij} ties stage times to stage points. RK4 is Simpson’s rule when ff depends on tt only.
  • Order conditions are equations in (b,c,A)(b, c, A) alone: 1,1,2,41, 1, 2, 4 new at orders 1 to 4 (1,2,4,81, 2, 4, 8 in total), then 9,209, 20.
  • At error 10−410^{-4} RK4 needed 36 evaluations to Euler’s 693; order 5 needs more than 5 stages (from memory), so order 4 is the sweet spot.
  • RK4’s R(z)R(z) is the degree-4 Taylor polynomial of eze^z; real stability limit 2.78532.7853, imaginary limit 2.82842.8284.
  • RK4 works on vectors unchanged but fixes neither stiffness nor energy drift (∣R(ih)∣<1\lvert R(ih)\rvert \lt 1).
Finished this lesson?

Mark it complete to track your progress (saved in this browser). Reading every section does this for you.

Where this leads

These later lessons build directly on this one: