21. Runge-Kutta法

数值分析



周维祺

基本思想

y(tn+1)=ytn+∫tntn+1f(t,y(t))dt=ytn+h∫01f(tn+hx,y(tn+hx))dxy(t_{n+1})=y_{t_n}+\int_{t_n}^{t_{n+1}}f(t,y(t))dt=y_{t_n}+h\int_{0}^{1}f(t_n+hx,y(t_n+hx))dx

∫01f(tn+hx,y(tn+hx))dx≈∑j=0vbjf(tn+cjh,y(tn+cjh))⏟数值积分\int_{0}^{1}f(t_n+hx,y(t_n+hx))dx\approx \underbrace{\sum_{j=0}^vb_jf(t_n+c_jh, y(t_n+c_jh))}_{数值积分}

节点计算

  • 令κj\kappa_j为对y(tn+cjh)y(t_n+c_jh)的估计，并令c1=0c_1=0，从而κ1=yn\kappa_1=y_n

  • κk=yn+h∑i=1vak,if(tn+cih,κi)\kappa_k=y_n+h\sum\limits_{i=1}^va_{k,i}f(t_n+c_ih,\kappa_i)

  • bjb_j: 权值；cjc_j: 节点；[ak,i]k,i[a_{k,i}]_{k,i}：Runge-Kutta系数矩阵; v:步数v: 步数

Butcher表

Butcher表

  • c⃗=(c1⋮cv)\vec c=\begin{pmatrix}c_1 \\ \vdots \\ c_v \end{pmatrix}，b⃗T=(b1…bv)\vec b^T=\begin{pmatrix}b_1 & \ldots & b_v \end{pmatrix}， A=(a1,1…a1,v⋮⋱⋮av,1…av,v)A=\begin{pmatrix} a_{1,1} & \ldots & a_{1,v} \\ \vdots & \ddots & \vdots \\ a_{v,1} & \ldots & a_{v,v} \\ \end{pmatrix}

  • Butcher表可以写成 c⃗Ab⃗T\begin{array}{c|c} \vec c & A \\ \hline & \vec b^T \\ \end{array}

显式和隐式

  • 显式：AA是严格下三角阵（主对角线也为00）

  • 隐式：AA不是严格下三角阵

  • 显式法一般还要求ci=∑j=1i−1ai,jc_i=\sum\limits_{j=1}^{i-1}a_{i,j}

例子

  • 欧拉法（1阶）： 001\begin{array}{c|c} 0 & 0 \\ \hline & 1\\ \end{array}

  • 中点法（2阶）： 0001/21/2001\begin{array}{c|cc} 0 & 0 & 0 \\ 1/2 & 1/2 & 0 \\ \hline & 0 & 1\\ \end{array}

一些二阶方法

  • 0002/32/301/43/4,\begin{array}{c|cc} 0 & 0 & 0 \\ 2/3 & 2/3 & 0 \\ \hline & 1/4 & 3/4\\ \end{array},\quad\quad0001101/21/2\begin{array}{c|cc} 0 & 0 & 0 \\ 1 & 1 & 0 \\ \hline & 1/2 & 1/2\\ \end{array}

  • 若v=2,b1+b2=1,b2c2=1/2,a21=c2,c1=0v=2, b_1+b_2=1, b_2c_2=1/2, a_{21}=c_2, c_1=0，则显式法具有至少2阶局部截断误差

一些三阶方法

  • 经典法： 00001/21/2001−1201/62/31/6\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}

  • Nystro¨mNystr{\"o}m法：00002/32/3002/302/301/43/83/8\begin{array}{c|ccc} 0 & 0 & 0 & 0 \\ 2/3 & 2/3 & 0 & 0 \\ 2/3 & 0 & 2/3 & 0 \\ \hline & 1/4 & 3/8 & 3/8 \end{array}

一种四阶方法

000001/21/20001/201/200100101/61/31/31/6\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}

显式法的一些结论

步数 可能的最高局部截断误差
v=1,2,3,4v=1,2,3,4 vv阶
v=5,6,7v=5,6,7 v−1v-1阶
v=8v=8 66阶
v=9,10v=9,10 77阶
v=11v=11 88阶

p≥8p\ge8时，至少需要p+3p+3步才能达到p阶，存在1717及1818步的1010阶方法

拓展阅读

  • 隐式法

  • 系数的设计：Collocation法

小结

  • Runge-Kutta法的基本思想和计算公式

  • Butcher表和对系数的一般要求

  • 显式法的步数与其截断误差的关系

  • 两步显式法具有22阶截断误差的条件