數(shù)值分析第五章

1、拉格朗日插值公式拉格朗日插值公式均差與牛頓插值公式均差與牛頓插值公式埃爾米特插值函數(shù)埃爾米特插值函數(shù)樣條插值方法樣條插值方法數(shù)值分析 Ch5引例引例.函數(shù)函數(shù) sin x 的逼近的逼近(1) 線性函數(shù)逼近線性函數(shù)逼近 y0 = x(2)泰勒級數(shù)逼近泰勒級數(shù)逼近 y1(x)= x x3/3! + x5/5! (3)拋物線逼近拋物線逼近(error=0.0559) y2=4x( x)/2(4)帕特逼近帕特逼近(error=0.0036)0123400.511.50123400.511.50123400.51)536411088(1555122260166320)(4253xxxxxxP 00.20

2、.40.60.811.21.41.61.82-0.4-0.200.20.40.6(1)復(fù)雜函數(shù)的計算復(fù)雜函數(shù)的計算;(2)函數(shù)表中非表格點計算函數(shù)表中非表格點計算(3)光滑曲線的繪制光滑曲線的繪制;(4)提高照片分辯率算法提高照片分辯率算法(5)定積分的離散化處理定積分的離散化處理;(6)微分方程的離散化處理微分方程的離散化處理;(7)積分方程的離散化處理積分方程的離散化處理;插值法的應(yīng)用背景插值法的應(yīng)用背景:510155101524682468已知已知f(x)在點在點xi上的函數(shù)值上的函數(shù)值 yi=f(xi), (i=0,1,2,n)則稱則稱 P(x) 為為 f(x) 的的插值函數(shù)插值函數(shù).

3、 稱稱 x0, x1, , xn為為 插值結(jié)點插值結(jié)點; 稱稱 f(x) 為為被插值函數(shù)被插值函數(shù). 如果如果 P(x)=a0 + a1x + anxn滿足滿足: P(xk)= yk (k = 0,1,n)設(shè)設(shè) f(x)C a , b, 取點取點 a x0 x1xnb代數(shù)插值問題代數(shù)插值問題插值條件插值條件點點,則滿足插值條件則滿足插值條件 P(xk)= yk (k = 0,1,n)的的 n 次插值多項式次插值多項式 P(x)=a0 + a1x + anxn存在而且是唯一的存在而且是唯一的。 nnnnnnnnnyxaxaayxaxaayxaxaa101111000010證明證明: 由插值條件由

4、插值條件P(x0)= y0P(x1)=y1P(xn)=yn定理定理5.1 若插值結(jié)點若插值結(jié)點x0, x1, xn 是是 (n+1)個互異個互異nnnnnxxxxxxA111|1100 方程組系數(shù)矩陣取行列式方程組系數(shù)矩陣取行列式故方程組有唯一解故方程組有唯一解.從而插值多項式從而插值多項式 P(x) 存在而且是唯一的存在而且是唯一的.例例5.1 誤差函數(shù)表可構(gòu)造誤差函數(shù)表可構(gòu)造6次插值函數(shù)次插值函數(shù)0)(0 jijinxxx 0 0.5000 1.0000 1.5000 2.0000 2.5000 3.0000y 0 0.5205 0.8427 0.9661 0.9953 0.9996 1.

5、0000)()(001010 xxxxyyyxL 過兩點直線方程過兩點直線方程求滿足求滿足: L(x0)=y0 , L(x1)=y1的線性函數(shù)的線性函數(shù) L(x)已知函數(shù)表已知函數(shù)表 x x0 x1 f(x) y0 y1例例 求求 的近似值的近似值(函數(shù)值函數(shù)值: 10.7238)11510.7143)100115(100121101110115 01010110)(,)(xxxxxlxxxxxl 記記當當 x0 x x1 時時 0l0(x)1, 0l1(x)1x x0 x1l0(x) 1 0l1(x) 0 11100)()()(yxlyxlxL y0 y1 = 1 0y0 + 0 1y100

6、111010)(yxxxxyxxxxxL 對稱形式對稱形式二次插值問題二次插值問題 x x0 x1 x2 f(x) y0 y1 y2已知函數(shù)表已知函數(shù)表求函數(shù)求函數(shù) L(x)=a0 + a1x + a2 x2 滿足滿足: L(x0)=y0 , L(x1)=y1, L(x2)=y2y0 y1 y2 = 1 0 0y0 + 0 1 0y1+ 0 0 1y2L(x)=l0(x)y0+l1(x)y1+l2(x)y2，)()()(2010210 xxxxxxxxxl 二次插值函數(shù)二次插值函數(shù): L(x)=l0(x)y0+l1(x)y1+l2(x)y2，xx0 x1x2l0(x) 1 0 0l0(x) 1

7、00l1(x) 010l2(x) 0 0 1L(x) y0y1y2 xx0 x1 x2)()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl 二次插值基函數(shù)圖形二次插值基函數(shù)圖形00.51-0.500.5100.51-0.500.5100.5100.51取取 x0 =0, x1 = 0.5, x2 = 100.51-0.500.51l0(x)=2(x 0.5)(x 1);l1(x)= 4 x(x 1);l2(x) = 2(x 0.5)x拉格朗日插值公式拉格朗日插值公式插值條件插值條件:L(xk)= yk (k = 0,1,n)nnnyxlyxlyxlxL

