拉格朗日插值

2018-06-17 21:24:26来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

拉格朗日插值

拉格朗日插值,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}$

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

代码

 

#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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:CPP--正码,反码,补码~附整数溢出的探讨

下一篇:洛谷P2044 [NOI2012]随机数生成器