插值法：原理與應(yīng)用【精制材料】

1、插值法：原理與應(yīng)用,Zhenhua Song,1,行業(yè)相關(guān),插值的背景,1. 只有n個點(diǎn)處的函數(shù)值 希望找到一條通過這些點(diǎn)的曲線（連續(xù)、光滑） 2. 函數(shù)太麻煩，近似簡化 找到一個好計算的函數(shù)，近似代替 3. 用多項式代替 多項式方便求值、求導(dǎo)、積分等,2,行業(yè)相關(guān),插值 & 逼近 & 擬合,0. 給定n個不同的點(diǎn)，構(gòu)造曲線 1. 插值：曲線依次通過n個點(diǎn) 2. 逼近：曲線最接近n個點(diǎn) （接近：在某種意義下） 例：最小二乘法 3. 擬合：插值 + 逼近,3,行業(yè)相關(guān),泰勒展開,在某一點(diǎn)x0處展開 只在x0處近似性較好 遠(yuǎn)離x0的點(diǎn)誤差較大 需要n個點(diǎn)近似性較好 插值可以勝任,4,行業(yè)相關(guān),一次

2、插值,用一次函數(shù)近似表示,5,行業(yè)相關(guān),二次插值,用二次函數(shù)來表示,6,行業(yè)相關(guān),多項式插值 ：示例,給定的n+1個不同的點(diǎn) 找到一個n次多項式， 依次通過這n+1個點(diǎn) n次多項式必然唯一,7,行業(yè)相關(guān),多項式插值：唯一性,設(shè)n次多項式為 = 0 + 1 + 2 2 + 在這n+1個點(diǎn)上，滿足n+1個方程 0 = 0 + 1 0 + 2 0 2 + 0 1 = 0 + 1 1 + 2 1 2 + 1 2 = 0 + 1 2 + 2 2 2 + 2 = 0 + 1 + 2 2 + ,8,行業(yè)相關(guān),多項式插值：唯一性,把上述線性方程組寫成矩陣形式 1 0 0 2 0 1 1 1 2 1 1 2 2

3、 2 2 1 2 0 1 2 = 0 1 2 系數(shù)矩陣行列式不為0： 范德蒙行列式， 0 到 互不相同 方程組解唯一 多項式系數(shù)唯一 插值多項式唯一,9,行業(yè)相關(guān),拉格朗日插值,一種多項式插值算法 n次多項式 不用求解線性方程組 基函數(shù)線性組合 = 0 , 0 + 1 , 1 + , + , , 0 , , 1 , , , , , 稱為基函數(shù),10,行業(yè)相關(guān),拉格朗日插值：2點(diǎn)情形, 1 = 0 1, 0 + 1 1, 1 我們希望通過 0 , 0 , 1 , 1 這2個點(diǎn) 可以取 1, 0 0 =1, 1,1 0 =0 1, 0 1 =0, 1,1 1 =1. 這樣， 1 0 = 0 1,

4、0 0 + 1 1, 1 1 = 0 ， 1 1 = 0 1, 0 1 + 1 1, 1 1 = 1 如何實(shí)現(xiàn)上述條件？,11,行業(yè)相關(guān),基函數(shù)的構(gòu)建：2點(diǎn)情形,條件： 1, 0 0 =1, 1,1 0 =0 1, 0 1 =0, 1,1 1 =1. 構(gòu)造一次多項式 構(gòu)造： 1, 0 = 1 0 1 , 1, 1 = 0 1 0 分子是一次多項式 滿足 1, =0 的條件 分母是系數(shù)，滿足 1, =1 = 的條件 實(shí)質(zhì)：=+的直線,12,行業(yè)相關(guān),基函數(shù)的構(gòu)建：n+1點(diǎn)情形,條件： 1, =0 , 1, =1 = 構(gòu)造n次多項式 構(gòu)造： , = 0 1 1 +1 0 1 1 +1 注意，分子沒

5、有 ，分母沒有 符合條件約束 實(shí)質(zhì)： 每個基函數(shù)都是n次多項式,13,行業(yè)相關(guān),拉格朗日插值：n+1點(diǎn)情形,插值函數(shù)： = 0 , 0 + 1 , 1 + , + , 基函數(shù)： , = 0 1 1 +1 0 1 1 +1 簡潔形式： = =0 0 , 0 = =0 0 =0, ,14,行業(yè)相關(guān),拉格朗日插值：誤差估計,拉格朗日是一種近似，存在誤差。 對于近似代替函數(shù)的情形。 誤差分析： = +誤差項 如果 +1 , , 誤差項= +1 +1 ! =0 ,15,行業(yè)相關(guān),拉格朗日插值：示例,對 =1/在 0 =2, 1 =2.75, 2 =4插值,16,行業(yè)相關(guān),Nevile迭代插值,對于給定的

