計算方法插值方法

計算方法插值方法第1頁，共67頁，2023年，2月20日，星期四第4章插值方法§4–1問題的提出§4–2拉格朗日插值多項式§4–3差商、差分及牛頓插值多項式§4–4高次插值的缺點及分段插值§4–5樣條插值函數(shù)2第2頁，共67頁，2023年，2月20日，星期四學習要點插值的基本概念，包括線性插值、拋物插值和多項式插值的存在唯一性；多項式插值方法，包括基于及函數(shù)的Lagrange插值，插值余項定理；高次插值和分段插值。3第3頁，共67頁，2023年，2月20日，星期四4.1問題的提出許多實際問題都用函數(shù)y=f(x)來表示某種內(nèi)在規(guī)律的數(shù)量關(guān)系,其中相當一部分函數(shù)是通過實驗或觀測得到的。雖然f(x)在某個區(qū)間[a,b]上是存在的，有的還是連續(xù)的，但卻只能給出[a,b]上一系列點

有的函數(shù)雖然有解析表達式,但由于計算復雜,使用不方便,通常也構(gòu)造一個函數(shù)表。如三角函數(shù)表、對數(shù)表、平方根表、立方根表等等。4第4頁，共67頁，2023年，2月20日，星期四5第5頁，共67頁，2023年，2月20日，星期四4.1.1插值函數(shù)的概念可以通過構(gòu)造簡單函數(shù)P(x),使P(xi)=yi(i=1,2…,n)，這種求P(x)的方法稱為插值法定義4.1：設函數(shù)y=f(x)在區(qū)間[a,b]上有定義，且已知點a≤x0<x1<…<xn≤b上的值為y0,y1,…,yn，若存在一個簡單的函數(shù)P(x)使得

P(xj)=yj(j=0,1,2…,n)成立，稱P(x)為f(x)的插值函數(shù)，點x0,x1,…,xn的為插值節(jié)點，[a,b]為插值區(qū)間,f(x)為被插函數(shù)，這個條件被稱為插值條件6第6頁，共67頁，2023年，2月20日，星期四代數(shù)多項式插值就是一種典型的插值函數(shù)7第7頁，共67頁，2023年，2月20日，星期四4.1.2插值多項式的存在唯一性定理4.1：滿足條件P(xj)=yj(j=0,1,2…,n)的n次多項式是存在而且唯一的。

上面的方程可以用待定系數(shù)法結(jié)合線性方程組解法求解8第8頁，共67頁，2023年，2月20日，星期四4.1.2插值多項式的存在唯一性其系數(shù)行列式為范德蒙德(Vandermode)行列式9第9頁，共67頁，2023年，2月20日，星期四4.2拉格朗日（Lagerange）插值多項式可以構(gòu)造函數(shù)P1(x)為

4.2.1基本插值多項式觀察一個兩點的插值情況：10第10頁，共67頁，2023年，2月20日，星期四4.2.1基本插值多項式顯然，l0(x)和l1(x)是滿足插值條件的一次插值多項式

如果令：則11第11頁，共67頁，2023年，2月20日，星期四如對n次多項式，求一個n次多項式lk(x)滿足：

或者寫為：顯然，lk(x)至少含有如下的n個一次因子：12第12頁，共67頁，2023年，2月20日，星期四其中Ak為待定因子，由lk(xk)=1,得：

因此，基本地，lk(x)可以寫為：13第13頁，共67頁，2023年，2月20日，星期四4.2.2拉格朗日插值多項式稱上式為n次拉格朗日多項式，記為Ln(x),即根據(jù)基本插值多項式可以得到滿足插值條件的n次插值多項式14第14頁，共67頁，2023年，2月20日，星期四練習：已知x=1,2,3,4,5，對應的函數(shù)值f(x)=1,4,7,8,6試構(gòu)造4次拉格朗日插值多項式。15第15頁，共67頁，2023年，2月20日，星期四4.2.3插值余項

在節(jié)點處

在其它點上，均是近似值。記稱Rn(x)為插值多項式的余項。16第16頁，共67頁，2023年，2月20日，星期四定理：設f(n)(x)在[a,b]上連續(xù)，f(n+1)(x)在(a,b)內(nèi)存在節(jié)點，a≤x0<x1<…<xn≤b，

Ln(x)

是滿足插值條件處，

Ln(xj)

