動機
當函數只能在選定的點求值時,插值用一個在這些點取相同值的多項式代替函數;數值積分則用有限個函數值的加權和近似積分。二者密切相關:對插值多項式積分便得到一個求積公式。這解釋了權重及其多項式精確度,但不能單憑節點上的吻合就保證高次多項式在節點之間也準確。
應區分三種誤差。插值誤差比較精確函數和穿過精確數據的多項式;求積截斷誤差比較精確積分和精確加權和;浮點捨入及測量數據誤差則會影響實際計算。下文的界在精確算術下成立,並要求列出的導數存在且有界,不能直接作為程式捨入誤差的證明。
定義
定義 7.1.1
(插值多項式與 Lagrange 基函數)
給定互異節點 x0,…,xn 和數值 y0,…,yn,插值多項式是滿足 p(xi)=yi、次數至多為 n 的多項式。令
ℓi(x)=0≤j≤nj=i∏xi−xjx−xj,p(x)=i=0∑nyiℓi(x).當 i=j 時 ℓi(xj)=1,否則為零;節點互異確保分母非零。若兩個次數至多為 n 的多項式插值相同數據,其差有 n+1 個互異零點,故恆為零。這同時說明上式給出的插值多項式存在且唯一。
對互異節點,定義 f[xi]=f(xi),並遞歸定義
f[xi,…,xj]=xj−xif[xi+1,…,xj]−f[xi,…,xj−1].同一插值多項式可以寫成
pn(x)=f[x0]+k=1∑nf[x0,…,xk]j=0∏k−1(x−xj).節點次序會改變係數,但不會改變最終多項式。新節點加入時可以保留前面的項,只需增加一個差商項。
Aitken–Neville 插值可直接計算某個目標點的值。令 Pi,i(x)=yi,對於 i<j 遞歸地設
Pi,j(x)=xj−xi(x−xi)Pi+1,j(x)−(x−xj)Pi,j−1(x).
兩個低階插值式在每個共同節點 xk 處都等於 yk,兩項權重之和為一;在另外兩個端點,適當的係數為零。歸納可知 Pi,j 的次數至多為 j−i,因此它插值第 i 至 j 個數據點,唯一性證明了遞推式。只需一個目標值時,三角陣列很方便;若需在很多點求值,可以考慮能反覆使用的表示。
計算 Neville 表
要把遞推式用於計算,需要清楚更新次序。固定目標 t,簡寫 Pi,j=Pi,j(t)。從數據 Pi,i=yi 出發,先計算所有 j−i=1 的項,再計算 j−i=2 的項,如此繼續,直至得到 P0,n。每個新項組合上一層的兩個結果。總共需要 n(n+1)/2 次更新,即一個目標點需 O(n2) 次算術運算,不計取得原始數據的開銷。換一個目標點便要重新計算表格。
設節點兩兩互異,陣列 A0,…,An 最初存放 y0,…,yn。對每個 k=1,…,n,按 i=0,1,…,n−k 遞增的次序更新:
Ai←xi+k−xi(t−xi)Ai+1−(t−xi+k)Ai.則第 k 層之後,每個 i≤n−k 的 Ai 都等於 Pi,i+k(t),最後的 A0 就是 P0,n(t),只需 n+1 個儲存位置。
第 1 層之前 Ai=Pi,i。設第 k 層之前,i≤n−k+1 的 Ai=Pi,i+k−1。本層此前的更新只改動下標小於 i 的元素,所以更新 Ai 之前,Ai=Pi,i+k−1、Ai+1=Pi+1,i+k。因此遞推式把 Pi,i+k 存入 Ai。對兩個下標歸納,最後的 A0 就是所求值。這裏假定精確算術與節點兩兩互異,故分母非零;這並非浮點誤差界的證明。
取節點 0,1,3,對應值 1,2,10,在 t=2 求值。第一層為
P0,1=1−0(2−0)2−(2−1)1=3,P1,2=3−1(2−1)10−(2−3)2=6.下一層得到 P0,2=[(2−0)6−(2−3)3]/(3−0)=5。事實上,數據位於 1+x2 上,它在 2 處的值為 5。單陣列算法中,依次保留的有效元素為 (1,2,10)、(3,6)、(5)。若第一層從右向左更新,舊值 A1=2 在供 A0 使用前已被 6 覆蓋,便得到 A0=11,最終錯誤結果為 23/3。
表格能告訴我們甚麼
差值 P0,k(t)−P0,k−1(t) 比較的是採用不同數據集的兩個插值多項式。加入節點後數值發生變化可以提醒我們注意,但這個差值並不是未知函數誤差的保證上界。例如所有 yi=0,而 f(x)=j=0∏n(x−xj),則表中每項均為零,但在節點之外 f(t)=0。要認證函數誤差,仍需下文餘項定理中的導數界等額外資訊。
即使計算完全精確,輸入數據的誤差也可能被放大。若 ∣δyi∣≤ε,由線性性及 Lagrange 公式可知
∣δp(t)∣≤εi=0∑n∣ℓi(t)∣.
上例在 t=2 的三個權重為 −1/3,1,1/3,故放大因子為 5/3;取與各權重同號、大小均為 ε 的擾動便達到上界。目標點雖在全部節點範圍內,仍有一個權重為負。這裏討論的是精確插值對數據的敏感度;表格計算的捨入誤差還需另行分析。因此,層間差值小或者目標點位於節點範圍內,都不能單獨保證準確。
快速檢查
(對節點 0,1,2 和數值 1,0,3,計算 t=3 時的 Neville 表。若每個數據都增加 0.1,結果如何變化?)
解答 · 答案
第一層為 P0,1=−2、P1,2=6;於是 P0,2=(3⋅6−1⋅(−2))/2=10。在 3 處的權重為 1,−3,3,總和為 1,所以精確算術下所有數據共同增加 0.1 時結果恰增加 0.1。這種共同平移並非最壞擾動:各數據獨立誤差均不超過 0.1 時,結果最多可改變 0.7。
求積公式的精確度
區間 [a,b] 上的求積公式 Q(f)=i∑wif(xi) 若對所有次數至多為 d 的多項式精確,並對至少一個 d+1 次多項式不精確,則稱其代數精確度為 d。這是代數性質;對一般函數建立誤差界還需要正則性和相應導數的估計。
定理/命題
設 x0,…,xn 為 [a,b] 中互異點,f∈Cn+1([a,b])。對任意非節點 x∈[a,b],在包含 x 及全部節點的最小區間的內部存在 ξ,使
f(x)−pn(x)=(n+1)!f(n+1)(ξ)j=0∏n(x−xj).在節點處誤差為零。因此若區間上 ∣f(n+1)∣≤M,誤差絕對值至多為 Mj∏∣x−xj∣/(n+1)!。
定理 7.1.7
(複合梯形與 Simpson 公式)
令 a<b,h=(b−a)/N,xj=a+jh。複合梯形公式為
TN=h[2f(x0)+f(xN)+j=1∑N−1f(xj)].若 f∈C2([a,b]) 且 ∣f′′∣≤M2,則
∫abf(x)dx−TN≤12(b−a)h2M2.當 N 為偶數時,複合 Simpson 公式為
SN=3hf(x0)+f(xN)+41≤j<Nj 為奇數∑f(xj)+22≤j<Nj 為偶數∑f(xj).若 f∈C4([a,b]) 且 ∣f(4)∣≤M4,則
∫abf(x)dx−SN≤180(b−a)h4M4.
這裏的階數指固定積分區間和導數界、逐步細化網格時的行為。h 減半分別使上述界變為原來的四分之一和十六分之一;某一次實際誤差不一定恰好按該比例變化。Simpson 公式雖由二次插值積分得到,對稱性卻使它對三次多項式也精確。
定理 7.1.8
(兩點 Gauss–Legendre 公式)
在 [−1,1] 上,
G2(f)=f(−1/3)+f(1/3)對所有次數至多為三的多項式精確。若 f∈C4([−1,1]),存在 ξ∈(−1,1) 使
∫−11f(t)dt−G2(f)=135f(4)(ξ).對 [a,b],換元 x=(a+b)/2+(b−a)t/2,並將求積結果乘以 (b−a)/2。若 f∈C4([a,b]),誤差為 (b−a)5f(4)(ξ)/4320,其中 ξ∈(a,b)。
證明思路
固定不等於任何節點的 x,令 ω(t)=j=0∏n(t−xj),再取 C=[f(x)−pn(x)]/ω(x),定義 F(t)=f(t)−pn(t)−Cω(t)。此函數在 n+1 個節點及 x 處均為零。反覆使用 Rolle 定理,在這些點的凸包內得到 F(n+1)(ξ)=0。由於 pn(n+1)=0,ω(n+1)=(n+1)!,便得餘項公式。ξ 可以隨目標點 x 改變,通常不能把所有目標點的 ξ 當作同一個數。
對於 Newton 形式,先由 Neville 遞推式歸納:P0,k 的 xk 係數等於 P1,k 和 P0,k−1 的最高次係數之差除以 xk−x0,因此等於 f[x0,…,xk]。從 P0,k 減去前 k 個節點的插值式,所得次數至多為 k 的多項式在這 k 點為零,故等於該最高次係數乘以 j<k∏(x−xj)。歸納得到 Newton 形式,再由唯一性與 Lagrange 形式相同。
在 [u,v] 上,對通過兩個端點的線性插值多項式積分得到梯形公式。插值餘項與 ∣(x−u)(x−v)∣=(x−u)(v−x) 給出局部誤差界 M2(v−u)3/12。對 N 個寬度為 h 的區間求和即得複合界,不需要假設局部誤差相互抵消。
對於中點為 m 的單個 Simpson 區間 [u,v],二次插值積分得到 (v−u)[f(u)+4f(m)+f(v)]/6。為了證明四階導數誤差,改用三次 Hermite 多項式 H:它在 u,m,v 匹配函數值,在 m 還匹配 f′。由於三個取樣值相同,f 與 H 的求積值相等;公式又能精確積分三次多項式 H,所以誤差等於 ∫uv(f−H)。廣義 Rolle 定理給出
f(x)−H(x)=4!f(4)(ξx)(x−u)(x−m)2(x−v).乘積在區間內非正,積分為 −(v−u)5/120。乘積符號固定且非正。連續函數 f(4) 的最大、最小值逐點控制商 (f−H)/[(x−u)(x−m)2(x−v)];以該乘積的負數作為非負權重積分,再用介值定理,便得到某個單獨的 ξ 表示積分誤差。這裏不需要所選 ξx 連續或可測:
∫uvf(x)dx−6v−u[f(u)+4f(m)+f(v)]=−2880(v−u)5f(4)(ξ).共有 N/2 個寬為 2h 的區間,局部誤差絕對值求和便得 (b−a)h4M4/180。這個估計需要四階導數;較不光滑的函數仍可能可近似,但此公式無法為其提供誤差證書。
證明透視
為甚麼中點要算兩次
通過 u,m,v 的二次插值,其餘項為 f′′′(ξ)(x−u)(x−m)(x−v)/6,核在 m 處變號,只能支持含三階導數的估計。加上條件 H′(m)=f′(m) 後,核變為 (x−u)(x−m)2(x−v),在區間上符號固定。這樣做之所以合理,有兩個事實。新增的三次項是 (x−u)(x−m)(x−v) 的倍數,它關於 m 為奇函數、積分為零,所以公式對 f 和 H 給出同一個數。而符號固定的核,正是讓 f(4) 的最大、最小值把積分誤差夾成單一的 f(4)(ξ) 的關鍵。若沒有這個二重根,變號就會堵住這一步,論證只能得到涉及 f′′′ 的較弱估計。
對於兩點 Gaussian 公式,先採用對稱形式:節點為 ±c,權重均為 w。奇次單項式的積分與求積值均為零。匹配常數和二次項得到 2w=2、2wc2=2/3,因而權重為一、節點為 ±1/3,所以至多三次均精確。誤差證明使用在兩節點同時匹配 f 和 f′ 的三次 Hermite 多項式 H。餘項中的因子 (t2−1/3)2≥0;求積公式對 H 和 f 的值相同,又對 H 精確。該因子的積分為 8/45,用同樣的最大最小值論證得到誤差 f(4)(ξ)(8/45)/4!=f(4)(ξ)/135。對 t4,誤差為 8/45=0,故代數精確度恰為三。允許調整節點及權重能提高每次求值的精確度,但不會消除近似或捨入誤差。
例題
節點 0,1,2 的值分別為 1,2,5。差商為 f[0,1]=1、f[1,2]=3、f[0,1,2]=1。Newton 形式給出
p2(x)=1+x+x(x−1)=1+x2.在 x=1/2 時值為 5/4。Neville 表中此目標點的第一層為 P0,1=3/2、P1,2=1/2,再遞推得 P0,2=5/4。由唯一性,Lagrange 公式給出同一多項式。雖然目標點位於全部節點範圍內,計算 P1,2 時相對於節點 1,2 是外插。
例題 7.1.10
(有誤差證書的 Simpson 計算)
令 f(x)=ex,積分區間為 [0,1],取 N=2、h=1/2。Simpson 公式給出
S2=61+4e1/2+e≈1.718861.因為 f(4)(x)=ex≤e,誤差至多為 e/2880≈0.000944。精確積分為 e−1≈1.718282,實際誤差約為 0.000579;界不是精確預測。此處 Simpson 值高於積分,與單區間公式中 ∫f−S2 為負一致。
例題 7.1.11
(將 Gauss 節點移到新區間)
對 [0,2] 上的 f(x)=x4,換元 x=1+t 得
G=(1−1/3)4+(1+1/3)4=956.精確積分為 32/5,所以 ∫02x4dx−G=8/45。對 (1+t)4 應用 [−1,1] 上的餘項,其四階導數為 24,也得到 24/135=8/45。此公式對三次多項式精確,但並非對所有四次多項式精確。
即使插值多項式唯一,節點之間的表現也可能很差。對 [−1,1] 上的 Runge 函數 f(x)=1/(1+25x2),等距節點的高次插值會在端點附近出現很大的振盪。改變節點或使用分段低次插值可能改善表現。餘項界展示了因子 j∏∣x−xj∣ 的影響,但高階導數界增長也會使估計失去資訊;僅在節點處誤差小不足以控制整個區間。
常見錯誤
無論節點之間的誤差多大,插值多項式在數據節點處的殘差都為零。應檢查光滑性、節點位置和餘項大小;對計算數據,還需考察結果對數據擾動的敏感性。若導數界未知或極大,形式上的誤差界就不能提供有效的數值證書。
Simpson 公式對三次多項式精確,並在 C4 條件下滿足四階導數誤差界。僅靠精確度不能推出一般函數的誤差常數。同樣,Gauss 公式的代數精確度是關於多項式的性質,不是所有光滑函數都被精確積分的保證。
總結
Lagrange、Newton 和 Neville 方法描述同一個唯一插值多項式。餘項定理將逼近誤差與導數及節點幾何聯繫起來。積分局部插值多項式產生 Newton–Cotes 公式;Gaussian 求積通過選取節點提高多項式精確度。誤差界需要相應正則性,且截斷誤差界與代數精確度均不能單獨量化浮點誤差。
練習
快速檢查
(對數據 (0,1),(1,0),(2,3) 寫出 Newton 插值形式,並計算 x=3 處的值。)
解答 · 答案
第一層差商為 −1 和 3,故 f[0,1,2]=2。於是 p(x)=1−x+2x(x−1)=2x2−3x+1,p(3)=10。
快速檢查
(對 [0,π] 上的 f(x)=sinx,求 N=10 的複合梯形誤差上界,並判斷近似值位於積分之上還是之下。)
估計 ∣f′′∣,並利用凹性。
解答 · 答案
h=π/10,且 ∣f′′∣=∣sinx∣≤1,所以 ∣I−T10∣≤π3/1200。sin 在此區間為凹函數,弦位於圖像之下,故 T10≤I=2。
快速檢查
(在 [−1,1] 上用兩點 Gauss 公式計算 f(t)=t4,並與精確積分比較。)
計算 t4 在 ±1/3 處的值。
解答 · 答案
求積值為 2(1/3)4=2/9,精確積分為 2/5。誤差 2/5−2/9=8/45,與 24/135 一致。
快速檢查
(在 [0,1] 上取 N=4 用 Simpson 公式,已知 ∣f(4)∣≤10。求絕對誤差界;若 N 加倍又如何?)
在 Simpson 誤差界中取 h=1/4。
解答 · 答案
h=1/4,誤差界為 10/(180⋅44)=1/4608。N 加倍使 h 減半,界變為原來的十六分之一,即 1/73728;實際誤差不一定恰好按此比例變化。
節點重用:梯形、中點與 Simpson 公式
在 N 個粗網格區間上的中點近似是 MN=hj=0∑N−1f(a+(j+21)h);TN 與 S2N 分別是上面定義的梯形和 Simpson 近似。
固定整數 N≥1、區間 [a,b](a<b)以及 h=(b−a)/N。把步長減半為 h/2,得到網格 a+kh/2,k=0,…,2N。偶數下標 k=2j 對應舊節點 a+jh;奇數下標 k=2j+1 對應中點 a+(j+21)h。在 T2N 的定義中把兩類節點分開,得
T2N=2h[2f(a)+f(b)+j=1∑N−1f(a+jh)]+2hj=0∑N−1f(a+(j+21)h)=2TN+MN.
在闊度為 h/2 的 2N 個子區間上,複合 Simpson 公式給端點權重 1、奇數節點權重 4、內部偶數節點權重 2,再整體乘以 h/6:
S2N=6h[f(a)+f(b)+2j=1∑N−1f(a+jh)+4j=0∑N−1f(a+(j+21)h)]=3TN+2MN.
代入 MN=2T2N−TN,即得 S2N=(4T2N−TN)/3。
這些都是代數恆等式。凡是能在網格節點上求值的函數,它們都成立。它們不涉及收斂性或光滑性。
計算上的意義。 先保存 TN 已用過的 N+1 個函數值。加密時只需新計算 N 個中點值來構成 MN,隨後 T2N 與 S2N 便可直接得到,無需重複求值。在浮點運算中,這些恆等式只在捨入誤差範圍內成立;捨入是另一個獨立的問題。
例。 取 [0,1] 上的 f(x)=x2,N=1。則 T1=21,M1=41,T2=83,S2=31。
快速檢查
(取 [0,1] 上的 f(x)=x3,N=1。驗證 T1=21,M1=81,T2=165,S2=41。)
先求 f 在 0、1/2、1 處的值。
解答 · 答案
節點值為 f(0)=0、f(1/2)=1/8、f(1)=1。代入得 T1=1/2、M1=1/8;再由恆等式得 T2=5/16、S2=1/4。
反例模式
估計值一致不能保證準確
兩個估計值相等,並不能證明結果準確。設 [0,1] 上 f(x)=x2(1−x)2(x−21)2。它在 0,21,1 處為零,所以 T1=M1=T2=S2=0。但令 u=x−21 可算得 ∫01f=8401>0。取樣值無法反映節點之間的行為。單一例子亦不能證明收斂。若要說 (4T2N−TN)/3 能減小誤差,必須對 f 另加正則性假設;恆等式本身並不提供這一點。
Newton–Cotes 公式:權重從哪裏來
梯形和 Simpson 公式屬於一個更大的族。Newton–Cotes 公式積分通過等距節點的插值多項式。閉型公式包含兩個端點,開型公式的節點則嚴格位於區間內部。端點值無法取得時,後者可能有用;但僅憑這一點,不能保證它在端點奇異附近的精度。
設 a<b 且 n≥1 為整數。對閉型公式,令 h=(b−a)/n、xi=a+ih(i=0,…,n)。若 ℓi 是這些節點的 Lagrange 基函數,定義
wi=∫abℓi(x)dx,Qn(f)=i=0∑nwif(xi).
於是 Qn(f)=∫abpn(x)dx。次數不超過 n 的多項式等於自己的插值多項式,因此該公式對它們精確。開型公式的構造相同,但使用 n+1 個內部節點 xi=a+(i+1)(b−a)/(n+2),i=0,…,n。中點公式是開型的 n=0 情形;梯形公式和單區間 Simpson 公式分別是閉型的 n=1 和 n=2 情形。
為甚麼 Simpson 公式對三次多項式也精確?兩類節點都關於 m=(a+b)/2 對稱。反射會交換對應的 Lagrange 基函數,因此 wi=wn−i。當 n 為偶數時,中心化單項式 (x−m)n+1 是奇函數,其積分和求積和都為零。每個次數不超過 n+1 的多項式都可寫成此單項式的倍數加上一個次數不超過 n 的多項式。所以兩類公式在 n 為偶數時的精確度至少為 n+1。這個對稱性論證使用精確算術,並不是任意函數的誤差界。
取四個節點 0,1,2,3。積分它們的 Lagrange 基函數得到權重 3/8,9/8,9/8,3/8。例如,
ℓ0(t)=−6(t−1)(t−2)(t−3),∫03ℓ0(t)dt=83.反射後的另一端點具有相同權重。兩個內部權重也由對稱性相等;又因為所有權重之和為 3,它們各為 9/8。作變量代換 x=a+ht,其中 0≤t≤3、h=(b−a)/3,便得到
Q(f)=83h[f(a)+3f(a+h)+3f(a+2h)+f(b)].由插值可知,它對次數至多為三的多項式精確。但對 [0,3] 上的 f(x)=x4,公式給出 99/2,積分則為 243/5;帶符號誤差 ∫f−Q(f)=−9/10。因此它的精確度恰為三。這個例子也說明,對低次多項式精確並不等於對每個光滑函數精確。
快速檢查
(在 [0,3] 上用兩個節點 1,2 構造開型公式。將它用於 f(x)=x2,並與積分比較。)
在 [0,3] 上積分每個 Lagrange 基函數。
解答 · 答案
基函數是 ℓ0(x)=2−x、ℓ1(x)=x−1。兩者的積分均為 3/2,故 Q(f)=23[f(1)+f(2)]=15/2。積分為 9,帶符號誤差為 3/2。該公式對常數和一次函數精確,但此例表明它並非對所有二次函數精確。