计算数学
插值法
拉格朗日插值
通过平面上不同两点可以确定一条直线经过这两点，这就是拉格朗日线性插值问题，对于不在同一条直线的三个点得到的插值多项式为抛物线。 这里给出一般的插值公式，拉格朗日插值的基多项式为： \[{l_i}(x) = \prod\limits_{\begin{array}{*{20}{c}} {j = 0}\\ {j \ne i} \end{array}}^n {\frac{{x - {x_i}}}{{{x_i} - {x_j}}},i = 0,1,2, \cdots ,n} \] 对于没有接触过插值方法的读者，一个比较好的快速熟悉拉格朗日插值方法是把上面的多项式展开一下，看看如何计算基函数。 有了基函数以后就可以直接构造插值多项式，插值多项式为 \[{p_n} = \sum\limits_{i = 0}^n {f({x_i}){l_i}(x)} \] 虽然拉格朗日插值法较为基础，但因算法实现简单，且在一定条件下精度能得到保证，故而很多实际应用问题就采用该方法实现插值。下面给出拉格朗日插值的C++代码。
void lagrange(const VEC &x,const VEC &y,const VEC &xx,VEC &yy)
/*------------------------------------------------------
Versions and Changes :
v1.0----2015-8-11
lagrange 插值方法， 对多点一次性完成插值
C++语言中，允许 xx为 VEC(1) yy为 VEC(1)
--------------------------------------------------------
paramtegers :
* x-----------样本数据
* y-----------样本函数值
* xx----------要计算的点
* 返回值为-----插值结果，维数同xx
Ref . :
scientific computation in C# Tsinghua Univ. Press
------------------------------------------------------
Author : Song Yezhi
Copyrigt(C) : Shanghai Astronomical Observatory, CAS
(All rights reserved) 2015
-------------------------------------------------------*/
{
//获得样本维数
int N = x.size();
//获得被插值点的数据
int M = xx.size();
int p,i;
for ( p = 0; p < M; p++)
//对所有的要插值的点做循环
{
//至各分式之和为0
double sum = 0;
for (i = 0; i < N; i++)
{
double tmp = y(i);
for (int k = 0; k < N; k++)
{
if (k == i) continue;
//如果k与i相等，则退出当次循环
//但并不退出循环体
tmp = tmp * (xx(p) - x(k)) / (x(i) - x(k));
}
sum = sum + tmp; }
//结果赋值给要计算的点
yy(p) = sum;
}