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

左邊是原有的信息，右邊是通過算法生成的新數據

就像這樣

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

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

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

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

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

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

牛逼的插值算法來自：

《自然哲學的數學原理》的第三卷的引理五

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

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

計算的公式就是這樣，因為是重復同一種范式，所以程序實現可以使用遞歸

事實上我們應該給出一點更加規范的論證(不就是個導數）

有了上面的定義，作用是給出每一項的系數。具體推導是這樣的：

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

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

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

這個圖就完美了！！！

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

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

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

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

就記幾項就行

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

u是啥？別著急

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

函數就是算這個的。

測試

下面的分母，需要求階乘，這里也準備一個小函數

將輸入的值轉為整型，準備一個list，將輸入的值輸入到空白的二維數值表。

就像這樣

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

審核編輯：劉清