代數(shù)多項(xiàng)式插值問題

4.1.1插值問題及代數(shù)多項(xiàng)式插值函數(shù)y=f(x)給出一組函數(shù)值

x:x0x1x2……xny:y0y1y2……yn其中x0,x1,x2,…,xn是區(qū)間[a,b]上的互異點(diǎn)，要構(gòu)造一個(gè)簡(jiǎn)單的函數(shù)φ(x)

作為f(x)的近似表達(dá)式，使?jié)M足

(插值原則、插值條件)

這類問題稱為插值問題。-----f(x)的插值函數(shù),

f(x)-----被插值函數(shù)x0,x1,x2,…,xn-----插值節(jié)點(diǎn)

求插值函數(shù)的方法稱為插值法。

若x∈[a,b]，需要計(jì)算f(x)的近似值φ(x),則稱x為插值點(diǎn)。

當(dāng)選擇代數(shù)多項(xiàng)式作為插值函數(shù)時(shí)，稱為代數(shù)多項(xiàng)式插值問題:代數(shù)多項(xiàng)式插值問題:設(shè)函數(shù)y=f(x)在[a,b]有定義,且已知在n+1個(gè)點(diǎn)a≤x0<x1<……<xn≤b上的函數(shù)值y0,y1,……,yn.,要求一個(gè)次數(shù)不高于n的多項(xiàng)式

使?jié)M足插值原則稱Pn(x)為f(x)的n次插值多項(xiàng)式。這樣的插值多項(xiàng)式是否存在、唯一？

定理4.1

在n+1個(gè)互異基點(diǎn)處滿足插值原則且次數(shù)不超過n的多項(xiàng)式Pn(x)是存在并唯一的。證

其系數(shù)行列式

因此方程組存在唯一的解

，因此Pn(x)存在并唯一。4.1.2插值多項(xiàng)式的誤差截?cái)嗾`差：

也稱為Pn(x)的余項(xiàng)。

定理4.2

設(shè)函數(shù)f(x)在包含基點(diǎn)x0,x1,…,xn的區(qū)間[a,b]上連續(xù)，在(a,b)上具有n+1階導(dǎo)數(shù)，Pn(x)為滿足插值原則的n次插值多項(xiàng)式，則對(duì)任一點(diǎn)x∈[a,b]，總存在相應(yīng)的點(diǎn)ξ∈(a,b)，使其中

證

當(dāng)x=xi(i=0,1,…,n)時(shí)，由插值條件知Rn(xi)=0，故結(jié)論顯然成立。當(dāng)x是[a,b]上任一個(gè)固定點(diǎn)，但不是插值基點(diǎn)時(shí)，作輔助函數(shù)

根據(jù)羅爾定理，在F(t)的兩個(gè)零點(diǎn)之間至少有一點(diǎn)使導(dǎo)數(shù)為0，即F(t)在區(qū)間[a,b]上至少有n+2個(gè)互異的零點(diǎn)x,x0,x1,…,xn。F(n+1)(ξ)=f(n+1)(ξ)=0從而結(jié)論成立。依此類推，可知F(n+1)(t)在(a,b)內(nèi)至少有一個(gè)零點(diǎn)ξ，則F

(t)在(a,b)內(nèi)至少有n個(gè)互異零點(diǎn)F

(t)在(a,b)內(nèi)至少有n+1個(gè)互異的零點(diǎn)

推論當(dāng)f(x)是次數(shù)不超過n的多項(xiàng)式時(shí)，其n次插值多項(xiàng)式就是f(x)本身。

證明因?yàn)閒(n+1)(x)=0，從而Rn(x)≡0，Pn(x)≡f(x)。誤差公式的用法：，則截?cái)嗾`差估計(jì)為

如果

設(shè)min{x0,x1,…,xn}=a，max{x0,x1,…,xn}=b當(dāng)插值點(diǎn)x∈(a,b)時(shí)稱為內(nèi)插，否則稱為外插。例若利用在100和144的值，對(duì)做一次插值，估計(jì)誤差是多少？

