en>Fortdj33: Clean up and spacing, added orphan tag using AWB

2012-03-16T18:23:20Z

Clean up and spacing, added orphan tag using AWB

New page

'''[[Runge–Kutta methods]]''' are methods for the numerical solution of the [[ordinary differential equation]]

:<math>\frac{d y}{d t} = f(t, y)\,</math>

which take the form

:<math>y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i\,</math>

:<math>k_i = f\left(t_n + c_i h, y_n + h \sum_{j = 1}^{s} a_{ij} k_j\right).</math>

The methods listed on this page are each defined by its [[Butcher tableau]], which puts the coefficients of the method in a table as follows:

:<math>
\begin{array}{c|cccc}
c_1 & a_{11} & a_{12}& \dots & a_{1s}\\
c_2 & a_{21} & a_{22}& \dots & a_{2s}\\
\vdots & \vdots & \vdots& \ddots& \vdots\\
c_s & a_{s1} & a_{s2}& \dots & a_{ss} \\
\hline
& b_1 & b_2 & \dots & b_s\\
\end{array}
</math>

==Explicit methods==

The explicit methods are those where the matrix <math>[a_{ij}]</math> is lower [[triangular matrix|triangular]].

===Forward Euler===

The [[Euler method]] is first order. The lack of stability and accuracy limits its popularity mainly to use as a simple introductory example of a numeric solution method.

:<math>
\begin{array}{c|c}
0 & 0 \\
\hline
& 1 \\
\end{array}
</math>

===Generic second-order method ===

:<math>
\begin{array}{c|ccc}
0 & 0 & 0 \\
x & x & 0 \\
\hline
& 1-\frac{1}{2x} & \frac{1}{2x} \\
\end{array}
</math>

===Kutta's third-order method ===

:<math>
\begin{array}{c|ccc}
0 & 0 & 0 & 0 \\
1/2 & 1/2 & 0 & 0 \\
1 & -1 & 2 & 0 \\
\hline
& 1/6 & 2/3 & 1/6 \\
\end{array}
</math>

===Classic fourth-order method===

The "original" Runge–Kutta method.

:<math>
\begin{array}{c|cccc}
0 & 0 & 0 & 0 & 0\\
1/2 & 1/2 & 0 & 0 & 0\\
1/2 & 0 & 1/2 & 0 & 0\\
1 & 0 & 0 & 1 & 0\\
\hline
& 1/6 & 1/3 & 1/3 & 1/6\\
\end{array}
</math>

===3/8-rule fourth-order method===

This method doesn't have as much notoriety as the "classical" method, but is just as classical because it was proposed in the same paper (Kutta, 1901).

:<math>
\begin{array}{c|cccc}
0 & 0 & 0 & 0 & 0\\
1/3 & 1/3 & 0 & 0 & 0\\
2/3 & -1/3 & 1 & 0 & 0\\
1 & 1 & -1 & 1 & 0\\
\hline
& 1/8 & 3/8 & 3/8 & 1/8\\
\end{array}
</math>

==Embedded methods==
The embedded methods are designed to produce an estimate of the local truncation error of a single Runge-Kutta step, and as result, allow to control the error with [[adaptive stepsize]]. This is done by having two methods in the tableau, one with order p and one with order p-1.

The lower-order step is given by

:<math> y^*_{n+1} = y_n + h\sum_{i=1}^s b^*_i k_i, </math>

where the <math>k_i</math> are the same as for the higher order method. Then the error is

:<math> e_{n+1} = y_{n+1} - y^*_{n+1} = h\sum_{i=1}^s (b_i - b^*_i) k_i, </math>

which is ''O''(''h'' ''p''). The Butcher Tableau for this kind of method is extended to give the values of <math>b^*_i</math>
:<math>
\begin{array}{c|cccc}
c_1 & a_{11} & a_{12}& \dots & a_{1s}\\
c_2 & a_{21} & a_{22}& \dots & a_{2s}\\
\vdots & \vdots & \vdots& \ddots& \vdots\\
c_s & a_{s1} & a_{s2}& \dots & a_{ss} \\
\hline
& b_1 & b_2 & \dots & b_s\\
& b_1^* & b_2^* & \dots & b_s^*\\
\end{array}
</math>

===Heun–Euler===
The simplest adaptive Runge–Kutta method involves combining the [[Heun method]], which is order 2, with the Euler method, which is order 1. Its extended Butcher Tableau is:
:<math>
\begin{array}{c|cc}
0\\
1& 1 \\
\hline
& 1/2& 1/2\\
& 1 & 0
\end{array}
</math>

The error estimate is used to control the stepsize.

===Bogacki–Shampine===

