1、1,計(jì) 算 方 法,南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,第二章 插值法 (Interpolation),2020/8/25,1,2,內(nèi) 容,2.1 引言 多項(xiàng)式插值問題的一般提法,2.2 拉格朗日(Lagrange)插值,2.3 均差與Newton插值公式,2.4 差分與等距節(jié)點(diǎn)插值公式,2.5 埃爾米特插值,2.6 分段低次插值,2.7 三次樣條插值,2020/8/25,2,3,2.0 為什么要研究插值法,插值法是廣泛應(yīng)用于理論和實(shí)踐的重要數(shù)值方法, 它是用簡單函數(shù)(特別是多項(xiàng)式或分段多項(xiàng)式)為離散數(shù)組建立連續(xù)模型；為非有理函數(shù)提供好的逼近方法。眾所周知，反映自然規(guī)律數(shù)量關(guān)系的函數(shù)大致有三種表示方法

2、：,解析表達(dá)式,圖象法,表格法,2020/8/25,3,4,2.0 為什么要研究插值法,許多函數(shù)關(guān)系數(shù)據(jù)是用表格法給出(如觀測(cè)和實(shí)驗(yàn)得到的數(shù)據(jù))。但用離散的函數(shù)值進(jìn)行理論分析和設(shè)計(jì)，是不方便或是不可能的。因此需要尋找與已知函數(shù)值相符，并且形式簡單的插值函數(shù)(或近似函數(shù))。,另外一情況是，函數(shù)表達(dá)式給定，但其形式不適宜計(jì)算機(jī)使用，一些涉及連續(xù)變量問題的計(jì)算需經(jīng)過離散化后才能進(jìn)行。如數(shù)值積分方法、數(shù)值微分方法、差分方程以及有限元法等，都必須直接或間接地應(yīng)用到插值理論和方法。,2020/8/25,4,5,2.1 多項(xiàng)式插值問題的一般提法,當(dāng)函數(shù) y = f (x) 復(fù)雜或未知，在一系列節(jié)點(diǎn) x0 x

3、n 處得函數(shù)值 y0 = f (x0) , , yn = f (xn)， 由此構(gòu)造一個(gè)簡單的近似函數(shù) p(x) f(x)， 滿足條件: p(xi) = f(xi) (i = 0, n)。 這里的 p(x) 稱為f(x) 的插值函數(shù)。,2020/8/25,5,6,插值函數(shù) p (x) 作為 f (x) 的近似，可以選自不同 類型的函數(shù), 如 p (x) 為代數(shù)多項(xiàng)式、三角多項(xiàng)式、有 理分式；其函數(shù)性態(tài)可以是光滑的、亦可以是分段光 滑的。其中，代數(shù)多項(xiàng)式類的插值函數(shù)占有重要地位：,(a) 結(jié)構(gòu)簡單、計(jì)算機(jī)容易處理、任何多項(xiàng)式的導(dǎo)數(shù)和積分也易確定。,(b) 著名的Weierstrass逼近定理(定義

4、在閉區(qū)間上的 任何連續(xù)函數(shù) f(x) , 存在代數(shù)多項(xiàng)式p(x)一致逼近f(x), 并達(dá)到所要求的精度)。,因此，我們主要考慮代數(shù)多項(xiàng)式的插值問題。,2020/8/25,6,7,x0 , x1, , xn 插值節(jié)點(diǎn),函數(shù) P(x) 稱為函數(shù) y=f(x) 的插值函數(shù)， 區(qū)間 a, b 稱為插值區(qū)間。,2020/8/25,7,8,插值法的適用,1.求函數(shù)表上兩值之間未列出的函數(shù)值.,需要求出 ln(1.64),如已知 f(x)=ln(x)的函數(shù)表:,9,2. 已知y=f(x)在若干點(diǎn)的函數(shù)值, 求經(jīng)過各點(diǎn)(xi, yi)的簡單函數(shù)P(x).,例如,已知,可求2次多項(xiàng)式P(x)=1-0.94175

