計(jì)算方法第三章插值法

計(jì)算方法第三章插值法第1頁，課件共55頁，創(chuàng)作于2023年2月假設(shè)已經(jīng)獲得n+1點(diǎn)上的函數(shù)值即提供了一張數(shù)據(jù)表

如何利用這張表求f(x)在其他給定點(diǎn)上的合理的近似值呢?

第2頁，課件共55頁，創(chuàng)作于2023年2月在實(shí)驗(yàn)數(shù)據(jù)的處理、難以計(jì)算的函數(shù)的逼近、數(shù)值微積分等方面需要解決這樣的問題，這是數(shù)值逼近中的一個(gè)基本問題。一個(gè)自然的想法是找一個(gè)簡單易計(jì)算的函數(shù)φ(x)，使得將φ(x)作為f(x)在一定范圍內(nèi)的近似函數(shù)，對于這個(gè)范圍內(nèi)的某個(gè)給定點(diǎn)a，取f(a)≈φ(a)。這種近似方法稱為插值法。φ(x)稱為f(x)的以{xi}(i=0,1,···,n)為插值節(jié)點(diǎn)的插值函數(shù)。插值節(jié)點(diǎn)上所給的函數(shù)值稱為樣本值。第3頁，課件共55頁，創(chuàng)作于2023年2月φ(xi)=yi稱為插值條件。函數(shù)值待求的點(diǎn)稱為插值點(diǎn)。插值節(jié)點(diǎn)所界定的范圍稱為插值區(qū)間。如果所給插值點(diǎn)位于插值區(qū)間之內(nèi)，這種插值過程稱為內(nèi)插，否則稱為外插。若用多項(xiàng)式來作為插值函數(shù)，則稱其為插值多項(xiàng)式。通常用n次多項(xiàng)式作為n+1個(gè)插值條件的插值多項(xiàng)式。如果插值條件只是給出節(jié)點(diǎn)的函數(shù)值，稱為拉格朗日插值，如果既有函數(shù)值也有節(jié)點(diǎn)處函數(shù)的導(dǎo)數(shù)值，稱為埃爾米特插值。第4頁，課件共55頁，創(chuàng)作于2023年2月因式定理：多項(xiàng)式P(x)具有r次因式(x-a)r的充要條件是最一般的插值條件：是重插值節(jié)點(diǎn)，定理：給定上述n+1個(gè)插值條件，則n次插值多項(xiàng)式是存在唯一的。第5頁，課件共55頁，創(chuàng)作于2023年2月設(shè)函數(shù)y=f(x)在閉區(qū)間[a,b]上有n+1階導(dǎo)數(shù)，滿足前面的一般插值條件，且插值節(jié)點(diǎn)各不相同，則插值截?cái)嗾`差為第6頁，課件共55頁，創(chuàng)作于2023年2月證明思路：構(gòu)造輔助函數(shù)，用羅爾定理。第7頁，課件共55頁，創(chuàng)作于2023年2月值得注意的是在較大區(qū)間上進(jìn)行插值時(shí)，誤差可能會(huì)很大！另外，一般情況下，外推不如內(nèi)插好！第8頁，課件共55頁，創(chuàng)作于2023年2月第二節(jié)Lagrange插值公式插值條件是Lagrange插值實(shí)質(zhì)上是求通過上面n+1個(gè)點(diǎn)的n次多項(xiàng)式。第9頁，課件共55頁，創(chuàng)作于2023年2月一次插值：問題為求一次多項(xiàng)式，即一次函數(shù)，過以下兩點(diǎn)：容易求出，該函數(shù)為：第10頁，課件共55頁，創(chuàng)作于2023年2月一般插值問題：求過n+1個(gè)點(diǎn)的不超過n次多項(xiàng)式。稱為Lagrange插值基函數(shù)，滿足：第11頁，課件共55頁，創(chuàng)作于2023年2月求過n+1個(gè)點(diǎn)的不超過n次多項(xiàng)式的插值多項(xiàng)式是唯一的。插值公式的誤差為：第12頁，課件共55頁，創(chuàng)作于2023年2月計(jì)算程序框圖第13頁，課件共55頁，創(chuàng)作于2023年2月第三節(jié)逐次線性插值函數(shù)y=f(x)在節(jié)點(diǎn)上的插值多項(xiàng)式記為，則有第14頁，課件共55頁，創(chuàng)作于2023年2月Aitken（埃特肯）算法Neville（列維爾）算法第15頁，課件共55頁，創(chuàng)作于2023年2月Aitken（埃特肯）算法第16頁，課件共55頁，創(chuàng)作于2023年2月Neville（列維爾）算法第17頁，課件共55頁，創(chuàng)作于2023年2月例子：求方程x3-2x-5=0在(2,3)內(nèi)的根思路:設(shè)y=f(x)=x3-2x-5，其反函數(shù)為x=f-1(y)，則根為x*

=f-1(0)

。先用3=f-1(16)，2=f-1(-1)插值，得N0,1(y)≈f-1(y),計(jì)算N0,1(0)=2.058823,f(2.058823)=-0.39，以-0.39為新的節(jié)點(diǎn)，繼續(xù)……yixiNi,i+1(0)Ni,i+1,i+2(0)Ni,i+1,i+2,i+3(0)163-122.058823-0.392.058232.0965892.0956590.0122.0956592.0945292.0945542.0945531.51E-52.094553第18頁，課件共55頁，創(chuàng)作于2023年2月第四節(jié)牛頓插值設(shè)插值點(diǎn)為插值多項(xiàng)式形如稱為Newton形式的插值多項(xiàng)式。第19頁，課件共55頁，創(chuàng)作于2023年2月差商概念：設(shè)函數(shù)f(x)，定義函數(shù)在兩個(gè)不同點(diǎn)的一階差商為三個(gè)不同點(diǎn)的二階差商為：在點(diǎn)處K+1

階差商為：第20頁，課件共55頁，創(chuàng)作于2023年2月給定n+1個(gè)點(diǎn)的函數(shù)值則牛頓插值公式為：第21頁，課件共55頁，創(chuàng)作于2023年2月差商的計(jì)算簡表：第22頁，課件共55頁，創(chuàng)作于2023年2月例子：用0、30、45、60、90五個(gè)點(diǎn)作出sinx牛頓插值多項(xiàng)式。做差商表00300.50.016667450.70710.013807-0.000063556600.8660.010595-0.00010707-0.00000079010.0044658-0.0001362-0.00000049第23頁，課件共55頁，創(chuàng)作于2023年2月第24頁，課件共55頁，創(chuàng)作于2023年2月牛頓插值的截?cái)嗾`差：第25頁，課件共55頁，創(chuàng)作于2023年2月例子：用0、90、180、270、360五個(gè)點(diǎn)作出sinx牛頓插值多項(xiàng)式。做差商表009010.011111800-0.01111-1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70第26頁，課件共55頁，創(chuàng)作于2023年2月第27頁，課件共55頁，創(chuàng)作于2023年2月差商的性質(zhì)差商的計(jì)算公式：通過比較插值多項(xiàng)式的Lagrange形式和Newton形式即可得。第28頁，課件共55頁，創(chuàng)作于2023年2月差商的對稱性：差商的線性性：第29頁，課件共55頁，創(chuàng)作于2023年2月由于n次插值多項(xiàng)式是唯一的，所以牛頓插值公式與Lagrange插值多項(xiàng)式一樣，這意味著余項(xiàng)也一樣，Lagrange余項(xiàng)為：所以牛頓余項(xiàng)也一樣，第30頁，課件共55頁，創(chuàng)作于2023年2月差商與導(dǎo)數(shù)的關(guān)系重節(jié)點(diǎn)差商推論：當(dāng)n個(gè)節(jié)點(diǎn)全為同一個(gè)點(diǎn)，牛頓插值變成泰勒多項(xiàng)式。第31頁，課件共55頁，創(chuàng)作于2023年2月差商的導(dǎo)數(shù)n

