拉格朗日插值法（伪代码 c/c++ python 实现）

插值法又称“内插法”，是利用函数f (x)在某区间中已知的若干点的函数值，作出适当的特定函数，在区间的其他点上用这特定函数的值作为函数f (x)的近似值，这种方法称为插值法。如果这特定函数是多项式，就称它为插值多项式。

拉格朗日插值是n次多项式插值，其成功地用构造插值基函数的 方法解决了求n次多项式插值函数问题。

其基本思想是将待求的n次多项式插值函数p(x）改写成另一种表示方式，再利用插值条件⑴确定其中的待定函数，从而求出插值多项式。

套用相关公式，即可实现相关的程序。

算法的流程图：

伪代码如下：

LagrangeInterpolationPolynomia(ele, n, x[], y[]) 
//ele是需要预测的元素值，n是提供的值的数量，x[]与y[]分别存储着已知的x值与所对应的y值
	sum <- 0
	k <- 0
	while k < n do
		t <- 1
		j <- 0
		while j < n do
			if j != k
				t <- ((ele - x[j])/(x[k] - x[j]))*t
				sum <- t * y[k] + sum
			end
			j <- j + 1
		end 
		k <- k + 1
	end 
	return sum

c/c++的代码：

#include <iostream>
using namespace std;
float LagrangeInterpolationPolynomia(float x,int n,float a[],float b[]);

int main ()
{
	float x,y,t,a[100],b[100];
	int i,j,k,n;
	cout << "输入n的值"<<endl;
	cin >> n;
	cout << "输入x的值"<<endl;
	cin >> x;
	y = 0;
	for (i=0;i<n;i++)
	{
		cout<< "输入x"<<i<<"的数据：";
		cin >> a[i];
		cout<< "输入y"<<i<<"的数据：";
		cin >> b[i];
	}
	cout << "y="<<LagrangeInterpolationPolynomia(x,n,a,b)<<endl;
	return 0;
}

float LagrangeInterpolationPolynomia(float x,int n,float a[],float b[])
{
	int k;
	float t,y=0;
	int j;
	for (k = 0;k < n;k++)
	{
		t = 1;
		for (j = 0;j < n;j++)
		{
			if (j != k)
			t = ((x - a[j])/(a[k]-a[j]))*t;
		}
		y = t * b[k]+y;
		cout << y << endl;
	}
	return y;
}

python的代码：

def LagrangeInterpolationPolynomia(ele, n, x, y):
    sum_num = 0
    for k in range(0, n):
        t = 1
        for j in range(0, n):
            if j != k:
                t = ((ele - x[j])/(x[k] - x[j]))*t
                sum_num = t * y[k] + sum_num
    return sum_num

x = [1, 3]
y = [1, 2]

print LagrangeInterpolationPolynomia(1.5, len(x), x, y)