第四章插值和曲線擬合課件

第四章插值和曲線擬合

在實際問題和科學(xué)實驗中所遇到的函數(shù)y=f(x),往往沒有解析表達(dá)式,只能根據(jù)試驗觀察或其它方法提供一系列點(diǎn)的函數(shù)值;有時盡管可以寫出表達(dá)式，但是比較復(fù)雜,直接使用它感到不方便。我們經(jīng)常需要利用已知的數(shù)據(jù)去尋求某個簡單的函數(shù)φ(x)來逼近f(x),即用φ(x)作為f(x)的近似表達(dá)式。本章的插值法和曲線擬合就是兩種用來求f(x)的近似函數(shù)φ(x)的重要方法。

第一節(jié)插值法的基本理論一、插值問題設(shè)函數(shù)y=f(x)給出了一組函數(shù)值yi=f(xi),i=0,1,…,n，或者給出了如下的一張表

x0,x1,x2,…,xny0,y1,y2,…,yn構(gòu)造一個簡單的函數(shù)φ(x)

作為f(x)的近似表達(dá)式，以滿足

φ(xi)=yi

,i=0,1,…,n我們稱這樣的問題為插值問題。

其中φ(xi)=yi

稱為插值原則;φ(x)稱為f(x)的插值函數(shù)；f(x)稱為被插值函數(shù);x0,x1,x2,…,xn稱為插值基點(diǎn)(或節(jié)點(diǎn))。根據(jù)插值原則求其余點(diǎn)x的函數(shù)值φ(x)稱為插值,x稱為插值點(diǎn)；根據(jù)插值原則求f(x)近似函數(shù)φ(x)的方法稱為插值法。插值法的幾何意義插值法的幾何意義就是通過n+1個點(diǎn):(xi,yi)(i=0,1,2,…,n)

作一條近似曲線y=φ(x)代替y=f(x)。如下圖所示。xxnx2x1x0Xn-1y0(x0,y0)(x1,y1)(x2,y2)(xn-1,yn-1)(xn,yn)…y=φ(x)y=f(x)插值函數(shù)φ(x)的類型在插值問題中，插值函數(shù)φ(x)的類型可有不同的選擇,如代數(shù)多項式、三角多項式、有理函數(shù)等，但是最簡單而常用的是代數(shù)多項式，這時就稱為代數(shù)多項式插值。在本章，我們主要討論代數(shù)多項式插值。

代數(shù)多項式插值的任務(wù)就是根據(jù)n+1個點(diǎn)

x0,x1,x2,…,xny0,y1,y2,…,yn構(gòu)造一個次數(shù)不超過n的多項式

Pn(x)=a0+a1x+a2x2+…+anxn使?jié)M足插值原則

Pn(xi)=yi

,i=0,1,…,n。

Pn(x)稱為f(x)的n次插值多項式。二、插值多項式的誤差

函數(shù)f(x)用n次插值多項式Pn(x)近似代替時，截斷誤差記為

Rn(x)=f(x)-Pn(x)稱Rn(x)為n次插值多項式Pn(x)的余項。定理設(shè)函數(shù)f(x)在包含基點(diǎn)x0,x1,x2,

…,xn

的區(qū)間[a,b]上具有n+1階導(dǎo)數(shù),Pn(x)為滿足Pn(xi)=yi的n次插值多項式,則對任一點(diǎn)x∈[a,b],總存在相應(yīng)的點(diǎn),使其中wn+1(x)=(x-x0)(x-x1)…(x-xn)第二節(jié)拉格朗日插值為了得到n次的拉格朗日插值多項式，我們從最簡單的一次、二次插值開始。一、一次插值（線性插值）已知x0x1求P1(x)y0y1

因P1(x0)=y0,P1(x1)=y1

所以P1(x)=y0+(y1-y0)/(x1-x0)*(x-x0)（線性插值多項式）

上式可改寫為：

P1(x)=y0L0(x)+y1L1(x)（拉格朗日線性插值多項式）

L0(x)=(x-x1)/(x0-x1),L1(x)=(x-x0)/(x1-x0)L0(x)、L1(x)特點(diǎn)：

L0(x)=1,x=x0L1(x)=1,x=x1

0,x=x1,0,x=x0線性插值舉例例已知1001/2=10，1211/2=11求1151/2解P1(x)=y0+(y1-y0)/(x1-x0)*(x-x0)P1(115)=10+(11-10)/(121-100)*(115-100)

