插值法的基本思想

基本思想： 给出函数$y=f(x)$的一组观测点(函数表)

$x$$x_0$$x_1$$\dots$$x_n$$y$$y_0$$y_1$$\dots$$y_n$

去寻找一个解析形式的函数$\varphi (x)$，它在各个插值节点处的函数值正好等于表中的函数值，而在其它点上的函数值近似于$f(x)$。如果选取的函数是次数不超过$n$的多项式，则称插值为代数插值。

插值法主要有：

n次多项式插值；分段线性插值Hermit插值三次样条函数插值B样条函数插值

每种插值方法在MATLAB中都有相应的函数（包括自己编写的），下面先讨论n次多项式插值。

n次Lagrange插值

1. 基本思想

给出函数$f(x)$的$n+1$组观测点$(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$，令$\phi (x)$是次数不超过n的多项式 $$\phi (x)=a_0+a_{1}x+a_2{x}^2+\dots +a_n{x}^n$$ 并且有$\phi (x_i)=y_i,i=0,1,\dots ,n$。将各个节点代入多项式得到系数$(a_0,\dots ,a_n)$满足的线性方程组 $$\{\begin{array}{c}{a}_0+a_1{x}_0+\dots +a_n{x}_0^n=y_0\\ a_0+a_1{x}_1+\dots +a_n{x}_1^n=y_1\\ \dots \\ a_0+a_1{x}_n+\dots +a_n{x}_n^n=y_n\end{array}$$ 易知此线性方程组的系数矩阵为Vandermonde矩阵 $$\mathbf{A}=\left(\begin{array}{cccc}1& x_0& \dots & x_0^n\\ 1& x_1& \dots & x_1^n\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_n& \dots & x_n^n\end{array}\right)$$ 它的行列式$|\mathbf{A}|={\prod }_{j\ne i}(x_j-x_i)$。当$|\mathbf{A}|\ne 0$时可以解出唯一解。

这种方法的缺点是计算量太大。

2. n次插值基函数

为了利于编程，可以将$\phi (x)$表示成$n+1$个插值基函数 $$(l_0(x),\dots ,l_n(x))$$ 的线性组合，插值基函数的性质是：$l_i(x)$在$x_i$上的取值为1，在其他点上的取值为0 $$l_i(x_j)=\{\begin{array}{cc}1& ,i=j\\ 0& ,i\ne j\end{array}$$ 那么$\phi (x)$被它们线性表出的表达式为 $$\phi (x)=\sum _{k=0}^n{y}_k{l}_k(x)$$ 很容易得出每个插值基函数的表达式为 $$l_i(x)=\frac{(x-x_0)\dots (x-x_{i-1})(x-x_{i+1})\dots (x-x_n)}{(x_i-x_0)\dots (x_i-x_{i-1})(x_i-x_{i+1})\dots (x_i-x_n)}$$

3. 程序实现

%Lagrange插值函数(保存为lagrange.m) function y = lagrange(x0, y0, x) %x0，y0是插值节点 %x是待计算其它点，y为这些点上的函数值 n=length(x0); m=length(x); for i = 1:m z = x(i); y(i) = baseLagrange(x0, y0, z, n); end %嵌套插值基函数 function s = baseLagrange(x0, y0, z, n) s = 0.0; for k = 1:n p = 1.0; for j = 1:n if j ~= k p = p*(z - x0(j))/(x0(k) - x0(j)); end end s = p*y0(k) + s; end end end

n次Newton插值

1. 均差

函数$f(x)$在两个节点$x_i,x_j$处的一阶均差为 $$f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}$$ 相应地，在三个节点$x_i,x_j,x_k$处的二阶均差为 $$f[x_i,x_j,x_k]=\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k}$$ 在n个节点$x_1,x_2,\dots ,x_n$处的n阶均差为 $$f[x_0,x_1,\dots ,x_n]=\frac{f[x_0,\dots ,x_{n-1}]-f[x_1,\dots ,x_n]}{x_0-x_n}$$

2. 均差表

将函数$f(x)$直到n阶均差列在一个表中，就得到了均差表 $$\left(\begin{array}{cccccc}x& y& f[x_i,x_j]& f[x_i,x_j,x_k]& \dots & f[x_0,x_1,\dots ,x_n]\\ x_0& y_0& & & & \\ x_1& y_1& f[x_0,x_1]& & & \\ x_2& y_2& f[x_1,x_2]& f[x_0,x_1,x_2]& & \\ x_3& y_3& f[x_2,x_3]& f[x_1,x_2,x_3]& \dots & \\ ⋮& ⋮& ⋮& ⋮& ⋮& \\ x_n& y_n& f[x_{n-1},x_n]& f[x_{n-1},x_{n-1},x_n]& \dots & f[x_0,x_1,\dots ,x_n]\end{array}\right)$$

3. Newton插值函数的表达式

已知$f(x)$在节点$x_0,x_1,\dots ,x_n$处的函数值为$\{f(x_k){\}}_{k=0}^n$，先构造均差表，然后取对角线作为系数构造n次牛顿插值公式 $$\begin{gathered} {\phi }_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1) \\ +f[x_0,x_1,\dots ,x_n](x-x_0)(x-x_1)\dots (x-x_{n-1}) \end{gathered}$$

