第四章多項式插值與數(shù)值逼近

第四章多項式插值與數(shù)值逼近第一頁，共四十二頁，編輯于2023年，星期五

實際問題中經(jīng)常要涉及到函數(shù)值的計算問題： （1）如果函數(shù)表達(dá)式本身比較復(fù)雜，且需要多次重復(fù)計算時，計算量會很大；（2）有的函數(shù)甚至沒有表達(dá)式，只是一種表格函數(shù)，而我們需要的函數(shù)值可能不在該表格中。對于這兩種情況，我們都需要尋找一個計算方便且表達(dá)簡單的函數(shù)來近似代替，這就是數(shù)值逼近問題。

問題背景第二頁，共四十二頁，編輯于2023年，星期五§1插值問題

/*InterpolationProblem*/（插值的定義）已知定義于區(qū)間上的實值函數(shù)在個互異節(jié)點

處的函數(shù)值，若函數(shù)集合中的函數(shù)滿足則稱為在函數(shù)集合中關(guān)于節(jié)點的一個插值函數(shù)，并稱為被插值函數(shù),[a,b]為插值區(qū)間，為插值節(jié)點，（*）式為插值條件。設(shè)外插法：內(nèi)插法：用計算被插值函數(shù)在點處的近似值用計算被插值函數(shù)在點處的近似值第三頁，共四十二頁，編輯于2023年，星期五插值類型代數(shù)插值：集合為多項式函數(shù)集x0x1x2x3x4xg(x)

f(x)幾何意義：有理插值：集合為有理分式函數(shù)集三角插值：集合為三角函數(shù)集第四頁，共四十二頁，編輯于2023年，星期五代數(shù)插值的存在唯一性設(shè)即代入插值條件：第五頁，共四十二頁，編輯于2023年，星期五方程組的系數(shù)矩陣是Vandermonde矩陣方程組存在唯一解，因此滿足插值條件(*)

的不超過n次的插值多項式是唯一存在的.第六頁，共四十二頁，編輯于2023年，星期五截斷誤差插值余項設(shè)在區(qū)間[a,b]上連續(xù)，在區(qū)間[a,b]上存在,

是滿足插值條件（*）的不超過n次的插值多項式，則對存在，滿足其中。且當(dāng)在區(qū)間[a,b]有上界時，有代數(shù)插值的插值余項/*Remainder*/第七頁，共四十二頁，編輯于2023年，星期五注意這里是對

t

求導(dǎo)證明：設(shè)結(jié)論顯然成立時構(gòu)造輔助函數(shù)則有個互異零點、由羅爾(Roll)定理在區(qū)間（a,b）上至少有n+1個互異零點在區(qū)間（a,b）上至少有n個互異零點以此類推，反復(fù)利用Roll定理在區(qū)間（a,b）上至少有1個零點第八頁，共四十二頁，編輯于2023年，星期五而注：（1）插值誤差與節(jié)點和之間的距離有關(guān)；

（2）如果本身為多項式，其插值函數(shù)為本身。

（3）通常不能確定,而是估計,x(a,b)

將作為誤差估計上限。第九頁，共四十二頁，編輯于2023年，星期五§2代數(shù)插值多項式的構(gòu)造方法一、拉格朗日多項式

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

次多項式使得條件：無重合節(jié)點，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可見P1(x)是過(x0

,y0)和(x1,y1

)兩點的直線。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl稱為拉氏基函數(shù)