或

P1(x)=y0L0(x)+y1L1(x)

P1(115)=10*(115-121)/(100-121)+11*(115-100)/(121-100)

二、二次插值(拋物線插值)

二次插值問題：已知f(x)在三個互異點(diǎn)x0,x1,x2的函數(shù)值y0,y1,y2,要構(gòu)造次數(shù)不超過二次的多項式P2(x)=a0+a1x+a2x2,使?jié)M足

P2(xi)=yi,i=0,1,2

設(shè)P2(x)=L0(x)y0+L1(x)y1+L2(x)y2,則當(dāng)x=x0時,P2(x0)=y0L0(x)=1,L1(x)=0,L2(x)=0當(dāng)x=x1時，P2(x1)=y1L0(x)=0,L1(x)=1,L2(x)=0當(dāng)x=x2時，P2(x2)=y2L0(x)=0,L1(x)=0,L2(x)=1由上知L0(x)=1,x=x00,x=x1,x2令L0(x)=A0(x-x1)(x-x2)則A0=1/[(x0-x1)(x0-x2)]所以L0(x)=(x-x1)(x-x2)/[(x0-x1)(x0-x2)]同理可得L1(x)=(x-x0)(x-x2)/[(x1-x0)(x1-x2)]L2(x)=(x-x0)(x-x1)/[(x2-x0)(x2-x1)]綜上可得P2(x)=y0(x-x1)(x-x2)/[(x0-x1)(x0-x2)]+y1(x-x0)(x-x2)/[(x1-x0)(x1-x2)]+y2(x-x0)(x-x1)/[(x2-x0)(x2-x1)]該式稱為拉格朗日二次插值多項式。二次插值舉例例已知函數(shù)y=f(x)的觀測數(shù)據(jù)如下表所示，試求其拉格朗日插值多項式，并計算f(1.5)的近似值。4-12y210x解P2(x)=y0(x-x1)(x-x2)/[(x0-x1)(x0-x2)]+y1(x-x0)(x-x2)/[(x1-x0)(x1-x2)]+y2(x-x0)(x-x1)/[(x2-x0)(x2-x1)]=2*(x-1)(x-2)/[(0-1)(0-2)]+(-1)*(x-0)(x-2)/[(1-0)(1-2)]+4*(x-0)(x-1)/[(2-0)(2-1)]=4x2-7x+2f(1.5)≈

P2(1.5)=4*1.52-7*1.5+2=0.5三、n次拉格朗日插值仿照P2(x)的構(gòu)造方法，可得出

Pn(x)=L0(x)y0+L1(x)y1+…+Ln(x)yn其中

L0(x)=[(x-x1)(x-x2)…(x-xn)]/[(x0-x1)(x0-x2)…(x0-xn)]Lk(x)=[(x-x0)…(x-xk-1)(x-xk+1)…(x-xn)]/[(xk-x0)…(xk-xk-1)(xk-xk+1)…(xk-xn)](k=0,1,…,n)這就是n次拉格朗日插值多項式。也可寫為

n次拉格朗日插值舉例

例

已知函數(shù)表

x1.12751.15031.17351.972y0.11910.139540.159320.17903應(yīng)用朗格拉日插值公式計算f(1.1300)的近似值。解P3(x)=L0(x)y0+L1(x)y1+L2(x)y2+L3(x)y3

=

……f(1.1300)≈

P3(1.1300)=0.1214

n次拉格朗日插值計算機(jī)實現(xiàn)

按n次拉格朗日插值公式實現(xiàn)分段插值

七、八次以上的高次插值在實際中很少采用。因為理論研究和實例都表明，插值基點(diǎn)增加并不能保證Pn(x)在非基點(diǎn)處逼近f(x)的精度得到提高,某些情況下甚至誤差反而變大。所以總是對每個插值點(diǎn)x選擇其附近的幾個插值基點(diǎn)作低次內(nèi)插(將x放在插值基點(diǎn)之間),或者采用分段低次插值(一次、二次插值)。

為什么要選擇x附近的幾個插值基點(diǎn)？根據(jù)其中wn+1(x)=(x-x0)(x-x1)…(x-xn)第三節(jié)牛頓插值

拉格朗日插值多項式結(jié)構(gòu)對稱,使用方便,但公式不具備遞推性,當(dāng)需要增加基點(diǎn)時必須全部重新計算。因此，我們希望構(gòu)造具有如下形式的插值多項式

Pn(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)

+…

