為何重用過去,而非重新取樣現在
本階段的一切都圍繞同一件任務:把數值初值問題 y' = f(x, y) 的解一步一步往前推進。歐拉法在每一步起點只用單一斜率;你剛認識的 Runge-Kutta 法則藉由在每一步*內部*多次計算 f、在精心挑選的內部點上取樣斜率後再下決定,來換取更高的精度。例如 RK4 每步呼叫 f 四次。這做得很漂亮——但留意那份悄悄的浪費:一步結束後,那四次計算就被丟棄,下一步又從頭開始它的取樣。
多步法問了一個節儉的問題:與其在每一步內部重新取樣斜率,何不重用我們在最近幾個格點上*早已*算好的斜率值 f 呢?畢竟,等到我們想從 x_n 邁向 x_(n+1) 時,我們手邊已坐擁一個小檔案庫——近期的解值 y_n、y_(n-1)、y_(n-2)、…… 以及它們的斜率 f_n、f_(n-1)、f_(n-2)、……。多步法讓一條多項式穿過那段近期的斜率歷史,並用它躍向前方,於是每一步新步只花大約*一次*全新的 f 計算,而非四次。名字已說明一切:像 Runge-Kutta 這樣的單步法只需當前點就能邁出一步;多步法則倚靠好幾個過去的點。
Adams-Bashforth:來自過去的顯式一步
把這個想法落實如下。將 y' = f(x, y) 在一步上精確積分,從 x_n 到 x_(n+1):y 的變化量就是 f 在那段區間上的積分。我們無法精確算這個積分——f 依賴於未知的解——所以我們*用一條多項式近似被積函數 f*,讓它穿過我們在近期各點早已知道的斜率值,然後改去積那條多項式,這很容易。若只穿過 f_n(一條平線),就還原成樸素的歐拉法。若讓一條直線穿過 f_n 與 f_(n-1) 並積分它,就跳出兩步的 [[adams-bashforth-method|Adams-Bashforth 法]]:y_(n+1) = y_n + (h/2)(3 f_n - f_(n-1))。
仔細看那條公式:右邊只用到你早已擁有的量——f_n 與 f_(n-1) 是你早已經過的點上的斜率。右邊沒有任何東西依賴未知的 y_(n+1)。這使 Adams-Bashforth 成為一個[[explicit-versus-implicit-method|顯式方法]]:你只需代入就能直接算出答案,沒有方程要解。精度的代價僅僅是記憶體——把最近幾個 f 值留著。加入更多過去的點會提高方法的階:常用的四步 Adams-Bashforth 讓一條三次多項式穿過 f_n、f_(n-1)、f_(n-2)、f_(n-3),達到四階,在精度上與 RK4 相當,卻每步只呼叫 f 一次,而非四次。
Exact over one step: y(x_{n+1}) = y_n + integral_{x_n}^{x_{n+1}} f(x, y) dx
Approximate f by a polynomial through KNOWN past slopes, then integrate it:
AB1 (Euler) : y_{n+1} = y_n + h * f_n
AB2 : y_{n+1} = y_n + (h/2) * ( 3 f_n - f_{n-1} )
AB3 : y_{n+1} = y_n + (h/12) * ( 23 f_n - 16 f_{n-1} + 5 f_{n-2} )
AB4 : y_{n+1} = y_n + (h/24) * ( 55 f_n - 59 f_{n-1} + 37 f_{n-2} - 9 f_{n-3} )
where f_k = f(x_k, y_k) are slopes you ALREADY computed
EXPLICIT: the right-hand side never mentions y_{n+1} -> just plug in.Adams-Moulton:偷看前方的隱式表親
現在容許一個額外、略帶調皮的動作。當我們讓一條多項式穿過斜率來近似那個積分時,為何要把自己限制在*過去*的點上?若我們也讓多項式穿過我們正要邁向的那一點上的斜率——尚未知道的 f_(n+1) = f(x_(n+1), y_(n+1))——那麼擬合就橫跨了我們正在積分的整個區間,而非從其末端往外外推,這確實更準確。這就給出 [[adams-moulton-method|Adams-Moulton 法]]。兩步版本是 y_(n+1) = y_n + (h/12)(5 f_(n+1) + 8 f_n - f_(n-1))。
但看出那條公式裡瞪著你的玄機:f_(n+1) 指的是在 y_(n+1) 處計算的 f——正是我們試圖求出的東西。未知量出現在*兩*邊。這使 Adams-Moulton 成為一個隱式方法:每一步都是一個要解出 y_(n+1) 的方程,而非一個拿來代入的配方。對於典型的非線性 f,這確實比顯式情形更難,通常需要一次迭代才能攻破。那何苦如此?因為在相同步數下,一個 Adams-Moulton 公式始終比它的 Adams-Bashforth 手足更準確,而且——如下一篇將精確說明的——隱式方法的穩定性好得多,這正是當一個方程剛性時你所需要的。隱式性是你付費換來的特性,不是瑕疵。
預測-校正:先猜,再精修
這裡有個優雅的化解之道。顯式的 Adams-Bashforth 法便宜卻略粗;隱式的 Adams-Moulton 法更準卻需要一個它尚未擁有的 y_(n+1) 值。何不讓便宜的那個*提供起始猜測*給準確的那個呢?這個配對就是[[predictor-corrector-method|預測-校正法]],是數值分析裡最漂亮的想法之一。先用一個顯式的 Adams-Bashforth 步預測,得到一個暫定答案,叫它 y*_(n+1)。然後校正:只用 y*_(n+1) 去計算斜率 f(x_(n+1), y*_(n+1)),把它餵進隱式的 Adams-Moulton 公式,於是掉出一個精修後、更準確的 y_(n+1)。
其深刻的巧妙在於它對隱式方法那份難處所做的事。Adams-Moulton 之所以難,是因為未知量同時坐在一個方程的兩邊。但一旦預測器交給我們一個對 y_(n+1) 的好猜測,我們就*只*在右邊用那個猜測去算一個斜率——於是校正器變成一個樸素的、顯式的代入。我們以「從一個聰明初始猜測出發、恰好做一次迭代」取代了解隱式方程,從而繞過了它。實際上,預測器把一個待解的方程變成一個待計算的公式,而校正器以僅僅多一次 f 計算的代價,兌現了隱式方法絕大部分的優越精度。
- 引導啟動:用像 RK4 這樣的單步法走最初幾步,把歷史視窗填滿,因為多步法無法只從一個點起步。
- 預測(P):把顯式 Adams-Bashforth 公式套用到儲存的斜率上,得到一個暫定的 y*_(n+1)。除了你已有的之外,這不需要新的 f 計算。
- 計算(E):在預測點處計算斜率 f*_(n+1) = f(x_(n+1), y*_(n+1))。這是唯一一次真正新的 f 計算。
- 校正(C):把那個斜率代入隱式 Adams-Moulton 公式,得到精修後的 y_(n+1)——此刻是一個顯式代入,而非待解的方程。
- 可選地再計算一次(最後的 E),把校正後的斜率存起來供下一步的歷史使用,然後推進視窗並重複。這個常見的模式稱為 PECE。
一份免費的誤差估計,以及一個誠實的裁決
預測-校正配對裡藏著一份絕妙的紅利,正是這些格式在真實軟體中佔有一席之地的原因。預測器與校正器是同階的不同公式,所以它們在同一步上犯下略為不同的誤差。因此預測的 y*_(n+1) 與校正的 y_(n+1) 之間的*差距*,就是對局部截斷誤差一個直接、可計算的估計——這方法本質上是透過比較它自己的兩個猜測,免費告訴你它剛才錯了多少。那個估計恰恰是一個自適應驅動器所需的訊號:若差距大,這一步太貪心,h 該縮小;若差距極小,你在浪費功夫,h 可以增大。下一篇正是在這種便宜、內建的誤差感測器之上建立自適應步進。
那麼你該選哪一個——單步的 Runge-Kutta 法,還是多步的預測-校正法?要誠實面對這個取捨,而非挑一個偏愛。當計算 f *昂貴*時(譬如每次呼叫都要解一個大的子問題),多步法大放異彩,因為它每步只啜飲一兩次計算,而 RK4 卻牛飲四次。當 f *便宜*、但你需要頻繁改變步長,或你才剛起步時,單步法以其毫不費力的自啟動與輕鬆的步長變更勝出。這裡沒有放諸四海皆準的冠軍——只有每步成本與彈性之間的平衡,而像經典 Adams 程式碼這樣優良的正式求解器,正是被打造成倚靠便宜的一側,同時替你打理那些雜務。