本次学习我们主要是从数学角度推导一下拉格朗日插值法和牛顿插值法，使读者能更深入理解该数据处理方法。

一、拉格朗日插值法

1）根据数学知识我们知道，对于平面上已知的n个点，可以找到一个n-1次多项式$y=a_0+a_1x+a_2x^2+…+a_{n-1}x^{n-1}$，使此多项式曲线过这n个点。
求已知的过n个点的n-1次多项式：
$$y=a_0+a_1x+a_2x^2+…+a_{n-1}x^{n-1}$$
将n个点的坐标$(x_1,y_1),(x_2,y_2)…(x_n,y_n)$代入多项式函数，得：
$$y_1=a_0+a_1x_1+a_2{x_1}^2+…+a_{n-1}{x_1}^{n-1}$$
$$y_2=a_0+a_1x_2+a_2{x_2}^2+…+a_{n-1}{x_2}^{n-1}$$
$$…$$
$$y_n=a_0+a_1x_n+a_2{x_n}^2+…+a_{n-1}{x_n}^{n-1}$$
2）于是，我们构造一个函数，这个函数要满足可以取到任意$(x_i,y_i)$这个点
$$L(x)=y_1{\frac{(x-x_2)(x-x_3)…(x-x_n)}{(x_1-x_2)(x_1-x_3)…(x_1-x_n)}}
+y_2{\frac{(x-x_1)(x-x_3)…(x-x_n)}{(x_2-x_1)(x_2-x_3)…(x_2-x_n)}}+…
+y_n{\frac{(x-x_1)(x-x_2)…(x-x_{n-1})}{(x_n-x_1)(x_n-x_2)…(x_n-x_{n-1})}}
=\sum_{i=0}^n{y_i{\prod_{j=0,j{\neq}i}^n{\frac{x-x_j}{x_i-x_j}}}}$$
令$l(i)={\prod_{j=0,j{\neq}i}^n{\frac{x-x_j}{x_i-x_j}}}$
由上式可以发现，$l(i)$只有在$x_i$处取到值1，在$x_j(j{\neq}i)$处都为0，那么$L(x)$这个多项式就可以取到点$(x_i,y_i)$且不影响其他n个点，用无数多个点就可以确定一个线，成为一个连续得函数，就可以求出上式求出某个给定$x$得近似值$L(x)$

此时提出一个问题：当插值点增减，多项式里的每一项都要变，这很不方便！！
所以提出：牛顿插值法

二、牛顿插值法

1）差商的定义：
函数$f(x)$在两个互异点$x_i,x_j$处的一阶差商定义为：
$$f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j} (i{\neq}j,x_i{\neq}x_j)$$
2阶差商：
$$f[x_i,x_j,x_k]=\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k} (i{\neq}k)$$
k+1阶差商
$$f[x_0,…,x_(k+1)]=\frac{f[x_0,x_1,…,x_k]-f[x_1,…,x_k,x_(k+1)]}{x_0-x_(k+1)}$$
2）求已知n个点对$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$的所有阶差商公式，推导以上$f(x)$:

N(x)是逼近函数，R(x)是误差函数
3）牛顿插值法的优点：
当增加一个插值节点只需在最后加一项，前面各项均不变。
也是多项式，取$(x_i,y_i)$不影响其他点，两者结果一样，只是表现形式不同。