6、n+1個點(diǎn) 0 , 1 , 通過遞推求出n次插值多項式 設(shè) 1 , 2 , 是的不同自然數(shù) 1 , 2 , 是定義在 1 , 2 , , ,17,行業(yè)相關(guān),Nevile迭代插值,對于給定的k+1個點(diǎn) 0 , 1 , 插值多項式 在k+1個點(diǎn)上 在除去點(diǎn)j的k個點(diǎn)上的插值多項式 在除去點(diǎn)i的k個點(diǎn)上的插值多項式 = ,18,行業(yè)相關(guān),Nevile迭代插值, 0,1 , 0 , 1 , 2 , 3 , 1,2 , 2,3 , 0,1,2 , 1,2,3 , 0,1,2,3 ,19,行業(yè)相關(guān),牛頓差商插值,n次多項式寫成多項式和： = 0 + 1 0 + 2 0 1 + 0 1 1 確定系數(shù)，可確定

7、插值多項式 經(jīng)過n+1個點(diǎn)確定唯一n次多項式 系數(shù)可以由差分確定,20,行業(yè)相關(guān),牛頓差商插值：系數(shù)確定,多項式： = 0 + 1 0 + 2 0 1 + 0 1 1 取值： 0 = 0 = 0 1 = 1 = 0 + 1 1 0 1 = 1 0 1 0 1 為差分形式 所有系數(shù)都可以寫成差商形式 定義符號：,21,行業(yè)相關(guān),牛頓差商插值：系數(shù)確定,定義符號： = 零階差商 , +1 = +1 +1 一階差商 , +1 , +2 = +1 , +2 , +1 +2 二階差商 , +1 , +2 , , + = +1 , +2 , + , +1 , +1 + k階差商 在 0 處差分： 0 =

8、0 = 0 , 0 , 1 = 1 0 處階差分= ,22,行業(yè)相關(guān),牛頓差商插值：公式導(dǎo)出, = 0 + =1 0 , 1 , 2 , , =0 1 定義符號： = 零階差商 , +1 = +1 +1 一階差商 , +1 , +2 = +1 , +2 , +1 +2 二階差商 , +1 , +2 , , + = +1 , +2 , + , +1 , +1 + k階差商,23,行業(yè)相關(guān),牛頓差商插值：系數(shù)求解, 0, 1, 2, 3, 0 , 1, 1 , 2, 2 , 3, 0 , 1 , 2, 1 , 2 , 3, 0 , 1 , 2 , 3,24,行業(yè)相關(guān),牛頓差商插值：間距相等,當(dāng)n+

9、1個點(diǎn)等距排列時： 設(shè)= +1 = 0 + 插值多項式變形： = 0 + =1 0 , 1 , 2 , , =0 1 其中 = 0 + 0 + = =0 1 = =0 1 ,25,行業(yè)相關(guān),牛頓差商插值：間距相等,變形處理： =0 1 = =0 1 組合數(shù) = ! ! 定義廣義組合數(shù) = 1 +1 ! = =0 1 ! 廣義組合數(shù)：s可以是任意實(shí)數(shù). =0 1 = ! = 0 + =1 0 , 1 , 2 , , ! ,26,行業(yè)相關(guān),牛頓差商插值：反向差商,之前，當(dāng)n+1個點(diǎn)等距排列時： 設(shè)= +1 = 0 + 對于反向差分： = + 多項式形式與= 0 +類似。,27,行業(yè)相關(guān),Hermi

10、te插值,拉格朗日插值缺點(diǎn) 在n+1個點(diǎn)處與 值相同 導(dǎo)數(shù)等不同 目的： 找到一個多項式函數(shù) 不光函數(shù)值相同 k階導(dǎo)數(shù)相同 數(shù)學(xué)語言： = ,=0,1, ,28,行業(yè)相關(guān),拉格朗日插值缺點(diǎn),插值多項式形狀、走向差異較大,29,行業(yè)相關(guān),Hermite插值 ：優(yōu)勢,只取1個點(diǎn)時： 取m階導(dǎo)數(shù)信息，相當(dāng)于泰勒展開 取n+1個點(diǎn)時： 不考慮導(dǎo)數(shù)信息，相當(dāng)于拉格朗日插值 具有更廣泛的應(yīng)用 生成的Hermite插值多項式唯一 在n+1個點(diǎn)，第i個點(diǎn) 階導(dǎo)數(shù)相同,30,行業(yè)相關(guān),Hermite ：一階導(dǎo)數(shù)相同,在n+1個點(diǎn)處函數(shù)值相同，切線相同 需要2n+1階多項式 條件： 1 , 0 , 1 , 2 ,

