拉格朗日插值法1

拉格朗日插值法解题步骤：
拉格朗日插值法是一种数学方法，用于通过已知的离散数据点来构造一个多项式，这个多项式可以用来估计或逼近其他未知的数据点。

以下是拉格朗日插值法的解题步骤：
1.确定已知数据点：首先，你需要有一组已知的数据点。

这些数据点是你用来进行插值的已知信息。

2.构造拉格朗日多项式：对于每一个数据点 (xi, yi)，构造一个拉格朗日基函数。

3. 计算拉格朗日多项式的值：将每个已知数据点的横坐标xi 代入拉格朗日多项式L(x)，得到对应的yi 值。

这样，你就可以得到一个新的数据点集，这些点的坐标是(xi, L(xi))。

4. 使用插值多项式进行预测：对于你想要预测的x 值，代入拉格朗日多项式L(x)，即可得到对应的y 值。

这就是拉格朗日插值法的基本步骤。

需要注意的是，这种方法只适用于已知的数据点是离散的情况。

如果数据点是连续变化的，你可能需要使用其他方法，如样条插值等。

拉格朗日插值法就是构造一个多项式，使得恰好在每一个x处取到对应的y
首先，n+1个点(xi,yi)若xi不同，则可以确定唯一的最高幂次不超过n的多项式。

而如果题目直接或是间接给出了n+1个点，让我们求由这些点构成的多项式在某一个位置的取值，那么应用拉格朗日插值可以在O(n2 )的时间内解决这一问题
思路如下：
对于这个函数，要想在k=x[i]的时候取到y[i]，并且y[i]仅在这一情况对答案有影响，就要构造出一项K[i]y[i],使得x仅在取到x[i]时K为1,其他情况K[i]为0。

于是，仿照中国剩余定理的思路，有了如下构造方式：
(1)首先，x≠x[i]时K[i]为0，就要让x取到除去x[i]外的任何值都为0，于是有了“累乘‘k-x[j]’”的思路；
(2)其次，如果简单地将y[i]与累乘‘k-x[j]’结合，则x=x[i]时
该项为“累乘x[i]-x[j]",所以需要在每一项下面加上"除以x[i]-x[j]”
(3)最后将每一项加和，得到上式
拓展：x取值连续时的做法
有时候，问题仅要求求解x连续的情况。

那么如果仅有一个k值需要代入f(k)，就可以用下面的方法将复杂度变为
O(n)
对于分子，维护出k的前缀积和后缀积，即：
由于最终求得的值一定为正数，故需判断一下正负号。

如果N-i为奇数，则分母要取负数（因为fac(N-i)表示的是绝对值，N-i为偶数的时候恰好所有负号消掉了）。

常见的插值方法及其原理1. 拉格朗日插值法（Lagrange Interpolation）拉格朗日插值法是一种基于多项式的插值方法，通过n+1个已知点的函数值来构造一个n次多项式。

具体的计算公式如下：L(x) = Σ[yk * lk(x)], k=0 to n其中yk为已知点（xi, yi）的函数值，lk(x)为拉格朗日基函数，定义为：lk(x) = Π[(x - xj)/(xi - xj)], j=0 to n, j≠k拉格朗日插值法的原理是通过构造一个通过已知点的n次多项式，来代替未知函数的近似值。

利用拉格朗日基函数的性质，可以保证插值多项式通过已知点。

2. 牛顿插值法（Newton Interpolation）牛顿插值法是一种递推的插值方法，通过已知点的函数值和差商来逐步构造插值多项式。

差商的定义如下：f[x0]=y0f[x1]=(f[x1]-f[x0])/(x1-x0)f[x2]=(f[x2]-f[x1])/(x2-x1)...f[xn] = (f[xn] - f[xn-1]) / (xn - xn-1)利用差商的定义，可以得到牛顿插值多项式的表达式：N(x) = f[x0] + f[x0, x1](x-x0) + f[x0, x1, x2](x-x0)(x-x1) + ... + f[x0, x1, ..., xn](x-x0)(x-x1)...(x-xn)牛顿插值法的原理是通过递推计算差商来得到插值多项式。