牛顿插值公式计算比较方便，只需要计算均差就可以马上得到函数的表达式。

差分Newton插值公式

1. 向前差分

已知函数$f(x)$在等距节点$x_k=x_0+kh(k=0,1,\dots ,n)$的函数值为$f_k=f(x_0+kh)$，其中$h$为步长。那么记$f(x)$在节点$x_0$处的一阶向前差分为 $$\Delta f_k=f_{k+1}-f_k,k=0,1,\dots ,n-1$$ n阶向前差分 $${\Delta }^n{f}_k={\Delta }^{n-1}{f}_{k+1}-{\Delta }^{n-1}{f}_k,n=2,3\dots$$

用函数值表示二阶向前差分 $$\begin{gathered} {\Delta }^2{f}_k=\Delta f_{k+1}-\Delta f_k \\ =f_{k+2}-2f_{k+1}+fk \end{gathered}$$

2. 差分与均差

$$f[x_0,\dots ,x_n]=\frac{1}{n!h^n}{\Delta }^n{f}_0$$ ${\Delta }^n{f}_0$是差分表中处在对角线的元素。

3. 等距节点的差分插值表达式

令$x=x_0+th$,$x_k=x_0+kh,k=1,2,\dots ,n$将均差表改为差分表，那么就得到了等距节点的Newton插值公式 $${\phi }_n(x)=f_0+t\Delta f_0+\frac{t(t-1)}{2!}{\Delta }^2{f}_0+\dots +\frac{t(t-1)\dots (t-n+1)}{n!}{\Delta }^n{f}_0$$

证明: 利用差分与均差的关系，可以的得到 $$\begin{gathered} f[x_0,\dots ,x_n](x-x_0)\dots (x-x_{n-1})=\frac{1}{n!h^n}{\Delta }^n{f}_0(x-x_0)\dots (x-x_{n-1}) \\ =\frac{1}{n!h^n}{\Delta }^n{f}_0{h}^{n}t(t-1)\dots t(t-n+1)=\frac{t(t-1)\dots (t-n+1)}{n!}{\Delta }^n{f}_0 \end{gathered}$$

n次插值多项式的余项

定理

设${\phi }_n(x)$是过点$x_0,x_1,\dots ,x_n$的n次插值多项式，$f(x)\in {\mathbf{C}}_{[a,b]}^n$，$f^{(n+1)}(x)$在$[a,b]$上存在，其中$[a,b]$是包含节点的任意区间，则任意给定$x\in [a,b]$，总存在一点$\xi \in (a,b)$，使得余项 $$R_n(x)=f(x)-{\phi }_n(x)={\omega }_n(x)f[x_0,\dots ,x_n]=\frac{f^{(n+1)}(\xi )}{(n+1)!}{\omega }_n(x)$$ 其中，${\omega }_n(x)=(x-x_0)\dots (x-x_{n-1})$

结尾

Lagrange插值和Newton插值是同一类型的插值Newton插值使用均差表，计算比Lagrange插值方便实际应用中并不常用这两种插值。