計(jì)算方法 Newton插值【優(yōu)選資料】

1、第2次 Newton 插值,計(jì)算方法 (Numerical Analysis),1,知識(shí)研究,牛頓插值多項(xiàng)式的概念 差商及其性質(zhì) 牛頓插值多項(xiàng)式的系數(shù)與誤差余項(xiàng)的導(dǎo)出 利用牛頓插值多項(xiàng)式近似求解的例子,2,知識(shí)研究,牛頓插值多項(xiàng)式的概念,3,知識(shí)研究,3 均差與牛頓插值多項(xiàng)式 拉格朗日插值多項(xiàng)式的優(yōu)點(diǎn)與缺點(diǎn) 優(yōu)點(diǎn)：結(jié)構(gòu)對(duì)稱，使用方便。 缺點(diǎn)：由于是用基函數(shù)構(gòu)成的插值，要增加一個(gè)節(jié)點(diǎn)時(shí)，所有的基函數(shù)必須全部重新計(jì)算，不具備承襲性，還造成計(jì)算量的浪費(fèi)。,4,知識(shí)研究,例如：3個(gè)節(jié)點(diǎn)，拋物插值的情況：,若要新增加一個(gè)節(jié)點(diǎn)，而進(jìn)行3次插值的時(shí)候，則需要重新計(jì)算,5,知識(shí)研究,試圖改進(jìn)：我們要構(gòu)造一種具

2、有承襲性的插值多項(xiàng)式P(x)來(lái)克服這個(gè)缺點(diǎn)， 即，每增加一個(gè)新節(jié)點(diǎn)時(shí)，只需在P(x)原來(lái)的表達(dá)式中增加相應(yīng)的一項(xiàng)即可，而不改變P(x)的原來(lái)已經(jīng)存在的表達(dá)式部分。 這就是牛頓插值多項(xiàng)式的特點(diǎn)。,6,知識(shí)研究,可以證明, 可將滿足插值條件 p(x0) = y0 , p(x1) = y1 ， p(xn) = yn 的n次插值多項(xiàng)式, 寫(xiě)成如下形式:,基函數(shù)： (x-x0 ), (x-x0 )(x-x1 ), ，(x-x0 )(x-x1 )(x-xn-1),7,知識(shí)研究,定義：給定n+1個(gè)插值節(jié)點(diǎn)x0 , x1 , xn, 如下形式的插值多項(xiàng)式稱為Newton插值多項(xiàng)式：,（3.12）,其中ak (

3、k=0,1,2,n)為待定系數(shù)。,無(wú)x n ,將出現(xiàn)在系數(shù)中,8,知識(shí)研究,牛頓插值多項(xiàng)式Nn(x)是插值多項(xiàng)式p(x)的另一種表示形式, 與Lagrange多項(xiàng)式相比 它克服了“增加一個(gè)節(jié)點(diǎn)時(shí)整個(gè)計(jì)算工作重新開(kāi)始”的缺點(diǎn), 節(jié)省乘除法運(yùn)算次數(shù), 在Newton插值多項(xiàng)式中用到的差商等概念，又與數(shù)值計(jì)算的其他方面有密切的關(guān)系.,要確定牛頓插值多項(xiàng)式Nn(x)系數(shù)，需要利用下一節(jié)差商的計(jì)算。,Home,9,知識(shí)研究,差商及其性質(zhì),10,知識(shí)研究,3.1 差商及其性質(zhì),定義：函數(shù)y= f(x)在區(qū)間xi ,xi+1上的平均變化率,稱為f(x)關(guān)于xi , xi+1 的1階差商。,定義2階差商,11

