數(shù)值分析第二章ppt課件

1、上一頁上一頁下一頁下一頁第二章第二章 函數(shù)基本逼近一）函數(shù)基本逼近一） 插值逼近插值逼近 上一頁上一頁下一頁下一頁1 1 引引 言言 函數(shù)逼近函數(shù)逼近: : 數(shù)學中的基本問題數(shù)學中的基本問題, , 最活躍的研究領域之一最活躍的研究領域之一 數(shù)值計算中函數(shù)表示的重要方法數(shù)值計算中函數(shù)表示的重要方法 討論如何用討論如何用 簡單函數(shù)近似代替復雜函數(shù)簡單函數(shù)近似代替復雜函數(shù) 簡單函數(shù)曲線擬合離散數(shù)據(jù)簡單函數(shù)曲線擬合離散數(shù)據(jù) 的方法、理論及其實現(xiàn)。的方法、理論及其實現(xiàn)。上一頁上一頁下一頁下一頁討論如何用簡單的函數(shù)討論如何用簡單的函數(shù)( )x ( )f x一個復雜的函數(shù)一個復雜的函數(shù)近似地代替近似地代替的

2、方法、理論及其實現(xiàn)的方法、理論及其實現(xiàn). . 近似代替又叫做逼近近似代替又叫做逼近 . .( )x ( )f x被逼近的函數(shù)被逼近的函數(shù) 或被近似的函數(shù)或被近似的函數(shù) 逼近的函數(shù)逼近的函數(shù) 或近似的函數(shù)或近似的函數(shù) 即即上一頁上一頁下一頁下一頁函數(shù)逼近是數(shù)值分析的許多分支的理論基礎函數(shù)逼近是數(shù)值分析的許多分支的理論基礎. . 例如例如: : 數(shù)值積分數(shù)值積分; ; 數(shù)值微分數(shù)值微分; ; 微分方程數(shù)值解微分方程數(shù)值解; ;曲線曲面擬合曲線曲面擬合; ;函數(shù)值近似計算函數(shù)值近似計算; ;等等等等上一頁上一頁下一頁下一頁從逼近論的觀點，通常有兩種意義下的逼近：從逼近論的觀點，通常有兩種意義下的逼近

3、：局部逼近局部逼近整體逼近整體逼近1 1、局部逼近、局部逼近所謂局部逼近就是求函數(shù)所謂局部逼近就是求函數(shù)( )f x在某點附近的近似在某點附近的近似 最常用的逼近方法：最常用的逼近方法： Taylor逼近方法逼近方法 理論依據(jù)：理論依據(jù)： Taylor定理定理 上一頁上一頁下一頁下一頁( )f x0 x00(,)Ixx 1n ,xI 定理定理1.11.1設設n n為一非負整數(shù)，為一非負整數(shù)，在點在點某一鄰域某一鄰域有有階連續(xù)導數(shù)，階連續(xù)導數(shù)，有有 則對則對的的( )( )( )nnf xpxR x( )npx( )nR x這里，這里，n n次次TaylorTaylor逼近多項式逼近多項式和誤差

4、余項和誤差余項分別為分別為( )00000()()( )()()() ,1!nnnf xfxp xf xxxxxn 0(1)(1)101( )( )()( )(),!(1)!nxnnnnxfR xxtft dtxxnn (1.1) (1.2) (1.3) 上一頁上一頁下一頁下一頁注意：注意：( )npx1 1、TaylorTaylor逼近多項式逼近多項式滿足以下逼近要求滿足以下逼近要求 00()(), 0,1, .kknkkd p xd f xkndxdx ( )f x0 x2、Taylor逼近是一種局部逼近逼近是一種局部逼近在一點在一點處的信息處的信息. .僅利用了被逼近的函數(shù)僅利用了被逼近

5、的函數(shù)下面舉例說明下面舉例說明TaylorTaylor多項式的逼近效果多項式的逼近效果. . 上一頁上一頁下一頁下一頁解解 由由(1.2)(1.2)式和式和(1.3)(1.3)式易求得式易求得 ( )00000()()( )()()() ,1!nnnf xfxp xf xxxxxn 0(1)(1)101( )( )()( )(),!(1)!nxnnnnxfR xxtft dtxxnn (1.2) (1.3) 1( )1,p xx 22( )1,2xp xx12111( )( ),2xR xep xx e 23221( )( ),6xR xep xx e 直觀理解可以參見下圖。直觀理解可以參見下

6、圖。 上一頁上一頁下一頁下一頁(a)xe的一次和二次的一次和二次TaylorTaylor逼近函數(shù)逼近函數(shù) (b)xe的一次和二次的一次和二次TaylorTaylor逼近誤差逼近誤差 (a)(b)上一頁上一頁下一頁下一頁因而，因而，TaylorTaylor逼近適合作函數(shù)的局部逼近逼近適合作函數(shù)的局部逼近. .由此可見：誤差不是均勻分布的由此可見：誤差不是均勻分布的. . 當當x x越偏離越偏離x0 x0誤差就越大誤差就越大即當即當x x越接近越接近x0 x0誤差就越??；誤差就越??；我們將主要討論整體逼近問題我們將主要討論整體逼近問題: :即對定義域上的所有點即對定義域上的所有點. .近似函數(shù)對被

