數(shù)值分析4(牛頓迭代法)

1、1/25*lim()nnxx 0101()()nnxxxxx 不動點框架不動點框架:12:00收斂性收斂性 收斂速度收斂速度(1)( )( *)( *)( *)0 ( *)0rrxxxx |( )| 1x 2/25數(shù)值分析4Newton迭代格式迭代格式Newton迭代法的收斂性迭代法的收斂性Newton迭代法收斂速度迭代法收斂速度弦截法迭代格式弦截法迭代格式12:003/2512:00Nature and Nature law lay hid in night. God said, Let Newton be, and all was light. Alexander Pope4/25( )

2、( )( )xxx f xx*()1()()0 xxfx*()0, ( )1/( )fxxfx 如如果果取取1:()/()nnnnxxf xfx 牛牛頓頓迭迭代代法法給定初值給定初值 x0 , 迭代產(chǎn)生數(shù)列迭代產(chǎn)生數(shù)列x0, x1, x2, xn, 12:005/25設設 x*是方程是方程 f(x)=0 的根的根, x0是是x*的近似值。的近似值。在在 x0 附近對函數(shù)做附近對函數(shù)做局部線性化局部線性化)()()(000 xxxfxfxf x1比比x0更接近于更接近于x*x0 x1x*0)()(000 xxxfxf f(x) = 0 )()(0001xfxfxx 化難為易化繁為簡12:006/

3、25應用應用求正數(shù)平方根算法求正數(shù)平方根算法設設C 0,Cx x2 C = 0令令 f(x) = x2 C , 則則xxf2)( nnnnxCxxx221 211nnnxCxx 12:007/25初值初值: x0=1.5迭代格式迭代格式: xn+1=0.5(xn+2/xn) (n = 0,1,2,)例例1. 平方根算法求平方根算法求2 xn | en |1.416666666666667 2.45e-0031.414215686274510 2.12e-0061.414213562374690 1.59e-0121.414213562373095 2.22e-0161.414213562373

4、095 2.22e-016表表1 1 平方根算法實驗平方根算法實驗12:008/25收斂性收斂性: (1) 符合不動點框架符合不動點框架00, 2 (1) ()nxxn只只有有界界要要112222nnnxxx 22121(2)22nnnnxxxx12:00(2) 從序列收斂的角度從序列收斂的角度(單調(diào)有界序列單調(diào)有界序列)21212=0 2(2)nnnnnnnxxxxxxx 單單調(diào)調(diào)下下降降9/25由此可知由此可知平方根算法具有平方根算法具有 2 階收斂速度。階收斂速度。 nnnxxx21)2(221 221|2|2|lim21 nnnxx222121 nnnxxx22121(2)22nnnn

5、xxxx2lim nnx思考思考: 如何求倒數(shù)、平方根和立方根？如何求倒數(shù)、平方根和立方根？10/25Newton迭代法的局部收斂性迭代法的局部收斂性定理定理2.7 設設 f(x) 在點在點x*的某鄰域內(nèi)具有二階連的某鄰域內(nèi)具有二階連續(xù)續(xù)導數(shù)導數(shù), 且且 f(x*)=0和和 f(x*) 0, 則對充分靠近則對充分靠近點點x*的初值的初值x0, Newton迭代法迭代法至少平方至少平方收斂收斂。)()(1nnnnxfxfxx )()()(xfxfxx *2()()()/(0)1 xf xfxfx 收收斂斂所以所以Newton迭代法至少平方收斂。迭代法至少平方收斂。)()()(*xfxfx 12:

6、0011/25例例2.求求 x3 +10 x 20 =0 在在 x0=1.5 附近的根附近的根解解:取取2010)(3 xxxf3121020310nnnnnxxxxx 牛頓迭代格式牛頓迭代格式則有則有103)(2 xxfn xn | en | 0 1.51 1.59701492537 0.002452808741981 2 1.59456374876 1.632137654805e-063 1.59456211663 7.227551890309e-134 1.59456211663 2.220446049250e-16 表表2 2 牛頓迭代法實驗牛頓迭代法實驗12:0012/25注釋注釋1

7、: 為了二次收斂有意義我們需要為了二次收斂有意義我們需要f(x)相除相除, 這這個假設是關鍵的。個假設是關鍵的。 f(x)=x3 3x + 2 = 0在在x*=1附近附近0)( xf12:001: ()/()nnnnxxf xf x 牛牛頓頓迭迭代代法法13/25x*x0 x0 x0Newton方法收斂性依賴于方法收斂性依賴于x0 的選取。存的選取。存在在 x0使使Newton迭代法陷入死循環(huán)。迭代法陷入死循環(huán)。注釋注釋2:12:0014/25Newton迭代法的變型弦截法迭代法的變型弦截法)()()()(111 nnnnnnnxxxfxfxfxx)()(1nnnnxfxfxx 1-1()()

8、()nnnnnf xf xfxxx 由于由于代入牛頓迭代格式代入牛頓迭代格式x0 x112:0015/25n xn | en | | en+1 |/| en |1.6181 -1.5 5.00e-0012 -2.5 5.00e-001 1.53473 -1.83783783783 1.62e-001 0.49784 -1.95420890762 4.57e-002 0.86915 -2.00552244119 5.52e-003 0.81096 -1.99982796307 1.72e-004 0.77427 -1.99999936831 6.31e-007 0.77858 -2.000000

9、00007 7.24e-011 0.7778表表3 弦截法收斂速度實驗弦截法收斂速度實驗例例3 3. .已知方程已知方程有兩根有兩根: :取根附近值做初值取根附近值做初值, ,分析牛頓迭代法實驗的數(shù)據(jù)。分析牛頓迭代法實驗的數(shù)據(jù)。 0233 xx2*1 x1*2 x參考參考: : 數(shù)值分析基礎數(shù)值分析基礎, , 關冶關冶 陸金甫陸金甫16/25表表4 初值取初值取 1.5 時牛頓迭代法速度時牛頓迭代法速度n xn | en | | en+1 |/| en |20-1.5 5.00e-0011-2.333333333333.33e-0011.33332-2.055555555555.55e-002

10、0.50003-2.001949317731.94e-0030.63164-2.000002528292.52e-0060.66545-2.000000000004.26e-0120.666712:0017/25表表5 初值取初值取 1.5 時牛頓迭代法速度時牛頓迭代法速度n xn | en | | en+1 |/| en |01.5 5.00e-00111.2666666 2.66e-001 0.533321.1385620 1.38e-001 0.519631.0707773 7.07e-002 0.510841.0357918 3.57e-002 0.505751.0180008 1.8

11、0e-002 0.502961.0090271 9.02e-003 0.501571.0045203 4.52e-003 0.500781.0022618 2.26e-003 0.500491.0011313 1.13e-003 0.5002101.0005657 5.65e-004 0.5001111.0002829 2.82e-004 0.500012:0018/25推論推論: 設設 x*是是 f(x)=0 的二重根的二重根, 則牛頓迭代法只具則牛頓迭代法只具有一階收斂。有一階收斂。證證: x*是二重根是二重根 f(x)=(x x*)2g(x)()()(2)()(*xgxxxgxxxf )

12、()()(2)()()(*xgxxxgxgxxxx 211)(* x 牛頓迭代法只是一階收斂牛頓迭代法只是一階收斂。*1, ()11mxn 重重根根12:0019/25nxn | en | | en+1 |/| en |201.5 5.00e-00111.033333333333.33e-002 0.133321.000182149361.85e-004 0.163931.000000005525.52e-009 0.1667 若若 x*是是 f(x)=0 的的 m 重根重根,修正的牛頓迭代法修正的牛頓迭代法)()(1nnnnxfxfmxx 為二階收斂為二階收斂 表表5 x*為二重根時修正的牛

13、頓迭代實驗為二重根時修正的牛頓迭代實驗)()(21nnnnxfxfxx m = 2 f(x)1/m或或f(x)/f(x)單根單根12:0020/25Examine the function graphically (to locate roughly where the roots are and how many there may be)l curve sketching is one way or.l best: use a Matlab plot to get the lay of the landset the interval or the starting point (find

14、 a range of x- values over which the function changes sign)iteratively refine the initial guess with a root-finding algorithm (bisection is dependable but slow; Newton is fast if the initial value is good)一些建議一些建議21/2512:00迭代方法比較迭代方法比較二分法二分法 函數(shù)值的正負號函數(shù)值的正負號不動點家族不動點家族(牛頓法牛頓法)函數(shù)值函數(shù)值(函數(shù)的導數(shù)值函數(shù)的導數(shù)值) 收斂速度慢

15、收斂速度慢 收斂速度快收斂速度快(特別快特別快) 總是收斂總是收斂 收斂是有條件的收斂是有條件的22/25非線性方程組非線性方程組: GaussNewton方法方法()()()( )()()()kkkF xF xFxxx ()()()()()()kkkFxxxF x 111122221212( )( )( )( )( )( )( )( )( )( )nnnnnnfxfxfxxxxfxfxfxxxxfxfxfxxxxFx (1)()()()1()()kkkkxxFxF x 12:001( )( )( )nfxF xfx 1nxxx ( )0F x 23/25例例3. 用牛頓迭代法求解非線性方程組

16、用牛頓迭代法求解非線性方程組 01)5 . 0()2(01222yxyx211212(,)1fx xxx2221212(,)(2)(0.5)1fxxxx 11121122212212421ffxxxFxxffxx 24/25()()12()()12(1)( )1111(,)(1)( )222(,)kkkkkkxxkkxxxxfFfxx 分別取初值分別取初值(1,0)和和(2,2),牛頓迭代法計算數(shù)據(jù)如下牛頓迭代法計算數(shù)據(jù)如下 nx1 x2 x1 x201 0 2 211.06250.12501.64581.583321.06730.13911.55701.416331.06730.13921.

17、54651.391741.06730.13921.54631.391225/25*lim()nnxx 0101()()nnxxxxx 不動點框架不動點框架:收斂性收斂性 收斂速度收斂速度|( )| 1x (1)( )( *)( *)( *)0 ( *)0rrxxxx 26/2512:00 Iteration in mathematics may refer to the process of iterating a function i.e. applying a function repeatedly, using the output from one iteration as the input to the next. Iteration o