+an(x-x0)(x-x1)…(x-xn-1)這種形式的優(yōu)點(diǎn)是便于改變基點(diǎn)數(shù)，每增加一個基點(diǎn)只需增加相應(yīng)的一項即可(具有遞推性)。為了確定出a0、a1、…、an,我們就需要討論牛頓差商插值多項式。下面首先介紹差商的概念。一、差商及差商表

1.差商定義在區(qū)間[a,b]上，函數(shù)f(x)關(guān)于兩點(diǎn)xi,xj的一階差商定義為

f[xi,xj]=[f(xj)-f(xi)]/(xj-xi)f(x)關(guān)于三點(diǎn)xi,xj,xk的二階差商定義為

f[xi,xj,xk]=(f[xj,xk]-f[xi,xj])/(xk-xi)f(x)關(guān)于k+1個點(diǎn)xi-k,xi-k+1,…,xi的k階差商定義為

f[xi-k,xi-k+1,…,xi]=(f[xi-k+1,…,xi]–f[xi-k,…,xi-1])/(xi-xi-k)f(x)關(guān)于一個點(diǎn)xi的零階差商定義為函數(shù)本身，即

f[xi]=f(xi)

不論幾階差商，差商均有對稱性（任意改變基點(diǎn)的次序后其值不變）。即

f[x0,x1,…,xk

]=f[]其中是x0,x1,…,xk

的任一種排列。（證略）

2.差商表

對于給定的基點(diǎn)及其函數(shù)值，我們可按表計算各階差商，這樣的表就叫差商表。如下:xi四階差商一階差商二階差商三階差商x0x4x3x2x1f(x4)f(x3)f(x2)f(x1)f(x0)f[x3,x4]f[x2,x3]f[x1,x2]f[x0,x1]f[x1,x2,x3]f[x2,x3,x4]f[x0,x1,x2]f[x0,x1,x2,x3]f[x1,x2,x3,x4]f[x0,x1,x2,x3,x4]….....................零階差商二、牛頓差商插值多項式

