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

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

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

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

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

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

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

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

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

9、計算方便，增加一個插值點，只要多計算一項，而Nn(x)的各項系數(shù)恰好是各階差商值，很有規(guī)律。,Home,若f(n+1)(x) 存在,30,知識研究,利用牛頓插值多項式近似求解的例子,31,知識研究,32,知識研究,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,知識研究,解2：利用公式求差商,用這種方法解得得系數(shù)與方法1的相同。,34,知識研究,解3：利用拉格朗日方法求插值對多項式,求2次插值對多項式,=-1/

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

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