【正文】 ??07:49:44 Numerical Analysis 39 梯形遞推算法流程圖 ?算法實現(xiàn) ??? ???10 212 )(22nk knn xfhTT輸出 T2 h ← ba T1 ← h/2*(f(a)+f(b)) xb Y T2← T1/2+h/2*s h ← h/2 T1 ← T2 s ← s+f(x) x ← x+h s ← 0 x ←a +h/2 N N Y |T2T1| ?輸入 a, b, ?← ← h/2 T ← T1 T1 ← T2 |T2T ?dxx x?10s i n求07:49:44 Numerical Analysis 40 舉例 解： 例 5(P110)： 用梯形法的遞推公式計算定積分 , 要求計算精度滿足 10s i n ( ) dx xx?? ?( 0 ) ( ) ( ) 0 .9 2 0 7 3 5 4 9 22baT f a f b?? ? ?0( 1 ) ( 0 )00001 ( 0 . 5 ) 0 . 9 3 9 7 9 3 2 8 522 ihT T f a i h h?? ? ? ? ??1( 2 ) ( 1 )11101 ( 0 . 5 ) 0 . 9 4 4 5 1 3 5 2 222 ihT T f a i h h?? ? ? ? ??1( 3 ) ( 2 )22201 ( 0 . 5 ) 0 . 9 4 5 6 9 0 8 6 422 ihT T f a i h h?? ? ? ? ?? 72 10|| ???? ?nn TTk T (k) 0 1 2 3 4 5 6 7 8 9 10 [ ] = 07:49:44 Numerical Analysis 41 梯形法的加速 ? 梯形法遞推公式算法簡單，編程方便 ? 梯形法的加速－－ 龍貝格 (Romberg) 算法 但收斂速度較 慢 定理 ：設(shè) f(x)?C ?[a, b], 記 Tn = T (h), 則有 2 4 212( ) [ ] iiT h I f h h h? ? ?? ? ? ? ? ?bahn??07:49:44 Numerical Analysis 42 梯形法的加速 2 4 212() [] iiIhTh f h h? ? ?? ? ? ? ? ?2 4 212[]2 2 2 2iih h h hT I f ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?46234 ( / 2 ) ( ) 3 [ ] ( 3 / 4 ) ( 15 / 16 )T h T h I f h h??? ? ? ? ? ? ?4612()1 4 ( ) [ ]32ShhT T h I f h h?????? ? ? ? ? ?????????2[ ] ( )I f O h??4[ ] ( )I f O h??68121 1 6 ( )() []1 5 2hS S h I fCh hh???? ?? ? ? ? ? ????? ????6[ ] ( )I f O h??81 64( ) [ ] ( )()5 3 2hCCR h I f O hh???? ?????? ?????Richardson 外推算法 07:49:44 Numerical Analysis 43 龍貝格算法流程圖 輸出 R2 h ←b a T1 ← h/2*(f(a)+f(b)) k ← 1 k=1 Y S2 ←(4T 2T1)/3 調(diào)用梯形遞推算法得 T2 N N |R2R1| ?輸入 a, b, ?C2← (16S2S1)/15 k← k+1 h ← h/2 T1 ← T2 S1 ← S2 R2← (64C2C1)/63 k=2 k=3 C1← C2 R1← R2 Y Y N N Y 07:49:44 Numerical Analysis 44 舉例 例： 計算定積分 10s i n ( ) dx xx?10 .9 2 0 7 3 5 4 9 2T ? 20 .9 3 9 7 9 3 2 8 5T ? 40 .9 4 4 5 1 3 5 2 2T ?k T0(k) 0 1 2 3 4 5 6 7 8 9 10 ? ?11 21 43 145 882TS T??? ?22 41 43 086 934TS T??[ ] = ? ?211 1 1 6 0 .9 4 6 0 8 3 0 0 415C SS ??07:49:44 Numerical Analysis 45 Romberg 算法 ① T1 =T0 (0) ② T2 =T0 (1) ③ S1 =T1 (0) ④ T4 =T0 (2) ⑤ S2 =T1 (1) ⑥ C1 =T2 (0) ⑦ T8 =T0 (3) ⑧ S4 =T1 (2) ⑨ C2 =T2 (1) ⑩ R1 =T3 (0) kkkk RTCTSTTTkkkk2)(32)(22)(12)(0 , , , ????記 : ????????()0kT()kmT: k 次等分后梯形公式計算所得的近似值 : m 次加速后所得的近似值 Romberg 算法是收斂的 ( 1 ) ( )() 11441m k kk mmm mTTT ??????07:49:44 Numerical Analysis 46 舉例 例： 用 Romberg 算法計算定積分 , 要求計算精度滿足 1 30 dxx?[ ]= 0. 4If( ) ( ) 71| | 10kkmmTT ? ??? ? ?k 0 1 2 3 3 3 解： 逐步計算可得 (k) T0 (k) T1 (k) T2 (k) T3 (k) T4 (k) T5 07:49:44 Numerical Analysis 47 本講內(nèi)容 ? 一般理論 : 公式 , 余項 , 收斂性 , 穩(wěn)定性 ? GaussLegendre 求積公式 ? GaussChebyshev 求積公式 ? 無限區(qū)間的 Gauss 求積公式 ? Gauss 求積公式 07:49:44 Numerical Analysis 48 Gauss 型求積公式 考慮求積公式 0( )d ( )nbiiaif x x A f x?? ??? 含 2n+2 個參數(shù) (節(jié)點與系數(shù) ), 為了使該公式具有盡可能高的代數(shù)精度 , 可將 f (x) = 1, x, x2, …, x2n+1 代入公式 , 使其精確成立 , 則可構(gòu)造出代數(shù)精度至少為 2n+1 的求積公式 ! 07:49:44 Numerical Analysis 49 舉例 例： 試確定節(jié)點 xi 和系數(shù) Ai ， 使得下面的求積公式具有盡可能高的代數(shù)精度，并求出此求積公式的代數(shù)精度。39。39。39。 00()nni i i iiiA f A f x ???????()iif f x ???定理 ：若 Ai 0, i = 0, 1, … , n， 則下面的求積公式是穩(wěn)定的 0( )d ( )nbiiaif x x A f x?? ?? 證明： P103 07:49:44 Numerical Analysis 19 NewtonCotes 公式 基于等分點的插值型求積公式 ? 積分區(qū)間： [a, b] ? 求積節(jié)點： xi = a + i ? h bahn??? 求積公式： ()0( ) d ( ) ( )nbniiaif x x b a C f x??? ??( ) ( )1 ( ) dbnnii aC l x xba? ? ?0 0 dnnkkih t k tb a i k???????? x a th??? ? 0 01 ( 1 ) ( ) d!!ni nnkkit k tn i n i????? ? ?? ??Cotes 系數(shù) NewtonCotes 求積公式 07:49:44 Numerical Analysis 20 NewtonCotes 公式 21,21 )1(1)1(0 ?? CCn = 1: ( ) [ ( ) ( )]2ba baf x d x f a Tfb????代數(shù)精度 = 1 梯形公式 代數(shù)精度 = 3 n = 2: 61,32,61 )2(2)2(1)2(0 ??? CCC2( ) [ ( ) 4 ( ) ( )]6b ababaf x d x f a f f b S??? ? ??拋物線公式 Simpson公式 n = 4: 0 1 2 3 4( ) [ 7 ( ) 3 2 ( ) 1 2 ( ) 3 2 ( ) 7 ( )]90babaf x d x f x f x f x f x f x C?? ? ? ? ??科特斯 (Cotes) 公式 4/)( , abhhiax i ?????代數(shù)精度 = 5 07:49:44 Numerical Analysis 21 Cotes 系數(shù)表 ? Cotes 系數(shù)與被積函數(shù) f (x) 及積分區(qū)間 [a, b] 無關(guān) ? Cotes 系數(shù)可通過查表獲得 07:49:44 Numerical Analysis 22 NC 公式 ? Cotes 系數(shù)具有以下特點： (1) 10)( ???niniC(2) )()( n inni CC ??(3) 當(dāng) n ? 8 時，出現(xiàn)負(fù)數(shù)， 穩(wěn)定性得不到保證 。 0( )d ( )nbiiaif x x A f x?? ??設(shè)求積節(jié)點為： a ? x0 x1 xn ? b 若 f (xi) 已知，則可做 n 次多項式插值： 0( ) (( ))nn iiiLx l x f x?? ?其中 ( ) dbiiaA l x x? ? 插值型求積公式 00( ) ( ) d( )d d ( )