計算方法第二章

1、第二章：解非線性方程的數(shù)值方法第二章：解非線性方程的數(shù)值方法 1. 1. 迭代法的一般概念迭代法的一般概念 2. 2. 區(qū)間分半法區(qū)間分半法 3. 3. 不動點迭代不動點迭代 4. Newton-Raphson4. Newton-Raphson方法方法 5. 5. 割線法割線法 6. 6. 多項式求根多項式求根1 在這一章中，我們將討論求實函數(shù)方程 f (x) =0 ( 1. 1 )的解的數(shù)值方法方程 f (x) =0的解，通常稱為方程的（實）根或函數(shù)f (x) 的零點求非線性方程的根，除了一些特殊方程，如二次三項式方程，一般需要應(yīng)用迭代法所謂迭代法是從給定的一個或幾個初始近似值（以后簡稱初始

2、值） 出發(fā)，按某種方法產(chǎn)生一個序列 （12）稱為迭代序列，使得此序列收斂于方程 f (x) =0的一個根 p，即 這樣，當(dāng)k足夠大時，取 作為 p 的一個近似值 例如，求 的問題可以化為求方程 的一個根在第一章中提到，給定 的一個初始值 ，我們可以由公式1. 1. 迭代法的一般概念迭代法的一般概念2rxxx,.,10,.,.,.,110krrxxxxxpxkklimkx3032x0(0)x 3 產(chǎn)生一個序列 對于選代法，一般需要討論的基本問題是，迭代法的構(gòu)造，迭代序列的收斂性和收斂速度以及誤差估計 解方程f (x) =0 的一個迭代法產(chǎn)生的迭代序列 是否收斂于f (x) =0 的一個根 ，通常

3、與初始近似值選取范圍有關(guān)，若從任何可取的初始值出發(fā)都能保證收斂，則稱之為大范圍收斂大范圍收斂但若為了保證收斂性，必須選取初始值充分接近于所要求的根（解），則稱它為局部收斂局部收斂 為了討論收斂速度，我們先給出一種衡量它的標(biāo)準(zhǔn)收斂階數(shù)假設(shè)一個迭代法收斂（局部或者大范圍）， , 是方程f (x) =0 的一個解令 若存在實數(shù) 和非零常數(shù)C，使得 1. 1. 迭代法的一般概念迭代法的一般概念32/ )3(11kkkxxx01,.,.kxxxkxplimkkxppkkexp (1.3)則稱該迭代法為 階收斂，或者說它的收斂階數(shù)收斂階數(shù)為 ,若 為整數(shù)，則可將（13）式改寫成 （1.4） 的大小反映了收

4、斂速度的快慢若 =1，則說該迭代法是線性收斂線性收斂的； 若 1，則說該迭代法為超線性收斂超線性收斂 通常，局部收斂方法比大范圍收斂方法收斂得更快因此，一個合理的算法是先用一種大范圍收斂方法求得接近于根的近似值，再以其作為新的初始值使用局部收斂方法 1. 1. 迭代法的一般概念迭代法的一般概念4Ceekkk1limCeekkk1lim 解非線性方程 f (x) = 0 （21）的一種直觀而又簡單的迭代法是建立在介值定理上，稱之為二分法二分法或區(qū)間分半?yún)^(qū)間分半法法設(shè)函數(shù)f (x) 在區(qū)間 上連續(xù)，且f (a) f (b) 0據(jù)介值定理知，方程f (x) =0 在區(qū)間 內(nèi)至少有一個根記 = ，設(shè)

