为什么节点位置会影响误差界
对 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 内互不相同的节点 x 0 , … , x n x_0,\ldots,x_n x 0 , … , x n ,若 f ∈ C n + 1 ( [ − 1 , 1 ] ) f\in C^{n+1}([-1,1]) f ∈ C n + 1 ([ − 1 , 1 ]) ,插值余项为
f ( x ) − p n ( x ) = f ( n + 1 ) ( ξ x ) ( n + 1 ) ! ∏ j = 0 n ( x − x j ) , f(x)-p_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{j=0}^n(x-x_j), f ( x ) − p n ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ x ) j = 0 ∏ n ( x − x j ) ,
当 x x x 不是节点时,ξ x \xi_x ξ x 位于 x , x 0 , … , x n x,x_0,\ldots,x_n x , x 0 , … , x n 的最小值与最大值之间;在节点处误差为零。若已知 ∥ f ( n + 1 ) ∥ ∞ ≤ M \|f^{(n+1)}\|_\infty\le M ∥ f ( n + 1 ) ∥ ∞ ≤ M ,节点乘积的大小就控制一致误差界。
m m m 次多项式若首项系数为 1 1 1 ,称为首一 多项式。节点乘积 ∏ j = 0 n ( x − x j ) \prod\limits_{j=0}^n(x-x_j) j = 0 ∏ n ( x − x j ) 是 n + 1 n+1 n + 1 次首一多项式。对 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上的函数 g g g ,记 ∥ g ∥ ∞ = max x ∈ [ − 1 , 1 ] ∣ g ( x ) ∣ \|g\|_\infty=\max\limits_{x\in[-1,1]}|g(x)| ∥ g ∥ ∞ = x ∈ [ − 1 , 1 ] max ∣ g ( x ) ∣ 。
哪个 n + 1 n+1 n + 1 次首一多项式在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上的一致范数最小?
Chebyshev 多项式
对 m ≥ 0 m\ge0 m ≥ 0 ,用以下递推式定义多项式:
T 0 ( x ) = 1 , T 1 ( x ) = x , T m + 1 ( x ) = 2 x T m ( x ) − T m − 1 ( x ) . T_0(x)=1,\quad T_1(x)=x,\quad T_{m+1}(x)=2xT_m(x)-T_{m-1}(x). T 0 ( x ) = 1 , T 1 ( x ) = x , T m + 1 ( x ) = 2 x T m ( x ) − T m − 1 ( x ) .
对所有 m ≥ 0 m\ge0 m ≥ 0 ,T m ( cos θ ) = cos ( m θ ) T_m(\cos\theta)=\cos(m\theta) T m ( cos θ ) = cos ( m θ ) 。当 m ≥ 1 m\ge1 m ≥ 1 时,T m T_m T m 的次数为 m m m ,首项系数为 2 m − 1 2^{m-1} 2 m − 1 。在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上 ∣ T m ( x ) ∣ ≤ 1 |T_m(x)|\le1 ∣ T m ( x ) ∣ ≤ 1 ,并且在以下 m + 1 m+1 m + 1 个点,
z k = cos ( k π / m ) , k = 0 , … , m , z_k=\cos(k\pi/m),\qquad k=0,\ldots,m, z k = cos ( k π / m ) , k = 0 , … , m , 它交替取值 T m ( z k ) = ( − 1 ) k T_m(z_k)=(-1)^k T m ( z k ) = ( − 1 ) k 。
m = 0 , 1 m=0,1 m = 0 , 1 的情形是 cos 0 = 1 \cos0=1 cos 0 = 1 与 cos θ = x \cos\theta=x cos θ = x 。恒等式 cos ( ( m + 1 ) θ ) + cos ( ( m − 1 ) θ ) = 2 cos θ cos ( m θ ) \cos((m+1)\theta)+\cos((m-1)\theta)=2\cos\theta\cos(m\theta) cos (( m + 1 ) θ ) + cos (( m − 1 ) θ ) = 2 cos θ cos ( m θ ) 表明,在 x = cos θ x=\cos\theta x = cos θ 处 cos ( m θ ) \cos(m\theta) cos ( m θ ) 满足同一递推式,由归纳即得 T m ( cos θ ) = cos ( m θ ) T_m(\cos\theta)=\cos(m\theta) T m ( cos θ ) = cos ( m θ ) 。递推式把首项乘以 2 x 2x 2 x ,所以次数增加一,首项系数加倍,从 m = 1 m=1 m = 1 时的 1 1 1 得到 2 m − 1 2^{m-1} 2 m − 1 。[ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 的每一点都可写成 cos θ \cos\theta cos θ ,所以 ∣ T m ( x ) ∣ = ∣ cos ( m θ ) ∣ ≤ 1 |T_m(x)|=|\cos(m\theta)|\le1 ∣ T m ( x ) ∣ = ∣ cos ( m θ ) ∣ ≤ 1 ,并且 T m ( z k ) = cos ( k π ) = ( − 1 ) k T_m(z_k)=\cos(k\pi)=(-1)^k T m ( z k ) = cos ( k π ) = ( − 1 ) k 。
因此首一多项式
q ∗ ( x ) = 2 1 − m T m ( x ) q_*(x)=2^{1-m}T_m(x) q ∗ ( x ) = 2 1 − m T m ( x )
在该区间上的最大绝对值为 2 1 − m 2^{1-m} 2 1 − m 。
T m T_m T m 的一致范数是 1 1 1 ,但它的首项系数是 2 m − 1 2^{m-1} 2 m − 1 ,不是 1 1 1 。节点乘积是首一的,所以它等于 2 1 − m T m 2^{1-m}T_m 2 1 − m T m ,范数为 2 1 − m 2^{1-m} 2 1 − m 。若在误差界中用 ∥ T m ∥ ∞ = 1 \|T_m\|_\infty=1 ∥ T m ∥ ∞ = 1 ,所得的界会被高估 2 m − 1 2^{m-1} 2 m − 1 倍。
乘积的极小极大定理
定理 7.8.4
(首一 Chebyshev 多项式的极小极大性质)
对每个 m ≥ 1 m\ge1 m ≥ 1 的实首一 m m m 次多项式 q q q ,
max x ∈ [ − 1 , 1 ] ∣ q ( x ) ∣ ≥ 2 1 − m . \max_{x\in[-1,1]}|q(x)|\ge2^{1-m}. x ∈ [ − 1 , 1 ] max ∣ q ( x ) ∣ ≥ 2 1 − m . 多项式 q ∗ = 2 1 − m T m q_*=2^{1-m}T_m q ∗ = 2 1 − m T m 达到该界。
假设相反,∥ q ∥ ∞ < 2 1 − m \|q\|_\infty<2^{1-m} ∥ q ∥ ∞ < 2 1 − m 。在每个 z k z_k z k 处,由于 ∣ q ( z k ) ∣ |q(z_k)| ∣ q ( z k ) ∣ 严格小于 ∣ q ∗ ( z k ) ∣ |q_*(z_k)| ∣ q ∗ ( z k ) ∣ ,差值 q ∗ ( z k ) − q ( z k ) q_*(z_k)-q(z_k) q ∗ ( z k ) − q ( z k ) 的符号为 ( − 1 ) k (-1)^k ( − 1 ) k 。相邻的 z k , z k + 1 z_k,z_{k+1} z k , z k + 1 互不相同且次序递减,所以介值定理在每对相邻点之间的 m m m 个互不相交的开区间内各给出一个 q ∗ − q q_*-q q ∗ − q 的零点。但两个多项式都是首一的,最高次项相消后差的次数至多为 m − 1 m-1 m − 1 。除非差恒为零,否则它不可能有 m m m 个不同零点;恒为零又与严格不等式矛盾。因此没有首一 q q q 具有更小的一致范数,而 q ∗ q_* q ∗ 达到了该界。
证明透视
交替的极值迫使零点过多 证明无需猜测任意竞争多项式在哪里达到最大值。我们只在 m + 1 m+1 m + 1 个已知极值点检验它。若它严格更好,差值的符号就会交替,从而至少有 m m m 个零点;但最高次项相消后次数至多只有 m − 1 m-1 m − 1 。首一这个假设恰好用在这次相消上;若没有它,常数倍 ε q ∗ \varepsilon q_* ε q ∗ 就会是任意小的竞争者。
从极小极大多项式得到节点
定理 7.8.5
(Chebyshev 根节点处的误差界)
令 m = n + 1 m=n+1 m = n + 1 。T m T_m T m 的零点为
x j = cos ( ( 2 j + 1 ) π 2 m ) , j = 0 , … , m − 1 , x_j=\cos\!\left(\frac{(2j+1)\pi}{2m}\right),\qquad j=0,\ldots,m-1, x j = cos ( 2 m ( 2 j + 1 ) π ) , j = 0 , … , m − 1 , 它们互不相同且位于 ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) ,在这些 Chebyshev 根节点 上插值得到
∥ f − p n ∥ ∞ ≤ M 2 n ( n + 1 ) ! . \|f-p_n\|_\infty\le\frac{M}{2^n(n+1)!}. ∥ f − p n ∥ ∞ ≤ 2 n ( n + 1 )! M . 在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 内所有 n + 1 n+1 n + 1 个互异节点的选择中,这组节点使节点乘积的一致范数最小。
角度 ( 2 j + 1 ) π / ( 2 m ) (2j+1)\pi/(2m) ( 2 j + 1 ) π / ( 2 m ) 互不相同且位于 ( 0 , π ) (0,\pi) ( 0 , π ) ,其 m m m 倍角的余弦均为零。因此上述点是 m m m 次多项式的 m m m 个互异根,均位于 ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) 。节点乘积是具有这些零点的首一多项式,所以等于 2 1 − m T m ( x ) 2^{1-m}T_m(x) 2 1 − m T m ( x ) ,范数为 2 1 − m = 2 − n 2^{1-m}=2^{-n} 2 1 − m = 2 − n ;再由余项公式得上述界。任何其他节点选择给出 m m m 次首一乘积,由极小极大定理,其范数至少为 2 1 − m 2^{1-m} 2 1 − m 。
在使用同一 M M M 时,这组节点也使这个特定误差界最小。其他常用的 Chebyshev 网格包括端点并有不同用途;它们并非这里推导的根节点网格。
当 n = 1 n=1 n = 1 、m = 2 m=2 m = 2 时,两节点为 ± 1 / 2 \pm1/\sqrt2 ± 1/ 2 ,乘积是 x 2 − 1 / 2 x^2-1/2 x 2 − 1/2 ,在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上的最大绝对值为 1 / 2 1/2 1/2 。对 f ( x ) = x 2 f(x)=x^2 f ( x ) = x 2 ,两节点处的线性插值多项式是常数 1 / 2 1/2 1/2 ,故实际最大误差也为 1 / 2 1/2 1/2 。导数界 M = 2 M=2 M = 2 给出 M / ( 2 1 2 ! ) = 1 / 2 M/(2^1 2!)=1/2 M / ( 2 1 2 !) = 1/2 ,恰好相等。
例题 7.8.7
(三个 Chebyshev 根节点对比等距节点)
当 n = 2 n=2 n = 2 、m = 3 m=3 m = 3 时,T 3 = 4 x 3 − 3 x T_3=4x^3-3x T 3 = 4 x 3 − 3 x 的根为 ± 3 / 2 \pm\sqrt3/2 ± 3 /2 和 0 0 0 ,节点乘积为 x 3 − 3 4 x = 1 4 T 3 x^3-\tfrac34x=\tfrac14T_3 x 3 − 4 3 x = 4 1 T 3 ,范数为 1 / 4 1/4 1/4 。对 f ( x ) = e x f(x)=e^x f ( x ) = e x 可取 M = e M=e M = e ,所以界为 e / ( 2 2 ⋅ 3 ! ) = e / 24 ≈ 0.113 e/(2^2\cdot3!)=e/24\approx0.113 e / ( 2 2 ⋅ 3 !) = e /24 ≈ 0.113 。若用等距节点 − 1 , 0 , 1 -1,0,1 − 1 , 0 , 1 ,乘积为 x 3 − x x^3-x x 3 − x ,它在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上的最大值是 2 / ( 3 3 ) ≈ 0.385 2/(3\sqrt3)\approx0.385 2/ ( 3 3 ) ≈ 0.385 ,在 x = ± 1 / 3 x=\pm1/\sqrt3 x = ± 1/ 3 处取得。对应的界为 ( e / 6 ) ⋅ 0.385 ≈ 0.174 (e/6)\cdot0.385\approx0.174 ( e /6 ) ⋅ 0.385 ≈ 0.174 ,大了约 0.385 / 0.25 ≈ 1.54 0.385/0.25\approx1.54 0.385/0.25 ≈ 1.54 倍。
当 n = 0 n=0 n = 0 、m = 1 m=1 m = 1 时只有一个节点,即 T 1 = x T_1=x T 1 = x 的零点 x 0 = 0 x_0=0 x 0 = 0 。节点乘积为 x x x ,范数为 1 = 2 1 − 1 1=2^{1-1} 1 = 2 1 − 1 ,插值多项式是常数 f ( 0 ) f(0) f ( 0 ) 。误差界写作 ∥ f − f ( 0 ) ∥ ∞ ≤ M \|f-f(0)\|_\infty\le M ∥ f − f ( 0 ) ∥ ∞ ≤ M ,其中 M = ∥ f ′ ∥ ∞ M=\|f'\|_\infty M = ∥ f ′ ∥ ∞ ;对 f ( x ) = x f(x)=x f ( x ) = x ,它在 x = ± 1 x=\pm1 x = ± 1 处达到。
反例模式
极小极大误差界不是对每个函数实际误差的断言 命题:对每个 f f f ,Chebyshev 根节点都给出最小的实际插值误差。如果 f f f 本身是次数至多为 n n n 的多项式,任意 n + 1 n+1 n + 1 个互异节点都给出精确插值。Chebyshev 根节点使最坏情况下的节点乘积和上面的导数型上界最小;对特定函数,其他节点可能给出更小的实际误差。例如 n = 1 n=1 n = 1 、f ( x ) = x 3 f(x)=x^3 f ( x ) = x 3 时,根节点 ± 1 / 2 \pm1/\sqrt2 ± 1/ 2 给出插值多项式 x / 2 x/2 x /2 ,误差为 x 3 − x / 2 = x ( x 2 − 1 / 2 ) x^3-x/2=x(x^2-1/2) x 3 − x /2 = x ( x 2 − 1/2 ) ,它在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上的最大值为 1 / 2 1/2 1/2 ,在 x = ± 1 x=\pm1 x = ± 1 取得。节点 ± 1 \pm1 ± 1 给出插值多项式 x x x ,误差为 x 3 − x x^3-x x 3 − x ,最大值为 2 / ( 3 3 ) ≈ 0.385 < 1 / 2 2/(3\sqrt3)\approx0.385<1/2 2/ ( 3 3 ) ≈ 0.385 < 1/2 。
这个界未解决什么
次数改变时,导数常数 M M M 也依赖 n n n 。仅凭公式不能证明每个无穷次可微函数的插值在 n → ∞ n\to\infty n → ∞ 时都收敛。它也没有控制数据误差或浮点舍入如何被放大;那是另外的条件性和稳定性问题。实际中可以用重心公式计算插值多项式,同时依据数据选择合适节点和次数。
练习与解答
快速检查
(计算 T 2 T_2 T 2 ,验证 2 − 1 T 2 2^{-1}T_2 2 − 1 T 2 是首一多项式。)
解答 · 答案 T 2 ( x ) = 2 x 2 − 1 T_2(x)=2x^2-1 T 2 ( x ) = 2 x 2 − 1 ,所以 2 − 1 T 2 = x 2 − 1 / 2 2^{-1}T_2=x^2-1/2 2 − 1 T 2 = x 2 − 1/2 。
快速检查
(当 m = 3 m=3 m = 3 时,列出 T 3 T_3 T 3 的根,并给出 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上首一三次多项式可能达到的最小最大范数。)
解答 · 答案 根为 3 / 2 , 0 , − 3 / 2 \sqrt3/2,0,-\sqrt3/2 3 /2 , 0 , − 3 /2 ,最小范数为 2 1 − 3 = 1 / 4 2^{1-3}=1/4 2 1 − 3 = 1/4 。
快速检查
(若 ∥ f ′ ′ ∥ ∞ ≤ 6 \|f''\|_\infty\le6 ∥ f ′′ ∥ ∞ ≤ 6 ,n = 1 n=1 n = 1 的 Chebyshev 根节点界是多少?)
解答 · 答案 界为 6 / ( 2 ⋅ 2 ) = 3 / 2 6/(2\cdot2)=3/2 6/ ( 2 ⋅ 2 ) = 3/2 。
快速检查
(为什么极小极大证明要先假设存在严格更好的多项式?)
解答 · 答案 严格改进使差值在每个极值点处的符号非零且交替,从而介值定理在相邻极值点之间给出不同零点。