通过使用差商来处理已知点的函数值差异，可以得到更高次的插值多项式。

3. 样条插值法（Spline Interpolation）样条插值法是一种基于分段低次插值函数的插值方法，常用的是三次样条插值。

样条插值法通过寻找一组分段函数，使得满足原函数的插值条件，并要求函数在每个插值点处的函数值、一阶导数和二阶导数连续。

这样可以保证插值函数在每个插值点处的平滑性。

三次样条插值法的原理是将整个插值区间划分为多个小区间，在每个小区间内使用三次多项式进行插值。

拉格朗⽇（Lagrange）插值算法拉格朗⽇插值（Lagrange interpolation）是⼀种多项式插值⽅法，指插值条件中不出现被插函数导数值，过n+1个样点，满⾜如下图的插值条件的多项式。

也叫做拉格朗⽇公式。

这⾥以拉格朗⽇3次插值为例，利⽤C++进⾏实现：1//利⽤lagrange插值公式2 #include<iostream>3using namespace std;45double Lx(int i,double x,double* Arr)6 {7double fenzi=1,fenmu=1;8for (int k=0;k<4;k++)9 {10if (k==i)11continue;12 fenzi*=x-Arr[k];13 fenmu*=Arr[i]-Arr[k];14 }15return fenzi/fenmu;16 }1718int main()19 {20double xArr[4]={};21double yArr[4]={};22//输⼊4个节点坐标23 cout<<"请依次输⼊4个节点的坐标:"<<endl;24for (int i=0;i<4;i++)25 cin>>xArr[i]>>yArr[i];2627//输⼊要求解的节点的横坐标28 cout<<"请输⼊要求解的节点的横坐标:";29double x;30 cin>>x;31double y=0;32for (int i=0;i<4;i++)33 y+=Lx(i,x,xArr)*yArr[i];34 printf("x=%lf时，y=%lf\n",x,y);3536//分界，下⾯为已知y求x37 cout<<"请输⼊要求解的节点的纵坐标:";38 cin>>y;39 x=0;40for (int i=0;i<4;i++)41 x+=Lx(i,y,yArr)*xArr[i];42 printf("y=%lf时，x=%lf\n",y,x);4344 system("pause");45return0;46 }作者：耑新新，发布于转载请注明出处，欢迎邮件交流：zhuanxinxin@。

拉格朗日（ Lagrange ）插值可对插值函数选择多种不一样的函数种类，因为代数多项式拥有简单和一些优秀的特征，比如，多项式是无量圆滑的，简单计算它的导数和积分，故常采纳代数多项式作为插值函数。

线性插值问题给定两个插值点此中，如何做经过这两点的一次插值函数过两点作一条直线，这条直线就是经过这两点的一次多项式插值函数，简称线性插值。

如下图。

图线性插值函数在初等数学中，可用两点式、点斜式或截距式结构经过两点的一条直线。

下边先用待定系数法结构插值直线。

设直线方程为，将分别代入直线方程得：当时，因，所以方程组有解，并且解是独一的。

这也表示，平面上解的存在性和唯一性，但要解一个方程组才能获得插值函数的系数，因工作量较大和不便向高阶推行，故这类结构方法往常不宜采纳。

当时，若用两点式表示这条直线，则有：（）这类形式称为拉格朗日插值多项式。

，，称为插值基函数，计算，的值，易见（）在拉格朗日插值多项式中可将看做两条直线，的叠加，并可看到两个插值点的作用和地位都是同等的。

拉格朗日插值多项式型式免去认识方程组的计算，易于向高次插值多项式型式推行。

线性插值偏差定理记为以为插值点的插值函数，。

这里，设一阶连续可导，在上存在，则对随意给定的，起码存在一点，使（）证明令，因是的根，所以可设对任何一个固定的点，引进协助函数：则由定义可得别在和和，即。

