理解插值法（拉格朗日、牛顿插值法）

引言

我们首先理解下插值法主要用来做什么事：插值法就是利用已知的点建立合适的插值函数 $f\left(x\right)$f(x) ,未知点 $x_i$xi​ 由插值函数 $f\left(x\right)$f(x) 可以求出函数值 $f\left(x_i\right)$f(xi​)，用求得的 $(x_i,f(x_i\left)\right)$(xi​,f(xi​))近似代替未知点。

对于平面上相异（无两点在一条直线上）的 $n$n 个点，我们必定可以找到一个 $n-1$n−1 次多项式 $y=a_0+a_{1}x+a_2{x}^2+...a_{n-1}{x}^{n-1}$y=a0​+a1​x+a2​x2+...an−1​xn−1 ，使这个多项式函数经过这些点。拉格朗日插值法和牛顿插值法所要做的就是求得这个多项式函数。只是求得多项式的方式有些不同，下面详细介绍。

拉格朗日插值法

1. 已知 $n$n 个点的坐标 $(x_1,y_1),(x_2,y_2),(x_3,y_3)....(x_n,y_n)$(x1​,y1​),(x2​,y2​),(x3​,y3​)....(xn​,yn​)，求得一个 $n-1$n−1 次多项式 过这些点。
2. 假设 $n-1$n−1 次多项式为： $y=a_0+a_{1}x+a_2{x}^2+...a_{n-1}{x}^{n-1}$y=a0​+a1​x+a2​x2+...an−1​xn−1
3. 将n个点代入多项式得： $y_1=a_0+a_1{x}_1+a_2{x}_1^2+...a_{n-1}{x}_1^{n-1}$y1​=a0​+a1​x1​+a2​x12​+...an−1​x1n−1​ $y_2=a_0+a_1{x}_2+a_2{x}_2^2+...a_{n-1}{x}_2^{n-1}$y2​=a0​+a1​x2​+a2​x22​+...an−1​x2n−1​ $.....$..... $y_n=a_0+a_1{x}_n+a_2{x}_n^2+...a_{n-1}{x}_n^{n-1}$yn​=a0​+a1​xn​+a2​xn2​+...an−1​xnn−1​
4. 易解出拉格朗日插值多项式为： $L\left(x\right)=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)}$L(x)=y1​(x1​−x2​)(x1​−x3​)...(x1​−xn​)(x−x2​)(x−x3​)...(x−xn​)​+y2​(x2​−x1​)(x2​−x3​)...(x2​−xn​)(x−x1​)(x−x3​)...(x−xn​)​ $...+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})}$...+yn​(xn​−x1​)(xn​−x2​)...(xn​−xn−1​)(x−x1​)(x−x2​)...(x−xn−1​)​
5. 上式也可以写为：
   $L\left(x\right)=\sum _{i=1}^n{y}_i\prod _{j=1,j≠i}^n\frac{x-x_j}{x_i-x_j}$L(x)=i=1∑n​yi​j=1,j≠​i∏n​xi​−xj​x−xj​​

拉格朗日插值公式在理论分析理解上很容易理解，但是若插值节点发生改变时，插值公式随之就要重新计算生成，在实际计算中会占用大量的计算量。e.g. 现在有n个节点生成的插值公式，这里第 n+1 个节点也要加入进去，若使用拉格朗日插值法，之前的n个节点生成的插值公式则要完全调整废弃，重新生成含 n+1 个节点插值公式，这样就带来很大的计算量。正常的想法是，当一个节点要加入，我们只需在原来的插值公式上稍加修改就可以得到新的插值公式，牛顿法的出现正是克服这个问题，当插值节点发生增加，新的插值公式基于原来的公式很容易就得到。

牛顿插值法

要理解牛顿插值法首先理解一些概念：

差商：

设函数 $f\left(x\right)$f(x) ，已知其 $n$n个插值节点为 $(x_1,y_1),(x_2,y_2),(x_3,y_3)....(x_n,y_n)$(x1​,y1​),(x2​,y2​),(x3​,y3​)....(xn​,yn​)，我们定义：

• 一阶差商
  
• 二阶差商
  
• $n$n阶差商
  
  其中 $\bigwedge$⋀是省略的意思￣□￣｜｜。

由以上定义我们的到 差商表 如下：

基于差商的牛顿插值公式：

根据差商的定义，我们可以得到下面公式：

我们可以从后往前不断地代入消去得到：

这时候上式有两部分组成， （不含未知x的）牛顿插值逼近函数 $P\left(x\right)$P(x)、（含未知x的）误差函数 $R\left(x\right)$R(x)也称为余项 把 $R\left(x\right)$R(x) 去掉，就得到牛顿插值公式：

拉格朗日、牛顿插值法小结

motivation： 将缺失的函数值对应的点 $x$x 代入多项式得到缺失值的近似值 $f\left(x\right)$f(x)。

牛顿插值法和拉格朗日插值法两者都是多项式插值法。从本质上说，两者给出的结果是一样的（相同的次数，相同的系数多项式），只不过表示的形式不同。牛顿插值法与拉格朗日插值法相比具有承袭性和易于变动的特点。