數(shù)值分析插值法

1、第六章第六章 插值插值 /* Interpolation */當(dāng)精確函數(shù)當(dāng)精確函數(shù) y = f(x) 非常復(fù)雜或未知時，在一非常復(fù)雜或未知時，在一系列節(jié)點(diǎn)系列節(jié)點(diǎn) x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構(gòu)造一個簡單易算的近似函，由此構(gòu)造一個簡單易算的近似函數(shù)數(shù) g(x) f(x)，滿足條件，滿足條件g(xi) = f(xi) (i = 0, n)。這里的。這里的 g(x) 稱為稱為f(x) 的的插值函數(shù)插值函數(shù)。最常。最常用的插值函數(shù)是用的插值函數(shù)是 ?多項式多項式x0 x1x2x3x4xg(x) f(x)1 拉格朗日多項式拉格朗日多項式 /*

2、 Lagrange Polynomial */niyxPiin,., 0,)(= = =求求 n 次多項式次多項式 使得使得nnnxaxaaxP = =10)(條件：條件：無重合節(jié)點(diǎn)，即無重合節(jié)點(diǎn)，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( = =使得使得111001)(,)(yxPyxP= = =可見可見 P1(x) 是過是過 ( x0 , y0 ) 和和 ( x1, y1 ) 兩點(diǎn)的直線。兩點(diǎn)的直線。)()(0010101xxxxyyyxP- - - - = =101xxxx- - -010 xxxx- - -= y0 + y1l

3、0(x)l1(x) = = =10)(iiiyxl稱為稱為拉氏基函數(shù)拉氏基函數(shù) /* Lagrange Basis */，滿足條件滿足條件 li(xj)= ij /* Kronecker Delta */1 Lagrange Polynomialn 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =niiinyxlxP0)()(，則顯然有，則顯然有Pn(xi) = yi 。li(x)每個每個 li 有有 n 個根個根 x0 xi xn = =- -= =- - - -= =njj i jiniiixxCxxxxxxCxl00)().

4、().()( - -= = =j i jiiiixxCxl)(11)(= = - - -= =njijjijixxxxxl0)()()( = = =niiinyxlxL0)()(Lagrange Polynomial與與 有關(guān)，而與有關(guān)，而與 無關(guān)無關(guān)節(jié)點(diǎn)節(jié)點(diǎn)f1 Lagrange Polynomial定理定理 (唯一性唯一性) 滿足滿足 的的 n 階插值多階插值多項式是唯一存在的。項式是唯一存在的。niyxPii,., 0,)(= = =證明：證明： (利用利用Vandermonde 行列式行列式論證論證)反證：若不唯一，則除了反證：若不唯一，則除了Ln(x) 外還有另一外還有另一 n 階多

5、項階多項式式 Pn(x) 滿足滿足 Pn(xi) = yi ?？疾炜疾?則則 Qn 的階數(shù)的階數(shù), )()()(xLxPxQnnn- -= = n而而 Qn 有有 個不同的根個不同的根n + 1x0 xn注：注：若不將多項式次數(shù)限制為若不將多項式次數(shù)限制為 n ，則插值多項式，則插值多項式不唯一不唯一。例如例如 也是一個插值也是一個插值多項式，其中多項式，其中 可以是任意多項式。可以是任意多項式。= =- - = =niinxxxpxLxP0)()()()()(xp1 Lagrange Polynomial 插值余項插值余項 /* Remainder */設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn))1( nf在在a , b

6、內(nèi)存在內(nèi)存在, 考察截斷誤差考察截斷誤差)()()(xLxfxRnn- -= =, baCfn bxxxan 10，且，且 f 滿足條件滿足條件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，則，則存在存在 使得使得 。)(x 0)()(10= = =xx ),(10 xx 0)(= = 推廣：推廣：若若0)()()(210= = = =xxx ),(),(211100 xxxx 使得使得0)()(10= = = = ),(10 使得使得0)(= = 0)()(0= = = =nxx 存在存在),(ba 使得使得0)()(= = nRn(x) 至少有至少有 個根個根n+1 =

7、 =- -= =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = =- - -= =niixtxKtRnt0)()()()( (x)有有 n+2 個不同的根個不同的根 x0 xn x),(, 0)()1(baxxn = = !)1()()()1(-nxKRxnn 注意這里是對注意這里是對 t 求導(dǎo)求導(dǎo)= = - - - !)1)()()()1()1(nxKLfxnnxn !)1()()()1( = = nfxKxn = = - - = =niixnnxxnfxR0)1()(! ) 1()()( 1 Lagrange Polynomial注：

8、注： 通常不能確定通常不能確定 x , 而是估計而是估計 , x (a,b) 將將 作為誤差估計上限。作為誤差估計上限。1)1()( nnMxf= = - - niinxxnM01|)!1(當(dāng)當(dāng) f(x) 為任一個次數(shù)為任一個次數(shù) n 的的多項式多項式時，時， , 可知可知 ，即插值多項式對于次數(shù)，即插值多項式對于次數(shù) n 的的多項多項式是式是精確精確的。的。0)()1( xfn0)( xRnQuiz: 給定給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是下面哪個是 l2(x)的圖像？的圖像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6

9、x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 1 Lagrange Polynomial例：例：已知已知233sin,214sin,216sin= = = = 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計算插值計算 sin 50 并估計誤差。并估計誤差。 解：解：0 x1x2x185500 =n = 1分別利用分別利用x0, x1 以及以及 x1, x2 計算計算4,610 =xx利用利用216/4/6/214/6/4/)(1 - - - - - -= =

10、xxxL這里這里)3,6(,sin)(,sin)()2( - -= = =xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 - - -= = xxfxRxx00762. 0)185(01319. 01- - - - Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的實(shí)際誤差的實(shí)際誤差 - -0.010010.010013,421 = = =xx利用利用sin 50 0.76008, 00660. 018500538. 01 R內(nèi)插內(nèi)插 /* interpolation */ 的實(shí)際誤差的實(shí)際誤差

11、 0.00596 0.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計算的要計算的 x 所在的區(qū)間的所在的區(qū)間的端點(diǎn)，插值效果較好。端點(diǎn)，插值效果較好。1 Lagrange Polynomialn = 223)()(21)()(21)()()(4363463464363646342 - - - - - - - - - - - - - - -= = xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 - - - - -= =xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的

12、實(shí)際誤差次插值的實(shí)際誤差 0.00061 0.00061高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值但絕對不是次數(shù)越但絕對不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿2 牛頓插值牛頓插值 /* Newtons Interpolation */Lagrange 插值雖然易算，但若要增加一個節(jié)點(diǎn)時，插值雖然易算，但若要增加一個節(jié)點(diǎn)時，全部基函數(shù)全部基函數(shù) li(x) 都需重新算過。都需重新算過。將將 Ln(x) 改寫成改寫成.)()(102010 - - - - - xxxxaxxaa).(10- - - - nnxxxxa的形式，希望每加一個節(jié)點(diǎn)時，的形式，希望每加一個節(jié)點(diǎn)時，只附加一項只附加一項

13、上去即可。上去即可。? 差商差商( (亦稱均差亦稱均差) ) /* divided difference */),()()(,jijijijixxjixxxfxfxxf - - -= =1階差商階差商 /* the 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji - - -= =2階差商階差商2 Newtons Interpolation11101010111010,.,.,.,.,., - - - - - -= =- - -= =kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfx

14、xf(k+1)階差商：階差商： = = = =kiikikxxfxxf010)()(,., 事實(shí)上事實(shí)上其中其中,)()(01= = - -= =kiikxxx = = - -= = kijjjiikxxx01)()( 差商的值與差商的值與 xi 的順序無關(guān)！的順序無關(guān)！2 Newtons Interpolation 牛頓插值牛頓插值 /* Newtons Interpolation */,)()()(000 xxfxxxfxf- - = =,)(,101100 xxxfxxxxfxxf- - = =,.,)(,.,.,0010nnnnxxxfxxxxfxxxf- - = =- -).(.)(

15、)()(10102010- - - - - - - - - = =nnnxxxxaxxxxaxxaaxN12 n- -11+ (x - - x0) 2+ + (x - - x0)(x - - xn- -1) n- -1.)(,)(,)()(102100100 - - - - - = =xxxxxxxfxxxxfxfxf).(,.,100- - - - nnxxxxxxf)().(,.,100nnnxxxxxxxxxf- - - - - -Nn(x)Rn(x)ai = f x0, , xi 2 Newtons Interpolation注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)，

