拉格朗日插值逐次線性插值法

第二章函數(shù)的插值學(xué)習(xí)目標(biāo)：掌握多項(xiàng)式插值的Lagrange插值公式、牛頓插值公式等，等距節(jié)點(diǎn)插值、差分、差商、重節(jié)點(diǎn)差商與埃米特插值。重點(diǎn)是多項(xiàng)式插值方法。2.1.5Hermite插值多項(xiàng)式2.1.4均差和Newton插值多項(xiàng)式2.1.3逐次線性插值2.1.2Lagrange插值多項(xiàng)式2.1.1問(wèn)題的提出2.1多項(xiàng)式插值

給定空間一組有序的控制點(diǎn)（controlpoint），得到一條光滑的分段參數(shù)多項(xiàng)式曲線的方法:曲線順序經(jīng)過(guò)所有的控制點(diǎn)，則稱為對(duì)這些控制點(diǎn)進(jìn)行插值，得到的曲線稱為插值曲線。

構(gòu)造一條在某種意義下最靠近控制點(diǎn)的曲線，這稱為對(duì)這些控制點(diǎn)進(jìn)行逼近，得到的曲線稱為逼近(擬合)曲線。

(a)5個(gè)控制點(diǎn)的插值曲線(b)5個(gè)控制點(diǎn)的逼近曲線

本章先討論插值問(wèn)題，然后再討論數(shù)據(jù)擬合的有關(guān)問(wèn)題。

擬合法就是考慮到數(shù)據(jù)不一定準(zhǔn)確，不要求近似表達(dá)式經(jīng)過(guò)所有的點(diǎn)，而只要求在給定的上誤差（i=0，1,…,n）按某種標(biāo)準(zhǔn)最小。若記

δ=(δ1,

δ2,…,δn

)T

，就是要求向量δ的范數(shù)||δ||

最小。

問(wèn)題１：基于未知函數(shù)或復(fù)雜函數(shù)的某些已知信息，如何構(gòu)造這些函數(shù)的近似表達(dá)式?情形１．函數(shù)f(x)在x０點(diǎn)的Taylor展開(kāi)式－－稱為函數(shù)f(x)的Taylor插值解:設(shè)例如：利用Taylor插值求利用Tylor插值，有y=f(x)x0p(x)Tylor插值的缺陷：①Tylor插值中有導(dǎo)數(shù)運(yùn)算，而計(jì)算機(jī)實(shí)現(xiàn)求導(dǎo)運(yùn)算存在困難；②近似區(qū)間小,在大的區(qū)間上不可行．情形２在區(qū)間［a,b］上考慮函數(shù)f(x)的近似．y=f(x)a

b

求解：y=f(x)在[a,b]上的近似曲線？利用函數(shù)f(x)在區(qū)間[a,b]上一系列點(diǎn)的值

yi=f(xi)（可通過(guò)觀察、測(cè)量、試驗(yàn)等方法得到）y=f(x)xx0x1x2…xnyy0y1y2…yn插值法解決思路

根據(jù)

f

(x)在n+1個(gè)已知點(diǎn)的值，求一個(gè)足夠光滑又比較簡(jiǎn)單的函數(shù)p(x)，作為

f(x)的近似表達(dá)式，x0x1x2x3x4

xf(x)p(x)從幾何上看曲線P

(

x)

近似f

(

x)從代數(shù)上看，看p(x)滿足以下代數(shù)條件p(xi)=yi

i=0,1,2,

?,n這就是所謂的插值．然后計(jì)算p(x)在[a,b]上其它點(diǎn)x處的函數(shù)值作為原來(lái)函數(shù)f

(x)在此點(diǎn)函數(shù)值的近似值。代數(shù)多項(xiàng)式、三角多項(xiàng)式、有理函數(shù)或樣條函數(shù)(2.1)式稱為插值條件，x2<?<xn≤

b

點(diǎn)上的值y0,y1,?,yn.

若存在一簡(jiǎn)單函數(shù)p(x),

使得

p(xi)=yi

i=0,1,2,

?,n

(2.1)

定義2.1f(

x

)稱為被插函數(shù)，[a,b]稱為插值區(qū)間，稱為插值節(jié)點(diǎn)，

求p

(

x

)

的方法就是插值法。設(shè)函數(shù)f(x)在[a,b]上有定義，且已知在a

≤

x0

<

x1<成立,則稱p(x)為

f(x)

的插值函數(shù)。近似計(jì)算f(x)的值、零點(diǎn)、極值點(diǎn)、導(dǎo)數(shù)、積分，插值點(diǎn)在插值區(qū)間內(nèi)的稱為內(nèi)插,否則稱外插.

最常用的插值函數(shù)是…?代數(shù)多項(xiàng)式用代數(shù)多項(xiàng)式作插值函數(shù)的插值稱為多項(xiàng)式插值本章主要討論的內(nèi)容插值函數(shù)的類型有很多種插值問(wèn)題插值法插值函數(shù)分段函數(shù)…三角多項(xiàng)式x0x1x2x3x4f(x)p(x)從幾何上看曲線P

