Python實現(xiàn)所有算法之牛頓前向插值介紹

今天的算法是插值，細分是牛頓插值。關(guān)于插值可能大家聽到最多的就是圖像插值，比如100元的攝像頭有4K的分辨率？？？其實這里就是使用的插值算法，通過已經(jīng)有的數(shù)據(jù)再生成一些，相當(dāng)于提升了數(shù)據(jù)的量。如果我們想放大圖像，我們需要使用過采樣算法來擴展矩陣。

左邊是原有的信息，右邊是通過算法生成的新數(shù)據(jù)

就像這樣

在上圖中，出現(xiàn)的算法是最近鄰算法，也稱為近端插值，是一維或多維空中多元插值的一種簡單方法。插值是通過已知的離散數(shù)據(jù)點在一定范圍內(nèi)尋找新數(shù)據(jù)點的過程或方法。最近鄰插值算法選擇最接近數(shù)據(jù)點的值，完全不考慮其他相鄰點的值，從而生成一個分段常數(shù)插值值作為數(shù)據(jù)點的值。線性的插值算法是雙線插值是二維坐標(biāo)系下線性插值的擴展，用于插值二元函數(shù)。它的核心思想是在兩個方向上執(zhí)行一次線性插值。

關(guān)于這里的圖像算法我不想說什么，等之后我會補上。簡單來說在數(shù)據(jù)給的少的情況下我們都可以考慮使用插值算法來生成新數(shù)據(jù)或者是改善。

注意我們處理的是離散數(shù)據(jù)：離散數(shù)據(jù)是指其數(shù)值只能用自然數(shù)或整數(shù)單位計算的數(shù)據(jù)。

離散函數(shù)：定義域是離散集合的函數(shù)稱為離散函數(shù)。其函數(shù)圖像為一系列離散的點。

在離散數(shù)據(jù)的基礎(chǔ)上補插連續(xù)函數(shù)，使得這條連續(xù)曲線通過全部給定的離散數(shù)據(jù)點。插值是離散函數(shù)逼近的重要方法，利用它可通過函數(shù)在有限個點處的取值狀況，估算出函數(shù)在其他點處的近似值。

理論就這么多了（其實也沒有理論就是說下基本的概念）

牛逼的插值算法來自：

《自然哲學(xué)的數(shù)學(xué)原理》的第三卷的引理五

對牛頓插值來說，它最大的特點是引入了差商這個概念。差商即均差，一階差商是一階導(dǎo)數(shù)的近似值。對等步長(h)的離散函數(shù)f(x)，其n階差商就是它的n階差分與其步長的n次冪的比值。例如n=1時，若差分取向前的或向后的，所得一階差商就是函數(shù)的導(dǎo)數(shù)的一階近似；若差分取中心的，則所得一階差商是導(dǎo)數(shù)的二階近似。

對一個f(x)可以構(gòu)造差商表來遞推的給出差商

計算的公式就是這樣，因為是重復(fù)同一種范式，所以程序?qū)崿F(xiàn)可以使用遞歸

事實上我們應(yīng)該給出一點更加規(guī)范的論證(不就是個導(dǎo)數(shù)）

有了上面的定義，作用是給出每一項的系數(shù)。具體推導(dǎo)是這樣的：

最后的就是我們的插值公式

為了看起來平易近人，可以寫成這樣

還有一種是等間距的插值計算，在下面的計算中間距設(shè)置為h（方向為前向差分）

這個圖就完美了?。。?/p>

二階的前向差分后和后向差分都在這里了

牛頓插值作為一種常用的數(shù)值擬合方法，因其計算簡單，方便進行大量插值點的計算。在實驗中經(jīng)常出現(xiàn)只能測量得到離散數(shù)據(jù)點的情況，或者只能用數(shù)值解表示某對應(yīng)關(guān)系之時，可以使用牛頓插值公式，對離散點進行擬合，得到較為準(zhǔn)確的函數(shù)解析值。

牛頓真厲害啊，幾百年前他萬萬沒有想到，一個小輩大晚上的還得研究人家隨手寫的東西。

牛頓插值算法的優(yōu)點是，每一個新項的生成都不需要龐大的算力，對前一項進行計算就行，拉格朗日的算法是每一個新項都需要對基函數(shù)完全計算，耗費算力。最后我們的泰勒公式其實就是對牛頓的插值算法進行了改進：

就記幾項就行

對了，插值是針對自變量的任何中間值估計函數(shù)值的技術(shù)，而計算給定范圍之外的函數(shù)值的過程稱為外插。

u是啥？別著急

這個公式對于在給定值集的開頭附近插值 f(x) 的值特別有用。h 稱為差值區(qū)間，u = ( x – a ) / h，這里 a 是第一項。

函數(shù)就是算這個的。

測試

下面的分母，需要求階乘，這里也準(zhǔn)備一個小函數(shù)

將輸入的值轉(zhuǎn)為整型，準(zhǔn)備一個list，將輸入的值輸入到空白的二維數(shù)值表。

就像這樣

這個沒有什么好說的，就是將輸入的值解到該有的位置，而且計算差分值。

審核編輯：劉清