應用中遇到的大多數微分方程都沒有閉式解,因此要在網格上逐步計算數值解。本單元介紹顯式一步法,並回答實驗報告必須回答的問題:誤差有多大、它如何依賴步長 h、高階方法的代價是甚麼。它延伸實驗 3 中的 Euler 實驗,並補充隱式 Euler 法與穩定性的意義(該處處理剛性衰減);本單元只討論顯式方法與準確度。
初值問題與 Euler 法
求解 y′=f(t,y),y(t0)=y0,區間為 [t0,T],網格為 tn=t0+nh,h=(T−t0)/N。
定義 15.1.1
(一步法、Euler 法、局部誤差與整體誤差)
一步法只由 yn 算出 yn+1;若 yn+1 由公式直接給出而無須解方程,則稱為顯式。Euler 法為
yn+1=yn+hf(tn,yn).以 y(t) 表示精確解,整體誤差為 en=y(tn)−yn。若起點為精確值,單一步所產生的誤差稱為局部誤差。
Euler 法的局部誤差。 若 y∈C2,Taylor 定理給出 y(tn+1)=y(tn)+hy′(tn)+2h2y′′(ξn),其中 ξn∈(tn,tn+1),而 y′(tn)=f(tn,y(tn))。因此局部誤差為 2h2y′′(ξn),是 h2 階。
設 f 對 y 滿足 Lipschitz 條件,常數為 L>0,即對所有相關的 t,u,v 有 ∣f(t,u)−f(t,v)∣≤L∣u−v∣,且解滿足 [t0,T] 上 ∣y′′∣≤M。若 y0 為精確值,則
∣en∣≤2LhM(eL(tn−t0)−1).
把 Euler 公式從 Taylor 展開式中減去:
en+1=en+h[f(tn,y(tn))−f(tn,yn)]+2h2y′′(ξn),所以 ∣en+1∣≤(1+hL)∣en∣+2h2M。由 e0=0,用歸納法得 ∣en∣≤2h2Mk=0∑n−1(1+hL)k=2h2M⋅hL(1+hL)n−1=2LhM((1+hL)n−1)。因 1+hL≤ehL,故 (1+hL)n≤enhL=eL(tn−t0)。
證明透視
每個假設在遞推中的位置
Lipschitz 條件只用了一次,就在方括號裏:它把精確點與算得點上的斜率之差變成至多 L∣en∣,所以上一步的誤差乘以的是 1+hL,而不是某個無法控制的量。界 ∣y′′∣≤M 也只用了一次,在每一步把新產生的局部誤差限制在 h2M/2 以內。關鍵一步是把單行遞推 ∣en+1∣≤(1+hL)∣en∣+h2M/2 展開成等比和;這個和約有 1/h 項,每項大小為 h2,所以總和是 h 階而不是 h2 階,這正是失去一次冪的確切位置。最後的不等式 1+hL≤ehL 把精確但不易處理的 (1+hL)n 換成不分別依賴 n 和 h 的量,因此出現因子 eL(tn−t0),在長區間上這個因子可以很大。y0 精確使 e0=0;若有初始誤差,界便要多出一項 eL(tn−t0)∣e0∣。
因此整體誤差是 h 階:局部誤差是 O(h2),但 N∼1/h 步的累積損失一次冪,所以 Euler 法是一階。
二階方法
若對光滑的 f,方法的整體誤差為 O(hp),稱該方法為 p 階。
兩個經典的二階方法每步計算兩次 f。
Heun 法(改進 Euler 法)。
k1=f(tn,yn),k2=f(tn+h,yn+hk1),yn+1=yn+2h(k1+k2).
中點法。
k1=f(tn,yn),k2=f(tn+2h,yn+2hk1),yn+1=yn+hk2.
命題 15.1.4
(Heun 法與中點法的局部誤差)
若 f 二階連續可微,則 Heun 法與中點法的局部誤差都是 O(h3)。局部誤差 O(h3) 累積成整體誤差 O(h2)。
以 f,ft,fy 表示在 (tn,yn) 的值,其中 yn=y(tn)。由於 y′′=ft+ffy,Taylor 定理給出 y(tn+1)=yn+hf+2h2(ft+ffy)+O(h3)。對 Heun 法,k2=f(tn+h,yn+hf)=f+hft+hffy+O(h2),所以 yn+1=yn+hf+2h2(ft+ffy)+O(h3)。兩個展開式在 O(h3) 之內一致。中點法的計算相同,此時 k2=f+2hft+2hffy+O(h2),而 k2 前的因子 h 恢復出相同的 2h2 項。
在測試方程 y′=λy 上,令 z=hλ,Heun 法與中點法都給出 yn+1=(1+z+2z2)yn,即 ez 的二次 Taylor 多項式,這解釋了二階準確度。
經典四階 Runge–Kutta 法
k1k3=f(tn,yn),=f(tn+2h,yn+2hk2),k2k4=f(tn+2h,yn+2hk1),=f(tn+h,yn+hk3),yn+1=yn+6h(k1+2k2+2k3+k4).
這是標準結果:此方法的局部誤差為 O(h5),整體誤差為 O(h4)。對 y′=λy,可以直接驗證它與指數函數的匹配。令 z=hλ、yn=y:k1=λy,k2=λ(1+2z)y,k3=λ(1+2z+4z2)y,k4=λ(1+z+2z2+4z3)y。於是 k1+2k2+2k3+k4=λy(6+3z+z2+4z3),且
yn+1=(1+z+2z2+6z3+24z4)yn,
這是 ez 的四次 Taylor 多項式。
RK4 每步需要計算四次 f,Heun 法兩次,Euler 法一次。代價以 f 的計算次數衡量,合理的比較是相同代價下的準確度,而不是相同 h 下的準確度。
以實驗量度階
若 E(h)≈Chp,則 E(h)/E(h/2)≈2p,故 p≈log2E(h/2)E(h)。這個近似只在 h 小得足以令首項佔主導時成立,並且需要精確解(或精細得多的參考解)來計算 E。
詳解例子
例題 15.1.5
(三種方法用於 y′=y)
取 y′=y、y(0)=1、T=1。精確值為 y(1)=e≈2.71828。對 y′=λy,每種方法每步都乘以一個固定因子。取 h=21,即 z=21,走兩步:
- Euler:因子 1.5,y2=2.25,誤差 0.46828。
- Heun:因子 1+21+81=1.625,y2=2.640625,誤差 0.07766。
- RK4:因子 1+21+81+481+3841=1.6484375,y2=2.717346,誤差 0.000936。
取 h=41(四步):Euler 為 1.254=2.441406,誤差 0.27688;Heun 因子 1.28125,y4=2.694856,誤差 0.02343;RK4 誤差 0.0000719。由 h=21 到 h=41 的誤差比為 1.69、3.31、13.0,當 h→0 時趨近 2、4、16,即階為 1、2、4。
例題 15.1.6
(兩種方法在非自治方程上的一步)
設 y′=y−t2+1、y(0)=21,精確解為 y=(t+1)2−21et,故 y(21)=2.25−21e1/2=1.425639。取 h=21。
- Euler:y1=21+21(21−0+1)=1.25。誤差 0.1756。
- Heun:k1=f(0,21)=1.5。預測點為 (21,21+21⋅1.5)=(21,1.25),所以 k2=1.25−41+1=2。於是 y1=21+41(1.5+2)=1.375。誤差 0.0506。
以下是 Heun 迴圈的 MATLAB 寫法,在這組數據上追蹤(第一輪:k1=1.5,k2=2,y=1.375):
f = @(t,y) y - t.^2 + 1;
h = 0.5; N = 1; t = 0; y = 0.5;
for n = 1:N
k1 = f(t, y);
k2 = f(t + h, y + h*k1);
y = y + h/2*(k1 + k2);
t = t + h;
end
例題 15.1.7
(給定步長下的 Euler 誤差界)
對 [0,1] 上的 y′=y:L=1,∣y′′∣=et≤e=:M,所以在 t=1 處 ∣en∣≤2he(e−1)≈2.335h。取 h=0.1 時為 0.2335,而實際的 Euler 誤差是 e−1.110=2.71828−2.59374=0.1245。這個界成立,但悲觀約兩倍。取 h=21 時,界為 e(e−1)/4≈1.168,而第一個詳解例子中的實際誤差為 0.468,相差約 2.5 倍。
常見錯誤與細微之處
局部誤差為 O(hp+1) 的方法,其整體誤差為 O(hp)。Euler 法的局部誤差是 2h2y′′,但 Euler 法是一階;因為有 h2 便稱之為二階,是誤解了 N∼1/h 步的累積。
在誤差表中把 h 減半時,必須使用同一個精確解和同一個終點 T;比較不同時刻的誤差會混入增長因子 eLt。在第一個詳解例子中,誤差比 1.69、3.31、13.0 都是在 t=1 處取得的。
RK4 的 k2 與 k3 都在中點時刻 tn+2h,但 k2 在 yn+2hk1 處計算,k3 在 yn+2hk2 處計算,而 k4 用完整步 hk3。弄錯哪個斜率用在哪一級,是手算中最常見的錯誤。
Euler 法的收斂界要求 f 對 y 滿足 Lipschitz 條件且精確解的二階導數有界;在奇點附近可能失效,且該界本身通常遠非最佳。
反例模式
大步長下高階方法未必更好
斷言:在任何步長下,階越高的方法誤差越小。取 y′=−10y、y(0)=1,走一步,h=21,則 z=hλ=−5,精確值為 e−5≈0.0067。Euler 的因子為 1+z=−4,Heun 為 1+z+2z2=8.5,RK4 為 1−5+12.5−6125+24625≈13.71。三者都遠離 0.0067,而且誤差隨階的升高而增大。取 h=0.05,z=−0.5,因子分別為 0.5、0.625 和 0.60677,而 e−0.5≈0.60653,此時階的排序才如預期。階描述的是 h→0 的極限;它對某個給定的較大 h 下的準確度或穩定性沒有任何說明。
練習
快速檢查
(對 y′=−2y、y(0)=1、h=41,分別用 Euler 法和 Heun 法計算 y2≈y(21),並與 e−1 比較。)
使用每步因子 1+z 與 1+z+2z2,其中 z=−21。
解答 · 引導解答
Euler:因子 1+hλ=1−21=21,所以 y2=41。Heun:z=−21 時因子 1+z+2z2 為 1−21+81=85,所以 y2=6425=0.390625。精確值為 e−1=0.367879;誤差分別為 0.1179(Euler)和 0.0227(Heun)。
快速檢查
(證明:Heun 法用於 y′=λy(λ<0 為實數)時,對每個 yn=0 有 ∣yn+1∣<∣yn∣,當且僅當 −2<hλ<0。)
把 1+z+2z2 配方。
解答 · 引導解答
令 z=hλ 為實數,因子為 1+z+2z2=21((z+1)2+1)≥21>0。所以它小於 1 當且僅當 (z+1)2<1,即 −2<z<0。當 z≤−2 或 z≥0 時,它至少為 1。因此 ∣yn+1∣<∣yn∣ 當且僅當 −2<hλ<0。
快速檢查
(Euler 法用步長 h、h/2、h/4,在同一時刻的誤差為 0.1200、0.0610、0.0307。估計其階。)
對每一對相鄰的值使用 p≈log2(E(h)/E(h/2))。
解答 · 答案
log2(0.1200/0.0610)=log21.967≈0.976,log2(0.0610/0.0307)=log21.987≈0.991。兩者都接近 1,與一階一致。
快速檢查
(證明:中點法用於 y′=λy 時,其更新因子與 Heun 法相同。)
令 z=hλ,分別計算兩種方法的 k2。
解答 · 引導解答
令 z=hλ。中點法:k1=λy,k2=λ(y+2hλy)=λ(1+2z)y,所以 yn+1=y+hλ(1+2z)y=(1+z+2z2)y。Heun 法:k2=λ(y+hλy)=λ(1+z)y,所以 yn+1=y+2hλy(2+z)=(1+z+2z2)y。兩個因子相同。
快速檢查
(對 [0,1] 上的 y′=y、y(0)=1,計算 h=21 時的 Euler 誤差界,並與第一個詳解例子中的實際誤差比較。)
使用 L=1、M=e、tn−t0=1。
解答 · 引導解答
∣e2∣≤2(1/2)e(e−1)=4e(e−1)≈1.168。實際誤差為 0.468,所以這個界成立,並高估約 2.5 倍。