計(jì)算方法Chapter04-方程求根的數(shù)值解法

1、四方程求根2方程求根方程求根方程求根概述方程求根概述根的隔離根的隔離二分法二分法迭代法的基本概念迭代法的基本概念迭代過(guò)程的收斂性迭代過(guò)程的收斂性迭代法的收斂速度及加速處理迭代法的收斂速度及加速處理牛頓迭代公式牛頓迭代公式牛頓迭代法的收斂性及收斂速度牛頓迭代法的收斂性及收斂速度牛頓迭代法的初值選取牛頓迭代法的初值選取3引言引言( )0f x 科研工作或生產(chǎn)實(shí)踐中遇到的數(shù)學(xué)問(wèn)題，常常需科研工作或生產(chǎn)實(shí)踐中遇到的數(shù)學(xué)問(wèn)題，常常需要求解一元（單個(gè)變量）的方程（或方程組）要求解一元（單個(gè)變量）的方程（或方程組）當(dāng)當(dāng) f (x) 為一般連續(xù)函數(shù)時(shí)，稱(chēng)上式為超越方程為一般連續(xù)函數(shù)時(shí)，稱(chēng)上式為超越方程若若 f

2、 (x) 不是不是 x 的線性函數(shù)，則稱(chēng)上式為非線性方程的線性函數(shù)，則稱(chēng)上式為非線性方程特別地，如果特別地，如果 f (x) 為某個(gè)為某個(gè) n 次多項(xiàng)式次多項(xiàng)式 pn(x)，稱(chēng)上式，稱(chēng)上式 n 次多項(xiàng)式方程或代數(shù)方程次多項(xiàng)式方程或代數(shù)方程方程的根方程的根 x* 又稱(chēng)又稱(chēng) f (x) 的零點(diǎn)，它可以是實(shí)數(shù)，也可的零點(diǎn)，它可以是實(shí)數(shù)，也可以是復(fù)數(shù)，我們主要學(xué)習(xí)實(shí)根的求法以是復(fù)數(shù)，我們主要學(xué)習(xí)實(shí)根的求法4引言引言理論上已證明，對(duì)于次數(shù)理論上已證明，對(duì)于次數(shù) 5 的多項(xiàng)式方程，它的的多項(xiàng)式方程，它的根一般不能用解析表達(dá)式表示，需要借助群論的相根一般不能用解析表達(dá)式表示，需要借助群論的相關(guān)知識(shí)解決；關(guān)知

3、識(shí)解決；對(duì)于次數(shù)對(duì)于次數(shù) n 4 的多項(xiàng)式方程，它的根可以用公式表的多項(xiàng)式方程，它的根可以用公式表示，但是對(duì)于示，但是對(duì)于 n 3, 4，其根的表達(dá)形式非常復(fù)雜，其根的表達(dá)形式非常復(fù)雜可見(jiàn)：對(duì)于一般的可見(jiàn)：對(duì)于一般的 f (x) 0 的方程，不存在根的解析的方程，不存在根的解析表達(dá)式表達(dá)式實(shí)際應(yīng)用中，也不一定必須得到方程根的解析表達(dá)實(shí)際應(yīng)用中，也不一定必須得到方程根的解析表達(dá)式，只要得到滿(mǎn)足一定精度要求的根的近似值就可式，只要得到滿(mǎn)足一定精度要求的根的近似值就可以了以了5方程求根問(wèn)題方程求根問(wèn)題根的存在性：方程有沒(méi)有根？如果有根，有幾個(gè)根？根的存在性：方程有沒(méi)有根？如果有根，有幾個(gè)根？哪兒有根

4、：求出有根的大致區(qū)間，即將哪兒有根：求出有根的大致區(qū)間，即將 x 的取值范的取值范圍劃分為若干個(gè)小區(qū)間，使得每個(gè)區(qū)間或是沒(méi)有根，圍劃分為若干個(gè)小區(qū)間，使得每個(gè)區(qū)間或是沒(méi)有根，或是只有一個(gè)根或是只有一個(gè)根根的精確化：上述有根區(qū)間內(nèi)的任一點(diǎn)均可看作方根的精確化：上述有根區(qū)間內(nèi)的任一點(diǎn)均可看作方程根的較為粗略的近似值，在此基礎(chǔ)上設(shè)法逐步把程根的較為粗略的近似值，在此基礎(chǔ)上設(shè)法逐步把根精確化，直到滿(mǎn)足精度要求為止根精確化，直到滿(mǎn)足精度要求為止迭代法迭代法6根的隔離根的隔離零點(diǎn)定理零點(diǎn)定理 若若 f (x) 在在 a, b 上連續(xù)，且上連續(xù)，且 f (a) f (b) 0，則方，則方程程 f (x) 0

