CH3+插值法與最小二乘法-34+Newton插值法

1、第三章 插值法與 最小二乘法2010年3月數(shù)值計(jì)算方法3.4 Newton 插值法1Lagrange 插值多項(xiàng)式的基函數(shù)：優(yōu)點(diǎn)：形式對(duì)稱，有很強(qiáng)的規(guī)律性，便于記憶。 缺點(diǎn)：(1) 重復(fù)計(jì)算多, 導(dǎo)致計(jì)算量大； (2) 插值基函數(shù) lj(x) 依賴于所有節(jié)點(diǎn)，當(dāng)增加插值節(jié)點(diǎn)時(shí)，原來(lái)已算出的所有 lj(x) 都需要重新計(jì)算，使計(jì)算量加大。 ？是否存在其它的插值法，可以解決上述問(wèn)題呢 Newton插值基函數(shù) 差商的定義和性質(zhì) 差商表示的Newton插值多項(xiàng)式 差分的定義和性質(zhì) 差分表示的Newton插值多項(xiàng)式3.4 Newton 插值法Newton (16241727) 由線性代數(shù)知識(shí)可知, 任何一

2、個(gè) n 次多項(xiàng)式都可表示成:這n+1 個(gè)多項(xiàng)式的線性組合.問(wèn)：是否可以將這 n+1個(gè)多項(xiàng)式作為插值基函數(shù)？ 已知函數(shù) f(x) 的插值節(jié)點(diǎn) xi 及相應(yīng)函數(shù)值 ,將上述線性無(wú)關(guān)的多項(xiàng)式取作Newton插值法的基函數(shù),即令：Newton插值基函數(shù)則相應(yīng)的插值多項(xiàng)式為:式中, 為待定參數(shù),它們可利用插值條件 來(lái)求,即令：可以求得：依此類推,可求得 .為標(biāo)記、推導(dǎo)、記憶方便,給出均差定義,可得參數(shù) 的一般表達(dá)式。這也太復(fù)雜了吧！為 關(guān)于節(jié)點(diǎn) 的一階均差(差商)4-1 均差(差商)1.均差的定義:設(shè)給定函數(shù) 在 個(gè)互異的節(jié)點(diǎn) 處的函數(shù)值為 ,稱為 關(guān)于節(jié)點(diǎn) 的二階均差(差商)缺倒數(shù)第二個(gè)節(jié)點(diǎn)缺最后一個(gè)

3、節(jié)點(diǎn)最后一個(gè)節(jié)點(diǎn)倒數(shù)第二個(gè)節(jié)點(diǎn)稱可見(jiàn)：一個(gè)高階差商可由兩個(gè)低一階的差商得到缺倒數(shù)第二個(gè)節(jié)點(diǎn)缺最后一個(gè)節(jié)點(diǎn)稱為 關(guān)于節(jié)點(diǎn) 的 k 階均差(差商)最后一個(gè)節(jié)點(diǎn)倒數(shù)第二個(gè)節(jié)點(diǎn)由此定義,顯然:用歸納法可證：將上述結(jié)果代入：2.差商的性質(zhì)性質(zhì)1：差商與函數(shù)值的關(guān)系 f(x) 關(guān)于 的 k 階差商是 f(x) 在這些點(diǎn)上函數(shù)值的線性組合,即例如:利用對(duì)稱性,可對(duì) f(x) 關(guān)于 的 k 階差商變形注：上式是計(jì)算中常用的差商公式，可建立差商表.缺第一個(gè)節(jié)點(diǎn)缺最后一個(gè)節(jié)點(diǎn)最后一個(gè)節(jié)點(diǎn)第一個(gè)節(jié)點(diǎn)性質(zhì)2：對(duì)稱性 差商對(duì)于定義它的節(jié)點(diǎn)而言是對(duì)稱的,也就是說(shuō)任意調(diào)換節(jié)點(diǎn)的次序,差商的值不變3. 差商的計(jì)算方法：差商表

