1、,第4章 插值法,1 插值問(wèn)題 2 線性插值與二次插值 3 代數(shù)多項(xiàng)式插值的存在唯一性 4 代數(shù)多項(xiàng)式的余項(xiàng) 5 拉格朗日插值多項(xiàng)式 6 牛頓均差插值多項(xiàng)式 7 牛頓前差和后差插值多項(xiàng)式 8 三次樣條插值 9 數(shù)值微分 10 曲線擬合法,?,7,=,x,i,4 9 16,y,i,2 3 4,4 7 9 16,4,3,2,0,應(yīng)用背景,造函數(shù)表：三角函數(shù)、對(duì)數(shù),預(yù)測(cè)：雞蛋價(jià)格、城市用水量,數(shù)控加工：造船、飛機(jī)機(jī)翼骨架、服裝,樣片、模具加工、刀具,計(jì)算機(jī)輔助設(shè)計(jì)：潛水艇、汽車造型,服裝樣片,實(shí)際問(wèn)題中，f (x)多樣，復(fù)雜，通常只能觀測(cè)到一些離散數(shù)據(jù)；或者f (x)過(guò)于復(fù)雜而難以運(yùn)算。這時(shí)我們要用

2、近似函數(shù)(x)來(lái)逼近f (x)。,自然地，希望(x)通過(guò)所有的離散點(diǎn)。, (x),f (x),已知,x,i,，,y,i,，,i,=0,1,n,是函數(shù),y=f,(,x,),的離散點(diǎn)，,(,x,),為,y=f,(,x,),的近似函數(shù)。,滿足,(,x,i,)=,y,i,，,i,=0,1,n,稱這個(gè)問(wèn)題為曲線插值問(wèn)題。,(,x,),為插值函數(shù)；,x,i,i,=0,1,n,為,插值節(jié),點(diǎn)；,f,被插值函數(shù)；,(,x,i,)=,y,i,插值條件或插值原則。,(,x,),求,1 插值問(wèn)題,數(shù)學(xué)模型：已知,x,i,，,y,i,，,求一條光滑曲線滿足,(,x,i,)=,y,i,。,理論問(wèn)題：,1,數(shù)學(xué)描述；,2

3、,誤差估計(jì)；,取前n+1項(xiàng)的部分和Pn(x)作為f (x)的近似式，也即：,若僅限于求函數(shù)在x=x0的近似函數(shù)，一個(gè)熟知的辦法就是將f(x)在x=x0處展成泰勒級(jí)數(shù)，即,多項(xiàng)式插值,（待定系數(shù)法）,多項(xiàng)式插值,（待定系數(shù)法）,代數(shù)多項(xiàng)式形式簡(jiǎn)單，便于計(jì)算， 且在某些情況下與給定的函數(shù)有較好的逼近的特性,1個(gè)點(diǎn)插值,x,y,2 線性插值與二次插值,2.1 線性插值 線性插值是代數(shù)多項(xiàng)式插值的最簡(jiǎn)單的形式。假設(shè)給定了函數(shù)f (x)在兩個(gè)互異點(diǎn)x0，x1的值,即,（2,點(diǎn)插值）,現(xiàn)要用一線性函數(shù) (x)=P1(x)=ax+b 近似地代替f (x)。按照插值原則，有：,因?yàn)閤0 x1,所以a，b可唯一

4、確定，且有,2.2 二次插值 二次插值又稱為拋物線插值,也是常用的代數(shù)多項(xiàng)式插值之一。設(shè)已知函數(shù)f(x)的三個(gè)互異插值基點(diǎn)x0，x1，x2的函數(shù)值分別為y0，y1，y2,見(jiàn)下表所示:,（3,點(diǎn)插值）,現(xiàn)要構(gòu)造一個(gè)二次函數(shù) (x)=P2(x)=ax2+bx+c 近似地代替f (x)，并滿足插值原則 P2(xi)=yi， i=0，1，2，,x0，x1，x2互異，a，b，c可唯一地確定。 二次函數(shù)P2(x)也唯一地被確定。,3 代數(shù)多項(xiàng)式插值的存在唯一性,對(duì)于一般的代數(shù)插值問(wèn)題，就是尋求一個(gè)n次的代數(shù)多項(xiàng)式： Pn(x)=a0+a1x+a2x2+anxn 使其在給定的n+1個(gè)互異的插值基點(diǎn)上滿足插值