8、)()()()(1100 )()()()()()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl 其中其中,第第k (k=0,1,，n)個插值基函數(shù)個插值基函數(shù)nkjjjkjkxxxxxl 0)()()(或或:Runge反例反例: , (-5x5)211)(xxf -5-4-3-2-1012345-0.500.511.52L10(t) f(t) f(x)取取xk= 5+k 計算計算: f(xk) (k=0,1,10) 構(gòu)造構(gòu)造L10(x).取取:tk= 5+0.05k (k=0,1,200),計算計算: L10(tk)x=-5:5;y=1./(1+x.2);t=-5

9、:0.05:5;y1=1./(1+t.2);n=length(t);for i=1:n z=t(i);s=0; for k=1:11 Lk=1;u=x(k); for j=1:11 if j=k,Lk=Lk*(z-x(j)/(u-x(j); end end s=s+Lk*y(k); end y2(i)=s;endplot(x,y,ko,t,y1,t,y2,r)00111010)(yxxxxyxxxxxL 兩點線性插值兩點線性插值插值余項插值余項(誤差誤差): R(x) = f(x) L(x) 由插值條件由插值條件,知知 R(x)=C(x) (x x0)(x x1)即即 f(x) L(x) =

10、C(x) (x x0)(x x1) C(x) = ? ax0 x1xnb則對任何則對任何xa , b, 滿足滿足 Ln(xk) = f(xk) 的的 n 次次插值多項式插值多項式Ln(x) 的誤差的誤差)()!1()()()()(1)1(xnfxLxfxRnnnnn )()()(101nnxxxxxxx 其中其中,),(ban 且與且與x有關(guān)有關(guān)定理定理5.2 設(shè)設(shè) f(x)Ca, b, 且且 f (x) 在在(a, b)內(nèi)具有內(nèi)具有n+1階導(dǎo)數(shù)階導(dǎo)數(shù), 取插值結(jié)點取插值結(jié)點證明證明: 記記 n+1(x) =(x x0)(x x1)(x xn)f(x) Ln(x)= C(x) n+1(x)取定

11、取定 x(a, b), 設(shè)設(shè) t( a, b ). 構(gòu)造函數(shù)構(gòu)造函數(shù) )()()()(1tCtLtftFnn 顯然顯然, F(x) = 0, F(xj) = 0, ( j = 0,1,n ) 由插值條件由插值條件Ln(xk) = f(xk) (k = 0,1,n)知存在知存在C(x)使得使得 F(t) 有有(n+2)個相異零點個相異零點. 根據(jù)根據(jù)Rolle定理定理, F(t)在區(qū)間在區(qū)間(a, b)內(nèi)至少有內(nèi)至少有 (n +1)個相異零點個相異零點. 0)!1()()1( nCfn )!1()()1( nfCn )()!1()()()(1)1(xnfxLxfnnn 依此類推依此類推,F (

12、n+ 1 )(t) 在區(qū)間在區(qū)間 ( a, b ) 內(nèi)至少有內(nèi)至少有一個零點一個零點。故存在故存在 (a, b), 使使F(n+1)( )=0)()()()()1(1)1()1()1(tCtLtftFnnnnnn 3232752)(xxxxP 例例 分析三次多項式插值誤差分析三次多項式插值誤差 x 0 1 2 3P3(x) -2 -2 -4 40)()4(3 xP)3)(2)(1()(! 41)()4(33 xxxxPxR 0)(3 xR32332752)()(xxxxPxL 例例 取被插值函數(shù)為正弦函數(shù)取被插值函數(shù)為正弦函數(shù) f(x) = sin x，取三點做取三點做二次插值。二次插值。 2

13、/ x 0 Sin x 0 1 06/ | )(2/(|cos|2 xxxR22/ )(4)( xxxL 486142|322 R思考題思考題: : 在區(qū)間在區(qū)間 內(nèi)增加插值結(jié)點是否會內(nèi)增加插值結(jié)點是否會導(dǎo)致導(dǎo)致RungeRunge現(xiàn)象現(xiàn)象, 0 例例5.3 設(shè)設(shè) y = f(x) 在區(qū)間在區(qū)間 a, b上有連續(xù)上有連續(xù),且且 f (x) 在在 (a, b)內(nèi)具有內(nèi)具有2階導(dǎo)數(shù)階導(dǎo)數(shù),已知已知f (x)在區(qū)間端點處在區(qū)間端點處的值的值.如果當如果當x (a, b)時時,有有|f (x)|M. 試證明試證明21)(8| )(|abMxR 證明證明 由由Lagrange插值誤差定理插值誤差定理)(

14、2)()()()(11bxaxfxLxfxR 令令h(x) = |( x a )( x b )| 4)()2()(max2abbahxhbxa 21)(8| )(|abMxR 應(yīng)用應(yīng)用: 考慮制做考慮制做 sin x 在在0, , 上等距結(jié)點的函數(shù)表上等距結(jié)點的函數(shù)表, ,要要求用線性插值計算非表格點數(shù)據(jù)時求用線性插值計算非表格點數(shù)據(jù)時, ,能準確到小數(shù)后兩能準確到小數(shù)后兩位位, ,問函數(shù)表中自變量數(shù)據(jù)的步長問函數(shù)表中自變量數(shù)據(jù)的步長h應(yīng)取多少為好應(yīng)取多少為好？ 解解：設(shè)應(yīng)取的步長為設(shè)應(yīng)取的步長為h , 則則 xj = jh ( j = 0,1,n). 當當 x(xj , xj+1)時時88)

15、(| )(|max| )(|2211hxxxfxRjjxxxjj sin)(sin)(1sin11jjjjxxxxxxhx 2210218 h h 0.2 只須只須取取x0, x1, x2,求二次函數(shù)求二次函數(shù) P(x)=a0 + a1(x x0) + a2 (x x0)(x x1)滿足條件滿足條件 P(x0)=f(x0), P(x1)=f(x1), P(x2)=f(x2) )()()()()()(21202202101011000 xfxxxxaxxaaxfxxaaxfa 插值條件引出關(guān)于插值條件引出關(guān)于a0, a1, a2方程方程牛頓插值問題牛頓插值問題010110)()(,xxxfxfx

16、xf 121221)()(,xxxfxfxxf 021021210,xxxxfxxfxxxf 解下三角方程組過程中引入符號解下三角方程組過程中引入符號a0 = f(x0), a1 = fx0, x1, a2 = fx0, x1, x2P(x)= f(x0) + fx1, x2(x x0) + fx0, x1, x2(x x0)(x x1)牛頓插值公式牛頓插值公式:定義定義5.3 若已知函數(shù)若已知函數(shù) f(x) 在點在點 x0,x1,xn 處的處的值值 f(x0), f(x1), , f(xn).如果如果 i j ,則則( j = 0,1,n-1 ) 一階均差一階均差n階均差階均差010110,

17、xxxxfxxfxxxfnnnn jjjjjjxxxfxfxxf 111)()(,二階均差二階均差jjjjjjjjjxxxxfxxfxxxf 212121,( j = 0,1,n-2 ) x- 2-1013y-56-16-2-24例例 由函數(shù)表由函數(shù)表求各階均差求各階均差xf(x) 一階均差一階均差二階均差二階均差三階均差三階均差-2-56-1-16 400-2 14 -131-2 0 -7 23 4 3 1 2解解:按公式計算一階均差按公式計算一階均差、二階均差二階均差、三階均差三階均差MATLAB程序計算程序計算x=-2 -1 0 1 3;y=-56 -16 -2 -2 4;data=x,

18、y;dy=y;n=length(x);for k=1:n-1 dx=x(k+1:n)-x(1:n-k) dy=diff(dy)./dx; f=zeros(n,1);f(k+1:n)=dy; data=data,f;enddata -2 -56 -1 -16 40 0 -2 14 -13 1 -2 0 -7 2 3 4 3 1 2 0函數(shù)值的計算函數(shù)值的計算:N3(x) = 56 + (x + 2) 40 +(x + 1) 13 +2 xN3(x) = 56 + 40(x + 2) 13(x + 2)(x + 1) + 2(x + 2)(x + 1) x 22680560 a5439401 a7

19、6132 a23 a3232752)(xxxxP -2-10123-60-50-40-30-20-10010根據(jù)代數(shù)插值存在唯一性定理根據(jù)代數(shù)插值存在唯一性定理, n 次牛頓插值公式恒次牛頓插值公式恒等于等于n次拉格朗日插值公式次拉格朗日插值公式,誤差余項也相等，即誤差余項也相等，即)()!1()()(1)1(xnfxRnnn 牛頓多項式算法牛頓多項式算法: 記插值節(jié)點為記插值節(jié)點為x0,x1,xn, f(x)的各階差商為的各階差商為 f0, f1, f2, , fn sfn 計算計算 s fk+s*(x-xk) (k=n-1,n-2, , 0)(1)(3) N(x)=s)()()(101nn

20、xxxxxxx 取插值結(jié)點取插值結(jié)點: ax0 x1xnb滿足滿足Ln(xk)=f(xk)的的 n 次多項式插值余項次多項式插值余項)()!1()()()()(1)1(xnfxLxfxRnnnnn )()()(101nnxxxxxxx 其中其中,選取選取: x0, x1 , xn , 使使min| )(|max1 xnbxa 結(jié)論結(jié)論: 切比雪夫多項式切比雪夫多項式Tn+1(x)的全部零點。的全部零點。拉格朗日插值余項拉格朗日插值余項 n+1階切比雪夫多項式階切比雪夫多項式: Tn+1=cos(n+1) cos = x 代入得代入得 Tn+1( x ) = cos(n+1) arccos x

21、)1(2)12(cos( nkxk 即即2)12(arccos)1( kxn( k=0,1,n )取取 f(x)C1, 1, 令令 x = cos , 則有則有 1, 1 0, 將將g( ) = f(cos )展開成余弦級數(shù)展開成余弦級數(shù) 10cos21)(nnnaag 切比雪夫結(jié)點切比雪夫結(jié)點211)(xxf 例例1. 函數(shù)函數(shù)取等距插值結(jié)點取等距插值結(jié)點: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 x-5, 5 11(x)=(x+5)(x+4)(x+3)(x+2)(x+1)x(x-1)(x-2)(x-3)(x-4)(x-5)(!11)()()(11)11(1

22、0 xfxLxfn 11(x) -4.9491 -4.5482 -3.7787 -2.7032 -1.4087 0.0000 1.4087 2.7032 3.7787 4.5482 4.9491在在-5, 5區(qū)間上區(qū)間上,取取11個切比雪夫結(jié)點個切比雪夫結(jié)點)22)12(cos(5 kxk( k=10, 9, 8, , 1, 0 ) 11(x)=(x x0)(x x1)(x x2)(x x10) 11(x) 00)(yxf 11)(yxf 00)(mxf 11)(mxf 插值函數(shù)插值函數(shù) H(x)= a0 + a1x + a2x2 + a3x3插值條件插值條件三次三次Hermite插值問題插值

23、問題xx0 x1H(x)y0y1H(x)m0m1設(shè)設(shè),)(104xxCxf 已知已知-0.4-0.200.20.40.60.811.21.41.6-0.6-0.4-0.200.20.40.60.81例例2. 插值條件插值條件:求求3次插值函數(shù)次插值函數(shù).)1()(1xxCxH 解解: 設(shè)設(shè)積分積分,得得利用函數(shù)插值條件利用函數(shù)插值條件, 得得 C2 = 0 , C1 = 6 H(x) = 3x2 2x3 = (3 2x)x2 x 0 1 H(x) 0 1 H(x) 0 02321)23(61)(CxxCxH 利用基函數(shù)表示利用基函數(shù)表示Hermite插值插值)()()()()(11001100

24、 xmxmxyxyxH x0 x1 10 00 01 0 0)(0 x )(1x )(0 x )(1x x)(1x )(0 x x0 x1 00 10 0 0 0 1)(1x )(0 x x令令010 xxxx 則則0111xxxx 20110100)(21()(xxxxxxxxx 20100111)(21()(xxxxxxxxx )1()(1 CH21)23()( 1)23()(20 設(shè)設(shè)2216/ )23()(CCH 則則2)1(21 22)1(2)1( )21)(1(2 )21()1(2 )(1 )(0 0 1 10 00 0 1 0 0)(1 )(0 201011)()(xxxxxxx

25、 210)()(xxxxCxH 設(shè)設(shè)1)()(2010 xxCxH201100)()(xxxxxxx )(1x )(0 x x0 x1 00 10 0 0 0 1)(1x )(0 x x1)()(2011 xxCxH)()()(120 xxxxCxH 設(shè)設(shè)210)4(3)(! 4)()()()(xxxxfxHxfxR 兩點兩點Hermite插值的誤差估計式插值的誤差估計式證明證明: 由插值條件知由插值條件知構(gòu)造輔助函數(shù)構(gòu)造輔助函數(shù)2120)()()()()(xtxtxCtHtftF 利用利用 f(x) H(x)=C(x)(x x0)2(x x1)22120)()()(xxxxxCxR 取取 x

26、 異于異于 x0 和和 x1, 有有0)()(00 xRxR0)()(11 xRxR2120)()()()()(xtxtxCtHtftF 0) ! 4)()()()4()4( xCfF ! 4)()()4( fxC 210)4()(! 4)()(xxxxfxR 顯然顯然,F(t) 有三個零點有三個零點 x0, x, x1, 由由Roll定理知定理知,存在存在 兩個零點兩個零點 t0, t1. )(tF )(tF 故故 有四個相異零點有四個相異零點1100 xtxtx 反復(fù)應(yīng)用反復(fù)應(yīng)用 Roll 定理定理, 得得 F(4)(t) 知一個零點設(shè)為知一個零點設(shè)為 分段線性插值分段線性插值插值節(jié)點滿足

27、插值節(jié)點滿足: x0 x1xn 已知已知yj=f (xj) ( j= 0,1,2,n)1111)( jjjjjjjjhyxxxxyxxxxxL( j= 0,1,n-1)xxj，xj+1時時, 線性插值函數(shù)線性插值函數(shù)分段三次分段三次Hermite插值插值 jjjjjjjhyxxxxxxxxxH2111)(21()( ( j= 0,1,2,n-1)已知函數(shù)值和導(dǎo)數(shù)值已知函數(shù)值和導(dǎo)數(shù)值 )(),(jjjjxfmxfy xxj，xj+112111)(21( jjjjjjjyxxxxxxxxjjjjjmxxxxxx211)( 1211)( jjjjjmxxxxxx( j= 0,1,2,n)一元函數(shù)線性

28、插值基一元函數(shù)線性插值基01 2/ )1(1 N2/ )1(2 N二元函數(shù)雙線性插值基二元函數(shù)雙線性插值基1 4/ )1)(1(1 4/ )1)(1(2 4/ )1)(1(3 4/ )1)(1(4 E )1, 1(1 P)1 , 1(3P)1 , 1(4 P)1, 1(2 P1 , 1 N1 1, 0N2 0, 1 01000110)()(111 NN )()(223 NN )()(214 NN )()(111 NN )()(122 NN 10001010 00101001 00010101 例例1. 飛機機翼剖面圖飛機機翼剖面圖 1.1.數(shù)據(jù)采集數(shù)據(jù)采集2. 數(shù)據(jù)插值處理數(shù)據(jù)插值處理X 0

29、-0.4552 -0.6913 -0.8640 -0.9689 -0.9996Y 0 0.3285 0.3467 0.2716 0.1408 -0.0160T=1:6;t=1:.2:6;x=spline(T,X,t);y=spline(T,Y,t);例例2:龍格函數(shù)的插值逼近龍格函數(shù)的插值逼近 -505-0.500.51211)(xxf -505-0.500.517結(jié)點等距插值結(jié)點等距插值7結(jié)點切比雪夫插值結(jié)點切比雪夫插值7結(jié)點樣條插值結(jié)點樣條插值7結(jié)點埃爾米特插值結(jié)點埃爾米特插值-50500.51-50500.51利用龍格函數(shù)的數(shù)據(jù)表做樣條插值第一步利用龍格函數(shù)的數(shù)據(jù)表做樣條插值第一步 x-

30、5.0 -3.33 -1.66 0 1.66 3.33 5.0 y0.038 0.082 0.264 1.0 0.264 0.082 0.038m 0.014 -0.0054 0.4142 0. -0.4142 0.0054-0.014 y 0.0140.045 0.233 0 -0.233 -0.045 -0.014估算結(jié)點處導(dǎo)數(shù)值估算結(jié)點處導(dǎo)數(shù)值 mk, 由三對角方程組求解得出由三對角方程組求解得出 54321543214114114114114FFFFFmmmmmhyyFkkk)(311 (k=1，2，3，4，5，6)， h=10/6 定義定義 5.4 給定區(qū)間給定區(qū)間a , b上的一個

31、分劃上的一個分劃: a = x0 x1 xn = b已知已知 f(xj) = yj (j = 0,1,n), 如果如果 ,),(,),(,),()(1212101nnnxxxxSxxxxSxxxxSxS滿足滿足: (1) S(x)在在 xj，xj+ 1上為三次多項式上為三次多項式; (2) S”(x)在區(qū)間在區(qū)間a，b上連續(xù)上連續(xù); (3) S(xj) = yj ( j = 0,1,n). 則稱則稱 S(x)為三次樣條插值函數(shù)為三次樣條插值函數(shù).當當xxj , xj+ 1 ( j= 0,1,n-1 )時時 Sj(x)= aj + bj x + cj x2 + dj x3插值條件插值條件: S(

32、xj) = yj ( j = 0,1,n)連續(xù)性條件連續(xù)性條件: S(xj+0) =S(xj-0) ( j = 1,n-1) S(xj+0) =S(xj-0) ( j = 1,n-1) S”(xj+0) =S”(xj-0) ( j = 1,n-1)由樣條定義由樣條定義,可建立方程可建立方程(4n-2)個！個！ n個三次多項式個三次多項式, 待定系數(shù)共待定系數(shù)共4n個個！方程數(shù)少于未知數(shù)個數(shù)方程數(shù)少于未知數(shù)個數(shù) ？(1)自然邊界條件自然邊界條件: S”(x0)=0, S”(xn)=0例例 5.7 已知已知f(1) = 1, f(0) = 0, f(1) = 1.求求1，1 上的三次自然樣條上的三

33、次自然樣條(滿足自然邊界條件滿足自然邊界條件). 解解 設(shè)設(shè) ,)(1001222232112131xdxcxbxaxdxcxbxaxS則有則有: a1+b1c1+d1=1,d1=0, a2+b2+c2+d2=1 d1=d2, c1=c2, b1=b2 (2)周期邊界條件周期邊界條件: S(x0)=S(xn), S”(x0)=S”(xn)(3)固定邊界條件固定邊界條件: S(x0)=f (x0), S(xn)=f (xn)由自然邊界條件由自然邊界條件: 6a1+2b1=0, 6a2+2b2=0 解方程組解方程組,得得 a1=-a2=1/2, b1=b2=3/2, c1=c2=d1=d2=0,)(1023210123212323xxxxxxxS問題的解問題的解 -1-0.8-0.6-0.4-0.200.20.40.60.8100.20.40.60.