7、逼近函數(shù)的逼近近似函數(shù)對被逼近函數(shù)的逼近函數(shù)曲線對樣本數(shù)據(jù)的擬合函數(shù)曲線對樣本數(shù)據(jù)的擬合考慮考慮: :上一頁上一頁下一頁下一頁(0.5, 0)(1, 0.25) (1.5, 1).ABC、和和例例2 2 求區(qū)間求區(qū)間0,1.50,1.5上的二次拋物曲線上的二次拋物曲線, ,要求要求該曲線過樣本點該曲線過樣本點 解解 設所求拋物線的方程為設所求拋物線的方程為2,yabxcx 利用待定系數(shù)法，可得利用待定系數(shù)法，可得21.4yxx 此例將引出所謂的此例將引出所謂的 Lagrange Lagrange 型多項式插值問題型多項式插值問題, , 這時給定這時給定的樣本數(shù)據(jù)僅包含函數(shù)值的樣本數(shù)據(jù)僅包含函數(shù)

8、值. . 上一頁上一頁下一頁下一頁例例3 3 求區(qū)間求區(qū)間0,10,1上的三次曲線，要求該函數(shù)曲線過上的三次曲線，要求該函數(shù)曲線過且其一階導函數(shù)曲線過樣本點且其一階導函數(shù)曲線過樣本點(0,0)(1,1)和和( (即函數(shù)曲線在即函數(shù)曲線在0,10,1點處的斜率分別為點處的斜率分別為0 0和和1).1).(0,1)A(1,0),B和和樣本點樣本點23,yabxcxdx 23143.yxx 解解 設所求的三次曲線為設所求的三次曲線為類似于例類似于例2 2的計算，可得的計算，可得上一頁上一頁下一頁下一頁上例將引出所謂的上例將引出所謂的HermiteHermite型多項式插值問題型多項式插值問題此時樣本

9、數(shù)據(jù)包含：此時樣本數(shù)據(jù)包含：1 1、函數(shù)值、函數(shù)值2 2、一階導數(shù)值、一階導數(shù)值. . 更廣泛的還有所謂的更廣泛的還有所謂的BirkhoffBirkhoff插值問題插值問題. . 注意：注意：上一頁上一頁下一頁下一頁1,0,1 121( 2,0)( 1, )(0, )(1, )636ABCD、(2,0)E 2,2 例例4 4 求區(qū)間求區(qū)間上的二階連續(xù)可微的分段三次多項式上的二階連續(xù)可微的分段三次多項式），要求該曲線過點），要求該曲線過點和和，且在，且在A、E兩點的導數(shù)為兩點的導數(shù)為0. 曲線其內部段點分別為曲線其內部段點分別為解解 注意所求函數(shù)為偶函數(shù)，注意所求函數(shù)為偶函數(shù)，利用待定系數(shù)法，利