5、7x+0.309636x2,滿足P(0)=1, P(0.5)=0.606531, P(1)=0.367879,(yi= f(xi),10, 3. 函數(shù)f(x)難以計(jì)算,希望在區(qū)間a,b找到簡單函數(shù)P(x)代替f(x),以便計(jì)算.,11,例子: f(x)=arctan(x), 在-1,1區(qū)間上, 可用 簡單函數(shù)多項(xiàng)式P(x)=0.987733x-0.202335x3 代替 f(x),12,例. (插值問題的一般解法),已知函數(shù) f(x) 有如下數(shù)據(jù):,求 f(x) 的插值多項(xiàng)式 p(x)， 并求 f(x) 在 x=0.5 處的近似值。,12,13,13,14,插值的幾何意義,從幾何上看，插值就是

6、求一條曲線 使其通過給定的 個(gè)點(diǎn) ， 并且與已知曲線 有一定的近似度。,從幾何上看,曲線 P ( x) 近似 f ( x),14,15,插值問題是否可解. 若有解,是否唯一. 如何求插值函數(shù)P(x). P(x)與 f(x)的誤差如何估計(jì). 當(dāng)插值節(jié)點(diǎn)無限加密時(shí), P(x)是否收斂 于f(x).,插值法的研究內(nèi)容,16,存在唯一性定理：,yf(x)在a,b有定義, 設(shè)a=x0 x1 x2 xn=b,已知f(x)在xi處的函數(shù)值 yi=f(xi), (i = 0,1, ,n),則存在唯一的多項(xiàng)式P(x), 使得: P(xi)=yi , (i = 0,1, ,n),證明: 設(shè) P(x) = a0+a

7、1x+a2x2+.+anxn,條件P(xi)=yi 代入, 得:,這是關(guān)于未知系數(shù)a0 , a1,.,an的線性方程組,插值條件,17,其系數(shù)行列式為Vandermonde行列式,因此,關(guān)于a0 , a1,.,an的線性方程組有唯一解.,即存在唯一的多項(xiàng)式P(x) = a0+a1x+a2x2+.+anxn,滿足插值條件.,18,n = 1,已知 x0 , x1 ; y0 , y1 ，求,使得,1,1,1,0,0,1,),(,),(,y1,x1,L,y0,x0,L,=,=,可見 L1(x) 是過 ( x0 , y0 ) 和 ( x1, y1 ) 兩點(diǎn)的直線。,2.2 拉格朗日多項(xiàng)式 /* Lag

8、range Polynomial */,線性插值基函數(shù),1. 線性插值與拋物插值:,2020/8/25,18,19,線性插值與其基函數(shù)示意圖,2020/8/25,19,20,顯然, 是過 、 、 三點(diǎn)的一條拋物線。,已知 , 求 ，,n = 2,使得,2020/8/25,20,21,顯然, 是過 、 、 三點(diǎn)的一條拋物線。,已知 , 求 ，,n = 2,使得,21,22,拋物線插值基函數(shù),于是,拋物線基函數(shù),22,23,推導(dǎo)n+1節(jié)點(diǎn)的Lagrange插值多項(xiàng)式,24,25,希望找到 li (x)，i = 0, , n 使得 li (xj) = ij ；然后令,，則顯然有 Pn(xi) = y

9、i 。,每個(gè) li 有 n 個(gè)根 x0 , xi , xn,， k = 0, 1 , n .,k = 0, 1 , n .,由 得:,25,26,設(shè) 函數(shù)表 則滿足插值條件的多項(xiàng)式,（Lagrange）插值多項(xiàng)式,其中, .,2020/8/25,26,27,以下的問題：如何分析插值的余項(xiàng)？,(1) 先求插值基函數(shù). (2) 構(gòu)造插值多項(xiàng)式.,構(gòu)造插值多項(xiàng)式的方法：,2020/8/25,27,28,已知連續(xù)函數(shù) f (x) 的函數(shù)表如下：,求方程 f (x)=0 在(-1,2)內(nèi)的近似根。,例題,2020/8/25,28,29,解：利用Lagrange插值法有,取初值x=0.5，利用牛頓法求解可

10、得 f (x) 在(-1,2)內(nèi)的近似根 為0.67433。,解方程,已知連續(xù)函數(shù)f (x)的函數(shù)表如下：,試求方程 f (x)=0 在(-1,2)內(nèi)的近似根。,例題,29,30,，且 f 滿足條件 , Lagrange插值法插值余項(xiàng),設(shè)節(jié)點(diǎn),在a , b內(nèi)存在, 考察截?cái)嗾`差:,2020/8/25,30,31, Lagrange插值法的插值余項(xiàng),2020/8/25,31,32, Lagrange插值法的插值余項(xiàng),證明：由已知條件得到：,于是有：,其中 是與 x 有關(guān)的待定函數(shù)。,2020/8/25,32,33,故,處均為零，,在,上有n+2個(gè)個(gè)零點(diǎn)，根據(jù) Roll 定理,在 的每兩個(gè)零點(diǎn)間至

11、少有一個(gè)零點(diǎn)，故 在 內(nèi)至少有 n+1個(gè)零點(diǎn)，對(duì) 再用Roll 定理，可知 在 內(nèi)至少有 n 個(gè)零點(diǎn)，依此類推， 在 內(nèi)至少有一個(gè)零點(diǎn)，記為,使得:,2020/8/25,33,34,由于 是不能確定，因此我們并不能確定誤差的大小 但如能求出 ，那么用 逼近 的截?cái)嗾`差限是： 當(dāng) 時(shí)， 當(dāng) 時(shí),2020/8/25,34,35,當(dāng) f (x) 為任一個(gè)次數(shù) n 的多項(xiàng)式時(shí)， , 可知， 即插值多項(xiàng)式對(duì)于次數(shù) n 的多項(xiàng)式是精確的。,注意,2020/8/25,35,36,37,38,給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個(gè)是 l2(x) 的圖像？,問題,202