The [[Bogacki–Shampine method]] has two methods of orders 3 and 2. Its extended Butcher Tableau is:
{| cellpadding=3px cellspacing=0px
|width="20px"| || style="border-right:1px solid;" | 0
|-
||| style="border-right:1px solid;" | 1/2 || 1/2
|-
||| style="border-right:1px solid;" | 3/4 || 0 || 3/4
|-
||| style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 2/9 || style="border-bottom:1px solid;" | 1/3 || style="border-bottom:1px solid;" | 4/9 || style="border-bottom:1px solid;" |
|-
||| style="border-right:1px solid;" | || 2/9 || 1/3 || 4/9 || 0
|-
||| style="border-right:1px solid;" | || 7/24 || 1/4 || 1/3 || 1/8
|}

The first row of ''b'' coefficients gives the third-order accurate solution, and the second row has order two.

===Fehlberg===

The [[Runge–Kutta–Fehlberg method]] has two methods of orders 5 and 4. Its extended Butcher Tableau is:
{| cellpadding=3px cellspacing=0px
|width="20px"| || style="border-right:1px solid;" | 0
|-
||| style="border-right:1px solid;" | 1/4 || 1/4
|-
||| style="border-right:1px solid;" | 3/8 || 3/32 || 9/32
|-
||| style="border-right:1px solid;" | 12/13 || 1932/2197 || −7200/2197 || 7296/2197
|-
||| style="border-right:1px solid;" | 1 || 439/216 || −8 || 3680/513 || −845/4104
|-
||| style="border-right:1px solid; border-bottom:1px solid;" | 1/2 || style="border-bottom:1px solid;" | -8/27 || style="border-bottom:1px solid;" | 2 || style="border-bottom:1px solid;" | −3544/2565 || style="border-bottom:1px solid;" | 1859/4104 || style="border-bottom:1px solid;" | −11/40 || style="border-bottom:1px solid;" |
|-
||| style="border-right:1px solid;" | || 25/216 || 0 || 1408/2565 || 2197/4104 || −1/5 || 0
|-
||| style="border-right:1px solid;" | || 16/135 || 0 || 6656/12825 || 28561/56430 || −9/50 || 2/55
|}

The first row of ''b'' coefficients gives the fourth-order accurate solution, and the second row has order five.

===Cash-Karp===

Cash and Karp have modified Fehlberg's original idea. The extended tableau for the [[Cash–Karp method]] is

{| cellpadding=3px cellspacing=0px
|width="20px"| || style="border-right:1px solid;" | 0
|-
||| style="border-right:1px solid;" | 1/5 || 1/5
|-
||| style="border-right:1px solid;" | 3/10 || 3/40 || 9/40
|-
||| style="border-right:1px solid;" | 3/5 || 3/10 || −9/10 || 6/5
|-
||| style="border-right:1px solid;" | 1 || −11/54 || 5/2 || −70/27 || 35/27
|-
||| style="border-right:1px solid; border-bottom:1px solid;" | 7/8 || style="border-bottom:1px solid;" | 1631/55296 || style="border-bottom:1px solid;" | 175/512 || style="border-bottom:1px solid;" | 575/13824 || style="border-bottom:1px solid;" | 44275/110592 || style="border-bottom:1px solid;" | 253/4096 || style="border-bottom:1px solid;" |
|-
||| style="border-right:1px solid;" | || 37/378 || 0 || 250/621 || 125/594 || 0 || 512/1771
|-
||| style="border-right:1px solid;" | || 2825/27648 || 0 || 18575/48384 || 13525/55296 || 277/14336 || 1/4
|}

The first row of ''b'' coefficients gives the fifth-order accurate solution, and the second row has order four.

===Dormand–Prince===

The extended tableau for the [[Dormand–Prince method]] is

{| cellpadding=3px cellspacing=0px
|width="20px"| || style="border-right:1px solid;" | 0
|-
||| style="border-right:1px solid;" | 1/5 || 1/5
|-
||| style="border-right:1px solid;" | 3/10 || 3/40 || 9/40
|-
||| style="border-right:1px solid;" | 4/5 || 44/45 || −56/15 || 32/9
|-
||| style="border-right:1px solid;" | 8/9 || 19372/6561 || −25360/2187 || 64448/6561 || −212/729
|-
||| style="border-right:1px solid;" | 1 || 9017/3168 || −355/33 || 46732/5247 || 49/176 || −5103/18656
|-
||| style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 35/384 || style="border-bottom:1px solid;" | 0 || style="border-bottom:1px solid;" | 500/1113 || style="border-bottom:1px solid;" | 125/192 || style="border-bottom:1px solid;" | −2187/6784 || style="border-bottom:1px solid;" | 11/84 || style="border-bottom:1px solid;" |
|-
||| style="border-right:1px solid;" | || 5179/57600 || 0 || 7571/16695 || 393/640 || −92097/339200 || 187/2100 || 1/40
|-
||| style="border-right:1px solid;" | || 35/384 || 0 || 500/1113 || 125/192 || −2187/6784 || 11/84 || 0
|}

