Lagrange插值公式：
P
(
x
)
=
∑
k
=
0
n
L
n
,
k
(
x
)
f
(
x
k
)
P(x) = \sum_{k=0}^{n}L_{n,k}(x) f(x_{k})
P
(
x
)
=
∑
k
=
0
n
L
n
,
k
(
x
)
f
(
x
k
)
L
n
,
k
(
x
)
=
∏
i
=
0
,
i
≠
k
n
x
−
x
i
x
k
−
x
i
L_{n,k}(x) = \prod_{i=0,i\neq k}^{n}\frac{x-x_{i}}{x_{k}-x_{i}}
L
n
,
k
(
x
)
=
∏
i
=
0
,
i
̸
=
k
n
x
k
−
x
i
x
−
x
i
,k = 0,1,2,…,n
=
(
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
)
\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})}
=
(
x
k
−
x
0
)
(
x
k
−
x
1
)
.
.
.
(
x
k
−
x
k
−
1
)
(
x
k
−
x
k
+
1
)
.
.
.
(
x
k
−
x
n
)
(
x
−
x
0
)
(
x
−
x
1
)
.
.
.
(
x
−
x
k
−
1
)
(
x
−
x
k
+
1
)
.
.
.
(
x
−
x
n
)
Lagrange插值法的算法已知条件：
（1）
(
x
0
,
f
(
x
0
)
)
,
(
x
1
,
f
(
x
1
)
)
,
.
.
.
,
(
x
n
,
f
(
x
n
)
)
.
(x_{0},f(x_{0})),(x_{1},f(x_{1})),…,(x_{n},f(x_{n})).
(
x
0
,
f
(
x
0
)
)
,
(
x
1
,
f
(
x
1
)
)
,
.
.
.
,
(
x
n
,
f
(
x
n
)
)
.
（2）n
（3）所要进行内插的点
x
a
x_{a}
x
a
.
（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
*/