[科普中國]-多項式插值法

定義

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

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

， i=0,...,n。

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

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

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

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

p插值點意味著，所有i∈{0,1,..,n}。

如果我們把插值多項式方程代入，我們得到一個線性方程的系數(shù)ak。得到矩陣-向量形式為

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

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

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

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

對于矩陣參數(shù)，這個公式叫做Sylvester公式，矩陣的拉格朗日多項式是弗羅貝尼烏斯協(xié)變。

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

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

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

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

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

3、多項式插值是執(zhí)行次二次乘法和平方的必要條件（例如Karatsuba乘法和Toom-Cook乘法），其中一個多項式的插值，它定義了乘積本身的乘積。例如，給定a = f（x）= a0x0 + a1x1 + ...和b = g（x）= b0x0 + b1x1 + ...，乘積ab等價于W(x)= f(x)g(x)。通過將x代入f(x)和g(x)中，沿W（x）找到點，并在曲線上得到這些點?；谶@些點的插值，將產生W（x）的項和隨后的乘積ab。在Karatsuba乘法的基礎上，即使對于中等規(guī)模的輸入，該技術也比二次乘法更快。在并行硬件實現(xiàn)時尤其如此。

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

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

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

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

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

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