MATH/APPM 4650
Class notes, March 20

Adaptive Runge-Kutta and Adams-Bashforth

Last time we introduced the Runge-Kutta methods as a way of approximating the Taylor methods using only function evaluations (rather than computing derivatives of those functions and then evaluating).

The second-order Runge-Kutta methods we discussed basically involved finding one new point k₁ computed in terms of f(t, y).

For example, in the modified Euler method, we take k₁ = f(t_i, w_i), then take k₂ = f(t_i+h, w_i+hk₁). The new estimate is then w_i+1 = w_i + h/2 (k₁ + k₂).

This method is said to involve two steps since there are two function evaluations that must be performed to get every new estimate.

These two-step methods also have local truncation error O(h²), so they are second-order.

In general the number of steps in a Runge-Kutta method is not the same as the order.

Steps	2	3	4	5	6	7	8	9	10
Order	2	3	4	4	5	6	6	7	7

The general pattern is not known.

The important thing is that four steps give fourth order, but five steps does not give fifth-order.

This is one reason why the fourth-order Runge-Kutta method is so popular.

It goes like this:

1. k₁ = f(t, w)
2. k₂ = f(t+h/2, w+hk₁/2)
3. k₃ = f(t+h/2, w+hk₂/2)
4. k₄ = f(t+h, w+hk₃)

Then the next step is w_new = w + h/6 (k₁ + 2k₂ + 2k₃ + k₄).
This is one of the most popular methods.

---

Adaptive Runge-Kutta:

A smarter method is, instead of using a fixed h, to change h if the error is too large.

Of course, to do this one needs an estimate for the error.

1. One could do the same Runge-Kutta again with half the step size and estimate the error. But then you'd have to do four function evaluations for the initial method, and another eight function evaluations for the half-step (because you need four to get halfway, and another four to get all the way). That's twelve in all, and only one is repeated, so you have 11 function evaluations.
2. One could use a four-step Runge-Kutta for the method and a six-step Runge-Kutta for the error prediction. Then you get a fourth-order method and a fifth-order error prediction (and you can estimate the error as being roughly the difference between the fourth-order prediction and the fifth-order prediction, since the fifth-order should be much better). But then you need four evalutions for the method and six evaluations for the error calculation, so ten evaluations in all.

It turns out that you can do six function evaluations and get both a fourth-order prediction method as well as a fifth-order correction method using the same function values. This was Fehlberg's discovery.

The method is called Runge-Kutta-Fehlberg, often abbreviated rkf45.

This is the standard prepackaged ODE solver. (In MATLAB it's called ode45.)

For details see the textbook.

---

The Adams-Bashforth method:
This is the simplest multistep method. It expresses w_i+1 in terms of not just w_i but also terms like w_i-1 (the two-step method) and possibly earlier terms as well (three-step incorporates w_i-2, etc.).

The two-step Adams-Bashforth method is w_i+1 = w_i + h/2 ( 3 f(t_i, w_i) - f(t_i-1, w_i-1) ). It is a second-order method.

Other Adams-Bashforth methods are listed in the textbook.

Unlike Runge-Kutta, an Adams-Bashforth method with n steps always has order n.

Important notes::

1. For the two-step Adams-Bashforth method, you can get w₂ in terms of w₀ and w₁. The first term w₀ comes from your initial condition. You need to get w₁ some other way. (A Taylor method or a Runge-Kutta method.) Always use at least a method of at least the same order! For example, with the two-step Adams-Bashforth you could use the midpoint method, the modified Euler method, or the Heun method to get w₁, but you'd never use the regular Euler method. It's a larger error, and it will propagate so that your entire method will be reduced to first-order because of the initial mistake.
2. Despite how the formula looks, you'd never program it that way. If you did, you'd be computing two function evaluations at each step, which defeats the entire purpose of the Adams-Bashforth method. (Which is to get a higher-order method while only doing one additional function evaluation.) Instead save the last few function evaluations you did, then reuse those values instead of recomputing them.

Bad pseudocode:
INPUT f, w[0], t[0], N, h
% Get started using midpoint method
fold = f(t[0], w[0])
w[1] = w[0] + h*f(t[0]+h/2, w[0]+h/2*fold)
FOR i FROM 1 to N-1 DO
   t[i] = t[0] + i*h
   w[i+1] = w[i] + h/2*(3*f(t[i], w[i]) - f(t[i-1],w[i-1]))
   % Computed f twice at each step here!
END DO
OUTPUT w

Better pseudocode:
INPUT f, w[0], t[0], N, h
% Get started using midpoint method
fold = f(t[0], w[0])
w[1] = w[0] + h*f(t[0]+h/2, w[0]+h/2*fold)
FOR i FROM 1 to N-1 DO
   t[i] = t[0] + i*h
   fnew = f(t[i], w[i])
   % Only one computation of f inside the loop!
   w[i+1] = w[i] + h/2*(3*fnew - fold)
   fold = fnew
END DO
OUTPUT w