計(jì)算方法-2-插值法

1、2022-6-111第二章 插值法2022-6-112第二章 插值法 2.1 引言引言 2.2 拉格朗日插值拉格朗日插值 2.3 均差與牛頓插值公式均差與牛頓插值公式 2.4 差分與等距節(jié)點(diǎn)插值差分與等距節(jié)點(diǎn)插值 2.5 埃爾米特插值埃爾米特插值 2.6 分段低次插值分段低次插值 2.7 三次樣條插值三次樣條插值2022-6-113本章要點(diǎn)用簡單的函數(shù)(如多項(xiàng)式函數(shù))作為一個(gè)復(fù)雜函數(shù)的近似,最簡單實(shí)用的方法就是插值.本章主要介紹有關(guān)插值法的一些基本概念，及多項(xiàng)式插值的基礎(chǔ)理論和幾個(gè)常用的插值方法：拉格朗日插值、分段線性插值、牛頓插值、埃爾米特插值和三次樣條插值.2022-6-114 2.1 引

2、言引言且不利于在計(jì)算機(jī)上其函數(shù)形式可能很復(fù)雜對(duì)函數(shù),),(xf個(gè)不同的點(diǎn)上的一組在區(qū)間可以獲得量假如可以通過實(shí)驗(yàn)或測(cè)運(yùn)算1,)(,nbaxfbxxxxan210nixfyii,2 , 1 , 0),(上的函數(shù)值能否存在一個(gè)性能優(yōu)良、便于計(jì)算的函數(shù)滿足比如多項(xiàng)式函數(shù)),(xP一、插值問題2022-6-115niyxPii,2 , 1 ,0)()()(xfxP近似代替并且用這就是插值問題，上式為插值條件的插值函數(shù)為函數(shù)稱函數(shù))()(xfxP則稱之為插值多項(xiàng)式為多項(xiàng)式函數(shù)如果,)(xP稱為插值節(jié)點(diǎn)點(diǎn), 2 , 1 , 0,nixi稱為插值區(qū)間區(qū)間,ba個(gè)等分點(diǎn)上若給定如函數(shù)5,0,sinxy 其插值

3、函數(shù)的圖象如下圖2022-6-11600.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的 插 值xy)()(xPxf和插值函數(shù)對(duì)于被插函數(shù)處的函數(shù)值必然相等在節(jié)點(diǎn)ix)()(xfxP的值可能就會(huì)偏離但在節(jié)點(diǎn)外必然存在

4、著誤差近似代替因此)()(xfxP2022-6-117二、插值法的類型上的代數(shù)插值多項(xiàng)式為在區(qū)間設(shè)函數(shù),)(baxfy nnnxaxaxaaxP2210)(且滿足niyxPiin,2 , 1 ,0)(其中 為實(shí)數(shù)，就稱P(x)為插值多項(xiàng)式，相應(yīng)的插值法稱為多項(xiàng)式插值；若P(x)為分段的多項(xiàng)式，就稱為分段插值；若P(x)為三角多項(xiàng)式，就稱為三角插值。ia本章只討論多項(xiàng)式插值與分段插值2022-6-118 2.2 拉格朗日插值拉格朗日插值 此插值問題可表述為如下： 問題問題 求作次數(shù) 多項(xiàng)式 ，使?jié)M足條件 這就是所謂的拉格朗日（拉格朗日（Lagrange）插值）插值。n ), 1 , 0( ,ni

5、yxLiin)(xLn 拉格朗日（Lagrange）插值公式(以下統(tǒng)稱為Lagrange插值公式)的基本思想是，把pn(x)的構(gòu)造問題轉(zhuǎn)化為n+1個(gè)插值基函數(shù)li(x)(i=0,1,n)的構(gòu)造。2022-6-1192022-6-1110問題問題 已知函數(shù)y=f(x)在點(diǎn)x0,x1上的值為y0,y1，求 作一次一次式 ，使?jié)M足條件 其幾何意義，就是通過兩點(diǎn) 的一條直線。 2.2.1 線性插值與拋物插值線性插值與拋物插值111001)(,)(yxLyxL),(),(1100yxByxA一、線性插值一、線性插值點(diǎn)斜式點(diǎn)斜式)(1xL2022-6-1111L12022-6-1112由直線兩點(diǎn)式可知，通

6、過A，B的直線方程為 稱為線性插值(n=1的情況)，分為內(nèi)插與外推。)()(1001010 xLxxxxyyyy適用情況：適用情況：|01xx 很小時(shí)2022-6-1113)()()11001xlyxly(xL也可表示為如下對(duì)稱形式：其中，0101)(xxxxxl1010 xxxx(x)l顯然，;)(xl,)(xl;)(xl,)(xl010101111000為線性插值基函數(shù)及函數(shù)1 0(x)l(x)l2022-6-1114 線性插值的局限性線性插值的局限性2022-6-1115線性插值舉例線性插值舉例例1: 已知 ， ，求代入點(diǎn)斜式插值多項(xiàng)式得 y=10.71428精確值為 10.723805

7、，故這個(gè)結(jié)果有3位有效數(shù)字。10100 11121 115y)()(0010101xxxxyyyxL2022-6-1116 問題問題 求作二次二次式 ，使?jié)M足條件二次插值的幾何解釋是用通過三個(gè)點(diǎn) 的拋物線來近似考察曲線，故稱為拋物插值。類似于線性插值，構(gòu)造基函數(shù)，要求滿足下式：)(2xL二、拋物插值二、拋物插值) 1, 1()(2kkkjyxLjj)()()()11kk112xlyxlyxly(xLkkkk2022-6-11172022-6-1118x0=100, x1=121, x2=144f(x0)=10, f(x1)=11, f(x2)=12 (121100)(121144)L2(115

8、) =(100121)(100144)(115121)(115144)* 10+(115100)(115144)* 11+(144100)(144121)(115100)(115121)* 12= 10.7228拋物插值拋物插值舉例2(x0 x1)(x0 x2)(xx1)(xx2)f(x0) +(x1x0)(x1x2)(xx0)(xx2)f(x1)+(x2x0)(x2x1)(xx0)(xx1)f(x2)L L2 2(x)=(x)=和用線性插值相比，有效數(shù)字增加一位2022-6-1119為了構(gòu)造 ，我們先定義n次插值基函數(shù)。)(xLn2.2.2 拉格朗日n次插值多項(xiàng)式定義：若n次多項(xiàng)式),1 ,

