Numerical Methods Using MATLAB(4版)-04-Divided Difference

引自Numerical Methods Using MATLAB(4版)书籍，如有侵权请联系删除

前言

这一章主要讲多项式的逼近和插值。

学习过程

泰勒级数

绝对误差： $|error|=|E_N(x)| \leq \frac{MR^{N+1}}{(N+1)!}$
$M \leq max\{|f^{(N+1)}(z)|:x_0-R \leq z \leq x_0+R\}$

插值

假设 $[a,b]$ 里有 $N+1$ 个点经过函数 $y=f(x)$ ，则一定存在一个多项式 $P(x)$ 在 $[a,b]$ 逼近 $f(x)$ 。而当我们需要知道误差函数 $E(x)=f(x)-P(x)$ 时，我们就需要计算 $f^{(N+1)}(x)$ 。
如果这 $N$ 个点都高度精确，且 $x_0<x<x_N$ ，那么我们称 $P(x)$ 为内插值；如果 $x<x_0$ 或 $x_N<x$ ，那么我们称 $P(x)$ 为外插值。

拉格朗日多项式

多项式通式
假设多项式 $P_N(x)$ 为 $N$ 阶经过 $N+1$ 个点，则它有此形式
$P_N(x)=\sum_{k=0}^{N}y_kL_{N,k}(x),$
其中 $L_{N,k}(x)=\frac{(x-x_0)...(x-x_{k-1})(x-x_{k+1})...(x-x_N)}{(x_k-x_0)...(x_k-x_{k-1})(x_k-x_{k+1})...(x_k-x_N)}.$
该多项式是唯一的。
原理
$f(x)=P_N(x)+E_N(x)$
$E_N(x)=\frac{(x-x_0)(x-x_1)...(x-x_N)f^{(N+1)}(c)}{(N+1)!}$
其中 $c$ 在 $[a,b]$ 之中。
Proof.
假设 $N=1$ 来进行证明。
设 $g(t)=f(t)-P_1(t)-E_1(x)\frac{(t-x_0)(t-x_1)}{(x-x_0)(x-x_1)}$
$g(x)=f(x)-P_1(x)-E_1(x)=0,$
$g(x_0)=f(x_0)-P_1(x_0)-0=0,$
$g(x_1)=f(x_1)-P_1(x_1)-0=0.$
根据罗尔定理，有 $x_0<d_0<x$ 使得 $g'(d_0)=0$ ，有 $x<d_1<x_1$ 使得 $g'(d_1)=0$ ，有 $d_0<c<d_1$ 使得 $g^{(2)}(c)=0$ 。
因为 $g'(t)=f'(t)-P_1'(t)-E_1(x)\frac{(t-x_0)(t-x_1)}{(x-x_0)(x-x_1)},$
$g''(t)=f''(t)-0-E_1(x)\frac{2}{(x-x_0)(x-x_1)}.$
这里因为多项式阶数为1，所以二次求导后肯定为0。
所以，当 $t=c$ 时，有
$0=f''(c)-E_1(x)\frac{2}{(x-x_0)(x-x_1)}$
即 $E_1(x)=\frac{(x-x_0)(x-x_1)f^{(2)}(c)}{2!}$ 。
等距情况
当区间每个点间隔相同时，即 $x_k=x_0+hk$ ，则有 $|f^{(N+1)}(x)| \leq M_{N+1},x_0 \leq x \leq x_N$ 。
举例：
$|E_1(x)| \leq \frac{h^2M_2}{8},x∈[x_0,x_1],$
$|E_2(x)| \leq \frac{h^3M_3}{9\sqrt{3}},x∈[x_0,x_2],$
$|E_3(x)| \leq \frac{h^4M_4}{24},x∈[x_0,x_3],$
P215的例子4.8很清晰。

牛顿多项式

通式
$P_N(x)=P_{N-1}(x)+a_N(x-x_0)(x-x_1)(x-x_2)...(x-x_{N-1}).$
其中， $P_0(x)=a_0.$
原理
假设有 $N+1$ 个独立点处于 $[a,b]$ 之中，则有 $f(x_j)=P_N(x_j)$ ，其中 $a_k=f[x_0,x_1,...,x_k]$ 。
点独立存在时，存在唯一多项式经过这N+1个点。
对于 $f[]$ ，为了方便计算 $a_k$ ，我们有如下定义：
$f[x_k]=f(x_k),$
$f[x_{k-1},x_k]=\frac{f[x_k]-f[x_{k-1}]}{x_k-x_{k-1}},$
$f[x_{k-2},x_{k-1},x_k]=\frac{f[x_{k-1},x_k]-f[x_{k-2},x_{k-1}]}{x_k-x_{k-2}},$
$f[x_{k-3},x_{k-2},x_{k-1},x_k]=\frac{f[x_{k-2},x_{k-1},x_k]-f[x_{k-3},x_{k-2},x_{k-1}]}{x_k-x_{k-3}},$
$f[x_{k-j},x_{k-j+1},...,x_k]=\frac{f[x_{k-j+1},...,x_k]-f[x_{k-j},...,x_{k-1}]}{x_k-x_{k-j}}.$

切比雪夫多项式 Chebyshev Polynomials

拉格朗日和牛顿多项式的误差项计算都是一样的，我们可以知道误差是等于N+1阶导数在区间某个点的值的函数，因此我们使用切比雪夫多项式来探究选择哪些点从而减少这个函数的最大值。
切比雪夫多项式的性质
1、迭代式：设 $T_0(x)=1$ ， $T_1(x)=x$ ，则存在迭代式 $T_k(x)=2xT_{k-1}(x)-T_{k-2}(x),k=2,3,...$
2、系数：在 $T_N(x)$ 中， $x^N$ 的系数是 $2^{N-1},N \geq 1$ 。
3、对称性：当 $N=2M$ 时， $T_{2M}(x)$ 是偶函数；当 $N=2M+1$ 时， $T_{2M+1}(x)$ 是奇函数。
4、 $[-1,1]$ 区间的三角表示： $T_N(x)=cos(Narccos(x)),-1 \leq x \leq 1$ 。
5、 $[-1,1]$ 区间的零： $T_N(x)$ 在区间 $[-1,1]$ 上有 $N$ 个零点 $x_k$ ， $x_k=cos(\frac{(2k+1)\pi}{2N}),k=0,1,...,N-1$ 。
这些零点叫做切比雪夫结点。
6、极值： $|T_N(x)| \leq 1,-1 \leq x \leq 1$ 。

可知 $E_N(x)=Q(x)\frac{f^{(N+1)}(c)}{(N+1)!}$ ， $Q(x)=(x-x_0)(x-x_1)...(x-x_N)$ ，于是 $|E_N(x)| \leq |Q(x)|\frac{max_{-1 \leq x \leq 1}\{|f^{(N+1)}(x)|\}}{(N+1)!}$ 。切比雪夫发现选择 $N$ 个点，使得 $Q(x)=(1/2^N)T_{N+1}(x)$ 时， $|Q(x)|$ 有最小值。
略，P233-251后续有空自学。

词汇学习

interpolation 插值
rational 合理的
contraste 对比
numerator 分子
denominator 分母
concave 凹
tabulated 列表的
proportional 成比例的