5Ordinary differential equations
IB Numerical Analysis
5.4 Runge-Kutta methods
Finally, we look at Runge-Kutta methods. These methods are very complicated,
and are rather tedious to analyse. They have been largely ignored for a long
time, until more powerful computers came along and made these methods much
more practical. These are used quite a lot nowadays since they have many nice
properties.
Runge-Kutta methods can be motivated by Gaussian quadrature, but we
will not go into that connection here. Instead, we’ll go straight in and work with
the method.
Definition
(Runge-Kutta method)
.
General (implicit)
ν
-stage Runge-Kutta
(RK) methods have the form
y
n+1
= y
n
+ h
ν
X
`=1
b
`
k
`
,
where
k
`
= f
t
n
+ c
n
h, y
n
+ h
ν
X
j=1
a
`j
k
j
for ` = 1, ··· , ν.
There are a lot of parameters we have to choose. We need to pick
{b
`
}
ν
`=1
, {c}
ν
`=1
, {a
`j
}
ν
`,j=1
.
Note that in general,
{k
`
}
ν
`=1
have to be solved for, since they are defined in
terms of one another. However, for certain choices of parameters, we can make
this an explicit method. This makes it easier to compute, but we would have
lost some accuracy and flexibility.
Unlike all the other methods we’ve seen so far, the parameters appear inside
f
. They appear non-linearly inside the functions. This makes the method much
more complicated and difficult to analyse using Taylor series. Yet, once we
manage to do this properly, these have lots of nice properties. Unfortunately, we
will not have time to go into what these properties actually are.
Notice this is a one-step method. So once we get order
p ≥
1, we will have
convergence. So what conditions do we need for a decent order?
This is in general very complicated. However, we can quickly obtain some
necessary conditions. We can consider the case where
f
is a constant. Then
k
`
is always that constant. So we must have
ν
X
`=1
b
`
= 1.
It turns out we also need, for ` = 1, ··· , ν,
c
`
=
ν
X
j=1
a
`j
.
While these are necessary conditions, they are not sufficient. We need other
conditions as well, which we shall get to later. It is a fact that the best possible
order of a ν-stage Runge-Kutta method is 2ν.
To describe a Runge-Kutta method, a standard notation is to put the
coefficients in the Butcher table:
c
1
a
11
··· a
1ν
.
.
.
.
.
.
.
.
.
.
.
.
c
ν
a
ν1
··· a
νν
b
1
··· b
ν
We sometimes more concisely write it as
c A
v
T
This table allows for a general implicit method. Initially, explicit methods came
out first, since they are much easier to compute. In this case, the matrix
A
is
strictly lower triangular, i.e. a
`j
whenever ` ≤ j.
Example.
The most famous explicit Runge-Kutta method is the 4-stage 4th
order one, often called the classical Runge-Kutta method. The formula can be
given explicitly by
y
n+1
= y
n
+
h
6
(k
1
+ 2k
2
+ 2k
3
+ k
4
),
where
k
1
= f(x
n
, y
n
)
k
2
= f
x
n
+
1
2
h, y
n
+
1
2
hk
1
k
3
= f
x
n
+
1
2
h, y
n
+
1
2
hk
2
k
4
= f (x
n
+ h, y
n
+ hk
3
) .
We see that this is an explicit method. We don’t need to solve any equations.
Choosing the parameters for the Runge-Kutta method to maximize order
is hard. Consider the simplest case, the 2-stage explicit method. The general
formula is
y
n+1
= y
n
+ h(b
1
k
1
+ b
2
k
2
),
where
k
1
= f(x
n
, y
n
)
k
2
= f(x
n
+ c
2
h, y
n
+ r
2
hk
1
).
To analyse this, we insert the true solution into the method. First, we need to
insert the true solution of the ODE into the k’s. We get
k
1
= y
0
(t
n
)
k
2
= f(t
n
+ c
2
h, y(t
n
) + c
2
hy
0
(t
n
))
= y
0
(t
n
) + c
2
h
∂f
∂t
(t
n
.y(t
n
)) + ∇f(t
n
, y(t
n
))y
0
(t
n
)
+ O(h
2
)
Fortunately, we notice that the thing inside the huge brackets is just
y
00
(
t
n
). So
this is
= y
0
(t
n
) + c
2
hy
00
(t
n
) + O(h
2
).
Hence, our local truncation method for the Runge-Kutta method is
y(t
n+1
) − y(t
n
) − h(b
1
k
1
+ b
2
k
2
)
= (1 − b
1
− b
2
)hy
0
(t
n
) +
1
2
− b
2
c
2
h
2
y
00
(t
n
) + O(h
3
).
Now we see why Runge-Kutta methods are hard to analyse. The coefficients
appear non-linearly in this expression. It is still solvable in this case, in the
obvious way, but for higher stage methods, this becomes much more complicated.
In this case, we have a 1-parameter family of order 2 methods, satisfying
b
1
+ b
2
= 1, b
2
c
2
=
1
2
.
It is easy to check using a simple equation
y
0
=
λh
that it is not possible to get a
higher order method. So as long as our choice of
b
1
and
b
2
satisfy this equation,
we get a decent order 2 method.
As we have seen, Runge-Kutta methods are really complicated, even in the
simplest case. However, they have too many good properties that they are
becoming very popular nowadays.