[科普中國(guó)]-多項(xiàng)式插值法

定義

在數(shù)值分析中，多項(xiàng)式插值法是通過(guò)多項(xiàng)式對(duì)給定數(shù)據(jù)集的插值：給定一些點(diǎn)，找到一個(gè)正好穿過(guò)這些點(diǎn)的多項(xiàng)式。

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

， i=0,...,n。

唯一可解性定理表明這樣的多項(xiàng)式p存在且是唯一的，并且可以通過(guò)范德蒙矩陣來(lái)證明，如下所述。

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

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

構(gòu)造插值多項(xiàng)式假設(shè)插值多項(xiàng)式方程如下圖形式，

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

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

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

范德蒙矩陣的條件數(shù)可能很大2，當(dāng)計(jì)算系數(shù)ai時(shí)，如果使用高斯消除來(lái)求解方程組，則會(huì)導(dǎo)致較大的誤差。

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

或者，我們可以立即用拉格朗日多項(xiàng)式來(lái)寫(xiě)多項(xiàng)式:

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

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

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

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

應(yīng)用1、其中多項(xiàng)式可用于近似復(fù)雜的曲線，例如排版中的字母形狀（需要提供幾點(diǎn)）。

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

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

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

在計(jì)算過(guò)程中，如果插值的數(shù)據(jù)很多，則需要大量的計(jì)算時(shí)間，這對(duì)于大型項(xiàng)目或?qū)崟r(shí)性計(jì)算，顯得很不利。查表方法可以提高運(yùn)算速度，但需要較多的內(nèi)存存放數(shù)據(jù)，而且無(wú)法得到任意值。

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

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

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

插值多項(xiàng)式是廣為人知的，無(wú)論何種插值方法實(shí)質(zhì)上都是構(gòu)造一個(gè)n階多項(xiàng)式。當(dāng)然，多項(xiàng)式的形式和構(gòu)造方法可以是多種多樣的。5