10、用待定系數(shù)法，0,2x 上的表示式為上的表示式為 可得該函數(shù)在可得該函數(shù)在y 3212, 0123xxx 32142, 1263xxxx上一頁上一頁下一頁下一頁其圖形如下圖所示其圖形如下圖所示. .此例將引出所謂的樣條插值問題：此例將引出所謂的樣條插值問題： 即求滿足一定的即求滿足一定的整體光滑或連接條件的分段插值多項式整體光滑或連接條件的分段插值多項式. . 上一頁上一頁下一頁下一頁 1,1 ( ),f x2|arctan1sin, 1,0)(0,1,( )40, 0,xxxxf xxx 1( ),p x111max|( )( )|xf xp x 1211( ( )( ) f xp xdx

11、例例5 5 如下圖，如下圖， 上的函數(shù)上的函數(shù)達到最小達到最小. . 給定區(qū)間給定區(qū)間其表達式為其表達式為求一直線求一直線使誤差使誤差或或上一頁上一頁下一頁下一頁上例將引出所謂的最佳一致和最佳平方逼近問題。上例將引出所謂的最佳一致和最佳平方逼近問題。 x01234567y27.0 26.8 26.5 26.3 26.1 25.7 25.3 24.8例例6 6 給定離散數(shù)據(jù)下表），給定離散數(shù)據(jù)下表），數(shù)據(jù)，使誤差平方和最小。數(shù)據(jù)，使誤差平方和最小。125.273036. 0 xy此例將引出所謂的此例將引出所謂的最小二乘逼近問題。最小二乘逼近問題。 用一直線擬合這組用一直線擬合這組上一頁上一頁下一

12、頁下一頁(0,0.1)( )f xsin3sin4( )0.12sin2,23xxf xx 301sin,2kkabkx 例例7 7 如下圖，如下圖，滿足滿足(1)(1)最佳平方逼近于最佳平方逼近于f(x);f(x);或或(2)(2)擬合圖中實心點所示擬合圖中實心點所示對稱的周期為對稱的周期為22的曲線的曲線( (或樣本點或樣本點) )求三角多項式求三角多項式給定關于給定關于的所有樣本點，使誤差平方和最小的所有樣本點，使誤差平方和最小. . 上一頁上一頁下一頁下一頁上例將引出所謂的周期函數(shù)的最佳平方逼近問題及上例將引出所謂的周期函數(shù)的最佳平方逼近問題及快速快速FourierFourier變換。

13、變換。 逼近問題主要由以下三個要素構成：逼近問題主要由以下三個要素構成：(1) (1) 被逼近函數(shù)或樣本數(shù)據(jù)）被逼近函數(shù)或樣本數(shù)據(jù)）(2) (2) 逼近函數(shù)空間逼近函數(shù)空間簡單函數(shù)：主要是指可以用四則運算進行計簡單函數(shù)：主要是指可以用四則運算進行計算的函數(shù)，通常為代數(shù)或三角多項式、算的函數(shù)，通常為代數(shù)或三角多項式、分段多項式和有理多項式函數(shù)分段多項式和有理多項式函數(shù). .簡單函數(shù)所屬的函數(shù)空間簡單函數(shù)所屬的函數(shù)空間上一頁上一頁下一頁下一頁 逼近問題主要由以下三個要素構成：逼近問題主要由以下三個要素構成：(1) (1) 被逼近函數(shù)或樣本數(shù)據(jù)）被逼近函數(shù)或樣本數(shù)據(jù)）(2) (2) 逼近函數(shù)空間逼近

14、函數(shù)空間簡單函數(shù)：主要是指可以用四則運算進行計簡單函數(shù)：主要是指可以用四則運算進行計算的函數(shù)，通常為代數(shù)或三角多項式、算的函數(shù)，通常為代數(shù)或三角多項式、分段多項式和有理多項式函數(shù)分段多項式和有理多項式函數(shù). .簡單函數(shù)所屬的函數(shù)空間簡單函數(shù)所屬的函數(shù)空間上一頁上一頁下一頁下一頁(3) (3) 逼近方式逼近方式插值逼近：要求逼近函數(shù)曲線通過樣本數(shù)據(jù)點插值逼近：要求逼近函數(shù)曲線通過樣本數(shù)據(jù)點( (有時還要求在樣本數(shù)據(jù)點處，等于給定的導數(shù)值有時還要求在樣本數(shù)據(jù)點處，等于給定的導數(shù)值) )本章將在插值逼近方式下，討論相應的逼近問題本章將在插值逼近方式下，討論相應的逼近問題. .上一頁上一頁下一頁下一頁

15、插值問題涉及的基本內容：插值問題涉及的基本內容：1.1.問題提法問題提法 2.2.問題的適定性問題的適定性( (解的存在、唯一性解的存在、唯一性) )3.3.解的構造解的構造 ( (或表示或表示 ) )及其相關算及其相關算法法 4.4.誤差分析誤差分析( (逼近度刻化逼近度刻化) )及穩(wěn)定性分析及穩(wěn)定性分析 首先首先, ,對逼近函數(shù)取為代數(shù)多項式，樣本數(shù)據(jù)對逼近函數(shù)取為代數(shù)多項式，樣本數(shù)據(jù)僅包含被逼近函數(shù)的函數(shù)值的情形，討論相應的僅包含被逼近函數(shù)的函數(shù)值的情形，討論相應的插值問題插值問題. . 上一頁上一頁下一頁下一頁2 Lagrange2 Lagrange插值插值 一、問題的提法一、問題的提

16、法 二、適定性和二、適定性和LagrangeLagrange插值公式插值公式 三、三、NewtonNewton插值公式插值公式 上一頁上一頁下一頁下一頁一、問題的提法一、問題的提法(),0,1, ,iif xyin ,),(baIxxf 1 n知：知： 或其或其 個樣本值個樣本值nxxx,10且且彼此互異。彼此互異。01nnaa xa x 記所有次數(shù)不超過記所有次數(shù)不超過n n的代數(shù)多項式的代數(shù)多項式.nP的全體為的全體為上一頁上一頁下一頁下一頁插值問題：插值問題： 求求,nnPp 滿足滿足(),0,1, .niipxyin 00,x y ,iix y ,nnxy( )f x( )npx01,

17、nxxx稱稱為被插函數(shù)，為被插函數(shù)，為為n n次多項式插值函數(shù)，次多項式插值函數(shù)，為插值節(jié)點，為插值節(jié)點，的的LagrangeLagrange插值問題。插值問題。 并稱并稱而上述問題被稱為而上述問題被稱為 01,nxxx關于節(jié)點關于節(jié)點上一頁上一頁下一頁下一頁二、適定性和二、適定性和LagrangeLagrange插值公式插值公式 定理定理 2.1 2.1 插值問題的解是存在且唯一的插值問題的解是存在且唯一的. . 證明：（構造性證明）證明：（構造性證明）（1 1存在性存在性 首先構造特殊插值多項式首先構造特殊插值多項式,)(niPxl , 1, 0)(,kikixlkiki ., 1 , 0

18、,nki 克羅內克爾克羅內克爾(Kronecker)(Kronecker)符號符號. .:,ki (2.1) 上一頁上一頁下一頁下一頁n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)=ij ；然后；然后令令 niiinyxlxP0)()(，則顯然有，則顯然有Pn(xj) = yj 。li(x)每個每個 li 有有 n 個根個根 x0 xi-1 xi+1 xn njj i jiixxCxl0)()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange 多項式多項式與與 有關，而與有關，

