從多項式精確性走向誤差界
一個有 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 的零點,並在相鄰兩點之間的每個開區間內至少有一個零點。因此,按重數計算的零點總數每求一次導數最多減少一。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 。
證明透視
節點多項式的平方在哪裏起作用 三個假設分別用在三個地方。對至多 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 。
區間縮放與複合雙節點公式
現在考慮小區間 [ u , v ] [u,v] [ u , v ] 上的無權積分。記寬度為 h = v − u > 0 h=v-u>0 h = v − u > 0 ,中點為 c = ( u + v ) / 2 c=(u+v)/2 c = ( u + v ) /2 。令 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 ∣ 。在每個非零點按通常微分定義計算,四階導數都是零;然而函數在零點甚至不可微。雙節點公式給出
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 )! ,恰好恢復餘項公式。在每個節點,f ( x i ) = q ( x i ) f(x_i)=q(x_i) f ( x i ) = q ( x i ) ,與 α \alpha α 無關。增大 ∣ α ∣ |\alpha| ∣ α ∣ 不會改變樣本,卻能令誤差任意大。導數上界透過限制 ∣ α ∣ ( 2 n ) ! |\alpha|(2n)! ∣ α ∣ ( 2 n )! ,排除了這種自由度。