，这样起码有上应用洛尔定理，可知和，对3个零点，不失一般性，假设在每个区间起码存在一个零点，不如记为在上应用洛尔定理，获得，分在上起码有一个零点，。

此刻对求二次导数，此中的线性函数)，故有代入，得所以即二次插值问题给定三个插值点，, 此中互不相等，如何结构函数的二次的（抛物线）插值多项式平面上的三个点能确立一条次曲线，如下图。

图三个插值点的二次插值仿制线性插值的拉格朗日插值，即用插值基函数的方法结构插值多项式。

设每个基函数是一个二次函数，对来说，要求是它的零点，所以可设同理，也相对应的形式，得将代入，得同理将代入获得和的值，以及和的表达式。

多项式⼊门——拉格朗⽇插值多项式⼊门——拉格朗⽇插值插值⽤来求解这样⼀类问题：给定 \(n\) 点 \((x_i,y_i)\) 求过这些点的多项式。

1 简介设 \(f(x)\) 为这个多项式，我们有：\[f(x)\equiv f(a)\bmod (x-a)\tag{1} \]这是因为：\[f(x)-f(a)=(a_0-a_0)+a_1(x-a)+a_2(x^2-a^2)+... \]⽽后者显然有⼀个根为 \(a\) ，所以 \((1)\) 式得证。

通过把这 \(n\) 个点代⼊我们可以得到：\[\begin{cases} f(x)\equiv y_1\bmod x-x_1\\ ...\\ f(x)\equiv y_n\bmod x-x_n \end{cases} \]显然模数互质，所以我们考虑⽤中国剩余定理来解决这个事情。

令 \(M=\prod_{i=1}^n(x-x_i)\) ，\(m_i=\frac{M}{x-x_i}=\prod_{i\not= j}(x-x_j)\) 。

并且在模 \(x-x_i\) 的意义下，我们有：\[m_i^{-1}=\frac{1}{\prod\limits_{i\not=j}(x_i-x_j)} \]这是因为我们有：\[\prod_{i\not =j}(x-x_j)\equiv \prod_{i\not =j}(x-x_j-x+x_i)=\prod_{i\not =j}(x_i-x_j) \]所以上述结论成⽴。

所以我们有：\[f(x)\equiv \sum\limits_{i=1}^ny_im_im_i^{-1}\equiv \sum\limits_{i=1}^ny_i\prod\limits_{j\not=i}\frac{x-x_j}{x_i-x_j} \]这个东西可以在 \(n^2\) 的时间内求出。

2 例题直接模拟上⾯的过程即可。

#include<bits/stdc++.h>#define dd double#define ld long double#define ll long long#define uint unsigned int#define ull unsigned long long#define N 2010#define M numberusing namespace std;const int INF=0x3f3f3f3f;const ll mod=998244353;template<typename T> inline void read(T &x) {x=0; int f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;for(;isdigit(c);c=getchar()) x=x*10+c-'0';x*=f;}inline ll ksm(ll a,ll b,ll mod){ll res=1;while(b){if(b&1) (res*=a)%=mod;a=a*a%mod;b>>=1;}return res;}inline ll inv(ll a){return ksm(a,mod-2,mod);}ll n,k,x[N],y[N],ans;int main(){read(n);read(k);for(int i=1;i<=n;i++){read(x[i]);read(y[i]);}for(int i=1;i<=n;i++){ll fenzi=1,fenmu=1;for(int j=1;j<=n;j++){if(j==i) continue;fenmu*=(x[i]-x[j]);fenmu%=mod;fenzi*=(k-x[j]);fenzi%=mod;}ans+=y[i]*fenzi%mod*inv(fenmu)%mod;ans%=mod;}printf("%lld\n",(ans%mod+mod)%mod);return 0;}注意：需要把分母乘出来再求逆元，这样复杂度的瓶颈就不会是求逆元。