為甚麼先預測再校正?
梯形法把舊、新端點的斜率取平均;但新端點斜率依賴未知的新數值,因此一般每一步都要解代數方程。若已有前兩個斜率,Adams–Bashforth 預測可以廉價地估計新端點,再用該處斜率校正一次。這省去隱式求解,代價是所得公式成為另一個顯式兩步法:只校正一次,並不保證預測值等於梯形方程的解。
定義 4.3.1
(一次 AB2 預測與一次梯形校正)
設 ,固定步長 ,,。由兩個起始值計算
校正後,要重新計算並儲存 ,供下一步使用。把預測點的 當作 沿用,得到的是另一算法。可用顯式中點法等單步法求 ,令其誤差為 或更小;任意起始值不一定保留所需階數。
概念視角算法
不動點迭代的一次掃描
把梯形方程寫成 ,其中 。校正值正好是 :從 AB2 猜測值出發的一次不動點掃描。由於 的 Lipschitz 常數是 ,校正值與梯形解 的距離按這個因子縮小:。在下面的單步例子中, 與 分別偏離 達 與 ,比值正是 。
從局部誤差到收斂
定理 4.3.2
(有限時間區間上的二階收斂)
假設 對狀態變量在所有時間上一致地全域 Lipschitz,常數為 ,且精確解在 上三階導數有界。若 和 均為 ,則當 時,所有滿足 的格點有 。同一論證適用於固定有限維空間中的任何範數。
證明
(精確起步缺陷與兩層 Gronwall 論證)
把前兩個精確值代入預測式。在 附近對 和 作泰勒(Taylor)展開,可知預測端點 與 之差一致地為 。由於 有界,對 的梯形積分公式有 的狀態缺陷。將精確端點斜率改成 ,所得校正值最多改變 ;故從精確歷史出發的校正缺陷為 。
比較兩組數值歷史,令 為它們在第 和 點差的範數最大值。Lipschitz 條件令兩個預測值的差不超過 ,因此兩個校正值的差不超過 。當 ,此式不超過 ,其中 。把數值歷史與精確解的採樣比較,再加上每步 的缺陷,可得
迭代不多於 次,得到 。各行的常數可以適當放大,故結論成立。這是有限時間結論,並不保證每一個大步長都穩定。
證明透視
為甚麼一次不精確的校正不損失階數
證明的相容性部分取決於一次乘法。從精確歷史出發,預測值與 相差 。這個誤差只透過斜率 進入校正式,而斜率乘以 ,其改變又不超過 乘狀態誤差。因此預測值只貢獻 ,比梯形缺陷 低一階。這是關鍵一步:預測器的精度比校正器低一階便已足夠。
穩定性部分要處理兩步法,所以追蹤 ,即相鄰兩層誤差的較大者。Lipschitz 常數用了兩次:一次經過預測式,其中權重二分之三與二分之一給出 ;一次經過校正式。步長界 把 吸收進 。起始假設 只在最後出現,離散 Gronwall 界把它乘以 。由於剛性問題的 可以極大,這個有限時間定理對大步長毫無說明;下面的線性穩定區間才回答這個問題。
實際算法的穩定性
令 ,。消去預測值後,實際遞推式及其特徵方程為
每個特徵根 對應一個遞推模態。採用有界根的慣例:兩根模長均不超過一,且單位圓上的根必須是單根,才稱 穩定。重單位根須排除,因為它還產生 模態。
定理 4.3.3
(負實軸穩定區間)
當 、,上述一次校正算法恰在 時穩定。若 ,兩根都嚴格位於單位圓內; 時重根 使遞推不穩定。
證明
(實二次式的根位置判別)
對實係數首一二次式 ,兩根嚴格位於單位圓內的充要條件是 、 和 。複共軛根的模長平方等於 ;若兩根為實數,前兩個不等式排除只有一根超出任一端點,最後一個排除兩根同時超出同一端點。反過來,由兩根在圓內可直接得到三個不等式。
此處 、,上述三項分別是 、、;三者同時為正恰好等價於 。 時根為 。 時 ;例如 、 給出 。若 ,兩根之積 ,故至少有一根模長大於一。
詳解例子
例題 4.3.4
(實際計算一步)
取 、、、。因 、,得 ,。下一步儲存的斜率是 ,不是預測斜率 。相同的 若用完全隱式梯形法,須解 ,得到 。兩種方法確實給出不同結果。
例題 4.3.5
(衰減振盪和不穩定邊界)
對 ,當 時兩根為 ,模長均為 :任何歷史都會衰減,雖可能改變符號。當 時兩根均為 ,某些歷史線性增長。相比之下,梯形法在測試方程的放大因子為 ;當 ,其模長不超過一。一次校正算法不繼承這種 A 穩定性。
例題 4.3.6
(以精確起步作細化檢查)
取 上的 、,並用精確起始值 、,使定理適用。把方法推進至 ,得
相鄰誤差之比約為 與 ,逐漸接近二階方法應有的因子四。此處 遠在穩定區間之內,傳播不會干擾。這些比值與定理相符,但只是證據,不是證明。
常見誤解
常見錯誤
(儲存預測斜率)
預測值只是中間狀態,不是最終接受值。校正後必須計算並儲存 。在實際計算一步的例子中,儲存的斜率是 ,不是預測斜率 ;沿用後者便定義了另一方法,其穩定性分析亦不同。
常見錯誤
(邊界根只檢查模長)
在 ,兩根的模長都是一,只看模長便會接受這個值。但根 是重根,遞推有解 ,按有界根慣例此值不穩定。
常見錯誤
(任意選取第二個起始值)
收斂定理假設 。若直接取 ,對非常數解的起始誤差是 階,便不能再套用定理。顯式中點法等單步起步法可滿足此假設。
局部缺陷小,還要控制誤差的累積才能推出精度;同樣,齊次測試遞推的穩定性不是一般非線性方程的誤差界。以上區間也只適用於固定步長的一次校正公式;增加校正次數或改變步長會得到不同遞推。
反例模式
校正後的方法不繼承 A 穩定性
既然校正式就是梯形法,有人會以為方法像梯形法一樣,對每個 都穩定。取 、,即 。此時 、,特徵方程 的根為
由 、,遞推給出 、,而精確解按 衰減。同一 的梯形法因子為 。修正後的命題就是上面證明的穩定區間:在負實軸上,一次校正方法只在 時穩定。
小檢查
快速檢查
(預測值並不精確,為甚麼校正仍可有二階精度?)
追蹤預測誤差如何經端點斜率進入。
解答 · 答案
從精確歷史出發,端點預測誤差為 ;相應斜率誤差再乘 ,只對校正狀態產生 影響。梯形公式的缺陷本已有 ,所以精確起步缺陷仍為 。
練習與解答
快速檢查
(對 、,按有界根慣例判斷遞推是否穩定。)
計算 。
解答 · 答案
位於 ,兩根都嚴格位於單位圓內,兩個模態均衰減。
快速檢查
(對 、、、,計算第一次校正。)
使用 、。
解答 · 答案
預測值為 ;校正值為 ,應儲存的斜率是 。
快速檢查
(在 ,求 、 的解,並解釋其意義。)
特徵多項式是 。
解答 · 答案
遞推有重根 ,故 ;由起始值得 。再小的非零起始擾動也會隨 無界增長。
快速檢查
(學生使用精確 ,但取 ,可否套用上述二階收斂定理?)
把起始誤差與假設比較。
解答 · 答案
不可以。第二個起始誤差為 ,不是 ,而定理要求兩個起始誤差均為 。單憑這點並不能判定其後每個值的誤差,只是失去了保證。