Python實(shí)現(xiàn)所有算法-二分法

Python實(shí)現(xiàn)所有算法-力系統(tǒng)是否靜態(tài)平衡

Python實(shí)現(xiàn)所有算法-力系統(tǒng)是否靜態(tài)平衡（補(bǔ)篇）

Python實(shí)現(xiàn)所有算法-高斯消除法

Python實(shí)現(xiàn)所有算法-牛頓-拉夫遜（拉弗森）方法

Python實(shí)現(xiàn)所有算法-雅可比方法（Jacobian）

Python實(shí)現(xiàn)所有算法-矩陣的LU分解

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

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

就像這樣

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

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

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

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

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

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

牛逼的插值算法來自：

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

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

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

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

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

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

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

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

還有一種是等間距的插值計(jì)算，在下面的計(jì)算中間距設(shè)置為h（方向?yàn)榍跋虿罘郑?/p>

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

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

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

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

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

就記幾項(xiàng)就行

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

u是啥？別著急

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

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

測試

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

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

就像這樣

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

最后輸入插值表

潘老師的數(shù)值分析講義是我見過相當(dāng)不錯的

如圖

?

嘻嘻，以前還問過老師的參考資料

https://math.ecnu.edu.cn/~jypan/Teaching/NA/index.html

講義一覽

https://www.zhihu.com/question/26692289

https://www.geeksforgeeks.org/newton-forward-backward-interpolation/

非常多的數(shù)值算法的實(shí)現(xiàn)

原文標(biāo)題：Python實(shí)現(xiàn)所有算法-牛頓前向插值

文章出處：【微信公眾號：云深之無跡】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。