12、0/8/25,38,39,算例1,Lagrange插值法,已知 ， ， 用線性插值及拋物線插值計(jì)算 的值并估計(jì)截?cái)嗾`差。,2020/8/25,39,40,算例1,Lagrange插值法,已知 ， ， 用線性插值及拋物線插值計(jì)算 的值并估計(jì)截?cái)嗾`差。,線性插值時(shí)取,解:,2020/8/25,40,41,其截?cái)嗾`差為： 其中, 因?yàn)?可取 于是：,2020/8/25,41,42,用拋物線插值時(shí)，取所有節(jié)點(diǎn)，得到,余項(xiàng)討論： 其中：,2020/8/25,42,43,算例2,Lagrange插值法,利用 100，121 的開方計(jì)算 .,由于:,解:,利用Lagrange插值法有,于是,的精確值為 10

13、.72380529, 因此, 近似值 10.71428 有3 位有效數(shù)字.,Return,2020/8/25,43,44,45,第二章 習(xí)題 P. 42 第2題 第2題改用L二次 插值計(jì)算, 估計(jì)誤 差 P.42 第3題（線性插值用x=0.5, 0.6兩點(diǎn)；二次插 值用x=0.5, 0.6, 0.7三點(diǎn)）,估計(jì)誤差 P.42 第4題 第6題 第8題 p.43 第19題,2020/8/25,45,46,k = 0, 1 , , n .,復(fù)習(xí)：Lagrange插值,設(shè) y = f (x) , 已知：,Lagrange插值公式：,插值余項(xiàng):,2020/8/25,47,f(x)=xlnx， 已知,2次

14、插值多項(xiàng)式求f(4.5)，用余項(xiàng)公式估計(jì)誤差,48,2.3 差商與Newton插值公式,Lagrange 插值雖然易算，但若要增加一個(gè)節(jié)點(diǎn)時(shí)， 全部基函數(shù) li (x) 都需重新計(jì)算。,48,2020/8/25,49,增加節(jié)點(diǎn)需要重新計(jì)算基函數(shù),給計(jì)算帶來不便,看2次和3次L插值公式,在0,3求f(x)的插值函數(shù):,50,由線性代數(shù)知識(shí)可知：任一n次多項(xiàng)式都可以表示成,n+1 個(gè)線性無關(guān)多項(xiàng)式的線性組合。,那么，可以將這 n+1 個(gè)多項(xiàng)式作為插值基函數(shù).,而 ,線性無關(guān),51,設(shè)插值多項(xiàng)式P(x)具有如下形式：,再繼續(xù),形式更復(fù)雜,為此引入差商和差分的概念.,P(x)應(yīng)滿足插值條件：,有：,5

15、1,52,2.3.1 差商（也稱均差）的及其性質(zhì),從零階差商出發(fā)，歸納地定義各階差商:,稱 為函數(shù) 關(guān)于點(diǎn) 的一階差商.,一般地， 關(guān)于 的 k 階差商:,記函數(shù) 在 的值 ， 稱 為 關(guān)于 的零階差商。,52,53,一般， 關(guān)于 的 n 階差商:,n 階差商的概念,2020/8/25,53,或,54,差商的基本性質(zhì),性質(zhì)1：差商可表示為函數(shù)值的線性組合，即：,54,fx0,x1,xk=c0 f(x0)+c1 f(x1)+ck f(xk),其中,因此, 均差f x0,x1,xn 與節(jié)點(diǎn)x0,x1,xn次序無關(guān). 從而有:,55,可用歸納法證明,性質(zhì)2：差商與所含節(jié)點(diǎn)次序無關(guān),性質(zhì)3：,56,性

16、質(zhì)4：設(shè)f(x)在a,b 存在 n 階導(dǎo)數(shù)，且 ，則 使得:,例. f(x)=3x4-5x3+4x-8,則 f0,1,2,3,4,f1,2,3,4,5,6,=f(4)/4! =3,= f(5)/5! =0,57,差商的計(jì)算,2020/8/25,57,差 商 表,58,已知,計(jì)算三階差商,解：列表計(jì)算,算例,2020/8/25,58,59, 2.3.2 牛頓插值公式,根據(jù)差商的定義，把 x 看成a,b上的一點(diǎn)， 可得：,2020/8/25,59,60,牛頓插值公式,把后一式代入前一式,2020/8/25,60,根據(jù)差商的定義，把 x 看成a,b上的一點(diǎn)，,61,顯然Nn(x)滿足插值條件，且次數(shù)

17、不超過n,它就 是插值多項(xiàng)式，其系數(shù)為： 我們稱 為牛頓插值多項(xiàng)式.,2020/8/25,61,其中,62,2020/8/25,62,63,從表中可以看到4 階差商幾乎為0，故取4次插值多項(xiàng)式即可， 于是：,解：列表計(jì)算,已知 的函數(shù)表，求4 次牛頓插值多項(xiàng)式, 并求,算例,2020/8/25,63,64,解：列表計(jì)算,已知 的函數(shù)表，求4 次牛頓插值多項(xiàng)式, 并求,算例,截?cái)嗾`差為：,2020/8/25,64,65,2.4 差分與等距節(jié)點(diǎn)插值公式,在前面的討論中，節(jié)點(diǎn)是任意分布的，但實(shí)際上經(jīng)常遇 到等距節(jié)點(diǎn)的情況，這時(shí)插值公式可以得到簡化，為此，我 們先介紹差分的概念。 設(shè)函數(shù) 在等距節(jié)點(diǎn)

