拉格朗日插值法与牛顿插值法

#include <stdio.h>
double x[15],y[15];
int n;
double f(double xx)  //利用拉格朗日插值函数 f(x) = sigma(（ x-xj ）/(xk-xj)*yk)  k=1,2,3,4,……
{
    double ans=0;
    double  deno=1,nomi=1;
    for(int i=1;i<=n;i++)
    {
        deno=1;
        nomi=1;
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                deno*=(xx-x[j]);
                nomi*=(x[i]-x[j]);
            }

        }
        ans+=(deno/nomi)*y[i];
    }
    return ans;
}
int main()
{
    double fx=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&x[i]);
        scanf("%lf",&y[i]);
    }
    double xx;
    while(scanf("%lf",&xx)!=EOF)
    {
    fx=f(xx);
    printf("%lf\n",fx);
    }
    return 0;

#include <bits/stdc++.h>
using namespace std;
const int maxn=20;
double x[maxn];
double y[maxn];
double a[maxn];
int n;
double getfx(int k)
{
    double fenzi;
    double fenmu;
    double ans=0;
    for(int i=1;i<=k;i++)
    {
         fenzi=y[i];
         fenmu=1;
        for(int j=1;j<=k;j++)
        {
            if(i==j)continue;
            fenmu=fenmu*(x[i]-x[j]);
        }
        ans+=fenzi/fenmu;
    }
    return ans;
}
double getnx(double xc)
{
    double t=1.0,ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]*t;
        t=t*(xc-x[i]);
        //cout<<ans<<" "<<t<<endl;
    }

    return ans;
}

int main()
{

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&x[i]);
        scanf("%lf",&y[i]);
    }
    for(int i=1;i<=n;i++)
    {
         a[i]=getfx(i);

         cout<<"第"<<i<<"阶差商   "<<a[i]<<endl;
    }
    double xx;
    while(scanf("%lf",&xx)!=EOF)
    {
        printf("%.6lf",getnx(xx));
    }
    return 0;
}

总结：拉格朗日插值法和牛顿插值法可以使得插值函数完美的匹配给定的节点，在一般情况下，拉格朗日插值法就能满足我们对于给定样本进行插值的要求，但是当我们给定的节点个数在不断增多的时候，拉格朗日插值法每次都必须重新计算插值函数的各项系数，显然是不怎么方便的，但是牛顿插值法每次插值只和前n项的值有关，这样每次只要在原来的函数上添加新的项，就能够产生新的函数，但是在插值方法中，为了提高插值多项式的逼近程度，常常需要增加节点个数，这样插值多项式的次数逐次提高，但是高次插值的逼近效果往往不理想，由于计算量的增大可能会产生严重的误差积累，稳定性也得不到保证。