動機
均勻求積在函數平緩和變化迅速的地方投入相同的取樣密度。自適應方法則反覆檢查子區間,把工作集中到看起來需要更多精度的部分。這個想法雖然直觀,實際算法卻必須處理共享樣本、局部容差和未能完成的情況;更重要的是,它必須說清楚「成功」究竟證明了甚麼。
本節給出兩種使用同一分割策略的算法。第一種通過粗、細 Simpson 值的差來估計誤差;第二種假設已知四階導數界,從而在精確算術下得到真正的絕對誤差保證。
定義
對 ,令 ,單區間 Simpson 值為
定義 、、。兩種公式合共使用五個點 。細規則的誤差估計量為 ;帶符號的修正值為 。此指標在模型下估計未修正值 的誤差,而非 的誤差;與 一起返回時仍然只是啟發式指標。符號不能隨便改變:在平滑的主導項模型中, 估計的是 ,不是其相反數。
絕對容差 是積分誤差預算,其單位與積分相同。每次二分,將容差各分一半給兩個子區間。這只是分配預算,不自動證明真實誤差滿足預算。積分接近零或發生抵消時,相對容差需要另外處理。
定理/命題
定理 6.6.1
(差值究竟估計甚麼)
令 為固定緊緻區間, 且 。對面板 ,當 時,下列展開一致成立:
因此 ,且 。大 中的常數可以依賴 的界。以上結論不能推出 。
定理 6.6.2
(由導數界得到的保證)
設 ,已知 。將區間分成有限個長度為 的面板 ,每個面板計算兩子區間 Simpson 值之和 。在精確算術下,
若已知各面板上的界 ,可在相應項中替換全局界 。若返回修正值 ,則另一個有效上界是各項 之和。
導數界必須對整個面板成立,不能僅由五個取樣點上的數值斷言。可以用已證明的解析不等式或合適的區間算術求界。函數值近似、求和捨入、溢出以及端點捨入都需要額外控制;上述精確算術保證本身不涵蓋這些誤差。
證明思路或證明
證明
(在面板中點作 Taylor 展開)
在 處將函數 Taylor 展開至五次。積分及兩種規則都關於 對稱,並且精確積分所有至多三次多項式,因此五次奇項也消失。對 ,直接計算得 、,故 。乘上 Taylor 係數 ,得到粗規則主項 。在每個子面板中心重新展開該四次式,其餘項次數至多為三,規則對它們精確;兩子面板寬度減半,故其四次誤差之和變為原來的 。當六階導數有界時,Taylor 餘項逐點為 ,積分與加權和各增加一個長度因子,故餘項均為 。
兩式相減得 ,於是得到定理中的修正關係。特別是當 時,主項消失,估計量的相對解釋更不可靠。
證明
(把單面板 Simpson 誤差界相加)
單個寬度為 的 Simpson 面板誤差界為 。對寬度均為 的兩個子面板分別應用並相加,得到 。再對所有面板求和並用三角不等式,即得整體結論。由於 ,對修正值再用一次三角不等式便得到第二個界;這並不聲稱修正一定改善認證誤差界。
證明透視
為何一個證明給出估計,另一個給出上界
第一個證明只有一個關鍵步驟:兩種規則都關於 對稱,且對三次式精確,所以除餘項外,各自的誤差都只是 的倍數;面板減半時,四次誤差乘以 。 中的 完全來自這個縮放。假設 只用於餘項:令它逐點為 ,再對總質量為 的權重積分後成為 。其常數沒有算出,所以證明只以「相差未知的 項的等式」作結,從不給出不等式。這就是即使 非常光滑, 仍然只是估計的原因。
第二個證明完全不看 。它只用 及一個在整個面板上都有效的數 ,對每個子面板套用已知的單面板不等式,再把絕對值相加。若去掉關於 的假設,取樣值中沒有任何數據能代替它,下面的反例正說明這一點。
例題詳解
例題 6.6.3
(四次函數的完整自適應計算)
取 ,區間為 ,絕對容差為 。根面板上 、、,故 ,需要二分,並給每一半分配 的容差。
在 ,粗、細值分別為 和 ;在 ,分別為 和 。兩個差值都是 ,故兩個估計量都是 ,兩葉均通過。修正值分別為 和 ,總和是 。
根面板用了五個不同的取樣點;檢查兩個子面板只需再計算四個點,即 的奇數倍位置。共享端點和中點都被重複利用。此四次函數碰巧被修正公式精確積分,但停止條件並不保證一般函數也如此。
例題 6.6.4
(同一棵樹上的嚴格保證)
對 可取 。每個半區間細規則的誤差界是 ,兩者之和 。返回兩項細規則之和 ,便在精確算術下得到不超過 的嚴格誤差界。事實上此例恰好達到這個界:。修正結果恰為真值,是四次函數的特殊計算結果,而不是由估計量保證的。
例題 6.6.5
(邊界情況:平方根奇點)
在 上取 ,其積分為 。這裏 在 附近無界,所以對接觸原點的面板,兩條定理都不適用。準確至六位小數,根面板的值為
細值的實際誤差為 ,約為 的八倍。若 ,啟發式測試在根面板便接受,返回 ,其誤差 超出容差四倍以上。修正的符號正確,但由 縮放預測的大小是錯的,因為該縮放假設四階導數有界。必須在 附近進一步細分,或作 之類的變量代換,估計量才可信。
可以實作的遞歸
下面用精確實數描述數學算法。simpson(u,v,fu,fm,fv) 使用上面的公式;eval(x) 要麼返回函數值,要麼報告失敗。depth 是非負整數;浮點實作還必須檢查新節點嚴格有序。
integrate(f, a, b, tolerance, maxDepth):
require a < b, tolerance > 0, maxDepth >= 0
m = (a+b)/2
evaluate fa=f(a), fm=f(m), fb=f(b), or return failure
A = simpson(a,b,fa,fm,fb)
return visit(a,b,fa,fm,fb,A,tolerance,maxDepth)
visit(u,v,fu,fm,fv,A,tau,depth):
m = (u+v)/2; l = (u+m)/2; r = (m+v)/2
if nodes are not strictly ordered: return failure
evaluate fl=f(l), fr=f(r), or return failure
left = simpson(u,m,fu,fl,fm)
right = simpson(m,v,fm,fr,fv)
B = left + right; D = B-A
if abs(D)/15 <= tau: return success(B+D/15, abs(D)/15)
if depth == 0: return failure
leftResult = visit(u,m,fu,fl,fm,left,tau/2,depth-1)
rightResult = visit(m,v,fm,fr,fv,right,tau/2,depth-1)
if either child failed: return failure
return success(leftResult.value+rightResult.value,
leftResult.estimate+rightResult.estimate)
返回的估計量是接受的葉節點指標之和,不是經過證明的誤差上界。程式可以在失敗時附上部分結果,但不能聲稱它滿足容差保證。實作時還應處理非有限函數值或中間結果。浮點代碼需依據允許的數值範圍選擇避免溢出的中點公式,並檢測節點重合與容差下溢;僅限制遞歸深度並不能認證精度。
若要嚴格保證,把接受條件改成 ,返回 及此界,其他分割和失敗規則不變。若已知全局 有限且算術精確,均勻二分至深度 時,每個葉節點的界與所分配容差之比為 。故足夠大的有限 保證接受,葉預算求和又證明整體誤差不超過 。此論證在所有節點使用同一個全局 ;更精細的局部界也可認證葉節點,但各自需要有效界和終止論證。如果最大深度 maxDepth 過小仍會失敗。這個終止論證不適用於有任意不光滑或不準確函數值的啟發式測試。
常見錯誤
反例模式
五個樣本不能認證所有光滑函數
在 上令 。它是非負多項式,僅在有限個點為零,所以積分嚴格為正。兩種根面板規則只看到零,因而 ,無論正容差多小,啟發式測試都會接受。將 乘以常數可使漏掉的積分任意大。這不違反導數界定理:放大函數時,導數界也改變。
各葉估計量的和低於預算只是一項記賬結果,並不證明真實誤差受這些估計量約束。反過來,嚴格界可能遠大於實際誤差;不能認證也不代表答案必然錯誤。即使最後的樹不均勻,每個子面板分得父面板一半預算仍是有效分配,因為所有葉預算之和等於根預算。
概念視角結構
三個不同的斷言
差值衡量兩個有限取樣公式的一致程度;漸近模型將差值聯繫到誤差主項;嚴格保證則在定量假設下控制整個誤差。三者不能不經論證地互相替代。
常見錯誤
(修正方向弄反)
由於 ,而模型給出 ,修正值是 。若寫成 ,或改用 ,答案便離積分更遠。對 上的 ,正確公式恰好給出 ;符號反轉則得 ,其誤差 是未修正值 誤差的兩倍。
常見錯誤
(把整個容差傳給每個子面板)
若每個子面板分得 而非 ,有 個葉的樹可接受總和接近 的局部估計。正是減半規則使葉預算之和等於根容差;沒有它,連記賬上的總數也會超出要求的預算。
快速檢查
快速檢查
(若 ,加到 上的修正是甚麼符號?)
回想 與 的定義。
解答 · 答案
答案是正號:。這只回答模型中的符號問題,並不證明 低估積分。
練習
快速檢查
(在 上取 和 。求根面板細規則的嚴格誤差界;它能否認證 ?)
對長度 的單一面板使用保證公式。
解答 · 答案
界為 ,大於 ,所以此測試不能認證該容差。對於本四次函數,這也是細規則的實際誤差:。
快速檢查
(證明任意有限二叉分割樹的所有葉預算之和等於根預算。)
追蹤一次分割對總和的影響。
解答 · 答案
最初唯一葉節點擁有全部預算。每次分割把預算 的一個葉換成兩個預算 的葉,不改變總和。對有限次分割歸納即可。
快速檢查
(若每個函數樣本的絕對誤差至多為 ,求精確加權運算下分區細 Simpson 值之和的擾動界。)
Simpson 權重均為正。
解答 · 答案
每個子 Simpson 規則的權重為正,總和等於子區間長度;故面板 上的擾動不超過 ,整體至多 。這裏不假設重複利用的樣本相互獨立。捨入以及假設界之外的求值偏差仍需另行處理。
快速檢查
(將 寫成五個等距根節點上的加權公式,並說明它為何精確積分所有至多五次多項式。)
寫 ,再收集每個樣本的係數。
解答 · 答案
設 、,則 ,合併權重得 。兩原規則均精確積分至多三次多項式,修正恰好消除四次誤差;對稱性使以中點為中心的五次冪在規則和積分中均為零。線性組合說明至多五次均精確,並不說明六次也精確。