数值计算之 插值法（4）切比雪夫零点插值

前言

上篇插值法讨论了多项式插值的解，以及龙格现象。本篇将介绍一种在抽取节点时有效降低龙格现象的方法——切比雪夫零点插值。

插值点选取

插值多项式阶数较高时，在取值空间均匀取点，容易出现龙格现象。 即区间边缘的插值结果与原函数差异很大，而区间中央的插值结果相对较好。这表明，高阶多项式插值对区间中央的节点拟合好，而对两端节点拟合效果差。

自然而然会想到，在两端多采样一些节点，在中间少采样一些节点，就能更好的对函数插值了。

第一类切比雪夫多项式

n阶切比雪夫多项式可以表示为： T n ( x ) = cos ⁡ ( n arccos ⁡ x ) , ∣ x ∣ ≤ 1 T_n(x)=\cos(n\arccos x),|x|\le1 Tn​(x)=cos(narccosx),∣x∣≤1 切比雪夫多项式可以写成递推形式： T n + 1 ( x ) = 2 x T n ( x ) − T n − 1 ( x ) T_{n+1}(x)=2xT_n(x)-T_{n-1}(x) Tn+1​(x)=2xTn​(x)−Tn−1​(x) 前四阶切比雪夫多项式如下： T 0 ( x ) = 1 T 1 ( x ) = x T 2 ( x ) = 2 x 2 − 1 T 3 ( x ) = 4 x 3 − 3 x T 4 ( x ) = 8 x 4 − 8 x 2 + 1 T_0(x)=1 \\ T_1(x)=x \\ T_2(x)=2x^2-1 \\ T_3(x)=4x^3-3x \\ T_4(x)=8x^4-8x^2+1 \\ T0​(x)=1T1​(x)=xT2​(x)=2x2−1T3​(x)=4x3−3xT4​(x)=8x4−8x2+1 切比雪夫多项式有几个性质：

性质一： n阶切比雪夫多项式在 x ∈ [ − 1 , 1 ] x\in[-1,1] x∈[−1,1]上有n个零点： x k = cos ⁡ ( 2 k − 1 2 n π ) , k = 1 , 2 , … , n x_k=\cos (\frac{2k-1}{2n}\pi),k=1,2,\dots,n xk​=cos(2n2k−1​π),k=1,2,…,n 这个性质对于插值而言非常重要。如果取11阶切比雪夫多项式插值，就是用这个性质计算切比雪夫零点。并且求出来的零点，在取值区间内刚好两端多一些，中间少一些。

定理一 x ∈ [ − 1 , 1 ] x\in[-1,1] x∈[−1,1]时，在所有n阶首一多项式中，切比雪夫多项式是使最大值最小的多项式： ∀ P n ( x ) , 1 2 n − 1 ≤ m a x ∣ T n ( x ) ∣ ≤ m a x ∣ P n ( x ) ∣ \forall P_n(x), \frac{1}{2^{n-1}}\le max|T_n(x)|\le max|P_n(x)| ∀Pn​(x),2n−11​≤max∣Tn​(x)∣≤max∣Pn​(x)∣

拉格朗日插值多项式的余项

如果原函数为 f ( x ) f(x) f(x)，n阶拉格朗日多项式插值的结果为 P n ( x ) P_n(x) Pn​(x)，则余项可表示为： R n ( x ) = f n + 1 ( ϵ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) ϵ ∈ [ x m i n , x m a x ] m a x ( ∏ i = 0 n ( x − x i ) ) ≥ m a x ( T n ( x ) ) R_n(x)=\frac{f^{n+1}(\epsilon)}{(n+1)!}\prod_{i=0}^{n}(x-x_i) \\ \epsilon\in[x_{min},x_{max}] \\ \quad \\ max(\prod_{i=0}^{n}(x-x_i)) \ge max(T_n(x)) Rn​(x)=(n+1)!fn+1(ϵ)​i=0∏n​(x−xi​)ϵ∈[xmin​,xmax​]max(i=0∏n​(x−xi​))≥max(Tn​(x)) 因此，使得插值余项 R n ( x ) R_n(x) Rn​(x)最小，就是使 ∏ i = 0 n ( x − x i ) \prod_{i=0}^{n}(x-x_i) ∏i=0n​(x−xi​)化为切比雪夫多项式，即令 x 0 , x 1 , … , x n x_0,x_1,\dots,x_n x0​,x1​,…,xn​为切比雪夫零点。

切比雪夫零点插值

由上面的公式和定理我们知道，在拉格朗日多项式插值时，取切比雪夫零点作为节点，可以降低余项，避免龙格现象。然而上面的推到中，节点的取值区间 x ∈ [ − 1 , 1 ] x\in[-1,1] x∈[−1,1]。在实际应用中，需要将区间扩展： 假 设 x k 是 x ∈ [ − 1 , 1 ] 时 n 阶 切 比 雪 夫 的 零 点 现 在 要 将 它 转 换 到 区 间 x ∈ [ a , b ] 中 x ^ k = a + b 2 + b − a 2 x k 假设x_k是x\in [-1,1]时n阶切比雪夫的零点\\ 现在要将它转换到区间x\in [a, b]中 \\ \quad \\ \hat x_k=\frac {a+b}{2}+\frac {b-a}{2}x_k 假设xk​是x∈[−1,1]时n阶切比雪夫的零点现在要将它转换到区间x∈[a,b]中x^k​=2a+b​+2b−a​xk​ 于是，切比雪夫零点插值就扩展到了插值区间 x ∈ [ a , b ] x\in [a,b] x∈[a,b]。

后记

本篇记录了使用切比雪夫多项式零点来降低多项式插值造成的龙格现象。下篇将学习记录分段插值。