動機
儀器只在若干時刻量度數值,我們卻可能想知道兩次量度之間的函數值、某一瞬間的變化率,或整段時間的累積量。插值、數值微分及求積分別處理這三個問題,背後有共同做法:先用簡單函數配合取樣值,再對這個函數求值、微分或積分。這個觀點既解釋公式,也提醒我們公式能保證甚麼。
完全通過取樣點,不代表在點與點之間準確;無數光滑函數都可配合同一組有限數據。因此,誤差保證需要額外假設,例如未知函數的某階導數有已知上界。以下分開研究以近似函數取代原函數的誤差,以及輸入取樣值的擾動。電腦運算的捨入還可帶來第三種誤差,不能自動算進前兩項。
定義
定義 4.1.1
(插值多項式與 Lagrange 基底)
設 是相異實數節點, 是輸入值。以 表示次數不超過 的多項式空間,包括零多項式。插值多項式滿足每個條件 。Lagrange 基底及相應構造為
空乘積定為一,因此 也適用。相異節點保證分母非零。當 時 ,否則為零,故公式配合全部數據。對常數函數插值又得 。但係數可以為負,所以這未必是凸組合。
定義 4.1.2
(中央差分)
若 ,兩個取樣點給出中央差分
即通過兩個取樣點的直線斜率。
定義 4.1.3
(複合梯形法)
在 上令 、整數 、、,複合梯形法定為
它是連續分段線性插值函數的積分。內部節點由左右兩段共用,因此合計得到完整權重。這些定義都指對輸入值作精確算術。
表示函數至第 階的導數連續,端點導數由內部連續延伸。最高階導數的絕對值因此在緊緻區間有有限最大值,但如何找到實用的數值上界,仍須另作分析,不能僅從取樣表讀出。
定理 / 命題
定理 4.1.4
(插值的唯一性與餘項)
相異節點的任意數據恰有一個 插值。若數據為 ,且 ,其中區間包含全部節點及求值點 ,則當 不是節點時,在這些點的最小值與最大值之間存在 ,使
在節點誤差為零。若整段區間上 ,則絕對誤差不超過 。
命題 4.1.5
(數據敏感度與兩個離散化誤差界)
若取樣值的變化為 ,且 ,相應插值多項式滿足
若 且 ,則
若 且 ,則
光滑性及導數上界必須在所述整段區間成立,不能只檢查節點。若已知上界只適用於節點所涵蓋的區間,便不能直接套用於區間外的外推。
概念視角結構
同一組數據,不同的線性泛函
固定目標後,三種公式都是取樣值的加權和。插值求值的權重為 ,中央微分為 ,梯形積分則有總和等於區間長度的非負權重。各輸入值的絕對誤差分別不超過 時,權重絕對值之和決定最壞放大倍數,解釋了重建導數為何可能遠比積分敏感。
證明思路或證明
多加一個零點,得到插值餘項
證明
(唯一性與插值餘項)
Lagrange 公式已證明存在性。若有兩個插值多項式,兩者之差次數不超過 ,卻有 個相異零點。非零多項式不可能如此,故兩者相等。
固定不是節點的 ,令 ,並考慮
它在全部節點及 都為零,共有 個相異零點。依大小排列後,Rolle 定理在每對相鄰零點之間各給出一個 的零點,共 個。再對這些導數零點應用同一論證, 至少有 個零點。如此反覆, 在原來兩端極值之間至少有一個零點 。由於 ,而 是 次首一多項式,
代回 即得餘項。在節點直接用插值條件,不能除以零值 。
證明透視
額外零點如何把未知誤差轉為導數
選擇 的目的,是在插值已有的 個零點之外多加一點。反覆 Rolle 恰好到達第 階:插值多項式消失,首一乘積則變成已知常數 。所得 隨求值點而變,並非對每個 都共用同一點。
輸入數據的擾動
證明
(插值對數據的敏感度)
線性關係給出 ,三角不等式遂給出所述上界。對固定 ,將每個非零係數的誤差選為 ,便可取到 。這是各項絕對誤差受限時可達到的最壞情況,不是隨機誤差總會同向累加的斷言。合併兩種誤差得
中央差分的誤差平衡
證明
(中央差分的二階截斷誤差)
在 展開 Taylor 公式,分別有
相減後除以 ,偶次項消去,留下
兩個餘項點不必相同,但各導數的絕對值均不超過 ,故得 。若兩個輸入值各有不超過 的絕對誤差,差分值另有最多 的變化。因此,對不確定取樣值精確計算時,
前項隨步長縮小而減少,後項卻增加。當 ,在所有正步長中令此上界最小,得到 ;還須確認步長留在光滑性假設的區間內。這只是最小化已證明的上界,不一定最小化實際誤差。公式亦未計入形成 、函數求值、相減及相除時的捨入;分析完整硬件算法須另行說明這些運算。
梯形法為何出現十二
證明
(逐段估計梯形法誤差)
在長度為 的一段 ,令 通過兩個端點值。線性插值餘項給出
故 。積分此不等式,不能把未知的 當常數提出:
將 段相加便得 。若 ,由 可知 ,故凸函數的梯形估計偏大。
所有梯形權重非負,總和為 。每個取樣值的絕對誤差若不超過 ,積分估計的變化便不超過 ,此數據模型下與 無關。這裏各項分別受限不表示概率上的獨立:允許任何符號及相依關係。增加分段數可減少截斷誤差上界,卻不減少這個最壞數據界。要利用統計抵消,必須另加測量模型;同一內部節點始終是兩段共用的一個輸入值。即使權重非負,浮點加總仍可能另有誤差。
例題詳解
例題 4.1.6
(二次函數的求值與雜訊放大)
在 對 取樣,得到 。在 ,
所以 。唯一性也保證這個結果,因為 。但 ,若三個值的誤差為 ,答案會偏移 。求值點位於節點區間內,仍不能保證全部權重非負。
例題 4.1.7
(在零附近對正弦函數作差分)
對 ,有 及 。由 ,截斷誤差不超過 。當 ,上界是 ,實際誤差約為 。若每個輸入值有 的絕對不確定性,上界另加 。改用 ,截斷界雖降至約 ,數據項卻升至 ;步長變小可以削弱整體保證。
例題 4.1.8
(達到梯形誤差上界的例子)
對 上的 ,取 、,
精確積分是 ,故偏大 。定理中 ,上界恰為 ,等號成立。若三個取樣值各有至多 的誤差,權重 給出至多 的數據誤差;精確算術下總保證為 。
常見錯誤
反例模式
更小步長可以放大微分雜訊
「減小 必定改善數值導數」即使對真函數 也不成立。輸入容許的值 、,中央差分便是 ,但真導數和截斷誤差皆為零。固定 時,此值隨 無界增長。正確說法是:縮小步長可減少光滑函數的截斷上界,但數據不確定性仍要獨立分析。
常見錯誤
(以為次數越高必定越準)
提高插值次數並無無條件的準確度保證。餘項涉及更高階的導數上界 及另一個節點乘積 ,數據敏感度 亦可能增大。精確插值帶雜訊的數據只會重現雜訊,並不能去噪。
常見錯誤
(把餘項中的點當作常數)
插值餘項中的 以未指明的方式依賴 。把餘項公式當作 固定來求導,並無根據。因此中央差分的誤差直接由 Taylor 公式推出,而不是由插值餘項求導得來。
總結
插值在指定多項式空間內唯一,但逼近未知函數的準確度需要光滑性數據。反覆 Rolle 給出餘項,Lagrange 權重的絕對值總和則量度取樣敏感度。中央差分同時有 截斷界及 數據項。複合梯形法有 全局界,對凸函數偏大,非負權重也保留簡單的數據誤差界。每個結論均須連同其假設及誤差模型理解。
練習
快速檢查
(在節點 插值數據 ,求 的值。若各值的絕對誤差至多 ,求可達到的最壞不確定性界。若數據是 上滿足 的精確取樣,再求該點的近似誤差界。)
把插值多項式寫成 ,並用 的餘項。
解答 · 答案
,故 。權重為 ,絕對值總和為一,所以數據界是 ;兩個誤差皆取 即達到。餘項界為 。若兩種不確定性並存,合併界為 。
快速檢查
(對 計算 及誤差。它是否達到 的上界?加上取樣誤差至多 的項,當 時在 中最小化此上界。)
展開兩個立方, 的偶次項會消去。
解答 · 答案
展開得 ,故 ,誤差恰為 。合併上界是 ,其導數為 ,在 為零,且由負轉正。上界在正半軸兩端皆趨於無窮,故這是最小值點。若取樣區間受限,還須檢查此步長是否可用。
快速檢查
(對 上的 ,分別用 計算 、誤差及誤差比。若 ,利用定理保證截斷誤差不超過 的最小正整數 是多少?)
在梯形法誤差界中代入 。
解答 · 答案
、,減去 得偏大誤差 ,前者是後者四倍。要求 ,即 ,最小整數為 。此例恰好達到界,但其他函數未必如此。
快速檢查
( 及 在節點 的取樣均為零。比較兩者在 的值及在 的積分,說明當 改變時,單憑取樣不能給出一致的插值或積分誤差界。)
先計算 ,再比較導數上界。
解答 · 答案
在 ,兩函數值為 ;積分則為 。同一組零數據可對應隨 任意增大的答案差。每個 都光滑,但 並無一致上界。若另給共同導數界,便能限制 並恢復誤差保證;只有光滑性而無定量界仍不足夠。