龙格函数与 n 阶插值多项式之间的误差趋于∞

hbghlyj

考虑以下龙格函数：$$f(x)=\frac {1}{1+25x^2}$$
在 −1 与 1 之间按均匀间隔取样：$$x_i=-1+(i-1){\frac {2}{n}},\qquad i\in \left\{1,2,\dots ,n+1\right\}$$
龙格发现如果这样的等距点 $x_i$ 使用 $≤n$ 阶多项式 $P_n(x)$ 进行插值，那么在接近端点 −1 与 1 的地方插值结果就会出现震荡。

1. f[x_] := 1/(1 + 25 x^2);
2. points = Table[{x, f[x]}, {x, -1, 1, .1}];
3. Plot[Evaluate[InterpolatingPolynomial[points, x]], {x, -1, 1},
4. PlotRange -> All, Epilog -> {Red, Map[Point, points]}]

Copy the Code

hbghlyj

$f(x)$ 与 $n$ 阶插值多项式之间的误差为
$$ f(x)-P_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i}) $$
其中 $ \xi $ 在 (−1, 1) 之间。因此，
$$ \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq \max _{-1\leq x\leq 1}{\frac {\left|f^{(n+1)}(x)\right|}{(n+1)!}}\max _{-1\leq x\leq 1}\prod _{i=0}^{n}|x-x_{i}| $$
记 $ w_{n}(x) $ 为节点函数
$$ w_{n}(x)=(x-x_{0})(x-x_{1})\cdots (x-x_{n}) $$
并令 $ W_{n} $ 为 $ w_{n} $ 函数的最大值：
$$ W_{n}=\max _{-1\leq x\leq 1}|w_{n}(x)| $$
易证明，对于等距节点
$$ W_{n}\leq n!h^{n+1} $$
其中 $ h=2/n $ 是步长。

此外，假设 $ f $ 的 (n+1) 阶导数是有界的，即
$$ \max _{-1\leq x\leq 1}|f^{(n+1)}(x)|\leq M_{n+1} $$
因此，
$$ \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq M_{n+1}{\frac {h^{n+1}}{(n+1)}} $$
但是，当 n 增加时，Runge 函数的 (n+1) 阶导数的大小也会增加。

hbghlyj

此演示显示了插值和函数之差
要插值的函数$y=\frac1{1+25x^2}$以橙色显示，插值多项式以蓝色显示，数据点以红色显示。可见：

• 用等距插值节点$x_j=1-\frac{2 j}{N} \quad(0 \leq j \leq N)$则误差在 $\pm1$ 附近趋于∞
• 用Chebyshev插值节点$x_j=1-\frac{2 j}{N} \quad(0 \leq j \leq N)$则误差一致趋于0

Chebyshev节点在近似理论中非常重要，因为它们形成了一组特别好的多项式插值节点。给定区间 $ [-1,+1] $ 上的函数 $ f $ 和该区间内的 $ n $ 个点 $ x_{1},x_{2},\ldots ,x_{n} $，插值多项式是唯一的多项式 $ P_{n-1} $，其次数最多为 $ n-1 $，并且在每个点 $ x_{i} $ 处的值为 $ f(x_{i}) $。在 $ x $ 处的插值误差为
$$f(x)-P_{n-1}(x)={\frac {f^{(n)}(\xi )}{n!}}\prod _{i=1}^{n}(x-x_{i})$$
其中 $ \xi $（取决于 $x$）在 $[-1, 1]$ 内。因此，我们尝试最小化
$$\max _{x\in [-1,1]}{\biggl |}\prod _{i=1}^{n}(x-x_{i}){\biggr |}$$
这个乘积是一个次数为 $n$ 的首一多项式。可以证明，任何此类多项式的最大绝对值（sup范数）下界为 $2^{1-n}$。这个界限由缩放的切比雪夫多项式 $2^{1-n} T_n$ 达到，它们也是首一的。（回忆一下，对于 $x ∈ [-1, 1]$，$|T_n(x)| ≤ 1$。）因此，当插值节点 $x_i$ 是 $T_n$ 的根时，误差满足
$$\left|f(x)-P_{n-1}(x)\right|\leq {\frac {1}{2^{n-1}n!}}\max _{\xi \in [-1,1]}\left|f^{(n)}(\xi )\right|$$
对于任意区间 $[a, b]$，变量变换表明
$$\left|f(x)-P_{n-1}(x)\right|\leq {\frac {1}{2^{n-1}n!}}\left({\frac {b-a}{2}}\right)^{n}\max _{\xi \in [a,b]}\left|f^{(n)}(\xi )\right|$$

hbghlyj

例：设 $f(x)=\frac{1}{1+x^2}$ ，在 $[-5,5]$ 上利用 $T_{11}(x)$ 的零点作插值点，构造 10 次 Lagrange 插值多项式 $\bar{L}_{10}(x)$ 。与等距节点造出的 $L_{10}(x)$ 作比较。
解：在 $[-1,1]$ 上的 11 次 Chebyshev 多项式 $T_{11}(x)$ 的零点 $t_k$ 做变换后得 $[-5,5]$ 上的 Chebyshev 节点 \[ x_k=5 t_k=5 \cos \frac{2 k+1}{22} \pi, \quad k=0,1, \cdots, 10 \] MATLAB代码

1. %
2. % 利用Chebyshev多项式零点作为拉格朗日插值节点作拉格朗日插值
3. %
4. clear
5. clc
6. close all
7. % 定义Runge函数
8. RungeFun = @(x) 1./(1 + x.^2);
9. % 区间[-5,5]
10. a = -5.0;
11. b = 5.0;
12. % 分段数10和20
13. n = 10;
14. %
15. % 为画图所取的点（包含各小区间内再分10段的点）
16. xx = a:(b-a)/(10*n):b;
17. % 所有点个数
18. xxlen = length(xx);
19. % 所有点上的函数值
20. yy = RungeFun(xx);
21. plot(xx,yy,'-b')
22. c={'r','k'};
23. for index = 1:2
24. % 插值节点
25. if index == 1
26. % Chebyshev零点
27. x = (b-a)/2*cos((2*[0:n]+1)*pi/(2*(n+1))) + (a+b)/2;
28. else
29. % 均匀取点
30. x=linspace(-5,5,n+1);
31. end
32. % 节点函数值
33. y = RungeFun(x);
34. % 插值节点数
35. xlen = length(x);
37. % 计算Lagrange插值函数在所有点上的取值
38. temp = zeros(xlen,xxlen);
39. for i = 1: xlen
40. temp(i,:) = xx - x(i);
41. end
42. val = zeros(xlen,xxlen);
43. % w_n'(x_k)
44. WnDer = zeros(xlen,1);
45. for k = 1: xlen
46. t = x(k) - x;
47. tk = [t(1:k-1) t(k+1:end)];
48. % prod：连乘函数
49. WnDer(k) = prod(tk);
50. for j = 1 : xxlen
51. if k == 1
52. val(k,j) = prod(temp(2:end,j));
53. else
54. val(k,j) = prod(temp(1:k-1,j))*prod(temp(k+1:end,j));
55. end
56. end
57. end
58. % 基函数法算插值函数（求和）
59. Lag = val'*(y'./WnDer);
60. % 画图比较
61. hold on
62. h=plot(xx,Lag','--');
63. set(h,'Color',c{index})
64. xlabel('x')
65. ylabel('y')
66. end
67. legend('y = 1/(1+x^2)',strcat( 'Chebyshev： L', num2str(n) ),strcat( 'L', num2str(n) ),'Location','South')

Copy the Code