計(jì)算方法第三章r

第三章插值法

第一節(jié)插值多項(xiàng)式的基本概念假設(shè)已經(jīng)獲得若干點(diǎn)上的函數(shù)值即提供了一張數(shù)據(jù)表

如何利用這張表求某個(gè)給定點(diǎn)上的函數(shù)值呢?插值方法所要研究的就是這個(gè)課題。

通常用多項(xiàng)式來(lái)作為近似函數(shù)，稱為插值多項(xiàng)式。數(shù)據(jù)表中的函數(shù)值為已知的節(jié)點(diǎn)稱為插值節(jié)點(diǎn)，插值節(jié)點(diǎn)上所給的函數(shù)值稱為樣本值。函數(shù)值待求的點(diǎn)稱為插值點(diǎn)。插值節(jié)點(diǎn)所界定的范圍稱為插值區(qū)間。如果所給插值點(diǎn)位于插值區(qū)間之內(nèi)，這種插值過(guò)程稱為內(nèi)插，否則稱為外插。如果插值條件只是給出節(jié)點(diǎn)的函數(shù)值，稱為拉格朗日插值，如果既有函數(shù)值也有節(jié)點(diǎn)處函數(shù)的導(dǎo)數(shù)值，稱為埃爾米特插值。因式定理：多項(xiàng)式P(x)具有r次因式(x-a)r的充要條件是P(a)=P‘(a)=……=P(a)(r-1)

=0最一般的插值條件：是重根，定理：一旦插值條件給定，則插值多項(xiàng)式是唯一的。設(shè)函數(shù)y=f(x)在閉區(qū)間[a,b]上有n+1階導(dǎo)數(shù)，滿足前面的一般插值條件，且插值節(jié)點(diǎn)各不相同，則插值截?cái)嗾`差為證明思路：構(gòu)造輔助函數(shù)，用羅爾定理。值得注意的是在較大區(qū)間上進(jìn)行插值時(shí)，誤差可能會(huì)很大！另外，一般情況下，外推不如內(nèi)插好！第二節(jié)Lagrange插值公式插值條件是Lagrange插值實(shí)質(zhì)上是求通過(guò)上面n+1個(gè)點(diǎn)的n次多項(xiàng)式。一次插值：?jiǎn)栴}為求一次多項(xiàng)式，即一次函數(shù)，過(guò)以下兩點(diǎn)：容易求出，該函數(shù)為：二次插值：?jiǎn)栴}為求二次多項(xiàng)式，即二次函數(shù)，過(guò)以下三點(diǎn)：容易求出，該函數(shù)為：一般插值問(wèn)題：求過(guò)n+1個(gè)點(diǎn)的不超過(guò)n次多項(xiàng)式。稱為L(zhǎng)agrange插值基函數(shù)，滿足：?jiǎn)栴}:過(guò)n+1個(gè)點(diǎn)的Lagrange插值多項(xiàng)式是否唯一？滿足n+1個(gè)插值條件的n次多項(xiàng)式是唯一的；滿足n+1個(gè)插值條件的多項(xiàng)式不是唯一的；插值公式的誤差為：計(jì)算程序框圖第三節(jié)逐次線性插值函數(shù)y=f(x)在節(jié)點(diǎn)上的插值多項(xiàng)式記為，則有Aitken（埃特肯）算法Neville（列維爾）算法Aitken（埃特肯）算法Neville（列維爾）算法例子：求方程在(2,3)內(nèi)的根思路，用反函數(shù)yx163-122.058823-0.392.058232.0965892.0956590.0121.51E-52.0956592.0945532.0945292.0945542.094553第四節(jié)牛頓插值差商設(shè)函數(shù)f(x)，定義函數(shù)在兩個(gè)不同點(diǎn)的一階差商為三個(gè)不同點(diǎn)的二階差商為：在點(diǎn)處K+1

階差商為：給定n+1個(gè)點(diǎn)的函數(shù)值，則牛頓插值公式為：差商的計(jì)算簡(jiǎn)表：例子：用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牛頓插值的截?cái)嗾`差：例子：用0、30、45、60、90五個(gè)點(diǎn)作出sinx牛頓插值多項(xiàng)式。做差商表009010.011111800-0.01111-1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70差商的計(jì)算公式：差商的對(duì)稱性：差商的線性由于n次插值多項(xiàng)式是唯一的，所以牛頓插值公式與Lagrange插值多項(xiàng)式一樣，這意味著余項(xiàng)也一樣，Lagrange余項(xiàng)為：所以牛頓余項(xiàng)也一樣，差商與導(dǎo)數(shù)的關(guān)系重節(jié)點(diǎn)差商推論：當(dāng)n個(gè)節(jié)點(diǎn)全為同一個(gè)點(diǎn)，牛頓插值變成泰勒多項(xiàng)式。差商的導(dǎo)數(shù)n次多項(xiàng)式的的1階差商是n-1次多項(xiàng)式。推論：設(shè)p(x)是n次多項(xiàng)式，kn時(shí)k階差商是n-k次多項(xiàng)式，k>n時(shí)k階差商為零。差分設(shè)函數(shù)，定義為該函數(shù)在i