5、 在區(qū)間在區(qū)間 a, b 上上至少至少有一個(gè)根。有一個(gè)根。區(qū)間區(qū)間 a, b 內(nèi)如果有且僅有一個(gè)根，則稱(chēng)該區(qū)間為內(nèi)如果有且僅有一個(gè)根，則稱(chēng)該區(qū)間為有根區(qū)間。通?？捎弥鸫嗡阉鞣ㄇ笥懈鶇^(qū)間。通?？捎弥鸫嗡阉鞣ㄇ?f (x) 0 的有根區(qū)的有根區(qū)間間yabxyabx*x*x7逐次搜索法逐次搜索法 在在 x 的不同取值點(diǎn)上計(jì)算的不同取值點(diǎn)上計(jì)算 f (x)，觀察，觀察 f (x) 的符號(hào)，的符號(hào)，只要在充分接近的相鄰兩點(diǎn)函數(shù)值只要在充分接近的相鄰兩點(diǎn)函數(shù)值 f (x) 反號(hào)，則以該反號(hào)，則以該兩點(diǎn)為端點(diǎn)的區(qū)間必然是有根區(qū)間兩點(diǎn)為端點(diǎn)的區(qū)間必然是有根區(qū)間例例：求方程：求方程 的有的有根區(qū)間根區(qū)間.32(

6、 )11.138.841.770f xxxx 解：解：取步長(zhǎng)為取步長(zhǎng)為 1 對(duì)方程的根進(jìn)行搜索，結(jié)果如下：對(duì)方程的根進(jìn)行搜索，結(jié)果如下：x0123456f (x) 符號(hào)符號(hào) 因此方程因此方程 三個(gè)有根區(qū)間，分別為三個(gè)有根區(qū)間，分別為 ：1, 2、3, 4、 5, 68二分法二分法逐步將較大的有根區(qū)間進(jìn)行二分，通過(guò)判斷分割點(diǎn)逐步將較大的有根區(qū)間進(jìn)行二分，通過(guò)判斷分割點(diǎn)處的函數(shù)值的符號(hào)，將原來(lái)較大的有根區(qū)間不斷折處的函數(shù)值的符號(hào)，將原來(lái)較大的有根區(qū)間不斷折半縮小，直至有根區(qū)間縮小到容許的誤差范圍內(nèi)半縮小，直至有根區(qū)間縮小到容許的誤差范圍內(nèi)取一系列二分后，最后得到的有根區(qū)間的取一系列二分后，最后得到

7、的有根區(qū)間的中點(diǎn)中點(diǎn)作為作為方程根的近似值。方程根的近似值。9二分法（續(xù)）二分法（續(xù)）假設(shè)已找到假設(shè)已找到 f (x) 的較為粗略的有根區(qū)間的較為粗略的有根區(qū)間 a0, b0，并且并且 f (x) 在在 a0, b0 上連續(xù)上連續(xù)取中點(diǎn)取中點(diǎn) 將區(qū)間將區(qū)間 a0, b0 分成兩半，檢分成兩半，檢查查 f (x0) 與與 f (a0) 是否同號(hào)？是否同號(hào)？000() 2xab同號(hào)：說(shuō)明根同號(hào)：說(shuō)明根 x* 仍在仍在 x0 的右側(cè)，取的右側(cè)，取 a1 x0 , b1 b0得到只有原有根區(qū)間一半寬度的新有根區(qū)間得到只有原有根區(qū)間一半寬度的新有根區(qū)間 a1, b1異號(hào)：說(shuō)明根異號(hào)：說(shuō)明根 x* 仍在仍

8、在 x0 的左側(cè)，取的左側(cè)，取 a1 a0 , b1 x0 得到只有原有根區(qū)間一半寬度的新有根區(qū)間得到只有原有根區(qū)間一半寬度的新有根區(qū)間 a1, b1重復(fù)上述過(guò)程，取重復(fù)上述過(guò)程，取 將區(qū)間將區(qū)間 a1, b1 分分半，確定根半，確定根 x* 在在 x1 的哪一側(cè)，得到新區(qū)間的哪一側(cè)，得到新區(qū)間 a2, b2111() 2xab 10二分法（續(xù)）二分法（續(xù)）0a0b0a0b1b1a2a2b3a3byx( )yf x*x0 x1x2x3x11二分法（續(xù)）二分法（續(xù)）這樣便可以得到一系列有根區(qū)間：這樣便可以得到一系列有根區(qū)間：001122,nna ba ba bab 其中每一個(gè)區(qū)間的寬度都是前一個(gè)

