第4章解非線性方程-2

1、 4.4 非線性方程的牛頓法非線性方程的牛頓法 (Newton Method of Nonlinear Equations )內(nèi)容提綱（內(nèi)容提綱（Outline) 牛頓法及其幾何意義牛頓法及其幾何意義 收斂性及其收斂速度收斂性及其收斂速度 計(jì)算實(shí)例及其程序演示計(jì)算實(shí)例及其程序演示取取x0 0作為初始近似值作為初始近似值，將將 f (x)在在x0 0做做TaylorTaylor展開展開: :20000( )( )()()()()2!ff xf xfxxxxx0000( *)()()( *)f xf xfxxx000()*()f xxxfx1()()kkkkf xxxfx重復(fù)上述過程重復(fù)上述過程

2、0100()()fxxxfx作為第一次近似值作為第一次近似值一、牛頓法及其幾何意義一、牛頓法及其幾何意義Newton迭代公式迭代公式基本思路：基本思路：將非線性方程將非線性方程 f (x)=0 線性化線性化牛頓法的幾何意義牛頓法的幾何意義000:()()()Tangent line yf xfxxxxyx*x00100()()fxxxfxx 1x 21211()()fxxxfx牛頓法也稱為切線法牛頓法也稱為切線法, 迭代函數(shù)迭代函數(shù)( )( )( )f xxxfx（局部收斂性定理局部收斂性定理） 設(shè)設(shè) f (x) C2a, b，若若 x* 為為 f (x) 在在a, b上的根上的根,且且 f

3、(x*) 0，則存在則存在 x* 的鄰域的鄰域 使得任取初始值使得任取初始值 ，Newton 法產(chǎn)生的序列法產(chǎn)生的序列 xk 收斂到收斂到 x*，且滿足且滿足( *)Ux0( *)xUx12|*|( *) |lim|*|2 |( *) |kkkxxfxxxfx至少平方收斂至少平方收斂二、牛頓法的收斂性與收斂速度二、牛頓法的收斂性與收斂速度定理定理4.4.1 2( *)( *)( *)01( *)fxf xxfx在在x*的附近的附近收斂收斂由由Taylor 展開：展開：2()0( *)()()(*)(*)2!kkkkkffxfxfxxxxx2()()*( *)()2()kkkkkkf xfxxx

4、xfxfx12*()( *)2()kkkkxxfxxfx 令令k ，由由 f (x*) 0，即可得結(jié)論。即可得結(jié)論。證明：證明：Newton法法實(shí)際上是一種特殊的迭代法實(shí)際上是一種特殊的迭代法( )( )( )f xxxfx迭代函數(shù)為：迭代函數(shù)為：思考題思考題1 若若 ，Newton法法是否仍收斂？是否仍收斂？( *)0fx設(shè)設(shè) x* 是是 f 的的 m 重根，則令：重根，則令： 且且*( )()( )mf xxxq x( *)0q x2* 2*2( )( )( )( )( ) (1) ( )2 () ( )()( )( )() ( )f x fxxfxq x m mq xm xx q xxx

5、qxmq xxx q x1|( *)|11xm Answer1: 有局部收斂性有局部收斂性Answer2: 線性收斂線性收斂思考題思考題2當(dāng)當(dāng)x* 是是 f (x)=0的的m重根重根, 是否平方收斂？是否平方收斂？1*( )( )( )()()mmmfxq xq xxxxx*1*()()(1) ()() ()()()() ()kkkkkkkkkkkffmqqmqqxxxxxxxxxxxxxxxx*11*1|limlimkkkkkkmmxxxxNewton法的收斂性依賴于法的收斂性依賴于x0 的選取。的選取。 局部收斂定理對初始值局部收斂定理對初始值 x0 要求較高。要求較高。x*x0 x0 x

6、0 有根有根根唯一根唯一 (全局收斂性定理全局收斂性定理): 設(shè)設(shè) f (x) C2a, b, 若若(1)f (a) f (b) 0；則由則由Newton法產(chǎn)生的序列法產(chǎn)生的序列 xk 單調(diào)地收斂到單調(diào)地收斂到f (x)=0 在在 a, b 的唯一根的唯一根x*,且收斂速度至少是二階的且收斂速度至少是二階的保證保證產(chǎn)生的序列產(chǎn)生的序列xk單調(diào)有界單調(diào)有界保證保證Newton迭迭代函數(shù)代函數(shù)將將a , b映射于自身映射于自身定理定理4.4.2 將將f (x* )在在 xk 處作處作TaylorTaylor展開展開*2( ) 0= ()()()()()2!kkkkkff xf xfxxxxx對迭代

