數(shù)值分析 第4章解非線性方程迭代法

1、第第4 4章章 非線性方程求根非線性方程求根 本章討論求非線性方程 (x)=0 (4.1)的根的問題. 其中(x)是高次多項(xiàng)式函數(shù)或超越函數(shù).如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2等等.1 二二 分分 法法 設(shè)(x)在區(qū)間a,b上連續(xù)且(a)(b)0,根據(jù)連續(xù)函數(shù)的介值定理,區(qū)間a,b上必有方程(x)=0的根,稱a,b為方程(x)=0的有根區(qū)間. ,得到新的有根區(qū)間a1,b1, 設(shè)(x)在區(qū)間a,b上連續(xù)且(a)(b)0 .0abyxy=(x) 記a0=a,b0=b,計(jì)算,2000bax若|(x0)| ,則取x0 ;否則,若(a0)(x0)0,

2、取a1=x0,b1=b0 而且有根區(qū)間a1,b1長度是有根區(qū)間a0,b0長度的一半,x0再對(duì)有根區(qū)間a1,b1重復(fù)上面運(yùn)算, 即: 計(jì)算,2111bax若|(x1)|, 則取x1; 否則,若(a1)(x1)0, 取a2=x1 ,b2=b1,得到新的有根區(qū)間a2,b2. x1 而且有根區(qū)間a2,b2長度是有根區(qū)間a1,b1長度的一半.一直進(jìn)行下去,直到求出有根區(qū)間ak,bk.此時(shí),再計(jì)算.2kkkbax 或者有|(xk)| ,或者有11002112222kkkkkkkababababx可見,k趨向無窮大時(shí),xk收斂于 .而且,若要|xk-| ,只要12kab1log2abk或者此時(shí)可取近似根xk

3、 . 在計(jì)算過程中,若出現(xiàn)|(xk)|1,或bk-ak2 .則可取xk作為方程(x)=0的近似根,終止運(yùn)算.例例1 用二分法求x3+4x-10=0在區(qū)間1,2內(nèi)根的近似值,并估計(jì)誤差. 解解 這里(x)=x3+4x-7， (1)(2)=-180,所以(x)=0在1,2區(qū)間有唯一根. 取x0=1.5,由于(x0)=2.375,得新有根區(qū)間1,1.5,x1=1.25,由于(x1)=-0.0468,得新有根區(qū)間1.25,1.5,x2=1.375,由于(x2)=1.0996,得新有根區(qū)間1.25,1.375,x3=1.3125,由于(x3)=0.511,得新有根區(qū)間1.25,1.3125, .x9=1

4、.254882813,得有根區(qū)間1.254882813,1.255859375,x10=1.255371094, (x10)=-0.000105285取x10=1.255371094作為方程根的近似值,且有 00049. 02254882813. 1255859375. 12|101010abx只需k5ln210-115.61.即需取x16. 如果取精度=10-5,則要使51110212|kkkabx 二分法要求函數(shù)在區(qū)間a，b上連續(xù)，且在區(qū)間兩端點(diǎn)函數(shù)值符號(hào)相反，二分法運(yùn)算簡便、可靠、易于在計(jì)算機(jī)上實(shí)現(xiàn)。但是，若方程(x)=0在區(qū)間a，b上根多于1個(gè)時(shí)，也只能求出其中的一個(gè)根。另外，若方程(

5、x)=0在區(qū)間a，b有重根時(shí)，也未必滿足(a)(b)0. 而且由于二分法收斂的速度不是很快,一般不單獨(dú)使用,而多用于為其他方法提供一個(gè)比較好的初始近似值. 2.1 簡單迭代法的一般形式簡單迭代法的一般形式2 簡簡 單單 迭迭 代代 法法 首先把方程(x)=0改寫成等價(jià)(同解)形式 x=(x) (4.2)得到迭代序列xk , 如果xk ,則有=(), 即是方程(x)=0的根.取一個(gè)合適的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3) 這種求方程根的方法稱為簡單迭代法簡單迭代法,或逐逐次逼近法次逼近法.其中(x) 稱為迭代函數(shù)迭代函數(shù) ,式(4.3)稱為迭代格式迭代格

6、式. 若迭代序列xk 收斂 , 則稱簡單迭代法是收斂的簡單迭代法是收斂的. 解解 改寫原方程為等價(jià)方程 求方程x3-2x-3=0在1,2內(nèi)的根.例例2 332 xx , ,建立迭代格式3123,0,1,2.kkxxk如果取初值x0=1.9 ,計(jì)算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.893289201.89328920 由計(jì)算結(jié)果有，x10=x9，因此可取x10=1.89328920. 定義定義4.14.1 設(shè)(x)為定義在區(qū)

