拉格朗日插值

1.1插值多项式

用多项式作为研究插值的工具，称为代数插值。其基本问题是：已知函数 $f(x)$ 在区间 $[a, b]$ 上 $n+1$ 个不同点 $x_{0}, x_{1}, dots, x_{n}$ 处的函数值 $y_{i}=feft(x_{i}ight)(i=0,1, dots, n)$ ，求一个至多 $n$ 次多项式：
$arphi_{n}(x)=a_{0}+a_{1} x+dots+a_{n} x^{n}（1）$
使其在给定点处与 $f(x)$ 同值，即满足插值条件：
$arphi_{n}eft(x_{i}ight)=feft(x_{i}ight)=y_{i} uad(i=0,1, dots, n)（2）$

$arphi_{n}(x)$ 称为插值多项式， $x_{i}(i=0,1, dots, n)$ 称为插值节点，简称节点， $[a, b]$ 称为插值区间。从几何上看， $n$ 次多项式插值就是过 $n+1$ 个点，作一条多项式曲线 $y=arphi_{n}(x)$ 近似曲线 $y=f(x)$ 。

$n$ 次多项式（1）有 $n+1$ 个待定系数，由插值条件（2）恰好给出 $n+1$ 个方程：
$eftegin{array}{l}{a_{0}+a_{1} x_{0}+a_{2} x_{0}^{2}+dots+a_{n} x_{0}^{n}=y_{0}} {a_{0}+a_{1} x_{1}+a_{2} x_{1}^{2}+dots+a_{n} x_{1}^{n}=y_{1}} {dots dots dots dots dots dots dots dots dots dots dots} {a_{0}+a_{1} x_{n}+a_{2} x_{n}^{2}+dots+a_{n} x_{n}^{n}=y_{n}}nd{array}ight.（3）$

记此方程组的系数矩阵为 $A$ ，则：
$peratorname{det}(A)=eft|egin{array}{ccccc}{1} & {x_{0}} & {x_{0}^{2}} & {dots} & {x_{0}^{n}} {1} & {x_{1}} & {x_{1}^{2}} & {dots} & {x_{1}^{n}} {} & {dots} & {dots} & {dots} & {dots} {1} & {x_{n}} & {x_{n}^{2}} & {dots} & {x_{n}^{n}}nd{array}ight|$

称为范德蒙特行列式。当 $x_{0}, x_{1}, dots, x_{n}$ 互不相同时，此行列式值不为零。因此方程组（3）有唯一解。这表明，只要 $n+1$ 个节点互不相同，满足插值要求（2）的
插值多项式（1）是唯一的。

插值多项式与被插函数之间的差：
$R_{n}(x)=f(x)-arphi_{n}(x)$

称为截断误差，又称为插值余项。当 $f(x)$ 充分光滑时，
$R_{n}(x)=f(x)-L_{n}(x)=rac{f^{(n+1)}(i)}{(n+1) !} mega_{n+1}(x), i n(a, b)$
其中，
$mega_{n+1}(x)=rod_{j=0}^{n}eft(x-x_{j}ight)$

1.2.拉格朗日插值多项式

实际上比较方便的作法不是解方程（3）求待定系数，而是先构造一组基函数：
$egin{aligned} l_{i}(x) &=rac{eft(x-x_{0}ight) dotseft(x-x_{i-1}ight)eft(x-x_{i+1}ight) dotseft(x-x_{n}ight)}{eft(x_{i}-x_{0}ight) dotseft(x_{i}-x_{i-1}ight)eft(x_{i}-x_{i+1}ight) dotseft(x_{i}-x_{n}ight)} &=rod_{j=0 top j eq i}^{n} rac{x-x_{j}}{x_{i}-x_{j}}, uad(i=0,1, dots, n) nd{aligned}$
$l_{i}(x)$ 是 $n$ 次多项式，满足：
$l_{i}eft(x_{j}ight)=eftegin{array}{ll}{0} & {j eq i} {1} & {j=i}nd{array}ight.$
令：
$L_{n}(x)=um_{i=0}^{n} y_{i} l_{i}(x)=um_{i=0}^{n} y_{i}eft(rod_{j=0 top j eq i}^{n} rac{x-x_{j}}{x_{i}-x_{j}}ight)（4）$

上式称为 $n$ 次 $Lagrange$ 插值多项式，由方程（3）解的唯一性， $n+1$ 个节点的 $n$ 次 $Lagrange$ 插值多项式存在唯一。

伪代码如下

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++实现

#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;
}

# 1.1插值多项式

# 1.2.拉格朗日插值多项式

1.1插值多项式

1.2.拉格朗日插值多项式