【文章內(nèi)容簡介】 .. , [ ? ? ? ? ? ? ? ? ? ? ? ? ? k k k k k k k k k k k x x x x x f x x x f x x x x x f x x x f x x f (k+1) 階 差 商 )()()()()()(4433221100xfxxfxxfxxfxxfxxfxkk四階差商三階差商二階差商一階差商差商的計算方法 (表格法 ): ],[ 10 xxf],[ 21 xxf],[ 32 xxf],[ 43 xxf],[ 210 xxxf],[ 321 xxxf],[ 432 xxxf],[ 3210 xxxxf],[ 4321 xxxxf],[ 410 xxxf ?規(guī)定函數(shù)值為 零階差商 差商表 差商具有如下性質(zhì) : 且的線性組合表示可由函數(shù)值階差商的,)(,),(),(],[)()1(10110kkkxfxfxfxxxxfkxf?? ?],[ 110 kk xxxxf ???? ?? ?????ki kiiiiiiixxxxxxxxxf0 110 )())(()()(?? Warning: my head is exploding… What is the point of this formula? 差商的值與 xi 的順序無關(guān)！ Newton插值公式及其余項 ],[)()()( 000 xxfxxxfxf ???],[)(],[],[ 101100 xxxfxxxxfxxf ???],. ..,[)(],. ..,[],. ..,[ 0010 nnnn xxxfxxxxfxxxf ????1 2 … … … … n+1 1 + (x ? x0) ? 2 + … … + ( x ? x0)…( x ? xn?1) ? n+1 . ..))(](,[)](,[)()( 102100100 ??????? xxxxxxxfxxxxfxfxf)) . .. (](,...,[ 100 ???? nn xxxxxxf))() .. . (](,. ..,[ 100 nnn xxxxxxxxxf ???? ?Nn(x) Rn(x) ai = f [ x0, …, xi ] Newton插值公式及其余項 ix0x1x2x3x[]ifx0()fx1()fx2()fx3()fx1[ , ]iif x x ?01[ , ]f x x12[ , ]f x x23[ , ]f x x12[ , , ]i i if x x x??0 1 2[ , , ]f x x x1 2 3[ , , ]f x x x1 2 3[ , , , ]i i i if x x x x? ? ?0 1 2 3[ , , , ]f x x x x0 0 1 0 0 1 2 1 00 1 1 1 0( ) ( ) ( ) [ , ] ( ) ( ) [ , , ]( ) ( ) ( ) [ , , , ]nnnP x f x x x f x x x x x x f x x xx x x x x x f x x x?? ? ? ? ? ?? ? ? ? ?Newton插值公式及其余項 例： 已知 x=1,4,9的平方根為 1,2,3，利用牛頓基本差商 公式求 的近似值。 ix149ix1231[ , ]iif x x ?21 0 33 33 341 .? ??32 0294 .? ??12[ , , ]i i if x x x??0 2 0 3 3 3 3 3 0 0 1 6 6 791.. .? ???7解： 從而得二階牛頓基本差商公式為 2 1 0 3 3 3 3 3 1 0 0 1 6 6 7 1 4( ) . ( ) . ( ) ( )P x x x x? ? ? ? ? ?2 7 2 6 9 9 9 2( ) . .P ?因此計算得 的近似值為 7二、代數(shù)插值多項式的存在 唯一性 上的代數(shù)插值多項式為在區(qū)間設(shè)函數(shù) ],[)( baxfy ?nnn xaxaxaaxP ????? ?2210)(且滿足 niyxP iin ,2,1,0)( ???(2) (3) 滿足線性方程組的系數(shù)即多項式 nn aaaaxP ,)( 210 ?00202022 yxaxaxaa nn ????? ?11212110 yxaxaxaa nn ????? ?nnnnnn yxaxaxaa ????? ?2210???????????(4) 上述方程組的系數(shù)行列式為 n+1階范德蒙行列式 nnnnnnxxxxxxxxxV????????212110200111? ? ??? ????10 1)(ninijij xxji xx ??0由 Cramer法則 ,線性方程組 (4)有唯一解 定理 1. nnn xaxaxaaxP ????? ?2210)(niyxP iin ,2,1,0)( ???),( jixx ji ??若插值節(jié)點 則滿足插值條件 的插值多項式 存在且唯一 . 注： 若不將多項式次數(shù)限制為 n ，則插值多項式 不唯一 。 例如 也是一個插值多項式，其中 可以是任意多項式。 ????? niin xxxpxLxP0)()()()()(xp性質(zhì) 3 P32 練習(xí) 7 4 0 1 7 0 1 83 1 [ 2 , 2 , , 2 ] [ 2 , 2 , , 2 ]f x x x f f? ? ? ?已 知 ， 求 及()fx分 析 ： 本 題 是 一 個 多 項 式 ， 可 利 用 差 商 的 性 質(zhì)解 ： 由 差 商 與 導(dǎo) 數(shù) 之 間 的 關(guān) 系( 7 )0 1 7 ( ) 7 ![ 2 , 2 , , 2 ] 17 7 !ff ?? ? ?！( 8 )0 1 8 ( ) 0[ 2 , 2 , , 2 ] 08 8 !ff ?? ? ?！167。 埃爾米特插值 /* Hermite Interpolation */ 不僅要求函數(shù)值重合，而且要求若干階 導(dǎo)數(shù) 也重合。 即：要求插值函數(shù) ? (x) 滿足 ? (xi) = f (xi), ?’ (xi) = f ’ (xi), …, ?(mi) (xi) = f (mi) (xi). 注： ? N 個條件可以確定 階多項式。 N ? 1 ?要求在 1個節(jié)點 x0 處直到 m0 階導(dǎo)數(shù)都重合的插值多項式即為 Taylor多項式 00 )(!)(...))(()()(00 0)(000mm xxm xfxxxfxfx ????????其余項為 )1(00)1(00 )()!1()()()()( ?? ?????mm xxmfxxfxR ???一般只考慮 f 與 f ’的值。 167。 3 Hermite Interpolation 例： 設(shè) 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 多項式的思想，設(shè) 解： 首先， P 的階數(shù) = 3 ? ? ? 2 1 3 ) ( ) ( ) ( ) ( ) ( ? 0 i i i x h x1 f ’ x h x f x P ? h0(x) 有根 x1, x2， 且 h0’(x1) = 0 ? x1 是重根。 ) ( ) ( ) ( 2 2 1 0 0 x x x x C x h ? ? ? 又 : h0(x0) = 1 ? C0 )()()()()(202102210xxxxxxxxxh?????h2(x) h1(x) 有根 x0, x2 ? ) )( )( ( ) ( 2 0 1 x x x x B Ax x h ? ? ? ? 由余下條件 h1(x1) = 1 和 h1’(x1) = 0 可解。 與 h0(x) 完全類似。 (x) ? h1 有根 x0, x1, x2 ? ? h1 ) )( )( ( ) ( 2 1 0 1 x x x x x x C x ? ? ? ? ? h1 又 : ’(x1) = 1 ? C1 可解。 其中 hi(xj) = ?ij , hi’(x1) = 0, (xi) = 0, ’(x1) = 1 ? h1 ? h1 ),())()(()()()( 221033 xxxxxxxKxPxfxR ?????? !4 )()( )4( xfxK ??與 Lagrange 分析完全類似 167。 3 Hermite Interpolation 一般地，已知 x0 , …, xn 處有 y0 , …, yn 和 y0’ , …, yn’ ，求 H2n+1(x) 滿足 H2n+1(xi) = yi ， H’2n+1(xi) = yi’。 解： 設(shè) ? ? ? n i ) ( ) ( ) ( ? 0 i i x h x h yi x H2n+1 ? ? n ? 0 i yi’ 其中 hi(xj) = ?ij , hi’(xj) = 0, (xj) = 0, ’(xj) = ?ij ? hi ? hi hi(x) 有根 x0 , …, xi , …, xn且都是 2重根 ? ? ) ( ) ( ) ( 2 x l B x A x h i i i i ? ? ?? ???ij jiji xxxxxl)()()(由余下條件 hi(xi) = 1 和 hi’(xi) = 0 可解 Ai 和 Bi ? )()])((21[)( 2 xlxxxlxh iiiii ???? (x) ? hi 有根 x0 , …, xn, 除了 xi 外都是 2重根 ? ? hi ) ( ) ( i i li2(x) x x C x ? ? ? hi 又 : ’(xi) = 1 ? Ci = 1 ? hi ) ( x ) ( i li2(x) x x ? ? 設(shè) ],[,. . . 210 baCfbxxxa nn ?????? 則 20)22()()!22( )()( ?????? ??? ??? niixnn xxnfxR ?這樣的 Hermite 插值唯一 167。 3 Hermite Interpolation Quiz: 給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是 h2(x)的圖像？ ? x 0 1 1 2 3 4 5 6 y x y 0 1 1 2 3 4 5 6 斜率 =1 ? ? 求 Hermite多項式的基本步驟： ? 寫出相應(yīng)于條件的 hi(x)、 hi(x) 的組合形式； ? ? 對每一個 hi(x)、 hi(x) 找出盡可能多的條件給出的根； ? ? 根據(jù)多項式的總階數(shù)和根的個數(shù)寫出表達式； ? 根據(jù)尚未利用的條件解出表達式中的待定系數(shù)； ? 最后完整寫出 H(x)。 167。 4 分段低次插值 /* piecewise polynomial approximation */ Remember what I have said? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since highdegree polynomials are oscillating. 例： 在 [?5, 5]上考察 的 Ln(x)。取 211)(xxf ?? ),. . .,0(105 niinx i ???? 5 4 3 2 1 0 1 2 3 4 5 0 1 2 n 越大， 端點附近抖動 越大，稱為 Runge 現(xiàn)象 Ln(x)