牛頓插值公式求函數值的C程序實現

王增波

摘要：在給定的精度范圍內，利用C語言實現了利用牛頓插值公式通過對給定有限的采樣點值進行插值，計算和輸出相應的均差矩陣，并實現計算任意給定計值點的函數值，最后分析了算法的時間和空間復雜度。

關鍵詞：插值；函數；采樣；復雜度

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）34-8170-01

插值是計算數學中最基本和最常用的手段，是函數逼近理論中的重要方法，在數據建模競賽中進行數據處理時也經常會用到數據插值。利用插值可通過函數在有限個采樣點處的取值，估算出該函數在未采樣點處的值，即通過函數的有限數據，以得出其完整的數學描述。牛頓插值法即為其中一種插值方法。下面就該插值方法的實現步驟和程序代碼進行了詳述，最后對該算法的時間復雜度進行了分析。

1 算法步驟

2 數據結構

3 C源程序

4 結論

本程序最多使用了二重循環，時間主要用在求k階均差和求給定點函數值的過程中，在最壞情況下，當節點數為n時，時間復雜度為1+2+3+…+n=O（[n2]）。本程序使用了一個二維數組用來保存k階均差，空間復雜度主要在保存均差，占2×ROW個浮點型存儲單元。

參考文獻：

[1] 譚浩強. C語言程序設計[M].3版.北京：清華大學出版社，2014.

[2] 史萬明，吳裕樹，孫新. 數值分析 [M] .3版.北京：北京理工大學出版社，2010.endprint

摘要：在給定的精度范圍內，利用C語言實現了利用牛頓插值公式通過對給定有限的采樣點值進行插值，計算和輸出相應的均差矩陣，并實現計算任意給定計值點的函數值，最后分析了算法的時間和空間復雜度。……