【正文】 ,)( baxg ? () （ 2） )(xg 的導(dǎo)數(shù) )(xg? 在 ? ?ba, 上有界，且存在正數(shù) 1?L 使得對一切 ? ?bax ,? 有 ,1|)(| ??? Lxg () 那么對于任意初始值 ? ?bax ,0? 由不動點迭代 ()產(chǎn)生的序列都收斂于 g 在 ? ?ba, 的唯一不動點 p ，并且有誤差估計式 |,|1||01 xxLLekk ??? ,1?k () 其中 pxe kk ?? . 證明 首先證明 g 的不動點存在且唯一 . 令 ).()( xgxxh ?? () 據(jù)條件 (1) ,0)()( ??? agaah .0)()( ??? bgbbh 又據(jù)條件 (2)，在 )(xg? 上存在，因此 )(xg 在 ? ?ba, 上連續(xù)，從而 )(xh 在 ? ?ba, 上也連續(xù)，因此方程 0)( ?xh 在 ? ?ba, 上至少有一個跟．現(xiàn)假設(shè)方程 0)( ?xh 在 ? ?ba, 上有兩個根qpqp ?, ，則由 Lagrange 中值定理知，在 p 與 q 之間存在 ? 使得 |,||)(||))((||)()(||| qpgqpgqgpgqp ????????? ?? 再由 () .|||||||)(| qpqpLqpg ?????? ? 這就得到 矛盾式： .|||| qpqp ??? 因此 qp? ，即 0)( ?xh 在 ? ?ba, 中的根是唯一的． 其次證明由 不動點迭代格式 ()產(chǎn)生的序列 }{kx 是收斂于 p 的．根據(jù)定理條件 (1) ? ?baxk ,? ， ???? ,2,1,0k ，因此不動點迭代過程不會中斷．由 ()式有 ).()( 1 pgxgpx kk ??? ? () 應(yīng)用 Lagrange 中值定理，并根據(jù) ()式有 |||||)(||)()(||| 111 pxLpxgpgxgpx kkkk ???????? ??? ? 9 .|| 0 pxLk ?????? () 因為 10 ??L ，所以 ,0||l i m||l i m0 ???? ???? pxLpx kkkk 即 .lim pxkk ??? () 最后，推導(dǎo)估計式 ()． 應(yīng) 用收斂性的證明過程，有 |||)()(||| 111 ????????? ????? jkjkjkjkjkjk xxLxgxgxx |,| 01 xxL jk ?????? ? () 于是 ? ? ?? ?? ????? ???? ?????10 110 1||mj jkjkmj jkjkkmk xxxxxx ||1 )1(|| 010110 xxLLLxxLmkmjjk ?????? ???? .||101 xxLLk ??? () 在上式中令 ??m ，得 .1||||01 xxLLpxekkk ????? () ()式得證． 例 [2] 討論例 中不動點迭代 ???????????? ??? ?? ,2,1,22)(213 113 kxxgx kkk () 的收斂性 . 為使解的近似值的誤差不超過 810? ，試確定迭代次數(shù)． 解 迭代法 ()的迭代函數(shù)為 .22)(2133 ???????? ?? xxg )(3xg 的定義域為 ]4,( 3?? ．取初始值 ?x ，由不動點迭代 ()得 ?x ，因此取區(qū)間 ? ? ? ?, ?ba ．由于 ,02243)( 22133 ????????? ???? ? xxxg ? ?,?x 因此 )(3xg 在 ? ?, 上單調(diào)減?。? 而 ? ? ,)()(m i n , ??? gxgx 10 ? ? ,)()(m a x , ??? gxgx 于是，當(dāng) ? ?,?x 時， ? ?,)(3 ?xg ，但 ,04432243)( 232333 ??????? ?????????? ????? ? xxxxxg ? ?,?x )(3xg? 在 ? ?, 上單調(diào)減小，因此 ? ? ? ?? ?3 3 , , a x | ( ) | m a x | ( ) | , | ( ) |xxg x g g??? ? ?? .)(3 ??? g 因此，定理 的 條件 (2)不 成立．從表 看到，取 ?x 作為初始值 0x ， ?x 作為 1x ．當(dāng) ? ?3031,xxx? 時， ? ?303132,31 , xxxx ? 從而 ? ?30313 ,)( xxxg ? ．又由于 ? ?3 1 3 033,| ( ) | max | ( ) |x x xg x g x???? ? ?3 31 3 30m a x | ( ) | , | ( ) |g x g x??? ,18 5 3 5 4 1 0 7 )( 303 ????? Lxg 因此定理 的條件成立．故迭代過程收斂 ? ?3031,xx 中任意取初值，為使解 p 的近似值 kx的誤差不超過 810? ，根據(jù)誤差估計式 () |,|1||01 xxLLpxkk ???? 只要 .10||1 801 ???? xxLLk 因此， k 應(yīng)取為 8 10||lg 1 0 lg 1lgxxLk L????? 8 53 5 41 0 1 46 4 58 9 1 28 1 16 3 33 0 74 6 ?????? ???? .? 取 138?k ．于是迭代 138+30=168 次必可使近似解的誤差不超過 810? ． 實際上，從表 中可以看到，只要迭代 110 次便可達到所要求解的精度． ()式右端是最大可能的誤差界． 就本例來說，估計的迭代次數(shù)偏大了 . 11 不動點迭代 算 法的收斂速度 定理 [2] 在定理 的假設(shè)條件下，再設(shè)函數(shù) )(xg 在區(qū)間 ? ?ba, 上 )2(?m 次連續(xù)可微，且在方程 ()的跟 p 處 ,0)()( ?pgj ,1,1 ????? mj ,0)()( ?pg m () 則不動點迭代為 m 階收斂 . 證明 據(jù)定理 知，方程 （ ） 在 ? ?ba, 上有唯一根 p ．且對任意初始值 ? ?bax ,0? ，不動點迭代序列 ??kx 收斂于 p 由于 ),()()()(11 pgepgpgxgpxe kkkk ??????? ?? () 據(jù) Taylor 公式和定理條件有 ? ? mkkkmmkmkkk eepgmepgmepgepge )(!1)()!1( 1)(!21)( )(1121 ?????????????? ??? ,)(!1 )( mkkkm eepgm ??? 其中 10 ?? k? . 易知，對于充分大的 k ，若 01??ke ，則 ),1,(0 ?????? kkiek ，從而 ? ? ).(!1lim 1 pgmee mmkkk ???? (） 故證得不動點迭代為 m 階收斂． 關(guān)于不動點的迭代，還有下面的局部收斂定理 . 定理 [2] 設(shè) p 是方程 ()的一個根， )(xg 在 p 的某領(lǐng)域內(nèi) m 次連續(xù)可微，且 ,0)()( ?pgj ,1,1 ????? mj ,0)()( ?pg m ),2( ?m 則當(dāng)初始值 0x 充分接近 p 時（存在正數(shù) r ，對一切 ? ?rprpx ??? ,0 ），不動點迭代序列 ??kx都收斂于 p ，且收斂階數(shù)為 m . 證明 由于假設(shè) ??xg? 在 p 的某領(lǐng)域內(nèi)連續(xù)且 ? ? 0?? pg ，因此必存在 0?r 使得對一 切 ? ?rprpx ??? , 有 .1|)(| ??? Lxg 又據(jù) Lagrange 中值定理，有 ),)(()()( pxgpgxg ???? ? ? 在 x 與 p 之間，從而 ,|||||)(||)()(| rpxpxgpgxg ??????? ? 即 .|)()(| rpgxg ?? () 因此當(dāng) ? ?rprpx ??? , 時， ? ?rprpxg ??? ,)( ．據(jù)定理 和定理 知，對于任意初始值 ? ?rprpx ??? ,0 ，不動點迭代收斂，且收斂階數(shù)為 m ． 12 加速不動點迭代算法及其收斂 性 一個收斂的迭代過程將產(chǎn)生一個收斂序列 ?????? , 21 nxxx ， 如 pxnn ???lim．這樣，只要迭代足夠多次，即 n 充分大時，如 mn? ，則可取 mxp? ．但若迭代過程收斂緩慢，則會使計算量變得很大，因此需要加速收斂過程． 假設(shè)一個序列 ??nx ： ?????? , 21 nxxx ， 線性 收斂于 p (收斂緩慢 )，即有 ??????? px pxnnn 1lim ? ?.0?? () 于是當(dāng) n 足夠大時