Runge–Kutta methods 213671 222986105 2008-07-02T01:26:44Z Numsgil 444294 [[WP:UNDO|Undid]] revision 222966403 by [[Special:Contributions/66.199.74.34|66.199.74.34]] ([[User talk:66.199.74.34|talk]]) In [[numerical analysis]], the '''Runge–Kutta methods''' are an important family of implicit and explicit iterative methods for the approximation of solutions of [[ordinary differential equation]]s. These techniques were developed around 1900 by the German mathematicians [[Carl David Tolmé Runge|C. Runge]] and [[Martin Wilhelm Kutta|M.W. Kutta]]. See the article on [[numerical ordinary differential equations]] for more background and other methods. See also [[List of Runge-Kutta methods]]. ==The classical fourth-order Runge–Kutta method== One member of the family of Runge–Kutta methods is so commonly used that it is often referred to as "RK4" or simply as "''the'' Runge–Kutta method". Let an [[initial value problem]] be specified as follows. :<math> y' = f(t, y), \quad y(t_0) = y_0. </math> Then, the RK4 method for this problem is given by the following equations: :<math>\begin{align} y_{n+1} &= y_n + {h \over 6} \left(k_1 + 2k_2 + 2k_3 + k_4 \right) \\ t_{n+1} &= t_n + h \\ \end{align}</math> where <math> y_{n+1}</math> is the RK4 approximation of <math> y(t_{n+1}) </math>, and :<math>\begin{align} k_1 &= f \left( t_n, y_n \right) \\ k_2 &= f \left( t_n + {h \over 2}, y_n + {h \over 2} k_1\right) \\ k_3 &= f \left( t_n + {h \over 2}, y_n + {h \over 2} k_2\right) \\ k_4 &= f \left( t_n + h, y_n + h k_3 \right) \\ \end{align}</math> Thus, the next value (''y''<sub>''n''+1</sub>) is determined by the present value (''y''<sub>''n''</sub>) plus the product of the size of the interval (''h'') and an estimated [[slope]]. The slope is a [[weighted average]] of slopes: *''k''<sub>1</sub> is the slope at the beginning of the interval; *''k''<sub>2</sub> is the slope at the midpoint of the interval, using slope ''k''<sub>1</sub> to determine the value of ''y'' at the point ''t''<sub>''n''</sub> + ''h''/2 using [[Euler's method]]; *''k''<sub>3</sub> is again the slope at the midpoint, but now using the slope ''k''<sub>2</sub> to determine the ''y''-value; *''k''<sub>4</sub> is the slope at the end of the interval, with its ''y''-value determined using ''k''<sub>3</sub>. In averaging the four slopes, greater weight is given to the slopes at the midpoint: :<math>\mbox{slope} = \frac{k_1 + 2k_2 + 2k_3 + k_4}{6}.</math> The RK4 method is a fourth-order method, meaning that the error per step is [[Big O notation|on the order of]] ''h''<sup>5</sup>, while the total accumulated error has order ''h''<sup>4</sup>. Note that the above formulas are valid for both scalar- and vector-valued functions (i.e., ''y'' can be a vector and <math> f </math> an operator). For example one can integrate [[Schrödinger's equation]] using the Hamiltonian operator as function <math> f </math>. == Explicit Runge–Kutta methods == The family of [[Explicit and implicit methods|explicit]] Runge–Kutta methods is a generalization of the RK4 method mentioned above. It is given by :<math> y_{n+1} = y_n + h\sum_{i=1}^s b_i k_i, </math> where :<math> k_1 = f(t_n, y_n), \, </math> :<math> k_2 = f(t_n+c_2h, y_n+a_{21}hk_1), \, </math> :<math> k_3 = f(t_n+c_3h, y_n+a_{31}hk_1+a_{32}hk_2), \, </math> :::<math> \vdots </math> :<math> k_s = f(t_n+c_sh, y_n+a_{s1}hk_1+a_{s2}hk_2+\cdots+a_{s,s-1}hk_{s-1}). </math> :''(Note: the above equations have different but equivalent definitions in different texts).'' To specify a particular method, one needs to provide the integer ''s'' (the number of stages), and the coefficients ''a''<sub>''ij''</sub> (for 1 &le; ''j'' < ''i'' &le; ''s''), ''b''<sub>''i''</sub> (for ''i'' = 1, 2, ..., ''s'') and ''c''<sub>''i''</sub> (for ''i'' = 2, 3, ..., ''s''). These data are usually arranged in a mnemonic device, known as a ''Butcher tableau'' (after [[John C. Butcher]]): {| cellpadding=3px cellspacing=0px |width="20px"| || style="border-right:1px solid;" | 0 |- ||| style="border-right:1px solid;" | <math> c_2 </math> || <math> a_{21} </math> |- ||| style="border-right:1px solid;" | <math> c_3 </math> || <math> a_{31} </math> || <math> a_{32} </math> |- ||| style="border-right:1px solid;" | <math> \vdots </math> || <math> \vdots </math> || || <math> \ddots </math> |- ||| style="border-right:1px solid; border-bottom:1px solid;" | <math> c_s </math> | style="border-bottom:1px solid;" | <math> a_{s1} </math> | style="border-bottom:1px solid;" | <math> a_{s2} </math> | style="border-bottom:1px solid;" | <math> \cdots </math> | style="border-bottom:1px solid;" | <math> a_{s,s-1} </math> || style="border-bottom:1px solid;" | |- ||| style="border-right:1px solid;" | || <math> b_1 </math> || <math> b_2 </math> || <math> \cdots </math> || <math> b_{s-1} </math> || <math> b_s </math> |} The Runge–Kutta method is consistent if :<math>\sum_{j=1}^{i-1} a_{ij} = c_i\ \mathrm{for}\ i=2, \ldots, s.</math> There are also accompanying requirements if we require the method to have a certain order ''p'', meaning that the truncation error is O(''h''<sup>''p''+1</sup>). These can be derived from the definition of the truncation error itself. For example, a 2-stage method has order 2 if ''b''<sub>1</sub> + ''b''<sub>2</sub> = 1, ''b''<sub>2</sub>''c''<sub>2</sub> = 1/2, and ''b''<sub>2</sub>''a''<sub>21</sub> = 1/2. ===Examples=== The RK4 method falls in this framework. Its 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;" | 1/2 || 0 || 1/2 |- ||| style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 0 | style="border-bottom:1px solid;" | 0 || style="border-bottom:1px solid;" | 1 | style="border-bottom:1px solid;" | |- ||| style="border-right:1px solid;" | || 1/6 || 1/3 || 1/3 || 1/6 |} However, the simplest Runge–Kutta method is the (forward) [[Euler integration|Euler method]], given by the formula <math> y_{n+1} = y_n + hf(t_n,y_n) </math>. This is the only consistent explicit Runge–Kutta method with one stage. The corresponding tableau is: {| cellpadding=3px cellspacing=0px | width="20px" | || style="border-right:1px solid; border-bottom:1px solid;" width="10px" | 0 | style="border-bottom:1px solid;" width="10px" | |- ||| style="border-right:1px solid;" | || 1 |} An example of a second-order method with two stages is provided by the [[midpoint method]] :<math> y_{n+1} = y_n + hf\left(t_n+\frac{h}{2},y_n+\frac{h}{2}f(t_n, y_n)\right). </math> The corresponding tableau is: {| cellpadding=3px cellspacing=0px |width="20px"| || style="border-right:1px solid;" | 0 |- ||| style="border-right:1px solid; border-bottom:1px solid;" | 1/2 || style="border-bottom:1px solid;" | 1/2 | style="border-bottom:1px solid;" | |- ||| style="border-right:1px solid;" | || 0 || 1 |} <!-- for implicit method :<math>\begin{matrix} c_1 & | & a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\ c_2 & | & a_{21} & a_{22} & a_{23} & \cdots & a_{nn} \\ \vdots & | & \vdots & \vdots & \vdots & \ddots & \vdots \\ c_n & | & a_{n1} & a_{n2} & a_{23} & \cdots & a_{nn} \\ & & --- & --- & --- & --- & --- \\ & & b_1 & b_2 & b_3 & b_4 & b_5 \end{matrix}</math> --> Note that this 'midpoint' method is not the optimal RK2 method. An alternative is provided by [[Heun's method]], where the 1/2's in the tableau above are replaced by 1's and the b's row is [1/2, 1/2]. If one wants to minimize the truncation error, the method below should be used (Atkinson p. 423). Other important methods are [[Runge–Kutta–Fehlberg method|Fehlberg]], [[Cash-Karp]] and [[Dormand-Prince]]. Also, read the article on [[Adaptive Stepsize]]. ==Usage== The following is an example usage of a two-stage explicit Runge–Kutta method: {| cellpadding=3px cellspacing=0px |width="20px"| || style="border-right:1px solid;" | 0 |- ||| style="border-right:1px solid; border-bottom:1px solid;" | 2/3 || style="border-bottom:1px solid;" | 2/3 | style="border-bottom:1px solid;" | |- ||| style="border-right:1px solid;" | || 1/4 || 3/4 |} to solve the initial-value problem :<math> y' = (\tan{y})+1,\quad y(1)=1,\ t\in [1, 1.1]</math> with step size ''h''=0.025. The tableau above yields the equivalent corresponding equations below defining the method: :<math> k_1 = y_n \,</math> :<math> k_2 = y_n + 2/3hf(t_n, k_1) \,</math> :<math> y_{n+1} = y_n + h(1/4f(t_n,k_1)+3/4f(t_n+2/3h,k_2))\,</math> {| cellpadding=8px |- | <math>t_0=1</math> || || |- | || <math>y_0=1</math> |- | <math>t_1=1.025</math> |- | || <math>k_1 = y_0 = 1</math> || <math>f(t_0,k_1)=2.557407725</math> || <math>k_2 = y_0 + 2/3hf(t_0,k_1) = 1.042623462</math> |- | || colspan=3 style="border-bottom:1px solid;"|<math>y_1=y_0+h(1/4*f(t_0, k_1) + 3/4*f(t_0+2/3h,k_2))=1.066869388</math> |- | <math>t_2=1.05</math> |- | || <math>k_1 = y_1 = 1.066869388</math> || <math>f(t_1,k_1)=2.813524695</math> || <math>k_2 = y_1 + 2/3hf(t_1,k_1) = 1.113761467</math> |- | || colspan=3 style="border-bottom:1px solid;"| <math>y_2=y_1+h(1/4*f(t_1, k_1) + 3/4*f(t_1+2/3h,k_2))=1.141332181</math> |- | <math>t_3=1.075</math> |- | || <math>k_1 = y_2 = 1.141332181</math> || <math>f(t_2,k_1)=3.183536647</math> || <math>k_2 = y_2 + 2/3hf(t_2,k_1) = 1.194391125</math> |- | || colspan=3 style="border-bottom:1px solid;"| <math>y_3=y_2+h(1/4*f(t_2, k_1) + 3/4*f(t_2+2/3h,k_2))=1.227417567</math> |- | <math>t_4=1.1</math> |- | || <math>k_1 = y_3 = 1.227417567 </math> || <math>f(t_3,k_1)=3.796866512</math> || <math>k_2 = y_3 + 2/3hf(t_3,k_1) = 1.290698676</math> |- | || colspan=3 style="border-bottom:1px solid;"| <math>y_4=y_3+h(1/4*f(t_3, k_1) + 3/4*f(t_3+2/3h,k_2))=1.335079087</math> |} The numerical solutions correspond to the underlined values. Note that <math>f(t_i,k_1)</math> has been calculated to avoid recalculation in the <math>y_i</math>s. ==Adaptive Runge-Kutta methods== The adaptive methods are designed to produce an estimate of the local truncation error of a single Runge-Kutta step. This is done by having two methods in the tableau, one with order <math>p</math> and one with order <math>p - 1</math>. 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 <math>O(h^p)</math>. The Butcher Tableau for this kind of method is extended to give the values of <math>b^*_i</math>: {| cellpadding=3px cellspacing=0px |width="20px"| || style="border-right:1px solid;" | 0 |- ||| style="border-right:1px solid;" | <math> c_2 </math> || <math> a_{21} </math> |- ||| style="border-right:1px solid;" | <math> c_3 </math> || <math> a_{31} </math> || <math> a_{32} </math> |- ||| style="border-right:1px solid;" | <math> \vdots </math> || <math> \vdots </math> || || <math> \ddots </math> |- ||| style="border-right:1px solid; border-bottom:1px solid;" | <math> c_s </math> | style="border-bottom:1px solid;" | <math> a_{s1} </math> | style="border-bottom:1px solid;" | <math> a_{s2} </math> | style="border-bottom:1px solid;" | <math> \cdots </math> | style="border-bottom:1px solid;" | <math> a_{s,s-1} </math> || style="border-bottom:1px solid;" | |- ||| style="border-right:1px solid;" | || <math> b_1 </math> || <math> b_2 </math> || <math> \cdots </math> || <math> b_{s-1} </math> || <math> b_s </math> |- ||| style="border-right:1px solid;" | || <math> b^*_1 </math> || <math> b^*_2 </math> || <math> \cdots </math> || <math> b^*_{s-1} </math> || <math> b^*_s </math> |} 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;" | || 16/135 || 0 || 6656/12825 || 28561/56430 || −9/50 || 2/55 |- ||| style="border-right:1px solid;" | || 25/216 || 0 || 1408/2565 || 2197/4104 || −1/5 || 0 |} However, 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: {| cellpadding=3px cellspacing=0px |width="20px"| || style="border-right:1px solid;" | 0 |- ||| style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | |- ||| style="border-right:1px solid;" | || 1/2 || 1/2 |- ||| style="border-right:1px solid;" | || 1 || 0 |} The error estimate is used to control the stepsize. ==Implicit Runge-Kutta methods== The implicit methods are more general than the explicit ones. The distinction shows up in the Butcher Tableau: for an implicit method, the coefficient matrix <math>a_{ij}</math> is not necessarily lower triangular: :<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} = \begin{array}{c|c} \mathbf{c}& A\\ \hline & \mathbf{b^T} \\ \end{array} </math> The approximate solution to the initial value problem reflects the greater number of coefficients: :<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> Due to the fullness of the matrix <math>a_{ij}</math>, the evaluation of each <math>k_i</math> is now considerably involved and dependent on the specific function <math>f(t, y)</math>. Despite the difficulties, implicit methods are of great importance due to their high (possibly unconditional) stability, which is especially important in the solution of [[Numerical partial differential equations|partial differential equations]]. The simplest example of an implicit Runge-Kutta method is the backward Euler method: :<math>y_{n + 1} = y_n + h f(t_n + h, y_{n + 1})\,</math> The Butcher Tableau for this is simply: :<math> \begin{array}{c|c} 1 & 1 \\ \hline & 1 \\ \end{array} </math> It can be difficult to make sense of even this simple implicit method, as seen from the expression for <math>k_1</math>: :<math>k_1 = f(t_n + c_1 h, y_n + h a_{11} k_1) \rightarrow k_1 = f(t_n + h, y_n + h k_1).</math> In this case, the awkward expression above can be simplified by noting that :<math>y_{n+1} = y_n + h k_1 \rightarrow h k_1 = y_{n+1} - y_n\,</math> so that :<math>k_1 = f(t_n + h, y_n + y_{n+1} - y_n) = f(t_n + h, y_{n+1}).\,</math> from which :<math>y_{n + 1} = y_n + h f(t_n + h, y_{n + 1})\,</math> follows. Though simpler then the "raw" representation before manipulation, this is an implicit relation so that the actual solution is problem dependent. Multistep implicit methods have been used with success by some researchers. The combination of stability, higher order accuracy with fewer steps, and stepping that depends only on the previous value makes them attractive; however the complicated problem-specific implementation and the fact that <math>k_i</math> must often be approximated iteratively means that they are not common. ==References== *J. C. Butcher, ''Numerical methods for ordinary differential equations'', ISBN 0471967580 * George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. ''Computer Methods for Mathematical Computations''. Englewood Cliffs, NJ: Prentice-Hall, 1977. ''(See Chapter 6.)'' * Ernst Hairer, Syvert Paul Nørsett, and Gerhard Wanner. ''Solving ordinary differential equations I: Nonstiff problems'', second edition. Berlin: Springer Verlag, 1993. ISBN 3-540-56670-8. * William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. ''[[Numerical Recipes|Numerical Recipes in C]]''. Cambridge, UK: Cambridge University Press, 1988. ''(See Sections 16.1 and 16.2.)'' * [http://numericalmethods.eng.usf.edu/topics/runge_kutta_4th_method.html Runge-Kutta 4th-order method textbook notes, PPT, Matlab Mathematica Maple Mathcad] at [http://numericalmethods.eng.usf.edu Holistic Numerical Methods Institute] * Kendall E. Atkinson. ''An Introduction to Numerical Analysis''. John Wiley & Sons - 1989 * F. Cellier, E. Kofman. ''Continuous System Simulation''. Springer Verlag, 2006. ISBN 0-387-26102-8. ==External links== *[http://www.krellinst.org/UCES/archive/modules/diffeq/node10.html Runge-Kutta] *[http://numericalmethods.eng.usf.edu/ebooks/runge4th_08ode_ebook.pdf Runge-Kutta 4th Order Method] *[http://math.fullerton.edu/mathews/n2003/RungeKuttaMod.html Runge Kutta Method for O.D.E.'s] {{Numerical integrators}} [[Category:Numerical differential equations]] [[Category:Runge–Kutta methods]] [[de:Runge-Kutta-Verfahren]] [[es:Método de Runge-Kutta]] [[fa:روش‌های رونگه‐کوتا]] [[fr:Méthodes de Runge-Kutta]] [[it:Metodi di Runge-Kutta]] [[nl:Runge-Kuttamethode]] [[ja:ルンゲ=クッタ法]] [[pl:Algorytm Rungego-Kutty]] [[pt:Método de Runge-Kutta]] [[ru:Метод Рунге — Кутты]] [[sr:Метода Рунге-Кута]] [[sv:Runge-Kuttametoden]] [[tr:Runge-Kutta Yöntemleri]] [[uk:Метод Рунге-Кутта]] [[zh:龙格-库塔法]]