9、區(qū)間的寬度的一其中每一個(gè)區(qū)間的寬度都是前一個(gè)區(qū)間的寬度的一半，因此半，因此 ：1122002111()()()222nnnnnnnbabababa 012,nxxxx取每個(gè)有根區(qū)間的中點(diǎn)取每個(gè)有根區(qū)間的中點(diǎn) 作為作為 x* 的近的近似值，則在二分過(guò)程中，可以得到一系列精度越來(lái)似值，則在二分過(guò)程中，可以得到一系列精度越來(lái)越高的方程根的近似值序列：越高的方程根的近似值序列：() 2iiixab12對(duì)于有限次二分后得到的對(duì)于有限次二分后得到的 xn，它是準(zhǔn)確根，它是準(zhǔn)確根 x* 的近似的近似值，且它的絕對(duì)誤差的絕對(duì)值為：值，且它的絕對(duì)誤差的絕對(duì)值為：1100*21222nnnnnnbababaxx

10、如果給定了某個(gè)精度要求如果給定了某個(gè)精度要求 e e，則二分法的二分過(guò)程一，則二分法的二分過(guò)程一直要持續(xù)到新的有根區(qū)間寬度的一半不大于直要持續(xù)到新的有根區(qū)間寬度的一半不大于 e e*limlim2nnnnnabxx 顯然，當(dāng)顯然，當(dāng) n 時(shí)，必然有：時(shí)，必然有：1122002111()()()222nnnnnnnbabababa 13二分法的特點(diǎn)二分法的特點(diǎn)二分法計(jì)算過(guò)程簡(jiǎn)單，程序容易實(shí)現(xiàn)，可以在大范二分法計(jì)算過(guò)程簡(jiǎn)單，程序容易實(shí)現(xiàn)，可以在大范圍內(nèi)求根圍內(nèi)求根二分法收斂較慢，其收斂速度僅與一個(gè)以二分法收斂較慢，其收斂速度僅與一個(gè)以 1/2 為比為比值的等比級(jí)數(shù)相同值的等比級(jí)數(shù)相同二分法不能求解

11、偶數(shù)重根和復(fù)根二分法不能求解偶數(shù)重根和復(fù)根二分法一般用于求根的初始近似值，然后再使用其二分法一般用于求根的初始近似值，然后再使用其它的求根方法對(duì)根精確化它的求根方法對(duì)根精確化14例例求方程求方程 f (x) x3 e x 0 的一個(gè)實(shí)根，要求精確到的一個(gè)實(shí)根，要求精確到小數(shù)點(diǎn)后第小數(shù)點(diǎn)后第 3 位。位。解解：因?yàn)椋阂驗(yàn)?f (0) 0。 故故 f (x) 在在 (0, 1) 區(qū)間內(nèi)區(qū)間內(nèi)有根，由精度要求可知：有根，由精度要求可知：3*111()1022nnxxba 所以需要將區(qū)間所以需要將區(qū)間 (0, 1) 二分二分 10 次才能找到滿(mǎn)足精次才能找到滿(mǎn)足精度要求的近似根。各次計(jì)算結(jié)果見(jiàn)下表度要

12、求的近似根。各次計(jì)算結(jié)果見(jiàn)下表 即：即：3210n 9.968n 15例例nanbnxnf (xn) 符號(hào)符號(hào)00.0000-1.0000 +0.5000-10.5000-1.0000 +0.7500-20.7500-1.0000 +0.8750+30.7500-0.8750 +0.8125+40.7500-0.8125 +0.7812+50.7500-0.7812 +0.7656-60.7656-0.7812 +0.7734+70.7656-0.7734 +0.7695-80.7695-0.7734 +0.7714-90.7714-0.7734 +0.7724-100.7724-0.7734

13、 +0.7729+16迭代法迭代法1()0,1,2,nnxxn 當(dāng)給定初值當(dāng)給定初值 x0 后，由迭代格式可求得一系列準(zhǔn)確根后，由迭代格式可求得一系列準(zhǔn)確根的近似值，組成迭代序列的近似值，組成迭代序列 xn。由方程由方程 f (x) 0 變換為變換為 x (x)，然后建立迭代格式，然后建立迭代格式*x*()xx *x迭代法又稱(chēng)逐次迭代法，其基本思想是構(gòu)造不動(dòng)點(diǎn)迭代法又稱(chēng)逐次迭代法，其基本思想是構(gòu)造不動(dòng)點(diǎn)方程，以求得近似根（如果方程，以求得近似根（如果 滿(mǎn)足滿(mǎn)足 ，則稱(chēng)，則稱(chēng) 為為 (x) 的不動(dòng)點(diǎn)）的不動(dòng)點(diǎn)） 17迭代法（續(xù)）迭代法（續(xù)）如果迭代序列如果迭代序列 xn 收斂于收斂于 A，則，則

