東北農(nóng)業(yè)大學(xué)《數(shù)值分析》課件-第二章

東北農(nóng)業(yè)大學(xué)

數(shù)值分析

第二章

第二章插值法

§1引言

§2拉格朗日插值公式

§3逐步線性插值§4牛頓(Newton)插值§5埃爾米特(Hermite)插值§6有理函數(shù)插值§1引言發(fā)展歷史應(yīng)用插值問(wèn)題的提出插值問(wèn)題所需研究的問(wèn)題等距節(jié)點(diǎn)內(nèi)插公式劉焯（隋公元544－610年）不等距節(jié)點(diǎn)內(nèi)插公式張遂（唐公元683－727年）等距節(jié)點(diǎn)一般插值公式

Newton&Gregory(17世紀(jì)）非等距節(jié)點(diǎn)一般插值公式J.L.Lagrange(18世紀(jì)）發(fā)展歷史應(yīng)用對(duì)觀測(cè)數(shù)據(jù)的處理函數(shù)的近似表示曲線曲面擬合導(dǎo)出其它數(shù)值方法的依據(jù)（如數(shù)值積分、數(shù)值微分、微分方程數(shù)值解等）以近似計(jì)算函數(shù)值為例來(lái)說(shuō)明散點(diǎn)上的函數(shù)值，即已知函數(shù)表例：設(shè)在實(shí)際問(wèn)題中，某些變量之間的函數(shù)關(guān)系是存在的，但通常不能用式子表示，只能由實(shí)驗(yàn)、觀測(cè)得到在一系列離如何計(jì)算？我們希望尋求一個(gè)簡(jiǎn)單且易于計(jì)算的函數(shù)來(lái)近似，即，一般可選為多多項(xiàng)式、三角多項(xiàng)式、有理函數(shù)或樣條函數(shù)等。有些函數(shù)雖有表達(dá)式，但較復(fù)雜，計(jì)算函數(shù)值不經(jīng)濟(jì)，這時(shí)也希望用簡(jiǎn)單的函數(shù)來(lái)逼近。插值問(wèn)題的提出

已知函數(shù)在區(qū)間上有，求一個(gè)多定義，且已知，其中項(xiàng)式,使其滿足即要求該多項(xiàng)式的函數(shù)曲線要經(jīng)過(guò)

上已知的這n+1個(gè)點(diǎn)

同時(shí)在其它點(diǎn)上估計(jì)誤差為

YX研究問(wèn)題若滿足條件的存在，又如何構(gòu)造？滿足插值條件的多項(xiàng)式是否存在，唯一？用近似代替的誤差估計(jì)？§2拉格朗日插值插值多項(xiàng)式的存在唯一性

拉格朗日插值多項(xiàng)式插值基函數(shù)插值基函數(shù)的構(gòu)造

n次拉格朗日型插值多項(xiàng)式截?cái)嗾`差數(shù)值實(shí)例拉格朗日插值多項(xiàng)式的優(yōu)缺點(diǎn)插值多項(xiàng)式的存在唯一性Theorem.存在唯一的n

次多項(xiàng)式（1.1)滿足條件證明：由(1.1)可得(1.2)（1.2）為一個(gè)你n＋1未知量的線性方程組，要證明插值多項(xiàng)式存在唯一，只要證明參數(shù)存在且唯一，即只要證明其系數(shù)行列式不為零即可。

方程組（1.2）的系數(shù)行列式為

此為范德蒙行列式。利用行列式性質(zhì)可得系數(shù)行列式為

由于時(shí)，故所有因子，于是

即插值多項(xiàng)式存在唯一。

由方程組（1.2）求的系數(shù)，計(jì)算量大，且難于得到的簡(jiǎn)單表達(dá)式，下面通過(guò)找插值基函數(shù)的方法，可得到插值多項(xiàng)式的簡(jiǎn)單表達(dá)式。拉格朗日插值多項(xiàng)式1.插值基函數(shù)定義：若n次多項(xiàng)式在n+1個(gè)節(jié)點(diǎn)上滿足條件則稱這n+1個(gè)n次多項(xiàng)式為節(jié)點(diǎn)上的n次插值基函數(shù)。2.基函數(shù)的構(gòu)造由上述定義，知存在常數(shù)，使得由，可以定出，進(jìn)而得到：令則

于是可改寫成

3.n次拉格朗日型插值多項(xiàng)式是n+1個(gè)n次插值基本多項(xiàng)式的線性組合，相應(yīng)的組合系數(shù)是即是一個(gè)次數(shù)不超過(guò)n的多項(xiàng)式,且滿足，。拉格朗日插值多項(xiàng)式的截?cái)嗾`差

若在[a,b]上用多項(xiàng)式來(lái)近似代替函數(shù)f(x),其截?cái)嗾`差記作，即也稱為插值多項(xiàng)式的余項(xiàng)，關(guān)于插值余項(xiàng)估計(jì)，有以下定理：定理：設(shè)函數(shù)y=f(x)的n階導(dǎo)數(shù)y=f(n)(x)在[a,b]上連續(xù)，y=f(n+1)(x)在(a,b)上存在，插值節(jié)點(diǎn)為a≤x0<x1<…<xn≤b,

是n次拉格朗日插值多項(xiàng)式，則對(duì)任意x[a,b]有：其中(a,b),

，證明：由插值多項(xiàng)式的定義，顯然有構(gòu)造輔助函數(shù)有。反復(fù)利用Rolle定理，存在(a,b),

使得g(n+1)()=0,即，結(jié)論成立。數(shù)值實(shí)例例．求過(guò)點(diǎn)(2,0)(4,3)(6,5)(8,4)(10,1)的拉格朗日型插值多項(xiàng)式。解：用4次插值多項(xiàng)式對(duì)5個(gè)點(diǎn)插值

于是有例.已知sin0.32=0.314567,sin0.34=0.333487,

sin0.36=0.352274,用Lagrange插值計(jì)算sin0.3367的值，并估計(jì)截?cái)嗾`差。解：f(x)=sinx,取于是有可以發(fā)現(xiàn)，結(jié)果有六位有效數(shù)字的sinx表完全一致。截?cái)嗾`差為其中故有Lagrange插值公式優(yōu)缺點(diǎn)優(yōu)點(diǎn)：結(jié)果清晰、緊湊，適用于作理論分析、應(yīng)用；當(dāng)節(jié)點(diǎn)個(gè)數(shù)有所變動(dòng)，整個(gè)插值公式發(fā)生變化，在實(shí)際應(yīng)用時(shí)不方便?！?逐步線性插值

拋物插值的逐步線性插值A(chǔ)itken插值Neville算法數(shù)值實(shí)例小結(jié)1.拋物插值的逐步線性插值給定如下三個(gè)數(shù)據(jù)點(diǎn)逐步線性插值（Aitken插值）具體步驟如下：Step1.將分別對(duì)兩點(diǎn)作線性插值，得step2.對(duì)兩點(diǎn)作線性插值，得顯然插值節(jié)點(diǎn)；插值節(jié)點(diǎn)；插值節(jié)點(diǎn)。2.n次Aitken插值設(shè)給定數(shù)據(jù)表

構(gòu)造n次多項(xiàng)式，步驟如下：step1.將分別對(duì)作線性插值，得step2.將分別對(duì)作線性插值，得step3.將分別對(duì)作線性插值，得……stepn.對(duì)兩點(diǎn)

作線性插值，得可列表如下(以四次Aitken插值為例）：四次插值三次插值二次插值一次插值3.Neville算法可列表如下(以四次插值為例）：一次插值二次插值三次插值四次插值構(gòu)造n次多項(xiàng)式，步驟如下：step1.分別對(duì)與

兩兩作線性插值，得step2.分別對(duì)與兩兩作線性插值，得step3.分別對(duì)與兩兩作線性插值，得……stepn.對(duì)兩點(diǎn)

線性插值，易證得4.數(shù)值實(shí)例例.已知列表函數(shù)x1234y0-5-63用求f(2.5)的近似值。解(1)用Aitken算法列表法求解其中(2)用Neville算法求解其中5.小結(jié)由上例可以看出，若需提高插值多項(xiàng)式的次數(shù)而增加新插值點(diǎn)時(shí)，只須增加一些線性插值項(xiàng)，且前面計(jì)算結(jié)果無(wú)需重算，故Aitken插值、Neville算法具有算法承襲性。另外，這兩種算法對(duì)于求多項(xiàng)式在某點(diǎn)x處得值較有效，但不適合求多項(xiàng)式本身?！?Newton插值公式

差分及其性質(zhì)差商及其性質(zhì)Newton插值公式及誤差估計(jì)拉格朗日插值與牛頓插值的比較等距節(jié)點(diǎn)的Newton向前插值公式等距節(jié)點(diǎn)的Newton向后插值公式1.差分及其性質(zhì)

插值節(jié)點(diǎn)為等距節(jié)點(diǎn)：如右圖所示h稱為步長(zhǎng)，函數(shù)在節(jié)點(diǎn)處的函數(shù)值為

1.1差分的概念一階向前差分一階向后差分一階中心差分

n階向前差分如同理可以定義。Δ稱為向前差分算子，▽表示向后差分算子，表示中心差分算子，如果用函數(shù)表上的值，一階中心差分應(yīng)寫成

除差分算子外，常用的算子符號(hào)還有：不變算子I:;移位算子E：由上面各種算子的定義可得算子間的關(guān)系：由可得1.2差分的性質(zhì)（步長(zhǎng)均為h）

性質(zhì)1:各階差分均可用函數(shù)值表示，如

性質(zhì)2:可用各階差分表示函數(shù)值。性質(zhì)3:設(shè)是n次多項(xiàng)式，則有性質(zhì)4:各種差分之間可以互化。如2.差商定義及其性質(zhì)2.1差商的定義對(duì)于具有n+1個(gè)插值點(diǎn)的情況，可把插值多項(xiàng)式表示為其中為待定系數(shù)，可由插值條件

確定。

由得依次可得到。為寫出系數(shù)的一般表達(dá)式，現(xiàn)引入差商（均差）定義。定義：稱為函數(shù)關(guān)于節(jié)點(diǎn)的一階差商，記為稱為函數(shù)關(guān)于節(jié)點(diǎn)的二階差商。遞歸地用k-1階差商來(lái)定義k階差商，稱為關(guān)于k+1個(gè)節(jié)點(diǎn)的k階差商。對(duì)于重節(jié)點(diǎn)，定義2.2差商（均差）的性質(zhì)性質(zhì)1

k階差商可以表示成k+1個(gè)函數(shù)值的線性組合,即

可用歸納法證明。例:性質(zhì)2差商與節(jié)點(diǎn)的排列順序無(wú)關(guān)(差商的對(duì)稱性)，即

性質(zhì)3

若是的n次多項(xiàng)式,則一階差商是的次多項(xiàng)式,二階差商是的次多項(xiàng)式;一般地,函數(shù)的階差商是的次多項(xiàng)式,而當(dāng)時(shí),階差商為零。

證：若是的n

次多項(xiàng)式，則也是n

次多項(xiàng)式，且有，則可分解為其中為n-1次多項(xiàng)式，故有為n-1次多項(xiàng)式。性質(zhì)4若，則性質(zhì)5在等距插值的情況下,由定義可得出差分和差商有如下關(guān)系：利用差商的定義,可以用遞推法來(lái)計(jì)算差商。差商表如下：

一階差商

二階差商

三階差商

如要再增加一個(gè)節(jié)點(diǎn),計(jì)算四階差商時(shí),只須表中再要增加一行即可。

3牛頓插值公式

根據(jù)差商定義，把看成上的一點(diǎn)，可得

只要把后一式代入前一式，得:

最后一項(xiàng)中,差商部分含有,為余項(xiàng)部分,記作

而前n+1項(xiàng)中,差商部分都不含有,因而前n+1項(xiàng)是關(guān)于的n次多項(xiàng)式,記作于是,上式記為這就是牛頓插值公式。由牛頓插值公式與（2.1）式比較知：易證牛頓插值公式插值節(jié)點(diǎn)。

例2:已知求滿足以上插值條件的牛頓型插值多項(xiàng)式。解:12340-5-63一階差商二階差商三階差商12340-5-63-5-19251由上述差商表對(duì)角線上取得的值則牛頓三次插值多項(xiàng)式為

4.拉格朗日插值與牛頓插值的比較

與均是n次多項(xiàng)式,且均滿足插值條件:由插值多項(xiàng)式的唯一性,,因而,兩個(gè)公式的余項(xiàng)是相等的,即則可知n階差商與導(dǎo)數(shù)的關(guān)系如下：（2）當(dāng)插值多項(xiàng)式從n-1次增加到n次時(shí),拉格朗日型插值必須重新計(jì)算所有的基本插值多項(xiàng)式;而對(duì)于牛頓型插值,只需用表格再計(jì)算一個(gè)n階差商,然后加上一項(xiàng)即可。（3）牛頓型插值余項(xiàng)公式對(duì)是由離散點(diǎn)給出或?qū)?shù)不存在時(shí)均適用。

5Newton向前插值公式將牛頓差商（均差）插值公式中各階差商（均差）用相應(yīng)差分代替，就可得到各種形式的等距結(jié)點(diǎn)插值公式。如果節(jié)點(diǎn)為，要計(jì)算附近點(diǎn)的函數(shù)的值，可令于是

把其代入牛頓插值公式，再利用差分與差商之間的關(guān)系，得牛頓向前插值公式其余項(xiàng)為：6Newton向后插值公式如果要計(jì)算附近點(diǎn)的函數(shù)的值，插值點(diǎn)應(yīng)按的次序排列，可令，同理可得牛頓向后插值公式：

其余項(xiàng)為

向前、向后差分表

一階差分

二階差分三階n階差分差分

例已知函數(shù)的數(shù)值表：試作出的三次Newton向前向后插值公式，并計(jì)算、的近似值。解：由令0123121764構(gòu)造差分表如下：有上表，得012312176411547143218牛頓三次向前、向后插值公式分別為得§5Hermite插值公式Hermite插值問(wèn)題的提出三次Hermite插值插值基函數(shù)構(gòu)造法

滿足插值條件的牛頓插值法誤差估計(jì)2n+1次Hermite插值多項(xiàng)式1.Hermite插值問(wèn)題的提出由于理論與實(shí)踐的需要，在構(gòu)造插值函數(shù)時(shí)，不但要求在節(jié)點(diǎn)上函數(shù)值相等，而且還要求它的（高階）導(dǎo)數(shù)值也相等（即要求在節(jié)點(diǎn)上具有一定的光滑度），使得插值函數(shù)與被插函數(shù)貼近程度更好，滿足這種要求的插值多項(xiàng)式就是Hermite插值多項(xiàng)式，有時(shí)也稱為具有重節(jié)點(diǎn)插值或切觸插值。下面具體討論三次情形。2.三次Hermite插值問(wèn)題：求作三次多項(xiàng)式，使之滿足：稱之為兩點(diǎn)三次Hermite插值問(wèn)題，稱滿足插值條件（2.1）的為三次Hermite插值多項(xiàng)式。下面采用構(gòu)造基函數(shù)及牛頓插值的方法來(lái)確定多項(xiàng)式。2.1基函數(shù)構(gòu)造法構(gòu)造基函數(shù)使之滿足則即為所求。由插值條件，有由（2.3）可設(shè)再由（2.2）可求得同理可得特別的，在時(shí)，得到以區(qū)間端點(diǎn)為插值條件得三次Hermite插值多項(xiàng)式：其中2.2Newton插值法

滿足插值條件（2.1）式得插值問(wèn)題可視為重節(jié)點(diǎn)Newton插值問(wèn)題，且則其中各階差商可由定義直接求得，即2.3誤差估計(jì)由Newton插值法，可直接得到三次Hermite

插值問(wèn)題的截?cái)嗾`差為：于是有下述定理定理：設(shè)是以為插值節(jié)點(diǎn)的三次Hermite插值多項(xiàng)式，在內(nèi)存在，其中是包含的任一區(qū)間，則對(duì)任意給定的，總存在依賴于的點(diǎn)，使3.2n+1次Hermite插值多項(xiàng)式

