多項式插值

在數值分析這個數學分支中，多項式插值用多項式對一組給定數據進行插值的過程。換句話說就是，對於一組給定的數據（如來自於採樣的數據），其目的就是尋找一個恰好通過這些數據點的多項式。

應用

多項式可以根據少數給定的數據點來逼近複雜的曲線，如字體排印學中的文字。一個相關的應用是估計自然對數和三角函數的值：選擇幾個已知的數據點、構建一個查找表、然後在這些數據點之間進行插值。這樣可以得到非常快速的計算。另外多項式插值也是數值積分和數值常微分方程中算法的基礎。

多項式插值在 sub-quadratic 乘法以及平方運算中也很關鍵。例如，有 a = f(x) = a₀x⁰ + a₁x¹ + ... 以及 b = g(x) = b₀x⁰ + b₁x¹ + ... 那麼乘積 ab 等於 W(x) = f(x)g(x)。基於這些點的插值將得到 W(x) 以及乘積 ab。對於卡拉楚巴乘法來說，這項技術的速度要比普通數目輸入的二次乘法速度要快，尤其是在用並行的硬體實現的時候更是這樣。

定義

給定一組 n+1 個數據點（x_i,y_i），其中任意兩個 x_i 都不相同， 需要找到一個滿足

$p(x_{i})=y_{i}{\mbox{ , }}i=0,\ldots ,n.$

的不大於 n 階的 p 階多項式。唯一性定理表明存在一個並且僅有一個這樣的 p 階多項式。

用更加複雜的說法，這個多項式可以表述為：對於 n+1 個插值點 (x_i)，多項式插值定義了一個線性雙射

$L_{n}:\mathbb {K} ^{n+1}\to \Pi _{n}$

其中 $\Pi _{n}$ 是小於或者等於 n 的多項式的向量空間。

構建插值多項式

紅色點表示數據點(x_k,y_k)，藍色曲線表示插值多項式。

假設插值多項式的形式為

$p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}.\qquad (1)$

p 對數據點進行插值其含義為

$p(x_{i})=y_{i}\qquad {\mbox{for all }}i\in \left\{0,1,\dots ,n\right\}.$

如果代入等式（1），就得到係數為 $a_{k}$ 的線性方程系統，用矩陣向量形式表示為

${\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.$

為了構建插值多項式 $p(x)$，我們要解這個系統計算係數 $a_{k}$。

左側的矩陣通常叫作范德蒙矩陣，它的行列式不為零，這也就證明了唯一性定理：存在唯一的一個插值多項式。

非范德蒙解

我們要在 n 階多項式向量空間 $\Pi _{n}$ 中構建唯一的一個插值多項式。當用單項式基表示 $\Pi _{n}$ 時，為了建立插值多項式的係數 $a_{k}$ 我們要解范德蒙矩陣，這個過程可能會耗費大量的計算量。通過為 $\Pi _{n}$ 選擇另外一種基我們可以簡化係數的計算，但是如果需要用單項式基表示的話當然需要一些額外的計算工作。

其中一個方法是將插值多項式表示成牛頓型多項式，並且使用均差方法建立係數。其代價是$\mathrm {O} (n^{2})$運算，而高斯消去需要 $\mathrm {O} (n^{3})$運算。另外，如果在數據集中添加了額外的點，也只需要很少的額外運算；而其它方法通常都需要全部重新計算。

另外一個方法是使用拉格朗日型的插值多項式，得到的結果公式馬上就表明在滿足上面定理所定義條件下存在插值多項式。

伯恩斯坦形式最初是謝爾蓋·納塔諾維奇·伯恩施坦在魏爾施特拉斯逼近定理的建設性證明中所用的形式，如今它在計算機圖形學的貝塞爾曲線中得到了非常重要的應用。

插值誤差

用 n 階多項式在節點 x₀、...、x_n 對函數 f 插值的誤差為：

$f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})$

其中

$f[x_{0},\ldots ,x_{n},x]$

是均差符號。如果 f 在包含節點 x_i 的最小區間 I 上 n+1 次連續可導，那麼我們可以將在 I 中 $\xi$ 的誤差寫成拉格朗日型

$f(x)-p_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})$

這樣，拉格朗日型泰勒定理的餘數就是所有插值節點 x_i 都相同的情況下的插值誤差特例。 如果插值節點等距分布 $x_{i}=x_{0}+ih$，那麼插值誤差為 $O(h^{n})$。但是，這並不意味著隨著 n → ∞ 插值誤差將趨近於 0；實際上，在接近區間 $[x_{0},x_{n}]$ 端點的時候，誤差甚至可能會變得無限大，這種現象叫作龍格現象。

上面的誤差範圍說明我們要選擇使乘積 | ∏ (x − x_i) | 儘可能小的插值點 x_i。切比雪夫節點就可以實現這個結果。

勒貝格常數

