第四章插值和曲線擬合

第四章插值和曲線擬合第一頁(yè)，共三十一頁(yè)，2022年，8月28日第一節(jié)插值法的基本理論一、插值問(wèn)題設(shè)函數(shù)y=f(x)給出了一組函數(shù)值yi=f(xi),i=0,1,…,n，或者給出了如下的一張表

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

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

φ(xi)=yi

,i=0,1,…,n我們稱這樣的問(wèn)題為插值問(wè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)的方法稱為插值法。第二頁(yè)，共三十一頁(yè)，2022年，8月28日插值法的幾何意義插值法的幾何意義就是通過(guò)n+1個(gè)點(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)第三頁(yè)，共三十一頁(yè)，2022年，8月28日插值函數(shù)φ(x)的類型在插值問(wèn)題中，插值函數(shù)φ(x)的類型可有不同的選擇,如代數(shù)多項(xiàng)式、三角多項(xiàng)式、有理函數(shù)等，但是最簡(jiǎn)單而常用的是代數(shù)多項(xiàng)式，這時(shí)就稱為代數(shù)多項(xiàng)式插值。在本章，我們主要討論代數(shù)多項(xiàng)式插值。

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

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

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

Pn(xi)=yi

,i=0,1,…,n。

Pn(x)稱為f(x)的n次插值多項(xiàng)式。第四頁(yè)，共三十一頁(yè)，2022年，8月28日二、插值多項(xiàng)式的誤差

函數(shù)f(x)用n次插值多項(xiàng)式Pn(x)近似代替時(shí)，截?cái)嗾`差記為

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

…,xn

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

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

所以P1(x)=y0+(y1-y0)/(x1-x0)*(x-x0)（線性插值多項(xiàng)式）上式可改寫為：

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

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第六頁(yè)，共三十一頁(yè)，2022年，8月28日線性插值舉例例已知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)第七頁(yè)，共三十一頁(yè)，2022年，8月28日

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

二次插值問(wèn)題：已知f(x)在三個(gè)互異點(diǎn)x0,x1,x2的函數(shù)值y0,y1,y2,要構(gòu)造次數(shù)不超過(guò)二次的多項(xiàng)式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時(shí),P2(x0)=y0L0(x)=1,L1(x)=0,L2(x)=0當(dāng)x=x1時(shí)，P2(x1)=y1L0(x)=0,L1(x)=1,L2(x)=0當(dāng)x=x2時(shí)，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)]該式稱為拉格朗日二次插值多項(xiàng)式。第八頁(yè)，共三十一頁(yè)，2022年，8月28日二次插值舉例例已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)如下表所示，試求其拉格朗日插值多項(xiàng)式，并計(jì)算f(1.5)的近似值。

4

-1

2

y

2

1

0

x解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第九頁(yè)，共三十一頁(yè)，2022年，8月28日三、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次拉格朗日插值多項(xiàng)式。也可寫為

或

其中w(x)=(x-x0)…(x-xn)第十頁(yè)，共三十一頁(yè)，2022年，8月28日

n次拉格朗日插值舉例

例

已知函數(shù)表

x1.12751.15031.17351.972y0.11910.139540.159320.17903應(yīng)用朗格拉日插值公式計(jì)算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

第十一頁(yè)，共三十一頁(yè)，2022年，8月28日n次拉格朗日插值計(jì)算機(jī)實(shí)現(xiàn)

按n次拉格朗日插值公式實(shí)現(xiàn)第十二頁(yè)，共三十一頁(yè)，2022年，8月28日分段插值

七、八次以上的高次插值在實(shí)際中很少采用。因?yàn)槔碚撗芯亢蛯?shí)例都表明，插值基點(diǎn)增加并不能保證Pn(x)在非基點(diǎn)處逼近f(x)的精度得到提高,某些情況下甚至誤差反而變大。所以總是對(duì)每個(gè)插值點(diǎn)x選擇其附近的幾個(gè)插值基點(diǎn)作低次內(nèi)插(將x放在插值基點(diǎn)之間),或者采用分段低次插值(一次、二次插值)。為什么要選擇x附近的幾個(gè)插值基點(diǎn)？根據(jù)其中wn+1(x)=(x-x0)(x-x1)…(x-xn)第十三頁(yè)，共三十一頁(yè)，2022年，8月28日第三節(jié)牛頓插值

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

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ù)，每增加一個(gè)基點(diǎn)只需增加相應(yīng)的一項(xiàng)即可(具有遞推性)。為了確定出a0、a1、…、an,我們就需要討論牛頓差商插值多項(xiàng)式。下面首先介紹差商的概念。第十四頁(yè)，共三十一頁(yè)，2022年，8月28日一、差商及差商表

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個(gè)點(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)于一個(gè)點(diǎn)xi的零階差商定義為函數(shù)本身，即

f[xi]=f(xi)

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

f[x0,x1,…,xk]=f[]其中是x0,x1,…,xk的任一種排列。（證略）第十五頁(yè)，共三十一頁(yè)，2022年，8月28日

2.差商表對(duì)于給定的基點(diǎn)及其函數(shù)值，我們可按表計(jì)算各階差商，這樣的表就叫差商表。如下:xi四階差商一階差商二階差商三階差商x0x4x3

x2x1f(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]….....................零階差商第十六頁(yè)，共三十一頁(yè)，2022年，8月28日二、牛頓差商插值多項(xiàng)式

由差商定義和差商性質(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次牛頓(差商)插值多項(xiàng)式。

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

（w(x)=(x-x0)(x-x1)…(x-xn)）稱為n次牛頓插值多項(xiàng)式的余項(xiàng)。第十七頁(yè)，共三十一頁(yè)，2022年，8月28日牛頓差商插值多項(xiàng)式的兩個(gè)特殊形式牛頓(差商)插值多項(xiàng)式為當(dāng)n=1時(shí)

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

P2(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)即為拋物線插值?？梢?jiàn),增加一個(gè)基點(diǎn),只是增加了f[x0,x1,x2](x-x0)(x-x1)這一項(xiàng)。

注意,可以證明牛頓插值多項(xiàng)式與拉格朗日插值多項(xiàng)式是等價(jià)的,只不過(guò)形式不一樣而已。所以,兩者的截?cái)嗾`差是一樣的。

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)第十八頁(yè)，共三十一頁(yè)，2022年，8月28日牛頓差商插值多項(xiàng)式舉例例已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)如下表所示，試用全部基點(diǎn)構(gòu)造牛頓差商插值多項(xiàng)式，并用二次插值求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+1