給定n+1個(gè)節(jié)點(diǎn)和相應(yīng)的函數(shù)值和導(dǎo)數(shù)值：則可構(gòu)造2n+1次Hermite插值多項(xiàng)式滿足條件：1）是不超過(guò)2n+1次多項(xiàng)式；2）用類似于前面的方法在n+1個(gè)節(jié)點(diǎn)上構(gòu)造2n+1次Hermite插值多項(xiàng)式為其中插值基函數(shù)（定義如前）為定理：設(shè)是以為插值節(jié)點(diǎn)的2n+1次Hermite插值多項(xiàng)式，在內(nèi)存在，其中是包含節(jié)點(diǎn)的任一區(qū)間，則對(duì)任意給定的，總存在依賴于的點(diǎn)，使§6有理函數(shù)插值研究有理插值問(wèn)題的理論背景有理函數(shù)插值的基本概念有理插值問(wèn)題的提出研究的問(wèn)題有理插值的存在性連分式插值連分式插值在圖像處理中的應(yīng)用1.研究有理插值問(wèn)題的理論背景前面討論了用多項(xiàng)式逼近函數(shù)，它是一種計(jì)算簡(jiǎn)便的逼近工具，但當(dāng)函數(shù)在某點(diǎn)附近無(wú)界，或者當(dāng)而趨于某一定值時(shí)，采用多項(xiàng)式插值是不恰當(dāng)?shù)模@是因?yàn)槎囗?xiàng)式不能反映在某點(diǎn)附近無(wú)界的函數(shù)性態(tài)，而當(dāng)時(shí)，多項(xiàng)式的值總是趨于無(wú)窮，但有理分式函數(shù)，如卻能刻劃這些函數(shù)性態(tài)。2.有理函數(shù)插值2.1問(wèn)題的提出設(shè)給定在m+n+1個(gè)互異節(jié)點(diǎn)上的值，所謂有理函數(shù)插值問(wèn)題，即尋求有理分式函數(shù)使之滿足條件2.2研究的問(wèn)題

