動機
Lagrange 公式解決了存在性問題:在指定次數以內,有唯一多項式通過相異節點的數據。但實際計算還有不同問題。新增一次測量時,是否需要從頭計算?能否不展開單項式係數,直接計算高次插值多項式?如果可以決定測量位置,節點應放在哪裏?這些問題分別涉及更新、求值和實驗設計,不能把一個公式當成所有準確性問題的答案。
Newton 形式清楚顯示增加節點所添加的一項;重心形式將同一多項式重組為方便的求值公式;Chebyshev 節點使插值餘項中的某個最壞節點乘積最小。然而,三者都不能消除數據誤差本身。因此本節始終區分未知函數的近似、插值映射的條件,以及計算公式的捨入。
定義
定義 5.1.1
(差商與 Newton 形式)
設 是相異實節點,輸入數據記作 。差商遞歸定義為
差商只是數據的代數組合;記號並不假設輸入來自可微函數。Newton 插值式為
空乘積為一。求值時從最後一個係數開始,依次乘 再加下一個係數,得到嵌套算法,不必先轉成單項式形式。若數據按節點順序到達,已有係數可保留,僅需計算新的差商列。
定義 5.1.2
(重心權重與第二重心公式)
定義節點多項式及重心權重
所有權重非零。對於非節點,第二重心公式是
全部權重乘同一個非零常數不改變商。在節點應直接定義並返回 ,而非真的除以零。表面奇點來自表示,不屬於多項式。
完整差商表包含三角形排列的差及除法,預處理運算量隨節點數平方增長;係數備妥後,每個目標點的 Newton 嵌套求值只需線性運算量。一般重心權重的直接乘積構造也需要平方預處理,之後每次求值為線性。這裏計算的是算術操作數,不能解釋為準確性或位複雜度保證。同一組節點對應多個數據向量時可重用權重;節點改變後,權重也必須更新。
定義 5.1.3
(Lebesgue 常數與最佳近似誤差)
在包含節點的緊緻區間 上,以 表示連續函數的插值,定義
Lebesgue 常數 是一致數據範數下的插值算子範數,表示整個區間上最壞的絕對數據誤差放大。它由節點決定,並不等於浮點求值算法的誤差常數。 則問所有次數不超過 的多項式中,最佳近似能有多好;最佳多項式未必通過取樣點。
概念視角結構
表示、算子與最佳近似
Newton 式與重心式表示同一個線性插值算子。Lebesgue 常數研究算子的敏感度,最佳近似研究多項式空間能否接近未知函數。下面定理中的不等式將兩者聯繫起來,卻不把它們混為一談。高效求值公式也因此不能被誤讀為準確性定理。
定理/命題
定理 5.1.4
(Newton 係數與重心恆等式)
Newton 公式給出唯一插值多項式,其第 個節點乘積的係數正是前 個節點的差商。第二重心公式與這個多項式相同,非節點處的精確分母為 ,因此非零。對於 上連續函數,
若每個輸入樣本的絕對誤差不超過 ,再加上最多 的數據誤差。
定理 5.1.5
(Chebyshev 節點使首一節點乘積最小)
設整數 ,以 定義 Chebyshev 多項式。它的次數為 ,首項係數為 。在 上,所有首一 次實多項式的最小一致範數為 ,由 達到。其根為
將節點仿射映到 ,最小節點乘積範數為 。若 且 ,對應插值滿足
最後一個結論固定次數後優化導數型上界。次數增長時 也會改變,所以不能據此說任意光滑函數的誤差都趨零。使節點乘積最小與使 Lebesgue 常數最小也是不同問題。
這裏 表示節點數,對應前文的 ;插值多項式次數至多 ,可記為 。被優化的 次對象是節點乘積,而非插值多項式。
若只知道函數有三階連續導數,即使增加樣本,也不能直接使用需要十一階導數的界。無限可微函數的高階導數最大值也可能迅速增長。反過來,保守上界很大並不證明實際插值很差;它可能只是無法認證一次準確計算。報告結果時應區分已證明的上界、實際觀察的誤差,以及啓發式預期。
證明思路或證明
差商為甚麼是 Newton 係數
證明
(首項係數滿足差商遞歸)
前 個節點的 Lagrange 插值式,其 係數為
這個表達式滿足差商遞歸。取節點 的表達式,減去節點 的表達式,再除 。對內部數據 ,提取公共乘積後剩下
兩個端點係數直接計算也成立。從 歸納,即得 。再比較前 節點與前 節點的插值多項式:差在前 節點為零,次數至多 ,所以是節點乘積的常數倍。舊多項式次數較低,故這個常數正是新多項式的首項係數 。逐次添加便得 Newton 式。這個證明還說明差商對節點和數據的配對排列是對稱的,雖然計算表使用了某個順序。
有理式為甚麼仍是多項式
證明
(以節點多項式除兩個 Lagrange 恆等式)
Lagrange 基底滿足 。將插值式除以 ,得到重心分子。插值保持常數函數,因此 ;再除以 ,得到分母恆等式。兩者相除便證明公式。這裏討論精確分母,並未宣稱數值計算得到的分母絕不會發生捨入問題。在節點附近分子分母都可能很大,節點處應直接返回輸入值。
證明
(插值重現所有次數不超過 的多項式)
對任意 ,有 ,所以
第二項的範數至多為 。用三角不等式,再對 取下確界,便得最佳近似不等式。對數據擾動使用相同的絕對權重和,得到額外的 。誤差可以具有任意符號及相關性,不需要概率獨立假設。
反例模式
插值不等於最佳近似
一個誘人的說法是:插值多項式本身就是 中的最佳一致近似,所以因子 是多餘的。取 上的 、 及節點 。此時 ,,在 處達到。若直線 滿足 ,便須 ,但 ,矛盾;常數 的誤差恰為 ,所以 。由於 ,定理的上界 取等號。若改用節點 ,插值多項式是常數 ,正好達到 :差距取決於節點。
交錯極值如何給出最優節點乘積
證明
(交錯符號強迫過多的根)
餘弦恆等式給出 ,起點為 。歸納可得次數及首項係數。在 上,,並在 交替取值 。
設某首一多項式 的範數嚴格小於 。差 的最高次項抵消,次數至多 。在這 個相鄰極值點,因 , 的符號與 相反,故交替。介值定理在每兩個相鄰點之間給出一個根,總共 個相異根,與次數矛盾。因此任何首一多項式的範數都不能更小,而 確實達到該值。其根相異,所以它正是這些節點的首一乘積。仿射變換帶來因子 ,結合插值餘項便得導數誤差界。
證明透視
交錯證明究竟優化甚麼
論證由三個要素組成,各有確定的位置。首一假設只用一次:它令 與 的最高次項抵消,所以 的次數至多為 。等振盪性質提供 個點 ,在這些點 。嚴格假設 使 非零,且符號為 。若只有 ,某些 可能為零,符號計數便需要另外的論證。
介值定理接著在相鄰 之間的 個互不相交開區間內各給出一個根。次數至多 而有 個相異根的多項式恆為零,所以 ;但其範數恰為 ,與嚴格不等式矛盾,論證就此閉合。轉到 只用仿射變換及導數餘項。因此證明只在一致範數中優化節點乘積:它不涉及 Lebesgue 常數,也不涉及浮點求值。
例題詳解
例題 5.1.6
(新增樣本時保留原有計算)
節點 的值為 ,第一差商為一,故 。新增節點 、值 ,新的第一差商為三,第二差商為 。因此
在 ,嵌套求值得 。只增加一項能節省計算,但不能消除節點聚集或不確定數據的敏感性。
例題 5.1.7
(重心權重與數據放大)
節點 的權重為 ,也可統一縮放成 。在 ,未縮放的分母為 ;數據 的分子為 ,商為 。Lagrange 權重是 ,絕對和為 ,故樣本誤差可被放大到 。改變表示沒有改變問題的條件。
例題 5.1.8
(三個節點的兩種選擇)
的根為 ,節點乘積為 ,範數為 。等距節點 給出 ,在 的極值絕對值是 。若 ,兩者分別給出 與約 的上界。不過任意二次函數在兩組節點上都完全準確,說明上界比較並非每個函數的嚴格誤差比較。
常見錯誤
反例模式
增加等距插值次數可能更差
考慮 。在 取等距節點,於 ,四次插值約為 ,十次插值約為 ,而真值約為 。絕對誤差由約 增到 。這個有限計算展示 Runge 現象,並非漸近發散的完整證明;但已經否定「次數增加必然更準確」的無條件說法。
另外三個錯誤關乎公式的使用方式,而非公式本身的內容。
常見錯誤
(把「重心」當作穩定性證書)
公式的名稱不是誤差分析。用長乘積計算權重可能上溢或下溢,近節點求值仍需處理,捨入後的節點亦定義了擾動問題。節點設計處理近似與條件;穩定的實作還必須處理算術。
常見錯誤
(分別縮放個別重心權重)
只能移除公共因子。節點 、數據 時,縮放權重 在 給出 ,正是正確值。若只把最後一個權重改為 ,則得 。改動後的商一般是有理函數,而不是插值多項式。
常見錯誤
(把區間內的界用於外推)
Lebesgue 常數和餘項界都是在包含節點的區間上取最大值,對區間以外沒有任何保證。節點 時,Lagrange 權重絕對值之和在 上處處為一,但在 為二;外推需要獨立分析。
總結
差商支持逐點擴充的 Newton 構造。重心公式來自 Lagrange 恆等式,節點處應單獨返回樣本。Lebesgue 常數控制確定性數據誤差,並聯繫最佳近似。Chebyshev 根優化固定次數下的首一節點乘積及相應導數上界;次數增長、條件及浮點穩定性仍需獨立論證。
練習
快速檢查
(節點 的數據為 。建立差商表,寫 Newton 式並在 求值。若這些數據來自二次函數,會有甚麼結論?)
先求兩個一階差商,再求一個二階差商。
解答 · 答案
第一差商是 和 ,第二差商為 。因此 ,。若原函數是二次函數,唯一性說明它與插值多項式處處相同,不再存在未知導數餘項。
快速檢查
(求節點 的重心權重。在 求插值值及精確的最壞絕對誤差放大係數;在 的係數又是多少?)
在每個目標點計算兩個 Lagrange 函數。
解答 · 答案
權重為 ,可作公共縮放。在零點的 Lagrange 係數為 ,所以值為平均數,放大係數為一。在二點的係數為 ,放大係數為二,誤差 達到 。這個線性例子已顯示外推增加敏感度。
快速檢查
(求區間 上的兩個 Chebyshev 根及首一節點乘積。若 ,求定理給出的一致誤差界,並與端點節點 比較。)
把 的根 仿射映到 。
解答 · 答案
將 映到 ,得 。節點乘積為 ,範數為 ,故餘項界為 。端點節點的乘積為 ,範數為一,界為四。這些是上界,並非每個函數都達到的誤差。
快速檢查
(設 、,每個樣本絕對誤差不超過 。給出合併的一致誤差界。同一多項式換另一種精確表示能否改善這個界?)
使用第一個定理中的合併不等式。
解答 · 答案
近似項為 ,數據項為 ,總和為 。另一種精確表示不改變算子或其範數,但可以改變計算成本及未包含在此界內的算術誤差。