數值積分要判斷的是函數在兩個端點之間的整體行為,但電腦只會在有限多個位置求值。求積法以一個較簡單、可以直接積分的對象代替原函數。關鍵問題是:選了甚麼對象、如何加權樣本,以及用甚麼假設控制沒有觀察到的部分。
複合梯形法積分的是分段線性插值函數。Simpson 法則在每兩個子區間上積分二次插值多項式,但連三次多項式也能精確積分。本節推導兩條公式,證明帶有正確符號與常數的誤差界,再用一個可精確計算的例子,分清誤差保證與細分後的誤差估計。
先數清子區間,才寫權重
設 a<b,目標積分為 I=∫abf(x)dx。把區間平均分成 n 個子區間,令
h=nb−a,xj=a+jh(0≤j≤n).
包含兩端點在內,一共有 n+1 個取樣點。分清子區間數與點數,才能避免步長及權重的差一錯誤。梯形法容許任意整數 n≥1;下面的複合 Simpson 法要求 n≥2,而且 n 必須是偶數。
最初的推導假設函數值與算術都精確。求值誤差的影響會在後面另行處理。
把取樣點的個數當作 n 會得出錯誤的步長:五個取樣點表示 n=4 個子區間,h=(b−a)/4。這個錯誤同樣影響 Simpson 法,因為它要求子區間數為偶數,所以五個取樣點可用,六個則不可用。
積分直線,得到梯形公式
在 [xj,xj+1] 上,連接兩個端點函數值的直線,其積分是 h(f(xj)+f(xj+1))/2。把所有子區間的結果相加:內部節點屬於左右兩段直線,整體端點則只屬於一段。
定義 7.7.1
(複合梯形與 Simpson 公式)
複合梯形近似值為
Tn=h[2f(x0)+f(xn)+j=1∑n−1f(xj)].當 n 為偶數,複合 Simpson 近似值為
Sn=3hf(x0)+f(xn)+41≤j≤n−1j 為奇數∑f(xj)+22≤j≤n−2j 為偶數∑f(xj).空和取零。特別是 n=2 時,最後一個和是空的。
梯形權重全部為正,而且總和是 b−a,所以它能正確積分常數函數。它對一次函數也精確,因為線性插值就是原函數。不過,這兩點都不表示它能精確積分一般曲線。
推導 Simpson 權重,並解釋三次精確性
考慮三個節點 m−h,m,m+h。以 t=(x−m)/h 改變座標後,節點變成 −1,0,1。二次 Lagrange 基底多項式為 t(t−1)/2、1−t2、t(t+1)/2;它們在 [−1,1] 上的積分分別是 1/3,4/3,1/3。再乘上座標轉換因子 h,得到單個子區間對(panel)的公式
3h[f(m−h)+4f(m)+f(m+h)].
因此這條公式對所有二次多項式精確。它對 (x−m)3 也精確:這個函數關於中點是奇函數,積分與加權端點和都等於零。任何三次多項式都可寫成一個二次多項式,加上一個 (x−m)3 的倍數,所以三次情況亦精確。
依次接上互不重疊的子區間對 [x0,x2]、[x2,x4] 等,便得到複合權重。奇數索引節點是子區間對中點,權重為 4;內部偶數索引節點是兩個子區間對共用的端點,權重為 2。這正是此處規則要求偶數個子區間的原因。
對相同的嵌套網格,亦有一條精確的代數恆等式:
Sn=34Tn−Tn/2(n 為偶數).
逐一比較端點、奇數節點及偶數節點的係數即可證明。這條加權和之間的恆等式是精確的;若要進一步把某種相消解讀成未知積分誤差的估計,仍須額外論證。
導數界提供真正的誤差保證
若 f∈C2([a,b]),且整個區間上 ∣f′′(x)∣≤M2,則
∣I−Tn∣≤12b−ah2M2.此外,若 f′′≥0,則 I−Tn≤0。
在單個區間 [p,q] 上,令 g(x)=(x−p)(q−x)。它在端點為零,而且 g′′=−2。分部積分兩次,得到
∫pqf(x)dx−2q−p[f(p)+f(q)]=−21∫pq(x−p)(q−x)f′′(x)dx.非負權重 (x−p)(q−x) 的積分是 (q−p)3/6,所以絕對誤差不超過 M2(q−p)3/12。對 n 個寬度為 h 的子區間相加,便得到 nM2h3/12=(b−a)M2h2/12。
同一條恆等式還給出誤差符號:若 f′′≥0,則 I−Tn≤0。因此,對二次連續可微的凸函數,梯形近似值不小於真實積分。
若 f∈C4([a,b]),整個區間上 ∣f(4)(x)∣≤M4,而且 n 為偶數,則
∣I−Sn∣≤180b−ah4M4.此外,若 f(4)≥0,則 I−Sn≤0。
證明
(單個 Simpson 子區間對的四階導數核)
在參考區間 [−1,1],以 L(F) 表示真實積分減去 Simpson 加權和。以 −1 為展開點的 Taylor 積分餘項公式,把 F 寫成一個三次多項式,再加上
61∫−11(t−s)+3F(4)(s)ds,u+=max{u,0}.這裏 t 是函數自變量;當 s>t 時,相應項為零。因為 L 對三次多項式為零,套用 L 並交換積分次序,可得 L(F)=∫−11K(s)F(4)(s)ds。直接積分截斷三次函數,再代入三個取樣值,得到
K(s)=24(1−s)4−184(−s)+3+(1−s)3=−72(1−∣s∣)3(1+3∣s∣).這個核在 [−1,1] 上非正,積分為 −1/90,因此 ∣L(F)∣≤∥F(4)∥∞/90。
對實際子區間對 [m−h,m+h],令 F(t)=f(m+ht)。其四階導數為 h4f(4)(m+ht),積分轉換再帶來一個 h,所以單個子區間對的絕對誤差至多是 h5M4/90。子區間對共有 n/2 個,合起來就是 (n/2)h5M4/90=(b−a)h4M4/180。
這個核亦證明:若 f(4)≥0,則 I−Sn≤0。此處 Simpson 誤差的符號由四階導數控制,不能只看凸性。
證明透視
四階導數、符號與常數從何而來
論證靠三步。第一,三次精確性讓我們減去三次 Taylor 多項式,只剩下含 F(4) 的積分餘項。第二,核 K 在 [−1,1] 上符號不變:這使 L(F)=∫KF(4) 化為界 ∥F(4)∥∞∫∣K∣=∥F(4)∥∞/90,並且只要 F(4) 符號不變,就決定了誤差的符號。第三,縮放 F(t)=f(m+ht) 由導數帶來 h4,由積分再帶來一個 h,所以每個子區間對帶有 h5;把 n/2 個子區間對相加損失一個 h 的冪次,剩下 h4。若沒有三次精確性,第一步就不成立,論證只能得到三階結果。
這些保證以所列的導數假設為依據,不能單靠已取樣的函數值推出。
這個證明說明了為何只估計二次插值餘項、卻不處理相消,便得不到四階結果。三次精確性多消去了一項,而帶符號的核找出了剩餘的導數及常數。
常見錯誤
(凸性並不決定 Simpson 誤差的符號)
對凸函數,梯形法會高估,因為 I−Tn 的符號由 f′′ 控制。Simpson 誤差則由 f(4) 控制,所以 f(4)<0 的凸函數會被 Simpson 法低估。應檢查誤差公式中真正出現的那個導數。
精確計算一個細分表
例題 7.7.4
(在 [0,1] 上積分四次方函數)
對 f(x)=x4,真實積分是 I=1/5。在 [0,1] 上,可以使用 M2=12、M4=24。
例如,S2=(0+4(1/2)4+1)/6=5/24。由於四階導數恆為 24,複合 Simpson 誤差剛好達到所列的界。步長減半時,這個誤差恰好減至原來的 1/16。
梯形誤差界則雖然有效,卻偏保守。兩個觀測誤差之比接近 4,但不恰好等於 4,因為誤差除了主要的二階項,還可能有其他項。最壞情況的界不會對每個函數、每個網格都取等號。
例題 7.7.5
(n=2 時的三次函數)
取 [0,1] 上的 f(x)=x3,n=2,則 h=1/2,S2 中偶數索引的和是空的。精確值為 1/4。梯形值為 T2=21(21+81)=165,I−T2=−1/16:這是高估,與 f′′=6x≥0 的預測一致,並且在界 121⋅41⋅6=81 之內。Simpson 給出 S2=61(0+4⋅81+1)=41,精確,因為 f(4)=0,可取 M4=0。恆等式亦吻合:T1=1/2,(4T2−T1)/3=(5/4−1/2)/3=1/4=S2。
若要在計算樣本前,規劃使絕對誤差不超過 ε>0 的網格,可以重排誤差界。梯形法要求 n2≥(b−a)3M2/(12ε);Simpson 法要求 n4≥(b−a)5M4/(180ε),並且 n 為偶數。只有在整個區間上的導數界已被證明時,這才是有保證的充分選擇。
取 [0,1] 上的 f(x)=ex,ε=10−4。在 [0,1] 上 f′′=f(4)=ex≤e<3,所以 M2=M4=3 有效。梯形條件為 n2≥3/(12⋅10−4)=2500,故 n=50,需要 51 個取樣點。Simpson 條件為 n4≥3/(180⋅10−4)≈166.7;由於 24=16、44=256,最小的偶數 n 是 4,需要 5 個取樣點。驗算:n=4 的界為 3/(180⋅256)≈6.5⋅10−5≤10−4,而 n=2 的界為 3/(180⋅16)≈1.04⋅10−3。
細分估計還有額外假設
對足夠光滑的固定函數,假設這些均勻網格上的 Simpson 誤差具有非零首項 I−Sn=Ch4+o(h4)。步長減半後,首項除以 16。兩個近似值相減,得到估計
I−S2n≈15S2n−Sn,I≈S2n+15S2n−Sn.
當目前網格已處於漸近展開適用的範圍,這很有用。但不能只因函數光滑,或兩個答案接近,就把它當成嚴格上界。梯形法對應的首項估計用除數 3。如果首項係數為零,或網格太粗、首項還未主導誤差,觀測到的比例便可能不同。
對 x4,Simpson 誤差只有該四階項,因此 S4+(S4−S2)/15=1/5 恰好精確。但在一個多項式上的成功,不能為任意函數提供精度保證。
反例模式
兩次細分答案一致,也可能都漏掉正積分
在 [0,1] 上,定義
f(x)=r∈{0,1/4,1/2,3/4,1}∏(x−r)2.這是光滑的非負多項式,在 S2、S4 所使用的每個節點都等於零。因此兩個近似值及其差都是零,但函數在這些有限零點之間為正,積分嚴格大於零。再把函數乘上任意正常數,兩個樣本答案仍然是零,真實積分卻會按比例放大。
這並不違反導數誤差保證:放大函數時,導數界也跟著放大。錯誤在於把未證明的數值估計,當成了獨立成立的導數界。
分開積分誤差與求值誤差
兩條規則的權重都為正,總和是 b−a。如果每個輸入函數值與精確的 f(xj) 相差不超過 η,則加權和與精確函數值規則的差不超過 (b−a)η。因此,在尚未計算加總捨入誤差之前,三角不等式給出的總誤差界是原求積界加上 (b−a)η。
細分時,這個區分尤其重要。增加節點可以減少插值誤差,卻可能不減少求值誤差,並增加浮點運算量。精確算術下關於 I−Sn 的定理,本身不能保證浮點程式的輸出。嵌套網格可以重用舊函數值來節省工作,但不會改變上述數學假設。
練習與解答
快速檢查
(用 T2 和 S2 積分 [0,1] 上的 f(x)=x2。以 M2=2 驗證梯形誤差界,並在不估計四階導數的情況下解釋 Simpson 結果。)
解答 · 答案
真實積分是 1/3。梯形值為 (1/2)(0/2+1/4+1/2)=3/8,誤差是 3/8−1/3=1/24;誤差界為 (1)(1/2)2(2)/12=1/24,剛好取等號。Simpson 值為 (0+4(1/4)+1)/6=1/3,因為它對每個二次多項式都精確。
快速檢查
(對 [0,1] 上的 x4,按本節導數界,要保證絕對誤差至多 10−4,梯形法最小的 n 與 Simpson 法最小的偶數 n 各是多少?比較取樣點數。)
解答 · 答案
梯形界是 1/n2,所以 n=100 足夠,而且是此界容許的最小整數,需要 101 個函數值。
Simpson 界是 2/(15n4)。n=6 時為 1/9720>10−4,n=8 時則為 1/30720<10−4。此界隨 n 遞減,所以 8 是它能保證的最小偶數選擇,需要 9 個函數值。這比較的是同一函數的充分導數保證,不是普遍固定的速度提升。
快速檢查
(有人說 Simpson 法對光滑凸函數一定高估。用 [0,1] 上的 f(x)=x2−x4/12 檢查,並同時給出導數論證和精確誤差。)
解答 · 答案
此時 f′′(x)=2−x2≥1,所以函數凸。但 f(4)=−2,Simpson 核恆等式給出 I−S2>0,即低估。直接計算亦得 I=19/60、S2=91/288,所以 I−S2=1/1440。凸性控制梯形誤差的符號;本定理中,Simpson 誤差符號則由四階導數控制。
快速檢查
(在長度為 2 的區間上,已知 ∣I−Sn∣≤0.0003。每個輸入函數值的絕對誤差至多 0.0001。在尚未計入加總捨入前,總誤差可保證多少?極小的細分差能消除求值誤差項嗎?)
解答 · 答案
正權重總和是 2,所以求值誤差的貢獻至多 2(0.0001)=0.0002。三角不等式給出加總捨入前的總誤差至多 0.0005。極小的細分差不能消除這一項:誤差可能同時保留在兩個加權和中,而兩者一致並不是對精確函數值的獨立誤差保證。
解答提示: 下方互動圖會顯示上面各練習的結果,包括四次冪練習的最小網格數。請先嘗試練習,再展開互動圖。
展開互動圖(顯示練習 1–3 的解答)