14、 A 是方程的準(zhǔn)確根：是方程的準(zhǔn)確根：1limnnAx 針對(duì)某個(gè)方程針對(duì)某個(gè)方程 f (x) 0，可以構(gòu)造出不同的迭代公式，可以構(gòu)造出不同的迭代公式，只有滿(mǎn)足一定條件的迭代公式才收斂。只有滿(mǎn)足一定條件的迭代公式才收斂。lim ()nnx (lim)nnx ( )A 如何構(gòu)造不動(dòng)點(diǎn)方程，由如何構(gòu)造不動(dòng)點(diǎn)方程，由 f (x) 0 變換為變換為 x (x) ？如何選擇合適的初值如何選擇合適的初值 x0 ？n 時(shí)，時(shí)，迭代產(chǎn)生的序列迭代產(chǎn)生的序列 xn 是否收斂到是否收斂到 x* ？如果迭代序列如果迭代序列 xn 收斂，則有限次迭代得到的近似收斂，則有限次迭代得到的近似根的誤差如何估計(jì)？根的誤差如何估

15、計(jì)？18若若 x a, b 時(shí)，時(shí)， (x) a, b存在某個(gè)小于存在某個(gè)小于 1 的正數(shù)的正數(shù) L，使得，使得 x a, b，有：，有：迭代過(guò)程的收斂定理迭代過(guò)程的收斂定理( )1xL 設(shè)迭代函數(shù)設(shè)迭代函數(shù) (x) 在區(qū)間在區(qū)間 a, b 上具有連續(xù)的一階上具有連續(xù)的一階導(dǎo)數(shù)，并且：導(dǎo)數(shù)，并且：則迭代方程則迭代方程 x (x) 在區(qū)間在區(qū)間 a, b 上上有且僅有一個(gè)有且僅有一個(gè)根根 x*，并且對(duì)，并且對(duì)任意選取的初始值任意選取的初始值 x0 a, b，迭代過(guò)程，迭代過(guò)程生成的序列生成的序列 xn 收斂，且：收斂，且：*limnnxx 19( ) , ( )1xa bxL 在在區(qū)區(qū)間間上上連

16、連續(xù)續(xù)，且且 , ( ) , xa bxa b 且且( )( )g xxx 設(shè)設(shè)( )( )0g aaa ( )( )0g bbb 連續(xù)，故連續(xù)，故 連續(xù)連續(xù)( )x ( )g x由零點(diǎn)定理知，必存在零點(diǎn)由零點(diǎn)定理知，必存在零點(diǎn) 使得使得 ，* , xa b *()0g x 存在性存在性：*()()( )()xxxxxx 唯一性唯一性：*()0 xx *()xx 即：即：假設(shè)存在另外一點(diǎn)假設(shè)存在另外一點(diǎn) 也滿(mǎn)足也滿(mǎn)足* , xa b *()xx *1( ) ()0 xx 或或*,xx *,xx0 *xx 0 20( ) , ( )1xa bxL 在在區(qū)區(qū)間間上上連連續(xù)續(xù)，且且 , ( ) ,

17、xa bxa b 且且由微分中值定理可知：由微分中值定理可知：收斂性收斂性：*11()()( )()nnnxxxxxx 即：即：*1( )nnxxxx *1nL xx 2*2nL xx *0nL xx *0limlim0nnnnxxL xx *limnnxx *1,nxx *1,nxx 或或21迭代過(guò)程的誤差估計(jì)迭代過(guò)程的誤差估計(jì)*1*1011nnnnnLxxxxLLxxxxL 則有誤差估計(jì)式：則有誤差估計(jì)式：設(shè)迭代函數(shù)設(shè)迭代函數(shù) (x) 在區(qū)間在區(qū)間 a, b 上具有連續(xù)的一階上具有連續(xù)的一階導(dǎo)數(shù)，并且：導(dǎo)數(shù)，并且：若若 x a, b 時(shí)，時(shí)， (x) a, b存在某個(gè)小于存在某個(gè)小于 1

18、的正數(shù)的正數(shù) L，使得，使得 x a, b，有：，有：( )1xL 1,2,3,n 22*11nnnLxxxxL *101nnLxxxxL *11()()nnnnxxxxxx 111()()( ) ()nnnnnnxxxxxx *111nnnxxxxL 1*1nnnxLxxxL *101nnLxxLxx |ababab |ba 或或*1nnxxxx *nnxxL xx *(1)nL xx1nnLxx 212nnLxx 10nLxx 23因此只要兩次相鄰的迭代值相差足夠小，就可以因此只要兩次相鄰的迭代值相差足夠小，就可以保證最后一次迭代得到的近似值保證最后一次迭代得到的近似值 xn 足夠精確足夠

