東北農業大學

數值分析

第二章

第二章插值法

§1引言

§2拉格朗日插值公式

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

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

已知函數在區間上有，求一個多定義，且已知，其中項式,使其滿足即要求該多項式的函數曲線要經過

上已知的這n+1個點

同時在其它點上估計誤差為

YX研究問題若滿足條件的存在，又如何構造？滿足插值條件的多項式是否存在，唯一？用近似代替的誤差估計？§2拉格朗日插值插值多項式的存在唯一性

拉格朗日插值多項式插值基函數插值基函數的構造

n次拉格朗日型插值多項式截斷誤差數值實例拉格朗日插值多項式的優缺點插值多項式的存在唯一性Theorem.存在唯一的n

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

方程組（1.2）的系數行列式為

此為范德蒙行列式。利用行列式性質可得系數行列式為

由于時，故所有因子，于是

即插值多項式存在唯一。

由方程組（1.2）求的系數，計算量大，且難于得到的簡單表達式，下面通過找插值基函數的方法，可得到插值多項式的簡單表達式。拉格朗日插值多項式1.插值基函數定義：若n次多項式在n+1個節點上滿足條件則稱這n+1個n次多項式為節點上的n次插值基函數。2.基函數的構造由上述定義，知存在常數，使得由，可以定出，進而得到：令則

于是可改寫成

3.n次拉格朗日型插值多項式是n+1個n次插值基本多項式的線性組合，相應的組合系數是即是一個次數不超過n的多項式,且滿足，。拉格朗日插值多項式的截斷誤差

若在[a,b]上用多項式來近似代替函數f(x),其截斷誤差記作，即也稱為插值多項式的余項，關于插值余項估計，有以下定理：定理：設函數y=f(x)的n階導數y=f(n)(x)在[a,b]上連續，y=f(n+1)(x)在(a,b)上存在，插值節點為a≤x0<x1<…<xn≤b,

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

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

使得g(n+1)()=0,即，結論成立。數值實例例．求過點(2,0)(4,3)(6,5)(8,4)(10,1)的拉格朗日型插值多項式。解：用4次插值多項式對5個點插值

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

sin0.36=0.352274,用Lagrange插值計算sin0.3367的值，并估計截斷誤差。解：f(x)=sinx,取于是有可以發現，結果有六位有效數字的sinx表完全一致。截斷誤差為其中故有Lagrange插值公式優缺點優點：結果清晰、緊湊，適用于作理論分析、應用；當節點個數有所變動，整個插值公式發生變化，在實際應用時不方便。§3逐步線性插值

拋物插值的逐步線性插值Aitken插值Neville算法數值實例小結1.拋物插值的逐步線性插值給定如下三個數據點逐步線性插值（Aitken插值）具體步驟如下：Step1.將分別對兩點作線性插值，得step2.對兩點作線性插值，得顯然插值節點；插值節點；插值節點。2.n次Aitken插值設給定數據表

構造n次多項式，步驟如下：step1.將分別對作線性插值，得step2.將分別對作線性插值，得step3.將分別對作線性插值，得……stepn.對兩點

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

兩兩作線性插值，得step2.分別對與兩兩作線性插值，得step3.分別對與兩兩作線性插值，得……stepn.對兩點

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

差分及其性質差商及其性質Newton插值公式及誤差估計拉格朗日插值與牛頓插值的比較等距節點的Newton向前插值公式等距節點的Newton向后插值公式1.差分及其性質

插值節點為等距節點：如右圖所示h稱為步長，函數在節點處的函數值為

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

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

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

性質1:各階差分均可用函數值表示，如

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

確定。

由得依次可得到。為寫出系數的一般表達式，現引入差商（均差）定義。定義：稱為函數關于節點的一階差商，記為稱為函數關于節點的二階差商。遞歸地用k-1階差商來定義k階差商，稱為關于k+1個節點的k階差商。對于重節點，定義2.2差商（均差）的性質性質1

k階差商可以表示成k+1個函數值的線性組合,即

可用歸納法證明。例:性質2差商與節點的排列順序無關(差商的對稱性)，即

性質3

若是的n次多項式,則一階差商是的次多項式,二階差商是的次多項式;一般地,函數的階差商是的次多項式,而當時,階差商為零。

證：若是的n

次多項式，則也是n

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

一階差商

二階差商

三階差商

如要再增加一個節點,計算四階差商時,只須表中再要增加一行即可。

3牛頓插值公式

根據差商定義，把看成上的一點，可得

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

最后一項中,差商部分含有,為余項部分,記作

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

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

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

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

5Newton向前插值公式將牛頓差商（均差）插值公式中各階差商（均差）用相應差分代替，就可得到各種形式的等距結點插值公式。如果節點為，要計算附近點的函數的值，可令于是

把其代入牛頓插值公式，再利用差分與差商之間的關系，得牛頓向前插值公式其余項為：6Newton向后插值公式如果要計算附近點的函數的值，插值點應按的次序排列，可令，同理可得牛頓向后插值公式：

其余項為

向前、向后差分表

一階差分

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

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

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

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

插值問題的截斷誤差為：于是有下述定理定理：設是以為插值節點的三次Hermite插值多項式，在內存在，其中是包含的任一區間，則對任意給定的，總存在依賴于的點，使3.2n+1次Hermite插值多項式

給定n+1個節點和相應的函數值和導數值：則可構造2n+1次Hermite插值多項式滿足條件：1）是不超過2n+1次多項式；2）用類似于前面的方法在n+1個節點上構造2n+1次Hermite插值多項式為其中插值基函數（定義如前）為定理：設是以為插值節點的2n+1次Hermite插值多項式，在內存在，其中是包含節點的任一區間，則對任意給定的，總存在依賴于的點，使§6有理函數插值研究有理插值問題的理論背景有理函數插值的基本概念有理插值問題的提出研究的問題有理插值的存在性連分式插值連分式插值在圖像處理中的應用1.研究有理插值問題的理論背景前面討論了用多項式逼近函數，它是一種計算簡便的逼近工具，但當函數在某點附近無界，或者當而趨于某一定值時，采用多項式插值是不恰當的，這是因為多項式不能反映在某點附近無界的函數性態，而當時，多項式的值總是趨于無窮，但有理分式函數，如卻能刻劃這些函數性態。2.有理函數插值2.1問題的提出設給定在m+n+1個互異節點上的值，所謂有理函數插值問題，即尋求有理分式函數使之滿足條件2.2研究的問題

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

或，稱為上式的第n

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

定義3.2.1

稱下述形式的連分式：

為Thiele型連分式.定義3.2.2

設是一實點集，函數在有定義，令

稱為函數在處的i

階逆差商。定理設其中為函數在處的k

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

y-2-1-101得xy一階二階三階四階-2-2012-2-1-101123/24/31491/31/4-12分段低次插值多項式插值的問題分段線性插值分段三次埃爾米特插值小結1.多項式插值的問題前面介紹了構造插值公式的方法，并分析了它們的余項。在實際應用插值函數作近似計算時，總希望插值公式余項的絕對值小一些，即使得逼近的精度好。從表達式看，似乎提高插值多項式的次數便可達到目的，但實際上并非如此。在插值過程中有兩種誤差：1）由插值函數替代被插函數所引起的截斷誤差；2）節點數據的誤差。這種誤差在插值過程中是否會被擴散或放大呢？這就是插值過程的穩定性問題。對任意的插值節點，當