4、規(guī)定函數(shù)值為零階差商補(bǔ)充兩個(gè)性質(zhì)證明：稍后證明。性質(zhì)3:差商與函數(shù)導(dǎo)數(shù)之間的關(guān)系 當(dāng) f(k)(x) 在包含節(jié)點(diǎn) x0, x1, , xk 的區(qū)間存在時(shí),在 x0, x1, , xk 之間必存在一點(diǎn),使得證:等號(hào)右端分子是 m 次多項(xiàng)式,且當(dāng) x = xk +1 時(shí),分子為0,故分子中必有因子 x xk +1 ,與分母相消后,右端為 m -1次多項(xiàng)式.性質(zhì)5: 若 f(x) 是次數(shù)不超過(guò) k 的代數(shù)多項(xiàng)式,則它的 k+1階差商為零. 證: f (x)是 k 次多項(xiàng)式,則 f x, x0 是 k-1次多項(xiàng)式, f x, x0, x1 是 k-2次多項(xiàng)式，依此類推, k 階差商 是0次多項(xiàng)式,即是

5、常數(shù),所以 性質(zhì)4: 若 是 x 的 m 次多項(xiàng)式, 則 是 x 的 m -1次多項(xiàng)式內(nèi)容回顧上次課中,給出Newton插值基函數(shù):并形式上給出Newton插值多項(xiàng)式:式中, 待定.通過(guò)引進(jìn)均差/差商的概念,可以將系數(shù)表示為：4-2 Newton插值公式及其余項(xiàng)公式為 f (x) 關(guān)于節(jié)點(diǎn) 的 n 次Newton插值多項(xiàng)式.1.定義: 稱- (1)由插值多項(xiàng)式的唯一性, Newton 插值公式的余項(xiàng)為:實(shí)用的余項(xiàng)估計(jì)式：- (2)Lagrange插值多項(xiàng)式導(dǎo)數(shù)型余項(xiàng)若將 視為一個(gè)節(jié)點(diǎn),則由一階均差定義2. Newton插值余項(xiàng)的另一種表示同理,由二階均差定義有有因此可得:Newton插值多項(xiàng)式

