線性多步法

線性多步法是一種初值問題的常微分方程数值方法。在概念上，初值問題的數位方法是由初值開始，在時間上前進一小段，求解下一個點的數值。重覆此步驟，直到要求解的區間都完成為止。

單步法（像欧拉方法）只用前一個點以及其微分來計算目前的值，單步法的龙格-库塔法會用前一個點以及和中間點中間的值來計算目前的值，不過在計算下一個值時，就不考慮之前的資訊。

多步法和單步法的差異是，多步法會考慮以前的資料，以提昇效率。因此。多步法會參考之前的數個點以及數點微分值。線性多步法會使用之前的點和微分值的线性组合。

定義

常微分方程的數值方法設法找到以下初值問題的近似解 $$y'=f(t,y),\quad y(t_{0})=y_{0}.$$

結果是在各離散時間$t_{i}$下，$y(t)$的近似值： $$y_{i}\approx y(t_{i})\quad {\text{where}}\quad t_{i}=t_{0}+ih,$$ 其中$h$是時間步長（有時會表示為$\Delta t$），而$i$是整數。

多步法會用以前$s$步以內的資訊來計算下一個值。而線性多步法會用$y_{i}$和$f(t_{i},y_{i})$的線性組合，來計算$y$。因此，線性多步法可以表示如下 $${\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}}$$ 而$a_{s}=1$。係數$a_{0},\dotsc ,a_{s-1}$和$b_{0},\dotsc ,b_{s}$決定所使用的方法。設計者一方面要找到真實解的理想近似解，另一方面也要設計方便計算的方法。為了簡化計算，中許多係數會是0。

可以用係數來區分顯式和隱式方法。若$b_{s}=0$，此方法則為顯式法，因為可以直接計算$y_{n+s}$。若$b_{s}\neq 0$，則$y_{n+s}$的值和$f(t_{n+s},y_{n+s})$有關，需設法求解方程才能得到$y_{n+s}$, 此方法為隱式法。求解方程時，常會使用迭代法（例如牛顿法）求解。

有時，顯式的多步法會用來「預估」$y_{n+s}$的值，之後再用隱式公式中來得到「校正」後的值，這稱為预估-校正方法。

例子

考慮以下問題 $$y'=f(t,y)=y,\quad y(0)=1.$$ 其解是$y(t)=e^{t}$。

單步歐拉法

歐拉法是一種簡易的單步法： $$y_{n+1}=y_{n}+hf(t_{n},y_{n}).$$ 可以將歐拉法視為是退化的顯式多步法，其步數只有一步。

用此方法，配合步長$h={\tfrac {1}{2}}$求解問題$y'=y$，得到以下的解： $${\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法是簡單的多步法 $$y_{n+2}=y_{n+1}+{\tfrac {3}{2}}hf(t_{n+1},y_{n+1})-{\tfrac {1}{2}}hf(t_{n},y_{n}).$$ 此方法會用到二個值，$y_{n+1}$和$y_{n}$來計算下一個值$y_{n+2}$。不過，初始問題只會有一個值$y_{0}=1$。一種可能作法是用歐拉法計算$y_{1}$，當作第二個值。在此選擇下，Adams–Bashforth法得到結果如下（四捨五入到小數第四位）： $${\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}}$$ 在$t=t_{4}=2$的解是$e^{2}=7.3891\ldots$，二步的Adams–Bashforth法比歐拉法準確。一般而言，只要步長夠小，二步的Adams–Bashforth法都會比歐拉法準確。

相關條目

• 數位能量增益

參考資料

• 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.