19、精確L 較大時(shí)較大時(shí)不適用不適用可以用可以用 大致估計(jì)需要進(jìn)大致估計(jì)需要進(jìn)行迭代的次數(shù)行迭代的次數(shù) n*101nnLxxxxLe e 1nnxxe e 迭代終止條件：迭代終止條件：*11nnnLxxxxL *101nnLxxxxL 11LL 12L 即：即：*111nnnnnLxxxxxxLe e ( )1xL 24迭代法的基本步驟迭代法的基本步驟檢查檢查 | x1 x0 | e e，如成立，則迭代終止，方程的近，如成立，則迭代終止，方程的近似根為似根為 x1；如不成立，則將；如不成立，則將 x1 代入代入迭代方程迭代方程，重復(fù)，重復(fù)以上迭代、檢查的步驟以上迭代、檢查的步驟如果迭代次數(shù)超過(guò)預(yù)先

20、指定的次數(shù)如果迭代次數(shù)超過(guò)預(yù)先指定的次數(shù) N 后，仍然后，仍然不能滿(mǎn)足精度要求，則終止迭代，所構(gòu)造的迭代函不能滿(mǎn)足精度要求，則終止迭代，所構(gòu)造的迭代函數(shù)數(shù) (x) 發(fā)散發(fā)散將將 x0 代入代入迭代方程迭代方程，計(jì)算，計(jì)算10()xx 選定初始近似值選定初始近似值 x0，確定，確定 f (x) 0 0 的等價(jià)的等價(jià)形式形式 x (x)，構(gòu)造迭代方程，構(gòu)造迭代方程1()nnxx 25局部收斂性局部收斂性*()1x 定義定義：如果在準(zhǔn)確根：如果在準(zhǔn)確根 x* 的某個(gè)鄰域的某個(gè)鄰域 內(nèi)，內(nèi)， 迭代過(guò)程對(duì)于任意選定的初值迭代過(guò)程對(duì)于任意選定的初值 均收斂，則均收斂，則 稱(chēng)這種在根的鄰近所具有的收斂性為稱(chēng)

21、這種在根的鄰近所具有的收斂性為局部收斂局部收斂 性性。*|xx ：0 x 定理定理：設(shè)迭代函數(shù)：設(shè)迭代函數(shù) (x) 在準(zhǔn)確根在準(zhǔn)確根 x* 鄰近有連續(xù)的一鄰近有連續(xù)的一 階導(dǎo)數(shù)，且：階導(dǎo)數(shù)，且：則迭代過(guò)程則迭代過(guò)程 具有局部收斂性。具有局部收斂性。1()nnxx 26迭代法的幾何意義迭代法的幾何意義xyx0p0p1p2Q2Q1p*x*x2x1yx ( )yx 27迭代法的幾何意義（續(xù)）迭代法的幾何意義（續(xù)）xyyx ( )yx x0p0p*28例例3152nnxx 2312212max( )133(522)xx = =故迭代過(guò)程必收斂。故迭代過(guò)程必收斂。用迭代法求用迭代法求 在區(qū)間在區(qū)間 1,

22、 2 內(nèi)的近似根，內(nèi)的近似根，結(jié)果保留結(jié)果保留 5 位小數(shù)位小數(shù)3250 xx 解解：將方程改寫(xiě)成：將方程改寫(xiě)成： ，并作迭代方程：，并作迭代方程：352xx22331221( )33(52 )(52 )xxx = =因?yàn)椋阂驗(yàn)椋?9例例取取 ，通過(guò)迭代可得：，通過(guò)迭代可得：01x 11.44224x 21.28472x 31.34489x 41.32195x 51.33064x 61.32763x 71.32860 x 81.32814x 91.32831x 101.32825x 111.32827x 121.32826x 131.32826x 30構(gòu)造不同的迭代法求：構(gòu)造不同的迭代法求：

23、的根的根 230 x *3x 解解：(1) ，迭代方程為，迭代方程為3( )xx 13nnxx *23( ),()1xxx (2) ，迭代方程為，迭代方程為23( )4xxx 2134nnnxxx *3( )1,()10.134122xxx (3) ，迭代方程為，迭代方程為13( )2xxx 1132nnnxxx *213( )1,()012xxx31若取若取 x0 2.0 2.0，分別用上述三種迭代方法計(jì)算，分別用上述三種迭代方法計(jì)算，結(jié)果見(jiàn)下表（準(zhǔn)確根結(jié)果見(jiàn)下表（準(zhǔn)確根 x* 1.73205080757）1.7320508212.0 x881.7320509071.5x771.732051

