# Runge-Kutta and Step doubling

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!

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.

• I have been studying Runge-Kutta (and other methods) from a book, but maybe I should do as you suggested and look into wikipedia. Indeed, I think @arkamis' answer states the same thing that you said in the first part of your answer. In the second part, you refer that I am missing an $h^{5}$, though I don't see where. Thanks for the very nice (and simple in a good way) explanation for the rationale behind everything! – Sosi May 24 '13 at 15:09
• No problem, and you were quite right, I misread the last line. All was well! – Sharkos May 24 '13 at 15:15
• do you have any idea of the answer to question #5, which I included only now? Thanks – Sosi May 27 '13 at 13:14
• Assuming you mean your point 3, I've added an answer. Please don't retroactively change your question if you can help it by the way! – Sharkos May 27 '13 at 15:23

## 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.

• Very cool! Thank you so much! This was truly helpful – Sosi May 24 '13 at 15:11
• For part two, I'm not sure without expanding things out, or maybe there's a typo? If you do expand things out, a bunch of terms will probably cancel, and you might get a clear picture. – Emily May 24 '13 at 15:25
• Maybe I didn't express the question correctly. The second part is about the estimate of the truncation error and how we can use it to adapt the step size of the integration. In the book that I am reading - where I took the information from - they refer that those two equations are used to improve the numerical estimate of $y(x+2h)$, which we get after ignoring the terms $h^{6}$ and higher and then solve those two equations. From my guess, maybe Taylor expansion indicates that $\phi$ has those coefficients that add to $\frac{1}{15}$. Does it make any sense? – Sosi May 24 '13 at 15:55