(

x)

近似f

(

x)研究問(wèn)題：（1）滿足插值條件的P

(

x)

是否存在唯一？（2）若滿足插值條件的P

(

x)

存在，如何構(gòu)造P

(

x)？（3）如何估計(jì)用P

(

x)近似替代f

(

x)產(chǎn)生的誤差？問(wèn)題2－插值多項(xiàng)式的構(gòu)造②可設(shè)p

(

x

)=a0

+a1x+?+an

x

n①確定多項(xiàng)式p(x)的次數(shù)方法１：待定系數(shù)法要求插值多項(xiàng)式p(x)，可以通過(guò)求n+1個(gè)方程的解:得到。但這樣做不但計(jì)算復(fù)雜，而且難于得到pn(x)的簡(jiǎn)單表達(dá)式。結(jié)論：n+1個(gè)插值節(jié)點(diǎn)產(chǎn)生的插值多項(xiàng)式至多是n次的．問(wèn)題１－插值多項(xiàng)式的存在唯一性

設(shè)pn(

x

)是f(x)

的插值多項(xiàng)式，Hn表示次數(shù)不超過(guò)n的所有多項(xiàng)且pn(

x

)∈Hn.稱插值多項(xiàng)式存在且唯一，就是指在由(2.1)可得(2.2)方程組(2.2)有唯一解插值多項(xiàng)式的唯一性≠0(xi≠xj)定理2.1滿足條件(2.1)的插值多項(xiàng)式存在且唯一。范德蒙行列式a0,a1,a2,?,an存在唯一p(xi)=yi

i=0,1,2,

?,nHn中有且僅有一個(gè)pn(

x

)滿足插值條件(2.1)式。式的集合。n+1個(gè)節(jié)點(diǎn)互異為求得便于使用的簡(jiǎn)單插值多項(xiàng)式p(x)，我們先討論n=1的情形。當(dāng)n=1時(shí)，要構(gòu)造通過(guò)兩點(diǎn)

(x0,y0)和(x1,y1)的不超過(guò)1次的多項(xiàng)式p1(x)(后面記作L1(x))，使得拉格朗日插值y

0x

y=f(x)y=L1(x)x0x1

－－－稱為線性（一次）插值（兩點(diǎn)式）（點(diǎn)斜式）或L1(x)是兩個(gè)線性函數(shù)的線性組合稱為節(jié)點(diǎn)x0,x1上線性插值基函數(shù)------線性Lagrange插值多項(xiàng)式形式

y10

x0x1xl0(x)l1(x)

節(jié)點(diǎn)上的線性插值基函數(shù)：滿足

y10

x0x1x(2.3)(2.4)x0x1l0(x)10l1(x)01lk,lk+1稱為節(jié)點(diǎn)上線性插值基函數(shù).滿足

y10

xkxk+1x

y10

xkxk+1x

lk(x)lk+1(x)(2.7)xkxk+1lk(x)10lk+1(x)01

(2.6)式也稱為拉格朗日型插值多項(xiàng)式，其中基函數(shù)lk,lk+1與yk,yk+1無(wú)關(guān)，而由插值節(jié)點(diǎn)xk,xk+1決定．

因此，一次拉格朗日插值多項(xiàng)式是插值基函數(shù)lk,lk+1的線性組合，相應(yīng)的組合系數(shù)是該點(diǎn)的函數(shù)值yk,yk+1．例2.1已知,,解:這里x0=100，y0=10，x1=121，y1=11,利用線性插值利用線性插值求

先求插值基函數(shù)l0(x),l1(x),l2(x),它們滿足

(1)都是二次函數(shù)；

(2)在節(jié)點(diǎn)滿足(2.8)x0x1x2l0(x)100l1(x)010l2(x)001y

1

0

xy

1

0

xy

1

0

xx0

x1

x2

先求l0(x):待定系數(shù)x0

x1

x2x0

x1

x2

由l0(x)滿足的兩個(gè)條件類似地,可得知l0(x)中含有兩個(gè)因子(x-x1)(x-x2)，且是二次的再由l0(x)滿足的條件即得所以有L2(x)=y0l0(x)

+y1

l1(x)

+y2

l2(x)L2(

xj)=yj,j=k-1,k,k+1.

L2(x)=yk-1lk–1(x)

+yk

lk(x)

+yk+1lk+1(x)值件插條再構(gòu)造插值多項(xiàng)式L2(x)是三個(gè)二次插值多項(xiàng)式的線性組合，且也滿足插值條件．(2.9)-----過(guò)三點(diǎn)(xk-1,yk-1),(xk,yk)與(xk+1,

yk+1)的拋物線Y=L2(x)的幾何意義例2.1*