19、而與 無關無關節(jié)點節(jié)點f上一頁上一頁下一頁下一頁(2) (2) 唯一性唯一性設設n n次多項式次多項式( )( )nnL xQx和和()()()0,1,2,niiniL xf xQ xin ( ):( )( ),nnnG xL xQxP記記()()()0,0,1,.ininiG xL xQ xin 且且均為插值問題的解均為插值問題的解, ,則有則有由高等代數(shù)基本知識知，由高等代數(shù)基本知識知，若一個若一個n n次代數(shù)多項式至少次代數(shù)多項式至少存在存在n+1n+1個根，則它一定恒為零個根，則它一定恒為零. . ( )0,( )( ).nnG xL xQx故故即即唯一性得證唯一性得證. . 上一頁上

20、一頁下一頁下一頁稱為稱為f(x)f(x)的的n n次多項式插值的次多項式插值的 Lagrange Lagrange 公式公式也稱為也稱為Lagrange Lagrange 插值多項式插值多項式. . 0( )( )nni iiL xy l x 稱為稱為n n次多項式插值問題的基函數(shù)次多項式插值問題的基函數(shù)(Lagrange (Lagrange 因子因子) )()()()(ininixxxxxl 其中其中0( )().nnjjxxx 上一頁上一頁下一頁下一頁例例 當當n=1n=1時，線性插值公式時，線性插值公式11001()( )()xxL xyxx 0110()()xxyxx 上一頁上一頁下一

21、頁下一頁當當n=2n=2時，拋物插值公式時，拋物插值公式12200102()()( )()()xxxxL xyxxxx 0211012()()()()xxxxyxxxx0122021()()()()xxxxyxxxx 上一頁上一頁下一頁下一頁 插值余項插值余項 設節(jié)點設節(jié)點)1( nf在在(a , b)內存在內存在, 考察截斷誤差考察截斷誤差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 滿足條件滿足條件 ,Rolles Theorem: 假設假設 充分光滑，充分光滑， ，那么，那么存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推廣

22、：假推廣：假設設0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 個根個根n+1 niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考考察察 niixtxKtRnt0)()()()( (t)有有 n+2 個不同的根個不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(nxKRxnn 注意這里是對注意這里是對 t 求導求導 !)1)()()()1()1(nxKLfxnnxn

23、 !)1()()()1( nfxKxn niixnnxxnfxR0)1()(! ) 1()()( 上一頁上一頁下一頁下一頁niyxPiin,., 0,)( 求求 n 次多項式次多項式 使得使得nnnxaxaaxP 10)(條件：無重合節(jié)點，即條件：無重合節(jié)點，即jixx ji 首先找到首先找到li(x)，i = 0, , n 使得使得 li(xj)=ij ；然后；然后令令 niiinyxlxP0)()(，則顯然有，則顯然有Pn(xj) = yj 。定理定理 (唯一性唯一性) 滿足滿足 的的 n 階插值多階插值多項式是唯一存在的。項式是唯一存在的。niyxPii,., 0,)( 上一頁上一頁下一

24、頁下一頁li(x)每個每個 li 有有 n 個根個根 x0 xi-1 xi+1 xn njj i jiixxCxl0)()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange 多項式多項式與與 有關，而與有關，而與 無關無關節(jié)點節(jié)點f上一頁上一頁下一頁下一頁000010( )()().()()( )( )()()()ninnniinnnjjjjijijiijxxxxxxxxxxLxyyxxxxxxx 若若上上式式可可改改成成( )jlx上一頁上一頁下一頁下一頁設節(jié)點設節(jié)點)1( nf在在(a , b)內存在內存

25、在, 其截斷誤差其截斷誤差)()()(xLxfxRnn , baCfn bxxxan 10，且，且 f 滿足條件滿足條件 , niixnnxxnfxR0)1()(! ) 1()()( 插值余項插值余項 /* Remainder */上一頁上一頁下一頁下一頁注：注： 通常不能確定通常不能確定 x , 而是估計而是估計 , x(a,b) 將將 作為誤差估計上限。作為誤差估計上限。1)1()( nnMxf niinxxnM01|)!1(當當 f(x) 為任一個次數(shù)為任一個次數(shù) n 的多項式的多項式時，時， , 可知可知 ，即插，即插值多項式對于次數(shù)值多項式對于次數(shù) n 的多項式是精的多項式是精確的。

26、確的。0)()1( xfn0)( xRn上一頁上一頁下一頁下一頁10010, 12111, 14412,125例例1 1 知知線性插值和拋物插值公式求線性插值和拋物插值公式求的近似值的近似值. . 試分別用試分別用01121,144,xx 0111,12,yy 解解 （1 1選取選取利用線性插值公式，利用線性插值公式，011010110()()( )()()xxxxL xyyxxxx 1144( )11121144xL x 可得可得 12112,144121x 于是于是 1125(125)L 11.17391. 上一頁上一頁下一頁下一頁012100,121,144,xxx 01210,11,1

27、2,yyy 解解 （2 2選取選取利用拋物插值公式，利用拋物插值公式，可得可得 0212201010210120122021()()()()( )()()()()()() ()()xxxxxxxxL xyyxxxxxxxxxxxxyxxxx 2(121)(144)( )10(100121) (100144)xxL x (100)(144)11(121100) (121144)xx (100)(121)12,(144100) (144121)xx 于是于是 2125(125)L 11.18107. 上一頁上一頁下一頁下一頁注意：注意：12511.1803398 則線性插值公式所得近似值有則線性插

28、值公式所得近似值有3 3位有效數(shù)字位有效數(shù)字 拋物插值公式所得近似值有拋物插值公式所得近似值有4 4位有效數(shù)字位有效數(shù)字 上一頁上一頁下一頁下一頁 例例 知知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 xxxL這里這里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(

29、,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的實際誤差的實際誤差 0.010103,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R內插內插 /* interpolation */ 的實際誤差的實際誤差 0.00596內插通常優(yōu)于外推。選擇內插通常優(yōu)于外推。選擇要計算的要計算的 x 所在的區(qū)間的所在的區(qū)間的端點，插值效果較好。端點，插值效果較好。上一頁上一頁下一頁下一頁 n =

30、 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的實際誤差次插值的實際誤差 0.00061高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值上一頁上一頁下一頁下一頁計算機上算法實現(xiàn)計算機上算法實現(xiàn)在計算機上實現(xiàn)：在計算機上實現(xiàn)：001(1)(0,1,2,. )02(0,1,2,. )niiiniiipapppainsbsssbin （ ） 上一頁上一

31、頁下一頁下一頁Lagrange插值算法。輸出做對輸入插值點計算插值輸入vuylvvxxxulnjvuuLniyxjjnjiiijiiii,:4);2);/()(10,1,.,3)0;2);1);()2();,.,2 , 1 , 0(,:) 1 (o0o上一頁上一頁下一頁下一頁上一頁上一頁下一頁下一頁Lagrange插值公式的優(yōu)缺點：插值公式的優(yōu)缺點：優(yōu)點：公式的形式對稱，結構緊湊，優(yōu)點：公式的形式對稱，結構緊湊， 容易編寫計算程序，便于理論分析和許多容易編寫計算程序，便于理論分析和許多 數(shù)值計算公式的推導。數(shù)值計算公式的推導。缺點：沒有承襲性，缺點：沒有承襲性， 即當增加新的節(jié)點時，所有即當增

32、加新的節(jié)點時，所有LagrangeLagrange因子因子必須重新計算，這就會造成計算量的浪費。必須重新計算，這就會造成計算量的浪費。上一頁上一頁下一頁下一頁作業(yè)作業(yè):P56-57:P56-571 1題題(1), 2(1), 2題題,3,3題題上一頁上一頁下一頁下一頁三、三、 牛頓插值公式牛頓插值公式 Lagrange 插值雖然易算，但若要增加一個節(jié)點時，插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)全部基函數(shù) li(x) 都需重新算過。都需重新算過。將將 Ln(x) 改寫成改寫成.)()(102010 xxxxaxxaa).(10 nnxxxxa的形式，希望每加一個節(jié)點時，的形式，希望每加一

33、個節(jié)點時，只附加一項上去即可。只附加一項上去即可。? 差商差商),()()(,jijijijixxjixxxfxfxxf 1階差商階差商 )(,kixxxxfxxfxxxfkikjjikji 2階差商階差商上一頁上一頁下一頁下一頁一般地，一般地，nnnnnnxxxxxfxxxfxxxf 01112010, 稱為稱為f (x)f (x)在在x0 , x1 , , xnx0 , x1 , , xn點的點的 n n 階階差商。差商。上一頁上一頁下一頁下一頁重節(jié)點差商重節(jié)點差商 其定義式為其定義式為 100010,lim,xxf x xf x x 1010010()()lim().xxf xf xfx

34、xx 一般地，可定義一般地，可定義 0101, , , .nndf xxxx xf xxxxdx 上一頁上一頁下一頁下一頁010(),()nknknkf xf xxxx 此性質表明差商與節(jié)點的排列次序無關。此性質表明差商與節(jié)點的排列次序無關。 f x0 , x1 , x2 , ., xn=性質性質1 1 差商可以表示為函數(shù)值的線性組合，即差商可以表示為函數(shù)值的線性組合，即差商的性質差商的性質: : 性質性質2 (2 (差商的對稱性差商的對稱性) )f x1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn , x0 上一頁上一頁下一頁下一頁( )f x性質性質3 3

35、假設假設是一個是一個m m次代數(shù)多項式，次代數(shù)多項式， 那么那么1m 次代數(shù)多項式次代數(shù)多項式. . x0 x關于點關于點和任一已知和任一已知點點的一階差商是的一階差商是( )f x事實上，由差商的定義有事實上，由差商的定義有 000( )( ) ,f xf xf x xx x 上式右端的分子為上式右端的分子為m m次代數(shù)多項式次代數(shù)多項式, , 并且當并且當0 xx 時為零時為零, ,因此分子包含了因此分子包含了0 xx 因子剛好和分母約去因子剛好和分母約去, ,1m 次代數(shù)多項式次代數(shù)多項式. . 故右端為故右端為 上一頁上一頁下一頁下一頁 性質性質4 4 若若f(x)f(x)在在a,ba

36、,b上存在上存在n n階導數(shù)階導數(shù), , 且節(jié)點且節(jié)點x0, x0, x1 , xnx1 , xn a,b, a,b,則至少存在一點則至少存在一點a, b a, b 滿滿足下式足下式!)(,)(10nfxxxfnn 解解 f (8)(x)=-68 !, f 1,2, ,9=-6, f (9)(x)=0, f 1,2, ,10=0.例例1 f (x)=-6x8+7x5-10,1 f (x)=-6x8+7x5-10,求求f 1,2, ,9f 1,2, ,9及及f 1,2, ,10.f 1,2, ,10.上一頁上一頁下一頁下一頁 牛頓插值牛頓插值 / /* * Newtons Newtons Int

37、erpolation Interpolation * */ /).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN?上一頁上一頁下一頁下一頁010 ,.,.,0 ,.,nnnf x xxf xxnx xf x xx ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf （n+1） 上一頁上一頁下一頁下一頁 牛頓插值牛頓插值 ,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n+