5、為區(qū)間 的中點： 若 ， 是予先給定的足夠小的量，則 是所要求的方程 f(x) = 0的一個根的近似值若 ，且 f (p1) f (b1) 0 則區(qū)間 內(nèi)至少有方程 f (x) = 0 的一個根，令 ；若則區(qū)間 內(nèi)至少有f (x) = 0 的一個根，令 。因此，可繼續(xù)將區(qū)間 分半，即將 或 分半，得中點 2. 2. 區(qū)間分半法區(qū)間分半法5ba,ba,ba,11,ba1p2111bap)(1pf1p)(1pf11,bp1212,bbpa0)()(11bfpf11, pa1212,pbaa11, pa11,bp11,ba22,a b即 或如此繼續(xù)，可得到序列 當(dāng)區(qū)間中點的函數(shù)值的絕對值小于誤差容限

6、 或區(qū)間長度小于容限 時，過程終止最后區(qū)間的中點便作為方程 f (x) =0 的一個根的近似。 下面給出區(qū)間分半法求方程區(qū)間分半法求方程 f (x) =0 的近似根的一種算法的近似根的一種算法算法算法2.12.1 假設(shè)f (x)是區(qū)間 上的連續(xù)函數(shù),f (a) f (b)0,求f (x)=0 的一個解 輸人輸人 端點a，b；容限TOL1，TOL2；最大迭代次數(shù)m 輸出輸出 近似解 p 或失敗信息 step l step l 對 n=1，m做 step24 step 2step 2 step 3step 3 若 ，則輸出（p），停機 step 4 step 4 若 f (a) f (b)0，則

7、，否則 step 5 step 5 輸出（Method failed）； 停機 2. 2. 區(qū)間分半法區(qū)間分半法62222abp，2112bpp2112pap,.,.,2, 1npppba,2/ )(bap( )1()/ 22f pTOLbaTOL或pa pb 假設(shè)函數(shù) f (x) 在區(qū)間 a,b 上連續(xù),且兩個端點處函數(shù)值f (a)，f (b)異號不難看出，區(qū)間分半法產(chǎn)生的序列必收斂于方程 f (x) =0 的一個根 p 因此，它是大范圍收斂的并且，得到的序列 有誤差估計式 (2.2)這是一個先驗的絕對誤差界若令表示預(yù)先給定的絕對誤差容限，要求 ，則只要即 兩邊取對數(shù)得 （2.3） 2. 2

8、. 區(qū)間分半法區(qū)間分半法7,.,.,21nppp)(21abppnn ppn )(21abnabn22lg/ )(lgabn于是，可取n為大于 的最小整數(shù)這就給我們提供了一個迭代終止準(zhǔn)則我們可以在第 n步終止迭代在算法 2 1的第 3步的終止準(zhǔn)則 的缺點是，有可能出現(xiàn) 很接近于零，但卻與根 p 相差很大例如， 的一個根為 p = 1 。令則當(dāng) n l時， 但要 則必須 n 1000另一個較好的終止準(zhǔn)則是，考慮到 p本身的大小，令表示相對誤差容限，一直迭代到時，終止迭代過程 2. 2. 區(qū)間分半法區(qū)間分半法8(lg)/lg2ba1)(TOLpf)(npf10) 1()( xxfnpn/11310

9、)(npf310 ppnnnnppp1 例例 設(shè) 由于 f (x) 連續(xù)，且 ,因此f (x)在區(qū)間1，2內(nèi)至少有一個根又因 從而 f (x) 在（1，2）中單調(diào)增加，故 f (x) 在（1，2）內(nèi)有唯一根 p 我們用區(qū)間分半法來求根 p 的近似值，要求根 p 的近似值的絕對誤差不超過 由于因此要使 ，只要 即兩邊取對數(shù)得 因此，取 時，可使 .用區(qū)間分半法迭代14次得結(jié)果見表2.1 2. 2. 區(qū)間分半法區(qū)間分半法91)(3xxxf051)2() 1 (ff)2 , 1 (, 013)(2xxxf410nnnnabpp2/12/ ) 12(2/ )(4102/1n4102/1n4210n4l

10、g1013.3lg2n 14n410 ppn 表 2.1 2. 2. 區(qū)間分半法區(qū)間分半法10nbnanp)(npfn3102 . 631004. 25107 . 441095. 941074. 44105 . 1 使用區(qū)間分半法求方程的根時，從其誤差估計式看出，近似解的誤差下降速度不快但此方法比較簡單，且安全可靠在實際應(yīng)用中，這個方法可以用來求根的初始近似值 2. 2. 區(qū)間分半法區(qū)間分半法11 解非線性方程 f (x) = 0 （31）的問題，常常將它化為解等價方程 x g(x) （32）方程（32）的根又稱為函數(shù) g 的不動點不動點 例例1 方程在區(qū)間 中有唯一根我們可以用不同方法將它化

11、為方程： (1) (2) (3) (4) (5) 等等。 3. 3. 不動點迭代不動點迭代12042)(23xxxf2 , 142)(231xxxxgx1/22( )2(2/)xgxxx2/1332/2)(xxgx2/14)21(2)(xxgxxxxxxxgx4342)(2235為了求 g 的不動點，我們選取一個初始近似值 ，令 （ 3 4）以產(chǎn)生序列 ，這一類迭代法稱為不動點迭代法不動點迭代法，或 Picard迭代. g(x)又稱為迭代函數(shù). 顯然，若 g(x) 連續(xù)，且 g 的一個不動點。因此，p必為方程（3 1）的一個解 算法算法22 用不動點迭代求方程 x=g(x)的一個解 輸人輸人

12、初始值 ；誤差容限TOL；最大迭代次數(shù)m 輸出輸出 近似解 或失敗信息 step l 對k=1，2，m 做 step 23 step 2 step 3 若 ，則輸出 ；停機， 否則 step 4 輸出（Method failed）； 停機 在第3步中，迭代終止準(zhǔn)則可用 3. 3. 不動點迭代不動點迭代130 x,.2 , 1),(1kxgxkk kx是則ppxkk,limp0 x)(0 xgp TOLxp0( )ppx 00.pxTOLp 例例2 就方程（33），取初始值 ，對 g(x) 的五種選擇應(yīng)用迭代公式（34）計算得結(jié)果見表22 3. 3. 不動點迭代不動點迭代145 . 10 xk)

