動機
固定步長在解變化緩慢時可能浪費運算,在變化急劇時又可能太粗。自適應方法先試算,再比較同一時間區間上的兩個近似,據此決定是否保留。要把這個想法變成算法,單說「誤差大就縮短步長」並不足夠:我們還須指定保留哪個值、拒絕後從哪裏重試、如何到達終點,以及何時宣告失敗。
這裏選顯式 Euler 法,令每個階段都能手算。控制器刻意保守:拒絕時步長減半,接受後不增大。前一節已討論嵌入式 Runge–Kutta 估計與四階法的步長加倍;本節集中把一階法的比較寫成完整有限算法,並仔細區分指標和嚴格誤差界。
定義
考慮 y ′ = f ( t , y ) y'=f(t,y) y ′ = f ( t , y ) ,y ( t 0 ) = y 0 ∈ R d y(t_0)=y_0\in\mathbb R^d y ( t 0 ) = y 0 ∈ R d ,時間區間為 [ t 0 , T ] [t_0,T] [ t 0 , T ] ,其中 T > t 0 T>t_0 T > t 0 。從已接受狀態 ( t , Y ) (t,Y) ( t , Y ) 試步長 h > 0 h>0 h > 0 ,計算
k 0 = f ( t , Y ) , C = Y + h k 0 , M = Y + h 2 k 0 , k m = f ( t + h 2 , M ) , F = M + h 2 k m , D = F − C . \begin{aligned}
k_0&=f(t,Y),& C&=Y+hk_0,\\
M&=Y+\tfrac h2k_0,& k_m&=f(t+\tfrac h2,M),\\
F&=M+\tfrac h2 k_m,& D&=F-C.
\end{aligned} k 0 M F = f ( t , Y ) , = Y + 2 h k 0 , = M + 2 h k m , C k m D = Y + h k 0 , = f ( t + 2 h , M ) , = F − C .
C C C 是一個完整 Euler 步,F F F 是兩個半步。兩者必須從同一個數值狀態 Y Y Y 出發,而非比較兩條分別累積誤差的軌跡。
給定絕對容許量 a j > 0 a_j>0 a j > 0 與相對容許量 r j ≥ 0 r_j\ge0 r j ≥ 0 ,試算的尺度及按尺度調整的指標為
s j = a j + r j max ( ∣ Y j ∣ , ∣ F j ∣ ) , E = max 1 ≤ j ≤ d ∣ D j ∣ s j . s_j=a_j+r_j\max(|Y_j|,|F_j|),\qquad
E=\max_{1\le j\le d}\frac{|D_j|}{s_j}. s j = a j + r j max ( ∣ Y j ∣ , ∣ F j ∣ ) , E = 1 ≤ j ≤ d max s j ∣ D j ∣ . 當 E ≤ 1 E\le1 E ≤ 1 時試算被接受 ,傳遞的是較細的 F F F ,而非 C C C 。
a j a_j a j 與對應狀態分量有相同單位,r j r_j r j 無單位。正的絕對容許量使分母在狀態為零時仍為正。精確算術下,完整控制器如下:
設 H = T − t 0 H=T-t_0 H = T − t 0 、t = t 0 t=t_0 t = t 0 、Y = y 0 Y=y_0 Y = y 0 、深度 q = 0 q=0 q = 0 ,並選非負整數最大深度 Q Q Q 。
若 t = T t=T t = T ,回傳成功和 Y Y Y ;否則令 h = min ( H 2 − q , T − t ) h=\min(H2^{-q},T-t) h = min ( H 2 − q , T − t ) ,按上式算出 C , F , D , E C,F,D,E C , F , D , E 。
若 E ≤ 1 E\le1 E ≤ 1 ,設 ( t , Y ) ← ( t + h , F ) (t,Y)\leftarrow(t+h,F) ( t , Y ) ← ( t + h , F ) ,保留 q q q ,返回步驟 2。需要輸出軌跡時記錄接受的點。
若 E > 1 E>1 E > 1 且 q < Q q<Q q < Q ,丟棄兩個試算值,令 q ← q + 1 q\leftarrow q+1 q ← q + 1 ,在原來的 ( t , Y ) (t,Y) ( t , Y ) 返回步驟 2;若 E > 1 E>1 E > 1 且 q = Q q=Q q = Q ,回傳失敗和最後接受的點。
二進分割規則放棄自動增大步長,換取清楚的有限次數上界。在本算法的精確算術下,由於 H = T − t 0 H=T-t_0 H = T − t 0 且 q q q 不遞減,先前各接受步和全區間長度都是目前名義步長的整數倍;因此到達終點前截短不會發生。保留取最小值的步驟,是為初始 H H H 可任選的變體或謹慎實作的浮點運算提供終點防護。有限精度運算還須在階段值或指標非有限、t + h = t t+h=t t + h = t ,或中點無法與端點區分時宣告失敗;終點亦須用一致的表示。不可把這些情況誤報為成功。
定理 / 命題
設 f f f 在時間–狀態空間的開集 U U U 上為 C 1 C^1 C 1 ,且 f t , f y f_t,f_y f t , f y 局部 Lipschitz。令 K ⊂ U K\subset U K ⊂ U 為緊緻集,假設對起點 ( t , Y ) ∈ K (t,Y)\in K ( t , Y ) ∈ K 及 0 < h ≤ h 0 0<h\le h_0 0 < h ≤ h 0 ,精確解線段和兩個 Euler 階段點均位於包含於 U U U 的同一固定緊鄰域。令 ϕ h ( t , Y ) \phi_h(t,Y) ϕ h ( t , Y ) 表示以 Y Y Y 為時間 t t t 初值的精確解在 t + h t+h t + h 的值。對 ( t , Y ) ∈ K (t,Y)\in K ( t , Y ) ∈ K 一致地,當正的 h h h 充分小時,
D = h 2 4 A ( t , Y ) + O ( h 3 ) , ϕ h ( t , Y ) − F = D + O ( h 3 ) , A = f t + f y f . D=\frac{h^2}{4}A(t,Y)+O(h^3),\qquad
\phi_h(t,Y)-F=D+O(h^3),\quad
A=f_t+f_yf. D = 4 h 2 A ( t , Y ) + O ( h 3 ) , ϕ h ( t , Y ) − F = D + O ( h 3 ) , A = f t + f y f . 餘項在該緊緻集上一致。對有限的 Q Q Q ,只要階段值及指標均有定義且有限,上述精確算術控制器只試算有限次,並在 T T T 成功或於深度 Q Q Q 的拒絕步回傳失敗。成功只證明顯示的接受測試通過,並不證明精確解的誤差界。
概念視角 分析
把指標看成兩個斜率之差 兩條公式相減,精確地得到
D = h 2 ( k m − k 0 ) = h 2 ( f ( t + h 2 , M ) − f ( t , Y ) ) . D=\frac h2\bigl(k_m-k_0\bigr)=\frac h2\Bigl(f\bigl(t+\tfrac h2,M\bigr)-f(t,Y)\Bigr). D = 2 h ( k m − k 0 ) = 2 h ( f ( t + 2 h , M ) − f ( t , Y ) ) . 指標是半步內斜率變化的 h / 2 h/2 h /2 倍,相當於把 y ′ ′ = A y''=A y ′′ = A 的差商乘以 h 2 / 4 h^2/4 h 2 /4 。這既解釋了 D D D 的展開式,也解釋了下面零比較的例子:那裏兩個取樣斜率相同,所以不論兩者之間發生甚麼,D = 0 D=0 D = 0 。
證明思路或證明
對中點階段在時間和狀態兩個變量展開,得
k m = f ( t , Y ) + h 2 ( f t + f y f ) ( t , Y ) + O ( h 2 ) . k_m=f(t,Y)+\frac h2(f_t+f_yf)(t,Y)+O(h^2). k m = f ( t , Y ) + 2 h ( f t + f y f ) ( t , Y ) + O ( h 2 ) . 所以 F = Y + h f + h 2 A / 4 + O ( h 3 ) F=Y+hf+h^2A/4+O(h^3) F = Y + h f + h 2 A /4 + O ( h 3 ) ,而 C = Y + h f C=Y+hf C = Y + h f 。由微分方程有 y ′ ′ = f t + f y f y''=f_t+f_yf y ′′ = f t + f y f ,精確解展開為 ϕ h = Y + h f + h 2 A / 2 + O ( h 3 ) \phi_h=Y+hf+h^2A/2+O(h^3) ϕ h = Y + h f + h 2 A /2 + O ( h 3 ) 。相減即得兩個估計。這裏的「精確起點」是把當前的 Y Y Y 視為局部初值,並沒有聲稱整條計算軌跡上的 Y Y Y 等於原問題的 y ( t ) y(t) y ( t ) 。導數控制及緊鄰域保證餘項一致。
終止性方面,每次拒絕都令 q q q 增加;在接受或失敗之前最多增加 Q Q Q 次。在目前深度 q q q ,因 q q q 從不減少,先前每個接受步以及總長 H H H 均為 H 2 − q H2^{-q} H 2 − q 的整數倍。所以正的剩餘長度至少等於名義步長,截短不會發生。每個接受步至少長 H 2 − Q H2^{-Q} H 2 − Q ,故最多接受 2 Q 2^Q 2 Q 步,總試算次數亦有限。這個結論沒有保證在深度 Q Q Q 以內一定可達所選容許量。
證明透視
誤差結論需要三個獨立環節 展開只把 D D D 和局部缺陷聯繫至一個餘項;接受測試只檢查 D D D 相對於指定尺度的大小;要得到終點誤差界,還要計算該餘項的上界並控制已累積誤差的傳播。這些都不會單憑 E ≤ 1 E\le1 E ≤ 1 自動成立,因此不能說測試通過便保證每個真正局部誤差都小於其尺度。
若某分量 A j ( t , Y ) ≠ 0 A_j(t,Y)\ne0 A j ( t , Y ) = 0 且尺度連續變化,按尺度調整後的主導指標按 h 2 h^2 h 2 變化,步長減半後大約變為四分之一。不過這個算法每次拒絕後都重新計算 E E E ,不依靠漸近比例作接受決定。若主導項為零,較高階項或抵消可能主導比較,比例便不一定成立。
例如,若 L ≥ 0 L\ge0 L ≥ 0 ,各相關精確流的 Lipschitz 因子不大於 1 + L h 1+Lh 1 + L h ,並且已知真正局部缺陷的上界 δ n \delta_n δ n ,則 e n + 1 ≤ ( 1 + L h n ) e n + δ n e_{n+1}\le(1+Lh_n)e_n+\delta_n e n + 1 ≤ ( 1 + L h n ) e n + δ n ,因此
e N ≤ e L ( T − t 0 ) ( e 0 + ∑ n = 0 N − 1 δ n ) . e_N\le e^{L(T-t_0)}\left(e_0+\sum_{n=0}^{N-1}\delta_n\right). e N ≤ e L ( T − t 0 ) ( e 0 + n = 0 ∑ N − 1 δ n ) .
這是有條件的確定性界,不能未經證明便把 δ n \delta_n δ n 換成 ∥ D n ∥ \|D_n\| ∥ D n ∥ :必須先控制未知餘項。而每一步的局部容許量也不會自動限制這些上界之和。
例題詳解
例題 2.3.3
(完整計算:稍後狀態也可能遭拒絕)
取 y ′ = y y'=y y ′ = y 、y ( 0 ) = 1 y(0)=1 y ( 0 ) = 1 、T = 1 T=1 T = 1 、a = 1 / 32 a=1/32 a = 1/32 、r = 0 r=0 r = 0 、Q = 3 Q=3 Q = 3 。此時 C = Y ( 1 + h ) C=Y(1+h) C = Y ( 1 + h ) 、F = Y ( 1 + h / 2 ) 2 F=Y(1+h/2)^2 F = Y ( 1 + h /2 ) 2 、D = Y h 2 / 4 D=Yh^2/4 D = Y h 2 /4 。下表列的是未除以尺度的 D D D ;因狀態均為正,接受條件為 D ≤ 1 / 32 D\le1/32 D ≤ 1/32 。
第四個四分之一步有 531441 > 524288 531441>524288 531441 > 524288 ,故 D > 1 / 32 D>1/32 D > 1/32 ,時間保持在 3 / 4 3/4 3/4 。最後的接受值是
Y ( 1 ) = ( 9 8 ) 6 ( 17 16 ) 4 = 44386483761 17179869184 ≈ 2.58363340. Y(1)=\left(\frac98\right)^6\left(\frac{17}{16}\right)^4
=\frac{44386483761}{17179869184}\approx2.58363340. Y ( 1 ) = ( 8 9 ) 6 ( 16 17 ) 4 = 17179869184 44386483761 ≈ 2.58363340. 精確值 e ≈ 2.71828183 e\approx2.71828183 e ≈ 2.71828183 與它相差約 0.13464843 0.13464843 0.13464843 ,大於局部門檻 1 / 32 1/32 1/32 。這展示誤差累積;由於算法沒有承諾全域容許量,並無違反任何全域定理。若 Q = 2 Q=2 Q = 2 ,第四個四分之一步會在 t = 3 / 4 t=3/4 t = 3/4 回傳失敗。
取 y ′ = t ( t − 1 / 2 ) y'=t(t-1/2) y ′ = t ( t − 1/2 ) 、y ( 0 ) = 0 y(0)=0 y ( 0 ) = 0 ,區間為 [ 0 , 1 ] [0,1] [ 0 , 1 ] 。t = 0 t=0 t = 0 與 t = 1 / 2 t=1/2 t = 1/2 的兩個 Euler 階段斜率均為零,因此 C = F = D = 0 C=F=D=0 C = F = D = 0 ,任何正尺度都會接受整段。但積分得到 y ( 1 ) = 1 / 3 − 1 / 4 = 1 / 12 y(1)=1/3-1/4=1/12 y ( 1 ) = 1/3 − 1/4 = 1/12 。採樣時間之間的光滑多項式對這項比較不可見。零指標並不證明精確。
對 y ′ = − 100 y y'=-100y y ′ = − 100 y 和 h = 0.1 h=0.1 h = 0.1 ,兩個半步的放大因子為 ( 1 − 5 ) 2 = 16 (1-5)^2=16 ( 1 − 5 ) 2 = 16 ,但精確因子是 e − 10 e^{-10} e − 10 。重複這樣的步長會增長而非衰減。若絕對容許量刻意設得很寬,算法可接受它:令 Y = 1 Y=1 Y = 1 、a = 30 a=30 a = 30 ,則 C = − 9 C=-9 C = − 9 、F = 16 F=16 F = 16 、E = 25 / 30 < 1 E=25/30<1 E = 25/30 < 1 。收緊容許量可能使步長變短,但接受規則本身並非無條件穩定的保證。
常見錯誤
階數 p p p 的方法在共同主導缺陷展開成立時,細步誤差的倍數是 1 / ( 2 p − 1 ) 1/(2^p-1) 1/ ( 2 p − 1 ) 。這裏 p = 1 p=1 p = 1 ,倍數為一;套用 Runge–Kutta 步長加倍公式的四階分母 15 15 15 ,會把 Euler 估計低估十五倍。D D D 雖在漸近意義下近似細步帶符號誤差,也不因此自動成為嚴格上界。
拒絕後不可把試算狀態當成重試的起點。必須先以 T − t T-t T − t 截短,再算兩個近似,否則比較的不再是同一區間。若已知事件或不連續點,應在該點分段並採用合適的單側模型;沒有論證便不可把光滑展開跨越跳躍。
逐分量最大值測試的是所選尺度。改變某分量的單位而不相應改變其絕對容許量 a j a_j a j ,測試的含義也會改變。
總結
步長加倍比較一個 Euler 整步與兩個半步;在光滑條件下,兩者之差給出細步局部缺陷的主導近似。有限深度的接受/拒絕程序可到達終點,或明確回報失敗。通過局部比較本身並不能認證全域容許量或穩定性。
練習
快速檢查
(對 y ′ = 2 t y'=2t y ′ = 2 t 、y ( 0 ) = 0 y(0)=0 y ( 0 ) = 0 ,從 t = 0 t=0 t = 0 試步長 h h h 。求 C , F , D C,F,D C , F , D 和精確細步局部誤差;此例的估計是否恰好相等?)
解答 · 答案 第一個斜率為零,中點斜率為 h h h ,故 C = 0 C=0 C = 0 、F = h 2 / 2 F=h^2/2 F = h 2 /2 、D = h 2 / 2 D=h^2/2 D = h 2 /2 。積分得 y ( h ) = h 2 y(h)=h^2 y ( h ) = h 2 ,因此 y ( h ) − F = h 2 / 2 = D y(h)-F=h^2/2=D y ( h ) − F = h 2 /2 = D 。此例中高階餘項恰好為零,但任意光滑 f f f 不一定有此等式。
快速檢查
(考慮允許初始 H H H 任選的控制器變體中一次獨立試算,設 y ′ = y y'=y y ′ = y 、Y = 1 Y=1 Y = 1 、T − t = 1 / 2 T-t=1/2 T − t = 1/2 、a = 1 / 32 a=1/32 a = 1/32 、r = 0 r=0 r = 0 、目前名義步長為 1 1 1 。進行截短試算;若現有深度已是最大值,該變體回傳甚麼?)
解答 · 答案 截短後 h = 1 / 2 h=1/2 h = 1/2 ,故 C = 3 / 2 C=3/2 C = 3/2 、F = ( 5 / 4 ) 2 = 25 / 16 F=(5/4)^2=25/16 F = ( 5/4 ) 2 = 25/16 、D = 1 / 16 D=1/16 D = 1/16 。比例指標 E = 2 E=2 E = 2 ,試算被拒絕。在最大深度時算法回傳失敗及最後接受點 ( t , 1 ) (t,1) ( t , 1 ) ,既不推進時間,也不保留試算狀態。
快速檢查
(從精確初值出發,若證明每步真正局部缺陷的範數至多為 δ \delta δ ,精確流因子至多為 1 + L h n 1+Lh_n 1 + L h n ,其中 L ≥ 0 L\ge0 L ≥ 0 ,求總時間 T − t 0 T-t_0 T − t 0 內 N N N 個接受步後的誤差界。為何單憑 ∥ D n ∥ ≤ δ \|D_n\|\le\delta ∥ D n ∥ ≤ δ 不足?)
解答 · 答案 由上述界及 e 0 = 0 e_0=0 e 0 = 0 ,得 e N ≤ e L ( T − t 0 ) N δ e_N\le e^{L(T-t_0)}N\delta e N ≤ e L ( T − t 0 ) N δ 。此界可能偏大,但符合所列假設。比較值只控制 D n D_n D n ,真正缺陷還包括餘項;若未對餘項設界,就不能把 δ \delta δ 直接當作每步真正缺陷的上界。
快速檢查
(對 y ′ = − λ y y'=-\lambda y y ′ = − λ y 、λ > 0 \lambda>0 λ > 0 ,求兩個半 Euler 步的放大因子絕對值不超過一的所有正步長。邊界會怎樣?)
解答 · 答案 細步放大因子 ( 1 − λ h / 2 ) 2 ≥ 0 (1-\lambda h/2)^2\ge0 ( 1 − λh /2 ) 2 ≥ 0 。它不超過一恰當且僅當 − 1 ≤ 1 − λ h / 2 ≤ 1 -1\le1-\lambda h/2\le1 − 1 ≤ 1 − λh /2 ≤ 1 ,即 0 < h ≤ 4 / λ 0<h\le4/\lambda 0 < h ≤ 4/ λ 。在 h = 4 / λ h=4/\lambda h = 4/ λ 時放大因子為一:數值狀態的絕對值不衰減,雖然精確解會衰減。在嚴格區間內,非零狀態每步均衰減。