/*LagrangeBasis*/，滿足條件li(xj)=ij第十頁，共四十二頁，編輯于2023年，星期五與有關(guān)，而與無關(guān)n

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij；然后令==niiinyxlxP0)()(，則顯然有Pn(xi)=

yi

。li(x)每個li(x)

有n

個根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial節(jié)點f第十一頁，共四十二頁，編輯于2023年，星期五若記第十二頁，共四十二頁，編輯于2023年，星期五例如也是一個插值多項式，其中可以是任意多項式。（2）Lagrange插值多項式結(jié)構(gòu)對稱，形式簡單.（3）誤差估計注：（1）若不將多項式次數(shù)限制為n

，則插值多項式不唯一。（4）當(dāng)插值節(jié)點增加時，拉氏基函數(shù)需要重新計算，

n較大時，計算量非常大,故常用于理論分析。第十三頁，共四十二頁，編輯于2023年，星期五Quiz:

給定xi=i+1,i=0,1,2,3,4,5.下面哪個是l2(x)的圖像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC第十四頁，共四十二頁，編輯于2023年，星期五例1：已知分別利用sinx的1次、2次Lagrange

插值計算sin50

并估計誤差。解：n=1分別利用x0,x1

以及x1,x2

計算利用這里而sin50=0.7660444…)185(50sin10pL0.77614利用sin50

0.76008,選擇要計算的x

在區(qū)間的內(nèi)部，插值效果較好。第十五頁，共四十二頁，編輯于2023年，星期五高次插值通常優(yōu)于低次插值n=2)185(50sin20pL0.76543sin50=0.7660444…但絕對不是次數(shù)越高就越好，嘿嘿……第十六頁，共四十二頁，編輯于2023年，星期五反插值問題已知定義于區(qū)間上的單調(diào)連續(xù)函數(shù)在個互異節(jié)點處的函數(shù)值，若函數(shù)值已知，如何求？即求因此可以看作如下插值問題：已知定義于區(qū)間上的連續(xù)函數(shù)在個互異節(jié)點處的函數(shù)值，求函數(shù)值第十七頁，共四十二頁，編輯于2023年，星期五

xi

1.0

1.4

1.8

2.0yi=f(xi)

-2.0

-0.8

0.4

1.2例2：已知單調(diào)連續(xù)函數(shù)在如下采樣點的函數(shù)值：求方程在[1，2]內(nèi)根的近似值。解：第十八頁，共四十二頁，編輯于2023年，星期五二、

牛頓插值

/*Newton’sInterpolation*/Lagrange

插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)li(x)

都需重新算過。將Ln(x)改寫成的形式，希望每加一個節(jié)點，只附加一項上去即可。????差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商第十九頁，共四十二頁，編輯于2023年，星期五11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實上其中差商的值與xi

的順序無關(guān)！第二十頁，共四十二頁，編輯于2023年，星期五差商性質(zhì)

/*Propertyofdivideddifference*/性質(zhì)1即其中證明：數(shù)學(xué)歸納法n=1n=2第二十一頁，共四十二頁，編輯于2023年，星期五同理歸納，結(jié)論成立性質(zhì)2差商具有對稱性，即的值與節(jié)點的順序無關(guān)。由性質(zhì)1易知第二十二頁，共四十二頁，編輯于2023年，星期五性質(zhì)3如果的k階差商是的m次多項式，則的k+1階差商是的m-1次多項式。證明：上式右端的分子是的m次多項式，記為則為m-1次多項式性質(zhì)4第二十三頁，共四十二頁，編輯于2023年，星期五牛頓插值

/*Newton’sInterpolation*/已知定義于區(qū)間上的連續(xù)函數(shù)在個互異節(jié)點處的函數(shù)值n次Lagrange

插值多項式可表示為：其中第二十四頁，共四十二頁，編輯于2023年，星期五12…………n+11+(x

x0)2+……+(x

x0)…(x

xn1)n+1Nn(x)Rn(x)ai=

f[x0,…,xi]3第二十五頁，共四十二頁，編輯于2023年，星期五注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余項也相同，即

實際計算過程為（建立差商表）f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]……f[xn2,xn1,xn]f[x0,…,xn]

xn+1

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn第二十六頁，共四十二頁，編輯于2023年，星期五例3：已知函數(shù)的函數(shù)表：

xi

1

2

3

4

5yi=f(xi)

1

4

7

8

6寫出4次Newton插值多項式解：構(gòu)造差商表第二十七頁，共四十二頁，編輯于2023年，星期五對?(x)=(1+25x2)-1,在區(qū)間[-1,1]上取等距節(jié)點xi=-1+ih,i=0,1,…,10,h=0.2,作?(x)關(guān)于節(jié)點xi(i=0,1,…,10)的10次插值多項式L10(x),如圖所示看下面的例子補充分段插值多項式xyo1-10.511.5y=L10(x)這個現(xiàn)象被稱為Runge現(xiàn)象.表明高次插值的不穩(wěn)定性.實際上,很少采用高于7次的插值多項式.

§1分段Lagrange插值取節(jié)點ax0<x1<…<xnb,hi=xi-xi-1(i=1,2,…,n),插值條件yk=(xk),k=0,1,…,n.第二十八頁，共四十二頁，編輯于2023年，星期五

1.分段線性插值設(shè)S1(x)是滿足插值條件的分段一次多項式,則有S1(x)是平面上以點(xi,yi)(i=0,1,…,n)為節(jié)點的折線.若(x)C2[a,b],則當(dāng)x[xi-1,xi]時,有若記

,對任一x[a,b]都有可見,當(dāng)h0時,分段線性插值S1(x)收斂于(x).第二十九頁，共四十二頁，編輯于2023年，星期五

2.三次樣條插值給定節(jié)點a=x0<x1<…<xn=b,及其上的函數(shù)值yk=(xk),k=0,1,…,n.就是給出平面上n+1個點(xi,yi),i=0,1,…,n.xyo

