數(shù)值分析Newton法

1、1第三節(jié)第三節(jié) NewtonNewton法法2 2009, Henan Polytechnic University2 用迭代法可逐步精確方程用迭代法可逐步精確方程 根的近根的近似值，但必須要找到似值，但必須要找到 的等價(jià)方程的等價(jià)方程 , ,如果如果 選得不合適選得不合適, ,不僅影響收斂速度不僅影響收斂速度, ,而且有而且有可能造成迭代格式發(fā)散。能否找到一種迭代方法可能造成迭代格式發(fā)散。能否找到一種迭代方法, , 結(jié)構(gòu)簡(jiǎn)單結(jié)構(gòu)簡(jiǎn)單, ,收斂速度快。這就是本節(jié)要介紹的牛頓收斂速度快。這就是本節(jié)要介紹的牛頓迭代法。迭代法。 0)( xf0)( xf)(xx )(x 3 2009, Henan

2、Polytechnic University3取取x0 0作為初始近似值作為初始近似值，將將f(x)在在x0 0做做TaylorTaylor展開展開: :重復(fù)上述過(guò)程重復(fù)上述過(guò)程 作為第一次近似值作為第一次近似值6.3.1 牛頓迭代法牛頓迭代法基本思想：將非線性方程基本思想：將非線性方程f(x)=0 線性化線性化20000)(2)()()()(xxfxxxfxfxf )()()(0000 xxxfxfxf )()(000 xfxfxx )()(1kkkkxfxfxx )()(0001xfxfxx Newton迭代公式迭代公式4 2009, Henan Polytechnic Universit

3、y46.3.2 牛頓法的幾何意義牛頓法的幾何意義xyx*x0 x 1x 2牛頓法也稱為切線法牛頓法也稱為切線法)()(000 xxxfxfy )()(0001xfxfxx )()(1112xfxfxx 5 2009, Henan Polytechnic University5（局部收斂性定理）設(shè)局部收斂性定理）設(shè) f (x) C2a, b，若，若 x* 為為 f (x) 在在a, b上的根上的根, ,且且 f (x*) 0，則存在，則存在 x* 的的鄰域鄰域 使得任取初始值使得任取初始值 ，Newton 法產(chǎn)生的序列法產(chǎn)生的序列 xk 收斂到收斂到 x*，且滿足，且滿足至少平方收斂至少平方收斂

4、6.3.3 牛頓法的收斂性與收斂速度牛頓法的收斂性與收斂速度)( xU )(2)(lim21 xfxfxxxxkkk)(0 xUx 6 2009, Henan Polytechnic University6在在x*的附近收斂的附近收斂證明：證明：Newton法實(shí)際上是一種特殊的迭代法法實(shí)際上是一種特殊的迭代法10)()()()(2 xfxfxfxg)()()(xfxfxxg 7 2009, Henan Polytechnic University7由由Taylor 展開展開：令令k ，由由 f (x*) 0，即可得結(jié)論。即可得結(jié)論。2)(2)()()()(0kkkkxxfxxxfxfxf 2)

5、()(2)()()(kkkkkxxxffxfxfxx )(2)()(21kkkxffxxxx 8 2009, Henan Polytechnic University8有根有根根唯一根唯一全局收斂性定理：設(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*,且收斂速度至少是二階且收斂速度至少是二階的。的。9 2009, Henan Polytechnic University9證明：證明：以以0)(, 0)(, 0)( 0 xfxf

6、xf為例證明為例證明將將f(x*)在在 xk 處作處作Taylor展開展開2)(2)()()()(0kkkkxxfxxxfxfxf 212)()(2)()()(2)()()(kkkkkkkkxxxffxxxxffxfxfxx 10 2009, Henan Polytechnic University10對(duì)迭代公式兩邊取極限，對(duì)迭代公式兩邊取極限，得得 說(shuō)明數(shù)列說(shuō)明數(shù)列xk有下界有下界故故xk單調(diào)遞減單調(diào)遞減, , 從而從而xk收斂收斂. .令令？ kkxlim)()(0001xfxfxx xkkkkkxxfxfxx )()(1)()( ff 11 2009, Henan Polytechnic

7、 University11 例例1 1 用用Newton迭代法求方程迭代法求方程xex-1=0在在0.5附近附近的根的根, ,精度要求精度要求 =10-5. . 解解 Newton迭代格式為迭代格式為, 2 , 1 , 0,111 kxexxexeexxxkxkkxkxxkkkkkkkkxk(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.000000

8、0012 2009, Henan Polytechnic University12例例2 2 解：解：設(shè)設(shè), 0,2 cxcx則則取取cxxf 2)(則由則由Newton迭代公式迭代公式)(21221nnnnnnxcxxcxxx )0( cc用用 Newton 迭代法求迭代法求選取初始值選取初始值即即可可cx 0可可以以嗎嗎？cx 013 2009, Henan Polytechnic University13牛頓法牛頓法的的優(yōu)點(diǎn)優(yōu)點(diǎn)至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)辽俣A局部收斂，收斂速度較快，特別是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí)。代點(diǎn)充分靠近精確解時(shí)。牛頓法牛頓法的缺點(diǎn)的缺點(diǎn)對(duì)重根收斂速度較慢（線性收斂）對(duì)重根收斂速度較慢（線性收斂）對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解先用其它算法獲取一個(gè)近似解，然后使用牛頓法先用其它算法獲取一個(gè)近似解，然后使用牛頓法 需要求導(dǎo)數(shù)！需要求導(dǎo)數(shù)！14 2009, Henan Polytechnic University146.3.5 Newton下山法下山法1()()kkkkf xxx