動機
中心差分 ( f ( x + h ) − f ( x − h ) ) / ( 2 h ) \bigl(f(x+h)-f(x-h)\bigr)/(2h) ( f ( x + h ) − f ( x − h ) ) / ( 2 h ) 需要 x x x 兩側各一個數值,但這類數值往往無法取得。在一次實驗的首個記錄時刻,之前並沒有量度。在模型定義範圍的邊緣,另一側的公式根本沒有意義。已記錄的樣本亦常常間距不等,原因可能是讀數並非定時取得,或部分讀數被剔除。在這些情況下,我們必須由位於 x x x 一側、不必等距的點上的數值來估計 f ′ ( x ) f'(x) f ′ ( x ) 。
上一篇筆記的原則依然適用:先用多項式插值樣本,再對插值多項式求導。改變的是計算上的細節。權重不再對稱,其中一些頗大,而誤差常數取決於節點的位置。我們先在一般情況下推導權重,再證明一個把截斷誤差與數據誤差影響分開的界,然後完整處理模板 x x x 、x + h x+h x + h 、x + 3 h x+3h x + 3 h 。
設定與假設
固定整數 n ≥ 1 n\ge1 n ≥ 1 及 n + 1 n+1 n + 1 個互不相同 的實數 t 0 , … , t n t_0,\ldots,t_n t 0 , … , t n ,稱為無量綱節點偏移。固定目標點 x ∈ R x\in\mathbb R x ∈ R 及尺度 h > 0 h>0 h > 0 ;樣本點為 x + h t j x+ht_j x + h t j 。若所有 t j ≥ 0 t_j\ge0 t j ≥ 0 (或所有 t j ≤ 0 t_j\le0 t j ≤ 0 ),則稱該模板為單側 模板。通常取 t 0 = 0 t_0=0 t 0 = 0 ,使 x x x 本身亦被取樣。「不等距」僅表示 t j t_j t j 不必構成等差數列;互不相同是唯一的結構要求。
設 I I I 為包含 x x x 及所有樣本點的最小閉區間:
I = [ x + h min ( 0 , t 0 , … , t n ) , x + h max ( 0 , t 0 , … , t n ) ] . I=\bigl[x+h\min(0,t_0,\ldots,t_n),\;x+h\max(0,t_0,\ldots,t_n)\bigr]. I = [ x + h min ( 0 , t 0 , … , t n ) , x + h max ( 0 , t 0 , … , t n ) ] .
對單側模板而言,x x x 是 I I I 的端點。此時 f ′ ( x ) f'(x) f ′ ( x ) 是單側導數,按前一篇筆記的約定,理解為由內部連續延拓而得。
定義 13.1.2
(導數公式及在 P n \mathcal P_n P n 上的精確性)
模板上的導數公式 是指
D h f ( x ) = 1 h ∑ j = 0 n w j f ( x + h t j ) , D_hf(x)=\frac1h\sum_{j=0}^n w_j\,f(x+ht_j), D h f ( x ) = h 1 j = 0 ∑ n w j f ( x + h t j ) , 其中權重 w j w_j w j 為無量綱實數。若對每個次數不超過 n n n 的多項式 p p p 都有 D h p ( x ) = p ′ ( x ) D_hp(x)=p'(x) D h p ( x ) = p ′ ( x ) ,則稱此公式在 P n \mathcal P_n P n 上精確 。
數據模型是確定性的。我們收到 y ~ j = f ( x + h t j ) + e j \tilde y_j=f(x+ht_j)+e_j y ~ j = f ( x + h t j ) + e j ,其中 δ ≥ 0 \delta\ge0 δ ≥ 0 為已知數,∣ e j ∣ ≤ δ |e_j|\le\delta ∣ e j ∣ ≤ δ ,而誤差可以有任何正負號及任何相互依賴關係。報告值為 D ~ = h − 1 ∑ j w j y ~ j \tilde D=h^{-1}\sum\limits_jw_j\tilde y_j D ~ = h − 1 j ∑ w j y ~ j ,並以精確算術計算 。以下內容並不界定在構成 x + h t j x+ht_j x + h t j 、計算 f f f 或求加權和時的捨入誤差。若另有論證界定了函數求值的誤差,可把它們併入 δ \delta δ ;但組合本身的算術仍在本分析範圍以外。
光滑性假設分為兩部分。第一,f ∈ C n + 1 ( I ) f\in C^{n+1}(I) f ∈ C n + 1 ( I ) 。第二,存在數 M ≥ 0 M\ge0 M ≥ 0 ,使得對每個 s ∈ I s\in I s ∈ I 都有 ∣ f ( n + 1 ) ( s ) ∣ ≤ M |f^{(n+1)}(s)|\le M ∣ f ( n + 1 ) ( s ) ∣ ≤ M 。這是關於函數在整個區間上的資訊,須由數據以外提供。
一般定理
定理 13.1.3
(唯一的精確權重與兩部分誤差界)
設 L 0 , … , L n L_0,\ldots,L_n L 0 , … , L n 為節點 t 0 , … , t n t_0,\ldots,t_n t 0 , … , t n 的拉格朗日(Lagrange)基多項式,即 j = k j=k j = k 時 L j ( t k ) = 1 L_j(t_k)=1 L j ( t k ) = 1 ,否則 L j ( t k ) = 0 L_j(t_k)=0 L j ( t k ) = 0 。
(i) 恰有一組權重使 D h D_h D h 在 P n \mathcal P_n P n 上精確,即 w j = L j ′ ( 0 ) w_j=L_j'(0) w j = L j ′ ( 0 ) 。它既不依賴 x x x ,也不依賴 h h h ,並由以下矩方程刻畫:
∑ j = 0 n w j t j k = { 1 , k = 1 , 0 , k = 0 或 2 ≤ k ≤ n . \sum_{j=0}^n w_jt_j^k=\begin{cases}1,&k=1,\\0,&k=0\ \text{或}\ 2\le k\le n.\end{cases} j = 0 ∑ n w j t j k = { 1 , 0 , k = 1 , k = 0 或 2 ≤ k ≤ n . (ii) 在上述光滑性假設及數據模型下,
∣ D ~ − f ′ ( x ) ∣ ≤ C T M h n + C N δ h , C T = 1 ( n + 1 ) ! ∑ j = 0 n ∣ w j ∣ ∣ t j ∣ n + 1 , C N = ∑ j = 0 n ∣ w j ∣ . |\tilde D-f'(x)|\le C_{\mathrm T}Mh^n+C_{\mathrm N}\frac{\delta}{h},\qquad
C_{\mathrm T}=\frac{1}{(n+1)!}\sum_{j=0}^n|w_j|\,|t_j|^{n+1},\qquad
C_{\mathrm N}=\sum_{j=0}^n|w_j|. ∣ D ~ − f ′ ( x ) ∣ ≤ C T M h n + C N h δ , C T = ( n + 1 )! 1 j = 0 ∑ n ∣ w j ∣ ∣ t j ∣ n + 1 , C N = j = 0 ∑ n ∣ w j ∣. 對固定模板及任意容許的數據誤差,項 C N δ / h C_{\mathrm N}\delta/h C N δ / h 不能再減小。
證明
變量代換。 對多項式 p p p ,令 q ( t ) = p ( x + h t ) q(t)=p(x+ht) q ( t ) = p ( x + h t ) 。則 p ∈ P n p\in\mathcal P_n p ∈ P n 當且僅當 q ∈ P n q\in\mathcal P_n q ∈ P n ,而樣本為 p ( x + h t j ) = q ( t j ) p(x+ht_j)=q(t_j) p ( x + h t j ) = q ( t j ) 。鏈式法則給出 p ′ ( x ) = q ′ ( 0 ) / h p'(x)=q'(0)/h p ′ ( x ) = q ′ ( 0 ) / h 。因此 D h D_h D h 在 P n \mathcal P_n P n 上精確,當且僅當
∑ j = 0 n w j q ( t j ) = q ′ ( 0 ) ( ∗ ) \sum_{j=0}^n w_j\,q(t_j)=q'(0)\qquad(\ast) j = 0 ∑ n w j q ( t j ) = q ′ ( 0 ) ( ∗ ) 對每個 q ∈ P n q\in\mathcal P_n q ∈ P n 成立。( ∗ ) (\ast) ( ∗ ) 中既沒有 x x x ,也沒有 h h h 。
存在性。 由插值的唯一性,每個 q ∈ P n q\in\mathcal P_n q ∈ P n 都等於它自己的插值多項式:q = ∑ j q ( t j ) L j q=\sum\limits_jq(t_j)L_j q = j ∑ q ( t j ) L j 。在 0 0 0 處求導,得 q ′ ( 0 ) = ∑ j q ( t j ) L j ′ ( 0 ) q'(0)=\sum\limits_jq(t_j)L_j'(0) q ′ ( 0 ) = j ∑ q ( t j ) L j ′ ( 0 ) 。故 w j = L j ′ ( 0 ) w_j=L_j'(0) w j = L j ′ ( 0 ) 滿足 ( ∗ ) (\ast) ( ∗ ) 。
唯一性。 設兩組權重都滿足 ( ∗ ) (\ast) ( ∗ ) 。其差 u u u 對每個 q ∈ P n q\in\mathcal P_n q ∈ P n 滿足 ∑ j u j q ( t j ) = 0 \sum\limits_ju_jq(t_j)=0 j ∑ u j q ( t j ) = 0 。取 q = L k q=L_k q = L k ,即得每個 u k = 0 u_k=0 u k = 0 。
矩方程。 多項式 1 , t , … , t n 1,t,\ldots,t^n 1 , t , … , t n 生成 P n \mathcal P_n P n ,而 ( ∗ ) (\ast) ( ∗ ) 兩邊對 q q q 均為線性。因此 ( ∗ ) (\ast) ( ∗ ) 等價於 q ( t ) = t k q(t)=t^k q ( t ) = t k (0 ≤ k ≤ n 0\le k\le n 0 ≤ k ≤ n )的各個特例。當 k = 1 k=1 k = 1 時 q ′ ( 0 ) = 1 q'(0)=1 q ′ ( 0 ) = 1 ,否則 q ′ ( 0 ) = 0 q'(0)=0 q ′ ( 0 ) = 0 ,所以這些特例正是矩方程。以矩陣表示,即 V T w = r V^{\mathsf T}w=r V T w = r ;其中 V j k = t j k V_{jk}=t_j^k V j k = t j k 為范德蒙(Vandermonde)矩陣,而右端向量 r r r 在 k = 1 k=1 k = 1 的分量為 1 1 1 、其餘分量為 0 0 0 。上述論證表明此方程組恰有一解,這亦從另一角度說明節點互不相同時 V V V 可逆。
截斷誤差。 取 t j ≠ 0 t_j\ne0 t j = 0 。由 x x x 到 x + h t j x+ht_j x + h t j 的線段位於 I I I 內,帶拉格朗日餘項的泰勒(Taylor)定理給出
f ( x + h t j ) = ∑ k = 0 n f ( k ) ( x ) k ! h k t j k + f ( n + 1 ) ( ξ j ) ( n + 1 ) ! h n + 1 t j n + 1 , f(x+ht_j)=\sum_{k=0}^n\frac{f^{(k)}(x)}{k!}h^kt_j^k+\frac{f^{(n+1)}(\xi_j)}{(n+1)!}h^{n+1}t_j^{n+1}, f ( x + h t j ) = k = 0 ∑ n k ! f ( k ) ( x ) h k t j k + ( n + 1 )! f ( n + 1 ) ( ξ j ) h n + 1 t j n + 1 , 其中 ξ j \xi_j ξ j 介乎 x x x 與 x + h t j x+ht_j x + h t j 之間。對 t j = 0 t_j=0 t j = 0 ,餘項為零,所以同一等式對任何 ξ j ∈ I \xi_j\in I ξ j ∈ I 成立。把等式乘以 w j / h w_j/h w j / h 並對 j j j 求和。指標為 k k k 的項貢獻
f ( k ) ( x ) h k − 1 k ! ∑ j = 0 n w j t j k . \frac{f^{(k)}(x)h^{k-1}}{k!}\sum_{j=0}^nw_jt_j^k. k ! f ( k ) ( x ) h k − 1 j = 0 ∑ n w j t j k . 由矩方程,當 k = 1 k=1 k = 1 時此項等於 f ′ ( x ) f'(x) f ′ ( x ) ,否則為零。因此
D h f ( x ) − f ′ ( x ) = h n ( n + 1 ) ! ∑ j = 0 n w j t j n + 1 f ( n + 1 ) ( ξ j ) . D_hf(x)-f'(x)=\frac{h^n}{(n+1)!}\sum_{j=0}^n w_jt_j^{n+1}f^{(n+1)}(\xi_j). D h f ( x ) − f ′ ( x ) = ( n + 1 )! h n j = 0 ∑ n w j t j n + 1 f ( n + 1 ) ( ξ j ) . 各點 ξ j \xi_j ξ j 未知且一般互不相同,所以逐項分別界定,得 ∣ D h f ( x ) − f ′ ( x ) ∣ ≤ C T M h n |D_hf(x)-f'(x)|\le C_{\mathrm T}Mh^n ∣ D h f ( x ) − f ′ ( x ) ∣ ≤ C T M h n 。
數據誤差。 由線性,D ~ − D h f ( x ) = h − 1 ∑ j w j e j \tilde D-D_hf(x)=h^{-1}\sum\limits_jw_je_j D ~ − D h f ( x ) = h − 1 j ∑ w j e j 。三角不等式把其絕對值界定為 C N δ / h C_{\mathrm N}\delta/h C N δ / h 。現把
D ~ − f ′ ( x ) = ( D ~ − D h f ( x ) ) + ( D h f ( x ) − f ′ ( x ) ) \tilde D-f'(x)=\bigl(\tilde D-D_hf(x)\bigr)+\bigl(D_hf(x)-f'(x)\bigr) D ~ − f ′ ( x ) = ( D ~ − D h f ( x ) ) + ( D h f ( x ) − f ′ ( x ) ) 再用一次三角不等式,即證得該界。最後,e j = δ sign ( w j ) e_j=\delta\operatorname{sign}(w_j) e j = δ sign ( w j ) 是容許的,並使 D ~ − D h f ( x ) \tilde D-D_hf(x) D ~ − D h f ( x ) 恰好等於 C N δ / h C_{\mathrm N}\delta/h C N δ / h ,所以該項不能減小。□ \square □
證明透視
每項假設用在何處 節點偏移互不相同,只用於構造拉格朗日基,而這組基同時給出存在性與唯一性。矩方程完成全部抵消:它們消去除攜帶 f ′ ( x ) f'(x) f ′ ( x ) 那一項以外的所有泰勒項。證明以常數乘 h n h^n h n 界定餘項。第一個未被規定的矩是 k = n + 1 k=n+1 k = n + 1 的那一個,但對某些模板它也可能為零;在適當的額外光滑性假設下,進一步抵消可以提高階數。
界 M M M 必須在整個 I I I 上成立,因為餘項點 ξ j \xi_j ξ j 可以位於 x x x 與最遠節點之間的任何位置。
數據界從不與光滑性結合。即使對一個一無所知的函數,項 C N δ / h C_{\mathrm N}\delta/h C N δ / h 也完全一樣;因此它描述的是公式本身,而不是 f f f 。
模板 x x x 、x + h x+h x + h 、x + 3 h x+3h x + 3 h
例題 13.1.4
(模板 0 , 1 , 3 0,1,3 0 , 1 , 3 的權重)
取 n = 2 n=2 n = 2 及 ( t 0 , t 1 , t 2 ) = ( 0 , 1 , 3 ) (t_0,t_1,t_2)=(0,1,3) ( t 0 , t 1 , t 2 ) = ( 0 , 1 , 3 ) :這是 x x x 右側的三個節點,間隔分別為 h h h 與 2 h 2h 2 h 。拉格朗日基為
L 0 ( t ) = ( t − 1 ) ( t − 3 ) 3 , L 1 ( t ) = − t ( t − 3 ) 2 , L 2 ( t ) = t ( t − 1 ) 6 . L_0(t)=\frac{(t-1)(t-3)}{3},\qquad L_1(t)=-\frac{t(t-3)}{2},\qquad L_2(t)=\frac{t(t-1)}{6}. L 0 ( t ) = 3 ( t − 1 ) ( t − 3 ) , L 1 ( t ) = − 2 t ( t − 3 ) , L 2 ( t ) = 6 t ( t − 1 ) . 其導數為 L 0 ′ ( t ) = ( 2 t − 4 ) / 3 L_0'(t)=(2t-4)/3 L 0 ′ ( t ) = ( 2 t − 4 ) /3 、L 1 ′ ( t ) = − ( 2 t − 3 ) / 2 L_1'(t)=-(2t-3)/2 L 1 ′ ( t ) = − ( 2 t − 3 ) /2 及 L 2 ′ ( t ) = ( 2 t − 1 ) / 6 L_2'(t)=(2t-1)/6 L 2 ′ ( t ) = ( 2 t − 1 ) /6 。在 t = 0 t=0 t = 0 處求值得
w 0 = − 4 3 , w 1 = 3 2 , w 2 = − 1 6 , D h f ( x ) = 1 h ( − 4 3 f ( x ) + 3 2 f ( x + h ) − 1 6 f ( x + 3 h ) ) . w_0=-\frac43,\qquad w_1=\frac32,\qquad w_2=-\frac16,\qquad
D_hf(x)=\frac1h\left(-\frac43f(x)+\frac32f(x+h)-\frac16f(x+3h)\right). w 0 = − 3 4 , w 1 = 2 3 , w 2 = − 6 1 , D h f ( x ) = h 1 ( − 3 4 f ( x ) + 2 3 f ( x + h ) − 6 1 f ( x + 3 h ) ) . 矩方程印證了這一點:
− 4 3 + 3 2 − 1 6 = 0 -\tfrac43+\tfrac32-\tfrac16=0 − 3 4 + 2 3 − 6 1 = 0 ;
3 2 ⋅ 1 − 1 6 ⋅ 3 = 1 \tfrac32\cdot1-\tfrac16\cdot3=1 2 3 ⋅ 1 − 6 1 ⋅ 3 = 1 ;
3 2 ⋅ 1 − 1 6 ⋅ 9 = 0 \tfrac32\cdot1-\tfrac16\cdot9=0 2 3 ⋅ 1 − 6 1 ⋅ 9 = 0 。
下一個矩為 3 2 ⋅ 1 − 1 6 ⋅ 27 = − 3 ≠ 0 \tfrac32\cdot1-\tfrac16\cdot27=-3\ne0 2 3 ⋅ 1 − 6 1 ⋅ 27 = − 3 = 0 ,故此公式對三次多項式並不精確。
命題 13.1.5
(模板 0 , 1 , 3 0,1,3 0 , 1 , 3 的誤差界)
設 h > 0 h>0 h > 0 ,f ∈ C 3 ( [ x , x + 3 h ] ) f\in C^3([x,x+3h]) f ∈ C 3 ([ x , x + 3 h ]) ,且在 [ x , x + 3 h ] [x,x+3h] [ x , x + 3 h ] 上 ∣ f ′ ′ ′ ∣ ≤ M |f'''|\le M ∣ f ′′′ ∣ ≤ M 。設三個所給數值各自的絕對誤差不超過 δ \delta δ ,而 D ~ \tilde D D ~ 為上述公式在這些數值上的精確計算結果。則
∣ D ~ − f ′ ( x ) ∣ ≤ M h 2 + 3 δ h . |\tilde D-f'(x)|\le Mh^2+\frac{3\delta}{h}. ∣ D ~ − f ′ ( x ) ∣ ≤ M h 2 + h 3 δ .
此處 I = [ x , x + 3 h ] I=[x,x+3h] I = [ x , x + 3 h ] 。由一般餘項公式,取 ξ 1 ∈ ( x , x + h ) \xi_1\in(x,x+h) ξ 1 ∈ ( x , x + h ) 、ξ 2 ∈ ( x , x + 3 h ) \xi_2\in(x,x+3h) ξ 2 ∈ ( x , x + 3 h ) ,得
D h f ( x ) − f ′ ( x ) = h 2 6 ( 3 2 f ′ ′ ′ ( ξ 1 ) − 9 2 f ′ ′ ′ ( ξ 2 ) ) = h 2 4 ( f ′ ′ ′ ( ξ 1 ) − 3 f ′ ′ ′ ( ξ 2 ) ) . D_hf(x)-f'(x)=\frac{h^2}{6}\left(\frac32f'''(\xi_1)-\frac92f'''(\xi_2)\right)=\frac{h^2}{4}\bigl(f'''(\xi_1)-3f'''(\xi_2)\bigr). D h f ( x ) − f ′ ( x ) = 6 h 2 ( 2 3 f ′′′ ( ξ 1 ) − 2 9 f ′′′ ( ξ 2 ) ) = 4 h 2 ( f ′′′ ( ξ 1 ) − 3 f ′′′ ( ξ 2 ) ) . 以 M M M 界定每個三階導數,得 ( 1 4 + 3 4 ) M h 2 = M h 2 \bigl(\tfrac14+\tfrac34\bigr)Mh^2=Mh^2 ( 4 1 + 4 3 ) M h 2 = M h 2 ,故 C T = 1 C_{\mathrm T}=1 C T = 1 。權重絕對值之和為 4 3 + 3 2 + 1 6 = 3 \tfrac43+\tfrac32+\tfrac16=3 3 4 + 2 3 + 6 1 = 3 ,故 C N = 3 C_{\mathrm N}=3 C N = 3 。由一般定理即得此命題。
常數 1 1 1 來自讓兩個餘項以最大幅度取相反符號。論證並不聲稱 1 1 1 是最小的有效常數。下面關於函數族 g A g_A g A 的練習表明,此公式的最小有效常數至少為 1 2 \tfrac12 2 1 。
由誤差界選擇 h h h
記 B ( h ) = M h 2 + 3 δ / h B(h)=Mh^2+3\delta/h B ( h ) = M h 2 + 3 δ / h ,並設 M > 0 M>0 M > 0 及 δ > 0 \delta>0 δ > 0 。則 B ′ ( h ) = 2 M h − 3 δ / h 2 B'(h)=2Mh-3\delta/h^2 B ′ ( h ) = 2 M h − 3 δ / h 2 ;它在 0 < h < h ∗ 0<h<h_\ast 0 < h < h ∗ 時為負,在 h > h ∗ h>h_\ast h > h ∗ 時為正,其中
h ∗ = ( 3 δ 2 M ) 1 / 3 , B ( h ∗ ) = 3 M h ∗ 2 . h_\ast=\left(\frac{3\delta}{2M}\right)^{1/3},\qquad B(h_\ast)=3Mh_\ast^2. h ∗ = ( 2 M 3 δ ) 1/3 , B ( h ∗ ) = 3 M h ∗ 2 .
B ( h ∗ ) B(h_\ast) B ( h ∗ ) 的值成立,是因為在該點 3 δ / h ∗ = 2 M h ∗ 2 3\delta/h_\ast=2Mh_\ast^2 3 δ / h ∗ = 2 M h ∗ 2 。
這個極小點只在容許時才有意義。實際上 M M M 只在某區間 [ x , x + 3 H ] [x,x+3H] [ x , x + 3 H ] 上已知,因此 h h h 的取值範圍是 ( 0 , H ] (0,H] ( 0 , H ] 。
若 h ∗ ≤ H h_\ast\le H h ∗ ≤ H ,則 h ∗ h_\ast h ∗ 在 ( 0 , H ] (0,H] ( 0 , H ] 上使 B B B 取最小值。
若 h ∗ > H h_\ast>H h ∗ > H ,則 B B B 在整個 ( 0 , H ] (0,H] ( 0 , H ] 上遞減,按誤差界的選擇是 h = H h=H h = H 。若使用 h ∗ h_\ast h ∗ ,便會在 M M M 未知之處取樣,而 B ( h ∗ ) B(h_\ast) B ( h ∗ ) 根本不是已證明的界。
若 M > 0 M>0 M > 0 而 δ = 0 \delta=0 δ = 0 ,界 M h 2 Mh^2 M h 2 隨 h h h 減小而下降,在 ( 0 , H ] (0,H] ( 0 , H ] 上沒有最小值。若 M = 0 M=0 M = 0 而 δ > 0 \delta>0 δ > 0 ,則 f f f 在區間上與一個二次多項式相同,因此公式對精確樣本是精確的;界 3 δ / h 3\delta/h 3 δ / h 在 h = H h=H h = H 時最小。若 M = δ = 0 M=\delta=0 M = δ = 0 ,每個容許的 h h h 都使界等於零,因而都是極小點。
當 M , δ > 0 M,\delta>0 M , δ > 0 且 h ∗ h_\ast h ∗ 容許時,它最小化的是一個上界,而不是未知的實際誤差。當 h h h 很小時,模型所排除的捨入誤差亦可能變得重要。
三次多項式:實際誤差與誤差界的比較
設 f ( s ) = s 3 − 2 s f(s)=s^3-2s f ( s ) = s 3 − 2 s 、x = 1 x=1 x = 1 、h = 0.1 h=0.1 h = 0.1 。則 f ′ ( 1 ) = 1 f'(1)=1 f ′ ( 1 ) = 1 ,樣本為 f ( 1 ) = − 1 f(1)=-1 f ( 1 ) = − 1 、f ( 1.1 ) = − 0.869 f(1.1)=-0.869 f ( 1.1 ) = − 0.869 及 f ( 1.3 ) = − 0.403 f(1.3)=-0.403 f ( 1.3 ) = − 0.403 。因此
D h f ( 1 ) = 10 ( 4 3 − 3 2 ( 0.869 ) + 0.403 6 ) = 10 ( 1.33333 … − 1.3035 + 0.06716 … ) = 0.97 , D_hf(1)=10\left(\frac43-\frac32(0.869)+\frac{0.403}{6}\right)=10\,(1.33333\ldots-1.3035+0.06716\ldots)=0.97, D h f ( 1 ) = 10 ( 3 4 − 2 3 ( 0.869 ) + 6 0.403 ) = 10 ( 1.33333 … − 1.3035 + 0.06716 … ) = 0.97 , 帶符號誤差為 D h f ( 1 ) − f ′ ( 1 ) = − 0.03 D_hf(1)-f'(1)=-0.03 D h f ( 1 ) − f ′ ( 1 ) = − 0.03 。
同一數值亦可從結構上得出。對一般的 x x x 取 f ( s ) = s 3 f(s)=s^3 f ( s ) = s 3 ,展開三個樣本,得 D h f ( x ) = 3 x 2 − 3 h 2 D_hf(x)=3x^2-3h^2 D h f ( x ) = 3 x 2 − 3 h 2 ;而次數不超過二的多項式會被精確求導。因此,對任何首項係數為 a a a 的三次多項式,帶符號誤差恰為 − 3 a h 2 -3ah^2 − 3 a h 2 。此處 a = 1 a=1 a = 1 、h 2 = 0.01 h^2=0.01 h 2 = 0.01 。
取 M = 6 M=6 M = 6 ,命題只保證 ∣ D h f ( 1 ) − f ′ ( 1 ) ∣ ≤ 6 h 2 = 0.06 |D_hf(1)-f'(1)|\le6h^2=0.06 ∣ D h f ( 1 ) − f ′ ( 1 ) ∣ ≤ 6 h 2 = 0.06 ,是實際誤差的兩倍。餘項公式解釋了這個差距:f ′ ′ ′ ≡ 6 f'''\equiv6 f ′′′ ≡ 6 給出 h 2 4 ( 6 − 3 ⋅ 6 ) = − 3 h 2 \tfrac{h^2}{4}(6-3\cdot6)=-3h^2 4 h 2 ( 6 − 3 ⋅ 6 ) = − 3 h 2 。兩個餘項部分抵消,而誤差界卻把它們的大小相加。
符號亦有資訊價值:對每個 a > 0 a>0 a > 0 的三次多項式,此公式都會低估導數,而且低估量總是 3 a h 2 3ah^2 3 a h 2 。
雜訊放大與條件性
項 3 δ / h 3\delta/h 3 δ / h 是差分的代價。權重大小適中且總和為零,所以數據中的常數偏移會完全抵消。誤差的加權和要除以 h h h ,其最壞情況放大倍數隨 1 / h 1/h 1/ h 增長;但某些非常數的誤差模式也會抵消。對此模板,誤差 ( − δ , δ , − δ ) (-\delta,\delta,-\delta) ( − δ , δ , − δ ) 實現了最壞情況:不論 f f f 為何,它們都恰好使輸出增加 3 δ / h 3\delta/h 3 δ / h 。
以條件性的語言而言,C N / h = 3 / h C_{\mathrm N}/h=3/h C N / h = 3/ h 是此公式在此誤差模型下的精確最壞情況放大因子;它把最大的絕對數據誤差映射為所報告導數的絕對誤差。它不是相對條件數:當 f ′ ( x ) f'(x) f ′ ( x ) 接近零時,相對誤差的陳述可能差得多。它亦不描述隨機誤差的典型行為,因為隨機誤差可能部分抵消。
此界所保證的是雙向的:
沒有任何容許的數據誤差能使輸出改變超過 3 δ / h 3\delta/h 3 δ / h ;
有某個容許的數據誤差使輸出恰好改變這個量。
例題 13.1.7
(與等距模板 0 , 1 , 2 0,1,2 0 , 1 , 2 比較)
節點位置會影響兩個常數。對等距模板 0 , 1 , 2 0,1,2 0 , 1 , 2 ,矩方程為 w 0 + w 1 + w 2 = 0 w_0+w_1+w_2=0 w 0 + w 1 + w 2 = 0 、w 1 + 2 w 2 = 1 w_1+2w_2=1 w 1 + 2 w 2 = 1 及 w 1 + 4 w 2 = 0 w_1+4w_2=0 w 1 + 4 w 2 = 0 。後兩式相減得 w 2 = − 1 2 w_2=-\tfrac12 w 2 = − 2 1 ,從而 w 1 = 2 w_1=2 w 1 = 2 、w 0 = − 3 2 w_0=-\tfrac32 w 0 = − 2 3 。於是 C T = 1 6 ( 2 ⋅ 1 + 1 2 ⋅ 8 ) = 1 C_{\mathrm T}=\tfrac16\bigl(2\cdot1+\tfrac12\cdot8\bigr)=1 C T = 6 1 ( 2 ⋅ 1 + 2 1 ⋅ 8 ) = 1 ,截斷常數相同;雜訊常數則是 C N = 3 2 + 2 + 1 2 = 4 C_{\mathrm N}=\tfrac32+2+\tfrac12=4 C N = 2 3 + 2 + 2 1 = 4 。在相同的 h h h 下,模板 0 , 1 , 3 0,1,3 0 , 1 , 3 的雜訊常數較小。然而它取樣至 x + 3 h x+3h x + 3 h 而非 x + 2 h x+2h x + 2 h ,所以其假設涉及更長的區間,亦可能涉及更大的 M M M 。
下面關於模板 0 , 2 , 3 0,2,3 0 , 2 , 3 的練習表明,把中間節點移離 x x x 可以大幅增大截斷常數。只有在固定區間與光滑性假設的前提下,比較不同模板才有意義。
為何必須假設光滑性
反例模式
相同樣本,不同導數 取 x = 0 x=0 x = 0 及 g ( s ) = s ( s − h ) ( s − 3 h ) = s 3 − 4 h s 2 + 3 h 2 s g(s)=s(s-h)(s-3h)=s^3-4hs^2+3h^2s g ( s ) = s ( s − h ) ( s − 3 h ) = s 3 − 4 h s 2 + 3 h 2 s 。則 g ( 0 ) = g ( h ) = g ( 3 h ) = 0 g(0)=g(h)=g(3h)=0 g ( 0 ) = g ( h ) = g ( 3 h ) = 0 ,與零函數的三個樣本完全相同。然而
g ′ ( s ) = 3 s 2 − 8 h s + 3 h 2 , g ′ ( 0 ) = 3 h 2 ≠ 0. g'(s)=3s^2-8hs+3h^2,\qquad g'(0)=3h^2\ne0. g ′ ( s ) = 3 s 2 − 8 h s + 3 h 2 , g ′ ( 0 ) = 3 h 2 = 0. 兩個函數都是多項式,因而無限次可微。任何只看到這三個數值的程序,都必須對兩者報告同一個數,所以它對導數 0 0 0 與 3 h 2 3h^2 3 h 2 中至少一個的誤差不小於 3 h 2 / 2 3h^2/2 3 h 2 /2 。
把 g g g 換成 A g Ag A g ,差異便成為 3 ∣ A ∣ h 2 3|A|h^2 3∣ A ∣ h 2 ;隨 A A A 變化,它沒有上界。因此不可能由這些樣本一般地精確恢復 f ′ ( 0 ) f'(0) f ′ ( 0 ) 。
補救方法是定量假設。由於 ( A g ) ′ ′ ′ = 6 A (Ag)'''=6A ( A g ) ′′′ = 6 A ,假設 ∣ f ′ ′ ′ ∣ ≤ M |f'''|\le M ∣ f ′′′ ∣ ≤ M 在 [ 0 , 3 h ] [0,3h] [ 0 , 3 h ] 上成立,便迫使 ∣ A ∣ ≤ M / 6 |A|\le M/6 ∣ A ∣ ≤ M /6 ,因此在這個函數族內,每個導數 g A ′ ( 0 ) g_A'(0) g A ′ ( 0 ) 與零相差至多 M h 2 / 2 Mh^2/2 M h 2 /2 ;可能導數的範圍直徑是 M h 2 Mh^2 M h 2 。
這個教訓在每個目標點都成立。可微性,甚至無限次可微性,都不能從有限個樣本得出任何誤差保證。把 A g ( s − x ) A\,g(s-x) A g ( s − x ) 加到任何函數上,其在 x , x + h , x + 3 h x,x+h,x+3h x , x + h , x + 3 h 的樣本不變,而在 x x x 處的導數改變 3 A h 2 3Ah^2 3 A h 2 。所以數據與導數的任何實數值都相容。
在整個 [ x , x + 3 h ] [x,x+3h] [ x , x + 3 h ] 上對 f ′ ′ ′ f''' f ′′′ 的界可以限制這個函數族。只在 x x x 附近成立的界並不足夠,因為 ξ 2 \xi_2 ξ 2 可能靠近 x + 3 h x+3h x + 3 h 。這樣的界必須來自對數據來源的認識,例如函數所滿足的模型或微分方程;它不能從樣本中讀出。
常見錯誤
在 [ x , x + h ] [x,x+h] [ x , x + h ] 上或只在 x x x 附近界定 ∣ f ′ ′ ′ ∣ |f'''| ∣ f ′′′ ∣ ,並不足以套用命題。最遠節點的餘項點可以位於 ( x , x + 3 h ) (x,x+3h) ( x , x + 3 h ) 中的任何位置,所以 M M M 必須在整個 [ x , x + 3 h ] [x,x+3h] [ x , x + 3 h ] 上界定 ∣ f ′ ′ ′ ∣ |f'''| ∣ f ′′′ ∣ 。
步長 h ∗ h_\ast h ∗ 最小化的是最壞情況上界,而且只在容許時才成立。它不是使實際誤差最小的步長;實際誤差取決於未知函數及具體的數據誤差。
不等距模板的權重不能由等距模板的權重按比例換算得來。必須針對實際偏移,由矩方程或拉格朗日基重新計算。
總結
對 n + 1 n+1 n + 1 個互不相同的偏移,恰有一個公式 h − 1 ∑ j w j f ( x + h t j ) h^{-1}\sum\limits_jw_jf(x+ht_j) h − 1 j ∑ w j f ( x + h t j ) 在 P n \mathcal P_n P n 上精確。其權重為 L j ′ ( 0 ) L_j'(0) L j ′ ( 0 ) ,並滿足矩方程。
假設在整個取樣區間上 f ( n + 1 ) f^{(n+1)} f ( n + 1 ) 以 M M M 為界,而每個數據誤差以 δ \delta δ 為界。則在精確算術下,誤差不超過 C T M h n + C N δ / h C_{\mathrm T}Mh^n+C_{\mathrm N}\delta/h C T M h n + C N δ / h ,而數據項可以達到。
對模板 x , x + h , x + 3 h x,x+h,x+3h x , x + h , x + 3 h ,此界為 M h 2 + 3 δ / h Mh^2+3\delta/h M h 2 + 3 δ / h 。對首項係數 a ≠ 0 a\ne0 a = 0 的三次多項式,若取緊界 M = 6 ∣ a ∣ M=6|a| M = 6∣ a ∣ ,截斷項是實際絕對誤差的兩倍;若取更大的有效 M M M ,比值會更大。沒有定量的光滑性界,樣本並不能決定導數。
練習
快速檢查
(考慮單側模板 ( t 0 , t 1 , t 2 ) = ( 0 , 2 , 3 ) (t_0,t_1,t_2)=(0,2,3) ( t 0 , t 1 , t 2 ) = ( 0 , 2 , 3 ) 。)
(a) 求解矩方程,得出在 P 2 \mathcal P_2 P 2 上精確的權重,並用拉格朗日基核對其中一個權重。
(b) 計算 C T C_{\mathrm T} C T 與 C N C_{\mathrm N} C N ,並連同假設寫出所得的誤差界。
(c) 求首項係數為 a a a 的三次多項式的帶符號誤差,並與模板 0 , 1 , 3 0,1,3 0 , 1 , 3 比較。
解答 (a) k = 0 , 1 , 2 k=0,1,2 k = 0 , 1 , 2 的矩方程為
w 0 + w 1 + w 2 = 0 , 2 w 1 + 3 w 2 = 1 , 4 w 1 + 9 w 2 = 0. w_0+w_1+w_2=0,\qquad 2w_1+3w_2=1,\qquad 4w_1+9w_2=0. w 0 + w 1 + w 2 = 0 , 2 w 1 + 3 w 2 = 1 , 4 w 1 + 9 w 2 = 0. 第三式給出 w 1 = − 9 4 w 2 w_1=-\tfrac94w_2 w 1 = − 4 9 w 2 。代入第二式,得 − 3 2 w 2 = 1 -\tfrac32w_2=1 − 2 3 w 2 = 1 。因此
w 2 = − 2 3 , w 1 = 3 2 , w 0 = − 5 6 . w_2=-\tfrac23,\qquad w_1=\tfrac32,\qquad w_0=-\tfrac56. w 2 = − 3 2 , w 1 = 2 3 , w 0 = − 6 5 . 由定理,節點互不相同,所以解是唯一的;等價地,范德蒙行列式 ( 2 − 0 ) ( 3 − 0 ) ( 3 − 2 ) = 6 (2-0)(3-0)(3-2)=6 ( 2 − 0 ) ( 3 − 0 ) ( 3 − 2 ) = 6 不為零。
作為核對,L 1 ( t ) = t ( t − 3 ) 2 ( 2 − 3 ) = − t ( t − 3 ) 2 L_1(t)=\dfrac{t(t-3)}{2(2-3)}=-\dfrac{t(t-3)}{2} L 1 ( t ) = 2 ( 2 − 3 ) t ( t − 3 ) = − 2 t ( t − 3 ) ,故 L 1 ′ ( 0 ) = 3 2 L_1'(0)=\tfrac32 L 1 ′ ( 0 ) = 2 3 。
(b) 雜訊常數為 C N = 5 6 + 3 2 + 2 3 = 3 C_{\mathrm N}=\tfrac56+\tfrac32+\tfrac23=3 C N = 6 5 + 2 3 + 3 2 = 3 。至於截斷常數,w 1 t 1 3 = 12 w_1t_1^3=12 w 1 t 1 3 = 12 、w 2 t 2 3 = − 18 w_2t_2^3=-18 w 2 t 2 3 = − 18 ,故 C T = ( 12 + 18 ) / 6 = 5 C_{\mathrm T}=(12+18)/6=5 C T = ( 12 + 18 ) /6 = 5 。
所得陳述為:若 f ∈ C 3 ( [ x , x + 3 h ] ) f\in C^3([x,x+3h]) f ∈ C 3 ([ x , x + 3 h ]) 且在該區間上 ∣ f ′ ′ ′ ∣ ≤ M |f'''|\le M ∣ f ′′′ ∣ ≤ M ,而數據誤差不超過 δ \delta δ ,則在精確算術下
∣ D ~ − f ′ ( x ) ∣ ≤ 5 M h 2 + 3 δ h . |\tilde D-f'(x)|\le5Mh^2+\frac{3\delta}{h}. ∣ D ~ − f ′ ( x ) ∣ ≤ 5 M h 2 + h 3 δ . (c) 餘項為 h 2 6 ( 12 f ′ ′ ′ ( ξ 1 ) − 18 f ′ ′ ′ ( ξ 2 ) ) \tfrac{h^2}{6}\bigl(12f'''(\xi_1)-18f'''(\xi_2)\bigr) 6 h 2 ( 12 f ′′′ ( ξ 1 ) − 18 f ′′′ ( ξ 2 ) ) 。對三次多項式 f ′ ′ ′ ≡ 6 a f'''\equiv6a f ′′′ ≡ 6 a ,帶符號誤差為 h 2 6 ( − 6 ) ( 6 a ) = − 6 a h 2 \tfrac{h^2}{6}(-6)(6a)=-6ah^2 6 h 2 ( − 6 ) ( 6 a ) = − 6 a h 2 。
直接計算,對 x = 0 x=0 x = 0 處的 s 3 s^3 s 3 :
h − 1 ( 3 2 ⋅ 8 h 3 − 2 3 ⋅ 27 h 3 ) = − 6 h 2 . h^{-1}\bigl(\tfrac32\cdot8h^3-\tfrac23\cdot27h^3\bigr)=-6h^2. h − 1 ( 2 3 ⋅ 8 h 3 − 3 2 ⋅ 27 h 3 ) = − 6 h 2 . 模板 0 , 1 , 3 0,1,3 0 , 1 , 3 給出 − 3 a h 2 -3ah^2 − 3 a h 2 。兩個模板都覆蓋 [ x , x + 3 h ] [x,x+3h] [ x , x + 3 h ] ,且 C N = 3 C_{\mathrm N}=3 C N = 3 。然而,在 x x x 旁留下 2 h 2h 2 h 的空隙,會使三次多項式的誤差加倍,並把已證明的截斷常數由 1 1 1 提高到 5 5 5 。
快速檢查
(設 M > 0 M>0 M > 0 、h > 0 h>0 h > 0 ,及 g A ( s ) = A s ( s − h ) ( s − 3 h ) g_A(s)=A\,s(s-h)(s-3h) g A ( s ) = A s ( s − h ) ( s − 3 h ) 。)
(a) 考慮任何由 0 , h , 3 h 0,h,3h 0 , h , 3 h 處三個精確樣本報告一個數的程序。證明存在某個在 [ 0 , 3 h ] [0,3h] [ 0 , 3 h ] 上滿足 ∣ f ′ ′ ′ ∣ ≤ M |f'''|\le M ∣ f ′′′ ∣ ≤ M 的函數,使該程序的誤差至少為 M h 2 / 4 Mh^2/4 M h 2 /4 。
(b) 證明模板 0 , 1 , 3 0,1,3 0 , 1 , 3 的公式 D h D_h D h 對 g M / 6 g_{M/6} g M /6 的誤差恰為 M h 2 / 2 Mh^2/2 M h 2 /2 。這對 M h 2 Mh^2 M h 2 中的常數說明了甚麼?
解答 (a) 每個 g A g_A g A 都在 0 , h , 3 h 0,h,3h 0 , h , 3 h 處為零,與 f ≡ 0 f\equiv0 f ≡ 0 完全一樣。由反例中的計算,g A ′ ( 0 ) = 3 A h 2 g_A'(0)=3Ah^2 g A ′ ( 0 ) = 3 A h 2 。由於 g A ′ ′ ′ ≡ 6 A g_A'''\equiv6A g A ′′′ ≡ 6 A ,取 A = M / 6 A=M/6 A = M /6 滿足假設,零函數亦然。
收到樣本 ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) 的程序對兩個函數報告同一個數 c c c ,誤差分別為 ∣ c ∣ |c| ∣ c ∣ 與 ∣ c − M h 2 / 2 ∣ |c-Mh^2/2| ∣ c − M h 2 /2∣ 。兩者之和至少為 M h 2 / 2 Mh^2/2 M h 2 /2 ,故較大者至少為 M h 2 / 4 Mh^2/4 M h 2 /4 。
(b) 對零數據應用 D h D_h D h 得 0 0 0 ,而 g M / 6 ′ ( 0 ) = M h 2 / 2 g_{M/6}'(0)=Mh^2/2 g M /6 ′ ( 0 ) = M h 2 /2 ,所以誤差恰為 M h 2 / 2 Mh^2/2 M h 2 /2 。這與三次多項式公式 − 3 a h 2 -3ah^2 − 3 a h 2 在 a = M / 6 a=M/6 a = M /6 時一致。
因此,對此公式,任何對所有容許 f f f 成立、形如 C M h 2 CMh^2 C M h 2 的界都不能有 C < 1 2 C<\tfrac12 C < 2 1 。已證明的常數 C = 1 C=1 C = 1 至多是 D h D_h D h 最佳可能常數的兩倍。由 (a),任何基於這些樣本的公式都不能保證常數小於 1 4 \tfrac14 4 1 。
快速檢查
(設 f ( s ) = s 2 f(s)=s^2 f ( s ) = s 2 、x = 0 x=0 x = 0 及 δ > 0 \delta>0 δ > 0 ,使用模板 0 , 1 , 3 0,1,3 0 , 1 , 3 。)
(a) 給出數據誤差 ( e 0 , e 1 , e 2 ) = ( − δ , δ , − δ ) (e_0,e_1,e_2)=(-\delta,\delta,-\delta) ( e 0 , e 1 , e 2 ) = ( − δ , δ , − δ ) ,計算 D ~ \tilde D D ~ 。
(b) 改用誤差 ( δ , δ , δ ) (\delta,\delta,\delta) ( δ , δ , δ ) 重做。
(c) 解釋這兩個計算對界 3 δ / h 3\delta/h 3 δ / h 說明了甚麼。
解答 (a) 精確樣本為 0 , h 2 , 9 h 2 0,h^2,9h^2 0 , h 2 , 9 h 2 。於是
D h f ( 0 ) = h − 1 ( 3 2 h 2 − 1 6 ⋅ 9 h 2 ) = 0 = f ′ ( 0 ) , D_hf(0)=h^{-1}\bigl(\tfrac32h^2-\tfrac16\cdot9h^2\bigr)=0=f'(0), D h f ( 0 ) = h − 1 ( 2 3 h 2 − 6 1 ⋅ 9 h 2 ) = 0 = f ′ ( 0 ) , 符合在 P 2 \mathcal P_2 P 2 上精確的要求。數據誤差帶來
1 h ( − 4 3 ( − δ ) + 3 2 δ − 1 6 ( − δ ) ) = 3 δ h . \frac1h\left(-\frac43(-\delta)+\frac32\delta-\frac16(-\delta)\right)=\frac{3\delta}{h}. h 1 ( − 3 4 ( − δ ) + 2 3 δ − 6 1 ( − δ ) ) = h 3 δ . 所以 D ~ = 3 δ / h \tilde D=3\delta/h D ~ = 3 δ / h ,誤差等於 3 δ / h 3\delta/h 3 δ / h 。
(b) 誤差帶來 h − 1 δ ∑ j w j = 0 h^{-1}\delta\sum\limits_jw_j=0 h − 1 δ j ∑ w j = 0 ,所以 D ~ = 0 \tilde D=0 D ~ = 0 ,報告的導數是正確的。
(c) 由於 f ′ ′ ′ ≡ 0 f'''\equiv0 f ′′′ ≡ 0 ,可取 M = 0 M=0 M = 0 ,命題給出恰為 3 δ / h 3\delta/h 3 δ / h 的界,而 (a) 達到了它,所以數據項是緊的。(b) 表明,同樣大小的數據誤差可以無害。
此界是對所有符號模式的最壞情況保證,而非對某一特定模式誤差的預測。在 (a) 中,固定 δ \delta δ 時,誤差隨 h → 0 h\to0 h → 0 無界增長。
快速檢查
(使用模板 0 , 1 , 3 0,1,3 0 , 1 , 3 。設 ∣ f ′ ′ ′ ∣ ≤ M = 3 2 |f'''|\le M=\tfrac32 ∣ f ′′′ ∣ ≤ M = 2 3 ,而每個樣本的絕對誤差不超過 δ = 10 − 6 \delta=10^{-6} δ = 1 0 − 6 。)
(a) 假設導數界在 [ x , x + 3 h ∗ ] [x,x+3h_\ast] [ x , x + 3 h ∗ ] 上成立,計算 h ∗ h_\ast h ∗ 與 B ( h ∗ ) B(h_\ast) B ( h ∗ ) 。
(b) 現設該界只在 [ x , x + 0.015 ] [x,x+0.015] [ x , x + 0.015 ] 上已知。求使 B B B 最小的容許 h h h 及相應的界值。
(c) 計算 B ( 0.001 ) B(0.001) B ( 0.001 ) 並加以評論。
解答 (a) h ∗ 3 = 3 δ / ( 2 M ) = 3 ⋅ 10 − 6 / 3 = 10 − 6 h_\ast^3=3\delta/(2M)=3\cdot10^{-6}/3=10^{-6} h ∗ 3 = 3 δ / ( 2 M ) = 3 ⋅ 1 0 − 6 /3 = 1 0 − 6 ,故 h ∗ = 0.01 h_\ast=0.01 h ∗ = 0.01 。界的兩部分為 M h ∗ 2 = 1.5 × 10 − 4 Mh_\ast^2=1.5\times10^{-4} M h ∗ 2 = 1.5 × 1 0 − 4 及 3 δ / h ∗ = 3 × 10 − 4 3\delta/h_\ast=3\times10^{-4} 3 δ / h ∗ = 3 × 1 0 − 4 。因此 B ( h ∗ ) = 4.5 × 10 − 4 = 3 M h ∗ 2 B(h_\ast)=4.5\times10^{-4}=3Mh_\ast^2 B ( h ∗ ) = 4.5 × 1 0 − 4 = 3 M h ∗ 2 。
(b) 容許性要求 x + 3 h ≤ x + 0.015 x+3h\le x+0.015 x + 3 h ≤ x + 0.015 ,即 h ≤ H = 0.005 h\le H=0.005 h ≤ H = 0.005 。由於 h ∗ = 0.01 > H h_\ast=0.01>H h ∗ = 0.01 > H ,函數 B B B 在 ( 0 , H ] (0,H] ( 0 , H ] 上遞減。所以最佳容許選擇是 h = 0.005 h=0.005 h = 0.005 ,相應
B ( 0.005 ) = 1.5 ⋅ 2.5 × 10 − 5 + 3 × 10 − 6 0.005 = 3.75 × 10 − 5 + 6 × 10 − 4 = 6.375 × 10 − 4 . B(0.005)=1.5\cdot2.5\times10^{-5}+\frac{3\times10^{-6}}{0.005}=3.75\times10^{-5}+6\times10^{-4}=6.375\times10^{-4}. B ( 0.005 ) = 1.5 ⋅ 2.5 × 1 0 − 5 + 0.005 3 × 1 0 − 6 = 3.75 × 1 0 − 5 + 6 × 1 0 − 4 = 6.375 × 1 0 − 4 . (a) 中較小的值 4.5 × 10 − 4 4.5\times10^{-4} 4.5 × 1 0 − 4 並不可用:在 h = 0.01 h=0.01 h = 0.01 時,節點 x + 0.03 x+0.03 x + 0.03 位於 M M M 已知的區間以外。
(c) B ( 0.001 ) = 1.5 × 10 − 6 + 3 × 10 − 3 = 3.0015 × 10 − 3 B(0.001)=1.5\times10^{-6}+3\times10^{-3}=3.0015\times10^{-3} B ( 0.001 ) = 1.5 × 1 0 − 6 + 3 × 1 0 − 3 = 3.0015 × 1 0 − 3 ,約為 h = 0.005 h=0.005 h = 0.005 時界值的 4.7 4.7 4.7 倍。把 h h h 減到容許最優值以下,會縮小截斷部分,卻讓數據部分佔主導。這三個數都是精確算術下的界,而非觀察到的誤差。
尚待處理的範圍
本筆記只處理:
一階導數;
恰有 n + 1 n+1 n + 1 個節點並在 P n \mathcal P_n P n 上精確的公式;
最壞情況下有界的數據誤差;
精確算術。
以下題目在此並未分析:
橫座標或加權和中的捨入誤差;
緊的誤差常數。泰勒餘項的積分形式可以改進模板 0 , 1 , 3 0,1,3 0 , 1 , 3 的常數 1 1 1 ,而關於 g A g_A g A 的練習表明它不能低於 1 2 \tfrac12 2 1 ;此改進在此並未證明;
節點聚集或 n n n 增大時權重的表現;
使用多於未知數個樣本的最小二乘公式;
統計雜訊模型;
不等距模板上的二階及更高階導數。
這些都是自然的後續筆記題目,而上面證明的界並不蘊含其中任何一項。