Runge-Kutta methods

Although Euler integration is efficient and easy to understand, it generally yields poor approximations. Taking a Taylor series expansion of $ {\tilde{x}}$ at $ t=0$ yields

$\displaystyle x(\Delta t) = x(0) + \Delta t \; {\dot x}(0) + \frac{(\Delta t)^2}{2!} {\ddot x}(0) + \frac{(\Delta t)^3}{3!} x^{(3)}(0) + \cdots .$ (14.17)

Comparing to (14.16), it can be seen that the Euler method just uses the first term of the Taylor series, which is an exact representation (if $ {\tilde{x}}$ is analytic). Thus, the neglected terms reflect the approximation error. If $ x(t)$ is roughly linear, then the error may be small; however, if $ {\dot x}(t)$ or higher order derivatives change quickly, then poor approximations are obtained.

Runge-Kutta methods are based on using higher order terms of the Taylor series expansion. One of the most widely used and efficient numerical integration methods is the fourth-order Runge-Kutta method. It is simple to implement and yields good numerical behavior in most applications. Also, it is generally recommended over Euler integration. The technique can be derived by performing a Taylor series expansion at $ x(\frac{1}{2}\Delta t)$. This state itself is estimated in the approximation process.

The fourth-order Runge-Kutta integration method is

$\displaystyle x(\Delta t) \approx x(0) + \frac{\Delta t}{6} (w_1 + 2 w_2 + 2 w_3 + w_4) ,$ (14.18)

in which

\begin{displaymath}\begin{split}w_1 & = f(x(0),u(0))  w_2 & = f(x(0)+ \begin{m...
...  w_4 & = f(x(0)+\Delta t \; w_3,\;u(\Delta t)) . \end{split}\end{displaymath} (14.19)

Although this is more expensive than Euler integration, the improved accuracy is usually worthwhile in practice. Note that the action is needed at three different times: 0, $ \frac{1}{2}\Delta t$, and $ \Delta t$. If the action is constant over $ [0,\Delta t)$, then the same value is used at all three times.

The approximation error depends on how quickly higher order derivatives of $ {\tilde{x}}$ vary over time. This can be expressed using the remaining terms of the Taylor series. In practice, it may be advantageous to adapt $ \Delta t$ over successive iterations of Runge-Kutta integration. In [247], for example, it is suggested that $ \Delta t$ is scaled by $ (\Delta t / \Delta x)^{1/5}$, in which $ \Delta x = \Vert x(\Delta t) - x(0)\Vert$, the Euclidean distance in $ {\mathbb{R}}^n$.

Steven M LaValle 2012-04-20