是=yj(j=0,1,2,…,n)的n次多項式，則對任意x屬于[a,b]，插值余項

17第17頁，共67頁，2023年，2月20日，星期四說明：（1）當f(x)本身是一個次數(shù)不超過n的多項式時，Rn(x)=0，（2）由于余項表達式只有在f(x)的n+1階導數(shù)存在時才能使用，而ξ并不知道，因此一般常用求出誤差限，即

18第18頁，共67頁，2023年，2月20日，星期四練習：設f(x)=x4,試利用拉格朗日插值余項定理寫出以-1,0,1,2為插值節(jié)點的三次插值多項式。19第19頁，共67頁，2023年，2月20日，星期四例3：已知特殊角30°，45°，60°的正弦函數(shù)值為用一次插值多項式、二次插值多項式近似sinx,并用此近似sin50°.20第20頁，共67頁，2023年，2月20日，星期四4.2.4一類帶導數(shù)插值條件的插值例：設x0，x1，x2是互不相同的節(jié)點。已知節(jié)點上的函數(shù)值f(xj)=yj(xj),和x1處的導數(shù)值f’(xj)=m1。求一個次數(shù)不超過3的多項式P3(x),使得P3(xj)=yj

,P3‘

(x1)=m1

并估計插值余項f(x)-P3(x)。解：（1）求插值多項式。記21第21頁，共67頁，2023年，2月20日，星期四令，

P3(x)=L2(x)+Q(x)則Q(x)=P3(x)-L2(x)是不超過3次的多項式，且滿足，

Q(xj)=

P3(xj)-L2(xj)=yj-yj=0

j=0,1,2那么x0，x1，x2是Q(x)的3個零點。于是不妨設Q(x)=A(x-x0)(x-x1)(x-x2)A為待定系數(shù)。由P3’

(x1)=L2’

(x1)+Q’(x1)=m1可得22第22頁，共67頁，2023年，2月20日，星期四可得23第23頁，共67頁，2023年，2月20日，星期四（2）求余項。記

Rn(x)=f(x)-P3(x)項x0，x2是2個零點,x1是二重零點，設Rn(x)=K(x)(x-x0)(x-x1)2(x-x2)其中K(x)待定。設x≠x0，x1，x2時，作輔助函數(shù)它在插值區(qū)間內(nèi)有5個零點。由羅爾定理知，24第24頁，共67頁，2023年，2月20日，星期四其中，ζ在插值區(qū)間內(nèi)，且與x有關(guān)。因此，帶入得25第25頁，共67頁，2023年，2月20日，星期四4.3差商、差分和牛頓（Niuton）插值多項式拉格朗日插值法的缺點：插值多項式中的基函數(shù)li(x),(i=0,1,2…n)都依賴于全部插值節(jié)點，對某點x*處的近似值，無法預先估計，而且當增加或減少節(jié)點時，必須全部重新計算。26第26頁，共67頁，2023年，2月20日，星期四4.3.1差商及牛頓插值多項式假設f(x0)=y0,f(x1)=y1,構(gòu)造線性插值函數(shù)N1(x),使N1(x0)=y0,N1(x1)=y1由直線方程點斜式可得：令則27第27頁，共67頁，2023年，2月20日，星期四現(xiàn)推廣到3個點(x0,y0,),(x1,y1),(x2,y2,)的情況，構(gòu)造二次插值函數(shù)N2(x),使由插值條件：28第28頁，共67頁，2023年，2月20日，星期四可以推廣到n+1個點(x0,y0,),(x1,y1),…(xn,yn)的情況。為了簡化插值公式，引入差商概念定義設已知函數(shù)f(x)在n+1個互異節(jié)點x0,x1,…,xn上的函數(shù)值分別為f(x0),f(x1)…f(xn)稱為f(x)關(guān)于x0,x1的一階差商，稱29第29頁，共67頁，2023年，2月20日，星期四為f(x)關(guān)于x0,x1,x2的二階差商，稱為f(x)關(guān)于x0,x1,…,xn的n階差商特別，f(xi)為f(x)關(guān)于xi的零階差商，記為f[xi]。30第30頁，共67頁，2023年，2月20日，星期四差商的性質(zhì)(1)對稱性(2)如果f(x,x0,x1,…,xk)