定義6.1

給定節(jié)點a=x0<x1<…<xn=b,及其上的函數(shù)值yk=(xk),k=0,1,…,n.如果函數(shù)S(x)滿足

(1)S(x)是一個分段的三次多項式且S(xk)=yk;

(2)S(x)是連續(xù)的二階可導(dǎo)函數(shù)。則稱S(x)是區(qū)間[a,b]上的三次樣條插值函數(shù).第三十頁，共四十二頁，編輯于2023年，星期五

S(x)在區(qū)間[xi-1,xi]上是三次多項式,S(x)=aix3+bix2+cix+di,有4個待定系數(shù),要確定S(x)共有4n個待定系數(shù).由S(xi)=yi,i=0,1,…,n,有2n個條件.再由S(xi-0)=S(xi+0),i=1,2…,n-1,有n-1個條件及S(xi-0)=S(xi+0),i=1,2…,n-1,有n-1個條件共有4n-2個條件.第三十一頁，共四十二頁，編輯于2023年，星期五為了得到唯一的三次樣條函數(shù),通?？稍趨^(qū)間[a,b]的端點x0=a,xn=b上各加一個條件,稱為邊界條件.常用的邊界條件有

(1)S(x0)=y0,S(xn)=yn;

(2)S(x0)=y0,S(xn)=yn;

(3)假設(shè)(x)是以b-a為周期的周期函數(shù),這時要求

S(x0+0)=S(xn-0)

S(x0+0)=S(xn-0)

S(x0+0)=S(xn-0)這樣確定的S(x)為周期樣條函數(shù).

第三十二頁，共四十二頁，編輯于2023年，星期五最佳平方逼近若存在，使

用均方誤差最小作為度量標(biāo)準(zhǔn)，研究函數(shù)f(x)∈C[a，b]的逼近多項式，就是這一節(jié)要討論的最佳平方逼近問題。

就是f(x)在[a，b]上的最佳平方逼近多項式.我們要研究是否存在?

如何計算?第三十三頁，共四十二頁，編輯于2023年，星期五

正交多項式記區(qū)間[a,b]上所有連續(xù)函數(shù)的全體為C[a,b],可以證明C[a,b]是一個線性空間,把所有次數(shù)不超過n的多項式全體記為Pn,則Pn是C[a,b]的子空間.若(x),g(x)C[a,b],

則稱

為(x)與g(x)的內(nèi)積,記為(,g),滿足

(1)(,g)=(g,);

(2)(c,g)=c(,g);

(3)(1+2,g)=(1,g)+(2,g);若(,g)=0,稱(x)與g(x)正交,記為g.利用內(nèi)積可以定義函數(shù)的平方模第三十四頁，共四十二頁，編輯于2023年，星期五下面介紹幾個常用的正交多項式

1.Legendre多項式是區(qū)間[-1,1]上的正交多項式,且滿足:

(2)有三項遞推關(guān)系

(n+1)Ln+1(x)=(2n+1)xLn(x)-nLn-1(x),n1

L0(x)=1,L1(x)=x

(1)(Lm,Ln)=第三十五頁，共四十二頁，編輯于2023年，星期五

2.Chebyshev多項式

Tn(x)=cos(narccosx)x[-1,1],n=0,1,2,…是區(qū)間[-1,1]上權(quán)函數(shù)(x)=的正交多項式,且滿足:

(1)(Tm,Tn)=第三十六頁，共四十二頁，編輯于2023年，星期五

(2)有三項遞推關(guān)系

Tn+1(x)=2xTn(x)-Tn-1(x)n=1,2,3,…

T0(x)=1,T1(x)=x

(3)Tn(x)在[-1,1]上的n個零點為第三十七頁，共四十二頁，編輯于2023年，星期五

3.Laguere多項式是區(qū)間[0,+)上權(quán)函數(shù)(x)=e-x

的正交多項式,且滿足:

(1)(Lm,Ln)=

Ln+1(x)=(2n+1-x)Ln(x)-n2Ln-1(x),n1

L0(x)=1,L1(x)=1-x第三十八頁，共四十二頁，編輯于2023年，星期五

4.Hermite多項式是區(qū)間(-,+)上權(quán)函數(shù)(x)=的正交多項式,且滿足:

(1)(Hm,Hn)=

Hn+1(x)=2xHn(x)-2nHn-1(x),n1

H0(x)=1,H1(x)=2x第三十九頁，共四十二頁，編輯于2023年，星期五

數(shù)據(jù)擬合的最小二乘法

§1數(shù)據(jù)擬合問題經(jīng)常由觀察或測試可得到y(tǒng)(