13、(11kkxgx)(12kkxgx)(13kkxgx)(14kkxgx)(15kkxgx5107 . 3165.1 102/1333. 0 續(xù)表續(xù)表2.2從表22看到，選取迭代函數(shù)為 ， 分別迭代12次和4次得到方程的近似根1130395435若選取 作為迭代函數(shù)，則在k為奇數(shù)時迭代子序列 3. 3. 不動點迭代不動點迭代15k)(11kkxgx)(12kkxgx)(13kkxgx)(14kkxgx)(15kkxgx)(4xg)(5xg)(3xg單調(diào)增加，k為偶數(shù)時迭代子序列單調(diào)減小，迭代120次方能得到近似根1130395436。若選取 作為迭代函數(shù)，則迭代序列不收斂。選取 為迭代函數(shù)，出現(xiàn)

14、負數(shù)開方，因而無法繼續(xù)進行迭代。 這個例子說明，我們選擇迭代函數(shù)的基本原則是，首先必須保證 Picard迭代產(chǎn)生的迭代序列 在 g(x)的定義域中，以使迭代過程不致于中斷；其次要求迭代序列 收斂且盡可能收斂得快。 定理定理1 假設(shè)g(x) 為定義在 a,b 上的一個實函數(shù)，它滿足下列條件： (1) (2) Lipschitz 條件，且 Lipschitz 常數(shù) L1，即存在正常數(shù)L,使得 (3.5) 3. 3. 不動點迭代不動點迭代16)(1xg)(2xg,.,.,10kxxx kxbaxbaxg,)(bayxyxLygxg,)()( 那么，對任意的初始值 由Picard迭代（3.4）產(chǎn)生的序

15、列都收斂于g的唯一不動點 ，并且有誤差估計式 (3.6)其中 證明證明 首先證明g的不動點存在且唯一。令 據(jù)條件（1）知 又據(jù)條件（2）知，g（x）在a,b上連續(xù)，從而 h(x) 在a,b 上也連續(xù)因此，方程h(x)=0在a,b上至少有一個根，而且，方程 h(x)=0在a,b上只能有一個根. 否則，假設(shè)存在兩個根 , 則因 3. 3. 不動點迭代不動點迭代17p011xxLLekkpxekk)()(xgxxh0)()(0)()(bgbbhagaah11,pppp0 , xa b從而有 這與假設(shè)條件（2）矛盾，因此 。 其次證明 收斂于 ，據(jù)條件（1）， 因此Picard迭代過程不會中斷由（34

16、）式有據(jù)條件（3.5）因為 0L0，使得對一切 ，有 又據(jù)中值定理，有從而 即 故當(dāng)時，。據(jù)定理 1的推論和定理 2知，對一切 ,Picard迭代收斂，且收斂階數(shù)為 m . 3. 3. 不動點迭代不動點迭代25)(xg0)( pgrprpx,1)(Lxg)()()(pxgpgxgrpxpxgpgxg)()()(rpxg)(,rprpx,)(rprpxg,rprpx NewtonRaphson方法方法（或簡稱Newton法法）是解非線性方程 的最著名的和最有效的數(shù)值方法之一若初始值充分接近于根，則Newton法的收斂速度很快 在不動點迭代中，用不同的方法構(gòu)造迭代函數(shù)便得到不同的迭代法假設(shè)，令 （

17、4.1）則方程 f (x)0 和 xg(x) 是等價的我們選?。?1）為迭代函數(shù)據(jù)（3.4）式，Picard迭代為 （4.2）我們稱（ 4. 2）為 Newton 迭代公式迭代公式，稱為 Newton序列序列 4. Newton-Raphson4. Newton-Raphson方法方法260)( xf0)(xf)()()(xfxfxxg., 2 , 1 , 0,)()(1 kxfxfxxkkkk kx 算法算法23 用 Newton法求方程f(x)0的一個解 輸人輸人初始值x0；誤差容限TOL；最大迭代次數(shù)m輸出輸出 近似解 p 或失敗信息. step1 step2 對對 i =1,2,m 做

18、做step 34. step3step4 若 ,則輸出（ p ），否則step5 輸出（“Mathod failed”); 停機. 4. Newton-Raphson4. Newton-Raphson方法方法2700 xp )()(000pfpfppTOLpp0pp 0在第4步中的迭代終止準(zhǔn)則可用或者 例例1 應(yīng)用Newton法求方程 在 1，2 內(nèi)的一個根 解解 由于 f(1)= 7 , f(2)=16 ，因此 f(1)f(2) 0又因 f(x) 在1,2上連續(xù)，所以方程 f (x)=0 在區(qū)間（1，2）內(nèi)有唯一根 據(jù)Newton迭代公式取初始值 ，得 4. Newton-Raphson4.

19、 Newton-Raphson方法方法28TOLppp0TOLpfTOLppp)(0且020102)(23xxxxf2 , 1 ,01043)(2xxxxf, 2 , 1,104320102112112131 kxxxxxxxkkkkkkk10 x411764706. 11043201020020020301xxxxxxx 1368808189， 1368808108， l368808108， 關(guān)于Newton法有下面的局部收斂性定理 定理定理1 1 假設(shè)函數(shù) f (x) 有 m（2）階連續(xù)導(dǎo)數(shù)，p 是方程 f (x)=0 的單根，則當(dāng)x0充分接近于 p 時，Newton 法收斂，且至少為二階

20、收斂 證明證明 令由于假設(shè) f (x) 有 m（2）階連續(xù)導(dǎo)數(shù)，因此有 4. Newton-Raphson4. Newton-Raphson方法方法29369336471. 11043201021121121312xxxxxxx3x4x5x834101 . 8 xx)()()(xfxfxxg22)()()()()()()()(1)(xfxfxfxfxfxfxfxfxg 而 p 是 f (x) 的單重零點，即有f(p)=0 ， ，從而 ，且存在 r 0，使得對一切 ，有 因此， 在 上連續(xù)據(jù) 3 定理 3 知，當(dāng)初始值 充分接近于 p 時，由 Newton 法（4 2）產(chǎn)生的迭代序列 收斂于 p

21、 ，且收斂階數(shù)至少為 2 定理1表明，當(dāng)初始值充分接近于方程的根時，Newton法收斂得較快 假設(shè) f(x) 有足夠階連續(xù)導(dǎo)數(shù)若 p 是方程 f(x) = 0 的 q（2）重根，即有 則可將 f(x) 表示成 ，而 于是，若令 4. Newton-Raphson4. Newton-Raphson方法方法300)( pf0)( pg,rprpx0)( xf)(, )(xgxg ,rprp0 x kx0)(,0)(,0)(,0)()()1(pfpfpfpfqq但)()()(xhpxxfq0)(ph)()()(xfxfxxg則從而由于f(x)連續(xù)，因此，存在 r 0 ，使得對一切 有且位于 x 與

22、p 之間.由于 ，因此 g (x) 據(jù) 3 定理1 推論知初始值，Newton法收斂由于 4. Newton-Raphson4. Newton-Raphson方法方法31222)()()(1)()()()()(2)(1)( xqhxhpxxhqxhpxxqhxhpxqxg011)()(limqpgxgpx,rprpx1211)(qxgpxgpgxgpxg)()()()(pxpxq)211 (,rprpx,rprp,0rprpx故 Newton 法僅為線性收斂當(dāng) p 是 f(x) =0 的 q 重根時，為提高迭代法的收斂速度，我們作如下考慮 將 f(x) 和 在點 p 按 Taylor公式展開，

23、得到 其中， 和 位于 x 與 p 之間，因此 令因為 ，因此當(dāng) x 充分接近于 p 時， 均不為零據(jù)（44）和（43）知，p 是方程 f(x) =0 的單根.以 F(x) 代替Newton 4. Newton-Raphson4. Newton-Raphson方法方法32qpgeekkpx11)(lim1)(xf )()(!1)(1)(qqfpxqxf)()()!1(1)(2)(1qqfpxqxf21)3 . 4()()()(1)()(2)(1)(qqffpxqxfxf)4 . 4()()()(xfxfxF0)()(pfq)(,)(2)(1)(qqff法中的 f(x)，便得到迭代公式如果迭代函

24、數(shù)具有即需的連續(xù)性條件，那么無論根重數(shù)多少，這個方法至少是二階收的理論上，這個方法的缺點是增加二階導(dǎo)數(shù) 的計算以及迭代過程中的計算更復(fù)雜但是，實際上重根的出現(xiàn)將產(chǎn)生嚴重的舍入誤差問題 例例2 在例1中，方程 在區(qū)間（1，2）中有一個單根 p 取初始值 ，應(yīng)用Newton法迭代四次 4. Newton-Raphson4. Newton-Raphson方法方法33)()(111kkkkxFxFxx)5 . 4(2 , 1,)()()()()(1121111 kxfxfxfxfxfxkkkkkk)()()()()()(2xfxfxfxfxfxxg )(xf 020102)(23xxxxf10 x得

25、現(xiàn)在改用迭代公式（45）來計算它據(jù)（45）式取 ，得 例例3 方程 有一個二重根十了 我們應(yīng)用 Newton法和（45）來算它的近似值現(xiàn)在，Newton迭代公式（42）及其修改公式（45）分別為 4. Newton-Raphson4. Newton-Raphson方法方法34368808108. 14 xp)46)(20102()1043()1043)(20102(1112132112112112131kkkkkkkkkkkkkxxxxxxxxxxxxx368808108. 1368808065. 1368421053. 1321xxx10 x044)(24xxxf21.414213562 1

26、12142)(kkkkxxxx2)2()(121121kkkkkxxxxx取初始值 ，用 迭代三次得結(jié)果如下：由此看出，在 中 準(zhǔn)確到 若用 Newton法（42）來計算，要達到這個精確度則需迭代20次。 4. Newton-Raphson4. Newton-Raphson方法方法355 . 10 x）和（)()(kx414213562. 1425497619. 1414211438. 1436607143. 161.41176470458333333. l321xxx)(0 x810Newton法有明顯的幾何意義（見圖2.1）。函數(shù)方程 f(x) =0 的根 p 是曲線y=f(x) 與 X

27、軸的交點的橫坐標(biāo)。過點作曲線的切線，則切線方程為切線與 X 軸的交點的橫坐標(biāo)為 a p 圖.因此，Newton法又叫做切線法切線法 4. Newton-Raphson4. Newton-Raphson方法方法36)()(kkkxxxfxfy)()(1kkkkxfxfxx)(,(kkkxfxMkT1kxkxb)(,(111kkkxfxM)(,(kkkxfxM 前面我們指出了，若 f(x) 具有足夠階連續(xù)導(dǎo)數(shù)，且選取初始近似值 充分接近于方程 f(x)0的根p，則Newton迭代序列 收斂于 p 在實際應(yīng)用中，有的實際問題本身可以提供接近于根的初始值，但有的問題卻難以確定接近于根的初始值關(guān)于初始值

28、的選取，我們有下面的定理 定理定理2 設(shè)函數(shù) f(x) 在有限區(qū)間a，b上存在二階導(dǎo)數(shù)，且滿足條件： 則Newton法（.）對任意的初始值 ，都收斂于方程f(x)=0的唯一解 p，且收斂階數(shù)為。 4. Newton-Raphson4. Newton-Raphson方法方法37 kx0 x;)()(,)()()(,)()(;,0)()(; 0)()()(abbfbfabafafbaxfbaxxfbfaf 上不變號；在,0bax 在定理2中，條件（ ）保證方程 f(x) 0 在(a，b)內(nèi)至少有一個根條件（ ）表明函數(shù) f(x) 不是嚴格單調(diào)增大（ ）就是嚴格單調(diào)減?。?），因而 f(x) = 0

29、在(a，b)內(nèi)有唯一根條件（ ）說明 f 的圖形不是凹向上 就是凹向下 條件（ ）保證，當(dāng) 時，Newton序列 在（a，b）中例如，從圖22看到，取 時，Newton序列 為單調(diào)增大，且有上界，因而收斂 4. Newton-Raphson4. Newton-Raphson方法方法380 f0 f)0( f)0( f,0bax kxbxax00或,21kxxx)()(afafab)()(bfbf2 . 2圖 例例5 證明方程 在區(qū)間（l，2）內(nèi)有唯一根 p 你能否斷定對任意的初始值 ,Newton序列都收斂于 p ? 若把區(qū)間1，2 改為 8/5，2，則Newton序列收斂于P? 解解 因 f

30、(x) 在 1,2 上連續(xù)，且 因此方程 f(x) 在 1,2 內(nèi)有唯一根 p 由于但因此不能斷定對任意初始值 ，Newton序列都收斂于 p. 若把區(qū)間1,2縮小為 8/5，2 ，則 4. Newton-Raphson4. Newton-Raphson方法方法39032)(3xxxf2 , 1 0 x04)2() 1 (ff2 , 1 ,023)(2xxxf2 , 1 ,06)( xxxf112101)2()2(, 1124) 1 () 1 (ffff2 , 1 0 x0125/263)2()5/8(ff據(jù)定理2 ,對任意的 ，Newton序列都收斂于 p 例例 5 應(yīng)用 Newton法求平

31、方根 ，d0令 求平方根 的問題便化為求方程 f(x)0的根此時，Newton迭代公式為 取 a , b 使 0 a 0,使得對任意初始值 ，由割線法產(chǎn)生的序列 都收斂于 p 5. 5. 割線法割線法50qkqqkqkqkeKKeKeKeK11111111qq11)51 (21qkx618. 1)51 (21q)51 (21,11qeKeqkqk0)( pf,10rprpxxkx 例例2證明方程 x = cos x 在區(qū)間 內(nèi)有唯一根 p ，并且存在 r 0，使得對任意的初始值 ，由割線法產(chǎn)生的序列 都收斂于 p 證明證明 記 f(x)=x - cos x，則 f(x) 連續(xù)，且又因此 f(x

32、) 在 中單調(diào)增大，故在 中存在唯一根 p ，且 顯然， 在 p附近連續(xù)，據(jù)推論知，存在 r 0，使得對任意的 ，由割線法產(chǎn)生的序列 都收斂于 p 5. 5. 割線法割線法512, 0,10rprpxxkx02)2()0(ff2, 0,0sin1)(xxxf2, 0)2, 0(0)( pfxxfcos)( ,10rprpxxkx 在實際應(yīng)用中，經(jīng)常遇到求多項式的根問題我們主要討論實系數(shù)多項式的實根的計算用數(shù)值方法求多項式的近似根時往往要先估計根所在的范圍,設(shè) 是一個 n 次實系數(shù)多項式，其中 我們可以用 Lagrange 法來確定 p(x)的正根的上限設(shè) 為第一個負系數(shù)，即 ,再設(shè)b為負系數(shù)中

33、的最大絕對值，則 p(x) 的正根上限 若M是 p(-x) 的正根上限，則 M 是 p(x) 的負根下限進一步，我們還可以用Sturm序列或Descartes符號律來確定實根個數(shù)以及實根所在的更確切的位置。在確定多項式的實根的位置或求根的方法中，我們需要反復(fù)計算多項式6. 6. 多項式求根多項式求根52) 1 . 6()(0111axaxaxaxpnnnn0naknnaa , 0, 0, 0, 0121knnnaaa0kna但knab1p(x)及其導(dǎo)數(shù) 的值計算多項式的值的最有效的方法是HornerHorner算法算法假設(shè)我們要計算 .以 除 p(x)得商為余數(shù)為 ，則顯然， 將 p(x) 和

34、 q(x) 的表達式代入（62）式，比較X的同次冪項的系數(shù)可得因此，可按遞推公式（63）來計算 對（62）求導(dǎo)數(shù)得從而得到 因此，可以仿上述方法，由遞推公式 6. 6. 多項式求根多項式求根11)(xp)(0 xp0 xx12211)(bxbxbxbxqnnnn0b)2 . 6()()()(00bxqxxxp00)(bxpnnab ) 3 . 6(, 2 , 1,01njxbabjnjnjn)()(00bxp)()()()(0 xqxqxxxp)()(00 xqxp來計算 ： 算法算法2.5 主用 Horner 方法計算多項式 及其導(dǎo)數(shù) 在 的值。 輸入輸入 次數(shù) n；系數(shù) 輸出輸出 step

35、1step2 對 做step3step4 輸出 （y,z）;停機。6. 6. 多項式求根多項式求根54nnbc )4 . 6(. 1, 2 , 1,01njxcbcjnjnjn)(0 xp10)(cxp0111)(axaxaxaxpnnnn)(0 xp0 x010;,xaaan)();(00 xpzxpy;nay ;naz 1, 2 , 1nj;0yxayjn.0zxyz;00yxay 前面介紹的所有求非線性方程的根的方法都可以用來求多項式的實根Newton法則是求多項式實根的一種常用和有效的方法給定初始近似值 ，它的選代公式為 若使用 Horner方法計算多項式 p(x) 及其導(dǎo)數(shù) 的值，則

36、用 Newton法計算 p(x) 的實根的算法如下 算法算法2.6 用Newton法計算多項式 的一個實根 輸人輸人 次數(shù)n；系數(shù) ; 初始值 ;誤差容限TOL;最大迭代次數(shù)m 輸出輸出 近似解 p 或失敗信息 6. 6. 多項式求根多項式求根550 x.2 , 1,)()(111kxpxpxxkkkk)(xp0111)(axaxaxaxpnnnnnaaa,100 xstep1 step2 對 做 step37step3step4 對 做step5step6step7 若 ，則輸出（p），停機，否則 .step8 輸出（Method failed）； 停機. 例例1 多項式 有五個根，和，取初

37、始值 ，應(yīng)用Newton法迭代11次得到結(jié)果如下：6. 6. 多項式求根多項式求根56;00 xp mi,2, 1;nay ;naz ;0ypayjn.0zpyz1,2, 1nj;00ypayzypp/0TOLpp0pp 0)5 . 6(1241553)(2345xxxxxxp5 . 70 x15.97051024.77067033.84113243.13643752.62293562.27711172.08180282.00993892.000172102.000000112.000000這樣，我們計算得多項式 p(x) 的一個根 2 。據(jù)（6.2）式，例1中多項式（6.5）可以表示成p(x

38、)=(x2)q(x)q(x) 的系數(shù)可由（6.3）計算得：6. 6. 多項式求根多項式求根57ixi. 6555)(234xxxxxq q(x) 的每一個根也是 p(x) 的根。求多項式 p(x) 的除2以外的其它實根問題可以化為求多項式 q(x) 的實根。因 q(x) 的次數(shù)低于 p(x) 的次數(shù)，因此這種方法通常叫做降次法。降次法。 假設(shè) 是 n 次多項式 p(x) 的一個實根，則有等式一般地，我們只能計算得 的一個近似值 ，于是 這樣，不能保證 的實根是 的實根。應(yīng)用降次法時，實際上是求 的根作為 的近似根。例多項式例多項式的根為，和取初始值，應(yīng)用Newton法6. 6. 多項式求根多項

39、式求根581x1x1x)()()(1xqxxxp0,)()()(0011bbxqxxxp)()(1xqxq)(1xq)(xp)(1xq)(xp)6 . 6(24024020884344429312)(2345xxxxxxp110 x計算得 的根 的近似值 用降次法得其中我們?nèi)匀粚?應(yīng)用 Newton法，并取初始值 ，得到一個近似根 作為 的根 的近似值。我們再對 使用降次法得到其中我們不能保證的根是或的根，但仍然對應(yīng)用Newton法且取初始值 ，計算得的近似根 作為 的根的近似值對用降次法得到start6. 6. 多項式求根多項式求根59)(xp141x99990.131x011)()()(b

40、xqxxxp13.171609927.2650015.265999895. 1)(2341xxxxxq)(1xq110 x00016.122x)(xp122x)(1xq0221)()()(bxqxxxq)(1xq)(xp)(2xq)(2xq90 x)(2xq999949. 93x)(xp103x)(2xq0332)()()(bxqxxxq 其中剩下的兩個根由用兩次公式計算得在例中，應(yīng)用降次法時，我們使用了系數(shù)有攝動的多項式實際上其中我們用的系數(shù)有攝動的多項式的近似根作為的近似根，從而它又作為 的近似根對于有些多項式，系數(shù)的微小攝動會使其解發(fā)生很大的變化這類多項式通常說它們是壞條件的Wilkin

41、son曾經(jīng)考察了次多項式6. 6. 多項式求根多項式求根609999.14299998.23)(23xxxq)(3xq00006.114x99991.125x)()()(1xqxxxp171602662652)(234xxxxxq)(xq)(1xq)(xp)(xq1920210)20()2)(1()(xxxxxxp其根為，若把的系數(shù)換成，其余系數(shù)都保持不變，所得多項式的一些根就發(fā)生很大變化計算 p(x) 的個根為1.0000000006.00000694410.095266145 0.643500904i2.0000000006.99969723411.793633881 1.65232972

42、8i3.0000000008.00726760313.992358137 2.518830070i4.0000000008.91725024916.73073466 2.812624894i4.99999992820.84690810119.502439400 1.940330347i其中，有個根變成了復(fù)數(shù)在降次過程中，我們一個接一個地求根為使所求的近似根更加精確，在求得第一個近似根后進行降次并計算第二個近似根 ，不用再進行降次，而是以 作為初始值把 Newton法應(yīng)用于原多項式得到第二個根的一個改進的6. 6. 多項式求根多項式求根6119x23221019232)()(xxpxq1x2 x

43、2 x2 x近似值 然后以代替進行下一次降次過程這個過程也用來求其它所有近似根解非線性方程f(x)=0的割線法是從兩個初始值 出發(fā)，過點 與 的直線與X軸的交點 作為f(x)=0 的根的下一個近似值我們可以把它加以推廣，取三個初始值出發(fā)，經(jīng)過點，和的拋物線與軸的交點，作為f(x)=0 的根的一個近似值仿此繼續(xù)從出發(fā)確定等等這個求根方法稱為Muller方法方法或拋物線法拋物線法.Muller方法對于求多項式的根是特別有用的它還可以求多項式的復(fù)根，且一次求一對根6. 6. 多項式求根多項式求根622x2x2 x10,xx)(,(00 xfx)(,(11xfx2x210,xxx)(,(00 xfx)(,(11xfx)(,(22xfx3x321,xxx4x 假設(shè)二次多項式 經(jīng)過點， ， 由于因此得6. 6. 多項式求根多項式求根11cxxbxxaxq)()()(222)(,(00 xfx)(,(11xfx)(,(22x