次多項(xiàng)式的的1階差商是n-1次多項(xiàng)式。推論：設(shè)p(x)是

n

次多項(xiàng)式，k≤n

時(shí)k

階差商是n-k

次多項(xiàng)式，k>n

時(shí)k

階差商為零。第32頁，課件共55頁，創(chuàng)作于2023年2月差分設(shè)函數(shù)，定義為該函數(shù)在i

點(diǎn)的一階向前差分，記為類似地，定義二階向前差分為：K階差分為：此差分稱為向前差分。第33頁，課件共55頁，創(chuàng)作于2023年2月類似地，向后差分定義為：中心差分定義為：第34頁，課件共55頁，創(chuàng)作于2023年2月差商與差分的關(guān)系：等距節(jié)點(diǎn)時(shí)第35頁，課件共55頁，創(chuàng)作于2023年2月第五節(jié)帶導(dǎo)數(shù)的插值問題的提出：如果在已知節(jié)點(diǎn)處不僅知道函數(shù)值，同時(shí)還知道導(dǎo)數(shù)值，這樣，插值多項(xiàng)式就要求在已知節(jié)點(diǎn)處與函數(shù)值和導(dǎo)數(shù)值都相等。這就是所謂埃爾米特（Hermite）插值。

第36頁，課件共55頁，創(chuàng)作于2023年2月1、推廣牛頓插值法如果已知某個(gè)點(diǎn)i的，則插值節(jié)點(diǎn)應(yīng)視為個(gè)相同節(jié)點(diǎn)，并注意到k+1重節(jié)點(diǎn)的差商第37頁，課件共55頁，創(chuàng)作于2023年2月例子：已知關(guān)于函數(shù)y=f(x)的函數(shù)值、導(dǎo)數(shù)值xif(xi)f(xi,xi+1)f(xi,xi+1,xi+2)3階差商4階差商5階差商-100-4-40-4040-403-11-222-101-253121第38頁，課件共55頁，創(chuàng)作于2023年2月2、構(gòu)造基函數(shù)法已知函數(shù)在n個(gè)不同的節(jié)點(diǎn)處的函數(shù)值和導(dǎo)數(shù)值：求次數(shù)不超過2n-1次的多項(xiàng)式設(shè)想其具有形式：要求：第39頁，課件共55頁，創(chuàng)作于2023年2月由條件可得：此外，由得：第40頁，課件共55頁，創(chuàng)作于2023年2月同理：由，可得：最后，得到埃爾米特插值公式：第41頁，課件共55頁，創(chuàng)作于2023年2月特別，當(dāng)n=2

