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

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

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

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

(插值原則、插值條件)

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

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

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

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

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

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

定理4.1

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

其系數(shù)行列式

因此方程組存在唯一的解

，因此Pn(x)存在并唯一。4.1.2插值多項式的誤差截斷誤差：

也稱為Pn(x)的余項。

定理4.2

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

證

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

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

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

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

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

證明因為f(n+1)(x)=0，從而Rn(x)≡0，Pn(x)≡f(x)。誤差公式的用法：，則截斷誤差估計為

如果

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

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

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

（線性插值多項式）

（拉格朗日線性插值多項式）

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

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

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

線性插值多項式的截斷誤差為

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

例1給定函數(shù)y=lnx在兩點10、11的值如下表，試用線性插值求ln10.5的近似值，并估計截斷誤差。

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

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

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

使?jié)M足插值條件

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

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

例2

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

x012y2-14解

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

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

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

一階差商

二階差商

例如設(shè)

則k階差商

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

差商具有對稱性：任意改變基點的次序后其值不變。例如

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)

┊┊

┊

┊

┊

┊……

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

注意：差商表中，對角線上的差商是構(gòu)造牛頓型插值公式的重要數(shù)據(jù)。粗線框出的部分在計算機(jī)上可存入二維數(shù)組差商表的數(shù)據(jù)構(gòu)成一個矩陣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ī)上計算差商表的公式

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

例4.4

已知函數(shù)y=f(x)的觀測數(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牛頓差商型插值多項式根據(jù)線性插值的點斜式牛頓差商型線性插值多項式：設(shè)由可得牛頓差商型二次插值多項式：可得牛頓差商型n次插值多項式(n次牛頓差商插值多項式)

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

余項公式的牛頓形式：

例4.5

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

解用全部基點時，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)時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

若插值基點等距分布，牛頓型插值多項式還可以利用差分得到簡化,。差分

設(shè)基點等距，

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

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

h=0.5,計算解

利用差分可以簡化等距基點的牛頓型插值公式，稱為前差（或后差）插值公式。用數(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ù)牡痛味囗検?，按一定的光滑性要求連接起來構(gòu)成插值函數(shù)。

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

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

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

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

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

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

稱xoy平面上的點(xi,yi

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

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

解設(shè)

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

得由得由得由得求得

給定n+1個樣點(xi,yi

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

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

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

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

xix1x2

…..xnyiy1y2

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

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

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

是待定常數(shù)，

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

近似曲線在各點的偏差的平方和是

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

(n>m)

即

如果有向量c使得

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

定理4.3

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

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

稱方程組ATAc=ATy

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

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

簡寫為

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

，其中

(2)計算ATA,ATy

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

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

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

解

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

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

作超定方程組

n記號

指對i從1