表面上有m+n+2個(gè)待定參數(shù)，，但實(shí)際上只有m+n+1個(gè)待定參數(shù)，故從插值條件（2.1）可得關(guān)于系數(shù)的m+n+1個(gè)方程組。下面必須研究三個(gè)問(wèn)題：解的存在及唯一性；如何構(gòu)造有理插值函數(shù)；誤差估計(jì)問(wèn)題。2.3有理分式函數(shù)的基本概念設(shè)有兩個(gè)分式函數(shù)若存在一個(gè)非零常數(shù)a，使得則稱與恒等，記為.若則稱它們是等價(jià)的，記為（以后均視為同一函數(shù)）.有理插值問(wèn)題的不一定總是存在的。例1.給定型值點(diǎn)，求形如的有理插值。解由插值條件，易求得取則得于是顯然當(dāng)時(shí)，有，而與是值為3的同一函數(shù)的兩種不同表現(xiàn)形式。在幾何上當(dāng)時(shí)，是一條平行于x軸的直線，它不可能通過(guò)型值點(diǎn)，故它不是（2.1）的解。因此，滿足插值條件（2.1）的是不存在的。定理1插值問(wèn)題（2.1）若有解，則其解必唯一。證明：設(shè)有兩個(gè)有理函數(shù)均滿足插值條件(2.1),即由此可推出表明次數(shù)不超過(guò)m+n的多項(xiàng)式有1+m+n個(gè)互異零點(diǎn)。由代數(shù)基本定理，知由等價(jià)性定義知2.4有理插值的存在性定理2若（2.1）對(duì)應(yīng)的齊次線性方程組有非平凡解存在，為使?jié)M足插值條件（2.1）的最簡(jiǎn)有理分式存在，必須且只須方程組（2.4）的任意非平凡解在約去一切公因子后得到的互質(zhì)多項(xiàng)式仍是方程組（2.4）的解。3.連分式插值3.1連分式設(shè)和為兩個(gè)復(fù)數(shù)列，稱形如：的分式為連分式（Continuedfraction）,記做：

