一. 介紹

經(jīng)常在某乎看見此類問題：“數(shù)字找規(guī)律題，數(shù)字1、2、4、6、8、( )，請問括號內(nèi)應(yīng)填幾？”。我覺得這個問題很2B，不知道是哪個傻叉250問的。

那我在括號里隨手填個250，對不對？

對！沒毛病！

原因：假設(shè)整個數(shù)列通項符合某個?f(x)?，其中?x?從0開始計數(shù)，代入第0-5項可以找出這個通項公式為：

如果繼續(xù)填下一個：1、2、4、6、8、250、( )

嘿，那我還可以填：114514

原因：

這種不講武德的找規(guī)律填數(shù)字方法叫“多項式插值”。理論上給定n+1個x值不同的點，都可以找到一個對應(yīng)的n次多項式，它可以通過所有這些點。

比如上面的找規(guī)律問題，我把它轉(zhuǎn)換成了兩個插值問題：求過點(0,1)、(1,2)、(2,4)、(3,6)、(4,8)、(5,250) 的5次多項式，以及求過點(0,1)、(1,2)、(2,4)、(3,6)、(4,8)、(5,250)、(6,114514) 的6次多項式。

本文將介紹兩種通過已知點求多項式的方法。

二.多項式唯一

首先有個結(jié)論要了解：有n+1個點，他們的x值各不相同。那么過所有這些點的n次多項式存在且唯一。

左側(cè)的矩陣通常叫作范德蒙矩陣（Matrice de Vandermonde），它的行列式不為零（因為xi各不相同），這也就證明了唯一性定理：存在唯一的一個插值多項式。

所以對于同一系列的點，用拉格朗日插值法和牛頓插值法得到的多項式完全一致。

三. 拉格朗日插值法

先說插值法。插值法是做什么用的？插值法是通過已知點，求過這些點的未知函數(shù)的數(shù)學(xué)方法。

所以我們輸入的，是一堆點，也就是一堆x和一堆y。

我們想要得到的，是一個函數(shù)，這個函數(shù)能完美的通過這一堆x和這一堆y。

那你要怎么解決這個問題呢？說白了很簡單，就是一個開開關(guān)的問題。

這就是拉格朗日插值法的想法。

假設(shè)有三個點，可以通過“開關(guān)”的方式構(gòu)造通過這三個點的二次函數(shù)P(x):

這個三個開關(guān)有什么性質(zhì)呢？它們的值只能是0或1。

????1. 將x1帶入P(x)，開關(guān)1的值為1，開關(guān)2和開關(guān)3的值為0。

?????????這樣就保證P(x)了過第一個點。

????2.?將x2帶入P(x)，開關(guān)2的值為1，開關(guān)1和開關(guān)3的值為0。

?????????保證P(x)過第二個點。

????3.?將x3帶入P(x)，開關(guān)3的值為1，開關(guān)1和開關(guān)2的值為0。

?????????保證P(x)過第三個點。

那么開關(guān)的狀態(tài)是開（值為1）還是關(guān)（值為0），取決于什么呢？帶入的x值。

——任何數(shù)除自己都是1，零除任何數(shù)都是0。

以開關(guān)2為例，可以這樣構(gòu)造：

????????????

????????我們會發(fā)現(xiàn)，帶入x=x2，分子和分母的值相同，即開關(guān)為1。如果帶入x1或x3，則分子為0，即開關(guān)為0。

同理可得開關(guān)1和開關(guān)3的表達式。

進過簡單類推，我們就得到了拉格朗日插值法（Interpolation de Lagrange）的公式。

把它翻譯成人話：

，其中任一開關(guān)i的表達式是分式，分子為：該開關(guān)對應(yīng)的x值減其他非該點的x值，全部乘起來：

??

這樣帶入非該點的x值時，分子為0，開關(guān)的值為0。

分母則把上式中所有x替換成xi，這樣就保證帶入xi時，分子和分母一模一樣，開關(guān)的值為1：? ??

?

?另外補充與拉格朗日插值法相關(guān)的兩個點：

????1. 一般i從0開始取，以適應(yīng)計算機編程時的算法邏輯。

????2. 開關(guān)i一般用表示，它被稱為為拉格朗日基本多項式（或稱插值基函數(shù)）。??????

來一道例題：用拉格朗日插值法求經(jīng)過 （1,1），（2,4），（3,9）三個點的插值多項式。

解：

1. 首先構(gòu)造出這個多項式的基本結(jié)構(gòu)：

   ?注意這里第一個點表示為（x0,y0），以此類推...

   
   

2. 寫出每一個開關(guān)結(jié)構(gòu)：

   ?

   簡單驗算下：代入x=x0，L0(x)=1；代入x=x1 或 x=x2，L0(x)=0。沒問題。

   同理得剩余兩個開關(guān)：

   

   
   

3. 代入，化簡，得結(jié)果：?????

四.牛頓插值法

承接上面的例題，在有三個點的基礎(chǔ)上，增加第四個點（4,16），求經(jīng)過這四個點的插值多項式。如果繼續(xù)用拉格朗日插值法構(gòu)造開關(guān)的方法，會發(fā)現(xiàn)一個問題：每個開關(guān)都需要重新構(gòu)造，它們的分子和分母都要接納第四個點的x3和y3。

