动机
中心差分 ( 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 增大时权重的表现;
使用多于未知数个样本的最小二乘公式;
统计噪声模型;
不等距模板上的二阶及更高阶导数。
这些都是自然的后续笔记题目,而上面证明的界并不蕴含其中任何一项。