動機
微分方程在每一瞬間描述變化率,電腦卻只能儲存有限個數值。數值積分把連續演化轉成時間網格上的遞推式。不過,一串看來平滑的數值本身不是誤差保證;我們必須說明它與原方程的解有甚麼關係。
考慮初值問題
y′(t)=f(t,y(t)),y(0)=y0,0≤t≤T.
未知量可以是 Rd 中的向量。以下假設經典解在整段區間存在;若解可能在有限時間爆破,這項存在性必須另行檢查。在一個網格點,微分方程給出切向量。沿此方向走一小段時間便得到前向 Euler 方法。關鍵是連續走很多步後會怎樣,因為後來的切向量是在近似狀態上計算的。
誤差有兩個來源。即使從精確解出發,切線也會偏離彎曲的解軌跡;而起點的擾動又可能改變後續數值。相容性量度前者,對擾動的穩定性控制後者。收斂證明把兩者結合。這套分工也適用於 Runge–Kutta 方法及偏微分方程的時間離散。
定義
定義 1.1.1
(前向 Euler、整體誤差與單步缺陷)
取正整數 N,令 h=T/N、tn=nh。前向 Euler 方法為
Y0=y0,Yn+1=Yn+hf(tn,Yn),0≤n<N.大寫 Yn 是近似值,小寫 y(tn) 是精確值。固定 Rd 上的一個範數,定義整體誤差 en=y(tn)−Yn。固定終點的誤差,與只走一步所產生的誤差,是不同的量。
把精確解代入方法,定義未縮放的單步缺陷
dn+1=y(tn+1)−y(tn)−hf(tn,y(tn)),以及縮放後的缺陷 τn+1=dn+1/h。不同教材可能把其中任何一個稱為局部截斷誤差,因此使用名稱時要說清楚約定。以下假設下,Euler 方法有 dn+1=O(h2),而 τn+1=O(h);冪次相差一是因為定義不同。
定義 1.1.2
(收斂階與 Lipschitz 條件)
記號 ah=O(hp) 表示存在與網格大小無關的正常數 C,h0,使 0<h≤h0 時有 ∥ah∥≤Chp。對誤差序列而言,一致估計要求同一常數適用於固定時間 T 前的所有網格點。一階收斂估計寫成
0≤n≤Nmax∥en∥≤CTh.常數可以依賴方程和 T,但不能暗中隨 N=T/h 增長。證明使用狀態變量的 Lipschitz 條件:對所有 t∈[0,T] 及 u,v∈Rd,
∥f(t,u)−f(t,v)∥≤L∥u−v∥,L≥0.這裏採用全域條件,免去數值軌跡是否留在某個較小區域的額外證明。若只知道局部條件,必須同時控制精確軌跡與所有數值狀態的位置。
概念視角分析
把 Euler 看成左端點求積法則
把方程在一步上積分,得到精確恆等式
y(tn+1)=y(tn)+∫tntn+1f(s,y(s))ds.前向 Euler 用左矩形 hf(tn,Yn) 代替這個積分,並把被積函數凍結在計算狀態上。缺陷 dn+1 正是矩形法則對被積函數 y′(s) 的求積誤差;以 Yn 代替 y(tn) 所引起的額外改變,則由 Lipschitz 常數控制。當 f 不依賴 y 時,Euler 恰好就是左 Riemann 和。
定理/命題
若 y∈C2([0,T];Rd),而整段區間滿足 ∥y′′(t)∥≤M,則每一步都有 ∥dn+1∥≤Mh2/2。
設 f 連續,對狀態變量全域 Lipschitz,常數為 L≥0;精確解 y∈C2 且 ∥y′′∥≤M。初值精確時,若 L>0,則
∥en∥≤2LMh((1+hL)n−1)≤2LMh(eLtn−1).若 L=0,則 ∥en∥≤Mtnh/2。所以當 h→0,Euler 方法在固定區間的所有網格點上一致收斂。
證明思路
兩次使用微積分基本定理,得到積分形式的 Taylor 展開:
y(t+h)=y(t)+hy′(t)+∫tt+h(t+h−s)y′′(s)ds.代入 y′=f(t,y),餘下的積分就是缺陷。權重 t+h−s 的積分為 h2/2,取範數便得第一個命題。這個向量證明不需要假設所有分量共享同一個 Taylor 中間點。
把數值遞推式從精確恆等式相減:
en+1=en+h(f(tn,y(tn))−f(tn,Yn))+dn+1.因此
∥en+1∥≤(1+hL)∥en∥+Mh2/2.由 e0=0 反覆代入,出現等比級數。L>0 時其和為 ((1+hL)n−1)/(hL);L=0 時為 n。再使用 1+x≤ex,便得所述估計。這是最壞情況的上界,並沒有聲稱每一步誤差實際上都沿同一方向相加。
證明透視
兩個假設在哪裏起作用
光滑性只用了一次,就在缺陷命題中,而且只沿精確解使用:積分形式的 Taylor 公式把 ∥y′′∥≤M 化成 ∥dn+1∥≤Mh2/2。Lipschitz 條件也只用了一次,用來比較精確狀態與計算狀態上的斜率 f(tn,y(tn))、f(tn,Yn);這個比較產生放大因子 1+hL。由於條件是全域的,毋須另證 Yn 留在局部常數有效的區域內。
關鍵一步是以純量不等式 ∥en+1∥≤(1+hL)∥en∥+Mh2/2 取代向量遞推,並把它當作等比級數精確求解。約有 T/h 個大小為 h2 的缺陷被加入,每個至多被放大 (1+hL)n≤eLT 倍,這個因子與 h 無關。若不計此因子,只把局部缺陷乘以步數,便忽略了放大作用,算不上證明。沒有 Lipschitz 界,這個因子根本無法建立;「常見錯誤」中的反例顯示結論此時可以失效。
若初始誤差不超過 ε,誤差界須加上 (1+hL)nε。若每一步另有加性擾動 ρj+1,其累積貢獻不超過
j=0∑n−1(1+hL)n−1−j∥ρj+1∥.
這個公式可用來分析已指定模型下的捨入或求解誤差。若每步的絕對擾動不隨步長下降,無限縮小步長便不保證浮點結果無限改善。
例題詳解
對 y′=−y、y(0)=1,有 Yn=(1−h)n。取 h=1/4,依次得到 1,0.75,0.5625,0.421875,0.31640625。在 T=1,精確值為 e−1≈0.36787944,故有號誤差約為 0.05147319。
這裏 L=1、∣y′′∣≤1,定理給出較寬的上界 (e−1)/8≈0.21478523。上界不是對實際誤差的預測。取 h=1/8,得到 Y8≈0.34360892,誤差約為 0.02427052;兩誤差之比約為 2.12,接近一階收斂所預期的兩倍關係。
對 y′=2t、y(0)=0,精確解為 t2,每步缺陷恰為 h2。直接求和得
Yn=2h2j=0∑n−1j=h2n(n−1),en=nh2=tnh.因 f 不依賴狀態,可以取 L=0,而 M=2。定理的界 Mtnh/2 恰好等於真實誤差。雖然沒有舊誤差的放大,新缺陷仍會累積;單步的 h2 與終點的 Th 必須區分。
仍考慮 y′=−y、y(0)=1,要求 [0,1] 每個網格點的絕對誤差不超過 0.01。充分條件為 h(e−1)/2≤0.01,即 h≤0.02/(e−1)≈0.0116395。取 N=86,上界約為 0.00999001。
這是有證明的充分步數,未必最少。Lipschitz 界沒有利用解的衰減,因而偏保守。較粗網格的實驗也可能符合容許誤差,但實驗觀察與理論保證的邏輯地位不同。
細化實驗及其局限
若不知道精確解,可以在共同終點比較 h,h/2,h/4。假設存在展開 Yh=y(T)+Ch+O(h2) 且 C=0,則相鄰差值的比趨近二。單次觀察到接近二的比值只是證據,並非所有分量都已進入漸近區間的證明。若首項係數消失,比值也可能不同。
在上述展開下,2Yh/2−Yh 可消去一階項。不過,僅有一個 O(h) 誤差界,不足以推出此展開;外推的理由需要更強假設。應區分定理已證明的內容與實驗採用的誤差模型。
取得常數而非假設常數
常數也應從方程取得。若 f 有連續一階偏導,沿解有 y′′=ft+Dyff。在包含精確軌跡的區域上控制這三項,便可估計 M,不必先知道解的公式。微分不等式、守恆量或先驗界有時能提供該區域。若區域尚未證實,任意指定一個 M 並不能完成保證。
在凸區域內,沿兩狀態之間的線段積分 Jacobian,可由 Dyf 的算子範數界推出 Lipschitz 條件。矩陣各元素的界可以轉成算子範數界,但常數依賴所選範數與維數。證明中途混用最大範數與歐氏範數而不調整常數,可能令數值保證失效。
誤差遞推式也可以用歸納法仔細核對。第一步只有新缺陷;第二步包含被放大一次的第一個缺陷,以及剛加入的第二個缺陷。到第幾步,較早的缺陷便經歷較多次傳播。取範數和三角不等式會失去正負抵銷的資訊,這正是上界有時遠大於觀察誤差的原因。若要利用衰減方向或誤差抵銷,必須提出額外結構,不能在一般證明中直接假設它們存在。
實際報告結果時,應同時記錄步數與終點。比較兩個網格的終點值之前,先確認它們對應相同時間;若使用整數步數截斷到較早時間,差值便同時混入時間位置的差異。若最後一步特別縮短以到達指定終點,可用下面的非均勻步長分析,而不是把最後一段仍當作原來的步長。這些記錄讓細化實驗與理論中的固定時間比較保持一致。
非均勻步長
等距網格並非必要。設正步長 hj=tj+1−tj 的總和為 T,最大步長為 H。每步使用實際的 hj,缺陷界為 Mhj2/2。誤差傳播因子是若干個 1+Lhj 的乘積,最多為 eLT。又因 j∑hj2≤Hj∑hj=HT,所以初值精確時有
nmax∥en∥≤MeLTTH/2.
此界雖不如均勻網格的等比級數界銳利,卻說明只要最大步長趨零便收斂。大量極小步不能抵銷保留一個大步的影響。以局部缺陷選步長,也仍須考慮整體誤差的傳播。
一階保證容許某些問題更精確。當 f 為常數,Euler 在所有網格點都精確;某些問題的首項誤差也可能在特定終點消失。階數描述假設下的一般速率,不是每次把步長減半都必然令任何誤差恰好減半。
常見錯誤
相容性必須沿精確解計算。把缺陷中的 y(tn) 換成 Yn,所得已是另一種殘差或誤差表達式,Taylor 論證並不控制它。
常見錯誤
(因缺陷為 O(h2) 而稱 Euler 為二階)
未縮放缺陷 dn+1 為 O(h2),縮放缺陷 τn+1 為 O(h)。方法的階數指整體誤差的階數,與 τ 相同:約 T/h 個大小 h2 的缺陷累積成 O(h);精確例子 y′=2t 正好給出 en=tnh。
固定 T 的收斂定理在 T→∞ 時並不一致。對 y′=−y,誤差界按 eT 增長,但解與實際誤差都在衰減。衰減、振盪、守恆和長時間行為需要更細緻的穩定性分析。
Taylor 證明還需要解在整個區間足夠光滑,而非只在部分區域有一條看似可微的公式。
反例模式
沒有 Lipschitz 條件,誤差未必趨零
有人以為 f 連續且解光滑便已足夠。考慮 [0,1] 上的 y′=2∣y∣、y(0)=0。函數 y(t)=t2 是解,因為 y′=2t=2t2;它屬於 C2 且 ∣y′′∣=2。然而 Euler 每一步都算出 Yn+1=Yn+2h∣Yn∣=0,所以對每個 h 都有 eN=y(1)−YN=1。同一初值還有解:t≤a 時為 0、t≥a 時為 (t−a)2,每個 a≥0 各一個,因此根本沒有唯一的解可供逼近。右端在零附近不滿足 Lipschitz 條件:u→0 時 ∣2∣u∣−0∣/∣u∣→∞。恢復 Lipschitz 常數後,唯一性與誤差界便重新成立。
總結
Euler 使用左端點的向量場。二階導數有界給出 Mh2/2 的單步缺陷;Lipschitz 條件控制舊誤差的傳播,得到固定區間上一階的整體誤差。有效的誤差聲明應列明範數、初值精度、光滑性、時間區間及缺陷的縮放約定。
練習
快速檢查
(對 y′=y+t、y(0)=1,用步長 1/2 走兩步。求 Y1,Y2 及 t=1 的有號誤差;已知 y(t)=2et−t−1。)
解答 · 答案
初始斜率為 1,所以 Y1=1.5。在 t1=0.5,斜率為 1.5+0.5=2,故 Y2=2.5。精確值為 2e−2,所以 e2=2e−4.5≈0.93656366。把新狀態與舊時間混用會變成另一方法。
快速檢查
(對 y′=3t2、y(0)=0,求精確單步缺陷,並直接證明 [0,1] 終點誤差是一階。)
使用 y=t3 與整數平方和公式。
解答 · 答案
缺陷為 (tn+h)3−tn3−3htn2=3tnh2+h3。令 N=1/h,直接求和得 YN=3h3(N−1)N(2N−1)/6=1−3h/2+h2/2。故 eN=3h/2−h2/2,確為一階。一般定理取 M=6、L=0 也給出有效的較寬界 3h。
快速檢查
(設 L=2、M=3、T=1、初始誤差不超過 10−4、h=0.01。給出包含兩種貢獻的整體誤差界。)
解答 · 答案
所需界為 e210−4+(3×0.01/4)(e2−1)≈0.04865683。第一項約為 0.00073891,第二項約為 0.04791792。忽略第一項便等於擅自假設初值完全精確。