从多项式精确性到误差界
n n n 节点的 Gaussian 求积公式能够精确积分所有次数不超过 2 n − 1 2n-1 2 n − 1 的多项式。这一结论描述的是一个有限维空间。若要控制非多项式被积函数的误差,我们需要把该函数与这个空间联系起来的信息。本节使用的是其 2 n 2n 2 n 阶导数的界;所得公式控制误差的大小;当 2 n 2n 2 n 阶导数在整个区间上具有同一符号时,还能判断误差的符号。
我们沿用前一节的带权 Gaussian 构造。取有限实数 a < b a<b a < b 、在 [ a , b ] [a,b] [ a , b ] 上连续且满足 w ( x ) > 0 w(x)>0 w ( x ) > 0 的权函数 w w w ,以及整数 n ≥ 1 n\ge1 n ≥ 1 。定义
I w ( f ) = ∫ a b f ( x ) w ( x ) d x , Q n ( f ) = ∑ i = 1 n A i f ( x i ) , E n ( f ) = I w ( f ) − Q n ( f ) . I_w(f)=\int_a^b f(x)w(x)\,dx,\qquad
Q_n(f)=\sum_{i=1}^n A_i f(x_i),\qquad
E_n(f)=I_w(f)-Q_n(f). I w ( f ) = ∫ a b f ( x ) w ( x ) d x , Q n ( f ) = i = 1 ∑ n A i f ( x i ) , E n ( f ) = I w ( f ) − Q n ( f ) .
节点 x i x_i x i 是首一 正交多项式的互异内部零点,其中
π n ( x ) = ∏ i = 1 n ( x − x i ) . \pi_n(x)=\prod_{i=1}^n(x-x_i). π n ( x ) = i = 1 ∏ n ( x − x i ) .
前面的构造保证该公式对次数不超过 2 n − 1 2n-1 2 n − 1 的多项式精确,权数 A i A_i A i 为正,并且 ∑ i A i = I w ( 1 ) \sum\limits_i A_i=I_w(1) i ∑ A i = I w ( 1 ) 。这些是此 Gaussian 公式的性质,并非任意使用 n n n 个采样点的公式都具有的性质。以下公式均假设节点、权数和运算完全精确。
记 C 2 n [ a , b ] C^{2n}[a,b] C 2 n [ a , b ] 为直到 2 n 2n 2 n 阶的各阶导数都在闭区间上连续的函数类,其中端点处的值理解为从内部连续延拓得到的值。对所述区间上的连续函数 g g g ,记 ∥ g ∥ ∞ = max x ∈ [ a , b ] ∣ g ( x ) ∣ \|g\|_\infty=\max\limits_{x\in[a,b]}|g(x)| ∥ g ∥ ∞ = x ∈ [ a , b ] max ∣ g ( x ) ∣ ;这是在所有点上取的最大值,而非几乎处处的界。令
K n = ∫ a b π n ( x ) 2 w ( x ) d x > 0 , C n = K n ( 2 n ) ! . K_n=\int_a^b \pi_n(x)^2w(x)\,dx>0,\qquad
C_n=\frac{K_n}{(2n)!}. K n = ∫ a b π n ( x ) 2 w ( x ) d x > 0 , C n = ( 2 n )! K n .
这些常数取决于权函数和区间。改变权函数通常既会改变节点,也会改变 K n K_n K n 。
导数余项定理
定理 6.4.1
(具有明确光滑性条件的 Gaussian 余项)
在上述假设下,设 f ∈ C 2 n [ a , b ] f\in C^{2n}[a,b] f ∈ C 2 n [ a , b ] ,并令
m = min [ a , b ] f ( 2 n ) , M = max [ a , b ] f ( 2 n ) . m=\min_{[a,b]}f^{(2n)},\qquad M=\max_{[a,b]}f^{(2n)}. m = [ a , b ] min f ( 2 n ) , M = [ a , b ] max f ( 2 n ) . 则
m C n ≤ E n ( f ) ≤ M C n . mC_n\le E_n(f)\le MC_n. m C n ≤ E n ( f ) ≤ M C n . 因此存在一点 ξ ∈ [ a , b ] \xi\in[a,b] ξ ∈ [ a , b ] ,使得
E n ( f ) = C n f ( 2 n ) ( ξ ) , ∣ E n ( f ) ∣ ≤ C n ∥ f ( 2 n ) ∥ ∞ . E_n(f)=C_n f^{(2n)}(\xi),\qquad
|E_n(f)|\le C_n\|f^{(2n)}\|_\infty. E n ( f ) = C n f ( 2 n ) ( ξ ) , ∣ E n ( f ) ∣ ≤ C n ∥ f ( 2 n ) ∥ ∞ . 特别地,若 2 n 2n 2 n 阶导数非负,则 Q n ( f ) ≤ I w ( f ) Q_n(f)\le I_w(f) Q n ( f ) ≤ I w ( f ) ;若它非正,则不等式方向相反。
ξ \xi ξ 的存在性并未给出寻找它的方法。实际可用的数值保证来自对整个区间上导数的有效界。我们只声明 ξ ∈ [ a , b ] \xi\in[a,b] ξ ∈ [ a , b ] ,这已足够得到下面的结论;建立误差界不需要排除端点。
为什么要使用二重插值
普通插值用次数不超过 n − 1 n-1 n − 1 的多项式匹配 n n n 个函数值,其余项含有会变号的节点乘积 π n \pi_n π n 。这里改用次数不超过 2 n − 1 2n-1 2 n − 1 的多项式 H H H ,同时匹配函数值和一阶导数:
H ( x i ) = f ( x i ) , H ′ ( x i ) = f ′ ( x i ) , 1 ≤ i ≤ n . H(x_i)=f(x_i),\qquad H'(x_i)=f'(x_i),\qquad 1\le i\le n. H ( x i ) = f ( x i ) , H ′ ( x i ) = f ′ ( x i ) , 1 ≤ i ≤ n .
引理 6.4.2
(在 Gaussian 节点上的二重插值)
设 f ∈ C 2 n [ a , b ] f\in C^{2n}[a,b] f ∈ C 2 n [ a , b ] 。恰有一个 H ∈ P 2 n − 1 H\in\mathcal P_{2n-1} H ∈ P 2 n − 1 ,对 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n 满足 H ( x i ) = f ( x i ) H(x_i)=f(x_i) H ( x i ) = f ( x i ) 及 H ′ ( x i ) = f ′ ( x i ) H'(x_i)=f'(x_i) H ′ ( x i ) = f ′ ( x i ) 。对每个 x ∈ [ a , b ] x\in[a,b] x ∈ [ a , b ] ,存在一点 η x ∈ [ a , b ] \eta_x\in[a,b] η x ∈ [ a , b ] ,使
f ( x ) − H ( x ) = f ( 2 n ) ( η x ) ( 2 n ) ! π n ( x ) 2 . f(x)-H(x)=\frac{f^{(2n)}(\eta_x)}{(2n)!}\pi_n(x)^2. f ( x ) − H ( x ) = ( 2 n )! f ( 2 n ) ( η x ) π n ( x ) 2 .
这样的多项式存在且唯一。事实上,从 P 2 n − 1 \mathcal P_{2n-1} P 2 n − 1 中的多项式到这 2 n 2n 2 n 个数据的线性映射,其核只有零:核中的多项式可被每个 ( x − x i ) 2 (x-x_i)^2 ( x − x i ) 2 整除,因而可被它们次数为 2 n 2n 2 n 的乘积整除,所以只能是零。两个维数均为 2 n 2n 2 n 的向量空间之间的单射线性映射也是满射。这便证明了存在性,无须预先假设 H H H 的表达式。
逐点二重插值余项。 固定一个不是节点的 x ∈ [ a , b ] x\in[a,b] x ∈ [ a , b ] ,定义
c = f ( x ) − H ( x ) π n ( x ) 2 , g ( t ) = f ( t ) − H ( t ) − c π n ( t ) 2 . c=\frac{f(x)-H(x)}{\pi_n(x)^2},\qquad
g(t)=f(t)-H(t)-c\pi_n(t)^2. c = π n ( x ) 2 f ( x ) − H ( x ) , g ( t ) = f ( t ) − H ( t ) − c π n ( t ) 2 . 函数 g g g 在 x x x 处为零,并在每个 x i x_i x i 处有二重零点:g ( x i ) g(x_i) g ( x i ) 和 g ′ ( x i ) g'(x_i) g ′ ( x i ) 均为零。反复应用 Rolle 定理,便得到这些点中最小者与最大者之间的一点 η x \eta_x η x ,使得 g ( 2 n ) ( η x ) = 0 g^{(2n)}(\eta_x)=0 g ( 2 n ) ( η x ) = 0 。
这个步骤背后的零点计数如下。在 p p p 有重数至少为 r r r 的零点,是指 g ( p ) = g ′ ( p ) = ⋯ = g ( r − 1 ) ( p ) = 0 g(p)=g'(p)=\cdots=g^{(r-1)}(p)=0 g ( p ) = g ′ ( p ) = ⋯ = g ( r − 1 ) ( p ) = 0 。若函数在互异点的零点重数下界分别为 r 1 , … , r k r_1,\ldots,r_k r 1 , … , r k ,那么对于每个满足 r j ≥ 2 r_j\ge2 r j ≥ 2 的原零点,其导数在该点有重数至少为 r j − 1 r_j-1 r j − 1 的零点,并且在相邻两个零点之间的 k − 1 k-1 k − 1 个开区间内各至少有一个零点。因此,按重数计算的零点总数至多减少一。由 g g g 的 2 n + 1 2n+1 2 n + 1 个零点开始,重复此论证 2 n 2n 2 n 次,即得到所需的 g ( 2 n ) g^{(2n)} g ( 2 n ) 的零点。二重零点都在内部,额外的点 x x x 可以是端点;Rolle 定理可应用于这些点之间的闭区间。
由于 H ( 2 n ) = 0 H^{(2n)}=0 H ( 2 n ) = 0 ,且 π n 2 \pi_n^2 π n 2 是次数为 2 n 2n 2 n 的首一多项式,
0 = f ( 2 n ) ( η x ) − c ( 2 n ) ! , f ( x ) − H ( x ) = f ( 2 n ) ( η x ) ( 2 n ) ! π n ( x ) 2 . 0=f^{(2n)}(\eta_x)-c(2n)!,\qquad
f(x)-H(x)=\frac{f^{(2n)}(\eta_x)}{(2n)!}\pi_n(x)^2. 0 = f ( 2 n ) ( η x ) − c ( 2 n )! , f ( x ) − H ( x ) = ( 2 n )! f ( 2 n ) ( η x ) π n ( x ) 2 . 在节点处,所需的 f − H f-H f − H 上下界两边均为零,因此不必在那里选取 η x \eta_x η x 。
尽管证明使用 f ′ ( x i ) f'(x_i) f ′ ( x i ) ,求积算法仍只使用 f ( x i ) f(x_i) f ( x i ) ;插值多项式只是分析工具。由于 Q n ( H ) = Q n ( f ) Q_n(H)=Q_n(f) Q n ( H ) = Q n ( f ) ,且公式对 H H H 精确,
E n ( f ) = I w ( f − H ) . E_n(f)=I_w(f-H). E n ( f ) = I w ( f − H ) .
引理随即完成定理的证明。
点 η x \eta_x η x 可以随 x x x 改变。我们不能把积分中所有这些点直接替换为同一个点。实际上,由 m ≤ f ( 2 n ) ( η x ) ≤ M m\le f^{(2n)}(\eta_x)\le M m ≤ f ( 2 n ) ( η x ) ≤ M 和 π n ( x ) 2 ≥ 0 \pi_n(x)^2\ge0 π n ( x ) 2 ≥ 0 ,对每个 x ∈ [ a , b ] x\in[a,b] x ∈ [ a , b ] 都有
m ( 2 n ) ! π n ( x ) 2 ≤ f ( x ) − H ( x ) ≤ M ( 2 n ) ! π n ( x ) 2 . \frac{m}{(2n)!}\pi_n(x)^2
\le f(x)-H(x)
\le\frac{M}{(2n)!}\pi_n(x)^2. ( 2 n )! m π n ( x ) 2 ≤ f ( x ) − H ( x ) ≤ ( 2 n )! M π n ( x ) 2 . 乘以正权函数并积分,得到 m C n ≤ E n ( f ) ≤ M C n mC_n\le E_n(f)\le MC_n m C n ≤ E n ( f ) ≤ M C n 。由于 C n > 0 C_n>0 C n > 0 ,商 E n ( f ) / C n E_n(f)/C_n E n ( f ) / C n 介于连续函数 f ( 2 n ) f^{(2n)} f ( 2 n ) 的最小值与最大值之间。介值定理保证存在一点 ξ ∈ [ a , b ] \xi\in[a,b] ξ ∈ [ a , b ] ,使函数在该点取到这个商。最后一步证明了单点余项公式,而不需要将 η x \eta_x η x 选成关于 x x x 的可测或连续函数。
证明透视
节点多项式的平方在哪里起作用 三个假设分别用在三个地方。对至多 2 n − 1 2n-1 2 n − 1 次多项式的精确性只用了一次,就是用在 H H H 上。同时匹配导数与函数值,使插值多项式的次数由 n − 1 n-1 n − 1 提升到 2 n − 1 2n-1 2 n − 1 ,却不必增加样本,因为 Q n ( H ) = Q n ( f ) Q_n(H)=Q_n(f) Q n ( H ) = Q n ( f ) 只涉及函数值。权函数 w w w 为正,是在积分逐点夹逼式时用到;若权函数变号,两个不等式都会失效。f ( 2 n ) f^{(2n)} f ( 2 n ) 的连续性保证 m m m 与 M M M 存在,并在最后用于介值定理。
关键一步是余项带有 π n 2 \pi_n^2 π n 2 而非 π n \pi_n π n 。由于这个因子从不变号,即使 η x \eta_x η x 随 x x x 移动,未知值 f ( 2 n ) ( η x ) f^{(2n)}(\eta_x) f ( 2 n ) ( η x ) 仍可在积分号下被夹在 m m m 与 M M M 之间。若用普通插值,因子 π n \pi_n π n 在每个节点都变号,同样的夹逼就失败。即使略去最后的介值步骤,双边界 m C n ≤ E n ( f ) ≤ M C n mC_n\le E_n(f)\le MC_n m C n ≤ E n ( f ) ≤ M C n 依然成立,而数值保证所用的正是这个界。
对这个固定公式,导数界中的常数是最优的 。取 f = π n 2 / ( 2 n ) ! f=\pi_n^2/(2n)! f = π n 2 / ( 2 n )! 。其 2 n 2n 2 n 阶导数恒等于一,求积值为零,积分值为 C n C_n C n 。因此,对整个函数类一致成立的界中,乘在 ∥ f ( 2 n ) ∥ ∞ \|f^{(2n)}\|_\infty ∥ f ( 2 n ) ∥ ∞ 前面的常数不能再减小。
概念视角 结构
归一化会改变常数 如果将正交多项式写为 p n = κ n π n p_n=\kappa_n\pi_n p n = κ n π n ,其中首项系数 κ n ≠ 0 \kappa_n\ne0 κ n = 0 ,其零点不变,但平方范数变为 κ n 2 K n \kappa_n^2K_n κ n 2 K n 。因此误差常数是
C n = 1 ( 2 n ) ! κ n 2 ∫ a b p n ( x ) 2 w ( x ) d x . C_n=\frac{1}{(2n)!\kappa_n^2}\int_a^b p_n(x)^2w(x)\,dx. C n = ( 2 n )! κ n 2 1 ∫ a b p n ( x ) 2 w ( x ) d x . 除非多项式是首一的,否则漏掉 κ n 2 \kappa_n^2 κ n 2 就会得到错误常数。例如 P 2 ( x ) = ( 3 x 2 − 1 ) / 2 P_2(x)=(3x^2-1)/2 P 2 ( x ) = ( 3 x 2 − 1 ) /2 与 π 2 ( x ) = x 2 − 1 / 3 \pi_2(x)=x^2-1/3 π 2 ( x ) = x 2 − 1/3 的节点相同,范数却不同。
双节点公式的精确计算
在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上取 w = 1 w=1 w = 1 ,双节点公式为
Q 2 ( f ) = f ( − 1 / 3 ) + f ( 1 / 3 ) , π 2 ( x ) = x 2 − 1 3 . Q_2(f)=f(-1/\sqrt3)+f(1/\sqrt3),\qquad
\pi_2(x)=x^2-\frac13. Q 2 ( f ) = f ( − 1/ 3 ) + f ( 1/ 3 ) , π 2 ( x ) = x 2 − 3 1 . 直接积分得到
K 2 = ∫ − 1 1 ( x 2 − 1 3 ) 2 d x = 2 5 − 4 9 + 2 9 = 8 45 , C 2 = 8 / 45 24 = 1 135 . K_2=\int_{-1}^1\left(x^2-\frac13\right)^2dx
=\frac25-\frac49+\frac29=\frac8{45},\qquad
C_2=\frac{8/45}{24}=\frac1{135}. K 2 = ∫ − 1 1 ( x 2 − 3 1 ) 2 d x = 5 2 − 9 4 + 9 2 = 45 8 , C 2 = 24 8/45 = 135 1 . 取 f ( x ) = x 6 f(x)=x^6 f ( x ) = x 6 。其积分值与求积值分别为 2 / 7 2/7 2/7 和 2 / 27 2/27 2/27 ,因此
E 2 ( f ) = 2 7 − 2 27 = 40 189 . E_2(f)=\frac27-\frac2{27}=\frac{40}{189}. E 2 ( f ) = 7 2 − 27 2 = 189 40 . 由于 f ( 4 ) ( x ) = 360 x 2 f^{(4)}(x)=360x^2 f ( 4 ) ( x ) = 360 x 2 ,一般误差界给出 0 ≤ E 2 ( f ) ≤ 360 / 135 = 8 / 3 0\le E_2(f)\le360/135=8/3 0 ≤ E 2 ( f ) ≤ 360/135 = 8/3 。这个界有效,但比实际误差大得多。单点公式与精确结果一致:
40 189 = 360 ξ 2 135 ⟺ ξ 2 = 5 63 . \frac{40}{189}=\frac{360\xi^2}{135}
\quad\Longleftrightarrow\quad \xi^2=\frac5{63}. 189 40 = 135 360 ξ 2 ⟺ ξ 2 = 63 5 . 有两个点的平方等于这个值;定理从未声称余项点唯一。如果自行代入中点 ξ = 0 \xi=0 ξ = 0 ,便会错误地预测误差为零。知道某个点存在,并不允许我们随意选一个方便的点。
例题 6.4.4
(e x e^x e x 的误差符号与大小保证)
对于同一区间上的 f ( x ) = e x f(x)=e^x f ( x ) = e x ,有 e − 1 ≤ f ( 4 ) ( x ) ≤ e e^{-1}\le f^{(4)}(x)\le e e − 1 ≤ f ( 4 ) ( x ) ≤ e ,所以
e − 1 135 ≤ ∫ − 1 1 e x d x − Q 2 ( e x ) ≤ e 135 . \frac{e^{-1}}{135}\le
\int_{-1}^1e^x\,dx-Q_2(e^x)
\le\frac e{135}. 135 e − 1 ≤ ∫ − 1 1 e x d x − Q 2 ( e x ) ≤ 135 e . 这既证实误差的方向,也给出上界。计算精确表达式 e − e − 1 − 2 cosh ( 1 / 3 ) e-e^{-1}-2\cosh(1/\sqrt3) e − e − 1 − 2 cosh ( 1/ 3 ) ,则是检验这个具体例子的另一种方法。
数值上,e − e − 1 ≈ 2.350402 e-e^{-1}\approx2.350402 e − e − 1 ≈ 2.350402 ,2 cosh ( 1 / 3 ) ≈ 2.342696 2\cosh(1/\sqrt3)\approx2.342696 2 cosh ( 1/ 3 ) ≈ 2.342696 ,所以误差约为 0.007706 0.007706 0.007706 。它落在 e − 1 / 135 ≈ 0.002725 e^{-1}/135\approx0.002725 e − 1 /135 ≈ 0.002725 与 e / 135 ≈ 0.020135 e/135\approx0.020135 e /135 ≈ 0.020135 之间,与保证相符;余项公式则由 e ξ = 135 ⋅ 0.007706 ≈ 1.040 e^\xi=135\cdot0.007706\approx1.040 e ξ = 135 ⋅ 0.007706 ≈ 1.040 满足,即 ξ ≈ 0.040 \xi\approx0.040 ξ ≈ 0.040 。
区间缩放与复合双节点公式
现在考虑在宽度为 h = v − u > 0 h=v-u>0 h = v − u > 0 、中点为 c = ( u + v ) / 2 c=(u+v)/2 c = ( u + v ) /2 的小区间 [ u , v ] [u,v] [ u , v ] 上,对无权函数积分。令 x = c + ( h / 2 ) t x=c+(h/2)t x = c + ( h /2 ) t 和 F ( t ) = f ( c + ( h / 2 ) t ) F(t)=f(c+(h/2)t) F ( t ) = f ( c + ( h /2 ) t ) 。变换后的双节点公式为
G [ u , v ] ( f ) = h 2 [ f ( c − h 2 3 ) + f ( c + h 2 3 ) ] . G_{[u,v]}(f)=\frac h2\left[
f\!\left(c-\frac{h}{2\sqrt3}\right)+
f\!\left(c+\frac{h}{2\sqrt3}\right)\right]. G [ u , v ] ( f ) = 2 h [ f ( c − 2 3 h ) + f ( c + 2 3 h ) ] .
链式法则给出 F ( 4 ) ( t ) = ( h / 2 ) 4 f ( 4 ) ( c + ( h / 2 ) t ) F^{(4)}(t)=(h/2)^4 f^{(4)}(c+(h/2)t) F ( 4 ) ( t ) = ( h /2 ) 4 f ( 4 ) ( c + ( h /2 ) t ) 。Jacobian 又带来一个因子 h / 2 h/2 h /2 ,因此对 f ∈ C 4 [ u , v ] f\in C^4[u,v] f ∈ C 4 [ u , v ] ,
∫ u v f ( x ) d x − G [ u , v ] ( f ) = h 5 4320 f ( 4 ) ( ξ ) , ξ ∈ [ u , v ] . \int_u^v f(x)\,dx-G_{[u,v]}(f)
=\frac{h^5}{4320}f^{(4)}(\xi),\qquad \xi\in[u,v]. ∫ u v f ( x ) d x − G [ u , v ] ( f ) = 4320 h 5 f ( 4 ) ( ξ ) , ξ ∈ [ u , v ] .
单个小区间上的误差含五次幂:其中四次来自变换后函数的求导,另一次来自积分变量的变换。
将 [ a , b ] [a,b] [ a , b ] 分成 N N N 个宽度均为 h = ( b − a ) / N h=(b-a)/N h = ( b − a ) / N 的小区间,把各小区间的公式相加得到 G N ( f ) G_N(f) G N ( f ) 。对各绝对误差界求和,得到
∣ ∫ a b f ( x ) d x − G N ( f ) ∣ ≤ ( b − a ) h 4 4320 ∥ f ( 4 ) ∥ ∞ = ( b − a ) 5 4320 N 4 ∥ f ( 4 ) ∥ ∞ . \left|\int_a^b f(x)\,dx-G_N(f)\right|
\le \frac{(b-a)h^4}{4320}\|f^{(4)}\|_\infty
=\frac{(b-a)^5}{4320N^4}\|f^{(4)}\|_\infty. ∫ a b f ( x ) d x − G N ( f ) ≤ 4320 ( b − a ) h 4 ∥ f ( 4 ) ∥ ∞ = 4320 N 4 ( b − a ) 5 ∥ f ( 4 ) ∥ ∞ .
对固定区间上的固定 C 4 C^4 C 4 函数,这是一个使用 2 N 2N 2 N 个采样值的 O ( N − 4 ) O(N^{-4}) O ( N − 4 ) 界。幂次从五降到四,是因为共有 N N N 个小区间。这里并未声称整体误差是五阶,也未给出积分接近零时的相对误差估计。
例题 6.4.5
(x 4 x^4 x 4 的精确复合误差)
在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上取 f ( x ) = x 4 f(x)=x^4 f ( x ) = x 4 ,其四阶导数恒为 24 24 24 。每个局部误差公式都以这个相同的导数值精确成立,因此
∫ 0 1 x 4 d x − G N ( x 4 ) = 1 180 N 4 . \int_0^1x^4\,dx-G_N(x^4)=\frac{1}{180N^4}. ∫ 0 1 x 4 d x − G N ( x 4 ) = 180 N 4 1 . 只有一个小区间时,积分值为 1 / 5 1/5 1/5 ,公式给出 7 / 36 7/36 7/36 ,两者之差为 1 / 180 1/180 1/180 。分成两个小区间时误差为 1 / 2880 1/2880 1/2880 ,恰为单区间误差的十六分之一。
假设在何处起作用
反例模式
导数几乎处处为零并不足够 在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上取 f ( x ) = ∣ x ∣ f(x)=|x| f ( x ) = ∣ x ∣ 。在所有可按经典意义求四阶导数的非零点处,该导数均为零;但 f f f 在零点甚至不可微。双节点公式给出
I ( f ) = 1 , Q 2 ( f ) = 2 3 , E 2 ( f ) = 1 − 2 3 < 0. I(f)=1,\qquad Q_2(f)=\frac2{\sqrt3},\qquad
E_2(f)=1-\frac2{\sqrt3}<0. I ( f ) = 1 , Q 2 ( f ) = 3 2 , E 2 ( f ) = 1 − 3 2 < 0. 若把几乎处处的零导数值当作 ∥ f ( 4 ) ∥ ∞ \|f^{(4)}\|_\infty ∥ f ( 4 ) ∥ ∞ ,就会错误地预测结果精确;由于 f ∉ C 4 [ − 1 , 1 ] f\notin C^4[-1,1] f ∈ / C 4 [ − 1 , 1 ] ,定理根本不适用。反复应用 Rolle 定理的论证不能穿过这个尖点。把积分在零处分开可以解决这个例子:函数在每一半区间上都是线性的,所以双节点 Gaussian 公式在每一半上都精确。这个观察并未证明一般奇异被积函数的误差定理。
导数证书也不同于依据样本的误差估计。上面的 Gaussian 和式本身无法证明未采样导数的大小。若采样值 f ~ i \widetilde f_i f i 具有独立论证得到的界 ∣ f ~ i − f ( x i ) ∣ ≤ δ |\widetilde f_i-f(x_i)|\le\delta ∣ f i − f ( x i ) ∣ ≤ δ ,则权数的正性给出
∣ I w ( f ) − ∑ i A i f ~ i ∣ ≤ C n ∥ f ( 2 n ) ∥ ∞ + I w ( 1 ) δ . \left|I_w(f)-\sum_i A_i\widetilde f_i\right|
\le C_n\|f^{(2n)}\|_\infty+I_w(1)\delta. I w ( f ) − i ∑ A i f i ≤ C n ∥ f ( 2 n ) ∥ ∞ + I w ( 1 ) δ .
第一项是求积误差,第二项是采样不确定性。这个结论仍假设节点、权数和累加过程完全精确;它不能证明浮点实现的误差界。端点奇异性、无穷区间和有符号权函数都需要其他假设与论证。
在 [ u , v ] [u,v] [ u , v ] 上,映射后公式的误差是 F F F 的参考误差乘以 h 2 \tfrac h2 2 h ,而 F ( 4 ) = ( h / 2 ) 4 f ( 4 ) F^{(4)}=(h/2)^4f^{(4)} F ( 4 ) = ( h /2 ) 4 f ( 4 ) ,所以常数为 ( h / 2 ) 5 / 135 = h 5 / 4320 (h/2)^5/135=h^5/4320 ( h /2 ) 5 /135 = h 5 /4320 。若只保留链式法则的因子,就得 ( h / 2 ) 4 / 135 = h 4 / 2160 (h/2)^4/135=h^4/2160 ( h /2 ) 4 /135 = h 4 /2160 。对 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上的 x 4 x^4 x 4 ,这预测误差为 24 / 2160 = 1 / 90 24/2160=1/90 24/2160 = 1/90 ,是实际误差 1 / 180 1/180 1/180 的两倍。
每个小区间的误差与 h 5 h^5 h 5 成正比,但共有 N = ( b − a ) / h N=(b-a)/h N = ( b − a ) / h 个小区间,所以全区间的界与 h 4 h^4 h 4 成正比。声称全区间误差界为 ( b − a ) 5 ∥ f ( 4 ) ∥ ∞ / ( 4320 N 5 ) (b-a)^5\|f^{(4)}\|_\infty/(4320N^5) ( b − a ) 5 ∥ f ( 4 ) ∥ ∞ / ( 4320 N 5 ) 是错的:对 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上的 x 4 x^4 x 4 取 N = 2 N=2 N = 2 ,它给出 24 / ( 4320 ⋅ 32 ) = 1 / 5760 24/(4320\cdot32)=1/5760 24/ ( 4320 ⋅ 32 ) = 1/5760 ,实际误差却是 1 / 2880 1/2880 1/2880 。
练习
快速检查
(对 [ 0 , 1 ] [0,1] [ 0 , 1 ] 上 w = 1 w=1 w = 1 的单节点公式,由 π 1 ( x ) = x − 1 / 2 \pi_1(x)=x-1/2 π 1 ( x ) = x − 1/2 求 C 1 C_1 C 1 。将结果应用于 f ( x ) = x 2 f(x)=x^2 f ( x ) = x 2 ,判断误差是否达到该界。)
直接计算 K 1 K_1 K 1 ,再除以 2 ! 2! 2 ! 。
解答 · 答案 直接积分得 K 1 = ∫ 0 1 ( x − 1 / 2 ) 2 d x = 1 / 12 K_1=\int_0^1(x-1/2)^2dx=1/12 K 1 = ∫ 0 1 ( x − 1/2 ) 2 d x = 1/12 ,故 C 1 = K 1 / 2 = 1 / 24 C_1=K_1/2=1/24 C 1 = K 1 /2 = 1/24 。该公式是中点公式 Q 1 ( f ) = f ( 1 / 2 ) Q_1(f)=f(1/2) Q 1 ( f ) = f ( 1/2 ) 。对于 x 2 x^2 x 2 ,E 1 = 1 / 3 − 1 / 4 = 1 / 12 = C 1 ⋅ 2 E_1=1/3-1/4=1/12=C_1\cdot2 E 1 = 1/3 − 1/4 = 1/12 = C 1 ⋅ 2 。因为处处有 f ′ ′ = 2 f''=2 f ′′ = 2 ,导数误差界达到等号。
快速检查
(从 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 上的双节点计算出发,使用通常的 Legendre 多项式 P 2 = ( 3 x 2 − 1 ) / 2 P_2=(3x^2-1)/2 P 2 = ( 3 x 2 − 1 ) /2 求误差常数。解释其首项系数的作用。)
使用 C n = ∫ p n 2 w / ( ( 2 n ) ! κ n 2 ) C_n=\int p_n^2w/\bigl((2n)!\kappa_n^2\bigr) C n = ∫ p n 2 w / ( ( 2 n )! κ n 2 ) 。
解答 · 答案 首项系数为 κ 2 = 3 / 2 \kappa_2=3/2 κ 2 = 3/2 ,且 ∫ − 1 1 P 2 2 d x = ( 9 / 4 ) ( 8 / 45 ) = 2 / 5 \int_{-1}^1P_2^2dx=(9/4)(8/45)=2/5 ∫ − 1 1 P 2 2 d x = ( 9/4 ) ( 8/45 ) = 2/5 。因此 C 2 = ( 2 / 5 ) / ( 24 ⋅ 9 / 4 ) = 1 / 135 C_2=(2/5)/(24\cdot9/4)=1/135 C 2 = ( 2/5 ) / ( 24 ⋅ 9/4 ) = 1/135 ,与首一多项式的计算一致。若只用 ( 2 / 5 ) / 24 (2/5)/24 ( 2/5 ) /24 ,就漏除了 9 / 4 9/4 9/4 。
快速检查
(希望用复合双节点公式计算 ∫ 0 1 e x d x \int_0^1e^x\,dx ∫ 0 1 e x d x ,使绝对求积误差不超过 10 − 6 10^{-6} 1 0 − 6 。利用 e < 3 e<3 e < 3 给出充分的整数 N N N ,然后检查同一个保守误差界能否保证再少一个小区间也满足要求。)
复合误差界为 ( b − a ) 5 ∥ f ( 4 ) ∥ ∞ / ( 4320 N 4 ) (b-a)^5\|f^{(4)}\|_\infty/(4320N^4) ( b − a ) 5 ∥ f ( 4 ) ∥ ∞ / ( 4320 N 4 ) 。
解答 · 答案 由于 ∥ f ( 4 ) ∥ ∞ = e < 3 \|f^{(4)}\|_\infty=e<3 ∥ f ( 4 ) ∥ ∞ = e < 3 ,误差小于 3 / ( 4320 N 4 ) = 1 / ( 1440 N 4 ) 3/(4320N^4)=1/(1440N^4) 3/ ( 4320 N 4 ) = 1/ ( 1440 N 4 ) 。只需 N 4 ≥ 10 6 / 1440 = 6250 / 9 N^4\ge10^6/1440=6250/9 N 4 ≥ 1 0 6 /1440 = 6250/9 。当 N = 6 N=6 N = 6 时,6 4 = 1296 > 6250 / 9 6^4=1296>6250/9 6 4 = 1296 > 6250/9 ,所以六个小区间、十二个采样值足够。当 N = 5 N=5 N = 5 时,5 4 = 625 < 6250 / 9 5^4=625<6250/9 5 4 = 625 < 6250/9 ,这个选定的界不能保证五个小区间足够。即使用 e e e 本身,e / ( 4320 ⋅ 625 ) ≈ 1.007 × 10 − 6 e/(4320\cdot625)\approx1.007\times10^{-6} e / ( 4320 ⋅ 625 ) ≈ 1.007 × 1 0 − 6 仍超过容许值。这些界不能作出保证,并不证明五个小区间的实际误差一定超过容许值。
快速检查
(设 q q q 为任意次数不超过 2 n − 1 2n-1 2 n − 1 的多项式,且 f = q + α π n 2 f=q+\alpha\pi_n^2 f = q + α π n 2 ,其中 α \alpha α 为实数。求精确误差。解释为何仅凭采样值无法给出误差的上界,尽管所有这样的 f f f 都与 q q q 有相同的采样值。)
利用 P 2 n − 1 \mathcal P_{2n-1} P 2 n − 1 上的精确性及 π n ( x i ) = 0 \pi_n(x_i)=0 π n ( x i ) = 0 。
解答 · 答案 由精确性有 E n ( q ) = 0 E_n(q)=0 E n ( q ) = 0 和 Q n ( π n 2 ) = 0 Q_n(\pi_n^2)=0 Q n ( π n 2 ) = 0 ,因此 E n ( f ) = α K n E_n(f)=\alpha K_n E n ( f ) = α K n 。又有 f ( 2 n ) = α ( 2 n ) ! f^{(2n)}=\alpha(2n)! f ( 2 n ) = α ( 2 n )! ,恰好得到余项公式。在每个节点上,无论 α \alpha α 如何变化,f ( x i ) = q ( x i ) f(x_i)=q(x_i) f ( x i ) = q ( x i ) 都成立。令 ∣ α ∣ |\alpha| ∣ α ∣ 增大,采样值保持不变,而误差无界。导数界则通过限制 ∣ α ∣ ( 2 n ) ! |\alpha|(2n)! ∣ α ∣ ( 2 n )! 排除了这种自由度。