插值与多项式逼近

2018-12-11 本文已影响16人 HerdingCat

插值与多项式逼近

关于插值，是利用已知函数上的点及其函数值，对某一点求函数值。数学图像上，表现为两个函数形状的相似；数学公式上，表述为 $f(x) = P(x) + E(x)$ 的形式，其中 $P(x)$ 用于逼近原函数 $f(x)$ ， $E(x)$ 表示为原函数与逼近函数之间的误差。
以下给出多个 $P(x)$ 的表示方式，同样 $E(x)$ 伴随给出，并确定误差界。

泰勒多项式逼近

关于泰勒多项式逼近，所用的是高数中的泰勒公式，对于函数 $f(x) \in C^{N+1} [a, b]$ ，希望求解某一点 $x_0$ 附近的函数值 $f(x)$ ，则可以用泰勒多项式逼近。
$f(x) = P(x) + E(x), \\ P(x) = \sum^N _{k=0} \frac{f^{k}(x_0)}{k!}(x-x_0)^k, \\ E(x) = \frac{f^{(N+1)}(c)}{(N+1)!}(x-x_0)^{N+1}, c \in [x, x_0] \ or \ c \in [x_0, x]$
有了误差 $E(x)$ ，需要知道最大误差是多少。
由于 $f(x) \in C^{N+1} [a, b]$ ，
则 $f^{N+1}(x)$ 在 $[a, b]$ 内存在最大值 $M$ ，即 $| f^{N+1}(c)| \le M$ ；
此时给定 $x_0$ 处的允许范围 $|x - x_0| \le R$ ，
则可确定误差 $E(x)$ 的范围， $E(x) \le \frac{M R^2}{(N+1)!}$
可以发现 $E(x)$ 随着 $M$ 和 $R$ 的变化而变化，当 $x$ 的取值离 $x_0$ 越来越远时，泰勒多项式逼近的程度就会越来越差。为了解决这个问题，提出了以下的拉格朗日多项式逼近。

拉格朗日多项式逼近

拉格朗日多项式逼近，是构造精巧的多项式得到的。
$f(x)=P_N(x) + E_N(x), \\ P_N(x) = \sum^N_{k = 0} y_k \cdot L_{k, N}(x),\ L_{k, N} (x) = \frac{\Pi^{N}_{j = 0, j \neq k}(x - x_j)}{\Pi^{N}_{j = 0, j \neq k} (x_k - x_j)}, \\ E_N(x) = \frac{\Pi ^N_{k = 0}(x - x_k)f^{N+1}(c)} {(N+1)!}$

