前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >拉格朗日插值

拉格朗日插值

作者头像
attack
发布2018-04-11 13:51:36
1.4K0
发布2018-04-11 13:51:36
举报
文章被收录于专栏:数据结构与算法

存在性和唯一性的证明以后再补。。。。

拉格朗日插值

拉格朗日插值,emmmm,名字挺高端的:joy:

它有什么应用呢?

我们在FFT中讲到过

设n-1次多项式为

y=\sum_{i=0}^{n-1}a_i x^i

有一个显然的结论:如果给定n个互不相同的点(x,y),则该n-1次多项式被唯一确定

那么如果给定了这互不相同的n个点,

利用拉格朗日插值,可以在O(n)的时间内计算出某项的值,还可以在O(n^2)的时间复杂度内计算出给定的x所对应的y

那么如何计算呢?

公式

不啰嗦了,直接给公式吧,至于这个公式怎么来的以后再补充

若对于n-1次多项式,给定了n个互不相同的(x,y)

那么对于给定的x,第i项的值为

l(i)=y_i\prod_{j=1,j\neq i}^{n} \dfrac{x-x_j}{x_i-x_j}

所对应的y为

y=\sum_{i=1}^{n} l(i)

=\sum_{i=1}^{n}y_i\prod_{j=1,j\neq i}^{n}\dfrac{x-x_j}{x_i-x_j}

利用这个公式,就可以进行计算啦

代码

代码语言:javascript
复制
#include<cstdio>
int x[1001],y[1001];
int N,ans=0;
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&x[i],&y[i]);
    int X;//待求的x 
    scanf("%d",&X);
    for(int i=1;i<=N;i++)
    {
        int tmp=y[i];
        for(int j=1;j<=N;j++)
        {
            if(i==j) continue;
            tmp=tmp*(X-x[j])/(x[i]-x[j]);
        }
        ans+=tmp;
    }
    printf("%d",ans);
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-01-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 拉格朗日插值
  • 公式
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档