线性多步法

线性多步法是一种初值问题的常微分方程数值方法。在概念上，初值问题的数位方法是由初值开始，在时间上前进一小段，求解下一个点的数值。重复此步骤，直到要求解的区间都完成为止。

单步法（像欧拉方法）只用前一个点以及其微分来计算目前的值，单步法的龙格-库塔法会用前一个点以及和中间点中间的值来计算目前的值，不过在计算下一个值时，就不考虑之前的资讯。

多步法和单步法的差异是，多步法会考虑以前的资料，以提升效率。因此。多步法会参考之前的数个点以及数点微分值。线性多步法会使用之前的点和微分值的线性组合。

定义

常微分方程的数值方法设法找到以下初值问题的近似解 $${\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}.}$$

结果是在各离散时间${\displaystyle t_{i}}$下，${\displaystyle y(t)}$的近似值： $${\displaystyle y_{i}\approx y(t_{i})\quad {\text{where}}\quad t_{i}=t_{0}+ih,}$$ 其中${\displaystyle h}$是时间步长（有时会表示为${\displaystyle \Delta t}$），而${\displaystyle i}$是整数。

多步法会用以前${\displaystyle s}$步以内的资讯来计算下一个值。而线性多步法会用${\displaystyle y_{i}}$和${\displaystyle f(t_{i},y_{i})}$的线性组合，来计算${\displaystyle y}$。因此，线性多步法可以表示如下 $${\displaystyle {\begin{aligned}&y_{n+s}+a_{s-1}\cdot y_{n+s-1}+a_{s-2}\cdot y_{n+s-2}+\cdots +a_{0}\cdot y_{n}\\&\qquad {}=h\cdot \left(b_{s}\cdot f(t_{n+s},y_{n+s})+b_{s-1}\cdot f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}\cdot f(t_{n},y_{n})\right)\\&\Leftrightarrow \sum _{j=0}^{s}a_{j}y_{n+j}=h\sum _{j=0}^{s}b_{j}f(t_{n+j},y_{n+j}),\end{aligned}}}$$ 而${\displaystyle a_{s}=1}$。系数${\displaystyle a_{0},\dotsc ,a_{s-1}}$和${\displaystyle b_{0},\dotsc ,b_{s}}$决定所使用的方法。设计者一方面要找到真实解的理想近似解，另一方面也要设计方便计算的方法。为了简化计算，中许多系数会是0。

可以用系数来区分显式和隐式方法。若${\displaystyle b_{s}=0}$，此方法则为显式法，因为可以直接计算${\displaystyle y_{n+s}}$。若${\displaystyle b_{s}\neq 0}$，则${\displaystyle y_{n+s}}$的值和${\displaystyle f(t_{n+s},y_{n+s})}$有关，需设法求解方程才能得到${\displaystyle y_{n+s}}$, 此方法为隐式法。求解方程时，常会使用迭代法（例如牛顿法）求解。

有时，显式的多步法会用来“预估”${\displaystyle y_{n+s}}$的值，之后再用隐式公式中来得到“校正”后的值，这称为预估-校正方法。

例子