解插值基點(diǎn)x0=100,x1=144,插值點(diǎn)110.4.2拉格朗日插值多項(xiàng)式4.2.1線性插值和二次插值4.2.2n次拉格朗日插值4.2.1線性插值和二次插值1線性插值----n=1時(shí)的代數(shù)多項(xiàng)式插值已知f(x0)=y0，f(x1)=y1,x0≠x1xx0x1yy0y1要構(gòu)造線性函數(shù)

P1(x)=a0+a1x,使?jié)M足插值條件P1(x0)=y0,P1(x1)=y1.

（線性插值多項(xiàng)式）

（拉格朗日線性插值多項(xiàng)式）

公式的結(jié)構(gòu)：它是兩個(gè)一次函數(shù)的線性組合

（線性插值基函數(shù)）

基函數(shù)的性質(zhì)

線性插值多項(xiàng)式的截?cái)嗾`差為

ξ是在包含x,x0,x1的區(qū)間內(nèi)某數(shù)。

例1給定函數(shù)y=lnx在兩點(diǎn)10、11的值如下表，試用線性插值求ln10.5的近似值，并估計(jì)截?cái)嗾`差。

解f(x)=lnx,x0=10,x1=11,x=10.5ln10.5≈P1(10.5)=x1011y2.3032.3982

二次插值----n=2時(shí)的代數(shù)多項(xiàng)式插值已知f(x)在三個(gè)互異點(diǎn)x0,x1,x2的函數(shù)值y0,y1,y2

xx0x1x2yy0y1y2要構(gòu)造次數(shù)不超過二次的多項(xiàng)式

使?jié)M足插值條件

公式的構(gòu)造：先對(duì)每個(gè)基點(diǎn)xi構(gòu)造二次插值基函數(shù)li(i=0,1,2)，使?jié)M足

