計算方法第三章插值法

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

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

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

階差商為：第20頁，課件共55頁，創(chuàng)作于2023年2月給定n+1個點的函數(shù)值則牛頓插值公式為：第21頁，課件共55頁，創(chuàng)作于2023年2月差商的計算簡表：第22頁，課件共55頁，創(chuàng)作于2023年2月例子：用0、30、45、60、90五個點作出sinx牛頓插值多項式。做差商表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月牛頓插值的截斷誤差：第25頁，課件共55頁，創(chuàng)作于2023年2月例子：用0、90、180、270、360五個點作出sinx牛頓插值多項式。做差商表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ì)差商的計算公式：通過比較插值多項式的Lagrange形式和Newton形式即可得。第28頁，課件共55頁，創(chuàng)作于2023年2月差商的對稱性：差商的線性性：第29頁，課件共55頁，創(chuàng)作于2023年2月由于n次插值多項式是唯一的，所以牛頓插值公式與Lagrange插值多項式一樣，這意味著余項也一樣，Lagrange余項為：所以牛頓余項也一樣，第30頁，課件共55頁，創(chuàng)作于2023年2月差商與導數(shù)的關(guān)系重節(jié)點差商推論：當n個節(jié)點全為同一個點，牛頓插值變成泰勒多項式。第31頁，課件共55頁，創(chuàng)作于2023年2月差商的導數(shù)n

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

n

次多項式，k≤n

時k

階差商是n-k

次多項式，k>n

時k

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

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

第36頁，課件共55頁，創(chuàng)作于2023年2月1、推廣牛頓插值法如果已知某個點i的，則插值節(jié)點應視為個相同節(jié)點，并注意到k+1重節(jié)點的差商第37頁，課件共55頁，創(chuàng)作于2023年2月例子：已知關(guān)于函數(shù)y=f(x)的函數(shù)值、導數(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個不同的節(jié)點處的函數(shù)值和導數(shù)值：求次數(shù)不超過2n-1次的多項式設想其具有形式：要求：第39頁，課件共55頁，創(chuàng)作于2023年2月由條件可得：此外，由得：第40頁，課件共55頁，創(chuàng)作于2023年2月同理：由，可得：最后，得到埃爾米特插值公式：第41頁，課件共55頁，創(chuàng)作于2023年2月特別，當n=2

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

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