主條目：勒貝格常數

在插值節點 x₀、...、x_n 以及包含所有插值節點的區間 [a, b] 確定下來，插值的過程就是將函數 f 映射到多項式 p。這定義了一個 [a, b] 區間上所有連續函數從空間 C([a, b]) 到其自身的映射。映射 X 是線性的，並且它是函數 f 在子空間 Π_n 上的投影。 勒貝格常數 L 定義為 X 的算子範數，它滿足勒貝格引理：

$\|f-X(f)\|\leq (L+1)\|f-p^{*}\|.$

換句話說，插值多項式的誤差最多是最優逼近的（L+1）倍，這表明我們要找使 L 最小的插值節點。尤其是選擇切比雪夫節點時：

$L\geq {\frac {2}{\pi }}\log(n+1)+C\quad {\mbox{for some constant }}C.$

我們再次證明切比雪夫節點是多項式插值中比較好的選擇，但是這些節點並不是最優的。

收斂性

很自然我們有一個疑問，即對於什麼類型的函數以及什麼樣的插值節點情況下，插值多項式才能夠收斂到被插值的函數。收斂性有不同的類型，如點態收斂、一致收斂或者積分收斂。下面將討論一致收斂。

下面的定理是一個相當令人振奮的答案：

對於在區間 [a,b] 內連續的任意函數 f(x)，存在一個節點表使得插值多項式 $p_{n}(x)$ 在 [a,b] 內一致收斂於 f(x)。

證明：根據魏爾施特拉斯逼近定理，我們知道最優逼近多項式序列 $p_{n}^{*}(x)$ 一致收斂到 f(x)。 現在我們只需證明每個 $p_{n}^{*}(x)$ 都可以通過在特定節點的插值得到，但是根據切比雪夫交錯定理這是最優逼近多項式的一個特性。我們明確地得知這樣的多項式至少與函數 f(x) 相交 n+1 次。將這些交點作為插值的節點，那麼插值多項式就是最優逼近多項式。

但是這個方法的缺點是對每個新函數 f(x) 都要重新計算插值節點，而這個算法很難用數值方法實現。是不是存在一個節點表能夠滿足插值多項式序列收斂到任意一個連續函數 f(x) 呢？這個問題的答案是否定的，其理由在於下面的定理的結論：

對於任何的節點表都存在一個連續函數 f(x) 在區間 [a,b] 上使得插值多項式發散。

這個證明主要是依據勒貝格常數下限的估計，它定義了 'Xn 的算子範數，其中 'X_n 是在 Π_n 上的投影算子。現在我們要找一個對於任意的 $f\in C([a,b])$ 符合

$\lim _{n\to \infty }X_{n}f=f,$

條件的節點表。根據巴拿赫-斯坦豪斯定理，只有當 X_n 的範數一致有界時才存在這樣的節點表，但是根據 $\|X_{n}\|\geq {\frac {2}{\pi }}\log(n+1)+C$ 我們知道這是不可能的。

例如，如果選擇等距點作為插值節點，那麼龍格現象中的函數表明這樣的插值就會出現發散現象。需要注意的是這個函數不僅連續而且在 [−1, 1] 內無限可導。但是對於效果較好的切比雪夫節點，根據下面的定理很難出現這個問題。

對於每個在 [−1, 1] 區間絕對連續的函數，在切比雪夫節點上構建的插值多項式序列一致收斂於 f(x)。

相關概念

龍格現象表明高階插值多項式可能在數據點之間出現震盪，通常可以通過樣條插值來解決這個問題，在這種情況下，它不僅僅是一個多項式，而且是樣條：一串低階多項式組合。

使用調和分析函數對周期函數的插值通常是使用傅立葉級數實現的，如在離散傅立葉變換中所作的那樣。這可以看作是一種帶有調和基函數的多項式插值，參見三角插值與三角多項式。

埃爾米特插值問題是不僅給出了多項式 p 的值，而且給出了一些導數。伯克霍夫插值是給定一些導數而沒有給定 p 自身的值的插值方法的一般形式。

微分與積分方程的配置法解法都是基於多項式插值。

參考文獻

• Kendell A. Atkinson (1988). An Introduction to Numerical Analysis (2nd ed.), Chapter 3. John Wiley and Sons. ISBN 0-471-50023-2
• L. Brutman (1997), Lebesgue functions for polynomial interpolation — a survey, Ann. Numer. Math. 4, 111–127.
• M.J.D. Powell (1981). Approximation Theory and Method, Chapter 4. Cambridge University Press. ISBN 0-521-29514-9.
• Michelle Schatzman (2002). Numerical Analysis: A Mathematical Introduction, Chapter 4. Clarendon Press, Oxford. ISBN 0-19-850279-6.
• Endre Süli and David Mayers (2003). An Introduction to Numerical Analysis, Chapter 6. Cambridge University Press. ISBN 0-521-00794-1.