7、間I I上的函數(shù), 且對(duì)任何xI I,均有(x)I I,則稱(x)為I I到自身上的映射到自身上的映射. 方程也可改寫成x=(x3-3)/2, 建立迭代格式 xk+1=(x3k-3)/2 , k=0,1,2, 仍取初值x0=1.9, 則有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529可見,xk,此迭代格式是發(fā)散的.2.2 簡單迭代法的收斂條件簡單迭代法的收斂條件 定義定義4.24.2 設(shè)(x)為I I到自身上的映射,且存在0L1,使對(duì)任何x1,x2I,I,有|(x2)-(x1)| L|x2-x1|,則稱(x)為I I上的壓縮映射壓縮映射, L稱為Lip

8、schitzLipschitz常數(shù)常數(shù). 若(x)為I上的壓縮映射,則(x)在I上連續(xù). 定理定理4.24.2 若(x)為I到自身上的映射,且(x)C1(I), |(x)| L1,則(x)為I上的壓縮映射. 證證 對(duì)任意x1,x2I,有 |(x2)-(x1)|=|()|x2-x1| L|x2-x1| 定義定義4.34.3 若(x)為I到自身上的映射,且I I滿足,= (),則稱為(x)的不動(dòng)點(diǎn)不動(dòng)點(diǎn). . 定理定理4.34.3 若(x)為I上的壓縮映射, 則(x)在I I上存在唯一的一個(gè)不動(dòng)點(diǎn),且對(duì)任何x0I,由迭代格式 xk+1=(xk) , k=0,1,2,產(chǎn)生的序列xk收斂于(x)的不動(dòng)

9、點(diǎn).定理定理4.1 證證 不妨設(shè)I=a,b,作函數(shù)(x)=(x)-x,由于xI時(shí), (x)I,則(a)=(a)-a0,(b)=(b)-b0,由(x)的連續(xù)性, 必存在I, 使()=()-=0,即=(),就是(x)的不動(dòng)點(diǎn). 若,I均為(x)的不動(dòng)點(diǎn),則有 |-|=|()-()| L|-|-|所以只能=,即(x)在I上僅有一個(gè)不動(dòng)點(diǎn). 對(duì)任意x0I,有x1=(x0)I,遞推得xkI,設(shè)是(x)的不動(dòng)點(diǎn),則 |xk+1-|=|(xk)-()| L|xk-| L2|xk-1-| Lk+1|x0-|所以xk. 若=(),而在I=-,+上(x)滿足 |(x)-()| L|x-|這里L(fēng)1為Lipschit

