為甚麼節點位置會影響誤差界
對 [ − 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 。
快速檢查
(為甚麼極小極大證明要先假設存在嚴格更好的多項式?)
解答 · 答案 嚴格改進使差值在每個極值點處的符號非零且交替,從而介值定理在相鄰極值點之間給出不同零點。