數(shù)值分析課件

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

2、x),g(x),,,由于代數(shù)多項式的結(jié)構(gòu)簡單，數(shù)值近似和理論分析都方便，實用中常取代數(shù)多項式作為插值函數(shù)，稱其為n次插值多項式/* n-degree Interpolating polynomial */ ，求Pn(x)的過程也叫做拉格朗日插值/* Lagrange Interpolation */ 。,,點(diǎn)斜式,2.1 拉格朗日插值 /* Lagrange Interpolation */,n = 1線性插值,可見

3、L1(x) 是過 ( x0 , y0 ) 和 ( x1, y1 ) 兩點(diǎn)的直線。,稱為拉氏基函數(shù) /* Lagrange Basis */，滿足條件 li(xj)=?ij /* Kronecker Delta */,,n = 2拋物線插值,已知 x0 , x1 , x2 ; y0 , y1 , y2 ，求L2(x)=a0+a1x + a2x2, 使得L2(xi)= yi , i=0,1,2.,用基函數(shù)表示,其中l(wèi)0(x)、

4、l1(x)、l2(x)為二次式，且滿足以下條件,,li(xj)=?ij,,,,,,,,,,,,n ? 1,每個 li 有 n 個零點(diǎn) x0 … [xi] … xn,,,,Lagrange Polynomial,與 有關(guān)，而與 無關(guān),節(jié)點(diǎn),f,,Quiz: 給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是 l2(x)的圖像？,?,,證明： 由插值條件可知，插值多項式Ln(x)

5、的系數(shù)ai滿足線性方程組,,,其系數(shù)行列式是n+1階范德蒙(Vandermonde)行列式,因為xi≠xj，于是V≠0，方程組的解存在且唯一,,? 插值余項 /* Remainder */,Rolle’s Theorem: 若 充分光滑， ，則存在 使得 。,推廣：若,,使得,,Rn(x) 至少有

6、 個根,n+1,?(t)有 n+2 個不同的根 x0 … xn x,,注意這里是對 t 求導(dǎo),,,,,,,例：已知,分別利用 sin x 的1次、2次 Lagrange 插值計算 sin 50? 并估計誤差。,解：,,n = 1,分別利用x0, x1 以及 x1, x2 計算,?利用,,而,,?sin 50? = 0.7660444…,外推 /* extrapolation */的實際誤差 ? ?0.01001,?利用,內(nèi)插/

7、* interpolation */ 的實際誤差 ? 0.00596,內(nèi)插通常優(yōu)于外推。選擇要計算的 x 所在的區(qū)間的端點(diǎn)，插值效果較好。,,n = 2,,?sin 50? = 0.7660444…,2次插值的實際誤差 ? 0.00061,高次插值通常優(yōu)于低次插值,但絕對不是次數(shù)越高就越好，嘿嘿……,,,?插值誤差的實用估計法,設(shè)Ln(x) 和Ln*(x)分別是以x0，x1,…,xn和x1, x2…,xn＋1為節(jié)點(diǎn)的插值多項式。則,,,

8、,,,Ln(x) 和Ln*(x)只相差一個節(jié)點(diǎn)，可以設(shè)想f(n+1)(ξ)≈ f(n+1) (ξ*),,,程序設(shè)計,,,,,,,,,,,,,,,,,,,,因此， 𝒇(𝒙)的零點(diǎn)為 𝒙 𝟏 =?𝟎.𝟗, 𝒙 𝟐 =𝟎.𝟗;,,,解：由二次插值,,例 已知二次式f(x)在x=0,

9、1,2的值分別為-0.81,0.19, 3.19, 求f(x)的零點(diǎn)、極值點(diǎn)、x=1處導(dǎo)數(shù)和積分 𝟎 𝟐 𝒇 𝒙 𝒅𝒙 .,極值點(diǎn) x=0;,𝒇 ′ 𝟏 =𝟐;,,𝟎 𝟐 𝒇 𝒙 𝒅𝒙≈x

10、783;.𝟎𝟒𝟔𝟔𝟔,例 設(shè) 𝒙 𝟎 , 𝒙 𝟏 ,?, 𝒙 𝒏 是互不相同的節(jié)點(diǎn)， 𝒍 𝒊 (𝒙)是拉格朗日插值基函數(shù)，求證：,,,證明(1)：設(shè)𝒇 𝒙 = 𝒙 &#

11、119948; , 𝒌=𝟎,𝟏,𝟐,?,𝒏, 求𝒇(𝒙)的𝒏次拉格朗日插值多項式，得到,,,,,,,例 設(shè) 𝒙 𝟎 , 𝒙 𝟏 ,?, 𝒙 𝒏 是互不相同的節(jié)點(diǎn)， 𝒍 𝒊 (w

12、961;)是拉格朗日插值基函數(shù)，求證：,,,,,,,,證明(2)：,,,,,,例 設(shè) 𝒙 𝟎 , 𝒙 𝟏 ,?, 𝒙 𝒏 是互不相同的節(jié)點(diǎn)， 𝒍 𝒊 (𝒙)是拉格朗日插值基函數(shù)，求證：,,,令x=0, 則有,,,,,,,另設(shè)𝒇 𝒙 = 𝒙 

13、9951;+𝟏 , 𝒇(𝒙)的𝒏次拉格朗日插值多項式為,,,(n+1)!,證明(3): 利用式(1), 令x=0, 則有,例 設(shè)𝒇 𝒂 =𝒇 𝒃 =𝟎, 在[a,b]上 𝒇 ′′ 𝒙 ≤ 𝑴 𝟐 ，求證：,,,,,,,,,0,

