Runge-Kutta method and step doubling

Question

I am studying Runge-Kutta and step size control and came up with a few doubts. Because they are related with this integration method, I will divide it in two parts. First, allow me to introduce the problem.

---

$1^{st}$ part - questions about Runge-Kutta Method

Consider a $2^{nd}$ order Runge-Kutta with general form:

$k_{1}=hf(x_{n},y_{n})$

$k_{2}=hf(x_{n}+\frac{1}{2}h,y_{n}+\frac{1}{2}k_{1})$

$y_{n+1}=y_{n}+k_{2}+O(h^{3})$

where $f(x_{n},y_{n}) = y'(x_{n})$

Now, if we are to consider $4^{th}$ order Runge-Kutta we would get

$k_{1}=hf(x_{n},y_{n})$

$k_{2}=hf(x_{n}+\frac{1}{2}h,y_{n}+\frac{1}{2}k_{1})$

$k_{3}=hf(x_{n}+\frac{1}{2}h,y_{n}+\frac{1}{2}k_{2})$

$k_{4}=hf(x_{n}+h,y_{n}+k_{3})$

$y_{n+1}=y_{n}+\frac{1}{6}k_{1}+\frac{1}{3}k_{2}+\frac{1}{3}k_{3}+\frac{1}{6}k_{4}+O(h^{5})$

This leads me to the following questions:

1. I understand why the 2nd order method has the $y_{n+1}$ indicated above. Yet, shouldn't the $4^{th}$ order version of the method be expressed only as $y_{n+1}=y_{n}+k_{4}+O(h^{5})$ given that $k_{4}$ implicitly has the values of $k_{1}$ to $k_{3}$?
2. Why does the $4^{th}$ order version have those fractional coefficients?

---

$2^{nd}$ part - questions about step-size control

Consider the exact solution for an advance from $x$ to $x+2h$ by $y(x+2h)$ and the two approximate solutions by $y_{1}$ (one step 2h) and $y_{2}$ (two steps each of size $h$). Considering the $4^{th}$ order method we have:

$y(x+2h)=y_{1}+(2h)^{5}\phi+O(h^{6})+...$

$y(x+2h)=y_{1}+2(h)^{5}\phi+O(h^{6})+...$

The difference between these estimates permits estimating the truncation error:

$\Delta=y_{2}-y_{1}$

Which we then use to improve the numerical estimate of the true solution:

$y(x+2h)=y_{2}+\frac{\Delta}{15}+O(h^{6})$

This brings me to the following questions:

1. In the two expressions of y(x+2h) at the top, does $\phi$ include the terms $k_{1}...k_{4}$ in the first part of this post?
2. Why is the final expression $5^{th}$ order, if the original problem was $4^{th}$ order?
3. Where does the coefficient $\frac{1}{15}$ come from?

Thank you for all the insight!

Answer 1

For the first part, the Wikipedia article http://en.m.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods has a detailed discussion of the different members of the family along with a derivation of RK-4. The key idea is that you can do whatever you want in terms of writing down the form of your approximation; all that matters is that doing a Taylor expansion makes all the error terms up to the order of approximation vanish. This is how the coefficients are chosen.

Then in the next part, $\phi$ is the the expression for the error made in the step, without the $(2h)^5$ term. It should be thought of as an expression in terms of the derivatives of $y$ at $x$, but its exact form isn't important, just its independence from $h$. It's the same in both lines to first order in $h$ so the errors are hidden away in the correction term. Note that fourth order means the error term is $h^5$ per step which it is throughout. You then use two fourth order approximations to get a better one by calculating the error approximately. This is reasonable since you've used more data.

---

As to the $1/15$ factor, that simply arises because $(2h)^5-2(h)^5=(16-1)h^5=15h^5$ and if you make only a step of size $h$ you get a factor of $h^5$. Try carefully defining and writing down the different things you work out, then you can see why you take the difference in this way.

Answer 2

Answer to Part 1

The fractional coefficients in RK4 sum to 1. This is in part to satisfy what is known as the order conditions of the integrator. Basically, we want RK4 to be a 4th order method. For this to be true, it has to satisfy a special relationship using the coefficients of its Butcher Tableau (see at the top here), namely

$$\mathbf{b}^T A^kC^{l-1}\mathbf{1} = \frac{(l-1)!}{(l+k)!}$$

where $A$ is the coefficients in the main part of the tableau, $\mathbf{b}$ is a vector of the $b$ coefficients (in RK4, this is 1/6, 1/3, 1/3, 1/6), and $C$ is a diagonal matrix formed by the $C$ coefficients.

We need to craft these coefficients to get $0$-stability. It is provable that if the method is $0$-stable, it will converge to the order of accuracy -- in this case, order 4, or $h^4$.

The reason that we carry $k_1$, $k_2$, etc. through to the final solution is because $k_4$ is not simply a sum of the previous $k$'s. Each $k$ can be thought of as a projection of a finite difference. The RK method essentially averages these projections in a non-standard way. If you do out the math formally, you find that with these weights, you get optimal accuracy for your number of function evaluations.