是x的m次多項式，則f(x,x0,x1,…,xk,xk+1)是x的m-1次多項式(3)若f(x)屬于Cn[a,b]，且xi屬于[a,b]，(i=0,1,…,n)互異，則有31第31頁，共67頁，2023年，2月20日，星期四4.3.1差商及牛頓插值多項式牛頓插值多項式根據(jù)定義，把x看為[a,b]上一點，那么把后一式帶入前一式，可得32第32頁，共67頁，2023年，2月20日，星期四4.3.1差商及牛頓插值多項式式中可以看到，因為所以于是滿足插值條件，且不次數(shù)超過n因此，Nn(x)被稱作n次的牛頓插值多項式，Rn(x)為插值余項33第33頁，共67頁，2023年，2月20日，星期四牛頓插值多項式的優(yōu)點（1）遞推性（2）牛頓插值中各項系數(shù)就是函數(shù)f(x)的各階均差，通過均差表便于計算kxkf(xk)一階均差二階均差三階均差…..0x0f(x0)1x1f(x1)f(x0,x1)2x2f(x2)f(x1,x2)f(x0,x1,x2)3x3f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)4x4f(x4)f(x3,x4)f(x2,x3,x4)f(x1,x2,x3,x4)...34第34頁，共67頁，2023年，2月20日，星期四4.3.1差商及牛頓插值多項式例5已知試用線性插值和拋物插值求的近似值。解：先構(gòu)造差商表x一階均差二階均差10010(11-10)/(121-100)=0.04761912111（0.043478-0.047619）/44=-0.00009411(12-11)/(144-121)=0.04347814412...35第35頁，共67頁，2023年，2月20日，星期四利用牛頓插值公式得：用拋物插值得：36第36頁，共67頁，2023年，2月20日，星期四4.3.2差分及等距節(jié)點插值公式在牛頓插值公式公式中，如果節(jié)點等距分布，差商及牛頓插值公式可以進一步簡化：定義設fi=f(xi),xi=x0+ih,,(i=0,1,2,…,n)，記分別稱為f(x)在xi處以步長為h的一階向前差分和一階向后差分，簡稱一階差分37第37頁，共67頁，2023年，2月20日，星期四二階向前差分和向后差分定義為：一般地，可定義m階向前差分及m階向后差分為：特別定義38第38頁，共67頁，2023年，2月20日，星期四一般地，i階均差與i階向前差分之間的關(guān)系為：由于：同理，i階均差與i階向后差分之間的關(guān)系為：39第39頁，共67頁，2023年，2月20日，星期四這樣，把上面兩式帶入牛頓差商插值多項式，可得等距節(jié)點下的前插和后插公式。若有節(jié)點，

xi=x0+ih,,(i=0,1,2,…,n)，要計算x0附近的函數(shù)f(x)的值，令x=x0+th，(0≤t≤1)結(jié)合前面帶入可得牛頓前插公式：余項為40第40頁，共67頁，2023年，2月20日，星期四牛頓后插公式作變換x=xn+th,(-1≤t≤0)余項為41第41頁，共67頁，2023年，2月20日，星期四4.4分段線性插值例：在[1,1]上考察的Ln(x)。取Ln(x)f(x)分段低次插值n

越大，端點附近抖動越大，稱為Runge現(xiàn)象42第42頁，共67頁，2023年，2月20日，星期四分段線性插值定義：設f(x)在給定的n+1個互異節(jié)點上的函數(shù)值為f(xi)=yi,(i=0,1,2,…,n),S1(x)為區(qū)間[a,b]上的函數(shù)，如果S1(x)滿足下列條件：S1(x)是在區(qū)間內(nèi)地每個小區(qū)間[xi,xi+1],(i=0,1,2,…,n)的線性函數(shù)；S1(xi)=yi,(i=0,1,2,…,n)S1(xi)是插值區(qū)間[a,b]上的連續(xù)函數(shù)則稱S1(x)是插值區(qū)間[a,b]上的分段線性插值函數(shù)43第43頁，共67頁，2023年，2月20日，星期四幾何意義：在每個小區(qū)間[xi,xi+1],(i=0,1,2,…,n)上，作連接點(xi,yi)與(xi+1,yi+1)的直線。函數(shù)S1(x)在區(qū)間[xi-1,xi)(i=0,1,2,…,n)上的表達式為：函數(shù)S1(x)在區(qū)間[xi-1,xi)(i=0,1,2,…,n)上的表達式為分段線性插值44第44頁，共67頁，2023年，2月20日，星期四如果用基函數(shù)表示，S1(x)在插值區(qū)間[a,b]上的表達式為：分段線性插值45第45頁，共67頁，2023年，2月20日，星期四分段線性插值余項定理：設f(x)在給定的互異節(jié)點xi上的函數(shù)值為f(xi)=yi,(i=0,1,2,…,n),f(x)屬于C1[a,b],

