動機
函數值告訴我們曲線經過哪裏;導數還告訴我們它怎樣經過該點。若軌跡必須以指定速度到達,只匹配位置便不足夠。Hermite 插值把導數條件視為真正數據。計算所需次數時必須把它們包括在內;重複節點代表額外導數資訊,並非把同一條方程再抄一次。
面對長長的數值表,另有一個設計問題:不必讓一個多項式在整段區間上不斷增加次數,而可在小區間使用三次多項式,再平滑連接。接點把相鄰片段聯繫起來,所以不能完全獨立選取每段。自然三次樣條藉把兩端二階導數設為零,消除餘下自由度。我們會推導其三對角系統,並證明所得曲線在全部二次連續可微插值函數中,最小化二階導數平方的積分。
先前相異節點插值單元是先備知識。
定義
令 t0<⋯<ts 為相異實節點。在 ti 指定導數 di,j,階數為 0≤j<μi,其中重數 μi≥1 為整數。記
N=i=0∑sμi,ω(x)=i=0∏s(x−ti)μi.Hermite 插值多項式的次數至多為 N−1,滿足 p(j)(ti)=di,j。每個節點的條件包括由零階至 μi−1 階的全部導數;若跳過中間階數,便屬另一類需要重新分析存在性的條件。數據可以是任意實數;只有要求近似餘項時,才需要背後有一個光滑函數。
重節點差商記號以導數記錄數據:
f[k+1 個t,…,t]=k!f(k)(t).
此記號並不要求除以零節點距離;導數值是給定數據。對多項式而言,此值也是在 t 的 Taylor 係數,不能直接把相異節點公式套入零分母。
樣條構造使用有序節點 a=x0<⋯<xn=b,整數 n≥1,以及值 y0,…,yn。定義區間長度及割線斜率
hi=xi+1−xi>0,δi=hiyi+1−yi,0≤i<n.三次樣條 S 屬於 C2([a,b]),在每個 [xi,xi+1] 上都是次數至多三的多項式。若 S(xi)=yi,它便插值數據;若 S′′(a)=S′′(b)=0,則稱為自然樣條。自然條件不代表端點斜率為零。記 Mi=S′′(xi),並定義彎曲泛函
J(g)=∫ab[g′′(x)]2dx,g∈C2([a,b]).
這在指定座標下懲罰二階導數,並不是幾何曲率按弧長的積分。我們會在明確指定的 C2 類中最小化它,不暗中使用弱導數或 Sobolev 空間定理。
定理/命題
定理 5.2.3
(Hermite 插值的存在、唯一性及重數餘項)
這 N 個 Hermite 條件恰好決定一個次數至多 N−1 的多項式。再假設 di,j=f(j)(ti)、f∈CN([A,B]),其中閉區間包含全部節點及求值點 x。若 x 不是節點,則在包含全部節點與 x 的最小區間內,存在 ξ 使
f(x)−p(x)=N!f(N)(ξ)ω(x).在節點處誤差為零。特別地,若 ∣f(N)∣≤KN,則 ∣f(x)−p(x)∣≤KN∣ω(x)∣/N!。單靠有限數據表不能認證這個導數界。
對每個嚴格遞增、n≥1 的節點列及任意實數數據,恰有一個自然三次插值樣條。其二階導數滿足 M0=Mn=0,且
hi−1Mi−1+2(hi−1+hi)Mi+hiMi+1=6(δi−δi−1),1≤i<n.內部系統非奇異。對每個滿足 g(xi)=yi 的 g∈C2([a,b]),即使 g 不滿足自然端點條件,亦有
J(g)=J(S)+J(g−S)≥J(S).等號成立當且僅當 g=S。所以樣條是整個 C2 插值函數類中的唯一極小者,而非只在分段三次多項式中最佳。
概念視角結構
選擇餘下自由度的三種不同方法
Hermite 插值用給定導數固定一個多項式。三次樣條連接條件聯繫相鄰片段,邊界條件再固定餘下全局自由度。最小彎曲定理則解釋,在只給定函數值時,為何自然邊界選擇有特殊變分地位。此解釋不會提供缺失的物理斜率,也不承諾保形或完整的樣條誤差理論。
證明思路或證明
把導數條件計作帶重數的零點
若多項式 q 滿足 q(j)(ti)=0、0≤j<μi,則 (x−ti)μi 整除 q;這由在 ti 展開有限 Taylor 多項式可見。不同節點的因子互質,故其乘積 ω 整除 q。兩個候選 Hermite 多項式之差正是這種次數至多 N−1 的 q;被次數為 N 的多項式整除,只能為零。
存在性方面,把次數至多 N−1 的 N 維多項式空間,映射到所要求的 N 個導數值。此映射線性,剛才的論證表明其核為零。同維有限維空間之間的單射線性映射也是滿射,故任意指定數據均可達到。若沒有這個獨立性論證,單純數方程條數並不能證明存在性。
餘項所需的是計入重數的 Rolle 定理。設足夠可微的函數在相異有序點有零點,指定重數為 r1,…,rℓ。在 rj≥2 的點,導數繼承重數 rj−1;Rolle 定理又在每個相鄰開間隙提供一個零點,共 ℓ−1 個,且與繼承零點相異。因此按重數共有 R=j∑rj 個零點,便使導數至少有 R−1 個按重數計的零點。在足夠可微下可重複使用;節點位於端點時,採用單側延拓的端點導數值仍然成立。
固定非節點 x,令 c=(f(x)−p(x))/ω(x)。函數 q(t)=f(t)−p(t)−cω(t) 在節點具有總重數 N 的零點,並在 x 多出一個零點。把上述 Rolle 論證用 N 次,在所得某個 ξ 處有
0=q(N)(ξ)=f(N)(ξ)−cN!,因 p(N)=0,且 ω 是首一 N 次多項式,餘項公式得證。ξ 可以依賴 x,卻不是已知可微的 x 函數;不能把它當作常數來微分餘項。
端點值及斜率給出明確三次基底
對 a<b,令 h=b−a、t=(x−a)/h,定義
H00=2t3−3t2+1,H10=t3−2t2+t,H01=−2t3+3t2,H11=t3−t2.
給定值 ya,yb 及相對於 x 的斜率 va,vb,插值式為
p(x)=yaH00(t)+hvaH10(t)+ybH01(t)+hvbH11(t).
在 t=0,1,值基函數取得所需值且 t 導數為零;H10,H11 的端點值均為零,並分別具有相應的單位 t 導數。因 d/dx=h−1d/dt,乘上 h 才把給定斜率換成正確單位。這些檢查加上唯一性,便證明公式。
若數據來自 f∈C4([a,b]),其餘項為
f(x)−p(x)=24f(4)(ξ)(x−a)2(x−b)2,∥f−p∥∞≤384K4h4.
寫成 t=(x−a)/h 後,有 t2(1−t)2≤1/16。對 f(x)=(x−a)2(x−b)2,四個 Hermite 數據全為零,p=0、f(4)=24,故界可達到。此主張使用精確端點導數數據,並不把從含雜訊函數值估計的導數當作精確值。
對線性二階導數積分,構造每個樣條片段
三次多項式的二階導數是仿射函數。若端點二階導數為 Mi,Mi+1,積分兩次再匹配兩個端點值,得到
Si(x)=6hiMi(xi+1−x)3+6hiMi+1(x−xi)3+(yi−6Mihi2)hixi+1−x+(yi+1−6Mi+1hi2)hix−xi.直接代入得 Si(xi)=yi、Si(xi+1)=yi+1 及兩個指定二階導數。這四個條件唯一決定一個三次多項式:齊次差的二階導數為仿射函數,在兩端為零,故二階導數恆零;差本身因而仿射,再由兩端零值可知它恆零。
此片段的端點斜率為
Si′(xi)=δi−6hi(2Mi+Mi+1),Si′(xi+1)=δi+6hi(Mi+2Mi+1).把 Si−1′(xi) 與 Si′(xi) 設為相等,整理後正好得到上述三對角方程。函數值本已連續相接,二階導數亦在共同的 Mi 相接;這些方程再使一階導數相等,故拼合函數確實屬於 C2。三階導數可以跳變,定義容許這點。
非均勻系統有唯一解
若 n=1,沒有內部未知數;M0=M1=0,樣條便是通過兩個值的直線。以下設 n≥2。內部係數矩陣 T 對稱,對角為 2(hi−1+hi),相鄰元素為 hi。把內部向量 z 延伸為 z0=zn=0,其二次型為
zTTz=2i=0∑n−1hi(zi2+zizi+1+zi+12)≥i=0∑n−1hi(zi2+zi+12)>0當內部 z 非零時嚴格為正,因 a2+ab+b2≥(a2+b2)/2 且每個 hi>0。故 T 正定且非奇異。解出二階導數後,片段公式構造出存在的樣條;反之,每個自然插值樣條均須滿足同一系統和片段公式,所以唯一。
直接精確算術構造只需線性數量的運算。令 ai=2(hi−1+hi)、bi=6(δi−δi−1),以 q1=a1、c1=b1 起步;對 2≤i<n 消去前一個未知數:
qi=ai−qi−1hi−12,ci=bi−qi−1hi−1ci−1.然後 Mn−1=cn−1/qn−1,再對 i=n−2,…,1 回代 Mi=(ci−hiMi+1)/qi。主元均非零:q1>h1,而 qi−1>hi−1 推出 qi>hi−1+2hi>hi。這證明精確算術中的除法有定義。浮點實作仍需數據縮放及捨入分析;遞推本身並非普遍準確度保證。
證明透視
方程與未知數的計數
先計數:內部二階導數共有 n−1 個,每個內部節點各有一條斜率相等的方程,共 n−1 條;自然條件 M0=Mn=0 去掉兩個端點未知數,所以系統是方陣。斜率方程是 C1 連續性唯一進入的地方;函數值及二階導數的一致由各段的構造保證。每個 hi 為正這一點用了兩次:在二次型中,以及在主元界 qi>hi 中,因此沒有隱藏等距假設。若重複節點使 hi=0,片段公式便無定義;若去掉自然條件,就會留下兩個自由參數,下文單一區間的反例正說明這一點。
最小彎曲來自正交交叉項
取任意 C2 插值函數 g,令 e=g−S,則 e(xi)=0。在一段上分部積分兩次,使用該片段三階導數的單側值:
∫xixi+1Si′′e′′dx=[Si′′e′−Si′′′e]xixi+1.剩下的積分含 Si(4)=0,所以消失。這只要求 e∈C2 及 Si 為多項式,不需要 g 有三階導數。含 e 的邊界項因每個節點 e=0 而消失。在內部節點,左右兩段的 S′′e′ 項因 S′′ 及 e′ 連續而抵消;最外端項則因 S′′(a)=S′′(b)=0 消失。因此 ∫abS′′e′′=0。
展開 g′′=S′′+e′′ 即得 J(g)=J(S)+J(e)。若等號成立,連續非負函數 (e′′)2 的積分為零,故 e′′ 處處為零。於是 e 仿射;它在兩個相異端點為零,迫使 e=0。注意競爭函數的端點斜率和二階導數從未受限制。自然條件屬於極小樣條,負責消除端點交叉項;若要求每個競爭者也滿足自然條件,只會證明較弱的主張。
證明透視
每個假設消去哪一種邊界項
真正的想法是:誤差 e=g−S 在積分內積下與 S′′ 正交,所以 J 像勾股和一樣分拆。每個假設消去一類邊界項:e(xi)=0 消去所有 Si′′′e 項,即使 S′′′ 在節點跳躍;S′′ 與 e′ 連續使內部的 S′′e′ 項抵消;S′′(a)=S′′(b)=0 消去最外兩項。沒有自然條件時,交叉項為 S′′(b)e′(b)−S′′(a)e′(a)。若 S′′(b)=0,取在各節點為零、且 w′(a)=0=w′(b) 的 w∈C2,則 J(S+ϵw)=J(S)+2ϵS′′(b)w′(b)+ϵ2J(w),取符號適當的小 ϵ 便低於 J(S)。最後,J(e)=0 加上兩個端點零點完成唯一性。
算例
對 [0,1] 上的 f(x)=x4,端點數據為 f(0)=f′(0)=0、f(1)=1、f′(1)=4,Hermite 三次多項式是
p(x)=H01(x)+4H11(x)=2x3−x2,f(x)−p(x)=x2(x−1)2.在 x=1/2,p=0、f=1/16。由 f(4)=24,一致餘項界為 24/384=1/16,在中點達到。三次多項式甚至在 1/4 取負值 p(1/4)=−1/32,雖然 f 非負。匹配函數值和斜率並不自動保留中間的正負號。
取節點 0,1,3 及值 0,1,0。此時 h0=1、h1=2、δ0=1、δ1=−1/2。唯一內部方程是 6M1=−9,故 M1=−3/2,而 M0=M2=0。代入得
S(x)={(5x−x3)/4,(3−x)−(3−x)3/8,0≤x≤1,1≤x≤3.接點兩側函數值均為一,一階導數均為 1/2,二階導數均為 −3/2。兩個最外端二階導數為零;但 S′(0)=5/4、S′(3)=−1,確認「自然」並非端點水平。這不是單一全局三次多項式,因兩段三階導數分別為 −3/2 和 3/4。
例題 5.2.7
(與全局插值二次多項式比較彎曲量)
同一數據亦由二次多項式 q(x)=x(3−x)/2 插值。其 q′′=−1,故 J(q)=3。樣條則在 [0,1] 上有 S′′=−3x/2,在 [1,3] 上有 S′′=3(x−3)/4,所以
J(S)=∫0149x2dx+∫13169(x−3)2dx=43+23=49.變分恆等式因而給出 J(q−S)=3/4。極小曲線的二階導數平方代價,小於這個更光滑的全局多項式。最小彎曲比較的是此特定泛函,並非多項式次數或存在多少階導數。
常見錯誤
反例模式
邊界條件不足會留下解族;相互矛盾的額外條件使問題無解
只有一段 [0,1]、端點值均為零時,每個三次多項式 p(x)=x(1−x)(A+Bx) 均插值,留下兩個自由參數;沒有內部接點條件去消除它們。自然端點條件選出零函數。
改為端點值零和一時,自然條件迫使仿射函數 p′′ 在兩端為零,故 p′′=0、p=x,端點斜率均為一。再加 p′(0)=p′(1)=0 便不相容。匹配這兩個固定斜率的三次多項式是 3x2−2x3,端點二階導數為 6、−6。自然與固定斜率條件描述不同插值問題,同時施加未必可行。
即使邊界條件彼此相容,自然樣條也只回答它被構造來回答的問題。
反例模式
自然樣條不會自動承襲端點 Hermite 餘項界,也不保證單調
對單一區間 [0,h] 上的 f(x)=x2、h>0,自然樣條為直線 S(x)=hx,最大絕對誤差是 h2/4,但 f(4)=0。含四階導數的三次 Hermite 餘項不能使用,因這條直線沒有插值真正的端點斜率。
又如節點 0,1,2 與非遞減數據 0,0,1,自然樣條有 M1=3/2,第一段為 (x3−x)/4,在 0<x<1 為負,在 1/2 等於 −3/32。最小彎曲不是非負或單調限制;保形插值需要額外設計選擇。
端點導數是獨立數據;沒有額外假設,不能從兩個相近函數值精確恢復它。若以差商代替所指定的斜率,問題及其誤差分析都隨之改變。
重節點插值不會平均互相矛盾的函數值:同一階導數若被指定兩個不同值,條件直接不相容。
三次樣條精確插值樣本,並非平滑樣條,也不會自動移除測量雜訊。若樣本帶有誤差,樣條會在節點處把誤差原樣重現。
小結
Hermite 插值把導數計作獨立條件及帶重數的零點,在明確的全局光滑假設下由重數 Rolle 論證得到餘項。自然三次樣條則在任意正節點間距上,解正定三對角系統來決定二階導數。所得 C2 曲線在全部 C2 插值函數中唯一最小化二階導數平方積分。邊界選擇、精確導數數據、近似誤差及保形條件仍是不同問題。
練習
快速檢查
(指定 p(0)=1、p′(0)=0、p(1)=2,求 Hermite 多項式及節點乘積。若數據來自 f∈C3([0,1]) 且 ∣f′′′∣≤6,給出 x=1/2 的誤差界。解釋為何重複零點處的函數值條件不能代替導數條件。)
設 p=a+bx+cx2,代入三個條件。
解答 · 答案
共有 N=3 個條件,零點處重數二、一點處重數一。寫 p=a+bx+cx2,得 a=1、b=0、c=1,所以 p=1+x2。節點乘積為 ω(x)=x2(x−1)。在 1/2 的餘項界為 6∣(1/2)2(−1/2)∣/3!=1/8。再寫一次 p(0)=1 只重複同一線性方程,不限制 b,仍留下二次插值式解族。
快速檢查
(在 [2,4],指定端點值分別為一和三,斜率分別為零和一。用 t=(x−2)/2 寫出 Hermite 三次式,求在三的值,並檢查兩端相對 x 的導數。若 ∣f(4)∣≤24,在所需光滑假設下給出一致餘項界。)
取 h=2,並保留斜率項上的因子 h。
解答 · 答案
區間長度為二,故 p=H00+3H01+2H11=1+4t2−2t3。在 x=3,t=1/2,得到 p=7/4。導數為 p′(x)=(8t−6t2)/2=4t−3t2,在 t=0 為零,在 t=1 為一。若數據來自 f∈C4([2,4]),一致界為 24(24)/384=1。右端斜率項若忘記乘以區間長度,便無法通過導數檢查。
快速檢查
(構造通過 (0,1),(1,0),(2,1) 的自然樣條。求內部二階導數、兩段三次式、接點共同斜率及彎曲泛函,再與二次式 (x−1)2 比較。)
當 h0=h1=1,內部方程為 4M1=6(δ1−δ0)。
解答 · 答案
此時 h0=h1=1、δ0=−1、δ1=1,故 4M1=12,即 M1=3。兩段為 [0,1] 上的 S0(x)=1−3x/2+x3/2,及 [1,2] 上的 S1(x)=1−3(2−x)/2+(2−x)3/2。接點的值為零、斜率為零、二階導數為三,外端二階導數為零。兩段二階導數是 3x、3(2−x),故 J(S)=3+3=6。二次式的二階導數為二,彎曲量八,比樣條多二,正好等於 J((x−1)2−S)。
快速檢查
(對算例中通過 (0,0),(1,1),(3,0) 的樣條 S,令 gϵ(x)=S(x)+ϵx(x−1)(x−3),其中 ϵ 為實數。證明它們是容許的 C2 競爭者,並精確求 J(gϵ)。使用極小化定理是否要求它們端點二階導數為零?)
所加的多項式 x(x−1)(x−3) 在每個節點都為零。
解答
多項式 w=x(x−1)(x−3) 在三個節點均為零,所以每個 gϵ 都是 C2 插值函數。由 w′′=6x−8,
J(w)=∫03(6x−8)2dx=324−432+192=84.與 S 的交叉項由已證恆等式消失,故 J(gϵ)=9/4+84ϵ2,唯一最小點為零。競爭者的端點二階導數分別為 −8ϵ、10ϵ,一般不為零,但仍被容許:交叉項論證只需要極小樣條滿足自然端點條件。