14、證明: 設(shè)節(jié)點(diǎn) 𝒙 𝟎 =𝒂, 𝒙 𝟏 =𝒃, 由插值理論有,因為|(x-a)(x-b)|有極大值(b-a)2/4,　并且 𝒇 ′′ 𝒙 ≤ 𝑴 𝟐 ，因此有,,2.2 牛頓插值 /* Newton’s Interpolation */,? 差商(亦稱均差) /* d

15、ivided difference */,,1階差商 /* the 1st divided difference of f w.r.t. xi and xj */,,2階差商,,(k+1)階差商：,差商的值與 xi 的順序無關(guān)！,,? 牛頓插值 /* Newton’s Interpolation */,,… … … …,,,Nn(x),,Rn(x),ai =,f [ x0, …, xi ],,,← … …,,=Nn(x)+Rn(

16、x),?,Nn(x) ＝ Ln(x),注：? 由唯一性可知 Nn(x) ? Ln(x)， 只是算法不同，故其余項也相同，即,,? 實際計算過程為,f (x0)f (x1)f (x2)…f (xn?1)f (xn),f [x0, x1]f [x1, x2]… …… …f [xn?1, xn],f [x0, x1 , x2]… …… …f [xn?2, xn?1, xn],f [x0, …, xn],f (xn+1)

17、 f [x0, …, xn+1],x0x1x2…xn?1xn,xn+1,,,?sin 50? = 0.7660444…,1/21/√2√3/2…,xi f (xi) f [xi, xj]

18、 f [xi, xj , xk],π/6π/ 4π/ 3…,解一：取 　構(gòu)造差商表,,,解二：取 　構(gòu)造差商表,,,,,,,,,注：構(gòu)造差商表時，插值節(jié)點(diǎn)要以距計算點(diǎn)ｘ由近到遠(yuǎn)的次序排列。,,2.3 埃爾米特插值 /* Hermite Interpolation */帶導(dǎo)數(shù)的

19、插值,不僅要求函數(shù)值重合，而且要求若干階導(dǎo)數(shù)也重合。即：要求插值函數(shù) ? (x) 滿足? (xi) = f (xi), ?’ (xi) = f ’ (xi),…, ?(m) (xi) = f (m) (xi).,注：? N 個條件可以確定 階多項式。,N ? 1,?一般只考慮 f 與f ’的值。,,其中基函數(shù)α0(x),α1(x),β0(x),β1(x)都是三次多項式，并滿足,α0(x)=,(x-1)2,由條件α

20、0(0) = 1 和α0’(0) = 0 可解A和B ?,同理,,解：假設(shè)x0=0, x1=1,且,,例：求三次多項式H3(x)，使?jié)M足插值條件H3(x0)=y0 ,H3’ (x0)=y0’, H3(x1)=y1 ,H3’ (x1)=y1’, 并估計誤差。,? 基函數(shù)法,(Ax+B),,,,,β0 (x)=,x(x-1)2 C,由條件β'0(0) = 1 可解C ?,,,,,例：試用下表建立不超過3次的插值多項式。,? 推廣牛

21、頓插值法,解：構(gòu)造差商表,,C=1,C,,2.4 分段低次插值 /* piecewise polynomial approximation */,例：在[?5, 5]上考察 的Ln(x)。取,n 越大，端點(diǎn)附近抖動越大，稱為Runge 現(xiàn)象,,? 分段線性插值 /* piecewise linear interpolation */,,,? 分段拋物線插值 /* piecewise pa

22、rabolic interpolation */,在每個區(qū)間 上，用2次式 逼近 f (x):,? 分段Hermite插值 /* Hermite piecewise polynomials */,,,為了保證xi-1, xi, xi+1, 是距x最近的三個節(jié)點(diǎn),xi-1, xi, xi+1并不一定是距x最近的三個節(jié)點(diǎn),,2.5 三次樣條 /* Cubic Spline */,定義,設(shè)

23、 。三次樣條函數(shù) , 且在每個 上為三次多項式 /* cubic polynomial */。若它同時還滿足 ，則稱為 f 的三次樣條插值函數(shù) /* cubic spline interpolant */.,注：三次樣條與分段 Hermite 插值

24、的根本區(qū)別在于S(x)自身光滑，不需要知道 f 的導(dǎo)數(shù)值（除了在2個端點(diǎn)可能需要）；而Hermite插值依賴于f 在所有插值點(diǎn)的導(dǎo)數(shù)值。,,,f(x),H(x),,S(x),,三彎矩法 /* method of bending moment */,,? 構(gòu)造三次樣條插值函數(shù),,S(x)是分段三次多項式，它在第i個子區(qū)間[xi-1, xi]上的表達(dá)式用Si(x)表示。假設(shè)S’i(xi-1)=mi-1, S’i(xi)=mi, hi= x

25、i- xi-1 ,則,,,,S(x)滿足整個區(qū)間內(nèi)C1連續(xù)嗎？,如何選取mi的值，使S(x)二階導(dǎo)數(shù)也連續(xù)？,,,,,,,兩邊乘以 ，并令,,,,1. 第一類邊界條件：,2. 第二類邊界條件：,3. 第三類邊界條件(當(dāng)y=f(x)是周期函數(shù))：,,,,?邊界條件/* boundary conditions */,,,S(x)= Si(x) ，x∈[xi-1, xi], i=1,2,…,n,,三對角　方程組