為甚麼要對插值多項式微分?
有限差分公式用附近的一小組數值估計導數。多項式譜方法採用另一條路:先找出一個通過全部數值的多項式,再對這個多項式作精確微分,最後在原來的節點計算導數。所得公式仍然是用一個矩陣乘以數值向量。矩陣通常是稠密的,因為每個插值基底多項式都依賴整個網格。
「精確微分」必須說清楚微分的對象。在精確算術下,我們精確地微分插值多項式。其導數未必等於提供樣本的原函數的導數。未被網格分辨的振盪、高次多項式,甚至很小的測量誤差,都可能令看來準確的函數值產生差異很大的導數。我們先證明代數結論,再指出哪些額外假設足以支持導數逼近。
本節的數據和函數均取實值,先在 [−1,1] 上討論。以 Pn 表示次數至多為 n 的多項式空間。上一節使用 n 個內部高斯(Gauss)節點,插值多項式屬於 Pn−1。本節的 n 則表示次數上限:共有 n+1 個洛巴托(Lobatto)節點,包括兩個端點。這兩種網格及其係數公式不能混用。
網格、插值多項式與矩陣定義
固定整數 n≥1,設
θj=njπ,xj=cosθj,j=0,…,n.因此 x0=1>x1>⋯>xn=−1。給定向量 v=(v0,…,vn)T,以 pv∈Pn 表示唯一滿足 pv(xj)=vj 的插值多項式。令 ℓj 為滿足 ℓj(xi)=δij 的基底多項式,則 pv=j=0∑nvjℓj。定義
Dij=ℓj′(xi),0≤i,j≤n.
餘弦在 [0,π] 上嚴格遞減,所以節點互異。拉格朗日(Lagrange)公式給出插值多項式的存在性;非零的 Pn 多項式不可能有 n+1 個互異零點,故插值唯一。因此,對每個數值向量,D 的定義都有意義,不必預先假定向量來自光滑函數。
尚未計算任何矩陣元素,線性性已經給出核心等式:
(Dv)i=j=0∑nℓj′(xi)vj=pv′(xi).
接下來要將定義化成明確的元素公式,尤其是對角元素。分母的正負將由上述節點遞減的次序決定。
推導非對角元素
回顧 Tk(cosθ)=cos(kθ)。當 0<θ<π,微分得
Tn′(cosθ)=nsinθsin(nθ).
所以 Tn′ 在內部節點 x1,…,xn−1 為零。取極限得到端點值
Tn′(1)=n2,Tn′(−1)=(−1)n−1n2.
這些結論在 n=1 時仍然成立,只是此時沒有內部節點。因此可選擇以下節點多項式:
W(x)=(x2−1)Tn′(x).
它的次數是 n+1,零點恰好是 n+1 個互異節點 xj。確實,Tn′ 的次數是 n−1,所列的 n−1 個互異內部零點已是其全部零點,且都是單零點;又有 Tn′(±1)=0,所以端點因子補上其餘兩個單零點。首項係數並不重要:將 W 乘以非零常數,不會改變以下基底公式:
ℓj(x)=(x−xj)W′(xj)W(x).
在 xj 看似存在的奇點可以消去。用 x−xj 除 W 得到多項式,其在 xj 的值正是 W′(xj)。
為計算節點處的 W′,先推導切比雪夫(Chebyshev)微分方程。對 Tn(cosθ)=cos(nθ) 兩次使用鏈式法則,得到
(1−x2)Tn′′(x)−xTn′(x)+n2Tn(x)=0.(1)
起初這個等式在 −1<x<1 成立。兩邊都是多項式,故它其實處處成立。在內部節點,Tn′(xj)=0,式 (1) 給出
W′(xj)=(xj2−1)Tn′′(xj)=n2Tn(xj)=n2(−1)j.
在端點,改用 W′(x)=2xTn′(x)+(x2−1)Tn′′(x),得到 W′(1)=2n2 及 W′(−1)=2(−1)nn2。定義 c0=cn=2,而 1≤j≤n−1 時 cj=1,便可合寫為
W′(xj)=n2cj(−1)j.(2)
當 i=j,微分基底公式並利用 W(xi)=0,即得
Dij=(xi−xj)W′(xj)W′(xi)=cjcixi−xj(−1)i+j.(3)
等價地,重心插值權重可取為 λj=(−1)j/cj 的共同非零倍數,式 (3) 就是 Dij=λj/[λi(xi−xj)]。
式 (3) 中的因子是 ci/cj,即比值 λj/λi,不是其倒數。寫成 cj/ci 只會改變端點所在的行或列的元素,因此不易察覺。對 n=2,這會給出 D01=−1/2 而非 −2,第 0 行之和變成 3/2−1/2+1/2=3/2。下面證明的恆等式 D1=0 立即揭示錯誤:正確矩陣的每一行之和都是零。
對角元素與端點的符號
在單零點 xi 附近,對基底公式作泰勒(Taylor)展開得
ℓi(x)=1+2W′(xi)W′′(xi)(x−xi)+⋯,Dii=2W′(xi)W′′(xi).(4)
對內部節點,先將式 (1) 微分:
(1−x2)Tn′′′−3xTn′′+(n2−1)Tn′=0.(5)
由 W′′=2Tn′+4xTn′′+(x2−1)Tn′′′、式 (5) 及 Tn′(xi)=0,得到 W′′(xi)=xiTn′′(xi)。將它和 W′(xi)=(xi2−1)Tn′′(xi) 代入式 (4),便有 Dii=−xi/[2(1−xi2)]。這裏可以除以 Tn′′(xi):式 (2) 說明 W′(xi)=0,而 xi2−1=0。
對 x0=1,將 1 代入式 (5) 得
Tn′′(1)=3n2(n2−1).
所以 W′′(1)=2n2+4n2(n2−1)/3。將它和 W′(1)=2n2 代入式 (4),得到 D00=(2n2+1)/6。反射對稱性則給出 xn=−1 處相反的符號。確實,由基底的唯一性,ℓn(x)=ℓ0(−x),故 ℓn′(−1)=−ℓ0′(1)。
對 n≥1 及網格 xj=cos(jπ/n),由基底微分定義的矩陣,其非對角元素由式 (3) 給出,對角元素為
D00=62n2+1,Dnn=−62n2+1,Dii=−2(1−xi2)xi(1≤i≤n−1).(6)此矩陣滿足 D1=0。對每個 q∈Pn,
D(q(x0),…,q(xn))T=(q′(x0),…,q′(xn))T.(7)
式 (3)–(6) 已由定義中的基底多項式推得。若向量是 q∈Pn 的樣本,唯一性說明其插值多項式就是 q;微分這個多項式恆等式便證明式 (7)。取 q=1 得 D1=0。特別地,對角元素也可由下式計算:
Dii=−j=i∑Dij(8)這是恆等式,不是另一個近似公式。
證明透視
精確插值為何能推出精確微分?
證明只有一步關鍵:把關於 n+1 個數的陳述換成多項式恆等式。假設 q∈Pn 只用了一次,就是用唯一性把樣本的插值多項式認定為 q 本身。此後兩者的導數處處相同,在節點上自然相同;式 (7) 只是把核心等式 (Dv)i=pv′(xi) 用於這個 v。行和恆等式是 q=1 的特例,無須另行計算。去掉這個假設,認定便告失效:在 n+1 個點相等不能推出兩個函數恆等,有限個等式也不能微分。在 n=2 的網格上,x3 與 x 的樣本相同,端點導數卻不同。餘下的結論只是:D 給出插值多項式的導數。
最小的網格已能檢驗式 (3) 和 (6) 中的每個符號。
當 n=1,沒有內部節點,且 c0=c1=2。在節點 (1,−1) 上,式 (3) 和 (6) 給出
D=21(11−1−1).每一行之和為零,符合 D1=0。q(x)=x 的樣本是 (1,−1)T,而 D(1,−1)T=(1,1)T 與兩個節點處的 q′=1 一致。由於 1 和 x 生成 P1,這兩項檢查已在此網格上完整驗證式 (7)。
若節點按遞增次序儲存,須同時反轉矩陣的行和列:新矩陣為 PDP−1,其中 P 是反序排列矩陣。這裏不會多出負號,因為仍然是對 x 微分。對 n=1,遞增節點 (−1,1) 給出 PDP−1=21(−1−111),它把 x 的樣本 (−1,1)T 映到 (1,1)T。若把矩陣取負,得到的導數便是 −1。
完整的小例子與邊界方程
例題 6.2.4
(三個節點、一階導數與狄利克雷(Dirichlet)問題)
當 n=2,節點為 1,0,−1。式 (3) 和 (6) 給出
D=3/21/2−1/2−2021/2−1/2−3/2,D2=111−2−2−2111.取 q(x)=1−x2,其數值向量是 u=(0,1,0)T。直接相乘得 Du=(−2,0,2)T 及 D2u=(−2,−2,−2)T,與 q′=−2x 和 q′′=−2 一致。
現在用同一網格,以配點法處理 (−1,1) 上的 −u′′=2,並要求 u(1)=u(−1)=0。先將端點數值設為零,再於唯一的內部節點要求微分方程成立:
−(D2u)1=−u0+2u1−u2=2.因此 u1=1。插值多項式恰好是 1−x2,即這個特定邊界問題的解。精確解屬於 P2,所以其樣本滿足配點方程,而這個只有一個未知數的系統有唯一解 u1=1。這些事實解釋了此處的精確恢復;它們並不是一般配點法的誤差估計。
可以重複微分,因為 pv′∈Pn−1⊂Pn,所以其導數樣本的插值多項式就是 pv′ 本身。歸納可得:對每個整數 m≥0,都有 (Dmv)i=pv(m)(xi),其中 D0 是單位矩陣。在精確算術下,Dn+1=0,因為每個 Pn 多項式的 n+1 階導數均為零。這個代數事實並不表示反覆作浮點矩陣乘法就沒有誤差問題。
概念視角代數
切比雪夫係數基底下的同一算子
在節點基底下 D 是稠密矩陣。寫 pv=k=0∑nakTk,並令 V 為元素 Vjk=Tk(xj)=cos(jkπ/n) 的 (n+1)×(n+1) 矩陣,則 v=Va;插值的唯一性保證 V 可逆。每個 Tk′ 都是滿足 m<k 且 k−m 為奇數的 Tm 的線性組合,所以微分在係數向量上由一個嚴格上三角矩陣 M 表示。因此
D=VMV−1.這個相似關係立即說明,在精確算術下為何 Dn+1=0,以及為何 D 的特徵值全為零:兩者在 M 上一目了然。對 n=1,V=(111−1)、M=(0010),而 VMV−1 正是上面的兩節點矩陣。
對一般區間 [a,b],假設 a<b,使用 t=(a+b)/2+(b−a)x/2。對 t 的一階微分矩陣是 2D/(b−a),二階微分矩陣是 4D2/(b−a)2。映射後的節點仍由 b 遞減至 a,縮放因子為正。
反例模式
先刪邊界再平方會丟失資訊
一個看似自然的做法是先從 D 刪去端點的行和列,再將餘下的矩陣平方,以近似零邊界值下的二階導數。對 n=2,這個內部矩陣是 (0),平方仍是 (0)。但 D2 的內部元素為 −2,正是例子需要的係數。函數 1−x2 在端點的一階導數並不為零;刪去這些中間導數值,便會丟失它們對二階導數的貢獻。應先形成完整的二階微分算子,再從二階方程消去已知的函數值。指定 u 的值,不等於指定 u′ 的值。
混疊與一個充分收斂條件
以 Lnf 表示 f 在洛巴托節點上、屬於 Pn 的插值多項式。在節點角度處,2nθj=2jπ。對整數 k≥0,寫成 k=2nq+s,其中 0≤s<2n,並定義
rn(k)={s,2n−s,0≤s≤n,n<s<2n.
於是 cos(kθj)=cos(rn(k)θj),由唯一性得
LnTk=Trn(k).(9)
與上一節的內部高斯網格不同,這個網格摺疊指標時沒有額外負號。特別地,LnT2n=1。因此,將微分矩陣作用於 T2n 的樣本會得到零,但 T2n′(1)=4n2。這是網格未能分辨原函數,不是次數至多為 n 的多項式精確性失效。
收斂論證必須同時控制未被分辨的項及其導數。式 (9) 直接給出一個精確的充分條件。
假設
f(x)=2a0+k=1∑∞akTk(x),k=1∑∞k2∣ak∣<∞.(10)此級數在 [−1,1] 定義一個連續可微函數,端點取單側導數,而且
∥f′−(Lnf)′∥∞≤2k>n∑k2∣ak∣⟶0.(11)所以在假設 (10) 下,由 D 給出的數值在各自的網格上一致逼近真正的導數。
由導數公式和 ∣sin(kθ)∣≤k∣sinθ∣,得 ∥Tk′∥∞≤k2。例如,將 e2ikθ−1 分解為 (e2iθ−1)h=0∑k−1e2ihθ,再用三角不等式,便證明上述正弦不等式。由連續性,導數界也適用於端點。因此,在 (10) 下,函數值級數和導數級數均一致收斂。為證明可以逐項微分,可從一個固定點積分一致收斂的導數級數;微積分基本定理加上該固定點的級數收斂,就將所得積分與 f 聯繫起來。這證明可微性,亦證明導數可連續延伸至端點,給出單側導數。
對固定的 n,插值算子是有限個點值與基底多項式的線性組合。因此,一致收斂級數可通過這個固定算子逐項插值及微分。用式 (9),並注意 k≤n 時 rn(k)=k,得
f′−(Lnf)′=k>n∑ak(Tk′−Trn(k)′).因為尾和內 rn(k)≤n<k,其一致範數不超過 k>n∑∣ak∣(k2+rn(k)2)≤2k>n∑k2∣ak∣。加權級數收斂,所以尾和趨零。最後,在 (Dv)i=pv′(xi) 中取 v=(f(x0),…,f(xn))T,便知所得向量正是 (Lnf)′ 的節點值。
證明透視
權重 k 平方的用途
(10) 中的權重與 ∥Tk′∥∞≤k2 相配,用了兩次:一次用來逐項微分 f 的級數,一次用來估計尾項。關鍵一步是:Ln 是點值的固定線性組合,因此可以穿過收斂的和;混疊規則 (9) 再把每個尾項送到某個 Trn(k),其中 rn(k)≤n<k,其導數不會更大,於是得到因子二。k≤n 的項恰好抵消。若只有 ∑∣ak∣<∞,便只能控制函數值,不能控制導數。
條件 (10) 是充分條件,並非必要條件;它比函數值係數絕對可和更強。僅有函數值插值誤差的估計,不能自動推出導數估計。尤其不能在一般插值餘項中,將未明確指定的中間點當成常數後直接微分。導數收斂需要獨立論證,例如上面的係數尾和證明。
噪聲與有限精度
假設測量向量為 v+e,其中 ∣ej∣≤ε。即使矩陣乘法完全精確,由數據誤差產生的導數誤差仍是 De,每一行均滿足
∣(De)i∣≤εj=0∑n∣Dij∣.(12)
在 x0=1,由於 1−xj>0,非對角元素 D0j 的符號為 (−1)j,而對角元素為正。又因 Tn(xj)=(−1)j,對 Tn 的精確性給出
j=0∑n∣D0j∣=j=0∑nD0j(−1)j=Tn′(1)=n2.
反射對稱性給出 xn=−1 處相同的絕對行和。取容許的擾動 ej=ε(−1)j,其插值多項式為 εTn,便達到端點誤差界 εn2。因此,端點微分可將有界數值誤差按 n 的平方放大。常數擾動的導數為零,所以這是最壞情況結論,不是每個誤差序列的預測。
當 n=2,D 的第 0 行是 (3/2,−2,1/2),各元素絕對值之和為 4=n2;中間一行 (1/2,0,−1/2) 的絕對值之和為 1。取 e=ε(1,−1,1)T,即 εT2=ε(2x2−1) 的樣本,則
De=ε(23+2+21, 21−21, −21−2−23)T=ε(4,0,−4)T,與 εT2′(x)=4εx 在節點的值一致。兩個端點行都達到式 (12) 的界 εn2=4ε,而內部誤差為零,低於該行的界 ε。同樣大小的常數擾動 ε(1,1,1)T 則給出 De=0。
形成及應用 D 時也會有算術誤差。端點附近節點聚集,令 1−x1=2sin2(π/(2n)) 為 n−2 的量級;直接將靠近 1 的已捨入餘弦值相減,可能損失相對精度。恆等式
xi−xj=−2sin2n(i+j)πsin2n(i−j)π
避免了這一處相減,但其數值計算仍須注意有限精度。用式 (8) 計算對角元素,可在構造矩陣時落實常數函數的恆等式;其後的內積運算仍可能留下捨入殘差。在精確算術下,等價的作用公式是
(Dv)i=j=i∑Dij(vj−vi).
這種寫法把常數數據的抵消直接呈現出來。這些重排都不能消除式 (12) 證明的數據敏感性,本節亦未建立任何具體實作的後向誤差界。加密網格時,必須同時考慮逼近尾和、數據誤差及算術誤差。
練習
練習 6.2.7
(在 n=2 的網格,將上面列出的矩陣作用於 f(x)=x3 的樣本。與三個節點處真正的導數比較,並找出插值多項式。)
基礎
解答(3)
1由樣本認出插值多項式
x3 的樣本為 (1,0,−1)T,與 x 的樣本相同。因此 L2f=x。
2作用矩陣
D(1,0,−1)T=(1,1,1)T,即 x 在三個節點的導數。
3與真正的導數比較
真正的導數向量為 (3,0,3)T,所以節點處的差 f′−(L2f)′ 是 (2,−1,2)T。取樣不能區分這兩個原多項式;只有其中一個的次數至多為二。
練習 6.2.8
(證明對每個 n≥1,都有 LnT2n−1=T1。計算 x=1 處真正導數與插值導數之差。)
核心
解答(2)
1在節點角度摺疊指標
關鍵一步
因為 (2n−1)θj=2jπ−θj,其餘弦等於 cosθj。因此 T2n−1 與 T1=x 在每個節點取值相同,由插值的唯一性得 LnT2n−1=x。
2比較端點處的導數
在 1 處的導數差是 T2n−1′(1)−1=(2n−1)2−1=4n(n−1)。當 n=1 時,此差為零,與預期一致:此時原多項式是 T1,屬於所表示的空間。
練習 6.2.9
(對 [0,2] 上的 −u′′=6t 及邊界條件 u(0)=u(2)=0,使用映射後的 n=2 網格,只在內部節點要求微分方程成立。找出配點多項式,與精確解比較,並解釋為何兩者節點值相同,導數卻不同。)
核心
解答(5)
1映射網格
映射後節點為 t=2,1,0,而 2/(b−a)=1,所以對 t 的導數仍用上面列出的 D2。
2解內部配點方程
端點值為零,內部方程便是 2u1=6,得到 u1=3。插值多項式為 q(t)=3t(2−t),滿足 −q′′=6,因此在 t=1 滿足原方程。
3求精確解
將 u′′=−6t 積分兩次並代入邊界條件,得精確解 u(t)=4t−t3。它在網格上同樣取值 (0,3,0),但 u′(1)=1,而 q′(1)=0。
4解釋節點值為何相同
關鍵一步
步長為一的中心二階差分 v0−2v1+v2,對每個三次多項式都等於其在 t=1 的精確二階導數;只須對 1,t,t2,t3 逐一核對,再用線性性即可。因此,三次精確解的樣本滿足同一內部方程和邊界值,而單一未知數系統的唯一性迫使節點值相同。
5分清數值與導數
也可直接觀察 u(t)−q(t)=−t(t−1)(t−2) 在三個節點均為零,但其導數不必在那裏為零。二次配點多項式並非在每一點都滿足微分方程。
練習 6.2.10
(假設 f 有式 (10) 的級數表示,且對 k≥1 有 ∣ak∣≤Ck−p,其中 C>0、p>3。驗證加權可和性,並由式 (11) 推導明確的冪次界。另外,選擇有界節點誤差,令端點導數誤差達到 εn2。)
綜合
解答(4)
1驗證加權可和的假設
由係數假設得 ∑k2∣ak∣≤C∑k2−p<∞,故可用 (10)。
依據: 級數 ∑k2−p 恰在 p>3 時收斂。
2以積分比較尾和
因為 x2−p 在 [n,∞) 上遞減且可積,
2k>n∑k2∣ak∣≤2Ck=n+1∑∞k2−p≤2C∫n∞x2−pdx=p−32Cn3−p.這估計的是精確數據下插值多項式的導數誤差。
3構造達到上界的數據誤差
關鍵一步
取 ej=εTn(xj)=ε(−1)j,則每項的絕對值為 ε,而 (De)0=εTn′(1)=εn2。
4分開兩種誤差來源
第一個估計不包含測量誤差;逼近尾和與數據誤差須分別納入考慮。
與其他筆記的聯繫
上一節的切比雪夫筆記介紹餘弦變量代換、連續係數,以及內部高斯節點的另一套混疊規則。有限元素筆記則提供從邊界方程建立有限維系統的另一條路。本節處理的是一種特定的多項式微分構造及一個簡單配點例子。一般譜邊值問題的穩定性、多維算子、解析函數的收斂率及浮點穩定性分析仍需另外討論。