24、5532.0 x661.7320563691.5x551.7320508081.7320923202.0 x441.7320508101.732360840 1.5x331.732142857 1.734375000 2.0 x221.751.751.5x112.02.02.0 x00 xnn13nnxx 2134nnnxxx 1132nnnxxx 32迭代過(guò)程的收斂速度迭代過(guò)程的收斂速度如果存在某個(gè)實(shí)數(shù)如果存在某個(gè)實(shí)數(shù) p 和正常數(shù)和正常數(shù) C，使得：，使得：定義：定義：設(shè)序列設(shè)序列 xn 是收斂于是收斂于 f (x) 0 的準(zhǔn)確根的準(zhǔn)確根 x* 的迭的迭代序列，記各步的迭代誤差為代序列，記

25、各步的迭代誤差為 e en xn x*,1limnpnnCe ee e 則稱(chēng)序列則稱(chēng)序列 xn 是是 p 階收斂的。階收斂的。漸近誤差常數(shù)漸近誤差常數(shù) p 1, 0 C 1 時(shí)，序列時(shí)，序列 xn 是線性收斂是線性收斂C 0 時(shí)，序列時(shí)，序列 xn 是超是超 p 階收斂階收斂1 p 2 時(shí)，序列時(shí)，序列 xn 是超線性收斂是超線性收斂p 2 時(shí)，序列時(shí)，序列 xn 是平方收斂是平方收斂p 越大，收斂越快越大，收斂越快33迭代過(guò)程的收斂速度（續(xù)）迭代過(guò)程的收斂速度（續(xù)）定理：定理：對(duì)于迭代過(guò)程對(duì)于迭代過(guò)程 xn 1 (xn)，如果迭代函數(shù)，如果迭代函數(shù) (x)在準(zhǔn)確根在準(zhǔn)確根 x* 的鄰近有連續(xù)

26、的二階導(dǎo)數(shù)，且：的鄰近有連續(xù)的二階導(dǎo)數(shù)，且：*()1x 則有：則有：當(dāng)當(dāng) 而而 時(shí)，迭代過(guò)程為平方時(shí)，迭代過(guò)程為平方收斂收斂*()0 x *()0 x 當(dāng)當(dāng) 時(shí)，迭代過(guò)程為線性收斂時(shí)，迭代過(guò)程為線性收斂*()0 x *(1)*()0,()0,()0pxxx 當(dāng)當(dāng) 而而 時(shí)，迭代過(guò)程為時(shí)，迭代過(guò)程為 p 階收斂階收斂()*()0px 34如果迭代函數(shù)如果迭代函數(shù) ( (x) ) 收斂，在收斂，在 x * 的某個(gè)鄰域的某個(gè)鄰域 內(nèi)有內(nèi)有 ( (x) 1) 1，當(dāng)有根區(qū)間較小或，當(dāng)有根區(qū)間較小或 ( (x) ) 在在 內(nèi)內(nèi)變化較平緩變化較平緩時(shí)，可近似將時(shí)，可近似將 ( (x) ) 取某個(gè)定值取某個(gè)

27、定值 a。迭代過(guò)程的加速迭代過(guò)程的加速設(shè)迭代方程設(shè)迭代方程 x ( (x) ) 的準(zhǔn)確根為的準(zhǔn)確根為 x *，由微分中值，由微分中值定理可知：定理可知：*1()nnxxa xx *1111nnaxxxaa *11()1nnnaxxxxa xn 1 的大致誤差，可的大致誤差，可以在以在 xn 1 的基礎(chǔ)上疊的基礎(chǔ)上疊加上這個(gè)誤差，從而加上這個(gè)誤差，從而得到比得到比 xn 1 本身更精本身更精確的近似值確的近似值*1()()( )()nnnxxxxxx 35經(jīng)過(guò)加速處理后，迭代過(guò)程為：經(jīng)過(guò)加速處理后，迭代過(guò)程為：迭代終止條件仍為：迭代終止條件仍為：1nnxxe e 迭代迭代：1()nnxx 111

28、()1nnnnaxxxxa 加速加速：*11()1nnnaxxxxa a 的確定需要求解迭的確定需要求解迭代函數(shù)的導(dǎo)函數(shù)代函數(shù)的導(dǎo)函數(shù) ( (x) )不便不便之處之處36埃特金（埃特金（Atiken）加速）加速(1)1()nnxx ( () )(2)(1)11nnxx ( () )*(2)*(1)11nnxxa xx *(1)*1()nnxxa xx *(1)*1*(2)*(1)11nnnnxxxxxxxx 所以：所以：( () )( () )( () )2*(1)*(2)11nnnxxxxxx 展開(kāi)得：展開(kāi)得：( () )( () )( () )( () )22*(1)*(1)112*(2)

