為甚麼要列表?
數據逐點到來時,每加一個節點都重新構造全部拉格朗日(Lagrange)基函數,會掩蓋可以重用的部分。牛頓(Newton)形式保留舊多項式,只增加一項;這一項在所有舊節點都為零,其係數由差商給出。三角表只用減法和除法便能算出這些係數。
定義 7.6.1
(差商表)
設 互不相同,數據為 。令 ,並對 、 定義
因此 ,即這些數據的差商。對角線上的 給出
構造此多項式不需要知道節點之間的函數值。 只是記錄給定數據的記號,並不要求額外求函數值。
為甚麼這些係數能插值?
定理 7.6.2
(牛頓插值公式)
對互不相同的節點 ,多項式 (其中 )是唯一一個次數至多為 且對所有 滿足 的多項式。
證明
(連續插值多項式之差)
記 為連續節點 上次數至多為 的唯一插值多項式。它的 係數是該組節點的差商: 時顯然成立;利用內維爾(Neville)遞推式將 寫成兩個重疊的低次插值多項式的組合,比較 的係數,就得到上面的差商遞推式。
於是 次數至多為 ,並在 處為零,故為 的常數倍。由於 次數更低,這個常數就是 的係數 。將這些差相加便得到牛頓公式;即使最高次係數為零,證明仍然成立。
證明透視
加入新節點時發生甚麼?
加入與舊節點不同的 和數值 時,舊係數保持不變。只需算出新增的最後一行,直到 ,再加上 。新項在舊節點為零,而遞推式確保新多項式也符合新數據。這是精確運算的結論;數據捨入或重複計算可能改變實際算得的係數。
節點互不相同這一假設用在每個分母 中,不能隨意去掉。
反例模式
重複節點會令差商表失效
一個誘人的說法是:任意 對數據都有一個次數至多為 的插值多項式,而差商表能把它算出來。取 ,,,。任何函數(無論是否多項式)都不可能在同一點 同時取值 和 。差商表的第一個條目會是 ,即除以零,所以失效並非公式的偶然缺陷。節點互不相同使每個分母非零。若要處理重複節點,數據須相容,並需要另一種構造,本單元不討論。
差商表與巢狀求值
例題 7.6.3
(四個數據點)
取 。差商表為
| 0 | 0 | 1 | |||
| 1 | 1 | 2 | 1 | ||
| 2 | 2 | 5 | 3 | 1 | |
| 3 | 3 | 10 | 5 | 1 | 0 |
例如 ,。因此 。末係數為零說明四個數據點已落在一個二次多項式上,不能說明未知的原函數在節點之間也是二次函數。
在 處,用巢狀形式求值:
從 開始,依次對 替換 。預先得到差值 後,共需 次乘法和 次加法。
例題 7.6.4
(不等距節點)
取節點 ,數據依次為 。一階差商為 和 ;二階差商為 。因此 ,。檢驗:、、。在 處巢狀求值得 ,與 一致。
例題 7.6.5
(加入一個新係數為零的節點)
在上一例的數據後面加入 ,並保持舊係數不變。新的一階差商為 ,二階差商為 ,三階差商為 。新增項為 ,故仍有 ,而且 。這個結論只針對這四個數據值,並不適用於所有與它們相符的函數。
原位計算及更新次序
初始化陣列 。對每個 ,按 的遞減次序更新:
定理 7.6.6
(原位更新的正確性與代價)
採用遞減更新時,第 輪之後, 的 ,而 的 。因此最後每個 。構造共需 次除法和 個陣列儲存位置。
證明
(遞減更新的不變式)
第 輪之前,對所有 有 。設第 輪之前,陣列滿足: 時 , 時 。在第 輪中, 由 遞減到 。更新 時,這一輪還沒有改動 ,因為 稍後才輪到,或在 時根本不會被更新。所以兩個運算元是 與 ,新值就是 。下標小於 的單元沒有被改動,而 此時已算好,故第 輪之後不變式成立。第 輪做 次除法,總數為 ;除節點外只需儲存陣列 。
每個目標點的巢狀求值需 次運算。
常見錯誤
(遞增更新會混合兩列)
上例前三個數的第一輪必須得到 。如果先將 覆蓋為 ,遞增更新就錯誤地算出 。這不是單純改變節點次序,而是使用已覆蓋的運算元進行了不同計算。
精確運算中,節點次序不影響唯一的插值多項式,但可能改變牛頓係數和中間計算。浮點運算中,不同次序可能造成不同的捨入誤差;節點相近時,除法也會對數據擾動敏感。節點處殘差小本身不能保證節點之間準確,也不能給出數值誤差界;穩定性和條件性需要另行分析。
練習與解答
快速檢查
(取節點 ,數據依次為 。求差商係數及插值多項式在 處的值。)
先算兩個一階差商,再算一個二階差商。
解答 · 答案
一階差商為 和 ,二階差商為 。因此 ,。於是 ,與 一致。
快速檢查
(對任意三個不同節點 ,解釋為何改變次序可能改變 ,卻不改變插值多項式。)
用前兩個節點表示 。
解答 · 答案
常數項後的第一個係數是前兩個節點間的斜率,更換前兩個節點可能改變斜率。但最終兩個次數至多為二的多項式插值同一組三個數據,因唯一性而在精確運算中相同。
快速檢查
(五個節點的差商表需要多少次除法?)
在代價結論中取 。
解答 · 答案
五個節點即 ,差商表需要 次除法:四輪分別是 次。
快速檢查
(若兩個節點重合,表中哪個分母會變為零?這說明甚麼?)
留意 。
解答 · 答案
當 時分母 為零。這表示數據不能按互異節點的插值處理:同一點上的兩個不同值互相矛盾,而相同的值也需要另一種構造。