10、z常數(shù),則當(dāng)x0-,+時(shí),有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI; 推論推論 若(x)C1a,b,且滿足 1.a(x)b, xa,b; 2.|(x)| L0, 使對(duì)任何xI=-, +都有|(x)| L1. 2.3 簡單迭代法的誤差分析與收斂階簡單迭代法的誤差分析與收斂階 推論推論 若=(),(x)在附近具有一階連續(xù)導(dǎo)數(shù),且|()|0, 當(dāng)x0I=-, +時(shí), 有 (1) 由迭代xk+1=(xk)產(chǎn)生的迭代序列xkI;lim)2(kkx (3) 是I上(x)的唯一不動(dòng)點(diǎn). 定理定理4.54.5 若(x)為I上壓縮映射,則x0I,由迭代 xk+1=(xk) , k=0,1,2,

11、產(chǎn)生的迭代序列xk滿足: 證證 |xk+1-xk|=|(xk)-(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|xk-|11kkkxxLLx011xxLLxkk |xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-|01111.111xxLLxxLLxxLxkkkkkk 由誤差估計(jì)式可見,對(duì)任一0,要使|xk-|, 只要LxxLkln)1 (ln01 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解解 可以驗(yàn)證方程xex-1=0在區(qū)間0.5,0.6內(nèi)僅有一個(gè)根.例例3 改寫方程為x=e-x ,建立迭代格式,

12、 2 , 1 , 0,1kexkxk 由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61則稱序列xk是p p階收斂的階收斂的, 稱p是收斂階收斂階,C是漸近誤差常漸近誤差常數(shù)數(shù). p=1稱為線性收斂線性收斂;p1稱超線性收斂超線性收斂;p=2稱平方收斂平方收斂. 設(shè)(x)充分光滑, 由于 |ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|所以,當(dāng)()0時(shí),有0| )(|)(limlim1kkkkkee于是此時(shí),迭代法是m階收斂的.所以,當(dāng)()0時(shí),簡單迭代法只具有線性收斂. 設(shè)()=()=(m-1)()=0,但(m)()0, 由于 |ek+1|=|xk+1-

13、|=|(xk)-()|mkkmem)(!1)(0| )(|!1)(!1limlim)()(1mkmkmkkkmmee所以mkkmmkmkkkxmxmxxx)(!1)()!1(1)(21)()()()(1)1(2 下面介紹AitkenAitken加速算法加速算法，此方法可對(duì)線性收斂的簡單迭代法起到加速作用，而且可應(yīng)用于其它數(shù)值方法中。假設(shè) (1)(2)，則有 由于 xk+1-=(1)(xk-) xk+2-=(2)(xk+1-)121kkkkxxxx即 (xk+1-)2(xk-)(xk+2-) xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2 解得 kkkkkkxxxxxx12212

14、2kkkkkkxxxxxx12212)(則,序列注意, 如果第k步發(fā)生zk-2yk+xk=0, 就終止計(jì)算, 取xk .如果記 kkkkkkkxxxxxxx12212)( kx 要比序列x k更快地收斂于 , 可構(gòu)造如下的Aitken加速算法:, 2 , 1 , 0,2)(21kxyzxyxxkkkkkkk)(kkxy)(kkyz例例4 分別用簡單迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)取x0= /2,計(jì)算結(jié)果如下k簡單迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.5

15、71091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078 NewtonNewton迭代法迭代法是求方程根的重要方法之一,其最大優(yōu)點(diǎn)是在方程的單根附近具有平方收斂,而且Newton迭代法還可用來求方程的重根、復(fù)根及非線性方程組.3 Newton 迭代法迭代法 3.1 Newton迭代公式迭代公式 設(shè)(x)在有根區(qū)間a,b上二階連續(xù)可微, x0是根的某個(gè)近似值, 因?yàn)?00000)(2)()()()(xxfxxxfxfxf 取(x)(x0)+(x0)(x-x0)

16、,方程(x)=0近似為 (x0)+(x0)(x-x0)=0若(x0)0, 其解為)()(0001xfxfxx得到根的新的近似值x1 ,一般地,在xk附近線性化方程為 (xk)+(xk)(x-xk)=0設(shè)(xk)0, 其解為)4 . 4(, 2 , 1 , 0,)()(1kxfxfxxkkkk迭代格式(4.4)稱為 NewtonNewton迭代法迭代法. . xyox0y=(x)x1x2直線 y=(x0)+(x0)(x-x0)就是 y-(x0)=(x0)(x-x0)Newton迭代法也叫切線法切線法. Newton迭代法相當(dāng)于取迭代函數(shù)3.2 Newton迭代法的收斂性迭代法的收斂性)()()(

17、xfxfxx的簡單迭代法. 因?yàn)?22)()()()()()()(1)(xfxfxfxfxfxfxfx 如果是(x)=0的單根, 即()=0, 但()0, 則有()=0, 從而可知Newton迭代法在根附近是收斂的.因?yàn)?)(2)()()()(kkkkxxfxxxfxfxf 所以2)(2)()()()(kkkkkxfxxfxff 于是有2)()(2)()()(kkkkkkxxffxfxfx 21)()(2)(kkkkxxffx 21)(limkkkxx)(2)(limkkkxff )(2)(ff 可見, Newton迭代法至少是平方收斂的. 若記其中(212mMC M2=max|(x)|,m1

18、=min|(x)|. 則有 |xk+1-| C|xk-|2因此 C|xk+1-| (C|xk-|)2 (C|xk-1-|)4 )1(20|)|(kxC可見,當(dāng)C|x0-|1, 即|x0-|1/2max|(x)|時(shí),簡化Newton迭代法對(duì)x0I收斂.通常取M=(x0). 簡化Newton迭代法一般只具有線性收斂. 2. 2.割線法割線法 因?yàn)? 2 , 1 , 0,)()()(11kxxxfxfxfkkkkkoxyy=(x)x0 x1x2x3 為了簡化計(jì)算(xk),采用迭代格式, 3 , 2 , 1,)()()()(111kxxxfxfxfxxkkkkkkk稱為割線割線法法. . 若(x)在根

19、附近二次連續(xù)可微,且()0,可以證明割線法是收斂的,且有)(2)(lim11ffeeekkkk 割線法收斂的階為.618. 1251p 3. 3.計(jì)算重根的計(jì)算重根的NewtonNewton迭代法迭代法 稱是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=處連續(xù)且h()0, 若h(x)在處充分可微,則 ()=()=(m-1)()=0,(m)()0由于mmxhxxf11)()()(可見,恰是方程0)(1mxf 的單根.應(yīng)用Newton迭代法可得:)()(1)(1111kmkmkkkxfxfmxfxx, 2 , 1 , 0,)()(kxfxfmxkkk稱之為帶參數(shù)帶參數(shù)m m的的NewtonNewton迭代法迭代法, 它是求方程(x)=0的m重根的具有平方收斂的迭代法. 再看函數(shù):( )() ( )( )() ( )( )( ) () ( )f xxh xu xxh xf xmh xxh x可見,恰是方程u(x)=0的單根, 應(yīng)用Newton迭代法有)()(1kkkkxuxuxx這是求方程(x)=0