5、原則 Pn(xi)=yi，i=0，1，n,根據(jù)插值原則式，代數(shù)多項(xiàng)式中的各個(gè)系數(shù)a0，a1，an應(yīng)滿足下列n+1階線性方程組,系數(shù)行列式為范德蒙特(Vander Monde)行列式,由于插值基點(diǎn)xi (I = 0，1，n)為互異,故 V(x0，x1，xn)0 方程組有唯一的一組解a0，a1，an Pn(x)存在且唯一。,4 代數(shù)多項(xiàng)式的余項(xiàng),一般說(shuō)來(lái),對(duì)插值區(qū)間a，b上插值基點(diǎn)xi (i=0，1，2，n)以外的點(diǎn)，P n (x) f (x)。若令： R n (x) = f (x) P n(x) 則： f (x) = P n (x) +R n (x),插值多項(xiàng)式Pn (x)的余項(xiàng),定理:設(shè)Pn(

6、x)是過(guò)點(diǎn)x0 ，x1 ，x2 ，xn的f(x)的n 次插值多項(xiàng)式，f(x) Cn+1a,b ，其中a，b是包含點(diǎn)x0 ，x1 ，x2 ，xn的區(qū)間，則對(duì)任意給定的xa，b，總存在一點(diǎn)（a，b）（依賴于x）使：,插值的截?cái)嗾`差,其中：,證明見(jiàn)書(shū)P145,插值的絕對(duì)誤差限為:,由上面定理有一下幾點(diǎn)結(jié)論: (1) 插值多項(xiàng)式只與插值基點(diǎn)及基點(diǎn)上的函數(shù)值有關(guān)，與函數(shù)f(x)沒(méi)有關(guān)系。但余項(xiàng)Rn(x)卻與f(x)聯(lián)系很緊。,(2) 若f(x)即為次數(shù)不超過(guò)n的多項(xiàng)式，那么以n+1個(gè)點(diǎn)為基點(diǎn)的插值多項(xiàng)式就一定是其本身，即P n (x) f (x)。 (3) 當(dāng)點(diǎn)x位于x0，x1，xn的中部時(shí)，|n+1(

7、x)|比較小，誤差小些，而位于兩端時(shí)，誤差要更大些。,說(shuō)明：,滿足插值條件,于是：,5 拉格朗日插值多項(xiàng)式,關(guān)鍵是,:,l,i,(,x,)=,？,故有,當(dāng),n=1,Lagerange,插值,x,0,x,1,y,0,y,1,x,y,22,當(dāng)n=2,時(shí)，,Lagerange插值為：,滿足插值條件：,例：已知函數(shù) y=f (x)的觀測(cè)數(shù)據(jù)為,試求拉格朗日插值多項(xiàng)式。,解 ：,已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)為,試求拉格朗日插值多項(xiàng)式。,解：,例：,解：,圖 4.3,圖 4.3,想法：,Lagrange插值每增加一個(gè)節(jié)點(diǎn)，所有的系數(shù)必須重新計(jì)算。 能否有一種方法，增加節(jié)點(diǎn)時(shí)，先前的計(jì)算仍然可以利用，只增

8、加很少的工作量就能得到新的高次插值多項(xiàng)式。,做法：,6 牛頓均差插值多項(xiàng)式,?,將插值多項(xiàng)式Pn(x)表示成下列形式:,依據(jù)條件，根據(jù)插值原則，可以依次確定系數(shù)a0，a1，an，例如： 取x=x0，得 取x=x1 ,得,為了得到計(jì)算系數(shù)ai的一般方法,下面引進(jìn)差商的概念.,取x=x2,得,二 差商的定義 給定a,b中互不相同的點(diǎn)x0，x1，x2，以及f(x)在這些點(diǎn)處相應(yīng)的函數(shù)值 f(x0)，f(x1)，f(x2)，用記號(hào) 表示f(x)在x0及x1兩點(diǎn)的一階差商。 x0，x1，x2三點(diǎn)的二階差商為： 一般地，有了k-1階差商之后，可以定義f(x)在x0，x1，.，x k的k階差商：,三 New

9、ton插值公式 由差商定義,有 f(x)= fx0+(x-x0)fx,x0 fx,x0= fx0,x1+(x-x1)fx,x0,x1 fx,x0,x1= fx0,x1,x2+(x-x2)fx,x0,x1,x2 . fx,x0,xn-1= fx0,xn+(x-xn)fx,x0,.,xn 將以上各式，由下而上逐步代入，得到 f(x)= f(x0)+(x-x0) fx0,x1+(x-x0)(x-x1) fx0,x1,x2 +(x-x0)(x-xn-1) fx0,xn,+(x-x0)(x-xn-1)(x-xn)fx,x0,xn,(5),牛頓差商表,例3 已知數(shù)據(jù)表，構(gòu)造f (x)的牛頓均差插值多項(xiàng)式。

10、,解： 作均差表,P3(x) = 0+(-5)(x-1)+2(x-1)(x-2) +(x-1)(x-2)(x-3) = x3-4x2+3,試求牛頓均差插值多項(xiàng)式。,例4 已知數(shù)據(jù)表,解:,7 牛頓前差和后差插值多項(xiàng)式,當(dāng)插值基點(diǎn)x0,x1,xn分布等距時(shí),也即 h=x k+1 -xk, k=0,1,2,n-1 牛頓均差插值多項(xiàng)式的表達(dá)形式可以簡(jiǎn)化。為此先引進(jìn)有限差概念。,7.1 有限差 我們分別稱,為一階前差、一階后差和一階中心差,又統(tǒng)稱為一階有限差。這里符號(hào)、分別表示前差、后差和中心差算子。 由一階有限差算子的定義,用遞推方法可定義高階有限差。二階前、后差分別定義為,依此類推,n階前差定義為

11、,n階后差定義為,并規(guī)定零階前、后差為,同樣可定義n階中心差,根據(jù)有限差的定義,可得到它的幾個(gè)簡(jiǎn)單性質(zhì):= (1)若函數(shù)f(x)為m次多項(xiàng)式,則,m-k次多項(xiàng)式,0km,km（即常數(shù)的有限差為零）,(431),(2) 均差與前、后差的關(guān)系可表示為,(432),(433),式(432)和(433)可用歸納法證明。,7.2 牛頓前差和后差插值多項(xiàng)式 1.牛頓前差插值多項(xiàng)式 在牛頓均差插值多項(xiàng)式(424)中,按式(432)將均差換成前差,即得到牛頓前差插值多項(xiàng)式,(434),令 x=x0+sh (s未必是整數(shù)) 則 xi=x0+ih x-xi=(s-i)h, i=0,1,2,n,這樣牛頓前差插值多項(xiàng)

12、式可改寫(xiě)成,(435),或記為,且其余項(xiàng)為,(436),2. 牛頓后差插值多項(xiàng)式 若將n+1個(gè)插值基點(diǎn)依xn,xn-1,x0的次序排列,則牛頓均差插值多項(xiàng)式為 Pn(x)=f(xn)+fxn,xn-1(x-xn) +fxn,x n-1,x0(x-xn)(x-xn-1)(x-x1) 根據(jù)公式(433)易得,用后差代替均差,可得牛頓后差插值多項(xiàng)式,令 x=xn+th（t不一定是整數(shù)） 則 x n-k= x n-k h x- x n-k =(t+k)h, k=0,1,2,n,于是牛頓后差插值多項(xiàng)式又可寫(xiě)成,(437),或記為,其余項(xiàng)為,(438),這里 n+1(x)=t(t+1)(t+2)(t+n)

13、hn+1,表45,表 46,例5 分別作出 f(x)=x2+x+1 的前差和后差表。 解 前差表見(jiàn)表47;后差表見(jiàn)表48。,表 47,表 48,例6 給出正弦函數(shù)sinx由x=0.4到0.7的值(h=0.1),試分別用牛頓前差和后差公式計(jì)算sin0.57891的近似值。 解 作差分表49。,表 4,利用牛頓前差公式,利用牛頓后差公式,8 三次樣條插值,8.1 三次樣條插值函數(shù)的定義 設(shè)給定區(qū)間a,b上n+1個(gè)點(diǎn) a=x0 x1x2xn=b 如果函數(shù)s(x)滿足: (1)在每一個(gè)子區(qū)間xk,xk+1(k=0,1,n-1)上,s(x)是一個(gè)不超過(guò)三次的多項(xiàng)式,且 s(xi)=f(xi),i=0,1

14、,2,n (439),(2)函數(shù)s(x)在a,b上具有直到二階的連續(xù)導(dǎo)數(shù),則稱s(x)是f(x)以x1,x2,xn-1為內(nèi)部基點(diǎn)的三次樣條插值函數(shù),并稱(xi,yi)(i=0,1,2,n)為樣條插值函數(shù)的樣點(diǎn)。,8.2 三次樣條插值法 按照三次樣條插值函數(shù)的定義,s(x)在每一個(gè)子區(qū)間xk,xk+1上是一個(gè)不超過(guò)三次的多項(xiàng)式,故s(x)是線性函數(shù)。 令 mk=s(xk), k=0,1,2,n (440) 設(shè)xxk,xk+1,則過(guò)兩點(diǎn)(xk,mk)與(xk+1,mk+1)的直線所表示的線性函數(shù)為,(441),其中 hk=x k+1 -xk 對(duì)(441)式兩端連續(xù)求兩次積分得,(442),(443

15、),其中Ak、Bk為積分常數(shù)。根據(jù)插值原則,由式(443)得到方程,(444),從而解出Ak和Bk,即,(445),(446),由式(443)可看出三次樣條插值函數(shù)s(x)僅與 mk、m k+1有關(guān)系,因此只要求得各個(gè)mk,則各個(gè)子區(qū) 間xk,x k+1上的三次樣條函數(shù)也就確定了。下面 介紹求mk的方法。,當(dāng)xx k-1,xk時(shí),(447)式應(yīng)表示為,當(dāng)xxk,x k+1時(shí),(448),(449),根據(jù)三次樣條插值函數(shù)的定義,應(yīng)有,整理后得到,(450),那么,于是(450)式可簡(jiǎn)寫(xiě)成,(451),也即,(452),此是含有n+1個(gè)未知量m0,m1,mn的n-1個(gè)方程的 方程組,我們可根據(jù)實(shí)際

16、問(wèn)題的具體要求補(bǔ)充兩個(gè)附加 條件,就可求出各個(gè)mk。,在區(qū)間a,b的端點(diǎn)a和b(即x0和xn)處對(duì)樣條插值函數(shù)加以限制,稱為端點(diǎn)條件。常用的端點(diǎn)條件有以下幾種: 函數(shù)y=f(x)在兩端點(diǎn)x0及xn處的導(dǎo)數(shù)y0和yn為已知。此時(shí)要求,由式(448)和(449)得到,也即,(453),其中,(454),式(452)與式(453)兩個(gè)方程組聯(lián)立成,其幾何解釋為曲線在兩端點(diǎn)的斜率。 函數(shù)y=f(x)在兩端點(diǎn)x0,xn處的二階導(dǎo)數(shù)為零。此時(shí)要求,其幾何解釋為曲線在兩端點(diǎn)的曲率為零。 函數(shù)y=f(x)是一個(gè)以b-a=xn-x0為周期的周期函 數(shù)。此時(shí) y0=yn,相應(yīng)也要求樣條插值函數(shù)s(x)也具有周期性

17、,故在端點(diǎn)要求滿足條件,由于hn=h0,mn=m0,yn=y0利用式(448)和式(449) 可得到,于是有,(457),例7 給出四個(gè)樣點(diǎn)(1,1)、(2,3)、(4,4)、(5,2),求其各個(gè)子區(qū)間上的樣條插值函數(shù)s(x)(設(shè)m0=m3=0),并求f(3)。 解 給定樣點(diǎn)的函數(shù)表為,于是求mk的方程組為,則關(guān)于m1,m2的方程組為,解得,在1,2上的樣條插值函數(shù)為,在2,4上的樣條插值函數(shù)為,在4,5上的樣條插值函數(shù)為,并且,9 數(shù)值微分,9.1 用插值法求數(shù)值微分 用插值多項(xiàng)式Pn(x)近似地表示函數(shù)f(x),即 f(x)Pn(x) 于是有 f(k)(x)P(k)n(x) 其余項(xiàng)相應(yīng)地為

18、R(k)n(x)。,設(shè)插值基點(diǎn)為等距分布,由牛頓前差插值多項(xiàng)式,其中,由于,于是,即,因?yàn)?而當(dāng)x=xi時(shí),s=i,此時(shí),(459),(460),特別當(dāng)x=x0時(shí),s=0,則,(461),1. 兩點(diǎn)公式(n=1),于是在區(qū)間x0,x2上有,(462),2. 三點(diǎn)公式(n=2),于是在區(qū)間x0,x2上有,9.2 用三次樣條函數(shù)求數(shù)值微分 設(shè)s(x)是f(x)在各區(qū)間xk,xk+1上的三次樣條插值函數(shù),則在區(qū)間xk, xk+1 上可通過(guò)三次樣條函數(shù)來(lái)求f(x)的數(shù)值微分。 1.一階數(shù)值微分公式,(465),若只求基點(diǎn)xk(k=0,1,n-1)上的一階導(dǎo)數(shù)值,則,(466),2. 二階數(shù)值微分公式,

19、特別,若只求基點(diǎn)上的二階導(dǎo)數(shù)值,則,(467),(468),10 曲線擬合法,設(shè)一組觀測(cè)數(shù)據(jù)為,能否找到一個(gè)簡(jiǎn)單易算的 p (x) ，使得 f(x) p (x),已知 f(x) 在某些點(diǎn)的函數(shù)值：,m 通常很大 yi 本身是測(cè)量值，不準(zhǔn)確，即 yi f (xi) 不要求f (xi)通過(guò)所給的數(shù)據(jù)點(diǎn)，但能表述（xi，yi）的趨勢(shì) 已知f (xi)的基本形式,這時(shí)不要求 p(xi) = yi , 而只要,p(xi) yi 總體上盡可能小,曲線擬合,使 最小,使 最小,p(xi) yi 總體上盡可能小,常見(jiàn)做法,設(shè)函數(shù)關(guān)系y=f (x)的一組觀測(cè)數(shù)據(jù)為(xi, yi) (i=0,1,2,n),欲求一個(gè)m(mn)次多項(xiàng)式 Pm(x)=0+1x+mxm 的平方和最小,最小二乘法,R稱為用Pm(x)擬合f (x)的總偏差,根據(jù)極值理論，要使得 R 達(dá)到極小，必有：,稱此方程組為正則方程組。通過(guò)它可求出a0, a1,