16、 只是算法不同，故其只是算法不同，故其余項也相同，即余項也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfkxnkn = = ),(,!)(,.,maxmin)(0 xxkfxxfkk = = 實(shí)際計算過程為實(shí)際計算過程為f (x0)f (x1)f (x2)f (xn- -1)f (xn)f x0, x1f x1, x2 f xn- -1, xnf x0, x1 , x2 f xn- -2, xn- -1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn- -1, xn, xn+1 f x1, , xn+1 f x0, , xn+1Newton插值多

17、項式的計算 =-10)(jjxx=-20)(jjxx-=-10)(njjxxNewton插值公式計算舉例)12)(11(0035. 0)11(0870. 03979. 2)(2-=xxxxN2.442275 5.05.00035.05.00870.03979.2 )5.11(5.11ln2= N所以：Newton插值公式計算例3續(xù)=-1210)(kkx=-1310)(kkx4423522.2 )5 .1()5 .0(5 .05 .1000005.0)5 .0(5 .0 5 .100022.05 .05 .100415.05 .10953.03026.2 )5 .11(5 .11ln4=-= N

18、所以：可用,321xxxxf0000825. 05 . 15 . 05 . 000022. 0)5 .11)(5 .11)(5 .11(,)(32143212=-xxxxxxxfxR近似00022. 0,4321=xxxxf的近似值，,321xxxxf的近似值。)(2xR2 Newtons Interpolation 等距節(jié)點(diǎn)公式等距節(jié)點(diǎn)公式 /* Formulae with Equal Spacing */向前差分向前差分 /* forward difference */iiifff- -= = 1ikikikikffff1111)(- - - - - - - = = = = 向后差分向后差

19、分 /* backward difference */111- - - - - - = = ikikikfffi- -1iifff- -= = 中心差分中心差分 /* centered difference */212111- - - - - -= =ikikikfff 其中其中)(221hiixff = = 當(dāng)節(jié)點(diǎn)當(dāng)節(jié)點(diǎn)等距等距分布時分布時:),.,0(0nihixxi= = = =More given on p.113-114.差分計算造表差分計算造表（續(xù)1）差分計算造表（續(xù)2）差分計算舉例60. 0lnln80. 0lnln40. 0lnln005103. 0)2(43434454544

20、1414=-xfxfxf65. 0ln27 . 06 . 0ln00750. 0 3321335323=fff又如差分的性質(zhì)kmkmkmbaf=.)!(!)1()1(2332002114212321231212為二項式展開式的系數(shù)其中一般地：例如：jmjmCjmfjmffjmffffffffffffffffffffjmjkmjjkmjmkmjjkmkkkkkkkkkkkkkkkkkk-=-=-=-=-=-=-=-=-=-=-=-差分的性質(zhì)（續(xù)1）2422223434422:-=-=-=ffffffff例如22221221211121111122)(122)(1,)()(,hfhffhhfhff

21、hxxxxfxxfxxxfhfhfxxxfxfxxfkkkkkkkkkkkkkkkkkkkkkkk=-=-=-=-=例如：2mkmkmmkmkmffff-=差分的性質(zhì)（續(xù)2）15)-(5 ), 2 , 1( !1 !1,1=mfhmfhmxxxfmkmmkmmmkkk16)-(5 )( ,!)(1mkkmmmkkkmkmxxfhxxxfhmf=2.4 等距節(jié)點(diǎn)插值公式 )()(!)(! 2)(1 )()(,)(,)()(110010202000110100100-=-=nnnnnnxxxxxxhnfxxxxhfxxfhfxxxxxxxxxfxxxxfxfxNNewton向前插值公式向前插值公式

22、17)-(5 !) 1() 1(! 2) 1()(002000fnntttfttftfthxNnn-=18)-(5 ),( )()!1()() 1( )()()!1()()(0) 1(110) 1(nnnnnnxxfhnntttxxxxxxnfxR-=-=Newton向后插值公式 19)-(5 !) 1() 1(! 2) 1()(2nnnnnnnfnntttfttftfthxN-=20)-(5 ),( )()!1()() 1()(0) 1(1nnnnxxfhnntttxR=表5-72) 1( -tt2) 1( -tt=-20)(! 31jjt=-20)(! 31jjt-=-10)(!1njjtn-=-10)(!1njjtn2) 1( tt=20)(!31jjt-=10)(!1njjtnNewton向前、向后插值公式 舉例)1(2tt)1(2-tt)2)(1(! 3ttt)2)(1(! 3-tttNewton向前、向后插值公式 舉例（續(xù)1）6433003102 sin)2109