7、公式兩邊取極限，得對迭代公式兩邊取極限，得*()()f xxxfx00001( )( )f xxxxfx又以以0)(, 0)(, 0)( 0 xfxfxf為例證明為例證明*2*211()() ()()2()()()2()kkkkkkkkkkkf xfxxxxfxfxfxxxxfx 說明數(shù)列說明數(shù)列 xk 有下界有下界*x1()()kkkkkf xxxxfx故故xk單調(diào)遞減單調(diào)遞減, 從而從而xk收斂收斂. .令令*limkkxx？定理定理4.4.3 (全局收斂性定理全局收斂性定理): 設(shè)設(shè) f (x) C2a, b, 若若 (1) f (a) f (b) 0； (2) 在整個(gè)在整個(gè)a, b上上

8、 f (x) 0, f (x) 0 ； (3)( )( )|, |.( )( )f af bbabafaf b則對任何則對任何 , Newton 迭代格式產(chǎn)生的序列迭代格式產(chǎn)生的序列 都收斂于都收斂于f (x)=0 的根的根 x* .0 , xa bkx注注:定理的條件定理的條件(3) 保證了從保證了從 x*兩側(cè)任取兩側(cè)任取 x0 , 所得到所得到的數(shù)列的數(shù)列 xk 均在均在a , b內(nèi)內(nèi).三、三、計(jì)算實(shí)例及其程序演示計(jì)算實(shí)例及其程序演示輔助工具輔助工具: : VC VC程序設(shè)計(jì)語言程序設(shè)計(jì)語言 MatlabMatlab數(shù)學(xué)軟件數(shù)學(xué)軟件 (1) (1) 選定初值選定初值x0 ,計(jì)算計(jì)算f (x

9、0) , f (x0) 計(jì)算步驟計(jì)算步驟(2) (2) 按公式按公式 迭代迭代 得新的近似值得新的近似值xk+1 1()()kkkkf xxxfx(3) (3) 對于給定的允許精度對于給定的允許精度 ，如果如果 則終止迭代，取則終止迭代，取 ; ;否則否則k=k+1，再轉(zhuǎn)再轉(zhuǎn) 步驟步驟(2)(2)計(jì)算計(jì)算*1kxx1|kkxx允許精度允許精度最大迭代次最大迭代次數(shù)數(shù)迭代信息迭代信息例例1 1：用用Newton法求方程法求方程 的根的根, 要求要求 20 xxe51| 10kkxx1ln(2)kkxx迭代格式一：迭代格式一：迭代格式二：迭代格式二：121kkxkkkxxexxe取初值取初值 x0

10、0.0,0.0,計(jì)算如下：計(jì)算如下：對迭代格式一對迭代格式一: : the iterative number is 27, the numerical solution is 0.442852706對迭代格式二對迭代格式二: the iterative number is 3, the numerical solution is 0.442854401解：解：例題例題2求函數(shù)求函數(shù) 的正實(shí)根的正實(shí)根精度要求：精度要求： 321019.6810.944f xxxx610從圖形中我們可以從圖形中我們可以看出：看出：在在x = 7和和 x = 8 之間有一單根；之間有一單根；在在x =1和和x =

11、2 之之間有一重根。間有一重根。用用MatlabMatlab畫圖，查看根的分布情形畫圖，查看根的分布情形初值初值x08.0 時(shí),計(jì)算的是單根計(jì)算的是單根, The iterative number is 28,The numerical solution is 7.600001481初值初值x01.0 ,計(jì)算的是重根計(jì)算的是重根, The iterative number is 1356,The numerical solution is 1.198631981取初值取初值x08.0, ,用牛頓迭代公式計(jì)算如下：用牛頓迭代公式計(jì)算如下：取初值取初值x01.0, ,用牛頓迭代公式計(jì)算如下：用牛頓

12、迭代公式計(jì)算如下：小小 結(jié)結(jié)(1) 當(dāng)當(dāng)f (x)充分光滑且充分光滑且 x* 是是f (x) =0的單根時(shí)，牛的單根時(shí)，牛頓法在頓法在 x*的附近至少是平方收斂的。的附近至少是平方收斂的。(2) 當(dāng)當(dāng)f (x)充分光滑且充分光滑且 x* 是是f (x) =0的重根時(shí)，牛的重根時(shí)，牛頓法在頓法在 x*的附近是線性收斂的。的附近是線性收斂的。(3) Newton法在區(qū)間法在區(qū)間a , b上的收斂性依賴于初值上的收斂性依賴于初值x0 的選取。的選取。(4) Newton法的突出優(yōu)點(diǎn)：收斂速度快法的突出優(yōu)點(diǎn)：收斂速度快 缺點(diǎn)：需計(jì)算函數(shù)的導(dǎo)數(shù)。缺點(diǎn)：需計(jì)算函數(shù)的導(dǎo)數(shù)。四四 重根情形的重根情形的Newt

13、onNewton迭代法迭代法重根情形的重根情形的NewtonNewton迭代法是線性收斂的迭代法是線性收斂的, , 且有且有1( *)1xm 由此易知若迭代函數(shù)為：由此易知若迭代函數(shù)為：( )( )( )f xxxmfx則則NewtonNewton迭代格式迭代格式 為平方收斂為平方收斂. .1()()kkkkf xxxmfx但但 m 通常未知通常未知, ,故常用修改方法：故常用修改方法：( )( )( )f xu xfx令令若若x*為為f (x)的的m重根重根, 則則x*為為u (x) = 0的單根的單根, ,取取( )( )( )u xxxux則得則得: :12()()()()()kkkkk

14、kkf xfxxxfxf xfx此格式二階收斂此格式二階收斂, ,但要計(jì)算二階導(dǎo)數(shù)但要計(jì)算二階導(dǎo)數(shù). .4.5 弦截法與拋物線法弦截法與拋物線法 一、一、 單點(diǎn)弦截法單點(diǎn)弦截法 固定一點(diǎn)固定一點(diǎn) P0( x0 , f (x0), 用差商用差商 代替代替Newton公式中的公式中的 , 則得離散化的公式則得離散化的公式: 00()()kkf xf xxx()kfx100()()()()kkkkkf xxxxxf xf x稱為單點(diǎn)弦截法稱為單點(diǎn)弦截法, 是一種簡單迭代法是一種簡單迭代法. 幾何意義幾何意義: 依次用弦線代替曲線依次用弦線代替曲線, 用線性函數(shù)的零點(diǎn)作為用線性函數(shù)的零點(diǎn)作為f (x)

15、零點(diǎn)的近似值零點(diǎn)的近似值. 定理定理4.5.1 設(shè)設(shè) f (x)在在a , b上滿足：上滿足： (1) f (a) f (b) 0; (2) 在在a , b上連續(xù)且不變號上連續(xù)且不變號; (3) 選取初始值選取初始值 , 使得使得 , 選選 定定a , b中的一個(gè)中的一個(gè), 另一個(gè)為另一個(gè)為 . ( ),( )fxfx0 , xa b00(),()f xfx0 x1x則由迭代格式則由迭代格式 100()()()()kkkkkf xxxxxf xf x所產(chǎn)生的序列所產(chǎn)生的序列 xk 單調(diào)地收斂于單調(diào)地收斂于f (x)=0在在a , b上的唯一根上的唯一根 x*,且收斂速度是線性的且收斂速度是線性

16、的. 二、二、 雙點(diǎn)弦截法雙點(diǎn)弦截法 若若 用差商用差商 代替代替Newton公式中的公式中的 , 則得公式則得公式: 11()()kkkkf xf xxx()kfx111()()()()kkkkkkkf xxxxxf xf x稱為雙點(diǎn)弦截法稱為雙點(diǎn)弦截法. 注：注：雙點(diǎn)弦截法與前面介紹的迭代法有明顯區(qū)別雙點(diǎn)弦截法與前面介紹的迭代法有明顯區(qū)別, 前面所講述前面所講述迭代法計(jì)算迭代法計(jì)算 xk+1時(shí)只用到時(shí)只用到 xk , 故稱為單步迭代故稱為單步迭代; 而雙點(diǎn)弦截法而雙點(diǎn)弦截法計(jì)算計(jì)算 xk+1時(shí)時(shí), 卻同時(shí)用到前面兩步的結(jié)果卻同時(shí)用到前面兩步的結(jié)果 xk 1和和 xk , 故稱為多步故稱為多

17、步迭代迭代.說明：說明：單點(diǎn)弦截是雙點(diǎn)弦截的特殊情況單點(diǎn)弦截是雙點(diǎn)弦截的特殊情況.幾何解釋：幾何解釋：xyx*xk 1xkxk+1Pk 1PkPk+1111(,(),(,()kkkkkkPxf xP xf x11()()kkkkf xf xxx為為 的斜率的斜率1kkP P直線方程為：直線方程為：11()()()()kkkkkkf xf xyf xxxxx定理定理4.5.2 (局部收斂定理局部收斂定理) 設(shè)設(shè) f (x)=0, 如果：如果： (1) f (x)在根在根 x*的某個(gè)領(lǐng)域內(nèi)有連續(xù)的二階導(dǎo)數(shù)的某個(gè)領(lǐng)域內(nèi)有連續(xù)的二階導(dǎo)數(shù), 且且(2) 任取任取 屬于該領(lǐng)域?qū)儆谠擃I(lǐng)域;則由雙點(diǎn)弦截公式所

18、得序列則由雙點(diǎn)弦截公式所得序列 收斂于根收斂于根 x*, 且收斂速度且收斂速度 ( )0fx01,xxkx151.6182P定理定理4.5.2 (全局性收斂定理全局性收斂定理) 設(shè)設(shè) f (x) C2a , b, 且且 (1) f (a) f (b) 0； (2) 在整個(gè)在整個(gè)a, b上上 f (x) 0, f (x) 0 ； (3)( )( )|, |.( )( )f af bbabafaf b則則 由雙點(diǎn)弦截公式所得序列由雙點(diǎn)弦截公式所得序列 收斂于收斂于 f (x)=0 的唯一根的唯一根 x*. 01, , xxa bkx例例1：用用單點(diǎn)弦截和雙點(diǎn)弦截求方程單點(diǎn)弦截和雙點(diǎn)弦截求方程 在在

19、2,3內(nèi)的特殊情況內(nèi)的特殊情況.3( )250f xxx解解: (1) 單點(diǎn)弦截法單點(diǎn)弦截法2( )320,( )60,(2)10,(3)160fxxfxxff 取取 ， 單點(diǎn)弦截公式為：單點(diǎn)弦截公式為：013,2xx331332532215(3)(1,2,)221221kkkkkkkkkkkxxxxxxxkxxxx(2) 雙點(diǎn)弦截法雙點(diǎn)弦截法取取 ， 雙點(diǎn)弦截公式為：雙點(diǎn)弦截公式為：013,2xx3111331155(1,2,)22kkkkkkkkkx xxxxkxxxx三、弦截法與三、弦截法與Aitken迭代法的聯(lián)系迭代法的聯(lián)系 設(shè)設(shè)( )0( ).(),()( ()kkkkkf xxxy

20、xzyx 對于對于 在在 和和 兩點(diǎn)處兩點(diǎn)處使用弦截法使用弦截法, 則得則得( )( )0g xxx(, ()kkxg x(, ()kkyg y即為即為Aitken迭代公式迭代公式21 ()( ()2 ()kkkkkkkxxxxxxx 四、拋物線法四、拋物線法 若用過三點(diǎn)若用過三點(diǎn) 和和 的的拋物線拋物線2211(,(),(,()kkkkxf xxf x(,()kkxf x與與x 軸交點(diǎn)的橫坐標(biāo)作為軸交點(diǎn)的橫坐標(biāo)作為 xk+1 , 則得拋物線法或則得拋物線法或Mlller方方法法. 一條拋物線有兩個(gè)實(shí)零點(diǎn)時(shí)一條拋物線有兩個(gè)實(shí)零點(diǎn)時(shí), 取與取與 xk 較近的那個(gè)零點(diǎn)較近的那個(gè)零點(diǎn)作為作為xk+1

21、 .12212121212121()()()()( )()()()()()()()()()()()kkkkkkkkkkkkkkkkkkkkkxxxxxxxxxf xf xxxxxxxxxxxxxf xxxxx4.5 非線性方程組的迭代算法非線性方程組的迭代算法一、不動點(diǎn)迭代格式一、不動點(diǎn)迭代格式(簡單迭代格式簡單迭代格式) 12121( )( )(,) ,( ) = ( ),( ),( ) )()TTnnkk= x xx0 +F xxxxxxxxx=x (0)(0)(0)012(,)Tn= xxxx取初值取初值 代入計(jì)算即可代入計(jì)算即可. 二、二、Newton迭代格式迭代格式111222121

22、2()0(,)0()0(,)0()()0(,)0nnnnnffxxxffxxxffxxx0 xxFxx( )( )( )1()( )()(),1,2,knkkiiijjjjfffxxinxxxx將非線性方程組線性化：將非線性方程組線性化：設(shè)設(shè) 為為 的第的第k 次近似解次近似解, 由由Taylor公公式得式得( )(, )kU*xx( ) 0 F x用線性方程組用線性方程組( )( )( )1()()()0,1,2,knkkiijjjjffxxinxxx即即( )( )( )()()()(*)kkk FxxxF x近似代替近似代替 , 用用(*)的解作為的解作為 的第的第k+1次近似次近似解解, 則得則得Newton迭代格式：迭代格式：( ) 0 F x( ) 0 F x(1)( )( )1( )()()(0,1,2,)k+kkkk xxFxF x這里這里111122221212()nnnnnnfffxxxfffxxxfffxx