拉格朗日插法的应用(ACM)
首先来了解拉格朗日插值法。
可理解为：
个点为(xi,yi)，这个多项式可以看做n个下面的函数的和。其中，第i个多项式函数fi除了在fi(xi)=yi外，其他的位置取值都为0，即fi(xj)=0(i≠j)。
f(x)=a(x−x1)(x−x2)
显然在f(x)=0
时，必有x1,x2
两解。推而广之，一个有n个顶点的n次多项式可以写为，
f(x)=a(x−x1)(x−x2)……(x−xn)
那么插值用的第i个多项式可写作为 ：
又有fi(xi)=yi，带入xi，可得：
即可得：
即插值公式为：