（拉格朗日二次插值多項(xiàng)式）P2(x)的截?cái)嗾`差為ξ是包含x0,x1,x2,x的區(qū)間內(nèi)某數(shù)。

例2

已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)如表所示，試求其拉格朗日插值多項(xiàng)式，并計(jì)算f(1.5)的近似值。

x012y2-14解

二次插值也稱之為拋物插值。當(dāng)三點(diǎn)(x0,y0),(x1,y1),(x2,y2)位于一條直線上時(shí)，顯然插值函數(shù)的圖形是直線。一般插值基函數(shù)的構(gòu)造思路：分析（一）分析（二）簡(jiǎn)略記號(hào)計(jì)算框圖：

4.3牛頓差商插值多項(xiàng)式4.3.1差商及差商表4.3.2牛頓差商型插值多項(xiàng)式目的：構(gòu)造具有如下形式的插值多項(xiàng)式：

它滿足遞推性：4.3.1差商及差商表

一階差商

二階差商

例如設(shè)

則k階差商

例如零階差商定義為函數(shù)值本身，即

差商具有對(duì)稱性：任意改變基點(diǎn)的次序后其值不變。例如

f[0,2,4]=f[2,0,4]=f[4,2,0]等等。差商表

xif(xk)1階2階3階4階

x0f(x0)

x1f(x1)f(x0,x1)

x2f(x2)f(x1,x2)f(x0,x1,x2)

x3f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)

x4f(x4)f(x3,x4)f(x2,x3,x4)f(x1,x2,x3,x4)f(x0,x1,x2,x3,x4)

┊┊

┊

┊

┊

┊……

計(jì)算規(guī)律：任一個(gè)k(≥1)階差商的數(shù)值等于一個(gè)分式的值，其分子為所求差商左側(cè)的數(shù)減去左上側(cè)的數(shù)，分母為所求差商同一行最左邊的基點(diǎn)值減去由它往上數(shù)第k個(gè)基點(diǎn)值。

注意：差商表中，對(duì)角線上的差商是構(gòu)造牛頓型插值公式的重要數(shù)據(jù)。粗線框出的部分在計(jì)算機(jī)上可存入二維數(shù)組差商表的數(shù)據(jù)構(gòu)成一個(gè)矩陣F：F00=f(x0)F10=f(x1),F11=f[x0,x1]F20=f(x2),F21=f[x1,x2],F22=f[x0,x1,x2]F30=f(x3),F31=f[x2,x3],F32=f[x1,x2,x3],F33=f[x0,x1,x2,x3]Fi,j-1=f[xi-j+1,…,xi]Fi-1,j-1=f[xi-j,,…,xi-1]計(jì)算機(jī)上計(jì)算差商表的公式

一般有Fi,j=f[xi-j,xi-j+1,…,xi-1,xi]

例4.4

已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)如表，試構(gòu)造差商表，并求f[2,4,5]及f[2,4,5,6]的值。

x02456f(x)159-413解

n=4,構(gòu)造差商表

xif(xi)1階2階3階4階0245621159-4132-13170-515-15f[2,4,5]=-5f[2,4,5,6]=54.3.2牛頓差商型插值多項(xiàng)式根據(jù)線性插值的點(diǎn)斜式牛頓差商型線性插值多項(xiàng)式：設(shè)由可得牛頓差商型二次插值多項(xiàng)式：可得牛頓差商型n次插值多項(xiàng)式(n次牛頓差商插值多項(xiàng)式)

計(jì)算牛頓差商插值多項(xiàng)式的步驟：（1）作差商表（2）根據(jù)公式計(jì)算牛頓型插值多項(xiàng)式（表中對(duì)角線上各差商值就是Pn(x)的各項(xiàng)系數(shù)）。

余項(xiàng)公式的牛頓形式：

例4.5

已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)如例4.4，試用全部基點(diǎn)構(gòu)造牛頓差商插值多項(xiàng)式，并用二次插值求f(3)的近似值。

解用全部基點(diǎn)時(shí)，n=4，先作差商表,見例4.4。

P4(x)=f(0)+f[0,2](x-0)+f[0,2,4](x-0)(x-2)+f[0,2,4,5](x-0)(x-2)(x-4)+f[0,2,4,5,6](x-0)(x-2)(x-4)(x-5)xif(xi)1階2階3階4階0245622-1317159-4130-515-151=1+2x-x(x-2)(x-4)+x(x-2)(x-4)(x-5)用二次插值求f(3)時(shí)n=2，x=3，作內(nèi)插取

x0=2,x1=4,x2=5f(3)≈P2(3)=f(2)+f[2,4](3–2)+f[2,4,5](3-2)(3-4)=7-5(3-2)(3-4)=12

若插值基點(diǎn)等距分布，牛頓型插值多項(xiàng)式還可以利用差分得到簡(jiǎn)化,。差分

設(shè)基點(diǎn)等距，

xi=x0+th,i=0,1,…,n.h稱為步長(zhǎng)。一階差分：一階向前差分、一階前差一階向后差分、一階后差二階差分：二階前差二階后差k階前差和k階后差零階差分規(guī)定為簡(jiǎn)記為例4.6

設(shè)f(x)=x2+x,取步長(zhǎng)

h=0.5,計(jì)算解

利用差分可以簡(jiǎn)化等距基點(diǎn)的牛頓型插值公式，稱為前差（或后差）插值公式。用數(shù)學(xué)歸納法可以證明前差、后差、差商之間的下述關(guān)系：△f(0)=f(0.5)-f(0)=0.75,△f(0.5)=f(1)-f(0.5)=1.25△2f(0)=△(△f(0))=△f(0.5)-△f(0)=1.25–0.75=0.5令x0=0,則x1=0.5,x2=14.4三次樣條插值4.4.1三次樣條插值函數(shù)的概念4.4.2三次樣條插值函數(shù)的求法4.4.1三次樣條插值函數(shù)的概念

樣條插值的思想：逐段選取適當(dāng)?shù)牡痛味囗?xiàng)式，按一定的光滑性要求連接起來構(gòu)成插值函數(shù)。

定義設(shè)給定區(qū)間[a,b]上n+1個(gè)點(diǎn)a=x0<x1<……<xn=b

以及相應(yīng)的函數(shù)值yi=f(xi),i=0,1,…,n.

如果函數(shù)S(x)滿足:

(1)在每個(gè)子區(qū)間

[xk,xk+1](k=0,1,…,n-1)上，S(x)是不超過三次的多項(xiàng)式，且S(xi)=yi,i=0,1,…,n.在[a,b]上連續(xù),

則稱S(x)是f(x)在基點(diǎn)x0,x1,x2,…,xn上的三次樣條插值函數(shù).

稱xoy平面上的點(diǎn)(xi,yi

)(i=0,1,…,n)為樣點(diǎn)。

例給定區(qū)間[0,3]上3個(gè)點(diǎn)的函數(shù)值f(0)=0,f(1)=2,f(3)=4,試求數(shù)a,b,c,d,使函數(shù)S(x)為給定點(diǎn)上的三次樣條插值函數(shù)。

解設(shè)

根據(jù)定義，由得d=0，故則由

得由得由得由得求得

給定n+1個(gè)樣點(diǎn)(xi,yi

)(i=0,1,…,n)

，確定一個(gè)三次樣條插值函數(shù)需要4n個(gè)獨(dú)立條件。在定義中，已指定了4n-2個(gè)條件，即所以，一般需補(bǔ)充指定2個(gè)邊界條件。

系數(shù)用結(jié)點(diǎn)處的二階導(dǎo)數(shù)表示的三次樣條函數(shù)補(bǔ)充條件4.5曲線擬合的最小二乘法4.5.1曲線擬合的最小二乘法4.5.2代數(shù)多項(xiàng)式擬合4.5.1曲線擬合的最小二乘法曲線擬合的問題：設(shè)函數(shù)y=f(x)在n個(gè)互異點(diǎn)的觀測(cè)數(shù)據(jù)為

求一個(gè)簡(jiǎn)單的近似函數(shù)φ(x)，使之“最好”地逼近f(x)，而不必滿足插值原則。稱函數(shù)y=φ(x)為經(jīng)驗(yàn)公式或擬合曲線。

xix1x2

…..xnyiy1y2

…..yn例子：（注意它與插值法的不同）

通常選擇函數(shù)類型的做法：描出散點(diǎn)圖，再根據(jù)專業(yè)知識(shí)和經(jīng)驗(yàn)來選擇φ(x)的類型。

為某類函數(shù)中線性無關(guān)的簡(jiǎn)單函數(shù)。

是待定常數(shù)，

如取就得到代數(shù)多項(xiàng)式

近似曲線在各點(diǎn)的偏差的平方和是

線性最小二乘法:使其在指定n個(gè)點(diǎn)的偏差平方和達(dá)最小。求近似函數(shù)問題轉(zhuǎn)化為求待定系數(shù)使達(dá)到極小。其中考慮超定方程組

(n>m)

即

如果有向量c使得

達(dá)到最小，則稱c為超定方程組的最小二乘解。

定理4.3

超定方程組Ac=y存在最小二乘解，且即為方程組ATAc=ATy

的解。當(dāng)A的列向量線性無關(guān)時(shí)ATA非奇異，這時(shí)有唯一的解。

稱方程組ATAc=ATy

為方程組Ac=y的正則方程組、正規(guī)方程組、法方程組

曲線擬合的最小二乘法可以看成求下述超定方程組的最小二乘解的問題:

簡(jiǎn)寫為

一般計(jì)算步驟為：(1)計(jì)算

，其中

(2)計(jì)算ATA,ATy

，形成法方程組ATAc=ATy(3)求解法方程組，輸出

c1,c2,…,cm,構(gòu)成

例已知觀測(cè)數(shù)據(jù)(1,–5),(2,0),(4,5),(5,6)，試用最小二乘法求形如的經(jīng)驗(yàn)公式。

解

作超定方程組即法方程組為求得a=1.537650114

b=－6.432976311所求經(jīng)驗(yàn)公式為4.5.2代數(shù)多項(xiàng)式擬合1直線擬合.

作超定方程組

n記號(hào)

指對(duì)i從1