Lagrange插值法

Lagrange插值公式：

$P(x) = \sum_{k=0}^{n}L_{n,k}(x) f(x_{k})$P(x)=∑k=0n​Ln,k​(x)f(xk​)

$L_{n,k}(x) = \prod_{i=0,i\neq k}^{n}\frac{x-x_{i}}{x_{k}-x_{i}}$Ln,k​(x)=∏i=0,i̸​=kn​xk​−xi​x−xi​​ ,k = 0,1,2,…,n
$\qquad = \frac{(x-x_{0})(x-x_{1})...(x-x_{k-1})(x-x_{k+1})...(x-x_{n})}{(x_{k}-x_{0})(x_{k}-x_{1})...(x_{k}-x_{k-1})(x_{k}-x_{k+1})...(x_{k}-x_{n})}$=(xk​−x0​)(xk​−x1​)...(xk​−xk−1​)(xk​−xk+1​)...(xk​−xn​)(x−x0​)(x−x1​)...(x−xk−1​)(x−xk+1​)...(x−xn​)​

Lagrange插值法的算法已知条件：

（1）$(x_{0},f(x_{0})),(x_{1},f(x_{1})),...,(x_{n},f(x_{n})).$(x0​,f(x0​)),(x1​,f(x1​)),...,(xn​,f(xn​)).
（2）n
（3）所要进行内插的点$x_{a}$xa​.
（4）Lagrange插值法的公式。

C语言简单实现如下：

#include<cstdio>
#include<iostream>

using namespace std;

double x[30];//x值
double f[30];//对应的y值
double xa;//待求的y值所给出的x值
double l;//l(k)的值
double ans;//结果

int main()
{
	int n;
	while(cin>>n&&n)
	{
		cin>>xa;
		for(int i=0;i<=n;i++)
			cin>>x[i]>>f[i];
		ans=0.0;
		for(int k=0;k<=n;k++)
		{
			l=1.0;
			for(int i=0;i<=n;i++)//计算l(k)
			{
				if(k!=i)
					l=l*(xa-x[i])/(x[k]-x[i]);
			}
			ans=ans+l*f[k];
		}
		printf("The value of P(%.4lf)=%.4lf\n\n",xa,ans);
	}
	return 0;
}
/*
三组测试用例：
3
1.5
1.0  0.0
2.0  0.693
3.0  1.099
4.0  1.386


3
1.5
1.0  0.000
1.2  0.182
1.4  0.336
2.0  0.693


9
1.5
1.0  0.000
1.2  0.182
1.7  0.531
2.0  0.693
2.2  0.788
2.7  0.993
3.0  1.099
3.2  1.163
3.7  1.308
4.0  1.386

*/