29、*(2)112nnnnnnxxxxxxxxx x即：即：37( () )( () )( () )( () )222*(1)*(1)*(2)*(2)11112nnnnnnxxxxxxxxx x ( () )2(2)(1)11(2)1(2)(1)112nnnnnnxxxxxx ( () )( () )( () )222(2)(1)(2)(2)(2)(2)(1)(1)11111111(2)(1)11222nnnnnnnnnnnnxxxx xxxxxxxx ( () )2(2)(1)11*(2)(1)112nnnnnnx xxxxxx ( () ) ( () )2(2)(2)(1)(2)(1)1111

30、1(2)(1)1122nnnnnnnnnxxxxxxxxx 38埃特金（埃特金（Atiken）加速（續(xù)）加速（續(xù)）加速公式中不再含有與加速公式中不再含有與 ( (x) ) 相關(guān)的系數(shù)相關(guān)的系數(shù) a需要兩次迭代再能得到下一步的近似值需要兩次迭代再能得到下一步的近似值某些發(fā)散的迭代公式經(jīng)埃特金法加速處理后，能夠某些發(fā)散的迭代公式經(jīng)埃特金法加速處理后，能夠獲得較好的收斂性獲得較好的收斂性?xún)纱蔚鷥纱蔚旱?1)1()nnxx 迭代：迭代：( () )(2)(1)11nnxx 加速：加速：( () )2(2)(1)11(2)11(2)(1)112nnnnnnnxxxxxxx 39牛頓法牛頓法

31、假設(shè)已知假設(shè)已知 f (x) 0 的某個(gè)初始近似根為的某個(gè)初始近似根為 x0，且在，且在 x0 的一個(gè)適當(dāng)小的鄰域內(nèi)的一個(gè)適當(dāng)小的鄰域內(nèi) f (x) 可微，將可微，將 f (x) 在點(diǎn)在點(diǎn) x0 附附近用泰勒公式展開(kāi)：近用泰勒公式展開(kāi)：200000()( )()()()()2!fxf xf xfxxxxx 如果僅取上述泰勒展開(kāi)式的前兩項(xiàng)，忽略如果僅取上述泰勒展開(kāi)式的前兩項(xiàng)，忽略 (x x0)2及其后的各項(xiàng)，則可以得到及其后的各項(xiàng)，則可以得到 f (x) 在在 x0 附近的近似線性附近的近似線性展開(kāi)式：展開(kāi)式：000( )()()()f xf xfxxx 000()()()0f xfxxx (

32、)0f x 40假設(shè)假設(shè) f (x0) 0，則上式的解為：，則上式的解為：如果將上面公式求得的如果將上面公式求得的 x 作為原方程的一個(gè)新的作為原方程的一個(gè)新的近似根近似根 x1，將，將 f (x) 在在 x1 附近作近似線性展開(kāi)，可求得附近作近似線性展開(kāi)，可求得另一個(gè)新的近似根另一個(gè)新的近似根 x2 。如此重復(fù)上述過(guò)程，可得到一。如此重復(fù)上述過(guò)程，可得到一般的迭代公式：般的迭代公式：000()()f xxxfx 1()()nnnnf xxxfx 這種迭代方法稱(chēng)為這種迭代方法稱(chēng)為牛頓法牛頓法牛頓迭代公式牛頓迭代公式000()()()0f xfxxx 41顯然，牛頓法對(duì)應(yīng)的方程為：顯然，牛頓法對(duì)

33、應(yīng)的方程為：( )( )f xxxfx 牛頓法的迭代函數(shù)為：牛頓法的迭代函數(shù)為：( )( )( )f xxxfx 如果如果 x* 是方程是方程 f (x) 0 的一個(gè)單根，即：的一個(gè)單根，即：1()()nnnnf xxxfx 其中：其中：( )0fx 22( )( )( )( )( )( )( )1( )( )fxfxf x fxf x fxxfxfx 由于：由于：*()0f x 而而*()0fx 則則 ，因此，因此 的鄰近迭代過(guò)程具有局部收斂性的鄰近迭代過(guò)程具有局部收斂性*()0 x *x42牛頓法的幾何意義牛頓法的幾何意義xy0 x1x2x3x*x( )yf x 0牛頓法又叫切線法牛頓法又