The first row of ''b'' coefficients gives the fourth-order accurate solution, and the second row has order five.

==Implicit methods==

===Backward Euler===

The [[backward Euler method]] is first order. Unconditionally stable and non-oscillatory for linear diffusion problems.

:<math>
\begin{array}{c|c}
1 & 1 \\
\hline
& 1 \\
\end{array}
</math>

===Implicit midpoint===

The implicit midpoint method is of second order. It is the simplest method in the class of collocation methods known as the Gauss methods. It is a [[symplectic integrator]].

: <math>
\begin{array}{c|c}
1/2 & 1/2 \\
\hline
& 1
\end{array}
</math>

===Lobatto methods===

There are three families of Lobatto methods, called IIIA, IIIB and IIIC. These are named after [[Rehuel Lobatto]]. All are implicit methods, have order 2''s'' − 2 and they all have ''c''<sub>1</sub> = 0 and ''c''<sub>''s''</sub> = 1. Unlike any explicit method, it's possible for these methods to have the order greater than the number of stages. Lobatto lived before the classic fourth-order method was popularized by Runge and Kutta.

====Lobatto IIIA methods====

The Lobatto IIIA methods are [[collocation method]]s. The second-order method is known as the [[trapezoidal rule (differential equations)|trapezoidal rule]]:

:<math>
\begin{array}{c|cc}
0 & 0 & 0 \\
1 & 1/2 & 1/2\\
\hline
& 1/2 & 1/2\\
\end{array}
</math>

The fourth-order method is given by

:<math>
\begin{array}{c|ccc}
0 & 0 & 0 & 0 \\
1/2 & 5/24& 1/3 & -1/24\\
1 & 1/6 & 2/3 & 1/6 \\
\hline
& 1/6 & 2/3 & 1/6 \\
\end{array}
</math>

====Lobatto IIIB methods====

The Lobatto IIIB methods are not collocation methods, but they can be viewed as [[discontinuous collocation method]]s {{harv|Hairer|Lubich|Wanner|2006|loc=§II.1.4}}. The second-order method is given by

:<math>
\begin{array}{c|cc}
0 & 1/2 & 0 \\
1 & 1/2 & 0 \\
\hline
& 1/2 & 1/2\\
\end{array}
</math>

The fourth-order method is given by

:<math>
\begin{array}{c|ccc}
0 & 1/6 & -1/6& 0 \\
1/2 & 1/6 & 1/3 & 0 \\
1 & 1/6 & 5/6 & 0 \\
\hline
& 1/6 & 2/3 & 1/6 \\
\end{array}
</math>

====Lobatto IIIC methods====

The Lobatto IIIC methods also are discontinuous collocation methods. The second-order method is given by

:<math>
\begin{array}{c|cc}
0 & 1/2 & -1/2\\
1 & 1/2 & 1/2 \\
\hline
& 1/2 & 1/2 \\
\end{array}
</math>

The fourth-order method is given by

:<math>
\begin{array}{c|ccc}
0 & 1/6 & -1/3& 1/6 \\
1/2 & 1/6 & 5/12& -1/12\\
1 & 1/6 & 2/3 & 1/6 \\
\hline
& 1/6 & 2/3 & 1/6 \\
\end{array}
</math>

==References==

* {{Citation | last1=Hairer | first1=Ernst | last2=Nørsett | first2=Syvert Paul | last3=Wanner | first3=Gerhard | title=Solving ordinary differential equations I: Nonstiff problems | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-3-540-56670-0 | year=1993}}.
* {{Citation | last1=Hairer | first1=Ernst | last2=Wanner | first2=Gerhard | title=Solving ordinary differential equations II: Stiff and differential-algebraic problems | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-3-540-60452-5 | year=1996}}.
* {{Citation | last1=Hairer | first1=Ernst | last2=Lubich | first2=Christian | last3=Wanner | first3=Gerhard | title=Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-3-540-30663-4 | year=2006}}.

{{Numerical integrators}}

{{DEFAULTSORT:List of Runge-Kutta methods}}
[[Category:Numerical differential equations]]
[[Category:Mathematics-related lists|Runge-Kutta methods]]
[[Category:Runge–Kutta methods]]

Math Girl - Revision history

en>Fortdj33: Clean up and spacing, added orphan tag using AWB