第四章插值和曲線擬合

第四章插值和曲線擬合第一頁，共三十一頁，編輯于2023年，星期五第一節(jié)插值法的基本理論一、插值問題設函數(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)的近似表達式，以滿足

φ(xi)=yi

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

其中φ(xi)=yi

稱為插值原則;φ(x)稱為f(x)的插值函數(shù)；f(x)稱為被插值函數(shù);x0,x1,x2,…,xn稱為插值基點(或節(jié)點)。根據(jù)插值原則求其余點x的函數(shù)值φ(x)稱為插值,x稱為插值點；根據(jù)插值原則求f(x)近似函數(shù)φ(x)的方法稱為插值法。第二頁，共三十一頁，編輯于2023年，星期五插值法的幾何意義插值法的幾何意義就是通過n+1個點:(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)第三頁，共三十一頁，編輯于2023年，星期五插值函數(shù)φ(x)的類型在插值問題中，插值函數(shù)φ(x)的類型可有不同的選擇,如代數(shù)多項式、三角多項式、有理函數(shù)等，但是最簡單而常用的是代數(shù)多項式，這時就稱為代數(shù)多項式插值。在本章，我們主要討論代數(shù)多項式插值。

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

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次插值多項式。第四頁，共三十一頁，編輯于2023年，星期五二、插值多項式的誤差

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

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

…,xn

的區(qū)間[a,b]上具有n+1階導數(shù),Pn(x)為滿足Pn(xi)=yi的n次插值多項式,則對任一點x∈[a,b],總存在相應的點,使其中wn+1(x)=(x-x0)(x-x1)…(x-xn)第五頁，共三十一頁，編輯于2023年，星期五第二節(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)特點：

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

0,x=x1,0,x=x0第六頁，共三十一頁，編輯于2023年，星期五線性插值舉例例已知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)第七頁，共三十一頁，編輯于2023年，星期五

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

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

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

設P2(x)=L0(x)y0+L1(x)y1+L2(x)y2,則當x=x0時,P2(x0)=y0L0(x)=1,L1(x)=0,L2(x)=0當x=x1時，P2(x1)=y1L0(x)=0,L1(x)=1,L2(x)=0當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)]該式稱為拉格朗日二次插值多項式。第八頁，共三十一頁，編輯于2023年，星期五二次插值舉例例已知函數(shù)y=f(x)的觀測數(shù)據(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第九頁，共三十一頁，編輯于2023年，星期五三、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次拉格朗日插值多項式。也可寫為

或

其中w(x)=(x-x0)…(x-xn)第十頁，共三十一頁，編輯于2023年，星期五

n次拉格朗日插值舉例

例

已知函數(shù)表

x1.12751.15031.17351.972y0.11910.139540.159320.17903應用朗格拉日插值公式計算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

第十一頁，共三十一頁，編輯于2023年，星期五n次拉格朗日插值計算機實現(xiàn)

按n次拉格朗日插值公式實現(xiàn)第十二頁，共三十一頁，編輯于2023年，星期五分段插值

七、八次以上的高次插值在實際中很少采用。因為理論研究和實例都表明，插值基點增加并不能保證Pn(x)在非基點處逼近f(x)的精度得到提高,某些情況下甚至誤差反而變大。所以總是對每個插值點x選擇其附近的幾個插值基點作低次內(nèi)插(將x放在插值基點之間),或者采用分段低次插值(一次、二次插值)。為什么要選擇x附近的幾個插值基點？根據(jù)其中wn+1(x)=(x-x0)(x-x1)…(x-xn)第十三頁，共三十一頁，編輯于2023年，星期五第三節(jié)牛頓插值

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

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

+…

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

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

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

f[xi,xj,xk]=(f[xj,xk]-f[xi,xj])/(xk-xi)f(x)關于k+1個點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)關于一個點xi的零階差商定義為函數(shù)本身，即

f[xi]=f(xi)

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

f[x0,x1,…,xk]=f[]其中是x0,x1,…,xk的任一種排列。（證略）第十五頁，共三十一頁，編輯于2023年，星期五

2.差商表對于給定的基點及其函數(shù)值，我們可按表計算各階差商，這樣的表就叫差商表。如下: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]….....................零階差商第十六頁，共三十一頁，編輯于2023年，星期五二、牛頓差商插值多項式

由差商定義和差商性質(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次牛頓插值多項式的余項。第十七頁，共三十一頁，編輯于2023年，星期五牛頓差商插值多項式的兩個特殊形式牛頓(差商)插值多項式為當n=1時

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

P2(x)=f(x0)+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)即為拋物線插值?？梢?增加一個基點,只是增加了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)第十八頁，共三十一頁，編輯于2023年，星期五牛頓差商插值多項式舉例例已知函數(shù)y=f(x)的觀測數(shù)據(jù)如下表所示，試用全部基點構(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+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第十九頁，共三十一頁，編輯于2023年，星期五牛頓差商插值多項式舉例（續(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=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)第二十頁，共三十一頁，編輯于2023年，星期五

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

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

1.求各階差商

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

y=φ(x)不要求完全通過所有n+1個已知點,只要求求得的近似曲線y=φ(x)能反映數(shù)據(jù)的基本趨勢即可。曲線擬合求得的近似曲線y=φ(x)比插值法求得的近似曲線y=φ(x)更能反映客觀實際。因為列表函數(shù)中的點往往是通過實驗、測量或計算得來的,而實驗、測量或計算得來的數(shù)據(jù)經(jīng)常帶有誤差,如果要求所得出的曲線y=φ(x)通過所有n+1個已知點(xi,yi),就會使曲線y=φ(x)

保留著這些誤差，而這是我們所不希望的。第二十二頁，共三十一頁，編輯于2023年，星期五一、曲線擬合問題設函數(shù)y=f(x)在n+1個互異點的觀測數(shù)據(jù)為

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

構(gòu)造函數(shù)φ(x)在包含全部基點的區(qū)間上“最好”地逼近(或靠近)f(x),這就是曲線擬合問題。如下圖所示,就是使曲線y=φ(x)盡量靠近已知點(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第二十三頁，共三十一頁，編輯于2023年，星期五

二、最小二乘法

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

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

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

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

……a0+a1xn+a2xn2+…+amxnm≈yn第二十四頁，共三十一頁，編輯于2023年，星期五最小二乘法(續(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個方程、m+1個未知數(shù)。若n+1=m+1,方程組有唯一解;若n+1<m+1,方程組有無窮多組解;若n+1>m+1,方程組無解(無精確解),稱為超定方程組。第二十五頁，共三十一頁，編輯于2023年，星期五最小二乘法(續(xù))

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

a0+a1x1+a2x12+…+amx1m=y1

……a0+a1xn+a2xn2+…+amxnm=yna0+a1x0+a2x02+…+amx0m=y0第二十六頁，共三十一頁，編輯于2023年，星期五超定方程組的最小二乘法

設超定方程組

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

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

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

(i=0,1,2,…,m)，