美賽中常見的算法：插值算法

數學建模中常常需要進行數據處理，當給定的數據較少不足以支撐分析的進行時， 可以採用插值算法產生一些新值滿足數據處理的需求，簡而言之，插值是求過已 知有限個數據點的近似函數。

常見的插值有拉格朗日多項式插值、牛頓插值、分段線性插值、Hermite 插值和三次樣條插值。

一、插值的定義

總之，插值的關鍵要滿足插值函數過插值節點。

二、拉格朗日多項式插值（Lagrange 插值）

三、龍格現象（Runge phenomenon）

在介紹龍格現象之前，可以考慮一個問題：插值多項式次數越高誤差越小嗎？

高次插值會產生龍格現象，即在兩端波動極大，產生明顯的震盪。在不熟悉曲線 運動趨勢的前提下，不要輕易使用高次插值。

四、牛頓插值（Newton）

Newton 插值的優點是：每增加一個節點，插值多項式只增加一項，因而便於遞 推運算，而且 Newton 插值的計算量小於 Lagrange 插值。

五、分段線性插值 分段低次插值的思路：

(1) 插值多項式次數高精度未必顯著提高

(2) 插值多項式次數越高攝入誤差可能顯著增大那麼，如何提高插值精度呢？採用分段低次插值是一種辦法

六、Hermite 插值

插值問題的一般要求是插值函數過插值節點，那麼爲了保持插值曲線在節點處有 切線，使插值函數和被插函數的密和程度更好，對插值問題提出了更高的要求；插值節點的導數值也要相等，甚至要求高階導數也相等。

Heimite 插值多項式爲

七、三次樣條插值

許多工程技術中提出的計算問題對插值函數的光滑性有較高要求，如飛機的 機翼外形，內燃機的進、排氣門的凸輪曲線，都要求曲線具有較高的光滑程度， 不僅要連續，而且要有連續的曲率，這就導致了樣條插值的產生。

八、插值算法總結

(1) 拉格朗日插值和牛頓插值：與拉格朗日插值法相比，牛頓插值法的計算過程具有繼承性。牛頓插值法每次插值只和前 n 項的值有關，這樣每次只要在原來的 函數上添加新的項，就能夠產生新的函數，但是牛頓插值也存在龍格現象的問題。

(2) 由於拉格朗日插值和牛頓插值只要求插值多項式在插值節點處與被插函數 有相等的函數值，但是這樣不能全面反映被插值函數的性態，由此引入了 Hermite 插值，Hermite 插值考慮了低階和高階的導數值。

(3) 三次樣條插值生成的曲線相對於其他方法來說更加光滑。

下半年評獎評優的國際級競賽必參加打卡，

2023年MCM/ICM美國大學生數學建模競賽正在報名中

保研加分、綜測評獎

由於報名參加美賽的同學不具備Visa或國際支付方式，以及缺乏一定的參賽經驗，爲了更好的提升參賽者的獲獎率，數模樂園繼續推出2023年美賽輔助報名及證書打印並郵寄的服務。 2022年 通過數模樂園輔助報名中， 4支 隊伍斬獲2021 Outstanding Winner獎（其中一支獲得SIAM Award冠名獎；另外3支獲得Outstanding Winner獎），O獎獲獎率同比增長 50% ，整體參賽獲獎率達99.3%， 2021年 助力1支隊伍獲得 1萬美元 獎學金。數模樂園已累計爲 8.5萬 多人以上同學完成了美賽輔助報名服務！已成爲 國內最大的美賽輔助報名平臺！

競賽報名

或複製下方報名官網進行報名：http://www.nmmcm.org.cn/match_detail/23

進羣領取歷年美賽真題及培訓資料，進羣備註：學校+專業

通過數模樂園報名完成後，數模樂園會在工作時間內將報名成功的郵件發送至參賽隊伍的隊長郵箱裡，（和你報名時間順序有關係，報名日期越早，收到的郵件就越早，所以很多同學一開始沒有很強的備賽意識，表示不是很急，結果報名的比較晚，但是還特別想快速的收到報名成功的郵件，這裡要告誡一下這類同學，越到最後，報名的隊伍就越多，所以爲了避免造成報名擁堵及郵件接收延遲問題，強烈建議同學們需要提前完成報名工作，每年這類問題經常會有發生）郵件中包含2023年美賽參賽指南、數模樂園贈送的備賽大禮包以及518密訓課程等內容。