4、,知識(shí)研究,2階差商 fxi, xj, xk是指,一般地,可定義xi, xi+1 , xi+n上的n階差商：,12,知識(shí)研究,為了方便地計(jì)算差商，需要建立差商表。表中的箭頭 指向表示更高階差商所需要的低階差商的參與。,13,知識(shí)研究,例2.11 求 f(x)= x3在節(jié)點(diǎn) x=0, 2, 3, 5, 6上 的各階差商值。,解: 計(jì)算得如下表,14,知識(shí)研究,性質(zhì)1 函數(shù) f(x) 的 n 階差商 f x0, x1 , , xn 可由 f (x0), f (x1 ), , f (xn ) 的線性組合表示：,差商的性質(zhì),驗(yàn)證,同學(xué)自己驗(yàn)證,真漂亮,15,知識(shí)研究,這種求解差商的方法的優(yōu)點(diǎn)是直接使用

5、公式，缺點(diǎn)是計(jì)算量較大。,應(yīng)理解：右端分母中，xk-xk 項(xiàng)永遠(yuǎn)不出現(xiàn)。,或者表示成,以上公式可以利用如下的表達(dá)式直接驗(yàn)證,16,知識(shí)研究,性質(zhì)2 差商具有對(duì)稱性,即在k階差商 中任意交換兩個(gè)節(jié)點(diǎn) 和 的次序,其值不變。,即：,學(xué)生自己驗(yàn)證以上兩個(gè)公式,17,知識(shí)研究,性質(zhì)3 若fx, x0, x1 , , xk 是 x 的 m 次多項(xiàng)式, 則 fx, x0, x1 , xk , xk+1是 x 的 m-1 次多項(xiàng)式。,注意：右端分子為 m 次多項(xiàng)式, 且由差商的對(duì)稱性可知，當(dāng) x = xk+1 時(shí), 分子為0 ,故分子含有因子 xk+1 x，與分母相消后，右端為m-1 次多項(xiàng)式。,證：由差商

6、定義,常數(shù),18,知識(shí)研究,性質(zhì)4 若 f(x)是n次多項(xiàng)式, 則fx, x0, x1 , , xn 恒為0。,證： f(x)是n次多項(xiàng)式，則fx, x0 是 n-1次多項(xiàng)式, f x, x0, x1 是 n-2 次多項(xiàng)式。,fx, x0, x1 , xn 0,依次遞推 ， f x, x0, x1 , , xn-1 是n-n次（零次）多項(xiàng)式，即常數(shù)c.,所以,19,知識(shí)研究,性質(zhì)5 若f(x)存在k階導(dǎo)數(shù)，則f(x)的k階差商 與其k階導(dǎo)數(shù)之間有下列關(guān)系：,證明：這個(gè)性質(zhì)可直接用羅爾(Rolle)定理證明。,Home,20,知識(shí)研究,牛頓插值多項(xiàng)式的系數(shù) 與誤差余項(xiàng)的導(dǎo)出,21,知識(shí)研究,牛頓

7、插值多項(xiàng)式的系數(shù)與誤差余項(xiàng)的導(dǎo)出,的系數(shù)ak (k=0,n)可根據(jù)以下插值條件推出。,22,知識(shí)研究,一般，用數(shù)學(xué)歸納法可證明,從上述各個(gè)公式中可以解出：,將a1 =fx0 , x1 代入下一個(gè)等式，得,23,知識(shí)研究,n次牛頓(Newton)插值公式的表達(dá)式：,這里沒(méi)有假設(shè)f(x)可導(dǎo),24,知識(shí)研究,牛頓插值多項(xiàng)式余項(xiàng)公式的推導(dǎo)：,設(shè)x為區(qū)間a, b上的一點(diǎn)，可得：,從前往后，將后式逐漸帶入到前式,即得：,根據(jù)1階差 商的定義,根據(jù)2階差 商的定義,25,知識(shí)研究,推導(dǎo)完畢(下一頁(yè)P(yáng)PT有3個(gè)節(jié)點(diǎn)情況的詳細(xì)推導(dǎo))。,26,知識(shí)研究,設(shè)x為區(qū)間a, b上的一點(diǎn)，可得：,將(2)式代入(1)式

