消去有規律的誤差
數值近似的誤差有時具有可利用的結構。假設目純量 的近似滿足
其中 ,而且兩個步長對應相同常數 。那麼 的主導誤差為 。取 與 的適當線性組合,便可消去該項。
定義 7.11.1
(Richardson 外推)
設 的近似 的主導誤差為 ,且在每個步長上的 都相同。外推值定義為
權重 與 之和為一,因而保留 ;加權後的主導誤差之和為零。這個推導依賴真正的漸近展開,不能僅因為兩個近似值接近就套用結論。
定理 7.11.2
(主導誤差的消去)
設 ,其中 ,且對 有 。則對 ,
證明
(把展開式代入組合)
由於 ,展開式在兩個步長上都適用:
括號內為 。除以 得 ,而
證明透視
消去誤差需要相同的係數
證明中唯一用到誤差結構的一步,是括號變為零;它變為零,是因為 在 和 上乘的是同一個 。其餘只是三角不等式。反之,若只知道 ,同樣的計算只得到 ,階數並不比原來的界好:兩個步長上互不相關的誤差未必抵消。權重之和為一只用了一次,使 在組合中的係數為 。
例題 7.11.3
(對中心差分作外推)
對足夠光滑的 ,
故 ,且 。取 及 ,則 ,與 及 一致。取 和 ,得 、,所以
結果在這裏精確,是因為三次函數的展開在 項之後就終止;對一般的 ,只有 項被消去,仍餘下 的誤差。
以上結論描述的是精確算術中的截斷誤差。相近數相減以及近似值的組合可能放大浮點誤差,因此不斷將 減半未必改善計算結果。
梯形公式構成的表
設 是在均勻網格上計算 的複合梯形近似,網格間距 。對固定的足夠光滑的 ,Euler–Maclaurin 展開只含偶次冪:
使用的項數越多,需要的光滑性也越高;這裏把展開作為假設,而不是說連續性就能保證它成立。令 ;步長不斷減半,提示我們逐列作外推。
定義 7.11.4
(Romberg 表)
令 (),並對 定義
由數 排成的三角形陣列稱為 Romberg 表;第 列是梯形值的第 次外推。
為甚麼每一列的因子不同?因子 就是 (),即第 列所消去的那一項的階。下面的結果把這點說清楚。
定理 7.11.5
(Romberg 各列的精確度)
假設上述 的展開對每個 都成立,係數 不依賴於 ,且餘項以 為界。則對 及 ,
其中 ,。特別地,。
證明
(對列數作歸納)
時即為假設,。設結論對第 列成立,其中 。因 ,故 ,而係數 在 與 中相同。所以在 中, 的係數是 ,而 的總權重為 。除以 便得到所列的係數。當 時因子 為零,所以求和從 開始。餘項滿足
仍是 的常數倍。若 ,首個保留的項為 階;若 ,求和為空,誤差為 。
第一次外推正好是兩個子區間上的 Simpson 公式:
例題 7.11.6
(二次函數的一次外推)
在 上積分 。單區間梯形值為 ,兩個區間給出 。外推得到
恰好等於精確積分。這是因為這個二次函數的梯形誤差恰好與 成比例(這裏 );一個例子不能證明第一次外推對所有函數都精確。
例題 7.11.7
( 的三行 Romberg 表)
在 上積分 ,。梯形值為 、,並由 得
第 1 列使用因子 :
第 2 列使用因子 :
| 0 | 1 | 1/2 | ||
| 1 | 1/2 | 9/32 | 5/24 | |
| 2 | 1/4 | 113/512 | 77/384 | 1/5 |
與 分別是兩個和四個子區間的 Simpson 公式。最後一項精確,是因為多項式的 Euler–Maclaurin 級數會終止:這裏 ,只有第 2 列所消去的兩項。對非多項式的被積函數,這一項仍帶有 的誤差。
網格可能漏掉函數的結構
反例模式
兩次近似相等仍可能有非零誤差
在 上取 。它在 、、 處都為零,因此單區間與雙區間梯形值及其外推值都為零;然而真實積分為 。所以兩個近似值相等本身不能給出普遍誤差界。下一級網格能解析這一振盪:。這個函數十分光滑;問題是前兩級網格太粗,無法顯示它的結構。
基於表中相鄰數值的停止準則只是指標,除非另有假設能控制餘項。尖峰、尚未解析的振盪以及端點奇異性都可能破壞所假設的展開,或者把資訊隱藏在取樣點之間。即使展開成立,捨入誤差最終也會與截斷誤差競爭。應檢查被積函數和表的穩定性,並在把指標當作保證之前使用適用於該問題的誤差定理。
常見錯誤
常見錯誤
(權重中用錯冪次)
若 ,正確的組合取 。若改用 的公式 ,則得 :誤差仍是 階,只是符號反了。權重必須對應誤差中真正出現的冪次。
常見錯誤
(每一列都用同一個因子)
在 的表中,第二列需要因子 。若再用第 1 列的因子 ,得 ,而不是 。此時權重之和雖為一,卻沒有消去 項。
練習與解答
快速檢查
(假設嚴格有 ,求 。)
代入 ,再按 的冪次合併。
解答 · 答案
代入得 : 項消失,四階項仍在。
快速檢查
(為甚麼外推權重之和必須為一?)
想想目標 在組合中如何出現。
解答 · 答案
權重之和為一能保留共同目標 ,而不是改變它的倍數: 的係數是 。
快速檢查
(對 上的 ,求單區間梯形值及第一個 Romberg 外推值。)
兩個梯形值都來自同一條直線。
解答 · 答案
、,故 。梯形公式對仿射函數精確。
快速檢查
(如果表中兩個數在機器精度內相等,精確積分一定與它們相等嗎?)
回想 上的被積函數 。
解答 · 答案
不一定。上面的 給出相等的零近似,但真實積分為 。