已知,,解:這里x0=100，y0=10，x1=121，y1=11,x2=144，y2=12，利用拋物線插值公式利用拋物線插值求這種用插值基函數(shù)表示的方法容易推廣到更一般的情形。n次Lagrange插值多項(xiàng)式求通過(guò)n+1個(gè)節(jié)點(diǎn)的n次插值多項(xiàng)式Ln(x)：先求插值基函數(shù)然后構(gòu)造插值多項(xiàng)式設(shè)Ln(x)=滿足插值條件：Ln(

xj)=yj

,j=0,1,?,n定義2.2

若n次多項(xiàng)式lk(

x

)(k=0,1,?,n)在各節(jié)點(diǎn)j,k=0,1,?,n上滿足條件

則稱這n

+1個(gè)n次多項(xiàng)式為這n+1個(gè)節(jié)點(diǎn)上的n次插值基函數(shù)。先求插值基函數(shù)，

k=0,1

,?,

n

.k=0,1,?,n

.L2(x)=y0l0(x)

+y1

l1(x)

+y2l2(x)（類似于前面討論n=1,2時(shí)的情形）(2.10)再構(gòu)造插值多項(xiàng)式（Ln(x)是n+1個(gè)插值基函數(shù)的線性組合）定理2.2（Lagrange）插值多項(xiàng)式通常次數(shù)=n

,但特殊情形次數(shù)可<n

,如：過(guò)三點(diǎn)的二次插值多項(xiàng)式共線時(shí)(2.11)顯然，如此構(gòu)造的L(x)是不超過(guò)n次多項(xiàng)式。當(dāng)n=1時(shí)，稱為線性插值。當(dāng)n=2時(shí)，稱為拋物線插值。

設(shè)為插值節(jié)點(diǎn)，n次多項(xiàng)式滿足條件

由此可得稱為lagrange插值基函數(shù)。Lagrange插值多項(xiàng)式的另一種形式于是，lk(x)可以寫成容易求得(2.12)x0x1xixi+1xn-1xny=f(x)y=p(x)ab在插值區(qū)間a,b上用插值多項(xiàng)式p(x)近似代替f(x),除了在插值節(jié)點(diǎn)xi上沒(méi)有誤差外，在其它點(diǎn)上一般是存在誤差的。若記R(x)=f(x)-p(x),則R(x)就是用p(x)近似代替f(x)時(shí)的截?cái)嗾`差,或稱插值余項(xiàng).我們可根據(jù)后面的定理來(lái)估計(jì)它的大小.問(wèn)題３Lagrange插值多項(xiàng)式的截?cái)嗾`差定理2.3設(shè)f(x)在a,

b有n+1階導(dǎo)數(shù)，x0,x1,…,xn為a,b上n+1個(gè)互異的節(jié)點(diǎn),Ln(x)為滿足

Ln(xi)=f(xi)(i=1,2,…,n)

的n次插值多項(xiàng)式，那么對(duì)于任何xa,b,(a,b),有插值余項(xiàng)其中注意：①余項(xiàng)表達(dá)式僅當(dāng)

存在時(shí)才能應(yīng)用，且是唯一的。②在(

a

,

b

)內(nèi)的具體位置通常不能給出，因此R(x)不能準(zhǔn)確地計(jì)算出來(lái)，只能估計(jì)它的值．③若有

,則截?cái)嗾`差限是

④

n次插值多項(xiàng)式對(duì)次數(shù)不高于n次的多項(xiàng)式完全精確。（因?yàn)椋鬴(x)為次數(shù)不高于n次的多項(xiàng)式,從而Rn(x)=0.）則f(n+1)(ξ)=0,

y0

xxk

xk+1

①線性插值：特別地，n=1,2時(shí)的插值余項(xiàng)：y0x②拋物線插值：xk-1

xk

xk+1

練習(xí)要制作三角函數(shù)sinx的值表，已知表值有四位小數(shù)，要求用線性插值引起的截?cái)嗾`差不超過(guò)表值的舍入誤差，試確定其最大允許的步長(zhǎng)。解f(x)=sinx,

設(shè)xi－１,xi為任意兩個(gè)插值節(jié)點(diǎn)，最大允許步長(zhǎng)記為h=hi=xi

－xi－１，5插值誤差的事后估計(jì)法

在許多情況下，直接用插值余項(xiàng)公式（2.13）來(lái)估計(jì)誤差是困難的。下面以線性插值為例，介紹另一種估計(jì)誤差的方法。由上式可見(jiàn)，可以通過(guò)兩個(gè)結(jié)果的偏差來(lái)估計(jì)插值誤差2.1.3逐次線性插值法為克服這一缺點(diǎn)，通?？捎弥鸫尉€性插值方法求得高次插值。例如在例2.1-2.1*中：則現(xiàn)在令表示函數(shù)關(guān)于節(jié)點(diǎn)的n-1次插值多項(xiàng)式，是零次多項(xiàng)式,,

i1,…,in均為非負(fù)整數(shù)。一般地，可通過(guò)利用兩個(gè)k次插值多次式的線性插值得到（k+1）次插值多項(xiàng)式：上式是關(guān)于x插值多項(xiàng)式，顯然