精华内容
下载资源
问答
  • 本文用适当的多项式函数近似高斯折射率分布函数,利用Ikuno的结果,导出了扩散平面光波导导模有效折射率的更精确近似公式.这个公式不仅简单便于计算,而且由它求得的导模有效折射率更接近光线方法的数值结果,其精度...
  • 牛顿插值多项式公式求函数近似

    千次阅读 2012-10-11 19:56:01
    下面这段代码是从liuhenghui5201借鉴过来的,只不过他没写算法说明,我就代劳了!正好在学数值分析,上机实现效果! 原文地址...  #include  main() ... double sum=0,w=1,x,b[5][6],c

    下面这段代码是从liuhenghui5201借鉴过来的,只不过他没写算法说明,我就代劳了!正好在学数值分析,上机实现效果!

    原文地址http://blog.csdn.net/liuhenghui5201/article/details/7588082#

     #include<stdio.h>
     main()
    {
     int i,j,k,m,z=0;
     double sum=0,w=1,x,b[5][6],cc[2][4];
     for(i=0;i<5;i++)
     {
      printf("请输入x[%d]、y[%d]:  ",i,i);
      scanf("%lf%lf",&b[i][0],&b[i][1]);
     }
     for(j=2,k=1;j<6;j++,k++)
     {
      for(i=j-1;i<5;i++)
      {
       b[i][j]=(b[i-1][j-1]-b[i][j-1])/(b[i-k][0]-b[i][0]);
      }
     }
     
     printf("enter x:");
     scanf("%lf",&x);
     for(m=0;m<4;m++,z=0)
     {
      cc[0][m]=b[m+1][m+2];
      do{
       w*=(x-b[z][0]);
      }while(z++!=m);
      cc[1][m]=w;  
     }
     sum=b[0][1];
     for(m=0;m<4;m++)
      sum+=(cc[0][m]*cc[1][m]);
     printf("\n差值y为: %lf\n",sum);

    }

    展开全文
  • 牛顿迭代法又称牛顿-拉夫逊方法(Newton-Raphson method),是牛顿在17世纪提出的一种在实数域和复数域上近似求方程的方法。该方法的基础是利用泰勒展开式。 方法使用函数f(x)的泰勒级数的前几项寻找方程f(x) = 0 的...

    牛顿迭代法又称牛顿-拉夫逊方法(Newton-Raphson method),是牛顿在17世纪提出的一种在实数域和复数域上近似求方程的方法。该方法的基础是利用泰勒展开式。

          方法使用函数f(x)的泰勒级数的前几项寻找方程f(x) = 0 的根。最大优点是在方程f(x)=0的单根附近具有平方收敛,该方法可以用来求方程的重根、复根。

    计算公式如下:

           设r是f(x)=0的根,选取x0作为r初始近似值,过点(x0,f(x0)),做曲线y=f(x)的切线L,L与x轴的交点的横坐标x1=x0-f(x0)/f'(x0),

    称x1是r的一次近似值,过点(x1,f(x1))做曲线y=f(x)的切线,求该切线与x轴的交点的横坐标为x2=x1-f(x1)/f'(x1),称x2为r的二次近似值。重复以上过程,知道r的近似值误足够小。

            

    解非线性方程f(x)=0的牛顿法是把非线性方程线性化的一种近似方法。把f(x)在x0点附近展开成泰勒级数 f(x) = f(x0)+(x-x0)f'(x0)+(x-x0)^2*f''(x0)/2! +… 取其线性部分,作为非线性方程f(x) = 0的近似方程,即泰勒展开的前两项,则有f(x0)+f'(x0)(x-x0)=0 设f'(x0)≠0则其解为x1=x0-f(x0)/f'(x0) 这样,得到牛顿法的一个迭代序列:x(n+1)=x(n)-f(x(n))/f'(x(n))。

    已经证明,如果是连续的,并且待求的零点是孤立的,那么在零点周围存在一个区域,只要初始值位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。

     

    C语言代码实现:

    #include<stdio.h>
    #include<math.h>
    
    
    
    double func(double x) //要求解的函数方程
    
    
    {
    
    
    	return x*x*x*x - 3 * x*x*x + 1.5*x*x - 4.0;
    
    
    }
    
    
    double func1(double x) //导函数
    
    
    {
    
    
    	return 4 * x*x*x - 9 * x*x + 3 * x;
    
    
    }
    
    
    
    
    int Newton(double *x, double precision, int maxcyc)//maxcyc 最大迭代次数
    
    
    {
    	double x1, x0;
    
    
    	int k;
    
    
    	x0 = *x;
    
    
    	for (k = 0; k < maxcyc; k++)
    
    
    	{
    
    
    		if (func1(x0) == 0.0)
    
    
    		{
    
    
    			printf("迭代过程中导数为0\n");
    
    
    			return 0;
    
    
    		}
    
    
    		x1 = x0 - func(x0) / func1(x0);
    
    
    		if (fabs(x1 - x0) < precision || fabs(func(x1)) < precision)//达到设定的精度
    
    
    		{
    
    			*x = x1;
    			return 1;
    
    
    		}
    
    
    		else
    
    
    			x0 = x1; //准备下次迭代
    
    	}
    
    
    	printf("迭代次数超过预期!\n"); //迭代次数达到,仍没有达到精度
    
    
    	return 0;
    
    
    }
    
    
    
    int main()
    
    
    {
    
    
    	double x, precision;
    
    
    	int maxcyc;
    
    
    	printf("输入初始迭代值x0");
    
    
    	scanf("%lf", &x);
    
    
    	printf("输入最大迭代次数:");
    
    
    	scanf("%d", &maxcyc);
    
    
    	printf("请输入迭代要求的精度:");
    
    
    	scanf("%lf", &precision);
    
    
    	if (Newton(&x, precision, maxcyc) == 1)
    
    
    		printf("该值附近的根为:%lf\n", x);
    
    
    	else
    
    		printf("迭代失败!\n");
    
    
    	while(1);
    
    
    	return 0;
    
    
    }

     

     

    C++实现:

    //此函数是用来求3元一次方程ax^3+bx^2+cx+d=0的解
    
    //比如 x^3-27=0,我们就可以输入1 0 0 -27,这样我们就可以得到一个解
    
    #include<iostream>
    
    #include<cmath>
    
    using namespace std;
    
    int main()
    
    {double diedai(double a,double b,double c,double d,double x);
    
    double a,b,c,d;
    
    double x=10000.0;
    
    cout<<"请依次输入方程四个系数:";
    
    cin>>a>>b>>c>>d;
    
    x=diedai(a,b,c,d,x);
    
    cout<<x<<endl;
    
    return 0;}
    
    double diedai(double a,double b,double c,double d,double x)
    
    {while(abs(a*x*x*x+b*x*x+c*x+d)>0.000001)
    
    {x=x-(a*x*x*x+b*x*x+c*x+d)/(3*a*x*x+2*b*x+c);
    
    }return x;}
    
    

     

    Matlab实现:

    %定义函数
    function y=f(x)
    y=f(x) ;%函数f(x)的表达式
    function z=f(x)
    z=h(x) ;%函数f(x)的导函数表达式
    
    %主程序
    x=X;%迭代初始值
    i=0;
    while i<I%迭代次数
    x0 = X - f(X)/h(X);%牛顿迭代格式
    if abs(x0-X)>;esp;%收敛判断
    X=x0;
    else break;
    end
    i =i+1;
    end
    fprintf('\n%s%.4f\t%s%d','X=',X,'i=',i);%输出结果
    

     

     

     

     

    展开全文
  • 数据集征兵抽签1-366号y366个不同的人抽x结果表明生日靠后的人易抽到小号概念最小二乘法多项式曲线拟合,根据给定的m个点,并不要求这条曲线精确地经过这些点,而是曲线y=f(x)的近似曲线y= φ(x)。原理 给定数据点pi...

    概念

    最小二乘法多项式曲线拟合,根据给定的m个点,并不要求这条曲线精确地经过这些点,而是曲线y=f(x)的近似曲线y= φ(x)。

    原理

     给定数据点pi(xi,yi),其中i=1,2,…,m。求近似曲线y= φ(x)。并且使得近似曲线与y=f(x)的偏差最小。近似曲线在点pi处的偏差δi= φ(xi)-y,i=1,2,...,m。 
    

    常见的曲线拟合方法:

     1.使偏差绝对值之和最小
    

     2.使偏差绝对值最大的最小
    

     3.使偏差平方和最小
    

    按偏差平方和最小的原则选取拟合曲线,并且采取二项式方程为拟合曲线的方法,称为最小二乘法。

    推导过程:

    1. 设拟合多项式为:

    2. 各点到这条曲线的距离之和,即偏差平方和如下:

    3. 为了求得符合条件的a值,对等式右边求ai偏导数:
      注意每个变量仍有下标i,且[]外的x也有被∑累加(sum)

                       .......
      

    4. 将等式左边进行一下化简,然后应该可以得到下面的等式:

                   .......
      

    5. 把这些等式表示成矩阵的形式,就可以得到下面的矩阵:

    6. 将这个范德蒙得矩阵化简后可得到:

    7. 也就是说X*A=Y,那么A = (X’*X)-1*X’*Y,便得到了系数矩阵A,同时,我们也就得到了拟合曲线

    以5.中公式为例,Python代码.

    数据集:征兵抽签1-366号(y),366个不同的人抽(x)。结果表明生日靠后的人易抽到小号

    # coding=utf-8  
    
    ''' 
    多项式曲线拟合算法 
    '''  
    import matplotlib.pyplot as plt  
    from math import *
    import numpy  
    import random  
    
    fig = plt.figure()  
    ax = fig.add_subplot(111)  
    
    '阶数为9阶 n=9=k'
    order=9  
    '被拟合的点'
    xa = []  
    ya = [] 
    '画图时,点的取值范围和点的密度。根据源数据点进行推断'
    start = 1 # -1
    end = 367 # 1
    step = (start + end)/200.0
    # 实验得步长不影响图形的弯曲程度
    # 此概念与KDE核密度的宽度不同
    # 因为系数a0,a1,a2...已经得到,此处步长只影响画图质量,可随意设置
    
    #生成样例曲线上的各个点 100个
    x = numpy.arange(start, end, step)  
    # y = [((a*a-1)*(a*a-1)*(a*a-1)+0.5)*numpy.sin(a*2) for a in x]  
    y = [((a*a-1)**3 + 0.5)*sin(2*a) for a in x]
    #print x
    #print y
    
    # print z
    # 生成的原曲线
    #ax.plot(x,y,color='r',linestyle='-',marker='.')  
    #,label="(a*a-1)*(a*a-1)*(a*a-1)+0.5"  
    
    #生成的曲线上的各个点随机偏移一下,并放入到xa,ya中去  
    i = 0  
    ##############################
    #生成xa ya的源数据点
    ##############################
    
    '''
    for xx in x:  
        yy = y[i]  
        # 偏移宽度(-40%,+40%)
        d = float(random.randint(60,140))/100  
        #ax.plot([xx*d],[yy*d],color='m',linestyle='',marker='.')  
        i += 1  
        xa.append(xx*d)  
        ya.append(yy*d)  
    
    '''
    d = []
    ya = [i for i in range(start, end)]
    random.shuffle(ya)
    xa = range(start, end)
    
    
    #d = tuple(zip(xa, ya))
    for i in range(len(xa)):
        d.append([xa[i],ya[i]])
    # print d
    nd = numpy.array(d)
    
    
    ax.plot(nd[:, 0], nd[:, 1], 'o', color="white", markersize=7, linewidth=3)
    
    # 偏移之后的点图
    #ax.plot(xa,ya,color='m',linestyle='',marker='.')  
    
    
    #进行曲线拟合  
    matA=[]  #整个多项式矩阵
    for i in range(0,order+1):  
        matA1=[]  # 每一行
        for j in range(0,order+1):  
            tx=0.0  # 每一列
            for k in range(0,len(xa)):  
                dx = 1.0  #  表示初始
                for l in range(0,j+i):  
                    # l为次数,对应一行的不同次的变量
                    # 本区域(重复)运行次数越多次数越高
                    # 第一次不运行此区域 表示n=dx
                    # 最后一次运行 2order次 即为x^2k(或n^2次)
                    dx = dx*xa[k]  
    
                tx += dx  
                # 运行n次(len(xa)次)后,tx为sum(x[i]^2k) 或 n (dx=1运行n次)
            matA1.append(tx)  
        matA.append(matA1)  
    
    #print(len(xa))  
    #print(matA[0][0])  
    
    # 转化为ndarray
    matA = numpy.array(matA)  
    
    matB = []  
    for k in range(0,order+1):  
        ty = 0.0  
        # 加和n个
        for i in range(0,len(xa)):  
            dy = 1.0  
            # 对于从i=1->n 求 (x[i])^(k-1)
            for l in range(0, k):  
                dy = dy * xa[i]  #dy即为公式中 (x[i])^k
            ty += ya[i] * dy  # 先乘完再加和
        matB.append(ty)  
    
    matB = numpy.array(matB)  
    
    # 多元一次 x^k为系数 a为未知数 求线性的a
    matAA = numpy.linalg.solve(matA,matB)  
    #得到系数矩阵
    
    
    # 下面画出拟合后的曲线  
    # a0 + a1*x + a2*x^2 +...+ ak*x^k
    
    #print(matAA)  
    xxa = numpy.arange(start, end, step)  
    yya = []  
    for i in range(0,len(xxa)):  
        yy = 0.0  
        for j in range(0,order+1):  
            dy = 1.0  
            for k in range(0,j):  
                dy *= xxa[i] # x^k
    
            # ak*x^k
            dy *= matAA[j]  # matAA[j]即为系数a 
            yy += dy  
        yya.append(yy)  
    ax.plot(xxa,yya,color='g',linestyle='-',marker='')  
    
    ax.legend()  
    plt.show() 

    遇到的问题:

    将一维数组变成二维
    zip返回列表内的元组:[(a,b), (c,d)]

    x = range(25)
    y = zip(*[iter(x)]*5)
    print y
    
    [(0,1,2,3,4),
    (5,6,7,8,9),
    (10,11,12,13,14),
    (15,16,17,18,19),
    (20,21,22,23,24)
    ]
    

    最小二乘法多项式曲线拟合原理
    在线拟合工具
    利用python搞机器学习——最小二乘法
    leastsq-wiki
    leastsq函数
    最小二乘法以及leastsq函数

    最大似然估计和最小二乘法怎么理解?
    最小二乘、极大似然、梯度下降有何区别
    最小二乘法和梯度下降法有哪些区别
    逻辑斯谛回归/曲线(方程、模型)
    梯度下降法,最小二乘法求线性回归
    python 分别用梯度下降法和最小二乘法求线性回归
    最小二乘法,牛顿法,梯度下降法以及比较

    展开全文
  • Lagrange 插值多项式的表达式例题Lagrange 基函数性质:Newton 插值多项式差商的性质:差商性质 1 :对称性例题差商性质 2带导数条件的插值多项式例题例题插值公式的误差例题:例 2 数据近似问题: 给定平面上 m+1 ...


    数据近似问题:
    给定平面上 m+1 个数据点 (xi,yi)(i=0,1,2,...,m){(x_i,y_i)}(i=0,1,2,...,m) 和一组函数 gk(x)(k=0,1,2,...,n)g_k(x)(k=0,1,2,...,n) (通常称为基函数),找一个函数 P(x),它是 gk(x)g_k(x) 的函数,按照某种标准,使 P(x)与这些数据点最接近。

    1. P(x)是 gk(x)(k=0,1,2,...,n)g_k(x)(k=0,1,2,...,n) 何种形式的函数。我们限定为如下形式:
      P(x)=α0g0(x)+α1g1(x)++αngn(x)P(x)=\alpha_0 g_0(x)+\alpha_1 g_1(x)+\cdots+\alpha_n g_n(x)
    2. 如何定义“ P(x)与这些数据点最接近”
    3. 插值函数与插值条件
      如果构成的函数 P(x)上述 a,b,c 三种标准能够达到值为 0,即
      P(xi)=pi=yi,i=0,1,2,&ThinSpace;,mP(x_i)=p_i=y_i,i=0,1,2,\cdots,m
      满足上式的函数 P(x)P(x) 称为插值数据点 {(xi,yi)}\{(x_i,y^i)\}插值函数,也称为插值条件

    多项式插值

    选取函数 gk(x)=xk(k=0,1,2,...,n)g_k(x)=x^k(k=0,1,2,...,n),
    则欲求的函数是 P(x)=α0+α1x+α2x2++αnxn=k=0nαkxkP(x) = {\alpha _0} + {\alpha _1}x + {\alpha _2}{x^2} + \cdots + {\alpha _n}{x^n} = \sum\limits_{k = 0}^n {{\alpha _k}} {x^k}{\rm{ }}
    由插值条件知:
    P(xi)=α0+α1xi+α2xi2++αnxin=yii=0,1,2,...,mP({x_i}) = {\alpha _0} + {\alpha _1}{x_i} + {\alpha _2}x_i^2 + \cdots + {\alpha _n}x_i^n = {y_i}{\rm{ }}i = 0,1,2,...,m
    这个线性方程组的矩阵形式是:
    (1x0x02x0n1x1x12x1n1x2x22x2n1xmxm2xmn)(α0α1α2αn)=(y0y1y2ym)\left( {\begin{matrix} 1&amp;{{x_0}}&amp;{x_0^2}&amp; \cdots &amp;{x_0^n}\\ 1&amp;{{x_1}}&amp;{x_1^2}&amp; \cdots &amp;{x_1^n}\\ 1&amp;{{x_2}}&amp;{x_2^2}&amp; \cdots &amp;{x_2^n}\\ \vdots &amp; \vdots &amp; \vdots &amp;{}&amp; \vdots \\ 1&amp;{{x_m}}&amp;{x_m^2}&amp; \cdots &amp;{x_m^n} \end{matrix}} \right)\left( {\begin{matrix} {{\alpha _{\rm{0}}}}\\ {{\alpha _{\rm{1}}}}\\ {{\alpha _{\rm{2}}}}\\ \vdots \\ {{\alpha _{\rm{n}}}} \end{matrix}} \right) = \left( {\begin{matrix} {{y_{\rm{0}}}}\\ {{y_{\rm{1}}}}\\ {{y_{\rm{2}}}}\\ \vdots \\ {{y_{\rm{m}}}} \end{matrix}} \right)
    求解得到 αk\alpha_k

    m>n 时,方程组无解
    m<n 时,方程组有无数多解
    所以讨论 m=n 时的情况,此时,系数矩阵是 n+1 阶的范德蒙矩阵。
    V=(1x0x02x0n1x1x12x1n1xnxn2xnn)V = \left( {\begin{matrix} 1&amp;{{x_0}}&amp;{x_0^2}&amp; \cdots &amp;{x_0^n}\\ 1&amp;{{x_1}}&amp;{x_1^2}&amp; \cdots &amp;{x_1^n}\\ \vdots &amp; \vdots &amp; \vdots &amp;{}&amp; \vdots \\ 1&amp;{{x_n}}&amp;{x_n^2}&amp; \cdots &amp;{x_n^n} \end{matrix}} \right)
    其行列式不为 0 时,方程组有唯一解。行列式为:det(V)=j=1n[i=0j1(xjxi)]\det (V) = \prod\limits_{j = 1}^n {\left[ {\prod\limits_{i = 0}^{j - 1} {\left( {{x_j} - {x_i}} \right)} } \right]}
    因此只要 xixjx_i \neq x_j ,就没有 0 因子,方程组就有唯一解。

    定理:
    若对 n+1 个数据点 (xi,yi)(i=0,1,2,...,m){(x_i,y_i)}(i=0,1,2,...,m),满足条件 xixj,i,j,ijx_i \neq x_j,\forall i,j,i\neq j ,则存在满足插值条件 P(xi)=pi=yi,i=0,1,2,...,nP(x_i)=p_i=y_i,i=0,1,2,...,n 的唯一的形如 P(x)=k=0nakxkP(x)=\sum_{k=0}^{n}a_kx^k 的次数不超过 n 的多项式。

    这样的多项式称为数据点的插值多项式

    例题

    给定数据点 ${ ( - 1, - 7),(1,7),(2, - 4),(5,35)} $ 可得线型方程组:
    (1111111112481525125)(α0α1α2α3)=(77435)\left( {\begin{matrix} 1&amp;{ - 1}&amp;1&amp;{ - 1}\\ 1&amp;1&amp;1&amp;1\\ 1&amp;2&amp;4&amp;8\\ 1&amp;5&amp;{25}&amp;{125} \end{matrix}} \right)\left( {\begin{matrix} {{\alpha _0}}\\ {{\alpha _1}}\\ {{\alpha _2}}\\ {{\alpha _3}} \end{matrix}} \right) = \left( {\begin{matrix} { - 7}\\ 7\\ { - 4}\\ {35} \end{matrix}} \right)
    解得 α0=10,α1=5,α2=10,α3=2{\alpha _0} = 10,{\alpha _1} = 5,{\alpha _2} = - 10,{\alpha _3} = 2
    所求的插值多项式为 P(x)=10+5x10x2+2x3P(x) = 10 + 5x - 10{x^2} + 2{x^3}

    性能

    1. 插值多项式计算一个方程组的时间复杂度是 O(n3)O(n^3)( 即解线性方程组的时间复杂度)
    2. 范德蒙矩阵的条件数常常比较大,使得解的精确度不高。条件数过大,就说明这个方程组是病态方程组。

    计算下列范德蒙矩阵的条件数。

    下面是 2 到 20 的范德蒙矩阵的条件数计算结果, 2 到 19 的全部被压在下面了。

    如果我们对 y 轴取对数:

    x = [2:50];
    y=x;
    for a=2:50
        y(a-1)=log(cond(vander(1:a)));
    end
    y
    plot(x, y)
    
    可以看到取对数之后基本上是一条直线,说明条件数随阶数 n 的增长指数级增长。

    Lagrange 形式

    即拉格朗日形式.

    因式定理

    n 次多项式 p(x)p(x) 具有 r 次因式 (x-a)的充要条件是 p(a)=p(a)=p(a)==p(r1)(a)=0p(a) = p&#x27;(a) = p&#x27;&#x27;(a) = \cdots = {p^{(r - 1)}}(a) = 0 ,即
    P(x)=(xa)rQ(x)P(x)=(x-a)^rQ(x)

    推导 Lagrange 插值多项式的表达式

    1. 首先看最简单的情况下的情况
      n=1 时,过 (x0,y0),(x1,y1)({x_0},{y_0}),({x_1},{y_1}) 的直线,
      p1(x)=y0+y1y0x1x0(xx0=y0+xx0x1x0(y1y0)=y0xx0x1x0y0+xx0x1x0y1{p_1}(x) = {y_0} + \frac{{{y_1} - {y_0}}}{{{x_1} - {x_0}}}(x - {x_0} \\ = {y_0} + \frac{{x - {x_0}}}{{{x_1} - {x_0}}}({y_1} - {y_0})\\ = {y_0} - \frac{{x - {x_0}}}{{{x_1} - {x_0}}}{y_0} + \frac{{x - {x_0}}}{{{x_1} - {x_0}}}{y_1}
      因此有 p1(x)=xx1x0x1y0+xx0x1x0y1{p_1}(x) = \frac{{x - {x_1}}}{{{x_0} - {x_1}}}{y_0} + \frac{{x - {x_0}}}{{{x_1} - {x_0}}}{y_1}
      p1(x){p_1}(x) 为已知函数 xx1x0x1,xx0x1x0\frac{{x - {x_1}}}{{{x_0} - {x_1}}},\frac{{x - {x_0}}}{{{x_1} - {x_0}}} 的线型组合,且组合系数为 y0,y1{y_0},{y_1}
    2. 复杂的情况
      因此可以设想,n+1 个点的 n 次插值多项式应该为
      pn(x)=l0(x)y0+l1(x)y1++ln(x)yn{p_n}(x) = {l_0}(x){y_0} + {l_1}(x){y_1} + \cdots + {l_n}(x){y_n}
      其中, li(x)(i=0,1,...,n){l_i}(x)(i = 0,1,...,n) 为 x 的 n 次式。
      在多项式的形式中,我们是先定基函数,再求系数。 Lagrange 形式与之相反,先定系数,再求多项式。
      我们可以将数据点进行类似线性表出的操作,即将 x0,x1,&ThinSpace;,xnx_0,x_1,\cdots,x_n 看做坐标轴,则
      (y0,y1,&ThinSpace;,yn)=y0(1,0,&ThinSpace;,0)+y1(0,1,&ThinSpace;,0)++yn(0,0,&ThinSpace;,1)(y_0,y_1,\cdots,y_n)=y_0(1,0,\cdots,0)+y_1(0,1,\cdots,0)+\cdots+y_n(0,0,\cdots,1)
      y0=1,y1=y2==yn=0{y_0} = 1,{y_1} = {y_2} = \cdots = {y_n} = 0 时, pn(x)=l0(x){p_n}(x) = {l_0}(x)
      l0(x)l_0(x) 是满足差值条件 l0(x0)=1,l0(x1)=l0(x2)==l0(xn)=0{l_0}({x_0}) = 1,{\rm{ }}{l_0}({x_1}) = {l_0}({x_2}) = \cdots = {l_0}({x_n}) = 0 的插值多项式。即表明 x1,x2,...,xn{x_1},{x_2},...,{x_n}l0(x)l_0(x) 的零点。
      l0(x)l_0(x) 必有因式 (xx1)(xx2)...(xxn)(x - {x_1})(x - {x_2})...(x - {x_n})
      由于 l0(x)l_0(x) 为 n 次多项式,可知 l0(x)=c(xx1)(xx2)...(xxn){l_0}(x) = c(x - {x_1})(x - {x_2})...(x - {x_n})
      由条件 l0(x0)=1{l_0}({x_0}) = 1 可知:
      c=1(x0x1)(x0x2)(x0xn)c = \frac{1}{{({x_0} - {x_1})({x_0} - {x_2}) \cdots ({x_0} - {x_n})}}
      l0(x)=(xx1)(xx2)(xxn)(x0x1)(x0x2)(x0xn){l_0}(x) = \frac{{(x - {x_1})(x - {x_2}) \cdots (x - {x_n})}}{{({x_0} - {x_1})({x_0} - {x_2}) \cdots ({x_0} - {x_n})}}
      以此类推
      i=0,1,...,ni = 0,1,...,n
      li(x)=(xx0)(xxi1)(xxi+1)(xxn)(xix0)(xixi1)(xixi+1)(xixn)=j=0,jinxxjxixj{l_i}(x) = \frac{{(x - {x_0}) \cdots (x - {x_{i - 1}})(x - {x_{i + 1}}) \cdots (x - {x_n})}}{{({x_i} - {x_0}) \cdots ({x_i} - {x_{i - 1}})({x_i} - {x_{i + 1}}) \cdots ({x_i} - {x_n})}} = \prod\limits_{j=0,j\neq i}^n {\frac{{x - {x_j}}}{{{x_i} - {x_j}}}}
      ω(x)=k=0n(xxk),ω(xi)=k=0,kjn(xixk)\omega (x) = \prod\limits_{k = 0}^n {(x - {x_k})} ,{\rm{ }}\omega &#x27;({x_i}) = \prod\limits_{k=0,k\neq j}^n {({x_i} - {x_k})}
      因为,令 w(x)=(xxi)Q(x)w(x)=(x-x_i)Q(x),w(x)=Q(x)+(xxi)Q(x)w&#x27;(x)=Q(x)+(x-x_i)Q&#x27;(x) ,所以 w(xi)=Q(x)w&#x27;(x_i)=Q(x)
      li(x)=ω(x)(xxi)ω(xi){l_i}(x) = \frac{{\omega (x)}}{{(x - {x_i})\omega &#x27;({x_i})}}
      称为Lagrange 插值多项式Lagrange 基函数

    Lagrange 多项式形式为:
    L(x)=i=0nyili(x)=i=0nyiω(x)(xxi)ω(xi)L(x) = \sum\limits_{i = 0}^n {{y_i}{l_i}(x)} = \sum\limits_{i = 0}^n {{y_i}\frac{{\omega (x)}}{{(x - {x_i})\omega &#x27;({x_i})}}}

    例题

    Lagrange 基函数性质:

    1. li(xi)=1{l_i}({x_i}) = 1
    2. li(xj)=0,ij{l_i}({x_j}) = 0,{\rm{ }}i \ne j
    3. li(xj)lj(xj)=0,li(xi)lj(xi)=0{l_i}({x_j}){l_j}({x_j}) = 0,{\rm{ }}{l_i}({x_i}){l_j}({x_i}) = 0
      即正交性。
    4. i=0nli(x)=1\sum\limits_{i = 0}^n {{l_i}(x)} = 1
      任何数的 Lagrange 基函数之和一定为 1

    Newton 插值多项式

    上述两个插值多项式有一个同样的缺点,在 n+1 个数据点求出插值多项式之后,如果再获取新的数据,需要连同原有的 n+1 个数据点一起求出插值多项式。每个 Lagrange 基函数都包含了所有点的信息,具有全局特性。

    Lk(x)L_k(x) 为以 {(xi,yi)}(i=0,1,2,...,k)\left\{ {\left( {{x_i},{y_i}} \right)} \right\}(i = 0,1,2,...,k) 为插值数据点的 k 次 Lagrange 形式的插值多项式,则 n 次插值多项式可以表示为
    Ln(x)=L0(x)+[L1(x)L0(x)]+[L2(x)L1(x)]++[Ln(x)Ln1(x)]{L_n}(x) = {L_0}(x) + \left[ {{L_1}(x) - {L_0}(x)} \right] + \left[ {{L_2}(x) - {L_1}(x)} \right] + \cdots + \left[ {{L_n}(x) - {L_{n - 1}}(x)} \right]
    Qk(x)=Lk(x)Lk1(x){Q_k}(x) = {L_k}(x) - {L_{k - 1}}(x) ,且为一个 k 次多项式,因此
    Ln(x)=L0(x)+k=1nQk(x) {L_n}(x) = {L_0}(x) + \sum\limits_{k = 1}^n {{Q_k}(x)}
    Lk(x)=Lk1(x)+Qk(x){L_k}(x) = {L_{k - 1}}(x) + {Q_k}(x)
    L0(x)=y0{L_0}(x) = {y_0}
    因为 Qk(xi)=Lk(xi)Lk1(xi)=yiyi=0,i=0,1,2,...,k1{Q_k}({x_i}) = {L_k}({x_i}) - {L_{k - 1}}({x_i}) = {y_i} - {y_i} = 0,i = 0,1,2,...,k - 1
    因为 QkQ_k 为 k 次多项式,而且它的零点为 x0,x1,,xk1x_0,x_1,\dots,x_{k-1} ,具有形式:
    Qk(x)=αk(xx0)(xx1)(xxk1){Q_k}(x) = {\alpha _k}(x - {x_0})(x - {x_1}) \cdots (x - {x_{k - 1}})
    因此:

    Ln(x)=L0(x)+k=1nQk(x)=L0(x)+k=1nαk(xx0)(xx1)(xxk1)=α0+α1(xx0)+α2(xx0)(xx1)+α3(xx0)(xx1)(xx2)++αn(xx0)(xx1)(xxn1){L_n}(x) = {L_0}(x) + \sum\limits_{k = 1}^n {{Q_k}(x)} \\ = {L_0}(x) + \sum\limits_{k = 1}^n {{\alpha _k}(x - {x_0})(x - {x_1}) \cdots (x - {x_{k - 1}})}\\ \begin{array}{l} = {\alpha _0} + {\alpha _1}(x - {x_0}) + {\alpha _2}(x - {x_0})(x - {x_1}) + {\alpha _3}(x - {x_0})(x - {x_1})(x - {x_2}) + \cdots \\ {\rm{ }} + {\alpha _n}(x - {x_0})(x - {x_1}) \cdots (x - {x_{n - 1}}) \end{array}
    由插值条件得:
    {α0=y0α0+α1(x1x0)=y1α0+α1(x2x0)+α2(x2x0)(x2x1)=y2α0+α1(xnx0)+α2(xnx0)(xnx1)++αn(xnx0)(xnx1)(xnxn1)=yn\left\{ \begin{array}{l} {\alpha _0} = {y_0}\\ {\alpha _0} + {\alpha _1}({x_1} - {x_0}) = {y_1}\\ {\alpha _0} + {\alpha _1}({x_2} - {x_0}) + {\alpha _2}({x_2} - {x_0})({x_2} - {x_1}) = {y_2}\\ \cdots \\ {\alpha _0} + {\alpha _1}({x_n} - {x_0}) + {\alpha _2}({x_n} - {x_0})({x_n} - {x_1}) + \cdots \\ {\rm{ }} + {\alpha _n}({x_n} - {x_0})({x_n} - {x_1}) \cdots ({x_n} - {x_{n - 1}}) = {y_n} \end{array} \right.
    逐个解出 α0,α1,...,αn{\alpha _0},{\alpha _1},...,{\alpha _n}
    α0=y0{\alpha _0} = {y_0}
    α1=(y1y0)/(x1x0){\alpha _1} = ({y_1} - {y_0})/({x_1} - {x_0})
    α2=[(y2y0)/(x2x0)(y1y0)/(x1x0)]/(x2x1){\alpha _2} = \left[ {({y_2} - {y_0})/({x_2} - {x_0}) - ({y_1} - {y_0})/({x_1} - {x_0})} \right]/({x_2} - {x_1})
    \vdots
    如果采用记号:
    {y[xi]=yi,i=0,1,2,...,ny[xi,xi+1]=y[xi+1]y[xi]xi+1xi,i=0,1,2,...,n1y[xi,xi+1,xi+2]=y[xi,xi+2]y[xi,xi+1]xi+2xi+1,i=0,1,2,...,n2y[xi,xi+1,xi+2,xi+3]=y[xi,xi+1,xi+3]y[xi,xi+1,xi+2]xi+3xi+2,i=0,1,2,...,n3y[x0,x1,&ThinSpace;,xn]=y[x0,x1,&ThinSpace;,xn2,xn]y[x0,x1,&ThinSpace;,xn1]xnxn1\left\{ \begin{array}{l} y[{x_i}] = {y_i}{\rm{ }},i = 0,1,2,...,n\\ y[{x_i},{x_{i + 1}}] = \frac{{y[{x_{i + 1}}] - y[{x_i}]}}{{{x_{i + 1}} - x{}_i}}{\rm{ }},i = 0,1,2,...,n - 1\\ y[{x_i},{x_{i + 1}},{x_{i + 2}}] = \frac{{y[{x_i},{x_{i + 2}}] - y[{x_i},{x_{i + 1}}]}}{{{x_{i + 2}} - x{}_{i + 1}}}{\rm{ }},i = 0,1,2,...,n - 2\\ y[{x_i},{x_{i + 1}},{x_{i + 2}},{x_{i + 3}}] = \frac{{y[{x_i},{x_{i + 1}},{x_{i + 3}}] - y[{x_i},{x_{i + 1}},{x_{i + 2}}]}}{{{x_{i + 3}} - x{}_{i + 2}}}{\rm{ }},i = 0,1,2,...,n - 3\\ \cdots \\ y[{x_0},{x_1}, \cdots ,{x_n}] = \frac{{y[{x_0},{x_1}, \cdots ,{x_{n - 2}},{x_n}] - y[{x_0},{x_1}, \cdots ,{x_{n - 1}}]}}{{{x_n} - x{}_{n - 1}}} \end{array} \right.
    式中,从上往下分别为零阶差商、一阶差商、二阶差商、…n 阶差商。
    则有:
    {α0=y[x0]α1=y[x0,x1]α2=y[x0,x1,x2]αn=y[x0,x1,x2,&ThinSpace;,xn]\left\{ \begin{array}{l} {\alpha _0} = y[{x_0}]\\ {\alpha _1} = y[{x_0},{x_1}]\\ {\alpha _2} = y[{x_0},{x_1},{x_2}]\\ \cdots \\ {\alpha _n} = y[{x_0},{x_1},{x_2}, \cdots ,{x_n}] \end{array} \right.

    插值公式可以表示为:
    Nn(x)=y[x0]+y[x0,x1](xx0)+y[x0,x1,x2](xx0)(xx1)++y[x0,x1,x2,&ThinSpace;,xn](xx0)(xx1)(xxn1)\begin{array}{l} {N_n}(x) = y[{x_0}] + y[{x_0},{x_1}](x - {x_0}) + y[{x_0},{x_1},{x_2}](x - {x_0})(x - {x_1}) + \\ \cdots + y[{x_0},{x_1},{x_2}, \cdots ,{x_n}](x - {x_0})(x - {x_1}) \cdots (x - {x_{n - 1}}) \end{array}
    所以,为了得到插值多项式,必须先计算各阶差商,但是上述定义不变计算。

    差商的性质:

    差商性质 1 :对称性

    我们在前面得到了插值公式,计算 n 阶差商需要计算 n-1 阶差商,比如计算 y[x0,x1,&ThinSpace;,xn]=y[x0,x1,&ThinSpace;,xn2,xn]y[x0,x1,&ThinSpace;,xn1]xnxn1y[{x_0},{x_1}, \cdots ,{x_n}] = \frac{{y[{x_0},{x_1}, \cdots ,{x_{n - 2}},{x_n}] - y[{x_0},{x_1}, \cdots ,{x_{n - 1}}]}}{{{x_n} - x{}_{n - 1}}} ,需要计算 y[x0,x1,&ThinSpace;,xn2,xn]y[{x_0},{x_1}, \cdots ,{x_{n - 2}},{x_n}],计算量巨大。

    对于任何正整数 k,k 阶差商与点的排列无关,即若 j0,j1,&ThinSpace;,jk{j_0,j_1,\cdots,j_k}{i,i+1,...,i+k}\{ i,i + 1,...,i + k\} 的任意一种排列,则
    y[xi,xi+1,xi+2,...,xi+k]=y[xj0,xj1,xj2,...,xjk]y[{x_i},{x_{i + 1}},{x_{i + 2}},...,{x_{i + k}}] = y[{x_{{j_0}}},{x_{{j_1}}},{x_{{j_2}}},...,{x_{{j_k}}}]

    证明:
    零阶差商是满足该性质的。
    一阶差商
    y[xi,xi+1]=y[xi+1]y[xi]xi+1xi=y[xi]y[xi+1]xixi+1=y[xi+1,xi]{\rm{ }}y[{x_i},{x_{i + 1}}] = \frac{{y[{x_{i + 1}}] - y[{x_i}]}}{{{x_{i + 1}} - x{}_i}}{\rm{ = }}\frac{{y[{x_i}] - y[{x_{i + 1}}]}}{{{x_i} - x{}_{i + 1}}}{\rm{ = }}y[{x_{i + 1}},{x_i}]
    一阶差商也满足。

    {(xi,yi),...,(xi+k,yi+k)}\{ ({x_i},{y_i}),...,({x_{i + k}},{y_{i + k}})\}为插值数据点做 k 次插值多项式,
    Nn(x)=y[xi]+y[xi,xi+1](xxi)+y[xi,xi+1,xi+2](xxi)(xxi+1)++y[xi,xi+1,xi+2,&ThinSpace;,xi+k](xxi)(xxi+1)(xxi+k1)\begin{array}{l} {N_n}(x) = y[{x_i}] + y[{x_i},{x_{i + 1}}](x - {x_i}) + y[{x_i},{x_{i + 1}},{x_{i + 2}}](x - {x_i})(x - {x_{i + 1}}) + \\ {\rm{ }} \cdots + y[{x_i},{x_{i + 1}},{x_{i + 2}}, \cdots ,{x_{i + k}}](x - {x_i})(x - {x_{i + 1}}) \cdots (x - {x_{i + k - 1}}) \end{array}
    其最高项系数为: y[xi,xi+1,xi+2,&ThinSpace;,xi+k]y[{x_i},{x_{i + 1}},{x_{i + 2}}, \cdots ,{x_{i + k}}]
    若以 ${ ({x_{{j_0}}},{y_{{j_0}}}),({x_{{j_1}}},{y_{{j_1}}}),…,({x_{{j_k}}},{y_{{j_k}}})} $ 为数据点:
    Nn___(x)=y[xj0]+y[xj0,xj1](xxj0)+y[xj0,xj1,xj2](xxj0)(xxj1)++y[xj0,xj1,xj2,&ThinSpace;,xjk](xxj0)(xxj1)(xxjk)\begin{array}{l} {\mathop N\limits^{\_\_\_} _n}(x) = y[{x_{{j_0}}}] + y[{x_{{j_0}}},{x_{{j_1}}}](x - {x_{{j_0}}}) + y[{x_{{j_0}}},{x_{{j_1}}},{x_{{j_2}}}](x - {x_{{j_0}}})(x - {x_{{j_{\rm{1}}}}}) + \\ {\rm{ }} \cdots + y[{x_{{j_{\rm{0}}}}},{x_{{j_1}}},{x_{{j_{\rm{2}}}}}, \cdots ,{x_{{j_{\rm{k}}}}}](x - {x_{{j_0}}})(x - {x_{{j_1}}}) \cdots (x - {x_{{j_k}}}) \end{array}
    最高项系数为 y[xj0,xj1,...,xjk]y[{x_{{j_0}}},{x_{{j_1}}},...,{x_{{j_k}}}]
    因为插值多项式具有唯一性,所以 NK(x)=Nk__(x){N_K}(x) = {\mathop N\limits^{\_\_} _k}(x) ,最高项系数是相同的。
    因此 y[xi,xi+1,...,xi+k]=y[xj0,xj1,...,xjk]y[{x_i},{x_{i + 1}},...,{x_{i + k}}] = y[{x_{{j_0}}},{x_{{j_1}}},...,{x_{{j_k}}}]
    证毕。

    因此有:
    y[xi,xi+1]=y[xi]y[xi+1]xixi+1y[{x_i},{x_{i + 1}}] = \frac{{y[{x_i}] - y[{x_{i + 1}}]}}{{{x_i} - x{}_{i + 1}}}
    y[xi,xi+1,xi+2]=y[xi,xi+2]y[xi,xi+1]xi+2xi+1=y[xi+1,xi+2,xi]=y[xi+1,xi]y[xi+1,xi+2]xixi+2y[{x_i},{x_{i + 1}},{x_{i + 2}}] = \frac{{y[{x_i},{x_{i + 2}}] - y[{x_i},{x_{i + 1}}]}}{{{x_{i + 2}} - x{}_{i + 1}}}= y[{x_{i + 1}},{x_{i + 2}},{x_i}] = \frac{{y[{x_{i + 1}},{x_i}] - y[{x_{i + 1}},{x_{i + 2}}]}}{{{x_i} - x{}_{i + 2}}}

    y[xi,xi+1,xi+2]=y[xi,xi+1]y[xi+1,xi+2]xixi+2\therefore {\rm{ }}y[{x_i},{x_{i + 1}},{x_{i + 2}}] = \frac{{y[{x_i},{x_{i + 1}}] - y[{x_{i + 1}},{x_{i + 2}}]}}{{{x_i} - x{}_{i + 2}}}
    同理:
    y[xi,xi+1,xi+2,xi+3]=y[xi,xi+1,xi+2]y[xi+1,xi+2,xi+3]xixi+3y[{x_i},{x_{i + 1}},{x_{i + 2}},{x_{i + 3}}] = \frac{{y[{x_i},{x_{i + 1}},{x_{i + 2}}] - y[{x_{i + 1}},{x_{i + 2}},{x_{i + 3}}]}}{{{x_i} - x{}_{i + 3}}}
    构造差商表:

    Nn(x)=y[x0]+y[x0,x1](xx0)+y[x0,x1,x2](xx0)(xx1)++y[x0,x1,x2,&ThinSpace;,xn](xx0)(xx1)(xxn1)\begin{array}{l} {N_n}(x) = y[{x_0}] + y[{x_0},{x_1}](x - {x_0}) + y[{x_0},{x_1},{x_2}](x - {x_0})(x - {x_1}) + \\ {\rm{ }} \cdots + y[{x_0},{x_1},{x_2}, \cdots ,{x_n}](x - {x_0})(x - {x_1}) \cdots (x - {x_{n - 1}}) \end{array}

    例题

    构造差商标的过程

    差商性质 2

    设函数 y(k)有 k 阶连续导数
    y[xi,xi+1,xi+2,...,xi+k]=y(k)(ξ)k!,ξ(xi,xi+k)y[{x_i},{x_{i + 1}},{x_{i + 2}},...,{x_{i + k}}] = \frac{{{y^{(k)}}(\xi )}}{{k!}}{\rm{ }},\xi \in ({x_i},{x_{i + k}})

    证明:
    xjx_j 满足 xj&lt;xj+1,(j=i,i+1,...,i+k1){x_j} &lt; {x_{j + 1}}, (j = i,i + 1,...,i + k - 1) ,即这些点的顺序是从左向右依次递增的。这为区间的表示提供了方便。
    以数据点
    {(xi,yi),(xi+1,yi+1),...,(xi+k1,yi+k1),(x,y)}\{ ({x_i},{y_i}),({x_{i + 1}},{y_{i + 1}}),...,({x_{i + k - 1}},{y_{i + k - 1}}),(\overline x ,\overline y )\}
    (一共 k+1 个点)为插值点的 k 次多项式为:
    Nk(x)=y[xi]+y[xi,xi+1](xxi)+y[xi,xi+1,xi+2](xxi)(xxi+1)+y[xi,xi+1,&ThinSpace;,xi+k1,x]j=ii+k1(xxj){N_k}(x) = y[{x_i}] + y[{x_i},{x_{i + 1}}](x - {x_i}) + y[{x_i},{x_{i + 1}},{x_{i + 2}}](x - {x_i})(x - {x_{i + 1}}) \cdots + y[{x_i},{x_{i + 1}}, \cdots ,{x_{i + k - 1}},\overline x ]\prod\limits_{j = i}^{i + k - 1} {(x - {x_j})}
    由于 Nk(xi)=yi{N_k}({x_i}) = {y_i}(j=i,i+1,...,i+k1)(j = i,i + 1,...,i + k - 1)Nk(x)=y{N_k}(\overline x ) = \overline y (即在前 k 个点上满足插值条件)。
    因此R(x)=y(x)Nk(x)R(x) = y(x) - {N_k}(x)( R(x)相当于误差,但是又不是误差)
    在包含xi,xi+1,...,xi+k1,x{x_i},{x_{i + 1}},...,{x_{i + k - 1}},\overline x的区间 II 中有 k+1 个零点。
    由罗尔定理知, R(x)R&#x27;(x) 在区间 II 中有 k 个零点,那么 R(x)R&#x27;&#x27;(x) 在区间 II 中有 k-1 个零点…R(k)(x)R^{(k)}(x) 在区间 II 中有 1 个零点。即存在 ξI\xi \in I ,满足:
    R(k)(ξ)=y(k)(ξ)Nk(k)(ξ)=0{R^{(k)}}(\xi ) = {y^{(k)}}(\xi ) - N_k^{(k)}(\xi ) = 0
    由于 Nk(x)N_{k}(x) 是首项系数为 y[xi,xi+1,...,xi+k1,x]y[{x_i},{x_{i + 1}},...,{x_{i + k - 1}},\overline x ] 的 k 次多项式。
    Nk(k)(ξ)=y[xi,xi+1,...,xi+k1,x]×k!N_{_k}^{(k)}(\xi ) = y[{x_i},{x_{i + 1}},...,{x_{i + k - 1}},\overline x ] \times k!
    y(k)(ξ)=Nk(k)(ξ)=y[xi,xi+1,...,xi+k1,x](k!)\therefore {\rm{ }}{y^{(k)}}(\xi ) = N_{_k}^{(k)}(\xi ) = y[{x_i},{x_{i + 1}},...,{x_{i + k - 1}},\overline x ](k!)
    x=xi+k\overline x {\rm{ = }}{x_{i + k}},有 y[xi,xi+1,...,xi+k1,xi+k]=y(k)(ξ)k!y[{x_i},{x_{i + 1}},...,{x_{i + k - 1}},{x_{i + k}}] = \frac{{{y^{(k)}}(\xi )}}{{k!}}
    (这里的 x\overline x 是数学上的一种手法,先设为一般形式,然后再把一般形式转变为特殊情况)
    证毕。

    带导数条件的插值多项式

    前面的插值多项式,满足的都是函数值条件,即 p(xi)=yip(x_i)=y_i
    在某些情况下,插值多项式 p(x)还要满足 p(xi)=yip&#x27;(x_i)=y&#x27;_i (例如在 PS 中,钢笔工具使用的时候,先画点,然后有一条要拖动的直线,直线的方向就代表了 p(xi)=yip&#x27;(x_i)=y&#x27;_i )。
    对于差商公式 y[xi,xi+1]=y(xi)y(xi+1)xixi+1y[{x_i},{x_{i + 1}}] = \frac{{y({x_i}) - y({x_{i + 1}})}}{{{x_i} - {x_{i + 1}}}} ,之前必须要求 xixj(ij)x_i \neq x_j(i\neq j) ,实际上可以放弃这个限制。
    y[xi,xi]=limΔx0y[xi,xi+Δx]=limΔx0y(xi+Δx)y(xi)Δx=limΔx0y(xi+Δx)y(xi)Δxy[{x_i},{x_i}] = \mathop {\lim }\limits_{\Delta x \to 0} y[{x_i},{x_i} + \Delta x] = \mathop {\lim }\limits_{\Delta x \to 0} \frac{{y({x_i} + \Delta x) - y({x_i})}}{{\Delta x}} = \mathop {\lim }\limits_{\Delta x \to 0} \frac{{y({x_i} + \Delta x) - y({x_i})}}{{\Delta x}}
    得到重节点差商公式。进一步根据差商公式性质 2 : y[xi,xi+1,xi+2,...,xi+k]=y(k)(ξ)k!y[{x_i},{x_{i + 1}},{x_{i + 2}},...,{x_{i + k}}] = \frac{{{y^{(k)}}(\xi )}}{{k!}} ,令 xi+jxi(j=1,2,...,k){x_{i + j}} \to {x_i}(j = 1,2,...,k),有:
    y[xi,xi,&ThinSpace;,xi]=y(k)(xi)k!y[x_i,x_i,\cdots,x_i]=\frac {y^{(k)}(x_i)}{k!}
    式中中括号里有 k+1 个 xix_i 。称为 k 重节点。

    例题

    求满足下表所列的插值条件的插值多项式。
    xi012yi115yi1 \begin{matrix} {{x_i}}&amp;0&amp;1&amp;2\\ {{y_i}}&amp;1&amp;{ - 1}&amp;5\\ {{{y&#x27;}_i}}&amp;{}&amp;1&amp;{}\\ \end{matrix}

    解:在 x=0 时, y=1y&#x27;=1 ,所以在 x=0 时有一阶重节点,故而取 x0=0,x1=x2=1,x3=2{x_0} = 0,{x_1} = {x_2} = 1,{x_3} = 2 ,利用重节点差商公式做差商表,按照牛顿插值公式的步骤即可。
    注意在下面红色的 1 处是 y[x1,x2]=y(x1)=y(1)=1{\rm{ }}y[{x_1},{x_2}] = y&#x27;({x_1}) = y&#x27;(1) = 1 ,所以为 1.

    对带有导数值的插值点进行插值所得到的多项式称为Hermite 插值多项式。它可以用牛顿插值公式得到,也可以用拉格朗日插值公式得到。

    上面例题中,插值多项式 p(x)p(x) 满足 p(0)=1,p(1)=1,p(2)=5,p(1)=1p(0) = 1,p(1) = - 1,p(2) = 5,p&#x27;(1) = 1 一共四个条件,因此应该是三次多项式。


    p(x)=y0H0(x)+y1H1(x)+y2H2(x)+y1H1__(x)p(x) = {y_0}{H_0}(x) + {y_1}{H_1}(x) + {y_2}{H_2}(x) + {{y&#x27;}_1}{\mathop H\limits^{\_\_} _1}(x)
    为所求的多项式。
    根据条件,可以设
    H0(x)=α0(x1)2(x2){H_0}(x) = {\alpha _0}{(x - 1)^2}(x - 2)
    H1(x)=(α1+β1x)x(x2){H_1}(x) = ({\alpha _1} + {\beta _1}x)x(x - 2)
    H2(x)=α2x(x1)2{H_2}(x) = {\alpha _2}x{(x - 1)^2}
    H1(x)=α__x(x1)(x2){\overline H _1}(x) = \mathop \alpha \limits^{\_\_} x(x - 1)(x - 2)
    由于 H0(0)=H1(1)=H2(2)=1{H_0}(0) = {H_1}(1) = {H_2}(2) = 1H1(1)=1{\overline {H&#x27;} _1}(1) = 1
    得到待定系数 α0=1/2,α1=1,β1=0,α2=1/2,α__=1{\alpha _0} = - 1/2,{\alpha _1} = - 1,{\beta _1} = 0,{\alpha _2} = 1/2,\mathop \alpha \limits^{\_\_} = - 1
    H0(x)=12(x1)2(x2),H1(x)=x(x2)H2(x)=12x(x1)2,H1__(x)=x(x1)(x2)\begin{matrix} {H_0}(x) = - \frac{1}{2}{(x - 1)^2}(x - 2),{H_1}(x) = - x(x - 2)\\ {H_2}(x) = \frac{1}{2}x{(x - 1)^2},{\mathop H\limits^{\_\_} _1}(x) = - x(x - 1)(x - 2) \end{matrix}
    因此 p(x)=H0(x)H1(x)+5H2(x)+H1__(x)=12x+3x(x1)+x(x1)2\begin{matrix} p(x) = {H_0}(x) - {H_1}(x) + 5{H_2}(x) + {\mathop H\limits^{\_\_} _1}(x)\\ {\rm{ }} = 1 - 2x + 3x(x - 1) + x{(x - 1)^2} \end{matrix}
    可以推广到一般情况
    设已知给定数据点 {(xi,yi)}(i=0,1,2,3,...,n)\{ ({x_i},{y_i})\} (i = 0,1,2,3,...,n)
    xix_i 处的导数值 yi(i=0,1,2,...n){{y&#x27;}_i}(i = 0,1,2,...n) ,满足条件
    {p(xi)=yip(xi)=yii=0,1,2,...,n\left\{ \begin{matrix} p({x_i}) = {y_i}\\ p&#x27;({x_i}) = {{y&#x27;}_i} \end{matrix} \right.{\rm{ }}i = 0,1,2,...,n
    插值多项式为 2n+1 次
    p(x)=k=0nyk[12lk(xk)(xxk)][lk(x)]2+k=0nyk(xxk)[lk(x)]2p(x) = \sum\limits_{k = 0}^n {{y_k}[1 - 2{{l&#x27;}_k}({x_k})(x - {x_k})]{{[{l_k}(x)]}^2}} + \sum\limits_{k = 0}^n {{{y&#x27;}_k}} (x - {x_k}){[{l_k}(x)]^2}
    其中 lk(x){l_k}(x) 为拉格朗日基本插值多项式。

    例题

    如果 y1y_1 的数据缺失,求满足下表所列的插值条件的插值多项式。
    xix0x1x2yiy0y2yiy1 \begin{matrix} {{x_i}}&amp;{x_0}&amp;{x_1}&amp;{x_2}\\ {{y_i}}&amp;{y_0}&amp;{}&amp;{y_2}\\ {{{y&#x27;}_i}}&amp;{}&amp;{y&#x27;_1}&amp;{}\\ \end{matrix}

    解:我们知道,牛顿插值多项式我为
    N2(x)=y0+y[x0,x1](xx0)+y[x0,x1,x2](xx0)(xx1)N_2(x)=y_0+y[x_0,x_1](x-x_0)+y[x_0,x_1,x_2](x-x_0)(x-x_1)
    但是这样无法求解,因为 y1y_1 未知,所以 y[x0,x1]y[x_0,x_1]y[