You have coded RK4 and RK45. This lesson is the why: where the weights 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 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 were derived and are not repeated. Ahead are 4.4 Adaptive Step Size & RK45 (choosing automatically) and 4.5 Stability Regions & Stiffness (what no explicit tableau fixes).
Transcript
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 stages:
Stage asks for the slope at time , at the point reached by walking with a mix of the earlier slopes. Explicit means exists only for , so each needs only earlier ones. The numbers define the method, and stages cost evaluations of per step.
The RK2 family by Taylor matching
Take two stages, and , and . The unknowns are . Match the Taylor series in of one step started on the exact curve. Write for partial derivatives, for the derivative of along the solution, and . The exact solution has , , and differentiating once more, . So
For the method, expand in two variables about with displacement :
Equate the and terms:
Two equations, three unknowns: a one-parameter family, , , every member of order 2. The terms do not match, and the local error is
| method | coefficient of | ||
|---|---|---|---|
| midpoint | |||
| Ralston | |||
| Heun |
(These match 4.2 The Euler Family: Forward, Backward, Heun & Midpoint once is split as above.) Two things follow. First, kills the term, which is Ralston’s choice; the term has no 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 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, (below) is zero for two stages, because the only nonzero multiplies .
Classical RK4
The four-stage method everyone codes:
Read it as three repairs: is the midpoint slope reached by an Euler half step; repeats it using for the half step, a better point; is the end slope, reached along . When depends on only, and the update is : 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 , , . The exact solution is , so . Stage by stage, each evaluation at the point named:
- .
- .
- .
- .
The error is . On this step Euler gives , Heun , Kutta’s third-order method (errors , , ). 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 down the left, the weights in the middle (row says how much of each earlier slope stage uses), and the final weights along the bottom. For RK4:
Think of as a bookkeeping table of slopes: row 3 reads “stage 3 uses half of 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 equals the sum of its row of :
The reason: treat time as one more unknown with . Its stage value is , and that must equal the stage time fed to , or the method would treat and the autonomous system 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 ) must be matched by the method, and each gives one equation in , , . Through order 4 (write for the vector with entries ):
| order | conditions |
|---|---|
| 1 | |
| 2 | |
| 3 | , |
| 4 | , , , |
Gently: is “stage ‘s mix of earlier stage times”; applies the mix twice. No appears. A method has order when every condition through order holds, and then (4.1 Local Error, Global Error & Order) the global error scales as .
How many? New conditions per order are , running totals . In the standard theory (quoted from memory) each condition belongs to one rooted tree, a picture of how derivatives of nest. Block B counts rooted trees by computer: for orders 1 to 4, exactly the conditions tabulated, then for orders 5 and 6, totals .
Block A prints the signed misses (left side minus right side). Computed orders (checked through order 4): Euler ; midpoint, Heun and Ralston ; Kutta’s RK3 (it misses two order-4 conditions, by and ); RK4 and the 3/8 rule . Ralston meets but misses by . The last row, Heun’s nodes with Ralston’s weights, misses by : order 1, though the row sums are fine. Block D confirms by running, halving from to to : observed orders (Euler), to then (midpoint, Heun, Ralston), (RK3), (RK4).
Things to try:
- RK4 at on the first equation reproduces the worked example: landing value , error .
- Choose the RK2 family and drag : the order stays and, on the second and third equations, the one-step error moves (on the first, and every lands on ). Here , which meets only at (set , read ).
- Heun and midpoint land together on the first equation ( at , since ) and apart on the others.
Cost against accuracy
Orders 1 to 4 need evaluations per step. An order- method has error about , so a tolerance needs and about evaluations. Block D finds the steps for error at on , :
| method | steps | evaluations |
|---|---|---|
| Euler | ||
| midpoint | ||
| Ralston | ||
| Heun | ||
| Kutta RK3 | ||
| RK4 |
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 for 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 conditions, while stages leave only free numbers (entries of and ) against for six. Counting proves nothing, but it shows why extra stages stop paying.
The amplification factor. On each stage is a number times ; with , RK4 gives , , , . Then
That is exactly the degree-4 Taylor polynomial of : the four coefficients are the order conditions , , , in disguise (in general , which block C evaluates for four tableaux). It is also a degree-4 polynomial, so it must exceed in size for large . Block C finds where on the negative real axis: (Euler and Heun), (Kutta’s RK3) and (RK4). So RK4 is stable for , only better than Euler despite four times the work. On the imaginary axis (pure oscillation, ) Euler and Heun are unstable for every , RK3 is stable up to and RK4 up to .
RK4 for systems
Only and each become vectors; the weights apply componentwise. Take from , , whose exact solution rotates: . Each stage is a pair:
- .
- at : slope .
- at : slope .
- at : slope .
The update , componentwise, adds , so , matching block E. The landing point is slightly inside the circle: its length is , not . That is not an accident. A step multiplies the length by , where , below for (the imaginary limit of block C). At this is , whose square root is the above.
Each step shrinks the oscillation a little. For small swings a pendulum is this rotation (), so the shrinking is a loss of energy. Block E runs the full pendulum from rad, at rest, to (I have not derived the size of the drift at that amplitude). The energy changes by at and by at . That drift is systematic, not noise.
What RK4 does not fix
- Stiffness. The limit 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 . A different family of steppers keeps energy bounded for oscillators and orbits (4.7 Energy & Symplectic Integrators).
- Choosing . Order says how error scales, not which meets a tolerance; two tableaux sharing stages estimate it: 4.4 Adaptive Step Size & RK45.
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 . The last test uses a tableau that looks like Heun’s but is only first order.
Problems
A three-stage method has , , , , .
- Check the row-sum rule.
- Check the order conditions through order 3, then test the single order-4 condition . What is the order?
- Stage 2 has weight . Why is it still needed?
Show worked solution
- Row 2: . Row 3: . Both hold.
- . . . Next and the other entries are , so . All hold: order at least 3. For order 4, , but it must be : the miss is . So the order is exactly 3.
- is not in the final sum, but is evaluated at ; the condition depends on stage 2 through .
Take the RK2 family member with .
- Find and write the tableau.
- Find the coefficient of in the local error.
- Apply one step with to , (exact ). For this equation and . Check the error against part 2.
- Which makes this step exact?
Show worked solution
- , . Tableau: , , .
- .
- , , . The error (exact minus numerical) is ; part 2 predicts , an exact match since and the expansion terminates.
- Exactness needs with , so (Ralston), the member that kills the term.
Advance the fast mode over in equal steps. Ignore accuracy; only require with , using the real stability limits (Euler, Heun), (Kutta’s RK3), (RK4) from block C.
- Find the smallest and the number of evaluations of for each of the four methods.
- For RK4 at that , find , then the amplitude after steps, and compare with the exact .
- What do the results say about higher order on this mode?
Show worked solution
- Need . Euler and Heun: , so ; evaluations and . RK3: , , evaluations . RK4: , , evaluations .
- , (from ). After steps the amplitude is , while the exact solution is . (Euler at gives and amplitude .)
- Stability forces the step, so extra order buys nothing: RK4 needs evaluations against Euler’s , and every method leaves to 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; stages cost evaluations of .
- Taylor matching of two stages gives , : one parameter, containing midpoint (), Ralston () and Heun (). Two stages cannot reach order 3.
- A Butcher tableau is the whole method; the row-sum rule ties stage times to stage points. RK4 is Simpson’s rule when depends on only.
- Order conditions are equations in alone: new at orders 1 to 4 ( in total), then .
- At error 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 is the degree-4 Taylor polynomial of ; real stability limit , imaginary limit .
- RK4 works on vectors unchanged but fixes neither stiffness nor energy drift ().