誤差估計不自動成為證明
自適應求積程式常比較粗網格與細網格的結果。兩者接近是有用的資訊,但取樣點可能漏掉窄峰或振盪。若要得到嚴格保證,必須有某個條件限制樣本之間的函數行為。這裏使用的條件是每個子區間上的二階導數已有經過證明的界。
定義 7.4.1
(中點保證所需的數據)
設 且 。取分割 ,記 、。保證所需的數據包括:
- 已知 ,使整個 上都有 ;
- 對每個中點,有計算區間 確實包含精確值 。
這些數據可以來自解析不等式或嚴格捨入的區間計算;一般來說,只在中點計算一次 並不能證明整個區間的界。
定理 7.4.2
(有保證的積分區間)
在上述假設下,
若要把該區間作為電腦證明,分割位置、精確中點、取樣區間及區間端點運算都必須精確表示,或用向外捨入包圍;特別是取樣區間必須包含證明所用精確中點的函數值。
證明
(Taylor 餘項與關於中點的對稱性)
當 位於第 個子區間時,Taylor 定理及餘項界給出
積分後,線性項因對稱性消失,並且
因為 ,用中點值的下界或上界替換 時,分別保持相應的不等式。對所有子區間求和,就得到 (1)。
證明透視
保證來自哪裏?
這裏有兩種不同的不確定性:中點函數值位於計算區間內,而曲率界控制未取樣的圖像。式 (1) 把兩者結合。僅用區間計算包住取樣值,不能控制取樣點之間的變化;僅有導數界而沒有安全捨入,也不能保證浮點端點正確。
常見錯誤
(每個區間只在一點取樣 )
中點處的 值可能很小,而 在區間內其他位置卻大得多。 必須在整個區間上界定 ,依靠解析不等式或 在該區間上的區間包圍。單一取樣只給出估計,而不是保證。
一個計算與加密網格的作用
例題 7.4.3
(二次函數:一段與兩段)
對 上的 ,精確中點函數值為 ,而 。只用一個區間得到
等分成兩段時,中點和為 ;由 (1) 得 ,包圍區間縮為 。真實積分是 。此處上端恰好達到真實值,是這個凸二次函數的特殊性質;(1) 則不需要預先知道 的符號。
命題 7.4.4
(包圍區間的寬度)
若所有 ,記 ,則
如果取樣本身也是區間,(1) 的寬度為
特別地,若每個中點區間寬度至多為 ,總寬度至多為 。
證明
(把各區間的寬度相加)
。(1) 的上端減下端為 。由 及 ,它至多為 ,而 (2) 把 界為 。
因此在精確取樣、整個分割序列共用同一個上界 時,只要最大網格寬度趨於零,包圍區間的寬度 就趨於零。 的連續性保證理論上存在有限整體界,但數值方法必須實際給出一致有界且有效的 。加密網格只能控制 (3) 的第二項。若要求達到指定寬度,取樣區間和算術運算也必須足夠精確。自適應算法可以按各項經過驗證的貢獻 決定要細分哪些子區間,但細分後必須重新計算或保留有效的導數界;子區間中點則是新的取樣位置。若要由 (2) 保證終止,還需要細分確實使 ,並能把取樣和算術不確定性降到足夠小。固定精度可能帶來無法透過加密網格消除的正誤差下限。
例題 7.4.5
(四個區間上的正弦積分)
取 上的 ,,分成四個等長區間,。精確中點值 約為 ,和約為 。中點和為 ,。包圍區間約為 ,包含精確值 。只用一個區間時,區間寬得多:。
例題 7.4.6
(零曲率與區間取樣)
對 上的線性函數 ,只用一個區間, 是有效的界,所以 。精確中點值為 ,包圍區間為 ,與 吻合。若取樣只知道位於 ,則 (3) 給出寬度 ,包圍區間為 。其餘的寬度全部來自取樣區間,而不是曲率。
反例模式
誤差估計為零,積分仍可能為正
在 上令
單區間 Simpson 公式和分成兩半的 Simpson 公式,其全部取樣點都屬於 ,所以結果都為零。兩者之差是零,但 連續、非負,且在這五點以外為正,因此 。事實上其積分為 。若沒有關於被積函數的額外資訊,兩個公式一致不能證明誤差很小。
這個限制並非 Simpson 公式獨有。對任意固定有限取樣點,把對應一次因子相乘後再平方,就得到一個光滑非負函數:它在全部取樣點為零,積分卻為正。即使只使用點值的確定性自適應算法在零函數上經過有限次取樣後停止,相應乘積函數的任意正常數倍在這些點也給出同樣的零值,因此算法會走同一條取樣路徑。放大係數能使該乘積函數的正積分任意大;若不限制函數類別,任何固定有限寬度的區間都不能同時對兩者有效。
常見錯誤
(把端點捨入到最近值)
用普通的就近捨入來計算端點,所得保證可能差一個末位單位:下端可能向上捨入,或上端向下捨入,儲存的區間便不再包含精確的包圍區間。應按定理要求,下端向下捨入、上端向上捨入。
練習與解答
快速檢查
(在 上對 使用一個區間、精確中點值和 ,應用 (1)。)
解答 · 答案
中點公式為 ,,故區間為 。
快速檢查
(在 上對 使用 個等長區間和精確中點值,給出保證區間寬度的上界。)
解答 · 答案
、;由 (2),。
快速檢查
(對 的分割,若每個中點計算區間寬度為 ,取樣區間對 (3) 的貢獻是多少?)
解答 · 答案
若各區間寬度都恰為該值,貢獻為 ;若只是至多為該值,這就是上界。
快速檢查
(為甚麼每個區間只取樣一次 ,本身不能證明 是有效上界?)
解答 · 答案
連續二階導數在取樣點可以很小,而在區間其他位置更大。
快速檢查
(如果粗、細 Simpson 公式的結果一致到機器精度,還需甚麼資訊才能得到嚴格包圍區間?)
解答 · 答案
例如,若每個區間的導數界經過驗證,取樣值得到嚴格包圍,且算術向外捨入,就可用 (1) 給出中點求積的嚴格區間;兩次計算一致本身不能提供這些界。