重用過往的導數值
單步方法由 yn 出發前進,只使用當前步所產生的資訊;多步方法則同時保留較早的數值。對於微分方程 y′=f(t,y):
定義 8.2.1
(二步 Adams–Bashforth 方法)
二步 Adams–Bashforth 方法(AB2)為
yn+1=yn+h(23f(tn,yn)−21f(tn−1,yn−1)),tn=t0+nh.
它需要兩個起步值 y0,y1。一旦有了起步值,只要儲存前一個值,每步只需計算一次新的 f。負係數並不表示時間倒流:它來自把導數外推到下一個區間。
推導與局部缺陷
設 g(t)=f(t,y(t))=y′(t),沿足夠光滑的精確解取值。在 tn−1 與 tn 對 g 作線性插值:
P(tn+s)=g(tn)+hs(g(tn)−g(tn−1)),0≤s≤h.
把 P 由 0 積分到 h,得 h(3g(tn)/2−g(tn−1)/2),這正是 AB2 的增量。
未縮放局部缺陷是從精確解出發走一步所產生的誤差:
dn+1=y(tn+1)−y(tn)−h(23g(tn)−21g(tn−1)).
若 g 的二階導數有界,則缺陷 dn+1 在固定區間上一致為 O(h3)。若 g 局部屬於 C2,則 dn+1=(5/12)h3g′′(tn)+o(h3)。
事實上,把 g(tn+s) 和 g(tn−h) 展開到二階並比較其積分:含 g(tn) 與 g′(tn) 的項相消,二階項留下 (61+41)h3g′′(tn)=125h3g′′(tn)。
常見錯誤
(局部截斷誤差與未縮放缺陷相差一個 h 的次冪)
有些書把缺陷除以 h,稱之為局部截斷誤差;依該約定其階為 O(h2),而這裏使用的缺陷為 O(h3)。引用任何一個指數而不說明約定,就會對階數產生常見的相差一階的分歧。
取 y′=y、y(0)=1、h=0.1,以及精確的起步值 y0=1、y1=e0.1≈1.1051709。則 y2=y1+0.1(1.5y1−0.5y0)=1.1051709+0.1(1.1577564)≈1.2209465。精確值為 e0.2≈1.2214028,誤差約為 4.56×10−4。由於起步值是精確的,這個誤差就是缺陷,而首項預測 (5/12)h3e0.1≈4.60×10−4,相差約百分之一以內。
由缺陷到全局誤差
僅有局部精度,並不能說明反覆迭代後仍然準確。下面的初等論證證明這個特定方法的收斂性。
假設 f 對所有狀態值及 t∈[t0,T] 在第二個變量上滿足全局 Lipschitz 條件,常數為 L,且精確解在直至固定終止時間 T 的範圍內具有一致的缺陷界 ∣dn+1∣≤Ch3。若 ∣y0−y(t0)∣+∣y1−y(t1)∣≤C0h2,則當 h↓0 時,AB2 的數值滿足 tn≤Tmax∣yn−y(tn)∣=O(h2)。
記 en=yn−y(tn),並對 n≥1 記 En=max(∣en∣,∣en−1∣)。將精確遞推式與數值遞推式相減。Lipschitz 連續性和缺陷界給出
∣en+1∣≤∣en∣+hL(23∣en∣+21∣en−1∣)+Ch3≤(1+2Lh)En+Ch3.同一個上界也控制 ∣en∣,所以 En+1≤(1+2Lh)En+Ch3。迭代至多 (T−t0)/h 步,乘積以 e2L(T−t0) 為界,累積缺陷以常數乘以 h2 為界。由於 E1=O(h2),結論成立。同一證明對向量值方程組也適用,只需相應的範數與 Lipschitz 常數。
證明透視
起步值是算法的一部分
遞推式涉及前兩個誤差,所以證明追蹤最近兩個誤差的最大值 En;這把雙項遞推化為單項不等式,Lipschitz 常數 3L/2 與 L/2 相加成 2L。每一步都產生 O(h3) 的缺陷,固定區間上共有 O(1/h) 步,這損失一個 h 的次冪。乘積 (1+2Lh)n≤e2L(T−t0) 保持有界,所以誤差遞推式的穩定性使放大效應不會破壞所得的 O(h2) 界。起步誤差只透過 E1 進入,並被同一個有界常數放大:起步誤差若只有 O(h),即使之後每一步 AB2 都精確計算,也不在這個二階定理的涵蓋範圍之內。
例題 8.2.6
(以 Euler 方法作起步值處理指數增長)
對 y′=y、y(0)=1、h=0.1,取一步顯式 Euler 所得的起步值 y1=1+h=1.1;其誤差為 e0.1−1.1≈0.0052,屬於 O(h2)。則 y2=1.1+0.1(1.65−0.5)=1.215,與 e0.2≈1.2214 相比誤差約為 0.0064。這比上一例由精確起步值得到的誤差 4.56×10−4 大十倍以上:二階起步值足以使 h→0 時保持二階收斂,但在固定步長下,它的誤差會主導常數。
試驗方程上的絕對穩定性
把方法應用於 y′=λy,並令 z=hλ。試探解 yn=ξn 給出
ξ2−(1+23z)ξ+21z=0.
定義 8.2.7
(AB2 在給定 z 處的絕對穩定性)
對固定的 z,絕對穩定性要求對任意起步值對,數值解都衰減;等價地,上面多項式的兩個根的模長都嚴格小於一。
重根還會產生因子 n,但只要模長小於一,仍然衰減。在 z=0 處,兩根為 1 和 0,所以數值解保持有界但不衰減。這個邊界情形稱為零穩定行為,而不是嚴格的絕對穩定。
對實數 z<0,AB2 穩定多項式的兩個根都位於 (−1,1) 內,當且僅當 −1<z<0。在 z=−1 時有一個根為 −1;當 z<−1 時有一個根的模長大於一。
對實數 z<0,記 z=−a(a>0),p(ξ)=ξ2−(1−3a/2)ξ−a/2。判別式 (1−3a/2)2+2a>0,所以兩根為實數。兩根之積為 −a/2,故一根為負、一根為正。特徵多項式在 1 處的值為 p(1)=a>0,在 −1 處的值為 p(−1)=2−2a。由於 p(1)=(1−r+)(1−r−) 且 1−r−>0,正根小於一當且僅當 p(1)>0,這對每個 a>0 都成立。由於 p(−1)=(1+r+)(1+r−) 且 1+r+>0,負根大於 −1 當且僅當 p(−1)>0,即 a<1。因此兩根都在 (−1,1) 內,當且僅當 0<a<1。
把條件寫成 −1≤z<0,就包括了端點 z=−1;在該點兩根為 −1 和 1/2。根 −1 給出永不衰減的分量 (−1)n,所以嚴格的絕對穩定性在那裏不成立,儘管數值解仍然有界。
例題 8.2.9
(y′=−10y 的三個步長)
此時 z=−10h,嚴格穩定要求 0<h<0.1。取 h=0.05,z=−0.5,多項式 ξ2−0.25ξ−0.25 的根約為 0.640 和 −0.390,都在單位區間內。取 h=0.1,z=−1 是邊界:根為 −1 和 1/2,當 y0=1、y1=0 時解為 yn=31(−1)n+32(1/2)n,其交替部分永不衰減。取 h=0.2,z=−2,根為 −1±2,約為 −2.414 和 0.414;其中一個模長大於一。精確解衰減,但一般的數值起步值對會激發增長模式。局部缺陷小,並不能消除這個長時間試驗問題上的步長限制。
反例模式
準確的公式仍可放大擾動
命題:AB2 的局部缺陷很小,所以對衰減方程 y′=−10y,在任何適中的步長下都給出衰減的解。取 h=0.2,則 z=−2,遞推式為 yn+1=−2yn+yn−1。從精確起步值對 y0=1、y1=e−2≈0.1353 出發,得 y2≈0.7293、y3≈−1.3233、y4≈3.3760、y5≈−8.0753,比值趨近 −2.414,而 t=1 處的精確值是 e−10≈4.5×10−5。即使不穩定根方向上只有微小的分量,它也隨步數幾何增長。這是關於固定 h 與試驗方程長時間行為的陳述,並不與有限區間上的收斂定理矛盾,後者是 h→0,且對固定的 λ 有 z=hλ→0。修正方法是限制步長 h<0.1。
練習與解答
快速檢查
(對 y′=−y,從 y0=1、y1=1−h 出發,用 AB2 走一步求 y2。)
解答 · 答案
增量為 h[23(−(1−h))−21(−1)]=h(−1+23h),所以 y2=1−h−h+23h2=1−2h+23h2。
快速檢查
(求 z=−1/2 時的兩個特徵根,並判斷是否每個數值解都衰減。)
把 z=−1/2 代入 ξ2−(1+23z)ξ+21z。
解答 · 答案
多項式為 ξ2−41ξ−41,根為 ξ=(41±17/4)/2=(1±17)/8,約為 0.640 和 −0.390。兩者模長都小於一,所以每個數值解都衰減。
快速檢查
(若精確起步值滿足 y0=y(t0),但 y1−y(t1)=h,上面的收斂定理是否保證二階精度?)
把起步誤差與假設 C0h2 比較。
解答 · 答案
不保證:假設的起步誤差為 O(h2),而這個誤差是 h。該定理不提供二階保證。
快速檢查
(對 y′=−4y,給出 h>0 在嚴格負實軸穩定性下的限制。)
寫出 z=−4h,並使用區間 −1<z<0。
解答 · 答案
此時 z=−4h,所以 −1<−4h<0 即 0<h<1/4。