由差商定義和差商性質(zhì)有f(x)=f(x0)+f[x0,x](x-x0)(f[x0,x]=[f(x)-f(x0)]/(x-x0))f[x0,x]=f[x0,x1]+f[x0,x1,x](x-x1)f[x0,x1,x]=f[x0,x1,x2]+f[x0,x1,x2,x](x-x2)……f[x0,x1,…,xn-1,x]=f[x0,x1,…,xn]+f[x0,x1,…,xn,x](x-xn)f(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+…+f[x0,x1,…,xn](x-x0)(x-x1)…(x-xn-1)+f[x0,x1,…,xn,x](x-x0)(x-x1)…(x-xn)=Pn(x)+Rn(x)Pn(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+…+f[x0,x1,…,xn](x-x0)(x-x1)…(x-xn-1)Pn(x)由于滿足Pn(xi)=f(xi)稱作n次牛頓(差商)插值多項式。

Rn(x)=f(x)-Pn(x)=w(x)*f(n+1)(ζ)/(n+1)!

（w(x)=(x-x0)(x-x1)…(x-xn)）稱為n次牛頓插值多項式的余項。牛頓差商插值多項式的兩個特殊形式牛頓(差商)插值多項式為當(dāng)n=1時

P1(x)=f(x0)+f[x0,x1](x-x0)即為線性插值。當(dāng)n=2時

P2(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)即為拋物線插值。可見,增加一個基點(diǎn),只是增加了f[x0,x1,x2](x-x0)(x-x1)這一項。

注意,可以證明牛頓插值多項式與拉格朗日插值多項式是等價的,只不過形式不一樣而已。所以,兩者的截斷誤差是一樣的。

Pn(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+…+f[x0,x1,…,xn](x-x0)(x-x1)…(x-xn-1)牛頓差商插值多項式舉例例已知函數(shù)y=f(x)的觀測數(shù)據(jù)如下表所示，試用全部基點(diǎn)構(gòu)造牛頓差商插值多項式，并用二次插值求f(3)的近似值。

解差商表為P4(x)=1+2(x-0)+0(x-0)(x-2)+(-1)(x-0)(x-2)(x-4)+(x-0)(x-2)(x-4)(x-5)=x4-12x3+44x2-46x+113-4951f(x)65420xxi

零階一階二階三階四階0

1

25

2492

05-4-13-5

-161317155

1牛頓差商插值多項式舉例（續(xù)）用二次插值求f(3)時,取x0=2,x1=4,x2=5f(3)≈P2(3)=f(2)+f[2,4](3-2)+f[2,4,5](3-2)(3-4)=5+2(3-2)-5(3-2)(3-4)=5+2+5=12xi

零階一階二階三階四階0

1

25

2492

05-4-13-5

-161317155

1差商表為P2(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)

牛頓差商插值多項式的計算機(jī)實現(xiàn)

按牛頓差商插值多項式公式實現(xiàn)。分兩大步：

1.求各階差商

2.按秦九韶方法求多項式的值。第四節(jié)曲線擬合插值法和曲線擬合都是用來求列表函數(shù)f(x)(只知道一些點(diǎn)的函數(shù)稱為列表函數(shù))的近似函數(shù)φ(x)。插值法求出的近似曲線y=φ(x)要完全通過所有n+1個已知點(diǎn)(即要滿足插值原則);而曲線擬合求出的近似曲線

y=φ(x)不要求完全通過所有n+1個已知點(diǎn),只要求求得的近似曲線y=φ(x)能反映數(shù)據(jù)的基本趨勢即可。曲線擬合求得的近似曲線y=φ(x)比插值法求得的近似曲線

y=φ(x)更能反映客觀實際。因為列表函數(shù)中的點(diǎn)往往是通過實驗、測量或計算得來的,而實驗、測量或計算得來的數(shù)據(jù)經(jīng)常帶有誤差,如果要求所得出的曲線y=φ(x)通過所有n+1個已知點(diǎn)(xi,yi),就會使曲線y=φ(x)

保留著這些誤差，而這是我們所不希望的。一、曲線擬合問題設(shè)函數(shù)y=f(x)在n+1個互異點(diǎn)的觀測數(shù)據(jù)為

x0,x1,…,xny0,y1,…,yn

構(gòu)造函數(shù)φ(x)在包含全部基點(diǎn)的區(qū)間上“最好”地逼近(或靠近)f(x),這就是曲線擬合問題。如下圖所示,就是使曲線y=φ(x)盡量靠近已知點(diǎn)(xi,yi)(i=0,1,2,…,n)。

xy0y=φ(x)×××××(x0,y0)(x1,y1)(xn,yn)(xn-1,yn-1)(x2,y2)εnεn-1ε2ε1ε0

二、最小二乘法

假設(shè)y=φ(x)其中(φ(x)=a0+a1x+a2x2+…+amxm）

為給定的一組數(shù)據(jù)(xi,yi)(i=0,1,2,…,n)的擬合曲線，

則將這n+1個點(diǎn)代入φ(x)得以下式子

a0+a1x0+a2x02+…+amx0m≈y0a0+a1x1+a2x12+…+amx1m≈y1

……a0+a1xn+a2xn2+…+amxnm

≈yn最小二乘法(續(xù))若將a0+a1x0+a2x02+…+amx0m≈y0a0+a1x1+a2x12+…+amx1m≈y1

……a0+a1xn+a2xn2+…+amxnm

=yn

中的“≈”換為“=”該式變?yōu)榉匠探Ma0+a1x0+a2x02+…+amx0m=y0

……a0+a1xn+a2xn2+…+amxnm

≈yn

a0+a1x1+a2x12+…+amx1m=y1

方程組中有n+1個方程、m+1個未知數(shù)。若n+1=m+1,方程組有唯一解;若n+1<m+1,方程組有無窮多組解;若n+1>m+1,方程組無解(無精確解),稱為超定方程組。最小二乘法(續(xù))

超定方程組無精確解但可求其近似解。那么解近似到什么程度才算近似解？這有不同的標(biāo)準(zhǔn)。

若所求得的近似解使得誤差平方和()達(dá)到最小，我們稱這組近似解為最優(yōu)近似解。根據(jù)誤差平方和達(dá)到最小這一標(biāo)準(zhǔn)求最優(yōu)近似解的方法就稱為最小二乘法。下面具體解釋一下什么是超定方程組的最小二乘法。

a0+a1x1+a2x12+…+amx1m=y1

……a0+a1xn+a2xn2+…+amxnm

=yn

a0+a1x0+a2x02+…+amx0m=y0超定方程組的最小二乘法

設(shè)超定方程組

根據(jù)高數(shù)知識，達(dá)到最小必須滿足條件

a0+a1x1+a2x12+…+amx1m=y1a0+a1x0+a2x02+…+amx0m=y0