11、 , 思想： 與拉格朗日基函數(shù)思想相似,31,行業(yè)相關(guān),Hermite：一階導(dǎo)數(shù)相同, 2+1 = =0 , + =0 , 當(dāng)= 時， 為了保證 2+1 = , 令 , =1, , =0 , , =0, , =0. 為了保證 2+1 = , 令 , =0, , =0 令 , =1, , =0,32,行業(yè)相關(guān),Hermite : 一階導(dǎo)數(shù)相同, 2+1 = =0 , + =0 , 其中， , = 12 , , 2 , = , 2 , 為拉格朗日基函數(shù)（第j個，n次多項式）,33,行業(yè)相關(guān),回憶拉格朗日基函數(shù),插值函數(shù)： = 0 , 0 + 1 , 1 + , + , 基函數(shù)： , = 0 1 1

12、 +1 0 1 1 +1 基函數(shù) , 性質(zhì) 在 處值為0， 在 處值為1.,34,行業(yè)相關(guān),Hermite ：其他,誤差分析 如果 2+2 , = 2+1 + 0 2 2 2+2 2 2+2 后面即為誤差項. 也可以用差分形式表達(dá) 形式與n次多項式牛頓差分類似 并不是次數(shù)越高越精確 誤差反而可能變大,35,行業(yè)相關(guān),三次樣條插值 ：背景,給定n+1個點(diǎn) 0 , 0 , , ， 0 1 2 分成n段，每一段：是一個分段函數(shù) 在 0, 處，分段函數(shù)取值為 盡可能保持光滑,36,行業(yè)相關(guān),線段連接：粗糙,相鄰兩點(diǎn)用線段連接 形成折線，不夠光滑,37,行業(yè)相關(guān),三次樣條插值：特性,每一段 , +1 用

13、3次多項式 表示 = , +1 = +1 . 或者說 +1 = +1 +1 分段函數(shù)在 +1 處連續(xù) 暫不考慮分段函數(shù)兩端的情況 +1 = +1 +1 . 分段函數(shù)在 +1 處一階導(dǎo)數(shù)相同 +1 = +1 +1 . 分段函數(shù)在 +1 處二階導(dǎo)數(shù)相同 具有較好的光滑性,38,行業(yè)相關(guān),三次樣條插值：邊界,對于兩端點(diǎn)，處理如下： 0 0 = 0 , = 0 0 =0, =0.,39,行業(yè)相關(guān),三次樣條插值：構(gòu)建,對于某一段 ,（不考慮端點(diǎn)） 設(shè) = + + 2 + 3 + + 2 + 3 = 處函數(shù)值相同 + +1 + +1 2 + +1 3 = +1 +1 處函數(shù)值相同 +1 + 2 +1 +

14、3 +1 2 = +1 +1 + 2 +1 +1 + 3 +1 +1 2 +1 兩端一階導(dǎo)數(shù)值相同 2 + 6 +1 = 2 +1 + 6 +1 +1 +1 兩端二階導(dǎo)數(shù)值相同,40,行業(yè)相關(guān),三次樣條插值：構(gòu)建,所有條件，可以組成線性方程組 =, 為稀疏矩陣 求解線性方程組，得到唯一解 三次樣條缺點(diǎn)： 估計誤差不方便,41,行業(yè)相關(guān),三次樣條插值：應(yīng)用, = , 0 =0, 1 =1, 2 =2, 3 =3,42,行業(yè)相關(guān),改變某一個點(diǎn) ,43,行業(yè)相關(guān),改變某一個點(diǎn) ：對比,多項式插值： 牽一發(fā)動全身，整個多項式都變了 三次樣條插值： 在 附近有較大影響，遠(yuǎn)離 處影響不大,44,行業(yè)相關(guān),

15、多項式插值：對比,45,行業(yè)相關(guān),參數(shù)曲線,對于n+1個點(diǎn) 0 , 0 , 1 , 1 , , +1 滿足參數(shù)方程 以為參數(shù) = , = n+1個點(diǎn)對應(yīng)n+1個參數(shù)取值： 0 1 2 ,46,行業(yè)相關(guān),參數(shù)曲線：圖像,47,行業(yè)相關(guān),三次參數(shù)曲線：定義,輸入： 點(diǎn) 0 , 0 , 1 , 1 0 , 0 處切線上某點(diǎn) 0 + 0 , 0 + 0 1 , 1 處切線上某點(diǎn) 1 + 1 , 1 + 1 輸出 = 是t的3次函數(shù), = 是t的3次函數(shù). 0 = 0 , 0 = 0 1 = 1 , 1 = 1 輸出三次參數(shù)曲線唯一,48,行業(yè)相關(guān),三次參數(shù)曲線：構(gòu)造,設(shè) = = 0 + 1 + 2 2 + 3 3 = = 0 + 1 + 2 2 + 3 3 滿足條件 0 = 0 = 0 , 0 = 0 = 0 1 = 1 = 0 + 1 + 2 + 3 1 = 1 = 0 + 1 + 2 + 3 0 = 0 , 1 = 1 , 0 = 0 , 0 = 0 方程解唯一存在 8個未知量，