38、11+ (x x0) 2+ + (x x0)(x xn1) n+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 上一頁上一頁下一頁下一頁57 注：注： 由唯一性可知由唯一性可知 Nn(x) Ln(x)， 只是算法不同，故只是算法不同，故其余項也相同，即其余項也相同，即)(!)1()()(,.,1)1(10 xnfxxxxfnxnnn),(,!)(,.,maxmin)(0 xxkfxxfkk 實際計算過程實際計算過程為為f (x

39、0)f (x1)f (x2)f (xn1)f (xn)f x0, x1f x1, x2 f xn1, xnf x0, x1 , x2 f xn2, xn1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn1, xn, xn+1 f x1, , xn+1 f x0, , xn+1上一頁上一頁下一頁下一頁差商表上一頁上一頁下一頁下一頁59上一頁上一頁下一頁下一頁60上一頁上一頁下一頁下一頁上一頁上一頁下一頁下一頁上一頁上一頁下一頁下一頁xk f(xk)一階均差一階均差 二階均差二階均差三階均差三階均差 四階均差四階均差0.400.550.650.800.900.4107

40、50.578150.696750.888111.026521.116001.186001.275731.384100.280000.358930.433480.197330.213000.03134例例2 已知已知f(x)的函數(shù)表的函數(shù)表, 求二次牛頓插值多項式求二次牛頓插值多項式, 并由并由此計算此計算f(0.596)的近似值。的近似值。 2( )0.41075 1.11600(0.40)N xx 解解 由上表可得過前三點的由上表可得過前三點的2 2次次NewtonNewton插值多項式為插值多項式為0.28000(0.40)(0.55)xx 上一頁上一頁下一頁下一頁632010. 0)59

