動機
積分涉及整個區間,電腦卻通常只能取得有限個函數值。梯形法使用分段直線;更高精度的方法可以利用對稱、對更大多項式空間的準確性,或自由選擇節點。不過,準確性仍需函數假設。一個對所有三次多項式準確的公式,未必能看見恰好避開節點的狹窄峰值。
本節區分兩種誤差資訊。已知導數上界可提供嚴格的先驗保證;粗細網格之差則可在漸近模型下估計誤差。自適應方法利用後一種資訊分配計算量。小的差值是模型下的證據,嚴格認證則需要真正控制未知函數的假設。
定義
求積公式為 。代數精度是它對所有次數不超過該數的多項式都準確的最大整數。積分和求積都是線性的,因此只需檢驗單項式 。
在 上取 個等長小區間,。複合中點公式為
當 為偶數,複合 Simpson 公式為
Gaussian 構造使用內積 。令 是與所有低次多項式正交的首一 次多項式。它存在,因為可從 減去其在 上的正交投影。相應 Gram 矩陣正定:非零多項式的平方積分嚴格為正。
誤差估計中設 ,並假設
其中固定 ,主係數 。Richardson 外推比較兩個步長以估計或消除主項。非零條件與比值解釋有關;若主係數為零,更高階項可能主導。這是關於一整族計算的假設,並不是兩個數值相近便能證明的事實。
定理/命題
定理 6.1.1
(中點與 Simpson 的光滑性誤差界)
若 且 ,則
若 、 為偶數,且 ,則
中點公式的代數精度為一,Simpson 為三。凸函數滿足 ;若四階導數非負,則 。兩個結論均可能取等號。
定理 6.1.2
(Gaussian 精度與正權重)
有 個相異根,全部在 。以這些根為節點, 表示第 個節點的 次 Lagrange 基底多項式。令 ,則公式對 準確。每個權重嚴格為正,權重和為二。任何只用 中 個實節點的公式,都不能對全部 準確。
若樣本絕對誤差各不超過 ,結果擾動不超過 。映到 後,界為 。
這些數據界針對擾動輸入的精確加權和,不包括浮點求和或函數求值本身的算法誤差。正權重在這個絕對數據模型中避免額外的抵消放大,但不能補救節點完全沒有捕捉函數結構的問題。
實際還需決定是在一個區間上增加代數精度,還是把區間細分。前者改善當前區間的多項式準確性,後者把局部困難隔開,取得的是不同資訊。函數求值可能很昂貴,所以成本常應按不同取樣點的數目計算。複合公式必須按各子區間長度縮放權重,並按實際局部權重合併共享端點貢獻,例如相鄰梯形各自給公共端點一個半權重。這些不是附屬記賬,而是所實施的數學公式本身。
證明思路或證明
中點對稱與 Simpson 核
證明
(Taylor 對稱與正核)
在寬度為 、中心為 的小區間,Taylor 定理給出 ,其中 。奇函數的一次項在 上積分為零,餘項上界積分為 。將 個界相加即得全局結論。凸性給出 ,再積分得到低估性質。
對 Simpson,先在 令 ,其中 。直接代入可見 消去 。從 展開的積分型 Taylor 定理將 函數寫成三次多項式加上
作用 並交換有限和與積分,得 ,其中
當 ,取樣的截斷三次項只有端點一有貢獻,故核為 ,化簡即上式。負半軸可直接計算或利用 的對稱。於是 。將區間映到 ,積分貢獻一次縮放,四階導數貢獻四次,共為 。相加 個雙小區間,得到 。核非負也證明誤差符號。分別代入 和 ,說明兩種公式的代數精度不能再提高。
正交如何加倍代數精度
證明
(數根與多項式除法)
設 在 中改變符號的根為 。若 ,取 ;沒有這種根時取一。乘積 在區間中不再改變符號,並在某個小區間非零,所以其積分不可能為零。但 ,正交性要求積分為零,矛盾。因此至少有 個變號根。次數恰為 ,故所有根都是相異的內部單根。
對 做多項式除法,寫成 ,其中 。正交性使第一項積分為零,節點處 又使其求積為零;插值權重準確積分 ,所以整個公式準確。再對次數為 的 使用準確性,得到
常數函數的準確性給出權重和。最後,節點乘積的平方是次數 的非負多項式,積分嚴格正,但所有節點值為零。因此任何這些節點上的公式都不可能準確積分它。最優代數精度並不等於對每個非多項式函數都最優。
證明透視
正內積的兩次使用
證明的關鍵是一次除法。寫成 ,便把 上的準確性化為 上的準確性;對任何 個相異節點,插值權重都能提供後者。剩下的 被處理兩次:因 ,正交性使其積分為零;因節點是 的根,其求積亦為零。節點的選取只在這裏起作用。
內積的正性也用了兩次。在數根時,符號不變的非零多項式 的積分必須非零。在 中,準確性被用於次數 的多項式,所以權重為正是額外精度的推論,而不是另外的計算。最優性一步以單一測試多項式 (次數 )結束論證;它對任何 個節點都成立,不論是否為 Gaussian 節點。
自適應估計究竟假設甚麼
在給定漸近模型下,
所以細網格的主誤差估計及外推值為
的主項抵消後只有 ;要斷言明確的更高階,需要更強的展開及受控餘項。Simpson 取 ,分母便是十五。自適應 Simpson 比較父區間與兩個子區間,估計足夠小時接受細結果或修正值,否則繼續細分。把父容差分配給子區間,可以保證有效局部上界之和不超總預算,卻不能把啟發式估計變成嚴格上界。
實際停止還要處理最大深度、函數求值失敗、浮點節點已無法區分,以及容差低於輸入或算術誤差下限。遇到這些情況應如實報告,不能把未達目標寫成成功。重用共享端點和中點可以節省求值並保持一致。當積分接近零時,還需絕對容差;單純相對容差可能沒有可用意義。
例題詳解
例題 6.1.3
(四次函數上的兩種公式)
在 積分 ,真值為 。兩個小區間的中點公式為 ,是低估。Simpson 為 ,高估 。由於 、,定理上界也是 ,恰好達到。
例題 6.1.4
(推導二節點 Gaussian 公式)
正交性給出 ,節點為 。對稱及常數矩條件給出兩個權重均為一,故 對三次多項式準確。但對 ,它給出 ,真積分為 。固定樣本數的最優代數精度仍然有限,不能解釋為對所有光滑函數準確。
節點是一個對稱三對角矩陣的特徵值,權則由其特徵向量給出。
自然延伸的下一個問題
m 很大時如何計算節點?
節點是一個對稱三對角矩陣的特徵值,權則由其特徵向量給出。
首一多項式滿足 ,其中 。因此 的根正是 對稱三對角矩陣的特徵值;該矩陣對角線為零,次對角元素為 。若 是對應 的單位特徵向量,則 。當 時,這給出 及兩個為一的權。
例題 6.1.5
(外推消去已知主項)
對於 的 ,複合 Simpson 的誤差恰為 。於是 、,差的絕對值是 。細結果的估計為 ,恰等於真實誤差;修正值 。這裏恰好準確,是因為該多項式沒有後續 Simpson 誤差項。
常見錯誤
反例模式
粗細結果相同不代表沒有誤差
在 令 。它非負,在有限個零點之間嚴格為正,所以積分嚴格正。父 Simpson 區間採樣 ,兩個子區間另外採樣 。函數在這五點全部為零。因此粗細結果及誤差估計都為零。函數非常光滑也不能排除這種失敗;認證仍需定量導數界或其他經過驗證的函數類別約束。
誤差階描述一個極限過程,不能保證最初的粗網格已進入漸近區間。間斷、端點奇異、快速振盪和不準確函數值都可能破壞模型。Gaussian 節點在內部,不會自動解決端點行為。細分增加成本,也不一定減少數據不確定性。報告必須說明目標是由證明上界、模型估計,還是僅由迭代上限結束。
概念視角結構
代數精度也是資訊預算
選擇 個 Gaussian 節點及權重,使矩條件可以滿足到 次。節點乘積的平方證明下一次已經出現不可避免的盲點。自適應方法在比較提示困難之處取得新樣本,但沒有額外函數約束,有限確定性取樣無法排除所有隱藏峰值。
常見錯誤
(只映射節點而忘記權重)
在 上,Gaussian 節點為 ,權重為 。只縮放節點是常見的疏忽。對 ,映射後的二節點公式節點為 , 在兩點的值之和為 。用正確權重 ,公式恰好給出 ;用未縮放的權重 ,則給出 。
常見錯誤
(把 Simpson 的分母用於其他階的公式)
分母 取決於被加密公式的階 。梯形法的 。在 上取 ,有 、,細結果誤差為 。正確估計 與之相符;除以十五則得 ,小了五倍。
總結
中點對稱給出二階全局界,Simpson 的正四階導數核給出四階及誤差符號。正交多項式根產生正 Gaussian 權重與最優代數精度。Richardson 比較依賴可辯護的漸近模型;自適應能分配計算量及容差,但停止報告必須區分估計和保證。
練習
快速檢查
(對 上的 ,求 和誤差。在中點定理中代入 ,求保證誤差不超過 的最小 。)
單一小區間的中點法只取樣 。
解答 · 答案
,低估 。全局界為 ,這個二次函數恰達到該界。要求 ,所以最小整數為 。記號 表示導數上界,而不是兩個小區間的中點近似。
快速檢查
(把二節點 Gaussian 公式映到 ,列出節點及權重,積分 。若每個函數值誤差至多 ,結果不確定性多大?)
仿射映射 的比例因子為一。
解答 · 答案
節點為 ,仿射比例為一,所以權重仍均為一。兩個節點的立方和是 ,等於真實積分。絕對權重和為二,故數據界為 ,同號誤差達到此界。
快速檢查
(設精確模型 。取 ,求粗細結果誤差、細結果的 Richardson 估計,以及修正誤差。)
取 ,故分母為 。
解答 · 答案
粗誤差為 ,細誤差為 ,差的絕對值為 。除以 得 ,恰好是細誤差。修正值 的誤差為零,因為模型只有一個誤差項。若有未指定的高階項,一般仍會留下餘項。
快速檢查
(兩個子區間的誤差數字為 、,總絕對目標為 。若它們是已證明的上界,可作何結論?若只是 Simpson 差值除十五,結論如何改變?)
區分已證明的上界與模型估計。
解答 · 答案
若兩個數字是有效局部上界,且兩個區間覆蓋積分域,三角不等式給出總求積誤差不超過 ,另外排除的輸入和算術誤差仍需另計。若只是模型估計,只能作條件性的準確度說明;隱藏多項式反例表明它們未必控制實際誤差,應報告估計收斂而非嚴格認證。