多項式插值法

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

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

， i=0,...,n。

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

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

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

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

p插值點意味着

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

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

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

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

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

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

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

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

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

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

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

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

3、多項式插值是執行次二次乘法和平方的必要條件（例如Karatsuba乘法和Toom-Cook乘法），其中一個多項式的插值，它定義了乘積本身的乘積。例如，給定a = f（x）= a₀x⁰ + a₁x¹ + ...和b = g（x）= b₀x⁰ + b₁x¹ + ...，乘積ab等價於W(x)= f(x)g(x)。通過將x代入f(x)和g(x)中，沿W（x）找到點，並在曲線上得到這些點。基於這些點的插值，將產生W（x）的項和隨後的乘積ab。在Karatsuba乘法的基礎上，即使對於中等規模的輸入，該技術也比二次乘法更快。在並行硬件實現時尤其如此。

在工程技術中，經常會遇到插值之類的計算問題，例如在半導體技術中，設計晶體管和分析其性能時，常常涉及到與半導體的雜質濃度有關的參量；在温度自動控制系統中的熱電偶和温度的對應關係，當採用計算機輔助分析和控制時，必須將這些關係曲線離散化，由於這些曲線很多都是通過經驗獲得的，無法用函數解析表示，如單晶硅電阻率與摻雜濃度換算表，熱電偶與温度的分度表。一般來講，不是將所有數據都存人計算機，而是取一系列數值利用通常的牛頓插值法、拉格朗日插值法等，求得對應於x的y值，這些插值法都構造一個多項式，用其近似已知的或未知的函數關係的解析表達式。

在計算過程中，如果插值的數據很多，則需要大量的計算時間，這對於大型項目或實時性計算，顯得很不利。查表方法可以提高運算速度，但需要較多的內存存放數據，而且無法得到任意值。

在半導體技術中，硅單晶珍雜濃度與電阻率關係，變化範圍達到幾個數量級，直接使用上述播值法不可能得到滿意的結果。

另一個問題，如果知道y值，欲求x值。使用一組數據是做不到的，這樣又會加重系統的負擔。

解決上述問題的基本思想是直接用一個多項式函數近似表示未知的函數關係，這樣就可以求得該函數定義域內的任意值。為了與上述插值方法以示區別，故稱為“多項式插值法”。

插值多項式是廣為人知的，無論何種插值方法實質上都是構造一個n階多項式。當然，多項式的形式和構造方法可以是多種多樣的。 ^[5]