多項式插值法

定義

在數值分析中，多項式插值法是通過多項式對給定數據集的插值：給定一些點，找到一個正好穿過這些點的多項式。

給定一組n+1個數據點(x_i,y_i)，其中沒有任何2個x_i是相同的，是在大多數n中尋找一個多項式p，

， i=0,...,n。

唯一可解性定理表明這樣的多項式p存在且是唯一的，並且可以通過范德蒙矩陣來證明，如下所述。

定理指出，對於n + 1插值節點(xi)，多項式插值定義了線性雙射。

Πn是多項式的向量空間(在任何時間間隔定義包含節點)，其最多為n。

假設插值多項式方程如下圖形式，

p插值點意味著

，所有i∈{0,1,..,n}。

如果我們把插值多項式方程代入，我們得到一個線性方程的係數a_k。得到矩陣-向量形式為

我們要用這個方程組來構造插值p(x)左邊的矩陣通常被稱為范德蒙矩陣。

范德蒙矩陣的條件數可能很大，當計算係數ai時，如果使用高斯消除來求解方程組，則會導致較大的誤差。

因此，一些作者提出了利用范德蒙德矩陣的結構來計算O(n²)運算中的數字穩定解的算法，而不是高斯消去法所要求的O(n³)。這些方法依賴於首先構造一個多項式的牛頓插值，然後將其轉換成上面的單項。

或者，我們可以立即用拉格朗日多項式來寫多項式:

對於矩陣參數，這個公式叫做Sylvester公式，矩陣的拉格朗日多項式是弗羅貝尼烏斯協變。

為了在n階多項式的向量空間Πn中構造唯一插值多項式。當使用Πn的單項式時，必須求解范德蒙德矩陣來構造插值多項式的係數a_k。這可能是一個非常複雜的操作（按照計算機嘗試做這個工作的時鐘周期計算）。通過選擇Πn，可以簡化係數的計算，但是當用單項式表示內插多項式時，必須進行額外的計算。

1、一種方法是以牛頓形式的多項式插值法，並使用分差法來構建係數，例如，內維爾的算法。則將大量花費在O(n²)運算，而高斯消除則花費在O(n³)運算。此外，如果在數據集中添加額外的點，則只需要執行O(n)個額外的計算，而對於其他方法，則必須重做整個計算。

2、另一種是使用拉格朗日形式的多項式插值法。所得公式立即顯示插值多項式存在於上述定理中所述的條件下。當對計算多項式的係數不感興趣時，在計算p（x）的值（給定的x不在原始數據集中）時，拉格朗日公式將優於范德蒙德公式。在這種情況下，我們可以將複雜度降低到O(n²)。

1、其中多項式可用於近似複雜的曲線，例如排版中的字母形狀（需要提供幾點）。

2、自然對數和三角函式的評估：選擇一些已知的數據點，創建一個查找表，並在這些數據點之間插值。多項式插值也成為數字正交和數值常微分方程中的算法和安全多方計算秘密共享方案的基礎。