點(diǎn)的一階差分，記為類似地，定義二階差分為：K階差分為：此差分稱為向前差分。類似地，向后差分定義為：中心差分定義為：差商與差分的關(guān)系：等距節(jié)點(diǎn)時(shí)第五節(jié)帶導(dǎo)數(shù)的插值問(wèn)題的提出：如果在已知節(jié)點(diǎn)處不僅知道函數(shù)值，同時(shí)還指導(dǎo)導(dǎo)數(shù)值，這樣，插值多項(xiàng)式就要求在已知節(jié)點(diǎn)處與函數(shù)值和導(dǎo)數(shù)值都相等。這就是所謂埃爾米特插值，記為H(x)1、牛頓插值如果已知某個(gè)點(diǎn)i的，則插值節(jié)點(diǎn)應(yīng)視為個(gè)相同節(jié)點(diǎn)，并注意到k+1重節(jié)點(diǎn)的差商例子：已知關(guān)于函數(shù)y=f(x)的函數(shù)值、導(dǎo)數(shù)值-100-4-40-4040-403-11-222-101-253121已知函數(shù)在n個(gè)不同的節(jié)點(diǎn)處的函數(shù)值和導(dǎo)數(shù)值：求次數(shù)不超過(guò)2n-1次的多項(xiàng)式設(shè)想該多項(xiàng)式具有形式：由條件可得：此外，由得：同理：由，可得：最后，得到埃爾米特插值公式：特別，當(dāng)n=2時(shí)，三階埃爾米特多項(xiàng)式為：埃爾米特插值公式唯一。誤差估計(jì)，設(shè)被插值函數(shù)在插值區(qū)間上2n次連續(xù)可導(dǎo)，則在n個(gè)節(jié)點(diǎn)上的2n-1次插值多項(xiàng)式的余項(xiàng)為：特別，對(duì)于2個(gè)節(jié)點(diǎn)3次插值，余項(xiàng)為：例子：如用距離較小的兩個(gè)點(diǎn)插值，效果會(huì)好得多第六節(jié)樣條函數(shù)由于被插值函數(shù)高階導(dǎo)數(shù)未知，因此，如果高階導(dǎo)數(shù)隨階數(shù)增長(zhǎng)出現(xiàn)無(wú)限增長(zhǎng)，則由誤差公式可知，高階插值公式就不一定無(wú)限接近被插值函數(shù)。這稱為龍格現(xiàn)象。所以，在進(jìn)行多項(xiàng)式插值時(shí)，不宜進(jìn)行高次多項(xiàng)式插值。一個(gè)解決的途徑是分段低次插值。龍格現(xiàn)象樣條函數(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ù)。3次樣條函數(shù)的基本思想：將樣條函數(shù)在每一個(gè)子區(qū)間端點(diǎn)的二階導(dǎo)數(shù)值當(dāng)作參數(shù)，則用這兩個(gè)二階導(dǎo)數(shù)值可以將樣條函數(shù)表示出來(lái)，再利用銜接條件，即每一段樣條函數(shù)在相鄰兩個(gè)子區(qū)間端點(diǎn)處的二階導(dǎo)數(shù)相等，建立求解二階導(dǎo)數(shù)的方程組。設(shè)S(x)在每個(gè)小區(qū)間端點(diǎn)的二階導(dǎo)數(shù)為：則：記，將上式積分兩次，并利用端點(diǎn)函數(shù)值已知，有：我們注意到，在相鄰的兩個(gè)子區(qū)間和的共同端點(diǎn)處，樣條函數(shù)一階導(dǎo)數(shù)相等，經(jīng)過(guò)化簡(jiǎn)，最后得到：注意到上面的方程組總共只有N－1個(gè)方程，而未知數(shù)卻共有N個(gè)，因此，要求解方程，還需要兩個(gè)條件（即兩個(gè)方程），通常有以下幾種方案:1、給出端點(diǎn)一階導(dǎo)數(shù)值，這相當(dāng)于增加兩個(gè)方程；2、給定端點(diǎn)二階導(dǎo)數(shù)值，得方程：特別，令二階導(dǎo)數(shù)在端點(diǎn)為零，得3、樣條件函數(shù)在第一后最后一個(gè)區(qū)間上為二次多項(xiàng)式，即樣條函數(shù)在第一和最后一個(gè)區(qū)間上的二階導(dǎo)數(shù)為常數(shù)，得兩個(gè)方程：總之，可以將方程組統(tǒng)一寫(xiě)為：4、周期性條件（這只有在給的初值滿足時(shí)才能用），此時(shí)，由周期性，，就得到兩個(gè)方程；第一個(gè)方程為，第二個(gè)方程為最后一個(gè)方程為：最后，方程組為：小結(jié)插值法，其目的是利用節(jié)點(diǎn)上的值，構(gòu)造通過(guò)這些節(jié)點(diǎn)的多項(xiàng)式，從原則上說(shuō)，利用n+1個(gè)節(jié)點(diǎn)的值，可以構(gòu)造n次多項(xiàng)式，而且這種構(gòu)造是唯一的！利用待定系數(shù)法，將節(jié)點(diǎn)值帶入后，得到一個(gè)n+1階線性方程，即可求出多項(xiàng)式。為便于在計(jì)算機(jī)上實(shí)現(xiàn)，本章引入了Lagrange插值公式和牛頓插值公式，各有千秋，Lagrange插值公式便于理解和記憶，牛頓公式便于計(jì)算機(jī)計(jì)算。但必須指出的是，不管用什么方法插值，所得到的插值公式實(shí)際上是完全一樣的，包括上面所說(shuō)的待定系數(shù)法，這就是插值公式唯一性。唯一性的一個(gè)直接推論就是各種插值公式的余項(xiàng)完全一樣，都是Lagrange余項(xiàng)。Lagrange公式的構(gòu)造思想非常重要！后面的埃爾米特公式出發(fā)點(diǎn)也是利用了這一點(diǎn)。如果節(jié)點(diǎn)上不僅已知函數(shù)值，同時(shí)還已知函數(shù)的導(dǎo)數(shù)值，即要求插值多項(xiàng)式在節(jié)點(diǎn)上與函數(shù)具有相同的函數(shù)值和導(dǎo)數(shù)值，這時(shí)要用埃爾米特公式。高次插值有時(shí)會(huì)引起較大誤差，對(duì)此，解決的方案是分段低次插值。如果對(duì)插值多項(xiàng)式要求較好的光滑性，這時(shí)就需要