41、6. 0()596. 0(2 Nf又又0123,0.19733f x x xx 可得過前四點的可得過前四點的3次次Newton插值多項式插值多項式32( )( )0.19733(0.40)(0.55)(0.65)NxNxxxx故故3(0.596)(0.596)0.6319145fN 故故2( )0.410751.11600(0.40)0.28000(0.40)(0.55)N xxxx 04,0.03134f xx 又又上一頁上一頁下一頁下一頁可得過前五點的可得過前五點的4次次Newton插值多項式插值多項式43( )( )0.03134(0.4)(0.55) (0.65)(0.80),N xN

42、xxxxx 于是于是4(0.596)(0.596)fN 0.63195. 當插值節(jié)點等距分布時，上述基于差商的當插值節(jié)點等距分布時，上述基于差商的NewtonNewton插值插值公式可以得到進一步簡化。公式可以得到進一步簡化。上一頁上一頁下一頁下一頁作業(yè)作業(yè):P57-58:P57-586 6題題, 7, 7題題上一頁上一頁下一頁下一頁 等距節(jié)點公式等距節(jié)點公式 向前差分向前差分 iiifff 1ikikikikffff1111)( 向后差分向后差分 111 ikikikfffi1iifff 中心差分中心差分 1122112211iiikkkiiiffffffdddd+-+-=-=-其中其中)(

43、221hiixff 當節(jié)點等距分布時當節(jié)點等距分布時:),.,0(0nihixxi 上一頁上一頁下一頁下一頁 差分的重要性質：差分的重要性質： 線性：例如線性：例如gbfaxgbxfa )()( 假設假設 f (x)是是 m 次多項式，那么次多項式，那么 是是 次多項式，而次多項式，而 )0()(mkxfk km )(0)(mkxfk 差分值可由函數(shù)值算出：差分值可由函數(shù)值算出： njjknjknfjnf0)1( njnjkjnknfjnf0) 1(!)1).(1(jjnnnjn 其中其中 函數(shù)值可由差分值算出：函數(shù)值可由差分值算出：kjnjknfjnf 0kkkhkfxxf!,.,00 kn

44、kknnnhkfxxxf!,.,1 kkkhff0)()( 由由 Rn 表達式表達式上一頁上一頁下一頁下一頁 牛頓公式牛頓公式).(,.,.)(,)()(1000100 nnnxxxxxxfxxxxfxfxN 牛頓向前插值公式牛頓向前插值公式 牛頓向后插值公式牛頓向后插值公式 將節(jié)點順序倒置：將節(jié)點順序倒置：).(,.,.)(,)()(101xxxxxxfxxxxfxfxNnnnnnnn 設設htxx 0，那，那么么)()()(000 xfkthtxNxNknknn ),(,).(1()!1()()(01)1(nnnnxxhntttnfxR 設設htxxn ，那，那么么)() 1()()(0n

45、knkknnnxfkthtxNxN 注：一般當注：一般當 x 靠近靠近 x0 時用牛頓向前插值公式，靠近時用牛頓向前插值公式，靠近 xn 時用牛頓向后插值公式。時用牛頓向后插值公式。上一頁上一頁下一頁下一頁例例3 3 設設 y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, 用三用三次插值多項式求次插值多項式求f(1.2) f(1.2) 及及f(2.8)f(2.8)的近似值的近似值. .解解 相應的函數(shù)值及差分表如下相應的函數(shù)值及差分表如下: :0.48146 0.74210 1.22356 1.14396 1.8

46、86063.10962 1.76341 2.90347 4.793437.90305 2.71828 4.481697.28906 12.1824920.08554四階差分四階差分三階差分三階差分二階差分二階差分一階差分一階差分函數(shù)值函數(shù)值上一頁上一頁下一頁下一頁函數(shù)值函數(shù)值一階差分一階差分二階差分二階差分三階差分三階差分四階差分四階差分2.71828 4.481697.28906 12.1824920.08554 1.76341 2.90347 4.793437.90305 1.14396 1.886063.10962 0.74210 1.223560.48146求求f(1.2)用用Newt

47、on前插公式前插公式, 且由且由 1.2=1+0.5t, 得得t=0.431.14396(1.2)(1.2)2.71828 1.76341 0.40.4 (0.4 1)2!0.742100.4 (0.4 1)(0.4 2)3!fN 3.3338632. 上一頁上一頁下一頁下一頁求求f(2.8)用用Newton后插公式后插公式,且由且由 2.8=3+0.5t, 得得 t=-0.43(2.8)(2.8)fN 15.7680872. 20.085547.90305 ( 0.4) 3.10962( 0.4)( 0.41)2! 1.22356( 0.4)( 0.41)( 0.42)3! 上一頁上一頁下一

48、頁下一頁 3 3 埃爾米特插值埃爾米特插值 不僅要求函數(shù)值重合，而且要求若干階導數(shù)也重合。不僅要求函數(shù)值重合，而且要求若干階導數(shù)也重合。即：要求插值函數(shù)即：要求插值函數(shù) (x) 滿足滿足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： N 個條件可以確定個條件可以確定 階多項式。階多項式。N 1要求在要求在1個節(jié)點個節(jié)點 x0 處直到處直到m0 階導數(shù)階導數(shù)都重合的插值多項式即為都重合的插值多項式即為Taylor多多項式項式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx 其余項為其余項為)1(00)

49、1(00)()!1()()()()(mmxxmfxxfxR 一般只考慮一般只考慮 f 與與f 的值。的值。上一頁上一頁下一頁下一頁 例：設例：設 x0 x1 x2, 知知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多求多項式項式 P(x) 滿足滿足 P(xi) = f (xi)，i = 0, 1, 2，且，且 P(x1) = f (x1), 并估計誤差。并估計誤差。模仿模仿 Lagrange 多項式的思想，設多項式的思想，設解：首先，解：首先，P 的階數(shù)的階數(shù) = 3213)()()()()(0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且，且 h0(

50、x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh 又又: h0(x0) = 1 C0 )()()()()(202102210 xxxxxxxxxh h2(x)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh 由余下條件由余下條件 h1(x1) = 1 和和 h1(x1) = 0 可解?？山?。與與h0(x) 完全類似。完全類似。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx h1又又: (x1) = 1 C1 可解?？山?。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x

51、1) = 1 h1 h1),()()()()()(221033xxxxxxxKxPxfxR !4)()()4(xfxK 與與 Lagrange 分析分析完全類似完全類似上一頁上一頁下一頁下一頁 一般地，知一般地，知 x0 , , xn 處有處有 y0 , , yn 和和 y0 , , yn ，求，求 H2n+1(x) 滿足滿足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：設解：設ni)()()(0iixhxhyixH2n+1 n0iyi其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hihi(x)有根有根 x0

52、 , , xi , , xn且都是且都是2重根重根 )()()(2xlBxAxhiiii ijjijixxxxxl)()()(由余下條件由余下條件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和 Bi )()(21 )(2xlxxxlxhiiiii (x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx hi又又: (xi) = 1 Ci = 1 hi)(x)(ili2(x)xx 設設,.210baCfbxxxann 那那么么20)22()()!22()()( niixnnxxnfxR 這樣的這樣的Hermi

53、te 插值唯插值唯一一上一頁上一頁下一頁下一頁 求求Hermite多項式的基本步驟：多項式的基本步驟： 寫出相應于條件的寫出相應于條件的hi(x)、 hi(x) 的組合形式；的組合形式； 對每一個對每一個hi(x)、 hi(x) 找出盡可能多的條件給出的根；找出盡可能多的條件給出的根； 根據(jù)多項式的總階數(shù)和根的個數(shù)寫出表達式；根據(jù)多項式的總階數(shù)和根的個數(shù)寫出表達式； 根據(jù)尚未利用的條件解出表達式中的待定系數(shù)；根據(jù)尚未利用的條件解出表達式中的待定系數(shù)； 最后完整寫出最后完整寫出H(x)。上一頁上一頁下一頁下一頁作業(yè)作業(yè):P57-58:P57-588 8題題, 10, 10題題上一頁上一頁下一頁下

54、一頁 4 分段低次插值分段低次插值 例：在例：在5, 5上考察上考察 的的Ln(x)。取。取211)(xxf),., 0(105niinxi -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端點附近抖動端點附近抖動越大，稱為越大，稱為Runge 現(xiàn)象現(xiàn)象Ln(x) f (x) 上一頁上一頁下一頁下一頁 )1(! 2! 1)(0200ttftffxp)1()1(!0 ntttnfnthxx 0 ,kfkf )1(! 2! 1)(0200ttftffxpNewtonNewton向前插值多項式：向前插值多項式：，那么：，那么：假設假

55、設不精確，成為不精確，成為上一頁上一頁下一頁下一頁這時這時 ikfikffkkk, ikikffRkkk, 0 knknknffR假設：假設：那么：那么：. . 得表：得表：)1()1(!0 ntttnfn上一頁上一頁下一頁下一頁 61520156 5 10105 46 4 3 3 2 kR 2 3 4 5 6 上一頁上一頁下一頁下一頁分段低次插值分段低次插值 算法數(shù)值穩(wěn)定性得不到保證算法數(shù)值穩(wěn)定性得不到保證舍入誤差嚴重影響高階差商或差分的準確性舍入誤差嚴重影響高階差商或差分的準確性最終嚴重影響到插值結果的精度最終嚴重影響到插值結果的精度. .上一頁上一頁下一頁下一頁 分段線性插值分段線性插值

56、 在每個區(qū)間在每個區(qū)間 上，用上，用1階多項式階多項式 (直線直線) 迫近迫近 f (x):,1 iixx11111)()( iiiiiiiiyxxxxyxxxxxPxf,for 1 iixxx記記 ，易證：當，易證：當 時，時，|max1iixxh 0h)()(1xfxPh一致一致| )(|max8| )()(|max 21xfhxPxfbxabxa上一頁上一頁下一頁下一頁( )f x假設假設在在a,ba,b上二階連續(xù)可微，上二階連續(xù)可微，ixe 時，時，則當則當有有111( )( )( )()(), ,2!iiiiiiff xp xxxxxxx 從而從而iiiiiixx xxx xf xp

57、 xxxxxfx11111|( )( )|max ()() max( ) ,2 上一頁上一頁下一頁下一頁iiiiiixx xxx xf xp xxxxxfx11111|( )( )|max ()() max( ) ,2 由于由于1211max |()()|, 4iiiiixx xhxxxx 11,iiihxx 于是，在整個區(qū)間于是，在整個區(qū)間a,ba,b上有上有 21|( )( )|max( ) ,8a x bhf xp xfx 其中其中1max.ii nhh 上一頁上一頁下一頁下一頁失去了原函數(shù)的光滑性。失去了原函數(shù)的光滑性。上一頁上一頁下一頁下一頁 分段分段Hermite插值插值 給定給定

58、nnnyyyyxx ,.,;,.,;,.,000在在 上利用兩點的上利用兩點的 y 及及 y ，可構造，可構造3次次Hermite函數(shù)函數(shù).,1 iixx, max1inihh 1iiixxh其誤差估計：其誤差估計：記記有：有：|,)(|max384| )()(|max)4(4xfhxHxfbxabxa上一頁上一頁下一頁下一頁( )f x假設假設在在a,ba,b上四階連續(xù)可微，上四階連續(xù)可微，ixe 時，時，則當則當有有(4)2211( )( )( )() () , (,),4!iiiiiiff xH xxxxxxx 從而在整個區(qū)間從而在整個區(qū)間a,ba,b上有上有 4(4)|( )( )|m

59、ax( ) ,384a x bhf xH xfx 其中其中1max.ii nhh 上一頁上一頁下一頁下一頁 5 樣條函數(shù)插值樣條函數(shù)插值 定義定義設設 。三次樣條函數(shù)。三次樣條函數(shù) , 且在每個且在每個 上為三次多項式上為三次多項式 /* cubic polynomial */。若它。若它同時還滿足同時還滿足 ，則稱為，則稱為 f 的三次樣條插值的三次樣條插值函數(shù)函數(shù) .bxxxan .10,)(2baCxS ,1 iixx),., 0(),()(nixfxSii 注：三次樣條與分段注：三次樣條與分段 Hermite 插值的根本區(qū)別在于插值的根本區(qū)別在于S(x)自自身光滑，不需要知道身光滑，不

60、需要知道 f 的導數(shù)值除了在的導數(shù)值除了在2個端點可能需個端點可能需要）；而要）；而Hermite插值依賴于插值依賴于f 在所有插值點的導數(shù)值。在所有插值點的導數(shù)值。f(x)H(x)S(x)上一頁上一頁下一頁下一頁 構造三次樣條插值函數(shù)的三彎矩法構造三次樣條插值函數(shù)的三彎矩法 在在 上，記上，記,1jjxx ,1 jjjxxh,for )()(1jjjxxxxSxS 對每個對每個j, 此為此為3次多項式次多項式那么那么 Sj”(x) 為為 次多項式，需次多項式，需 個點的值確定之。個點的值確定之。12設設 Sj”(xj1) = Mj1， Sj”(xj) = Mj 對于對于x xj1, xj 可