考虑以下问题 $${\displaystyle y'=f(t,y)=y,\quad y(0)=1.}$$ 其解是${\displaystyle y(t)=e^{t}}$。

单步欧拉法

欧拉法是一种简易的单步法： $${\displaystyle y_{n+1}=y_{n}+hf(t_{n},y_{n}).}$$ 可以将欧拉法视为是退化的显式多步法，其步数只有一步。

用此方法，配合步长${\displaystyle h={\tfrac {1}{2}}}$求解问题${\displaystyle y'=y}$，得到以下的解： $${\displaystyle {\begin{aligned}y_{1}&=y_{0}+hf(t_{0},y_{0})=1+{\tfrac {1}{2}}\cdot 1=1.5,\\y_{2}&=y_{1}+hf(t_{1},y_{1})=1.5+{\tfrac {1}{2}}\cdot 1.5=2.25,\\y_{3}&=y_{2}+hf(t_{2},y_{2})=2.25+{\tfrac {1}{2}}\cdot 2.25=3.375,\\y_{4}&=y_{3}+hf(t_{3},y_{3})=3.375+{\tfrac {1}{2}}\cdot 3.375=5.0625.\end{aligned}}}$$

二步Adams–Bashforth法

二步的Adams–Bashforth法是简单的多步法 $${\displaystyle y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).}$$ 此方法会用到二个值，${\displaystyle y_{n+1}}$和${\displaystyle y_{n}}$来计算下一个值${\displaystyle y_{n+2}}$。不过，初始问题只会有一个值${\displaystyle y_{0}=1}$。一种可能作法是用欧拉法计算${\displaystyle y_{1}}$，当作第二个值。在此选择下，Adams–Bashforth法得到结果如下（四舍五入到小数第四位）： $${\displaystyle {\begin{aligned}y_{2}&=y_{1}+{\tfrac {3}{2}}hf(t_{1},y_{1})-{\tfrac {1}{2}}hf(t_{0},y_{0})=1.5+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1=2.375,\\y_{3}&=y_{2}+{\tfrac {3}{2}}hf(t_{2},y_{2})-{\tfrac {1}{2}}hf(t_{1},y_{1})=2.375+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 1.5=3.7812,\\y_{4}&=y_{3}+{\tfrac {3}{2}}hf(t_{3},y_{3})-{\tfrac {1}{2}}hf(t_{2},y_{2})=3.7812+{\tfrac {3}{2}}\cdot {\tfrac {1}{2}}\cdot 3.7812-{\tfrac {1}{2}}\cdot {\tfrac {1}{2}}\cdot 2.375=6.0234.\end{aligned}}}$$ 在${\displaystyle t=t_{4}=2}$的解是${\displaystyle e^{2}=7.3891\ldots }$，二步的Adams–Bashforth法比欧拉法准确。一般而言，只要步长够小，二步的Adams–Bashforth法都会比欧拉法准确。

多步法分类

常用的多步法可以分为三类：Adams–Bashforth法、Adams–Moulton法及反向微分公式（英语：backward differentiation formula）（BDF）。

Adams–Bashforth法

Adams–Bashforth法是显式法，系数是${\displaystyle a_{s-1}=-1}$，${\displaystyle a_{s-2}=\cdots =a_{0}=0}$，而选择${\displaystyle b_{j}}$使此方法可以到s阶（因此在同一阶下，此方法的系数唯一）。

s = 1, 2, 3, 4, 5的Adams–Bashforth法如下，其中的第一式就是前向欧拉法：(Hairer, Nørsett & Wanner 1993，§III.1; Butcher 2003，第103页)： $${\displaystyle {\begin{aligned}y_{n+1}&=y_{n}+hf(t_{n},y_{n}),\\y_{n+2}&=y_{n+1}+h\left({\frac {3}{2}}f(t_{n+1},y_{n+1})-{\frac {1}{2}}f(t_{n},y_{n})\right),\\y_{n+3}&=y_{n+2}+h\left({\frac {23}{12}}f(t_{n+2},y_{n+2})-{\frac {16}{12}}f(t_{n+1},y_{n+1})+{\frac {5}{12}}f(t_{n},y_{n})\right),\\y_{n+4}&=y_{n+3}+h\left({\frac {55}{24}}f(t_{n+3},y_{n+3})-{\frac {59}{24}}f(t_{n+2},y_{n+2})+{\frac {37}{24}}f(t_{n+1},y_{n+1})-{\frac {9}{24}}f(t_{n},y_{n})\right),\\y_{n+5}&=y_{n+4}+h\left({\frac {1901}{720}}f(t_{n+4},y_{n+4})-{\frac {2774}{720}}f(t_{n+3},y_{n+3})+{\frac {2616}{720}}f(t_{n+2},y_{n+2})-{\frac {1274}{720}}f(t_{n+1},y_{n+1})+{\frac {251}{720}}f(t_{n},y_{n})\right).\end{aligned}}}$$

系数可以用以下方法计算。用多项式插值找到${\displaystyle s-1}$阶的多项式p使得 $${\displaystyle p(t_{n+i})=f(t_{n+i},y_{n+i}),\qquad {\text{for }}i=0,\ldots ,s-1.}$$ 多项式内插的拉格朗日插值法可以得到 $${\displaystyle p(t)=\sum _{j=0}^{s-1}{\frac {(-1)^{s-j-1}f(t_{n+j},y_{n+j})}{j!(s-j-1)!h^{s-1}}}\prod _{i=0 \atop i\neq j}^{s-1}(t-t_{n+i}).}$$ 多项式p是要求解的微分方程${\displaystyle y'=f(t,y)}$等号右边的局部好近似值，因此改为考虑方程${\displaystyle y'=p(t)}$，此方法有解析解，就是p的积分。因此得到下式 $${\displaystyle y_{n+s}=y_{n+s-1}+\int _{t_{n+s-1}}^{t_{n+s}}p(t)\,\mathrm {d} t.}$$ 当上述公式的p取代之后，就是Adams–Bashforth法。其系数${\displaystyle b_{j}}$可以由下式求得 $${\displaystyle b_{s-j-1}={\frac {(-1)^{j}}{j!(s-j-1)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s-1}(u+i)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s-1.}$$ 将${\displaystyle f(t,y)}$用内插的p取代，引进了数量级为h^s的误差，而s步的Adams–Bashforth法确实是s阶(Iserles 1996，§2.1)。

Adams–Bashforth法是由约翰·柯西·亚当斯求解毛细现象建模的微分方程而来，此微分方程出自Francis Bashforth（英语：Francis Bashforth）。Bashforth (1883)发表了他的理论以及亚当斯的数值方法(Goldstine 1977)。

Adams–Moulton法

Adams–Moulton法和Adams–Bashforth法类似，也是${\displaystyle a_{s-1}=-1}$，${\displaystyle a_{s-2}=\cdots =a_{0}=0}$，也是选择系数b到最高可能阶数。但Adams–Moulton法是隐式法。去除了${\displaystyle b_{s}=0}$的限制，s步的Adams–Moulton法可以到${\displaystyle s+1}$阶，而s步的Adams–Bashforth法只有s阶。

s = 0, 1, 2, 3, 4的Adams–Moulton法如下(Hairer, Nørsett & Wanner 1993，§III.1; Quarteroni, Sacco & Saleri 2000)，其中前两个分别是反向欧拉法和梯形法则： respectively: $${\displaystyle {\begin{aligned}y_{n}&=y_{n-1}+hf(t_{n},y_{n}),\\y_{n+1}&=y_{n}+{\frac {1}{2}}h\left(f(t_{n+1},y_{n+1})+f(t_{n},y_{n})\right),\\y_{n+2}&=y_{n+1}+h\left({\frac {5}{12}}f(t_{n+2},y_{n+2})+{\frac {8}{12}}f(t_{n+1},y_{n+1})-{\frac {1}{12}}f(t_{n},y_{n})\right),\\y_{n+3}&=y_{n+2}+h\left({\frac {9}{24}}f(t_{n+3},y_{n+3})+{\frac {19}{24}}f(t_{n+2},y_{n+2})-{\frac {5}{24}}f(t_{n+1},y_{n+1})+{\frac {1}{24}}f(t_{n},y_{n})\right),\\y_{n+4}&=y_{n+3}+h\left({\frac {251}{720}}f(t_{n+4},y_{n+4})+{\frac {646}{720}}f(t_{n+3},y_{n+3})-{\frac {264}{720}}f(t_{n+2},y_{n+2})+{\frac {106}{720}}f(t_{n+1},y_{n+1})-{\frac {19}{720}}f(t_{n},y_{n})\right).\end{aligned}}}$$

Adams–Moulton法的推导类似Adams–Bashforth法，不过，用的内插法不只用${\displaystyle t_{n-1},\dots ,t_{n-s}}$的点，也会用${\displaystyle t_{n}}$点，其系数为 $${\displaystyle b_{s-j}={\frac {(-1)^{j}}{j!(s-j)!}}\int _{0}^{1}\prod _{i=0 \atop i\neq j}^{s}(u+i-1)\,\mathrm {d} u,\qquad {\text{for }}j=0,\ldots ,s.}$$

Adams–Moulton法是由约翰·柯西·亚当斯独立完成，类似Adams–Bashforth法。福里斯特·雷·莫尔顿的名字出现在方法，是因为他发现此方法可以和Adams–Bashforth法一起使用，成为一对预估-校正方法(Moulton 1926)。Milne (1926)也有类似的想法，亚当斯是用牛顿法求解隐式方程(Hairer, Nørsett & Wanner 1993，§III.1)。

反向微分公式（BDF）

反向微分公式是${\displaystyle b_{s-1}=\cdots =b_{0}=0}$的隐式法，选择其他系数使阶数可以到s阶（最大可能阶数）。此方法特别用来求得刚性方程。

相关条目

• 数位能量增益（英语：Digital energy gain）

参考资料

• Bashforth, Francis, An Attempt to test the Theories of Capillary Action by comparing the theoretical and measured forms of drops of fluid. With an explanation of the method of integration employed in constructing the tables which give the theoretical forms of such drops, by J. C. Adams, Cambridge, 1883.
• Butcher, John C., Numerical Methods for Ordinary Differential Equations, John Wiley, 2003, ISBN 978-0-471-96758-3.
• Dahlquist, Germund, Convergence and stability in the numerical integration of ordinary differential equations, Mathematica Scandinavica, 1956, 4: 33–53, doi:10.7146/math.scand.a-10454 .
• Dahlquist, Germund, A special stability problem for linear multistep methods, BIT, 1963, 3: 27–43, ISSN 0006-3835, S2CID 120241743, doi:10.1007/BF01963532.
• Goldstine, Herman H., A History of Numerical Analysis from the 16th through the 19th Century, New York: Springer-Verlag, 1977, ISBN 978-0-387-90277-7.
• Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard, Solving ordinary differential equations I: Nonstiff problems 2nd, Berlin: Springer Verlag, 1993, ISBN 978-3-540-56670-0.
• Hairer, Ernst; Wanner, Gerhard, Solving ordinary differential equations II: Stiff and differential-algebraic problems 2nd, Berlin, New York: Springer-Verlag, 1996, ISBN 978-3-540-60452-5.
• Iserles, Arieh, A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, 1996, Bibcode:1996fcna.book.....I, ISBN 978-0-521-55655-2.
• Milne, W. E., Numerical integration of ordinary differential equations, American Mathematical Monthly (Mathematical Association of America), 1926, 33 (9): 455–460, JSTOR 2299609, doi:10.2307/2299609.
• Moulton, Forest R., New methods in exterior ballistics, University of Chicago Press, 1926.
• Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto, Matematica Numerica, Springer Verlag, 2000, ISBN 978-88-470-0077-3.
• Süli, Endre; Mayers, David, An Introduction to Numerical Analysis, Cambridge University Press, 2003, ISBN 0-521-00794-1.

外部链接

• 埃里克·韦斯坦因. Adams Method. MathWorld.