牛顿插值公式求函数值的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语言实现了利用牛顿插值公式通过对给定有限的采样点值进行插值，计算和输出相应的均差矩阵，并实现计算任意给定计值点的函数值，最后分析了算法的时间和空间复杂度。

关键词：插值；函数；采样；复杂度

中图分类号：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语言实现了利用牛顿插值公式通过对给定有限的采样点值进行插值，计算和输出相应的均差矩阵，并实现计算任意给定计值点的函数值，最后分析了算法的时间和空间复杂度。

关键词：插值；函数；采样；复杂度

中图分类号：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