8、，得：,牛頓插值多項(xiàng)式余項(xiàng)公式的仔細(xì)推導(dǎo)（以僅有3個(gè)插值節(jié)點(diǎn) 的2次插值為例）：,(1),(2),(3),(4),將(3)式代入(4)式，得：,整理，得,整理，得：,N2 (x),R2 (x),27,知識(shí)研究,解釋?zhuān)?由插值多項(xiàng)式的存在唯一性定理知，滿足同一組插值條件的拉格朗日插值多項(xiàng)式P(x)與牛頓插值多項(xiàng)式Nn(x)實(shí)際上是同一個(gè)多項(xiàng)式,的形式以后，所得的表達(dá)式是相同的。,即將P(x)和Nn(x)所得的多項(xiàng)式表達(dá)式，化為,28,知識(shí)研究,若f(n+1)(x)不存在，則只有使用(*)式來(lái)表達(dá)誤差。,Newton插值多項(xiàng)式的誤差(不要求f(x)光滑),(*),29,知識(shí)研究,評(píng)論：牛頓插值公式

9、計(jì)算方便，增加一個(gè)插值點(diǎn)，只要多計(jì)算一項(xiàng)，而Nn(x)的各項(xiàng)系數(shù)恰好是各階差商值，很有規(guī)律。,Home,若f(n+1)(x) 存在,30,知識(shí)研究,利用牛頓插值多項(xiàng)式近似求解的例子,31,知識(shí)研究,32,知識(shí)研究,N2(x)=1+1/3(x-1)-1/60(x-1)(x-4) =-1/60 x2 +5/12x+3/5,N2(7)=2.7,例 2.12 已知 x = 1, 4, 9 的平方根值，求,解1：考慮f(x)=x，利用差商表求差商,33,知識(shí)研究,解2：利用公式求差商,用這種方法解得得系數(shù)與方法1的相同。,34,知識(shí)研究,解3：利用拉格朗日方法求插值對(duì)多項(xiàng)式,求2次插值對(duì)多項(xiàng)式,=-1/

10、60 x2 + 5/12x + 3/5,35,知識(shí)研究,4.4 .1 差商及其性質(zhì),例2.13 已知 x=0, 2, 3, 5 對(duì)應(yīng)的函數(shù)值為 y=1, 3, 2, 5 , 作三次Newton插值多項(xiàng)式。,36,知識(shí)研究,例2.14 求 的值，并估計(jì)其誤差,解：令,，取 x0=4, x1=9, x2=6.25, 差商表,37,知識(shí)研究,在區(qū)間 4 , 9 上，,由,計(jì)算器計(jì)算結(jié)果：,N2(7)=2.7，差一些,例2.12中，計(jì)算結(jié)果為：,代入x=7,例2.14中，計(jì)算結(jié)果為：,N2(7)=2.64848，好一些,38,知識(shí)研究,4.4 .1 差商及其性質(zhì),例2.15 已知 f(x) = x7+

11、 x4+ 3x+ 1 求 f 20, 21, 27 及 f 20, 21, 27, 28 ,分析：本題 f(x)是一個(gè)多項(xiàng)式, 故應(yīng)利用差商的性質(zhì),解: 由差商與導(dǎo)數(shù)之間的關(guān)系,39,知識(shí)研究,例2.16 給出f(x)的函數(shù)表如下，求4次Newton插 值多項(xiàng)式，并且由此計(jì)算f(0.596)的值,并 且估計(jì)誤差 R4(0.596).,40,知識(shí)研究,解：首先計(jì)算出差商表如下：,41,知識(shí)研究,經(jīng)計(jì)算得 N4(0.596) = 0.63192,現(xiàn)在試圖進(jìn)行誤差估計(jì)： R4 (x) =|fx, x0, x1, x2, x3, x4 5(x)|,因?yàn)?x = 0.596，所以要進(jìn)行以上的差商運(yùn)算，需要知道f(0.596)的值，但是我們現(xiàn)在不知道f(0.596)的值。,怎么辦？,可以利用 f(0.596)N4(0.596) = 0.63192 來(lái)計(jì)算差商，見(jiàn)下頁(yè)。,42,知識(shí)研究,R4 (x