34、叫切線法000()()()yf xfxxx 111()()()yf xfxxx 43牛頓法的計(jì)算步驟牛頓法的計(jì)算步驟選擇合適的初始近似根選擇合適的初始近似根 x0，計(jì)算，計(jì)算 f (x0) 和和 f (x0)將將 x0 代入迭代公式：代入迭代公式：求得一個(gè)新的近似根求得一個(gè)新的近似根 x1，并計(jì)算，并計(jì)算 f (x1) 和和 f (x1)1()()nnnnf xxxfx 求得達(dá)到精度要求的近似根求得達(dá)到精度要求的近似根超過(guò)預(yù)定的迭代次數(shù)超過(guò)預(yù)定的迭代次數(shù) N 后仍未達(dá)到精度要求后仍未達(dá)到精度要求迭代過(guò)程中存在迭代過(guò)程中存在 f (xk) 0，此時(shí)應(yīng)終止迭代，此時(shí)應(yīng)終止迭代檢查檢查 | x1 x

35、0 | e e 且且 f (x1) 0，如成立，則迭代終如成立，則迭代終止，方程的近似根止，方程的近似根 x1；如不成立，則將；如不成立，則將 x1 代入代入迭代迭代方程方程，重復(fù)前述步驟，重復(fù)前述步驟44223( )( )( )( )2 ( )( )( )( )( )( )( )fx fxf x fxf x fxxfxfxfxfx 牛頓法的收斂速度牛頓法的收斂速度設(shè)設(shè) x*是是 f (x) 0 的一個(gè)準(zhǔn)確的一個(gè)準(zhǔn)確單根單根， f (x) 在在 x* 附近附近具有連續(xù)的二階導(dǎo)數(shù)，且具有連續(xù)的二階導(dǎo)數(shù)，且 f (x*) 0，則牛頓法具有二，則牛頓法具有二階收斂速度，即階收斂速度，即牛頓法是平方收

36、斂牛頓法是平方收斂牛頓法的迭代函數(shù)為：牛頓法的迭代函數(shù)為：( )( )( )f xxxfx 22( )( )( )( )( )( )( )1( )( )fxfxf x fxf x fxxfxfx *()0,()0f xfx *()()0()fxxfx 45牛頓法舉例牛頓法舉例每步迭代只做一次除法和一次加法再做一次移位即每步迭代只做一次除法和一次加法再做一次移位即可，計(jì)算量少，收斂速度又較快，是計(jì)算機(jī)求解開(kāi)可，計(jì)算量少，收斂速度又較快，是計(jì)算機(jī)求解開(kāi)方的一個(gè)實(shí)用有效的方法方的一個(gè)實(shí)用有效的方法22221( )222xaxxaaxxxxxx 2( )0f xxa 若用牛頓法求解，由牛頓迭代公式可得

37、：若用牛頓法求解，由牛頓迭代公式可得：112nnnaxxx 則迭代公式為：則迭代公式為：a假設(shè)假設(shè) a 0，求平方根，求平方根 的過(guò)程可化為解方程：的過(guò)程可化為解方程： 4632( )21020f xxxx 610 用牛頓法解方程用牛頓法解方程 ，要求誤差，要求誤差不超過(guò)不超過(guò) 例例解解：由于：由于 f (1) 7， f (2) 1616， f (1) f (2) 又：又：另：另：( )64fxx (1)6,(2)16ff 即：即：( )6,16fx ，所以：，所以：*()0fx ( )fx 事實(shí)上：事實(shí)上： 在在 1, 2 區(qū)間上為單調(diào)增函數(shù)，區(qū)間上為單調(diào)增函數(shù)， 且最大值為且最大值為 16

38、4732222( )21020( )34102(1)80( )6410,16f xxxxfxxxxxfxx 2( )( )( )( )f x fxxfx 可可正正可可負(fù)負(fù)考查考查 (x)的最大值：的最大值：322222102202324210 1.47 32212 110 12013 14 110 1.41 (2)(2)2(2)ff (1)(1)1(1)ff 2(1)920 x xx22(1)(1)710(1)0.242(1)17fff 22(2)(2)16 16(2)0.284(2)30fff 22(1.5)(1.5)2.875 13(1.5)0.07(1.5)22.75fff 滿(mǎn)足收斂定理

39、滿(mǎn)足收斂定理要求的條件要求的條件48取初值取初值 x0 2.0，建立牛頓迭代方程：，建立牛頓迭代方程：3212()21020()3410nnnnnnnnnnf xxxxxxxfxxx 611001.466666670.53310nxxx 3633221.368810222.7021010nxxx 6644331.368808112.11 1010nxxx 655441.36880811010nxxx 49例例如取初值如取初值 x0 1.5，則由牛頓迭代方程：，則由牛頓迭代方程：3212()21020()3410nnnnnnnnnnf xxxxxxxfxxx 可見(jiàn)選擇有根區(qū)間的中點(diǎn)，在相同的精度要求下可見(jiàn)選擇有根區(qū)間的中點(diǎn)，在相同的精度要求下所需的迭代次數(shù)較少所需的迭代次數(shù)較少可計(jì)算得：可計(jì)算得：611001.373626370.12610nxxx