牛頓、拉格朗日多項式插值法與基底變換

在座標平面上要找出通過固定幾個點的函數會有很多種，通常可以用多項式函數來近似原本的函數，稱為插值多項式。在高中一年級的課程就有提到牛頓插值法(Newton’s interpolation)和拉格朗日插值法(Lagrange’s interpolation)。前幾天在跟其他老師聊天時，說到我對這些多項式插值法的感覺，一是將多項式採用不同基底的線性組合，另一則是將拉格朗日多項式與數論的中國剩餘定理(the Chinese Remainder Theorem, CRT)作連結。以下就以基底的線性組合的觀點來談這件事(關於CRT和Lagrange’s interpolation的關係以後有空再寫)：

以不同基底的概念來說，例如欲求在座標平面上通過(x₁, y₁)、(x₂, y₂)、(x₃, y₃)的多項式函數y＝f(x)，其中degf(x)≦2，則f(x)可作以下假設：

(1)一般式的假設：f(x)＝ax²＋bx＋c

(2)牛頓插值法的假設：f(x)＝A(x－x₁)(x－x₂)＋B(x－x₁)＋C

(3)拉格朗日插值法的假設：f(x)＝α(x－x₁)(x－x₂)＋β(x－x₂)(x－x₃)＋γ(x－x₁)(x－x₃)

這三個其實就是考慮所有deg≦2的多項式構成的向量空間，分別採用B₁={x², x, 1}、B₂={(x－x₁)(x－x₂), (x－x₁), 1}、B₃={(x－x₁)(x－x₂)、(x－x₂)(x－x₃)、(x－x₁)(x－x₃)}為基底的假設，所以這三種假設法都能得到唯一的係數，確實能表示滿足所需條件的多項式。

更仔細來說，基底的座標變換矩陣可以寫成

所以

例：欲求在座標平面上通過(1, 6)、(2, 14)、(3, 26)的二次函數y＝f(x)的一般式。
Sol：

利用牛頓插值法假設，可設f(x)＝A(x－1)(x－2)＋B(x－1)＋C，依次代入(1, 6)、(2, 14)、(3, 26)，可得C＝6，B＝8，A＝2，即f(x)＝2(x－1)(x－2)＋8(x－1)＋6，若利用座標變換矩陣可得

 即f(x)＝2x²＋2x＋2。

若利用拉格朗日插值法，我們可以直接寫出

 利用座標變換矩陣可得

即f(x)＝2x²＋2x＋2。

當然上面兩種方法，直接將f(x)＝2(x－1)(x－2)＋8(x－1)＋6或f(x)＝13(x－1)(x－2)＋3(x－2)(x－3)－14(x－1)(x－3)展開都會比較容易。

相關文章：中國剩餘定理(the CRT)與拉格朗日插值法(Lagrange's interpolation)