6、差商型余項(xiàng)- (3)因此，推廣得：4. Newton插值估計(jì)誤差的實(shí)用公式：3. 性質(zhì)3 的證明- (4)5. 分段Newton插值 用Newton插值法也要避免使用高次插值,當(dāng)采用分段插值時(shí),也應(yīng)選擇靠近插值點(diǎn)的節(jié)點(diǎn)作插值節(jié)點(diǎn),這可減小截?cái)嗾`差.同Lagrange插值一樣,計(jì)算前先確定插值點(diǎn) x 屬于哪一個(gè)子區(qū)間,然后根據(jù)插值多項(xiàng)式的次數(shù),選擇靠近 x 的節(jié)點(diǎn).例1.已知 f (x) 的函數(shù)表如下所示：用分段三次Newton插值多項(xiàng)式計(jì)算 f (0.596)的近似值,并估計(jì)誤差.解 并根據(jù)插值點(diǎn) 0. 596 在均差表中的位置,選擇插值節(jié)點(diǎn).首先構(gòu)造均差表,1.1161.1861.27573

7、1.384101.515330.400.550.650.800.901.050.410750.578150.696750.888111.026521.253820.280.358920.433480.524920.19730.213030.22860.031460.03114-4.92310-40.596如何選擇插值節(jié)點(diǎn)？插值多項(xiàng)式為：截?cái)嗾`差為：6. Newton向后插值公式變?yōu)橥?當(dāng) x 位于表末時(shí), 可采用Newton向后插值公式進(jìn)行計(jì)算. 此時(shí), 可將節(jié)點(diǎn)視為按 的順序排列, 即將- (1)-(5)Newton向后插值公式Newton向后插值余項(xiàng)公式由均差的對(duì)稱性,可知因此,公式(5

8、)和公式(1)中的各階均差可在同一均差表中找到.例2.利用例1中的均差表,用三次 Newton 插值多項(xiàng)式計(jì)算 f(0.955) 的近似值并估計(jì)誤差. 解根據(jù)插值點(diǎn) 0.955 在均差表中的位置，選擇插值節(jié)點(diǎn).1.1161.1861.275731.384101.515330.400.550.650.800.901.050.410750.578150.696750.888111.026521.253820.280.358920.433480.524920.19730.213030.22860.031460.03114-4.92310-40.955如何選擇插值節(jié)點(diǎn)？插值多項(xiàng)式為：截?cái)嗾`差為：4-3

9、 差分定義4.2 設(shè) f (x) 在等距節(jié)點(diǎn) 處的函數(shù)值為 稱為 f (x)在 xk 處的 二階向前差分為 f (x)在 xk 處的 二階向后差分為 f (x)在 xk 處的 一階向前差分為 f (x)在 xk 處的 一階向后差分等距節(jié)點(diǎn)插值是比較常見(jiàn)的情況,為簡(jiǎn)化計(jì)算,引進(jìn)差分的概念.依此類推:為 f (x)在 xk 處的 m 階向前差分為 f (x)在 xk 處的 m 階向后差分向前差分和向后差分具有如下關(guān)系由差分的定義和數(shù)學(xué)歸納法可以證明：性質(zhì)：一階差分:二階差分:m 階差分:差分的計(jì)算方法:差分表在等距節(jié)點(diǎn)的前提下,差商與差分有如下關(guān)系:差商與差分的關(guān)系依此類推：4-4 差分表示的 N

10、ewton 插值公式1. Newton向前(差分)插值公式及余項(xiàng)公式記插值點(diǎn)：如果節(jié)點(diǎn) 是等距的, 即-(7)由均差與向前差分的關(guān)系：-(6)以及式(7)、(6)代入差商表示的插值公式：-(8)Newton向前(差分)插值公式得差分表示的 Newton 插值公式化為：Newton 插值多項(xiàng)式的余項(xiàng)公式節(jié)點(diǎn)等距時(shí), 化為-(9)若由差分近似代替導(dǎo)數(shù),上式可化為：-(10)實(shí)用的估計(jì)式：2. Newton向后(差分)插值公式及余項(xiàng)公式則：Newton 向后插值基本公式為： 當(dāng) x 位于表末時(shí), 設(shè)：Newton向后（差分）插值公式：同時(shí)可得 Newton向后（差分）插值余項(xiàng)公式：導(dǎo)數(shù)形式余項(xiàng)公式：

11、差分形式余項(xiàng)公式：實(shí)用的估計(jì)式：例3:給定 f (x) = cos x 的函數(shù)表如下：用四次Newton插值多項(xiàng)式計(jì)算cos0.048及cos0.566的近似值，并估計(jì)誤差.k0123456xk0.00.10.20.30.40.50.6f(xk)1.00000.995000.980070.955340.921060.877580.82534先構(gòu)造差分表,解再根據(jù)插值點(diǎn)在表中的位置選擇插值節(jié)點(diǎn).0.00.10.20.30.40.50.61.00000.995000.980070.955340.921060.877580.82534-0.00500-0.01493-0.02473-0.03428-

12、0.04348-0.05224-0.00993-0.00980-0.00955-0.00920-0.008760.000130.000250.000350.000440.000120.000100.00009-0.00002-0.000010.000010.048分別需要幾個(gè)插值節(jié)點(diǎn)？如何選擇？0.566顯然, h = 0.1, 當(dāng) x = 0.048 時(shí), 用前向公式,當(dāng) x = 0.566 時(shí), 用后向公式,例4:反函數(shù)插值. 已知 的函數(shù)表如表所示, 求函數(shù) 在0,2之間的零點(diǎn)近似值. xi012yi8-7.5-18 當(dāng)函數(shù)f(x)的解析式未知, 而僅知其在某區(qū)間上的函數(shù)表時(shí), 如何求其在 a, b 上的零點(diǎn)呢？ 一般地, 可先求 f(x) 在a,b上的插值函數(shù) y(x), 然后求 y(x)的零點(diǎn), 把此零點(diǎn)作為 f(x) 的近似零點(diǎn). 特別地, 若 f(x)的反函數(shù)存在, 記為 x = g(y). 于是求 f(x) 的零點(diǎn)問(wèn)題就變成求函數(shù)值g(0) 的問(wèn)題了. 若用插值法構(gòu)造出 g(y), 從而可求得的零點(diǎn)的近似值. 稱上述方法為“反插值”. 注: 反插值的條件是函數(shù) y=f(x) 有反函數(shù), 即要求 y=f(x) 單調(diào).本題中, 因?yàn)?yi 是按嚴(yán)格單調(diào)下降排列, 所以可用反插值法求f(x) 零點(diǎn)的近似值. 具體做法是, 先把原