9、 0()(nixli在n+1個(gè)節(jié)點(diǎn)nxxx10上滿足條件。次插 值插值基上的為節(jié)點(diǎn))(,),(),(次多 項(xiàng)多個(gè)1就稱 這1010n,x,xxxlxlxlnnnn2022-6-1120)()()()()()()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxlnkiiikixxxx0)()(), 2 , 1 , 0(nk)()(10nxxxxxx(x)n 1令)(xkn 1則)()()(1110nkkkkkkkxxxxxxxxxxn+1次多項(xiàng)式對(duì)n=1及n=2時(shí)的情況前面已經(jīng)討論，用類似的推導(dǎo)方法，可得到n次插值基函數(shù)為：2022-6-1121)()()()

10、()()()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxl), 2 , 1 , 0(nk且)(xLnnkknknkxxxxy011)()()()()()(11knknxxxx從而2022-6-1122為記為項(xiàng)式為插值基函數(shù)的插值多以上在節(jié)點(diǎn)于是)(), 1 , 0()(,), 1 , 0()(,xLnixlnixxfyniiininijjjijnnnyxxxxxlyxlyxlyxL001100)()()()()()(總總結(jié)結(jié)稱)(xLn為y=f(x)的拉格朗日插值多項(xiàng)式稱), 1 , 0)(nixli為n次拉格朗日插值基函數(shù)2022-6-1123例3：求

11、過點(diǎn)(2，0) (4，3) (6，5) (8，4) (10，1)的 拉格朗日插值多項(xiàng)式。2022-6-11242022-6-11252022-6-11262022-6-1127拉格朗日插值多項(xiàng)式的缺點(diǎn)：（1）插值基函數(shù)計(jì)算復(fù)雜（2）高次插值的精度不一定高2022-6-1128 2.2.3 插值余項(xiàng)與誤差估計(jì)插值余項(xiàng)與誤差估計(jì)一、插值余項(xiàng)插值的從上節(jié)可知Lagrangexfy)(,niiinxlyxL0)()(滿足nixfxLiin, 1 , 0)()(,bax但)()(xfxLn不會(huì)完全成立因此，插值多項(xiàng)式存在著截?cái)嗾`差,那么我們?cè)鯓庸烙?jì)這個(gè)截?cái)嗾`差呢？2022-6-1129)(xLn)(xR

12、n)()!1()(1)1(xnfnn,)()(01niinxxx其中.,),(xba且依賴于2022-6-1130)()()(xLxfxRnn令上顯然在插值節(jié)點(diǎn)為), 1 , 0(nixi)()()(iniinxLxfxRni, 1 , 0,0個(gè)零點(diǎn)上至少有在因此1,)(nbaxRn)()()(1xxKxRnn設(shè))()()(101nnxxxxxxx為待定函數(shù))(xK其中)()()()()(1xxKxLxfxRnnn證明：證明：假設(shè)在區(qū)間a,b上f(x)的插值多項(xiàng)式為)(xLn2022-6-1131)()()()(1xxKxLxfnn0)(x則有0的區(qū)分與注意xt)(ix且)()()(1inin

13、xxKxR0即個(gè)零點(diǎn)上至少有在區(qū)間若令因此,2,)(,nbatxxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)()()()()(1xxKxLxfnn)()()()(1ininixxKxLxf)()()()()(1txKtLtftnn若引入輔助函數(shù)2022-6-1132根據(jù)羅爾定理,個(gè)零點(diǎn)上有至少在區(qū)間1),()(nbat再由羅爾定理,個(gè)零點(diǎn)上有至少在區(qū)間nbat),()( 依此類推階導(dǎo)數(shù)為零的使得內(nèi)至少有一個(gè)點(diǎn)在區(qū)間1)(,),(ntba0)()1(n)()1(tn)()()()()1(1)1()1(txKtLtfnnnnn由于2022-6-1133)!1()()()1(

14、nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfnn所以)()()(截?cái)嗾`差的余項(xiàng)為插值多項(xiàng)式稱xLxRnn)()()()()()1(1)1()1()1(nnnnnnxKLf因此)!1()()()1(nxKfn02022-6-1134|)(|xRn則)()!1()(1)1(xnfnn)()!1(11xnMnn注意（1）余項(xiàng)表達(dá)式只有在f(x)的高階導(dǎo)數(shù)存在時(shí) 才能應(yīng)用。（2）在ba,內(nèi)的具體位置通常不可能給出，所以，設(shè))() 1(1maxxfMnbxan2022-6-1135例1:225,169,144,)(,. 1三個(gè)節(jié)點(diǎn)為若中在上節(jié)例xxf線性插值的余項(xiàng)為設(shè)Lagran

15、gexR)(1插值的余項(xiàng)為二次LagrangexR)(2解:.)175(截?cái)嗾`差近似值的線性和二次插值做試估計(jì)用fLagrangexxf21)(2341)( xxf2583)( xxf|)(|max2251692xfMx |)169(| f 41014. 1|)(|max2251443xfMx |)144(| f 61051. 12022-6-1136| )175(|2|)225175)(169175(|300| )175(|3|)225175)(169175)(144175(|9300| )175(|1R)175(! 2122M3001014. 121421071. 1| )175(|2R)

16、175(! 3133M93001051. 161631035. 22022-6-1137例2.5 , 5,11)(2xxxf設(shè)函數(shù)ninhihxnni, 1 ,0,10,515 , 5個(gè)節(jié)點(diǎn)等份取將插值多項(xiàng)式次的作試就Lagrangenxfn)(10, 8 , 6 , 4 ,2并作圖比較.解:211)(iiixxfy插值多項(xiàng)式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10, 8 , 6 , 4 ,2n2022-6-1138-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.

17、52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次數(shù)的拉格朗日插值多項(xiàng)式的比較圖Runge現(xiàn)象2022-6-1139結(jié)果表明,并不是插值多項(xiàng)式的次數(shù)越高,插值效果越好,精度也不一定是隨次數(shù)的提高而升高,這種現(xiàn)象在上個(gè)世紀(jì)初由Runge發(fā)現(xiàn),故稱為Runge現(xiàn)象. P44 1、2本章作業(yè)1、給定正弦函數(shù)

18、表如下，試用拉格朗日二次插值，求sin0.57891的近似值并估計(jì)誤差。0.50.60.70.479340.564640.644222、已知函數(shù)表x1.131.151.171.20y=f(x)1.1911.3951.5931.790應(yīng)用拉格朗日插值公式計(jì)算f(1.16)2022-6-1141 2.3 均差與牛頓插值公式均差與牛頓插值公式2022-6-1142 2.3.1 均差及其性質(zhì)均差及其性質(zhì))(xljnjiiijixxxx0)()(nj,2 , 1 ,0我們知道,拉格朗日插值多項(xiàng)式的插值基函數(shù)為形式上太復(fù)雜,計(jì)算量很大,并且重復(fù)計(jì)算也很多由線性代數(shù)的知識(shí)可知,任何一個(gè)n次多項(xiàng)式都可以表示成

19、, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,共n+1個(gè)多項(xiàng)式的線性組合2022-6-1143)()()()()(110102010nnnxxxxxxaxxxxaxxaaxP具有如下形式設(shè)插值多項(xiàng)式)(xP2022-6-1144000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa2022-6-1145一、差商(均差)定義2.nifxxfii, 1 ,0,)(處的函數(shù)值為在互異的節(jié)點(diǎn)設(shè)稱)0()()(,000kxxxfxfxxfkkk)(,

20、)(0差商一階均差關(guān)于節(jié)點(diǎn)為kxxxf2022-6-1146二、均差具有如下性質(zhì)：2022-6-1147,110kkxxxxfkjkjjjjjjjxxxxxxxxxf0110)()()()(2022-6-11482022-6-1149)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四階均差三階均差二階均差一階均差三、均差的計(jì)算方法(表格法):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf規(guī)定函數(shù)值為零階均差均差表2022-6-11502.3.2

21、 牛頓插值公式2022-6-11512022-6-1152)(xRn)()!1()()()(1)1(xnfxNxfnnn)(,110 xxxxxfnn我們稱 為牛頓(Newton)均差插值多項(xiàng)式。)(xNn稱)(xRn 為牛頓均差插值多項(xiàng)式的截?cái)嗾`差。2022-6-11532022-6-11542022-6-1155顯然：2022-6-1156例1：2022-6-1157解：2022-6-11582022-6-1159四、拉格朗日插值與牛頓插值的比較2022-6-1160P59 13、14本章作業(yè)2022-6-1161 2.4 差分與等距節(jié)點(diǎn)插值差分與等距節(jié)點(diǎn)插值2022-6-1162一、差分

22、定義3.稱處的函數(shù)值為在等距節(jié)點(diǎn)設(shè), 1 , 0,)(0nkfkhxxxfkkkkkfff1處的一階向前差分在為kxxf)(1, 1 ,0nk1kkkfff處的一階向后差分在為kxxf)(nk,2 , 1 2.4.1 差分及其性質(zhì)差分及其性質(zhì)2022-6-1163kmkmkmfff111階向前差分處的在為mxxfk)(階向后差分處的在為mxxfk)(依此類推111kmkmkmfff可以證明mkmkmff1kkff222kkff333kkff如kkkfff12處的二階向前差分在為kxxf)(12kkkfff處的二階向后差分在為kxxf)(2022-6-11644433221100fxfxfxfx

23、fxfxkk四階差分三階差分二階差分一階差分0f1f2f3f02f12f22f03f13f04f差分表4f3f2f1f42f32f22f43f33f44f2022-6-1165二、在等距節(jié)點(diǎn)的前提下,差商與差分有如下關(guān)系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hffii2222hfi,321iiiixxxxf312223hffii33! 3 hfiiiiixxff112211,iiiiiixxxxfxxf332121,iiiiiiiixxxxxfxxxf2022-6-11663322223hffii333! 3 hfi,1miiixxxf依此類推m

24、imhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!2022-6-1167 2.4.2 等距節(jié)點(diǎn)插值公式等距節(jié)點(diǎn)插值公式一、牛頓前插公式2022-6-11682022-6-1169二、牛頓向后(差分)插值公式2022-6-11702022-6-1171 牛頓插值法的優(yōu)點(diǎn)是計(jì)算較簡單,尤其是增加節(jié)點(diǎn)時(shí),計(jì)算只要增加一項(xiàng),這是拉格朗日插值無法比的. 但是牛頓插值仍然沒有改變拉格朗日插值的插值曲線在節(jié)點(diǎn)處有尖點(diǎn)，不光滑，插值多項(xiàng)式在節(jié)點(diǎn)處不可導(dǎo)等缺點(diǎn).三、牛頓插值公式與拉格朗日插值相比2022-6-1172 2.5 埃爾米特插值法埃爾米特插值法2022-6-1173 2.5 埃爾

25、米特插值法埃爾米特插值法2022-6-11742022-6-11752022-6-11762022-6-11772022-6-11782022-6-11792022-6-11802022-6-11812022-6-11822022-6-11832022-6-11842022-6-11852022-6-11862022-6-1187解：解：1 )2022-6-11882022-6-11892022-6-11902022-6-11912022-6-11922022-6-11932022-6-11942022-6-11952022-6-11962022-6-1197P60 15、16本章作業(yè)2022

26、-6-1198 2.6 分段插值法分段插值法2022-6-1199例2.5 , 5,11)(2xxxf設(shè)函數(shù)ninhihxnni, 1 ,0,10,515 , 5個(gè)節(jié)點(diǎn)等份取將插值多項(xiàng)式次的作試就Lagrangenxfn)(10, 8 , 6 , 4 ,2解:211)(iiixxfy插值多項(xiàng)式次作LagrangennjnjiiijijnxxxxxxL002)()(11)(10, 8 , 6 , 4 ,2n 2.6.1 高次插值的病態(tài)性質(zhì)高次插值的病態(tài)性質(zhì)2022-6-11100-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0

27、.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次數(shù)的拉格朗日插值多項(xiàng)式的比較圖Runge現(xiàn)象2022-6-11101結(jié)果表明,并不是插值多項(xiàng)式的次數(shù)越高,

28、插值效果越好,精度也不一定是隨次數(shù)的提高而升高,這種現(xiàn)象在上個(gè)世紀(jì)初由Runge發(fā)現(xiàn),故稱為Runge現(xiàn)象. 2022-6-11102 2.6.2 分段線性插值分段線性插值一、 分段線性插值的構(gòu)造2022-6-11103-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101

29、234-1-0.8-0.6-0.4-0.200.20.40.60.81的圖象分段線性插值)(1xLy 的一條折線10,實(shí)際上是連接點(diǎn),n, ,i),y(xii也稱折線插值,如右圖曲線的光滑性較差，在節(jié)點(diǎn)處有尖點(diǎn)。但如果增加節(jié)點(diǎn)的數(shù)量。減小步長,會(huì)改善插值效果)()(lim10 xfxLh上連續(xù)在若,)(baxf因此則2022-6-111042022-6-111052022-6-11106)()(max1xIxfhxxxkk| )( |max2121kkxxxxxxxMkk228)()(maxhMxIxfhbxa分段線性插值的誤差估計(jì)可利用插值余項(xiàng)得到或二、 分段線性插值的誤差估計(jì)其中)(max

30、2xfMbxa 2022-6-11107 2.6.3 分段三次埃爾米特插值分段三次埃爾米特插值2022-6-111082022-6-111092022-6-111102022-6-111112022-6-111122022-6-111132022-6-111142022-6-11115)(1xI2022-6-11116P59 18、19本章作業(yè)2022-6-11117 2.7 三次樣條插值三次樣條插值2022-6-11118 2.7 三次樣條插值三次樣條插值什么是樣條:是指飛機(jī)或輪船等的制造過程中為描繪出光滑的外形曲線(放樣)所用的工具.樣條本質(zhì)上是一段一段的三次多項(xiàng)式拼合而成的曲線在拼接處,

31、不僅函數(shù)是連續(xù)的,且一階和二階導(dǎo)數(shù)也是連續(xù)的1946年,Schoenberg將樣條引入數(shù)學(xué),即所謂的樣條函數(shù)2022-6-11119 2.7.1 三次樣條插值三次樣條插值2022-6-111202022-6-111212022-6-111222022-6-11123 2.7.2 樣條插值函數(shù)的建立樣條插值函數(shù)的建立三對(duì)角方程組三對(duì)角方程組2022-6-11124jjjjjjhxxMhxxMxs 11)(), 1 , 0()(njMxSjj 表達(dá)表達(dá))(xS，由于，由于1,jjxx)(xS 在區(qū)間在區(qū)間上是線性函數(shù)，可表示為上是線性函數(shù)，可表示為)(xs 1)(jjyxs對(duì)積分兩次并利用可定出積分常數(shù)，于是得三次樣條表達(dá)式2022-6-11125) 1, 1 , 0()6()6(6)(6)()(211123131njhxxhMyhxxhMyhxxMhxxMxSjjjjjjjjjjjjjjjjjjjjjjjjjjjjhMMhyyhxxM