為何要選擇性細分?
均勻的求積網格在平滑區域與急劇變化的區域花費相同的計算量。自適應方法會比較某個子區間及其子區間的近似值,並在兩者差異最大之處加密細分。只有在我們清楚這種比較所衡量的是甚麼時,它才有用:兩個近似值之差本身,並不是任何一個近似值之誤差的保證界限。
定義 7.3.1
(子區間上的 Simpson 比較)
對於寬度為 的區間 ,設 。Simpson 法則為
記 及 。給定 、 和容差 ,自適應問題是:求 的近似值,並決定哪些子區間需要細分。量 稱為該子區間的誤差指標。
第二個近似值使用五個節點;端點與中點的函數值是共用的。當子區間再次被分割時,先前已計算的函數值可以重複使用。
為何會出現因子十五
定理 7.3.2
(單一子區間上的 Simpson 誤差)
若 ,則存在 ,使
這是標準的 Simpson 餘項;其推導(包括符號與常數)見關於複合梯形與 Simpson 法則的那一節。兩個半區間各自的誤差具有相同形式,寬度為 ,但中間點可能不同。若 在該子區間上近似為常數,則首項誤差大致滿足 ,這是因為兩個半區間合共貢獻 。把兩條式子相減,得到
對於一般函數,即使 是平滑的,該比值也未必恰好是 。對於次數至多為五的多項式,它則是精確的。
定理 7.3.3
(對次數至多為五的多項式,修正是精確的)
設 是次數至多為五的多項式。則在每個子區間 上,
因此 。
證明
(關於中點的對稱性)
把 寫成 。Simpson 法則對 精確:對 ,在 上的積分為 ,法則給出 ;奇次冪 的積分與法則值因對稱性均為零。對 ,積分為 ,法則給出 ,所以誤差為 。因此 ;由 ,這等於 。
對兩個半區間(寬度 、中點 )應用同一公式。由於 是次數至多為一的多項式,。於是
兩式相減,,所以 。
證明透視
只有在額外資訊下,兩個誤差才共享首項
因子十五來自把比例為十六比一的誤差相減。在上面的證明中,「次數至多為五」這個假設恰好用了一次:它使 成為一次函數,所以 在兩個半區間中點的平均值等於它在 的值。對一般的 ,四階導數定理在兩個半區間上給出不同且未知的中間點;它並沒有說明這些點上的導數值相等。要作出可靠的終止判斷,需要額外的界限,或接受該差值只是一種啟發式方法。因此,絕對量 是誤差指標,而非無條件的保證。
一個簡單的細分規則
給定局部容差 ,在子區間上計算 。若 ,則接受修正值 ;否則將區間二分並遞歸,為每個子區間分配容差 。
命題 7.3.4
(各容差之和等於原先的容差)
設遞歸停止時,被接受的子區間為 ,其中 位於深度 ,容差為 。若每個被接受的值,其真實誤差都不超過所分配的容差,則總絕對誤差至多為 。
證明
(二分保持容差之和不變)
起初只有一個容差為 的區間。每次二分把容差為 的區間換成兩個容差為 的區間,所分配容差之和保持不變。因此最終的容差之和為 ,由三角不等式,總誤差至多為這個和。
其前提,即每個被接受的值的真實誤差都在容差之內,正是單憑差值檢驗不能證明的。實際實現還需要最大遞歸深度或最小子區間寬度、指標未能減小時的處理策略,以及對函數求值誤差和算術誤差的考量。若中點經捨入後等於某個端點,二分便不再產生更小的浮點子區間。這種停止是未能達到所要求精度,而不是已達容差的證據。
常見錯誤
(讓每個子區間都得到完整容差)
若兩個子區間都繼承 而不是 ,一次分割後所分配的容差之和便是 ,繼續分割後更大。即使每個子區間都通過了自己的檢驗,上述命題的保證也不再成立。
命題 7.3.5
(遞歸的函數求值次數)
若遞歸所考察的是一棵完整二分樹,其被接受的子區間共有 個,則 的不同求值總數為 。
證明
(計算新增的四分點)
有 個葉的完整二叉樹共有 個節點,每個節點(無論被接受還是被分割)都要計算 與 。根節點需要 三個值。對其他節點,其端點與中點都已被求值:端點是父節點的端點或中點,而它的中點是父節點的一個四分點。因此每個節點只需新增自己的兩個四分點。深度為 的節點寬度為 ,其四分點是離 為 的奇數倍,所以不同深度節點的四分點互不相同,同一深度的節點對應的子區間互不相交。總數為 。
例題 7.3.6
( 上 的單一子區間)
在 上取 ,則 且
因此 ,修正量為 。確實有 。符號十分重要:指標使用絕對值,但修正後的近似值使用帶符號的差值。
例題 7.3.7
(容差為 的細分過程)
繼續考慮 上的 ,取 。頂層子區間的指標為 ,所以要二分,每個子區間得到容差 。對 和寬度為 的子區間,,所以兩個子區間(寬度 )的 ,指標為 ,兩者都被接受。對左子區間,、,修正值為 。右子區間修正為 ,總和為 。整個過程共用 次求值:根子區間的五次,加上四個新增的四分點。
例題 7.3.8
(三次函數被即時接受)
對 上的 ,,,。指標為零,所以該子區間不經任何分割就被接受;在這裏這個判斷是正確的,因為 Simpson 法則對三次多項式精確。這是指標為零的邊界情形;一般而言,指標為零並不表示誤差為零,下一個例子說明了這點。
反例模式
取樣值相符,並不能控制取樣點之間的情況
設 ,定義於 。它是非負多項式,在 與 所用的全部五個節點上均為零,而在這些節點以外為正。兩個近似值及其差均為零,但 。把 乘以任何正常數,會按比例放大被遺漏的積分,而五個取樣值仍然全為零。因此,若無進一步假設,任何只使用這些取樣的法則都無法提供普遍的誤差保證。要得到保證,需要額外的假設,例如在該子區間上經過驗證的某個導數界。
常見錯誤
(把指標當作誤差界)
因為 就接受子區間,並報告「誤差至多為 」,所聲稱的比已證明的更多。指標只是一個估計,依賴 在子區間上近似為常數。除非另有導數界補上缺少的前提,否則只能把它當作估計來報告。
練習與解答
快速檢查
(若 且 ,求指標及修正值。)
解答 · 答案
指標為 ,修正值為 。
快速檢查
(為何 中五個值有三個已可由 得到?)
解答 · 答案
共用的點為 ;只有兩個四分點是新增的。
快速檢查
(假設兩個被接受的子區間,其誤差均經嚴格證明至多為 。求總絕對誤差的界限。)
解答 · 答案
把誤差相加並應用三角不等式,得總誤差至多為 。
快速檢查
(對於任意平滑函數,僅憑 能否證明積分是精確的?)
解答 · 答案
不能。反例中的非負多項式使兩個近似值均為零,但其積分為正。
快速檢查
(某次運行接受了 個子區間。它共用了多少次不同的 求值?)
解答 · 答案
由求值次數公式,為 。二分樹的 個節點各貢獻兩個四分點,再加根節點的 個值。