f’’(x)在[a,b]上存在，S1(x)為插值區(qū)間[a,b]上的、由數(shù)據(jù)(xi,yi)(i=0,1,2,…,n)構(gòu)成的分段線性插值函數(shù)。則,46第46頁，共67頁，2023年，2月20日，星期四分段線性插值余項例：設f(x)=1/(1+x2),在[-5,5]上取n=10，按等間距節(jié)點求線性插值函數(shù)S1(x)與f(x)的值，并估計誤差。解：h=(5-(-5))/10=1在區(qū)間[xi-1,xi](i=0,1,2,…,n)上的表達式為

由分段插值函數(shù)定義得47第47頁，共67頁，2023年，2月20日，星期四分段線性插值余項48第48頁，共67頁，2023年，2月20日，星期四分段線性插值余項由于f(x)=1/(1+x2),則令得f’’(x)的極值點為0，1，-1，于是49第49頁，共67頁，2023年，2月20日，星期四4.5樣條插值函數(shù)高次插值：計算復雜,可能出現(xiàn)不收斂現(xiàn)象,Runge現(xiàn) 象;分段線性插值:計算簡單,一致收斂,但光滑性不足;樣條函數(shù)插值:分段多項式,光滑連接50第50頁，共67頁，2023年，2月20日，星期四4.5.1三次樣條插值函數(shù)定義：設f(x)在區(qū)間[a,b]上給定n+1個節(jié)點a=x0<x1<…<xn=b.若函數(shù)S(x)滿足:S(x)在每一個小區(qū)間[xi,xi+1],(i=0,1,2,…,n-1)上是三次多項式；S(x)在[a,b]上有連續(xù)二階導數(shù).則稱S(x)為三次樣條函數(shù)51第51頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)設三次樣條函數(shù)表達式為:其中系數(shù)A,B,C,D為待定,需要滿足的條件為:52第52頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)定義：設f(x)在區(qū)間[a,b]上給定n+1個節(jié)點a=x0<x1<…<xn=b及函數(shù)y=f(x)在這些節(jié)點上的值yi=f(xi)(i=0,1,…,n).若3次樣條函數(shù)S(x)滿足一下插值條件:則稱S(x)為三次樣條插值函數(shù)53第53頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)求解條件：需求4n個未知數(shù),目前有4n-2個條件,通常還需加上邊界條件,通常有下面兩種:

當n大時,計算量非常大54第54頁，共67頁，2023年，2月20日，星期四4.5.2三次樣條插值函數(shù)求解求解條件：需求4n個未知數(shù),目前有4n-2個條件,通常還需加上邊界條件,通常有下面三種:已知端點一階導數(shù)已知端點二階導數(shù)特別地,若稱為自然邊界條件周期性邊界條件55第55頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)求解例：已知函數(shù)f(x)在三個點處的值為f(-1)=1,f(0)=0,f(1)=1,在區(qū)間[-1,1]上,求f(x)在自然邊界條件下的三次樣條插值函數(shù)解:已將區(qū)間分成兩個子區(qū)間[-1,0],[0,1],故設已由插值條件和連續(xù)條件得:56第56頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)求解已由內(nèi)節(jié)點x=0處,S’(x),S’’(x)連續(xù)且都為零得:由邊界條件得:57第57頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)求解最后解得:從而方程為:58第58頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)求解設S(x)在節(jié)點xi處的一階導數(shù)為mi,即S’(xi)=mi(i=0,1,2,…,n)，因為在每個小區(qū)間[xi,xi+1]上都是三次多項式，因此，可以將S(x)表示成整個區(qū)間上的分段兩點三次Hermite插值多項式，當x屬于[xi-1,xi]，且hi=xi+1-xi時59第59頁，共67頁，2023年，2月20日，星期四三次樣條插值函數(shù)求解對S(x)求二次導數(shù)，并整理得于是60第60頁，