$P_N(x)$ 的性质
由于 $L_{k,N}(x_j) = \left\{ \begin{array}{2} 1, \ j = k \\ 0, \ j \neq k \end{array}\right.$
那么 $P_N(x_j)= \left\{ \begin{array}{2} f(x_j), \ j = k \\ 0, \ j \neq k \end{array}\right.$
关于 $E_N(x)$
$E_N(x)$ 的推导过程需要构造函数并运用罗尔定理进行证明。

证明：构造 $g(t) = f(t) - P_N(t)-E_N(x)\frac{\Pi^N_{k = 0}(t-x_k)} {\Pi^N_{k = 0}x-x_k}$
对 $g(x)$ 取 $x, x_0, x_1, \cdots, x_n$ 得到
$g(x) = f(x) - P_N(x)-E_N(x) = 0, \\ g(x_0) = f(x_0) - P_N(x_0) -E_N(x_0) \times 0 = f(x_0) - f(x_0) = 0, \\ \cdots, \\ g(x_n) = f(x_n) - P_N(x_n) = 0$
又有 $g(t) \in C^{N+1}[a, b]$ ，再由罗尔定理得到，
存在 $d_k \ (k = 0, \cdots, n - 1)$ 分别属于由 $x, x_0, x_1, \cdots, x_n$ 划分的 $n$ 个区间内，
$g'(d_0) = g'(d_1) = \cdots = g'(d_{n-1}) = 0$
使用 $N+1$ 次罗尔定理可得，
$g^{(N+1)}(c) = 0, \\ g^{(N+1)}(t) = f^{(N+1)}(t) - E(x)\frac{1}{\Pi^N_{k = 0}(x-x_k)} (N+1)!$
则 $E(x) = \frac{\Pi ^N_{k = 0}(x - x_k)f^{N+1}(c)} {(N+1)!}$

考虑 $E(x)$ 的误差界

设 $f(x) \in C^{N+1}[a, b]$ ，则存在最大值 $M_{N+1}$ ，
有 $|f^{(N+1)}(c)| \le M_{N+1}$
设 $[a, b]$ 内等距的取值， $x_k = x_0 + kh$ ， $h$ 为两点间距离，
令 $t = x - x_0$ ，则 $x-x_k = t-kh, E_N(x) = \frac{\Pi ^N_{k = 0}(t - kh)f^{N+1}(c)} {(N+1)!}$
令 $\Phi(t) = \Pi ^N_{k = 0}(t - kh)$ ，可通过令 $\Phi ' (t) = 0$ 求得极值点并得到最大值。
通过上述两步便可求具体 $E_N(x)$ 的误差界

牛顿多项式逼近

拉格朗日多项式逼近时对于不同阶数的多项式需要重新给出 $L_{k,N}(x)$ ，显然有点麻烦。
这时牛顿多项式逼近应运而生。
该方法同样是通过构造多项式逼近函数
$f(x) = p_N(x) + E_N(x), \\ P_N(x) = P_{N-1}(x) + a_N\Pi^{N-1}_{k =0}(x-x_k) = \sum^N_{j = 1} a_j\Pi^{j - 1}_{k = 0}(x-x_k) + a_0,\\ E_N(x) = \frac{\Pi ^N_{k = 0}(x - x_k)f^{N+1}(c)} {(N+1)!}$

确定 $P_N(x)$ 中的系数

构造牛顿多项式所用的点是 $\big(x_k, f(x_k) \big), k =1, \cdots, N$ ，

其中 $P_1(x) = a_0 + a_1(x - x_0)$

因为 $P_1(x_0) = f(x_0), P_x(x_1) = f(x_1)$ ，则可以得到

$a_0 = f(x_0), a_1 = \frac{f(x_1) - a_0}{x_1 - x_0} = \frac{f(x_1) - f(x_0)}{x_1 - x_0}$

又有 $P_2(x_2) = f(x_2)$ ，则

$a_2 = \frac{f(x_2)-a_0-a_1(x_2 - x_0)}{(x_2-x_0)(x_2-x_1)}$ ，将所得到的 $a_0, a_1$ 代入表达式得到

$a_2=\Big(\frac{f(x_2)-f(x_0)}{x_2-x_0} - \frac{f(x_1)-f(x_0)}{x_1-x_0} \Big) \frac{1}{x_2 - x_1} = \frac{f(x_2)x_1-f(x_0)x_1-f(x_2)x_0-f(x_1)x_2+f(x_1)x_0+f(x_0)x_2}{(x_2-x_0)(x_2-x_1)(x_1-x_0)} \\ =\frac{\big(f(x_2)x_1+f(x_1)x_0-f(x_2)x_0-f(x_1)x_1\big)-\big(f(x_1)x_2+f(x_0)x_1-f(x_0)x_2-f(x_1)x_1\big)}{(x_2-x_0)(x_2-x_1)(x_1-x_0)}\\ = \Big(\frac{f(x_2)-f(x_1)}{x_2-x_1} - \frac{f(x_1)-f(x_0)}{x_1-x_0} \Big) \frac{1}{x_2 - x_0}$

可以发现 $a_k$ 的形式与导数的定义比较相似，人们称之为差商。有了差商，我们便可以通过计算差商来计算 $P_N(x)$ 中系数。差商的计算可以通过差商表计算。

$x_k$ $f(x_k)$ 一阶差商二阶差商

$x_0$ $f(x_0)$

$x_1$ $f(x_1)$ $f[x_0, x_1] = \frac{f(x_1)-f(x_0)}{x_1-x_0}$

$x_2$ $f(x_2$ ) $f[x_1, x_2]=\frac{f(x_2)-f(x_1)}{x_2-x_1}$ $f[x_0, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2-x_0}$

对角线上的值就是所要求系数 $a_k = f[x_0, \cdots, x_k] = \frac{f[x_0, \cdots, x_{k-1}] - f[x_1, \cdots, x_k]}{x_k-x_0}$ 。
关于 $E_N(x)$ 的论述与拉格朗日一致

$x_k$	$f(x_k)$	一阶差商	二阶差商
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$	$f[x_0, x_1] = \frac{f(x_1)-f(x_0)}{x_1-x_0}$
$x_2$	$f(x_2$ )	$f[x_1, x_2]=\frac{f(x_2)-f(x_1)}{x_2-x_1}$	$f[x_0, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2-x_0}$

切比雪夫多项式逼近

考虑拉格朗日逼近和牛顿多项式逼近误差能否控制在一个较小的范围。

构造的切比雪夫多项式就能将其中的 $Q(x) = (x-x_0)\cdots (x- x_N)$ 控制在 $\frac{1}{2^N}$ 。

如果要得到这个结论，需要了解切比雪夫多项式的相关性质。

递归关系： $T_0(x) = 1, T_1(x) = x, T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x), k=2, 3, \cdots$
首项系数：当 $N \ge 1$ 时， $T_N(x)$ 中的 $X^N$ 的系数为 $2^{N-1}$ 。
对称性：当 $N = 2M$ 时， $T_{2m}(x)$ 为偶函数；当 $N = 2M + 1$ 时， $T_{2m+1}(x)$ 为奇函数。
$[-1, 1]$ 上的三角函数表示 $T_N(x) = \cos(N\arccos(x)), -1\le x\le 1$ 。

第4条性质的证明：

利用三角恒等式 $\cos(k\theta) = \cos(k\theta -2\theta+2\theta ) = \cos(2\theta)\cos((k-2)\theta) - \sin(2\theta)\sin((k-2)\theta)$

其中的 $\cos(2\theta) = 2\cos^2(\theta) - 1, \sin(2\theta) = 2 \sin(\theta)\cos(\theta)$ ，并代入上式

$\cos(k\theta) = 2\cos^2(\theta)\cos((k-2)\theta) - \cos((k-2)\theta)-2\sin(\theta)\cos(\theta)\sin((k-2)\theta)\\ = 2\cos(\theta)\big(\cos(\theta)\cos((k-2)\theta) - \sin(\theta)\sin((k-2)\theta) - \cos((k-2)\theta)\big)\\ = 2\cos(\theta)\big(\cos((k-1)\theta) - \cos((k-2)\theta) \big)$

令 $\theta = \arccos(x)$ ，则上式可以写为

$\cos(k\arccos(x)) = 2x (\cos((k-1)\arccos(x)))-\cos((k-2)\arccos(x))$ ，满足切比雪夫多项式的递归关系

则 $T_N(x) = \cos(N\arccos(x))$ 。
$[-1, 1]$ 上有 $N$ 个不同的零点, $x_k =\cos\Big(\frac{(2k+1)\pi}{2N} \Big), k = 0, \cdots, N-1$ 。
$|T_N(x)|\le 1, -1 \le x\le 1$ 。

有了以上的性质， $Q(x)$ 与 $T_{N+1}(x)$ 同阶，只是差一个系数 $2^N$ （根据第2条性质）。此时 $T(x) = \frac{T_{N+1}(x)}{2^N}, \displaystyle \max_{-1\le x \le 1}\{ |T(x)|\} \le \displaystyle \max_{-1\le x \le 1}\{ |Q(x)|\}$ ，

其中的 $T_{N+1}(x) \le 1$ （根据第6条性质），则 $T_(x) \le \frac{1}{2^N}$ ，因此 $\frac{1}{2^N} \le\displaystyle \max_{-1\le x\le 1}\{|Q(x)|\}$ 。这也就说明了，选取的点是切比雪夫多项式的零点，那么拉格朗日逼近和牛顿多项式逼近误差项 $E(x)$ 就会减少。

拉格朗日逼近时，选取切比雪夫多项式的零点，也可以达到减少误差的效果；利用切比雪夫多项式的正交性可以直接构造切比雪夫多项式逼近。

切比雪夫逼近： $f(x)$ 在区间 $[-1, 1]$ 上次数小于等于 $N$ 的切比雪夫逼近多项式 $P_N(x)$ 可写为 $\{T_j(x)\}$ ，以及

$f(x) = P_N(x) + E_N(x), \\ P_N(x) = \sum^N_{j = 0}c_jT_j(x)$

其中的 $c_j$ 就是通过切比雪夫多项式的正交性求得的。

切比雪夫多项式的正交性：取 $x_k = \cos\Big(\pi \frac{2k + 1}{2N + 2} \Big), k = 0, \cdots, N$ ，即多项式零点（第5条性质）

$\left\{ \begin{array}{3} \sum^N_{k = 0}T_i(x_k)T_j(x_k) = 0, \ i \ne j \\ \sum^N_{k = 0} T_i(x_k)T_j(x_k) = \frac{N+1}{2}, \ i = j \ne 0 \\ \sum^N_{k = 0} T_0(x_k)T_0(x_k) = N + 1 \end{array}\right.$