為甚麼使用網格?
單一高次多項式會把所有樣本連繫到整個區間:新增一點便可能改變各處的插值,而且節點選得不好時,提高次數未必提高準確度。另一種簡單做法是用直線連接相鄰樣本。這會犧牲節點處的平滑斜率,卻令每個值只依賴左右兩個相鄰觀測,尤其適合本來就不等距的樣本。
以下組合所給樣本時假設使用精確算術;量度誤差與浮點運算是不同問題。
定義與局部權重
定義 5.3.1
(網格上的分段線性插值)
設 ,。給定數據 ,在 上定義
在共同節點,兩側公式都給出 ,所以 連續。每個區間內部的斜率為 。區間內兩個權重非負且總和為一,故插值介於兩端數據之間,數據為負亦然。這不代表插值在節點可微:兩邊斜率可以不同。
若 ,記插值為 ,並令 。下標描述整個劃分,並不要求等距。
定理 5.3.2
(不等距網格上的誤差與敏感度)
若 ,,則對 ,
在區間內部,
若每個給定樣本與 相差不超過 ,所得插值 滿足
導數估計只用於區間內部;插值在節點未必有導數。 時,上述近似誤差均為零。
證明:兩種不同誤差
證明
(餘項、平均斜率與凸數據權重)
對區間內部的 ,兩點插值餘項給出
其中 。證明是減去適當倍數的 ,使輔助函數多一個零點,再兩次應用羅爾(Rolle)定理。端點的誤差為零。到兩端的非負距離之乘積最多為 ,便得到第一個界。
斜率方面,微積分基本定理給出
由 ,在 處分開積分,便得到上述導數界。兩端距離的平方和最多為 ,故可進一步界定為 。這論證也適用於節點處的單側斜率極限;若左右斜率不同,不能因此說節點有導數。
最後,設樣本誤差為 。在每段上,含誤差插值與精確數據插值之差,是 的同一凸組合,絕對值最多為 。利用三角不等式便可把數據誤差加到近似誤差界。所有誤差都等於 時常數一可以達到;若數據品質不變,增加節點不會降低這種最壞情況的誤差界。
證明透視
為甚麼函數值與斜率的收斂階不同
證明以兩種不同方式使用 。函數值方面,羅爾定理在同一段內應用兩次,所以只涉及該段上的 ;因子 是兩個距離之積, 正由此而來。斜率方面,關鍵一步是把段上斜率寫成 在該段的平均值。於是斜率誤差是 的平均, 只作為 的 Lipschitz 常數出現:一個距離,一次 。
數據項依賴第三個事實:函數值權重非負且總和為一,所以樣本誤差只會被平均,不會被放大。數據斜率卻是權重為 的差商,沒有這個性質。這正是導數界需要精確樣本的原因,也是下面交替誤差反例成立的原因。最後由三角不等式把兩部分相加,論證閉合。
例子:不等距劃分
例題 5.3.3
(插值一個二次函數)
取 ,節點為 。在 上插值為 ,在 上則為 。於 ,插值為 ,真值為 。此處 、,局部函數值誤差界 恰好達到。節點 的左、右斜率分別為 和 ;雖然原函數平滑,插值卻有折角。
在 ,斜率誤差為 。當點從第二段內部趨向左端時,斜率誤差趨向 ,即上界 。因此這兩個常數作為這些假設下的一致界都是銳利的,儘管斜率誤差的上確界可出現在單側端點極限。
例題 5.3.4
(帶雜訊樣本的線性函數)
設 上 ,節點為 ,記錄所得樣本為 ,即誤差 。這是 的邊界情況:若數據精確,插值就等於 。因此函數值誤差界只剩數據項 。第一段的斜率為 ,插值為 ,誤差 留在 內。斜率誤差為 ,是這個數據擾動所容許的最大值。樣本本身已含的誤差,任何網格細分都無法消除。
例題 5.3.5
(為容許誤差選擇等距網格)
要在 上以精確樣本插值 ,並使一致誤差不超過 ,取 。定理要求 ,即
所以 個等距段已足夠: 給出 ,而 給出約 ,不合要求。證明只在每段內使用 ,因此 可換成該段的最大值 。在 附近這個最大值接近一,不等距網格在那裏可用長至約 的段。
對插值積分
逐段積分得到不等距複合梯形公式
命題 5.3.6
(不等距複合梯形公式的誤差)
若 ,,且 ,則
若改為對每個 都有 ,右方最多再增加 。
證明
(積分逐點餘項界)
對精確樣本,可直接積分逐點誤差界,而非把最大值乘以段長。令 ,
若 ,由於積分權重非負且總和為 ,還需加上最多 。
這些都是絕對最壞情況估計;兩個網格所得結果接近,單憑此不能認證誤差。
反例模式
函數值近似良好,斜率不一定良好
在 取 ,等距網格步長為 ,精確樣本交替受到 擾動。整個插值與零的距離仍不超過 ,但每段斜率的絕對值均為 。固定 而細分網格,導數誤差反而增加。必須同時考慮樣本精度和網格大小;上面的導數定理假設樣本精確。
常見錯誤
常見錯誤
(在不等距網格的誤差界中使用平均步長)
函數值誤差界由最寬的一段決定,而非 。對節點 上的 ,平均步長 會給出 ,但 的誤差卻是 。應使用 ,或更好的逐段界 。
常見錯誤
(在節點為插值指定導數)
插值在每個節點連續,但通常有兩個不同的單側斜率。在二次函數的例子中, 處的斜率分別為 和 ,所以 不存在。導數估計是開區間段上的結論;在節點只能報告單側極限。
練習
快速檢查
(對 上的 ,取節點 。計算 的插值、實際誤差及局部定理界。)
先找出包含 的一段。
解答 · 答案
第二段端點的值為 和 。從 到 佔段長的 ,所以插值為 ,誤差為 。代入 ,逐點界為 ,全段界為 。
快速檢查
(同一函數以 為節點。計算 上複合梯形近似,並與精確積分和立方和誤差界比較。)
兩段的長度分別為一和二。
解答 · 答案
公式給出 。精確積分為 ,誤差為 。取 ,誤差界 ,在此恰好達到。
快速檢查
(設 上 ,樣本誤差最多 ,。求一致函數值誤差界;能否認證誤差小於 ?)
把近似項與數據項相加。
解答 · 答案
誤差界為 ,不能認證小於 。這只是上界,並不證明實際誤差超過該門檻。
快速檢查
(每個節點誤差最多為 。求長度 的一段上斜率擾動界,並說明它可以達到。)
一段的斜率是兩個樣本的差商。
解答 · 答案
含誤差斜率與精確數據斜率之差為 ,絕對值最多 。取 、 即可達到。