從微分方程到更新公式
模型可能先告訴我們狀態的變化率,而非未來的狀態。初值問題同時指定變化率及起始值:
y′(t)=f(t,y(t)),y(0)=y0,0≤t≤T.
先假設區間上存在解。我們在等距網格 tn=nh 上求近似值 yn≈y(tn),其中 Nh=T。把方程在一步內積分,精確關係是
y(tn+1)=y(tn)+∫tntn+1f(s,y(s))ds.
用左端點的斜率乘步長來近似積分,得到第一個方法。
給定步長 h>0 與網格 tn=nh,顯式歐拉(Euler)法從 y0 出發,令
yn+1=yn+hf(tn,yn),n=0,1,…,N−1.
目前的狀態決定斜率,斜率決定下一個狀態。幾何上這等於沿切線前進一步,而不是說真正的解曲線是直線。縮小步長通常減少離散誤差,但也需要更多步,浮點捨入誤差亦可能累積。
單步缺陷與整體誤差
為了量度一個更新本身的誤差,把精確解而非已有誤差的近似值代入更新式。
設 y 是 [0,T] 上的精確解。顯式歐拉法在第 n+1 步的單步缺陷為
dn+1=y(tn+1)−y(tn)−hf(tn,y(tn)).
若 y 二次連續可微,並在 [0,T] 上滿足 ∥y′′(t)∥≤M,泰勒(Taylor)公式的積分餘項給出 ∥dn+1∥≤Mh2/2。這裏的絕對單步缺陷是 h2 階;有些文獻再除以 h 才稱為局部截斷誤差,因此報告階數時要先說明慣例。
設 y 是 [0,T] 上的二次連續可微解,且 ∥y′′∥≤M。假設在包含精確值和數值值的區域內,f 對第二個變量的 Lipschitz 常數為 L≥0。從精確初值開始,顯式歐拉法滿足
∥y(tn)−yn∥≤⎩⎨⎧2LMh(eLtn−1),2Mtnh,L>0,L=0.因此在固定終止時間、上述界可一致使用時,網格加密所得整體誤差是 O(h)。
令 en=y(tn)−yn。精確一步減去數值一步,得
en+1=en+h[f(tn,y(tn))−f(tn,yn)]+dn+1.由三角不等式、Lipschitz 條件及缺陷界,
∥en+1∥≤(1+hL)∥en∥+2Mh2.由 e0=0 反覆使用此式,誤差不超過 (Mh2/2)j=0∑n−1(1+hL)j。若 L>0,求幾何級數並用 (1+hL)n≤eLnh,便得到第一個界;若 L=0,和為 n,得到 Mnh2/2=Mtnh/2。在固定時間內約有 T/h 步,故每步 O(h2) 的缺陷累積成 O(h) 的整體界。
證明透視
收斂估計的條件各有用途
證明由一個精確分解和一條遞推組成。分解把 en+1 拆成傳播下來的舊誤差 en+h[f(tn,y(tn))−f(tn,yn)] 與新的缺陷 dn+1;這一步尚未作任何估計。Lipschitz 假設只用於傳播部分,而且之所以適用,是因為兩個 f 值都在同一時間 tn 取值。所以定理要求在同時包含精確值與數值值的區域內有同一個常數 L。界 ∥y′′∥≤M 只用於 dn+1;兩個假設不能互相取代。
關鍵一步是不再逐步估計,而是從 a0=0 展開線性遞推 an+1≤(1+hL)an+Mh2/2:第 j+1 步產生的缺陷傳到第 n 步時,至多被放大 (1+hL)n−1−j 倍。最後用 1+hL≤ehL 把 n 個放大因子合成與步長無關的 eLtn,證明由此收結;固定終止時間正是在這裏用上。若 f 只在局部滿足 Lipschitz 條件,須先證明步長足夠小時數值點留在同一個有界區域內,才有單一常數 L 可用。
對 y′=y、y(0)=1,精確解是 et;歐拉法給出 yn=(1+h)n。在 T=1,取 h=1/2 走兩步得 y2=(3/2)2=9/4=2.25,小於 e;取 h=1/4 走四步得 (5/4)4=625/256≈2.4414。精確值約為 2.7183。第二個答案較接近,但兩次計算本身並不能證明誤差階數;上述定理在其假設下提供誤差界。
兩個誤差約為 0.468 和 0.277,步長減半時比值約為 1.7。展開式 (1+h)1/h=e(1−2h+O(h2)) 顯示 h 細小時誤差約為 eh/2,所以比值趨向 2,與一階收斂一致。
每步 O(h2) 的缺陷並不給出 O(h2) 的整體誤差。約有 T/h 個缺陷累積,證明顯示總和是 O(h);對 f(t,y)=t,整體誤差恰好是 Th/2,見最後一道練習。引用階數時,要說明指的是單步缺陷、除以 h 後的缺陷,還是整體誤差。
穩定性是另一個問題
收斂定理研究固定問題與固定時間區間,並令 h→0 的情況。實際計算的步長卻是有限的。為研究誤差傳播,考慮純量測試方程 y′=λy,其中 λ 可為複數且 Reλ<0。精確解 eλty0 會衰減。顯式歐拉法每步卻把狀態和其擾動乘上
R(z)=1+z,z=hλ.
數值解經任意多步後也衰減,充要條件是 ∣1+z∣<1。若 λ 為負實數,這等價於 0<h<−2/λ。在 ∣1+z∣=1 時擾動未必衰減;在圓盤外則增長。這是測試方程的絕對穩定條件,並非對所有非線性問題的誤差界。
反例模式
衰減的真解可以產生增長的歐拉數列
取 y′=−10y、y(0)=1 和 h=1/4。精確值為正且遞減,但歐拉法給出 yn+1=−23yn,所以 y1=−3/2、y2=9/4;迭代值正負交替且振幅增大。同一問題在 h→0 時仍符合歐拉法收斂定理;只是這個步長不在穩定區間 0<h<1/5 內。
隱式歐拉法與剛性衰減
若用右端點近似積分,得到第二個方法。
給定步長 h>0,隱式(後退)歐拉法從 y0 出發,每個 yn+1 定為下列方程的解:
yn+1=yn+hf(tn+1,yn+1).
未知值同時出現在兩邊,故每一步都需要解方程;方程可能非線性,亦不一定唯一可解。例如,若 f 全局 Lipschitz 常數為 L 且 hL<1,右邊作為未知值的函數是壓縮映射,壓縮映射定理保證該步有唯一解。這是充分條件,並非必要條件。
對測試方程,隱式方程是線性的,可以寫出閉式解。
命題 1.9.6
(隱式歐拉法使每個衰減測試模態衰減)
設 λ∈C 且 Reλ<0,又設 h>0。對 y′=λy,隱式歐拉法每一步都唯一可解,yn+1=(1−hλ)−1yn,而且當 yn=0 時 ∣yn+1∣<∣yn∣。
記 z=hλ,一步的方程是 (1−z)yn+1=yn。由於 Re(1−z)=1−hReλ>1,1−z 不為零,所以該步有唯一解 yn+1=(1−z)−1yn。此外 ∣1−z∣≥Re(1−z)>1,故 ∣(1−z)−1∣<1;當 yn=0 時便有 ∣yn+1∣<∣yn∣。
這個假設對 h 沒有任何上限。當 λ=−10、h=1/4,因子是 2/7,而非顯式法的 −3/2。穩定並不保證準確:一步後 2/7≈0.286 與精確值 e−5/2≈0.0821 相差甚遠。大步長即使穩定,也可能錯誤描繪快速的暫態變化。
概念視角幾何
複平面上的兩個穩定區域
以 z=hλ 為變量,顯式歐拉法恰好在開圓盤 ∣z+1∣<1(以 −1 為圓心、半徑為一)上抑制測試模態。這個圓盤與負實軸的交集是 (−2,0),也就是條件 0<h<−2/λ。隱式歐拉法恰好在 ∣1−z∣>1 處抑制它,即以 1 為圓心、半徑為一的閉圓盤之外。這個外部包含整個開左半平面,這正是上述命題;它也包含所有 Rez>2 的 z,在那裏一個增長的模態會被錯誤地抑制。
一個系統可同時包含快、慢衰減模態。例如 u′=−u 與 v′=−1000v 的時間尺度相差很大。即使關心的是較長時間的慢模態,顯式歐拉法仍須取 h<0.002 才能抑制快模態。這是剛性的一個簡單表現:穩定性要求的步長可能遠小於描繪慢變化所需的步長。隱式方法放寬測試方程的穩定性限制,但代價是求解線性或非線性方程;兩種方法都仍需檢查精度。
取 y′=−y2、y(0)=1,其精確解為 y(t)=1/(1+t),並取 h=1/2。隱式歐拉法要求 y1=1−21y12,即
y12+2y1−2=0,y1=−1±3.兩個根都滿足步進方程,但只有 3−1≈0.7321 延續解的軌跡;−1−3≈−2.732 與真解無關。實際求解器從上一步的值開始迭代:對 g(u)=u2+2u−2 由 u=1 起用牛頓(Newton)法,得 1, 0.75, 0.73214,…,收斂到正確的根。與 y(1/2)=2/3≈0.6667 比較,隱式法誤差約為 0.065;顯式歐拉法給出 1−21=0.5,誤差約為 0.167。
對 u′=−u、v′=−1000v 及 h=0.1,每步的顯式因子(左)與隱式因子(右)是
1−h=0.9,1−1000h=−99;1+h1≈0.9091,1+1000h1≈0.0099.精確的慢因子是 e−0.1≈0.9048,所以在這個步長下兩種方法都能合理地描繪慢模態。可是顯式歐拉法每步把快分量乘以 −99:十步後,大小為 10−10 的快擾動變成約 9×109,因為 9910≈9.0×1019。隱式歐拉法每步把它縮小為 1/101,雖然精確的快因子 e−100 還要小得多。邊界情況說明顯式法的門檻是確切的:當 h=0.002,快因子為 1−2=−1,快擾動正負交替、永遠既不增長也不衰減。
上述命題只說隱式歐拉法不會放大衰減的測試模態,沒有說它追蹤該模態有多準確。取 λ=−1000、h=0.1,因子 1/101 是穩定的,但精確因子是 e−100。對增長模態,同一性質亦可能誤導:若 λ>0 且 hλ>2,則 ∣1−hλ∣>1,隱式歐拉法會把一個實際上增長的解壓低。
練習
快速檢查
(對 y′=2t、y(0)=0,以步長 h=1/2 用顯式歐拉法計算 t=1 時的 y2,並與精確值比較。)
解答 · 答案
t0=0 和 t1=1/2 的斜率分別為 0 和 1,所以 y1=0+21⋅0=0、y2=0+21⋅1=1/2。精確解為 y=t2,在 t=1 的誤差是 1/2。
快速檢查
(對 y′=y、y(0)=1,以 h=1/2 計算兩步隱式歐拉法,並與上面的顯式結果 9/4 比較。)
每一步都是線性方程 yn+1=yn+hyn+1。
解答 · 答案
每步解 (1−h)yn+1=yn,而 1−h=1/2=0,得 y1=2、y2=4。顯式結果 9/4 小於 e≈2.718,隱式結果 4 大於 e。這個增長模態沒有被壓低:當 hλ<1 時,隱式歐拉法不會抑制真正增長的解。
快速檢查
(對 y′=−4y,哪些正實步長能令顯式歐拉法使擾動衰減?非零邊界會發生甚麼?)
寫出放大因子 1+hλ。
解答 · 答案
因子是 1−4h,不等式 ∣1−4h∣<1 等價於 0<h<1/2。在 h=1/2 時因子為 −1,擾動正負交替但不衰減。
快速檢查
(設 f(t,y)=t 且初值精確,直接證明在 T=Nh 的顯式歐拉累積誤差絕對值是 Th/2。)
把左端點斜率 tn=nh 相加。
解答 · 答案
精確解是 y(t)=y0+t2/2;歐拉法把左端點相加,得到 yN=y0+h2n=0∑N−1n=y0+h2N(N−1)/2。從 y(T)=y0+N2h2/2 減去數值解,得 Nh2/2=Th/2。這裏 L=0、M=1,定理的界 MtNh/2=Th/2 恰好取到等號。