以第二個點的開關(guān)L1(x)為例，原本構(gòu)造為：

由于新增了一個點，需要重新構(gòu)造為以下形式：

原有的三個開關(guān)都要重新構(gòu)造，還要加構(gòu)造一個新的開關(guān)L3(x)。如果再增加一個點，則前四個開關(guān)都要重新構(gòu)造，再加構(gòu)一個L4(x)。如果再增加一個點，前五個開關(guān)又雙叒叕要重新構(gòu)造......

很明顯，拉格朗日插值法不具備遞歸性（Récursivité），每次插入新的點都會帶來大量的計算。而牛頓插值法則（Interpolation de Newton）可以解決這個問題。

牛頓插值法也用到了類似構(gòu)造開關(guān)的思想，考慮遞歸性，可以這樣構(gòu)造：

它要表達的意思是：某一項的值 = 前一項的值 + ai×開關(guān)。

現(xiàn)在開關(guān)的作用是，根據(jù)x的值決定要不要加上兩個多項式之間的差ai。每次新增一個插值點只需要多計算一個ai，之前算好的ai值不再變化。

以三個點為例：

如果增加第四個點的話，直接在原式后面增加第四項即可。之前算出的a0、a1、a2的值可保留：

按照這個邏輯，分別帶入x值算算a：

1.?

2.?

3.?

觀察到a0的值為y0，它被稱為0階差商。可表示為f(x0)。

a1的值為點（x0,y0）和點（x1,y1）之間的斜率。它被稱為1階差商?？杀硎緸閒[x0,x1]。

a2的值為 【點（x0,y0）和點（x1,y1）之間的斜率】和【點（x1,y1）和點（x2,y2）之間的斜率】?的斜率（好繞啊...），它被稱為2階差商。可表示為f[x0,x1,x2]。

...

以此類推，可以得出ai的值為i階差商?？梢员硎緸閒[x0,x1, ... ,xi]。

為了方便計算（不被繞暈），我們一般用差商表（Table de différences divisées）來計算每一階差商：

來個例題展示下這個方法的過程：用牛頓插值法求經(jīng)過 點1（1,1），點2（2,4），點3（3,9）的插值多項式。

在此基礎(chǔ)上，增加第四個點（4，16）。用牛頓插值法只需要多算下一階差商，再帶入到新增項后加入原式即可。

五.龍格現(xiàn)象

用前面兩種插值法，n個點需要得到n-1次的多項式。點越多，多項式的次數(shù)也越高。通過計算得到的多項式，并不只是給本文開頭扯淡的找規(guī)律題編一個像樣的理由。它更多地會被用于預(yù)測還沒有出現(xiàn)的點的位置。

為了預(yù)測準(zhǔn)確，我們希望這條曲線盡可能平滑自然、保持當(dāng)前趨勢。

舉個例子，有如下已知四點，預(yù)測第五個點x4的縱坐標(biāo)y4：

比較理想的情況是用前四點得到一條平滑的插值多項式，帶入x=x4來預(yù)測第五個點的縱坐標(biāo)：

不理想的情況是得到的多項式彎彎扭扭地通過前四點。用這樣的曲線來預(yù)測第五點的位置不具備說服力。尤其是多項式次數(shù)高了的話就容易出這個問題。

龍格現(xiàn)象（Phénomène de Runge）就是描述了這樣的不理想情況。

在科學(xué)計算領(lǐng)域，龍格現(xiàn)象（Runge）指的是對于某些函數(shù)，使用均勻節(jié)點構(gòu)造高次多項式差值時，在插值區(qū)間的邊緣的誤差可能很大的現(xiàn)象。它是由Runge在研究多項式差值的誤差時發(fā)現(xiàn)的，這一發(fā)現(xiàn)很重要，因為它表明，并不是插值多項式的階數(shù)越高，效果就會越好。

我會在下一篇文章用另一種插值法來回避這個問題。

至于本文這兩種插值法，預(yù)測未知點可能會出問題，但用來在某乎上回答找規(guī)律的題肯定綽綽有余咯。

六.參考資料

1. 在線計算器: 拉格朗日多項式計算器 (planetcalc.com)
   

2. 在線計算器: 牛頓多項式插值 (planetcalc.com)
   

3. Analyse_Numerique__Slides_Etu_1x2.pdf (univ-lorraine.fr)

4. 多項式插值 - 維基百科，自由的百科全書 (wikipedia.org)
   

5. 如何直觀地理解拉格朗日插值法？ - 知乎 (zhihu.com)

6. 拉格朗日插值法 - 維基百科，自由的百科全書 (wikipedia.org)

7. 牛頓多項式 - 維基百科，自由的百科全書 (wikipedia.org)

8. 龍格現(xiàn)象(Runge Phenomenon) - 知乎 (zhihu.com)

9. 找規(guī)律的數(shù)列問題真的沒有任何意義嗎？ - 知乎 (zhihu.com)