時(shí)，三階埃爾米特多項(xiàng)式為：第42頁，課件共55頁，創(chuàng)作于2023年2月埃爾米特插值公式唯一。誤差估計(jì)：設(shè)被插值函數(shù)在插值區(qū)間上2n次連續(xù)可導(dǎo)，則在n個(gè)節(jié)點(diǎn)上的2n-1次插值多項(xiàng)式的余項(xiàng)為：特別，對于2個(gè)節(jié)點(diǎn)3次插值，余項(xiàng)為：第43頁，課件共55頁，創(chuàng)作于2023年2月例子：第44頁，課件共55頁，創(chuàng)作于2023年2月第45頁，課件共55頁，創(chuàng)作于2023年2月如用距離較小的兩個(gè)點(diǎn)插值，效果會(huì)好得多第46頁，課件共55頁，創(chuàng)作于2023年2月第47頁，課件共55頁，創(chuàng)作于2023年2月第六節(jié)樣條函數(shù)由于被插值函數(shù)高階導(dǎo)數(shù)未知，因此，如果高階導(dǎo)數(shù)隨階數(shù)增長出現(xiàn)無限增長，則由誤差公式可知，高階插值公式就不一定無限接近被插值函數(shù)。這稱為龍格（Runge)現(xiàn)象。所以，在進(jìn)行多項(xiàng)式插值時(shí)，不宜進(jìn)行高次多項(xiàng)式插值。一個(gè)解決的途徑是分段低次插值。第48頁，課件共55頁，創(chuàng)作于2023年2月樣條函數(shù)：給定區(qū)間一個(gè)劃分如函數(shù)S(x)滿足下面條件：（1）在每個(gè)小區(qū)間上為m次多項(xiàng)式；（2）S(x)直至m－1階導(dǎo)數(shù)在整個(gè)區(qū)間上連續(xù)。則稱S(x)是關(guān)于該劃分的m次樣條函數(shù)，劃分點(diǎn)稱為節(jié)點(diǎn)，m＝3時(shí)，就是最常用的3次樣條函數(shù)。第49頁，課件共55頁，創(chuàng)作于2023年2月樣條函數(shù)插值：對給定的插值條件，尋找合適的樣條函數(shù)作為插值函數(shù)，使其滿足插值條件。3次樣條插值三彎矩方法的基本思想：將樣條函數(shù)在每一個(gè)子區(qū)間端點(diǎn)的二階導(dǎo)數(shù)值當(dāng)作參數(shù)，則用這兩個(gè)二階導(dǎo)數(shù)值可以將樣條函數(shù)表示出來，再利用銜接條件，即每一段樣條函數(shù)在相鄰兩個(gè)子區(qū)間端點(diǎn)處的二階導(dǎo)數(shù)相等，建立求解二階導(dǎo)數(shù)的方程組。第50頁，課件共55頁，創(chuàng)作于2023年2月設(shè)S(x)在每個(gè)小區(qū)間端點(diǎn)的二階導(dǎo)數(shù)為：則：記，將上式積分兩次，并利用端點(diǎn)函數(shù)值已知，有：第51頁，課件共55頁，創(chuàng)作于2023年2月我們注意到，在相鄰的兩個(gè)子區(qū)間和的共同端點(diǎn)處，樣條函數(shù)一階導(dǎo)數(shù)相等，經(jīng)過化簡，最后得到：第52頁，課件共55頁，創(chuàng)作于2023年2月注意到上面的方程組總共只有N－1個(gè)方程，而未知數(shù)卻共有

N+1個(gè)，因此，要求解方程，還需要補(bǔ)充兩個(gè)條件（即兩個(gè)方程），通常有以下幾種方案之一:1、給出端點(diǎn)一階導(dǎo)數(shù)值，這相當(dāng)于增加兩個(gè)方程；2、給定端點(diǎn)二階導(dǎo)數(shù)值，得方程：特別，令二階導(dǎo)數(shù)在端點(diǎn)為零，得第53頁，課件共5