讓新樣本發揮作用
當函數取值昂貴,我們仍希望近似 ,其中 。將區間等分為 個小區間,步長為 ,複合梯形值為
將步長減半時,無須重新計算所有舊節點。新增的 個點恰在舊相鄰節點的中間,所以在精確運算下,
檢查權重:在 中,舊內部節點的權重是 ,舊端點的權重是 ,每個新中點的權重是 ,與右邊完全一致。若取值成本高,應保存舊函數值。累加、節點構造和函數值的捨入誤差,與下面的精確恆等式是不同問題。
逐列消去不同次冪
定義 6.5.1
(Romberg 表)
從 開始,令 ,其中 。一旦兩個相鄰網格的第 列已算出,就定義
由數 ()組成的三角形陣列稱為 Romberg 表。
分母隨列數改變:每一列都用 並不能實現同樣的消項。第一列比較步長為 和 的值,消去 項;第二列比較剩餘主導項與 成正比的估計,依此類推。
定理 6.5.2
(在明確展開條件下外推)
令 。固定整數 ,假設當 時,
其中係數與 無關。那麼對每個固定的 ,
這是固定列在網格足夠細時的漸近結論,並非單個表項的誤差保證。
消項的證明
證明
(對列序號作歸納)
第零列具有假設中的展開。假設第 列展開到 後,首個可能非零項為 ,各係數均與 無關,餘項為 。較粗網格滿足 ,其對應項就是 。將細網格的值乘以 再減去粗網格的值,便消去這一項。分母 非零。其餘偶次冪仍有與網格無關的係數;由於 固定,餘項仍為 。由歸納法得證。
證明透視
展開式比單個誤差界提供更多資訊
證明中唯一的一步,是在兩個網格之間消去 。這只因為係數 在兩個網格上是同一個數才成立;「常數與 無關」的假設正是用在這裏。只有 ,並不能說明相鄰網格的帶符號誤差具有相同的首項係數。表格消去的是展開式中的共同項,而不是任何被 控制的誤差。
另有兩點使歸納得以完成。 的項 變為 ,係數仍與 無關,所以新的一列具有同樣形式的展開。餘項至多乘以 ;這只因 固定才是常數,定理對沿對角線 前進的情況沒有給出任何一致結論。
對於足夠光滑的函數,Euler–Maclaurin 公式給出這樣的偶次冪展開。例如若 ,則
因此定理可取 。這些係數來自該公式,並非僅從表格推斷出的誤差界。若某個導數差為零,相應首項係數可能消失,特定問題的收斂因而更快。分段光滑、端點奇異或被採樣網格漏掉的振盪,都需要另行分析;增加表格深度本身不能驗證展開條件。
遞推式還有另一種等價的讀法,可以解釋其中的權重。
概念視角代數
Romberg 即外推到零步長的多項式
令 、,則 。設 是關於 、次數至多為 的多項式,在 時於 取值 。插值多項式的 Neville 遞推在 處為
這正是 Romberg 遞推,所以 :每個表項用 的多項式穿過 個已算出的梯形值,再讀出它在達不到的步長 處的值。展開假設等於說:把 看成 的函數時,它能被這類多項式很好地近似。
第一外推列另有一個熟悉的名字。
命題 6.5.3
(第一列就是複合 Simpson 法則)
對每個 , 等於寬度為 的 個小區間上的複合 Simpson 法則,其中 。特別地, 是 個小區間上的複合 Simpson 值。
證明
(逐個節點比較權重)
以 ()標記細網格節點,並記 。在 中,每個端點的權重為 ,其他細節點的權重為 。在 中,端點權重為 ,偶數號內部節點權重為 ,奇數號節點不出現。相減後,端點得 ,奇數號節點得 ,偶數號內部節點得 。除以 得
即步長為 的複合 Simpson 法則。
四次函數的完整算表
例題 6.5.4
( 的精確算表)
取 上的 ,則 。梯形值為 、、。例如,加密公式給出
由上面的命題,第一外推列等於細網格上的複合 Simpson 值。現在把這些值放進完整表格:
| 0 | — | — | |
| 1 | — | ||
| 2 |
例如,,而 。最後恰好等於積分,是本多項式和精確運算的特殊情況。一般而言,有限次消項後仍有其餘誤差項。
更多算例
例題 6.5.5
( 的觀察收斂率)
在 上取 ,。精確地,
於是 、、。準確至六位小數:
| 誤差 | 誤差 | 誤差 | ||||
|---|---|---|---|---|---|---|
| 0 | — | — | — | — | ||
| 1 | — | — | ||||
| 2 |
梯形誤差依次縮小約 倍和 倍,趨近 項的因子 。第一列在一次減半中改善約 倍,正趨向 項的因子 。這裏 在 上光滑,且 ,首項係數確實存在,定理描述了這個趨勢;但它仍然沒有給任何單個表項提供誤差界。
例題 6.5.6
(邊界情況:週期被積函數與過粗的首個網格)
在 上取 ,則 。 的各階導數在 與 處相等,所以 Euler–Maclaurin 的每個係數都是零。取樣得 (兩端點的值都是 ),而 與 已是精確值。外推則給出
追溯到 的表項,比它們所用的最細梯形值(已經精確)還差。單一小區間太粗,無法分辨一個週期:它的誤差是混疊,而不是展開式的首項。這與定理一致,因為定理是 的漸近結論;它也說明由未進入漸近區間的網格構成的表項可能誤導。
數值一致不等於證明精度
反例模式
所有採樣點都可能漏掉積分
令 ,定義域為 。它連續、非負,在有限個零點之間為正,因此積分為正。然而,前面一、二、四個小區間的三層網格上,所有採樣值均為零。整個三角表都是零,相鄰表項完全一致。僅憑這個表,無法區分該函數和零函數。因此,若沒有額外資訊,例如有根據的導數界,表格不能保證誤差達到指定容限。
當誤差展開有根據且首項佔主導時,相鄰表項之差可作為實用指標。首項接近消失、網格尚未進入漸近區間、取值誤差或捨入都可能使指標誤導。可靠實作還要檢測浮點節點重複、非有限值和資源限制;除非另有誤差界,停止報告應將估計稱為估計。
常見錯誤
(每一列都用因子 )
權重 只適用於第 列。對四次函數的表使用 ,得 ,誤差仍約為 ;正確的 則給出 。第 列要消去的項與 成正比, 加倍時它乘以 。
常見錯誤
(跨越端點奇點作外推)
對 上的 ,導數在 處無界,梯形誤差並非偶次冪展開:它含有與 成正比的項。數值上,相鄰梯形誤差縮小的因子接近 ,第一列誤差 、、 亦然,而不是表格所針對的因子 。應先消除奇點,例如作代換 ,然後才使用 Romberg 權重。
練習與解答
快速檢查
(在 上由 加密至 ,需要哪些新點?)
新點位於相鄰舊節點的正中。
解答 · 答案
舊節點為 ;新中點是 。所以 。
快速檢查
(若 、、,計算 、 和 。)
第 列用分母 ,第 列用分母 。
解答 · 答案
依次為 、、。這些數相等本身並不能證明 。
快速檢查
(若第 列首個未消去誤差項為 ,為甚麼用因子 ?)
比較該項在步長 與 的網格上的值。
解答 · 答案
步長加倍使該項乘以 。將細網格估計也乘以此因子後,其首項與粗網格對應項相等,相減便消去。
快速檢查
(僅憑 ,能否證明 ?)
試考慮符號隨 交替的誤差。
解答 · 答案
不能。若某序列的誤差為 ,它滿足該界,但相鄰網格的帶符號係數不同:。外推後的誤差仍是 的非零倍數。係數相同的偶次冪展開提供了缺失的條件。