王增波

摘要：在給定的精度范圍內(nèi)，利用C語言實(shí)現(xiàn)了利用牛頓插值公式通過對(duì)給定有限的采樣點(diǎn)值進(jìn)行插值，計(jì)算和輸出相應(yīng)的均差矩陣，并實(shí)現(xiàn)計(jì)算任意給定計(jì)值點(diǎn)的函數(shù)值，最后分析了算法的時(shí)間和空間復(fù)雜度。

關(guān)鍵詞：插值；函數(shù)；采樣；復(fù)雜度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8170-01

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

1 算法步驟

2 數(shù)據(jù)結(jié)構(gòu)

3 C源程序

4 結(jié)論

本程序最多使用了二重循環(huán)，時(shí)間主要用在求k階均差和求給定點(diǎn)函數(shù)值的過程中，在最壞情況下，當(dāng)節(jié)點(diǎn)數(shù)為n時(shí)，時(shí)間復(fù)雜度為1+2+3+…+n=O（[n2]）。本程序使用了一個(gè)二維數(shù)組用來保存k階均差，空間復(fù)雜度主要在保存均差，占2×ROW個(gè)浮點(diǎn)型存儲(chǔ)單元。

參考文獻(xiàn)：

[1] 譚浩強(qiáng). C語言程序設(shè)計(jì)[M].3版.北京：清華大學(xué)出版社，2014.

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

摘要：在給定的精度范圍內(nèi)，利用C語言實(shí)現(xiàn)了利用牛頓插值公式通過對(duì)給定有限的采樣點(diǎn)值進(jìn)行插值，計(jì)算和輸出相應(yīng)的均差矩陣，并實(shí)現(xiàn)計(jì)算任意給定計(jì)值點(diǎn)的函數(shù)值，最后分析了算法的時(shí)間和空間復(fù)雜度。

關(guān)鍵詞：插值；函數(shù)；采樣；復(fù)雜度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8170-01

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

1 算法步驟

2 數(shù)據(jù)結(jié)構(gòu)

3 C源程序

4 結(jié)論

本程序最多使用了二重循環(huán)，時(shí)間主要用在求k階均差和求給定點(diǎn)函數(shù)值的過程中，在最壞情況下，當(dāng)節(jié)點(diǎn)數(shù)為n時(shí)，時(shí)間復(fù)雜度為1+2+3+…+n=O（[n2]）。本程序使用了一個(gè)二維數(shù)組用來保存k階均差，空間復(fù)雜度主要在保存均差，占2×ROW個(gè)浮點(diǎn)型存儲(chǔ)單元。

參考文獻(xiàn)：

[1] 譚浩強(qiáng). C語言程序設(shè)計(jì)[M].3版.北京：清華大學(xué)出版社，2014.

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

摘要：在給定的精度范圍內(nèi)，利用C語言實(shí)現(xiàn)了利用牛頓插值公式通過對(duì)給定有限的采樣點(diǎn)值進(jìn)行插值，計(jì)算和輸出相應(yīng)的均差矩陣，并實(shí)現(xiàn)計(jì)算任意給定計(jì)值點(diǎn)的函數(shù)值，最后分析了算法的時(shí)間和空間復(fù)雜度。

關(guān)鍵詞：插值；函數(shù)；采樣；復(fù)雜度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）34-8170-01

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

1 算法步驟

2 數(shù)據(jù)結(jié)構(gòu)

3 C源程序

4 結(jié)論

本程序最多使用了二重循環(huán)，時(shí)間主要用在求k階均差和求給定點(diǎn)函數(shù)值的過程中，在最壞情況下，當(dāng)節(jié)點(diǎn)數(shù)為n時(shí)，時(shí)間復(fù)雜度為1+2+3+…+n=O（[n2]）。本程序使用了一個(gè)二維數(shù)組用來保存k階均差，空間復(fù)雜度主要在保存均差，占2×ROW個(gè)浮點(diǎn)型存儲(chǔ)單元。

參考文獻(xiàn)：

[1] 譚浩強(qiáng). C語言程序設(shè)計(jì)[M].3版.北京：清華大學(xué)出版社，2014.

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