線性多步法

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

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

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

定義

常微分方程的數值方法設法找到以下初值問題的近似解 $${\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.