18、上的值 為已知，這里 為常數(shù)，稱為步長。,下面來討論差分的定義。,2020/8/25,65,66,差分的定義,記號(hào) 分別稱為 在 處以 為步長的 向前差分、向后差分、中心差分 符號(hào) 、 、 分別稱為向前差分算子、向后差分算子、 中心差分算子.,2020/8/25,66,67,高階差分,用一階差分可以定義二階差分 一般地可定義 m 階差分為： 中心差分定義為: 以此類推。,2020/8/25,67,68,不變算子 I、移位算子 E,定義 從而可得： 于是得到： 同理，由于： 得到： 由于： 得到： 由差分的定義及不變算子和移位算子有如下性質(zhì):,2020/8/25,68,69,差分的性質(zhì),性質(zhì)1：

19、各階差分均可用函數(shù)值表示，如：,2020/8/25,69,70,性質(zhì)2：某點(diǎn)的函數(shù)可用各階差分來表示：,71,性質(zhì)3：差商與差分有如下關(guān)系：,2020/8/25,71,性質(zhì)4：差分與導(dǎo)數(shù)有如下關(guān)系：,72,差分的計(jì)算,Return,2020/8/25,72,73,74,75,等距節(jié)點(diǎn)前插公式,2020/8/25,75,76,等距節(jié)點(diǎn)后插公式,2020/8/25,76,77,和 均是 n 次多項(xiàng)式,且均滿足插值條件: 由多項(xiàng)式的唯一性, ,因而,兩個(gè)公式 的余項(xiàng)是相等的,即 當(dāng)插值多項(xiàng)式從 n-1 次增加到 n 次時(shí), 拉格朗日型插值必須重新計(jì)算所有的基本插值多項(xiàng)式; 而對(duì)于牛頓型插值,只需用表

20、格再計(jì)算一個(gè) n 階差商, 然后加上一項(xiàng)即可。,牛頓插值公式和Lagrange插值公式比較,Return,2020/8/25,77,78,例.已知f(x)=sinx在0.5,0.6,0.7,0.8的值,分別用 二次, 三次Newton插值求sin0.57891.,解: 節(jié)點(diǎn)等距, 先求差分表,79,令 x= x0+ t h =0.57891, 則 t=0.7891,=0.547139,實(shí)際誤差: sin0.57891- 0.547139 = -2.713E-5,80,實(shí)際誤差: sin0.57891-0.547112=1.3287E-7,81, 2.5 埃爾米特 (Hermite) 插值,拉格朗日和牛頓均只保證函數(shù)插值； 實(shí)際問題有時(shí)需要導(dǎo)數(shù)也插值； 滿足這種需要的插值稱為埃爾米特插值.,2020/8/25,81,82,埃爾米特插值的一般提法為： 設(shè)函數(shù)在節(jié)點(diǎn) 的函數(shù)值與導(dǎo)數(shù)值為： 其中 是正整數(shù)，尋求一個(gè)次數(shù)盡可能低的多 項(xiàng)式