牛顿插值法是曲线拟合插值法中的一种，适合采用所有的数据都精确的情况下。

一、差商

   差商是牛顿插值法的基础，我们先来理解差商的概念，然后在了解牛顿插值法。下面是差商的定义

    我举一个例子来具体说明，差商的计算方法：

    根据下表来计算函数的差商表：

    

	x1	x2	x3	x4
xi	-2	-1	1	2
f(xi)	5	3	17	21

     函数的差商表如下：

xi	f(xi)	一阶差商	二阶差商	三阶差商
-2	5
-1	3	-2
1	17	7	3
2	21	4	-1	-1

     f[x1,x2]=-2

     f[x1,x2,x3]=3

    f[x1,x2,x3,x4]=-1

二、牛顿插值法

    三、python实现牛顿插值法

     下面是一个函数表：

    

	x1	x2	x3	x4	x5	x6
xi	0.40	0.55	0.65	0.80	0.90	1.05
f(xi)	0.41075	0.57815	0.69675	0.88811	1.02652	1.25382

    计算四阶牛顿插值多项式，并求f(0.596)

    下面是函数的差商表：

xi	f(xi)	一阶差商	二阶差商	三阶差商	四阶差商	五阶差商
0.40	0.41075
0.55	0.57815	1.11600
0.65	0.69675	1.18600	0.28000
0.80	0.88811	1.27573	0.35893	0.19733
0.90	1.02652	1.38410	0.43348	0.21300	0.03134
1.05	1.25382	1.51533	0.32493	0.22863	0.03126	-0.00012

   f(x)=0.41075+1.11600(x-0.4)+0.28000(x-0.4)(x-0.55)+0.19733(x-0.4)(x-0.55)(x-0.65)+0.03134(x-0.4)(x-0.55)(x-0.65)(x-0.8)

      把0.596代入上式，可求出预测值，下面是python实现。

import matplotlib.pyplot as plt
from pylab import mpl
import math
"""
牛顿插值法
插值的函数表为
xi      0.4，       0.55，     0.65，      0.80，       0.90，   1.05
f(xi)   0.41075,    0.57815,   0.69675,    0.88811,    1.02652,  1.25382
"""

x = [0.4, 0.55, 0.65, 0.80, 0.90, 1.05]
y = [0.41075, 0.57815, 0.69675, 0.88811, 1.02652, 1.25382]


"""计算五次差商的值"""
def five_order_difference_quotient(x, y):
    # i记录计算差商的次数，这里循环5次，计算5次差商。
    i = 0
    quotient = [0, 0, 0, 0, 0, 0]
    while i < 5:
        j = 5
        while j > i:
            if i == 0:
                quotient[j]=((y[j]-y[j-1])/(x[j]-x[j-1]))
            else:
                quotient[j] = (quotient[j]-quotient[j-1])/(x[j]-x[j-1-i])
            j -= 1
        i += 1
    return quotient;

def function(data):
    return x[0]+parameters[1]*(data-0.4)+parameters[2]*(data-0.4)*(data-0.55)+\
           parameters[3]*(data-0.4)*(data-0.55)*(data-0.65)\
           +parameters[4]*(data-0.4)*(data-0.55)*(data-0.80)

"""计算插值多项式的值和相应的误差"""
def calculate_data(x,parameters):
    returnData=[];
    for data in x:
        returnData.append(function(data))
    return returnData

"""画函数的图像
newData为曲线拟合后的曲线
"""

def draw(newData):
    plt.scatter(x,y,label="离散数据",color="red")
    plt.plot(x,newData,label="牛顿插值拟合曲线",color="black")
    plt.scatter(0.596,function(0.596),label="预测函数点",color="blue")
    plt.title("牛顿插值法")
    mpl.rcParams['font.sans-serif'] = ['SimHei']
    mpl.rcParams['axes.unicode_minus'] = False
    plt.legend(loc="upper left")
    plt.show()



parameters=five_order_difference_quotient(x,y)
yuanzu=calculate_data(x,parameters)
draw(yuanzu)

牛顿插值法的实现效果图：