拉格朗日插值

存在性和唯一性的證明以後再補。。。。

拉格朗日插值

拉格朗日插值，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;
}