或，稱為上式的第n

次漸近連分式(AsymptoticContinuedFractions)，或第n項(xiàng)截?cái)噙B分式(TruncatedContinuedFractions)。連分式是一種有效的逼近工具。例如：由可得令第n項(xiàng)截?cái)噙B分式為因此，可用下列連分式逼近函數(shù)：取時(shí)，得到的一組近似值而的Maclaurin展開(kāi)式為取，函數(shù)的精確值為0.4，可以分別用來(lái)逼近，得下表：顯然，收斂速度更快。因此，可得到結(jié)論：函數(shù)的連分式（非線性）展開(kāi)與線性展開(kāi)相比，有更好的逼近效果。n123450.480.480.36480.38710.38690.40220.38690.39960.40920.40013.2Thiele型連分式插值

定義3.2.1

稱下述形式的連分式：

為Thiele型連分式.定義3.2.2

設(shè)是一實(shí)點(diǎn)集，函數(shù)在有定義，令

稱為函數(shù)在處的i

階逆差商。定理設(shè)其中為函數(shù)在處的k

階逆差商,且則有證明：反復(fù)利用逆差商的定義知證畢。定義3.2.3如果連分式滿足則稱該連分式為函數(shù)的型Thiele插值連分式。例給定型值點(diǎn)求，使之滿足條件解構(gòu)造逆差商表：x-2-1012

y-2-1-101得xy一階二階三階四階-2-2012-2-1-101123/24/31491/31/4-12分段低次插值多項(xiàng)式插值的問(wèn)題分段線性插值分段三次埃爾米特插值小結(jié)1.多項(xiàng)式插值的問(wèn)題前面介紹了構(gòu)造插值公式的方法，并分析了它們的余項(xiàng)。在實(shí)際應(yīng)用插值函數(shù)作近似計(jì)算時(shí)，總希望插值公式余項(xiàng)的絕對(duì)值小一些，即使得逼近的精度好。從表達(dá)式看，似乎提高插值多項(xiàng)式的次數(shù)便可達(dá)到目的，但實(shí)際上并非如此。在插值過(guò)程中有兩種誤差：1）由插值函數(shù)替代被插函數(shù)所引起的截?cái)嗾`差；2）節(jié)點(diǎn)數(shù)據(jù)的誤差。這種誤差在插值過(guò)程中是否會(huì)被擴(kuò)散或放大呢？這就是插值過(guò)程的穩(wěn)定性問(wèn)題。對(duì)任意的插值節(jié)點(diǎn)，當(dāng)