13

-4

9

5

1

f(x)

6

5

4

2

0

x

xi零階一階二階三階四階

0

1

2

5

2

4

9

2

0

5

-4

-13

-5

-1

6

13

17

15

5

1第十九頁(yè)，共三十一頁(yè)，2022年，8月28日牛頓差商插值多項(xiàng)式舉例（續(xù)）用二次插值求f(3)時(shí),取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=12

xi零階一階二階三階四階

0

1

2

5

2

4

9

2

0

5

-4

-13

-5

-1

6

13

17

15

5

1差商表為P2(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)第二十頁(yè)，共三十一頁(yè)，2022年，8月28日

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

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

1.求各階差商

2.按秦九韶方法求多項(xiàng)式的值。第二十一頁(yè)，共三十一頁(yè)，2022年，8月28日第四節(jié)曲線擬合插值法和曲線擬合都是用來(lái)求列表函數(shù)f(x)(只知道一些點(diǎn)的函數(shù)稱為列表函數(shù))的近似函數(shù)φ(x)。插值法求出的近似曲線y=φ(x)要完全通過(guò)所有n+1個(gè)已知點(diǎn)(即要滿足插值原則);而曲線擬合求出的近似曲線

y=φ(x)不要求完全通過(guò)所有n+1個(gè)已知點(diǎn),只要求求得的近似曲線y=φ(x)能反映數(shù)據(jù)的基本趨勢(shì)即可。曲線擬合求得的近似曲線y=φ(x)比插值法求得的近似曲線y=φ(x)更能反映客觀實(shí)際。因?yàn)榱斜砗瘮?shù)中的點(diǎn)往往是通過(guò)實(shí)驗(yàn)、測(cè)量或計(jì)算得來(lái)的,而實(shí)驗(yàn)、測(cè)量或計(jì)算得來(lái)的數(shù)據(jù)經(jīng)常帶有誤差,如果要求所得出的曲線y=φ(x)通過(guò)所有n+1個(gè)已知點(diǎn)(xi,yi),就會(huì)使曲線y=φ(x)

保留著這些誤差，而這是我們所不希望的。第二十二頁(yè)，共三十一頁(yè)，2022年，8月28日一、曲線擬合問(wèn)題設(shè)函數(shù)y=f(x)在n+1個(gè)互異點(diǎn)的觀測(cè)數(shù)據(jù)為

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

構(gòu)造函數(shù)φ(x)在包含全部基點(diǎn)的區(qū)間上“最好”地逼近(或靠近)f(x),這就是曲線擬合問(wèn)題。如下圖所示,就是使曲線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第二十三頁(yè)，共三十一頁(yè)，2022年，8月28日

二、最小二乘法

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

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

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

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

……a0+a1xn+a2xn2+…+amxnm≈yn第二十四頁(yè)，共三十一頁(yè)，2022年，8月28日最小二乘法(續(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≈yna0+a1x1+a2x12+…+amx1m=y1

方程組中有n+1個(gè)方程、m+1個(gè)未知數(shù)。若n+1=m+1,方程組有唯一解;若n+1<m+1,方程組有無(wú)窮多組解;若n+1>m+1,方程組無(wú)解(無(wú)精確解),稱為超定方程組。第二十五頁(yè)，共三十一頁(yè)，2022年，8月28日最小二乘法(續(xù))

超定方程組無(wú)精確解但可求其近似解。那么解近似到什么程度才算近似解？這有不同的標(biāo)準(zhǔn)。若所求得的近似解使得誤差平方和()達(dá)到最小，我們稱這組近似解為最優(yōu)近似解。根據(jù)誤差平方和達(dá)到最小這一標(biāo)準(zhǔn)求最優(yōu)近似解的方法就稱為最小二乘法。下面具體解釋一下什么是超定方程組的最小二乘法。

a0+a1x1+a2x12+…+amx1m=y1

……a0+a1xn+a2xn2+…+amxnm=yna0+a1x0+a2x02+…+amx0m=y0第二十六頁(yè)，共三十一頁(yè)，2022年，8月28日超定方程組的最小二乘法

設(shè)超定方程組

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

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

……a0+a1xn+a2xn2+…+amxnm=yn

(i=0,