方程求根的數(shù)值解法

1、121、牛頓法的思想、牛頓迭代公式；、牛頓法的思想、牛頓迭代公式；2、牛頓法的收斂性；牛頓法的收斂性；3、牛頓法的收斂速度；、牛頓法的收斂速度；3、弦截法思想。、弦截法思想。3稱(chēng)為迭代公式。稱(chēng)為迭代函數(shù)，次近似，稱(chēng)為稱(chēng)為初始近似，是方程的根。即即則可得若序列有極限，即，出發(fā)，作序列再?gòu)哪骋粩?shù)先將方程化為對(duì)于一般形式的方程)()(0)()(lim,2, 1 ,0,)()(0)(10100nnnnnnnxgxxgnxxaafagaaxnxgxxxxgxxf4( )x kx( )0f x ( )x由前面的討論可知，選擇合適的迭代函數(shù)由前面的討論可知，選擇合適的迭代函數(shù) ，是提高迭代數(shù)列是提高迭代數(shù)列

2、 的收斂速度的關(guān)鍵。本節(jié)介紹一種的收斂速度的關(guān)鍵。本節(jié)介紹一種確定迭代函數(shù)確定迭代函數(shù) 的方法的方法 牛頓法。牛頓法是求解牛頓法。牛頓法是求解方程方程 的一種重要方法，它的最大優(yōu)點(diǎn)是方程在的一種重要方法，它的最大優(yōu)點(diǎn)是方程在單根附近具有較高的收斂速度，它還可以用于求代數(shù)方單根附近具有較高的收斂速度，它還可以用于求代數(shù)方程的重根、復(fù)根；也可以拓廣用于求解非線性方程組的程的重根、復(fù)根；也可以拓廣用于求解非線性方程組的問(wèn)題。問(wèn)題。5取取 在在 x0 做一階做一階taylor展開(kāi)展開(kāi):將將 看成高階小量，則有：看成高階小量，則有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxf

3、xx 只要只要 ，每一步迭代都有，每一步迭代都有 ， 而而 且且 ，*limxxkk ，則，則 的根。的根。1()()kkkkf xxxfx（牛頓公式）（牛頓公式）20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之間。之間。()0kfx6( )0f x ( )yf x( )yf x*xkxkxx(,()kkp xf x()()()kkkyf xfxxx令其為零，得切線令其為零，得切線 與與 軸的交點(diǎn)為軸的交點(diǎn)為lx()()kkkf xxxfx從幾何的角度來(lái)分析一下牛頓公式的直觀結(jié)構(gòu)，方程從幾何的角度來(lái)分析一下牛頓公式的直觀結(jié)構(gòu)，方程 的根就是曲線的根就是曲

4、線 與與 軸的交點(diǎn)。設(shè)軸的交點(diǎn)。設(shè) 為為 的一個(gè)近似值，過(guò)曲線的一個(gè)近似值，過(guò)曲線 上橫坐標(biāo)為上橫坐標(biāo)為 的點(diǎn)的點(diǎn) ，引一條切線，其方程為，引一條切線，其方程為7( )yf x( )yf xxx1()()kkkkf xxxfx()()kkkf xxxfx(,()kkp xf x將此式將此式 與上面求得的牛頓與上面求得的牛頓公式公式 進(jìn)行比較即可知道：牛頓公進(jìn)行比較即可知道：牛頓公式實(shí)際上就是用曲線式實(shí)際上就是用曲線 在在 點(diǎn)點(diǎn) 處的切線與處的切線與 軸的交點(diǎn)作為曲線軸的交點(diǎn)作為曲線 與與 軸交軸交點(diǎn)的近似，如下圖所示點(diǎn)的近似，如下圖所示8x*x0 x1x2xyf(x)9例例 用牛頓法求解方程用

5、牛頓法求解方程xxe在在00.5x 附近的根附近的根5(10 )解：將方程解：將方程xxe轉(zhuǎn)化為等價(jià)方程轉(zhuǎn)化為等價(jià)方程10 xxe 令令( )1xf xxe，則牛頓迭代公式為，則牛頓迭代公式為11(1)1kkkxxkkkkkxkkx exexxxexx(0,1,2,)k 00.5x ，迭代結(jié)果如下表，迭代結(jié)果如下表3.61000.5x ，迭代結(jié)果如下表，迭代結(jié)果如下表取初值取初值kkx012340.50.57102040.56715550.56714330.5671432*0.567143x ，與例，與例4、例、例6的迭代結(jié)果進(jìn)行比的迭代結(jié)果進(jìn)行比較可見(jiàn)，牛頓公式的收斂速度是相當(dāng)快的較可見(jiàn)，牛

6、頓公式的收斂速度是相當(dāng)快的。111213newton法的收斂性依賴于法的收斂性依賴于x0 的選取。的選取。x*x0 x0 x01410 10. ( ) 1,( )(1)( ) ( )( )1 10.5kxxxxxkkkkxefxxefxexfxxexxxfxxxexxxx例：用牛頓法解方程解：牛頓法迭代函數(shù)為牛頓公式為可先用二分法或經(jīng)驗(yàn)確定迭代初值，再按牛頓公式進(jìn)行迭代。151*1()( ) (0121kkkkkpkxxxxxexxkeccepppp 定義：設(shè)迭代過(guò)程收斂于方程的根,如果迭代誤差當(dāng)時(shí)成立下列漸進(jìn)關(guān)系式為常數(shù)）則稱(chēng)該迭代過(guò)程是 階收斂的。為線性收斂，為超線性為平收斂，方收斂。16

7、1()*(1)*()* (),( )()()()0;() 0 kkpppxxxxxxxxxp定理：對(duì)于迭代過(guò)程如果在所求根 的鄰近連續(xù)，并且則該迭代過(guò)程在點(diǎn) 鄰近是 階收斂的。17*1*( )*( )( )*11()0 1,()()( ) ()()()!( )()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep 證：由于故具有局部收斂性,將在根 處展開(kāi)，由條件有18 12* () ,()0,() ()() () ()()() () ()()(kkkkxxa bxfxxxfxfxxxfxfxfxxfxxfxfx迭 代 過(guò) 程 的 收 斂 速 度 依 賴 于 迭 代 函

8、數(shù)的 選取 。 如 果 當(dāng)時(shí)則 該 迭 代 過(guò) 程 只可 能 是 線 性 收 斂 。 對(duì) 牛 頓 公 式其 迭 代 函 數(shù) 為由 于假 定是的 一 個(gè) 單 根 ， 即*)0,()0,()0,fxxx則由 上 式 知由 上 述 定 理 知 ， 牛 頓 法 在 根的鄰 近 至 少 是 平 方 收 斂 的 。1921 01 ().2kkkcxcccxxx對(duì)于給定正數(shù)，應(yīng)用牛頓法解二次方程即導(dǎo)出求開(kāi)方值的計(jì)算程序02211221010202000 11 () ()22. ,2.1 0,1. kkkkkkkkkkkkkkkkkxxcxcxcxcxxxcxcxcxcxcxcxcxcxcqqxccxcqxq

9、kxc 現(xiàn)證此迭代公式對(duì)于初值都是收斂的。由迭代公式得記對(duì)任意總有，故當(dāng)時(shí)，20newton法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點(diǎn)，法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點(diǎn)，是求解非線性方程的有效方法之一。但它每次迭代均需是求解非線性方程的有效方法之一。但它每次迭代均需計(jì)算函數(shù)值與導(dǎo)數(shù)值，故計(jì)算量較大。而且當(dāng)導(dǎo)數(shù)值提計(jì)算函數(shù)值與導(dǎo)數(shù)值，故計(jì)算量較大。而且當(dāng)導(dǎo)數(shù)值提供有困難時(shí)，供有困難時(shí)， newton法無(wú)法進(jìn)行。法無(wú)法進(jìn)行。21（1）選取初始近似值）選取初始近似值x0；（2）取下山因子）取下山因子 = 1；)( )(1kkkkxfxfxx（3）計(jì)算）計(jì)算)(1kxf)(kxf（4）計(jì)算）計(jì)算f (x

10、k+1)，并比較，并比較 與與 的大小，分以下二種情況的大小，分以下二種情況11)(kxf否則若否則若 ，而，而 時(shí)，則把時(shí)，則把xk+1加上一個(gè)適當(dāng)選定的小正數(shù)，加上一個(gè)適當(dāng)選定的小正數(shù)，11)(kxf即取即取xk+1+ 作為新的作為新的xk值，并轉(zhuǎn)向（值，并轉(zhuǎn)向（3）重復(fù)計(jì)算；當(dāng)）重復(fù)計(jì)算；當(dāng) ；且；且 ，則將下山因子縮小一半，取則將下山因子縮小一半，取 /2代入，并轉(zhuǎn)向（代入，并轉(zhuǎn)向（3）重復(fù)計(jì)算。）重復(fù)計(jì)算。 牛頓下山法計(jì)算步驟可歸納如下：牛頓下山法計(jì)算步驟可歸納如下：)() 1kkxfxf21kkxx21kkxx1）若）若 ，則當(dāng)，則當(dāng) 時(shí)，取時(shí)，取x* xk+1，計(jì)算過(guò)程結(jié)束；，計(jì)

11、算過(guò)程結(jié)束； 當(dāng)當(dāng) 時(shí)，則把時(shí)，則把xk+1作為新的作為新的xk值，并重復(fù)回到（值，并重復(fù)回到（3）。）。)()1kkxfxf 2）若）若 ，則當(dāng)，則當(dāng) 且，取且，取x* xk，計(jì)算過(guò)程結(jié)束；，計(jì)算過(guò)程結(jié)束；22例例5 5：求方程：求方程 的根的根k xk010.611/251.14063211.36681311.32628411.32472牛頓下山法的計(jì)算結(jié)果：牛頓下山法的計(jì)算結(jié)果：2311111 (),(),() ,( )0(),(),(),( ),( )0( )0 kkkkkk rkkk rrrkkf xf xfxxxxf xf xf xf xp xp xf xxx基本思想：利用一些函數(shù)

12、值來(lái)回避導(dǎo)數(shù)值的計(jì)算。設(shè)是的一組近似根，利用函數(shù)值構(gòu)造插值多項(xiàng)式并適當(dāng)選取的一個(gè)根作為的新的近似根，這就確定了一個(gè)迭代過(guò)程，記迭代函數(shù)為 ：1(,). 12kkk rxxxrr當(dāng)時(shí)為弦截法，當(dāng)時(shí)為拋物線法。24111111111111 ,( )0(),()( )( )0( )0.()() ( )()()() ().()()()kkkkkkkkkkkkkkkkkkkkkxxf xf xf xpxpxf xxf xf xpxf xxxxxf xxxxxf xf xf xxxf設(shè)是的近似根，利用構(gòu)造一次插值多項(xiàng)式，并用的根作為的新的近似根由此迭代公式可看作牛頓公式11()()()( )kkkkkxf

13、 xf xfxxx中的導(dǎo)數(shù)用差商取代的結(jié)果。25)(kxf 0011)()()()(xxxfxfxxxfxfkkkkkk或則得雙點(diǎn)或單點(diǎn)弦割法迭代格式則得雙點(diǎn)或單點(diǎn)弦割法迭代格式)()()(111kkkkkkkxfxfxxxfxx 在牛頓迭代格式中，將曲線在牛頓迭代格式中，將曲線 上點(diǎn)上點(diǎn) 的切線斜率的切線斜率 ，改為其上兩點(diǎn)連線，改為其上兩點(diǎn)連線(弦弦)的斜率的斜率( )yf x(,()kkxf x26x0xx1 x2 x3y f(x)0p0p2 p1x11011 ,.,kkkkkxxxxxxx弦 截 法 在 求時(shí) 要 用 到 前 面 兩 步 的 結(jié) 果需 兩 個(gè) 初 值， 而 牛 頓 切 線 法 在 計(jì) 算時(shí) ， 只用 到 前 一 步的 值 。27x0 x1切線切線 割線割線 切線斜率切線斜率 割線斜率割線斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx228切線斜率切線斜率 割線斜率割線斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfx