同時選取節點與權重
求積公式以函數值的加權和取代積分。當節點預先固定時,若要匹配更多冪次,可用的權重終會用盡。高斯(Gauss)求積連節點也一併選取。對於有限區間上的正權重,n 個經仔細選取的節點能夠精確積分所有次數至多為 2n−1 的多項式。這額外的精確度並非魔術:它源自一個與所有較低次多項式正交的多項式之根。
設 a<b,並設 w 在 [a,b] 上連續且嚴格為正。寫
I(f)=∫abf(x)w(x)dx,Qn(f)=i=1∑nλif(xi).
權重函數 w 屬於積分的一部分,而數字 λi 則是求積權重。我們要求的精確度是針對多項式而言,因此需要為它命名。
若對每個次數至多為 d 的多項式 p 皆有 Qn(p)=I(p),則稱法則 Qn 精確至 d 次。
正交多項式及其根
在實多項式上定義 ⟨p,q⟩=I(pq)。w 的正性使它成為內積。對 1,x,…,xn 施行 Gram–Schmidt 正交化,再把最後一個多項式縮放為首一多項式,便得到下面定義的多項式。
權重 w 在 [a,b] 上的首一正交多項式 pn,是唯一滿足下述條件的首一 n 次多項式:對每個次數小於 n 的多項式 q 皆有 ⟨pn,q⟩=I(pnq)=0。
多項式 pn 在 (a,b) 內有 n 個相異的實根。
設 r1,…,rk 為 (a,b) 內 pn 變號處的相異根,並令 q(x)=j=1∏k(x−rj);若 k=0,則 q=1。在非零點處,pnq 於整個 (a,b) 上符號不變:pn 的每次變號都被 q 中對應的因子抵消。該乘積並非恆為零,故嚴格為正的權重使 I(pnq)=0。然而,若 k<n,則 degq<n,由正交性得 I(pnq)=0,矛盾。因此 k≥n;而 n 次多項式至多有 n 個根,故這 n 個根全部相異且位於區間內部。
構造求積公式
設 x1,…,xn 為這些根,ℓi 為滿足 ℓi(xj)=δij 的 Lagrange 基底多項式。令 λi=I(ℓi)。這已使法則對次數至多為 n−1 的多項式精確,因為它們的 Lagrange 插值多項式就是其本身。
以上述方式定義節點與權重後,Qn 對每個次數至多為 2n−1 的多項式皆精確。每個 λi 皆為正,而且任何使用這 n 個相異節點的法則都不可能對所有 2n 次多項式精確。
以 pn 除任何次數至多為 2n−1 的多項式 p:
p=spn+r,degs≤n−1,degr≤n−1.正交性給出 I(spn)=0。在每個節點處 pn(xi)=0,故 Qn(p)=Qn(r)=I(r)=I(p)。關於正性,ℓi2 的次數為 2n−2,故剛證得的精確度給出
λi=Qn(ℓi2)=I(ℓi2)>0.最後,Qn(pn2)=0,但 I(pn2)>0。由於 pn2 的次數為 2n,精確度不能延伸至該次數的每個多項式。更一般地,同一個平方乘積論證排除了任何基於區間內 n 個實節點的法則達到 2n 次精確的可能,不論其權重為何。
證明透視
為何除法能解鎖兩倍的次數
餘式 r 可藉插值被精確積分。商項 spn 在所有節點處皆為零,而正交性亦使其積分為零。這兩個「零」是不同的事實:一個關乎取樣,另一個關乎積分。兩者合起來便能處理至 2n−1 的次數。
界限 2n−1 只在一處出現:以 pn 除次數至多為 2n−1 的多項式,所得商式 s 的次數至多為 n−1,s 才屬於 pn 與之正交的那一類多項式。在 2n 次時,商式的次數可以是 n(例如 s=pn 本身),正交性便不再適用;這正是證明末尾所用的多項式 pn2。w 的正性被用了兩次:一次是把根放進 (a,b) 內,另一次是使 I(ℓi2) 與 I(pn2) 嚴格為正。
例題
取 [−1,1] 上的 w=1。與 1 和 x 正交的首一二次多項式 p2=x2+Ax+B 滿足
32+2B=0,32A=0.因此 p2=x2−1/3,而 x±=±1/3。由對稱性及對常數的精確度得 λ+=λ−=1。對於 f(x)=x4,該法則給出 Q2(f)=2/9,而 I(f)=2/5;誤差為 I(f)−Q2(f)=8/45。至三次的精確度並不包括四次。
在任意區間 [a,b] 上取單位權重時,仿射變換 x=(a+b)/2+(b−a)t/2 把兩個節點轉換為 (a+b)/2±(b−a)/(23),並把每個權重乘以 (b−a)/2。導數與誤差常數也隨此變換而縮放;若把 [−1,1] 上的常數原封不動地照搬,將會出錯。
例如在 [0,2] 上,令 h=1/3。節點為 1±h,兩個權重皆為 1。對 f(x)=x3,
(1+h)3+(1−h)3=2+6h2=2+2=4=∫02x3dx,故搬移後的法則對三次多項式仍然精確。
例題 7.2.7
(三個節點,以及六次時的首次失效)
取 [−1,1] 上的 w=1,記 p3=x3+Ax2+Bx+C。與 1 及 x2 正交的條件只涉及偶被積函數,由奇偶性迫使 A=C=0;與 x 正交則給出
∫−11(x4+Bx2)dx=52+32B=0,B=−53.因此 p3=x(x2−3/5),節點為 0,±3/5。對 1 與 x2 精確給出 λ0+2λ1=2 及 2λ1⋅53=32,故 λ1=5/9、λ0=8/9。檢驗:x4 被精確積分,2⋅95⋅259=52;奇次冪則由對稱性相消。六次是首個失效的次數:Q3(x6)=2⋅95⋅12527=256,而 I(x6)=72,誤差為 72−256=1758。
反例模式
多項式精確度不等於普遍精確度
對於任何給定的節點,非負多項式 i=1∏n(x−xi)2 在每個取樣點上皆為零。無論有限個權重如何取值,求積結果都是零,但它對 w 的積分卻為正。例如在 [−1,1] 上取 w=1 的兩節點法則,該多項式為 (x2−1/3)2:它在 ±1/3 處為零,故 Q2 給出 0,但 ∫−11(x4−32x2+91)dx=52−94+92=458=0。因此,有限個取樣點不可能精確積分每個光滑函數。多項式精確度是針對指定有限維函數類的精確保證,而非普遍適用的誤差界。
常見錯誤
對主要定理有兩種常見的誤讀。
n 個高斯節點的法則精確至 2n−1 次。上面的兩節點法則能精確積分 x3,卻在 x4 上差了 8/45,所以「n 個節點、2n 次」是差一的錯誤。
正的求積權重可避免權重之間互相抵消,但不保證對每個函數的誤差都很小,也不保證不受浮點誤差影響。被積函數的光滑性與性質、節點的數值計算以及條件數仍然重要。高精確度是一種結構性質,而非完整的穩定性分析。
練習與解答
快速檢查
(取一個節點,並在 [−1,1] 上取 w=1,構造高斯法則並說明其精確度的次數。)
解答 · 答案
與常數正交的首一一次多項式為 p1=x,故節點為零,其權重為 2。該法則精確至一次,但對 x2 不精確。
快速檢查
(利用 [−1,1] 上的兩節點法則近似計算 ∫−11(x3+2x2+1)dx。)
解答 · 答案
該多項式為三次,故結果精確:0+2(2/3)+2=10/3。
快速檢查
(解釋當 w>0 時,為何一個對常數精確的法則,其權重中至少有一個必為正。)
解答 · 答案
對常數函數的精確度給出 i∑λi=I(1)>0,故不可能所有權重皆非正。
快速檢查
(一個帶有任意符號權重的 n 節點法則,可否對所有 2n 次多項式精確?請解釋。)
解答 · 答案
不可以。平方式 i∏(x−xi)2 非負、次數為 2n,且在所有節點處為零,但其積分為正。此論證並不假設權重為正。