非線性方程數(shù)值解法詳解PPT課件

1、非線性方程根的概念 給定非線性方程f(x)=0 如果有使得f()=0，則稱為f(x)=0的根或f(x)的零點(diǎn). 設(shè)有正整數(shù)m使得f(x)=(x-)mg(x) 且g()0 ，則當(dāng)m2時(shí)，稱為f(x)=0的m重根；當(dāng)m=1時(shí)，稱為f(x)=0的單根. 若為f(x)=0的m重根，則 f()=f()=f (m-1)()=0, f (m)()0 這里只討論實(shí)根的求法.第1頁(yè)/共57頁(yè)求根步驟 （1）根的存在性. （2）根的隔離. （3）根的精確化.第2頁(yè)/共57頁(yè)非線性方程求根的數(shù)值方法 二分法 迭代法 單點(diǎn)迭代法(不動(dòng)點(diǎn)迭代，Newton迭代法) 多點(diǎn)迭代法(弦截法）第3頁(yè)/共57頁(yè)迭代法的一般理論第

2、4頁(yè)/共57頁(yè) 迭代法是一種逐次逼近的方法，它的基本思想是通過構(gòu)造一個(gè)遞推關(guān)系式 (迭代格式) ，計(jì)算出根的近似值序列,并要求該序列收斂于方程的根.第5頁(yè)/共57頁(yè)單點(diǎn)迭代法 將方程f(x)=0改寫成等價(jià)形式 x=(x) (1)建立迭代公式 xk+1=(xk) (2)在根的附近任取一點(diǎn)x0，可得一序列 .若 收斂，即 ，且(x)連續(xù)，則對(duì)(2)兩端取極限有 =() ，從而為方程(1)的根，也稱為(x)的不動(dòng)點(diǎn)，這種求根算法稱為不動(dòng)點(diǎn)迭代法（Picard迭代法）. (x) 稱為迭代函數(shù). 0kkx 0kkxlimkkx第6頁(yè)/共57頁(yè)多點(diǎn)迭代法 建立迭代公式 xk+1=(xk-n+1, ,xk-

3、2, xk-1, xk) (3)第7頁(yè)/共57頁(yè)對(duì)于迭代法需要考慮一下幾個(gè)主要問題 收斂性 收斂速度 計(jì)算效率第8頁(yè)/共57頁(yè)迭代法的局全收斂性 定義1 設(shè)為f(x)=0的根，如果x0a, b，由迭代法產(chǎn)生的序列都收斂于根 ，則稱該迭代法是全局收斂的。第9頁(yè)/共57頁(yè)迭代法的局部收斂性 定義2 設(shè)方程x=(x) 根, 如果存在的某個(gè)鄰域 : x-，對(duì)任意初值x0，迭代過程所產(chǎn)生的序列均收斂于根 ，則稱該迭代法是局部收斂的.第10頁(yè)/共57頁(yè)迭代過程的收斂速度 定義3 記 ek = - xk ，若則稱迭代過程是p階收斂的.特別地，當(dāng)p=1時(shí)，稱為線性收斂； 當(dāng)p1時(shí)，稱為超線性收斂， 當(dāng)p=2時(shí)

4、，稱為平方收斂. p越大，收斂越快.1lim0kpkkeCe第11頁(yè)/共57頁(yè)效率指數(shù) 定義3 稱為效率指數(shù). 其中p表示迭代的收斂階，表示每步迭代的計(jì)算量. EI越大，計(jì)算效率越高.1pEI 第12頁(yè)/共57頁(yè)不動(dòng)點(diǎn)迭代法第13頁(yè)/共57頁(yè)不動(dòng)點(diǎn)迭代法的整體收斂性 定理1.1 設(shè)(x)滿足 (1)當(dāng)xa, b時(shí)，(x)a, b ； (2)x1, x2a, b ，有 (x1)-(x2)L x1-x2 ， L1 則對(duì)任意初值x0 a, b, 迭代過程 xk+1=(xk)收斂于 x=(x)的惟一根 ，且有誤差估計(jì)式11011kkkkkLxxxLLxxxL第14頁(yè)/共57頁(yè) 證 根的存在性 由(2)

5、知(x)連續(xù). 令f(x)=x-(x), f(a)0, f(b)0, 從而f(x)=0在a, b 上有根，即x=(x)在a, b 上有根. 根的唯一性 設(shè)x=(x)在a, b 上有兩根1, 2， 1 2 ， 1- 2=(1)-(2)L 1- 2 與 L1矛盾.故1= 2 序列的收斂性 xk+1-=(xk)-()Lxk- , xk+1-Lk+1x0- 由0L1有 limkkx第15頁(yè)/共57頁(yè) 誤差估計(jì) xk+1-xk=(xk)(xk-1)Lxk-xk-1 xk+2-xk+1=(xk+1)(xk)L2xk-xk-1 xk+p-xk+p-1Lpxk-xk-1xk+p-xk xk+p-xk+p-1+

6、xk+p-1-xk+p-2+ xk+1-xk (Lp+Lp-1+L) xk-xk-1 =令p，有111pkkLLxxL11011kkkkkLxxxLLxxxL第16頁(yè)/共57頁(yè) 定理1.2 設(shè)(x)在a, b上具有一階導(dǎo)數(shù)，且 (1)當(dāng)xa, b時(shí), (x)a, b ； (1) xa, b ，有(x)L1則對(duì)任意初值x0 a, b, 迭代過程 xk+1=(xk)收斂于 x=(x)的惟一根. 第17頁(yè)/共57頁(yè)不動(dòng)點(diǎn)迭代法的局部收斂性及收斂階 定理1.3 若(x)在方程x=(x)的根的鄰域內(nèi)有一階連續(xù)的導(dǎo)數(shù)，且() 1,則迭代過程xk+1=(xk)具有局部收斂性 證 由連續(xù)函數(shù)性質(zhì)，存在的充分小

7、鄰域 : x-, 使當(dāng)x 時(shí)，有 (x)L1 由微分中值定理有 (x)=(x)()=()x-x- 故(x)，由定理1.2知對(duì)任意初值x0 均收斂.第18頁(yè)/共57頁(yè) 定理1.4 若(x)在方程x=(x)的根的鄰域內(nèi)有充分階連續(xù)的導(dǎo)數(shù)，則迭代過程xk+1=(xk)是p階收斂的充分且必要條件是 (j)()=0, j=1,2,p-1 (p)()0第19頁(yè)/共57頁(yè) 證 充分性 必要性 （略）1( )1lim( )0!kppkkxpx1(1)1( )()11( )( )()( )()( )()(1)!kkppppkkkxxxxxpp ( )111()()!ppkkxxp第20頁(yè)/共57頁(yè)例能不能用迭代

8、法求解方程x=4-2x，如果不能時(shí)，試將方程改寫成能用迭代法求解的形式. 方程為x-4+2x =0.設(shè)f(x)= x-4+2x ，則f(1)0， f(x)= 1+2x ln20,故方程f(x)=0僅在區(qū)間(1, 2)內(nèi)有唯一根.題中 (x)=4-2x，當(dāng)時(shí)x(1,2)時(shí), (x)=-2xln22ln21 ,由定理1.2不能用 來(lái)迭代求根. 把原方程改寫為x=ln(4-x)/ln2, 此時(shí)(x)=ln(4-x)/ln2 , 則有 1當(dāng)x1,2時(shí)， (x)1,ln3/ln2 1,2 2x(1,2) ，有 (x)= 由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2來(lái)求解(1,2)區(qū)間內(nèi)的

9、唯一根. 142kxkx1111114ln242 ln22ln2x第21頁(yè)/共57頁(yè)例設(shè)F(x)=x+c(x2-3)，應(yīng)如何選取c才能使迭xk+1=F(xk)代具有局部收斂性？ 方程x=F(x)的根為 ，函數(shù)F(x)在根附近具有連續(xù)一階導(dǎo)數(shù)，又F (x)=1+2cx，解 得解 得從而使迭代xk+1=F(xk) 具有局部收斂性,則 ，且c0. 令 得 ；令 得 .這時(shí) 為平方收斂.故當(dāng)c取 時(shí)，這個(gè)迭代收斂較快. 123,3 (3)1 2 31Fc 103c12 31c13c 103c)3(F(3)12 30Fc 12 3c ( 3)12 30,Fc 12 3c ( )20Fxc12 3第22頁(yè)

10、/共57頁(yè)例例 設(shè)設(shè)a0,x00, ,證明證明: :迭代公式迭代公式是計(jì)算是計(jì)算 的三階方法的三階方法. . 證 顯然當(dāng)a0，x00時(shí)，xk0（k=1,2,）.令 (x)=x(x2+3a)/(3x2+a)則故對(duì) ，從而迭代收斂.設(shè)xk的極限為l，則有解得 .由題知取 .即迭代序列收斂于 .故此迭代式確是求 的三階方法.212(3 )(3)kkkkxxaxxaa222222222(33 )(3)(3 ) 63()( )(3)(3)xaxax xaxxaxxaxa0,( )1xx 22(3 )(3)l lalla0,lla ala323133322(3)/(3)()limlimlim()()()

11、(3)11lim034kkkkkkkkkkkkkkaxaxxaaxaxaxaxaxxaxaaa第23頁(yè)/共57頁(yè)Newton迭代法第24頁(yè)/共57頁(yè)Newton迭代法 設(shè)有方程f(x)=0，在f(x)=0的根附近任取一點(diǎn)x0作為初始近似根，由迭代公式 逐次逼近方程f(x)=0的根 ，這種求根算法稱為Newton法（切線法），此公式稱為Newton迭代公式.1()(0,1,2,)()kkkkf xxxkfx第25頁(yè)/共57頁(yè)Newton迭代法的收斂性及收斂階 Newton法的迭代函數(shù)是從而 由此知若是f(x)=0的一個(gè)單根, f()=0, f()0, ()=0, ()=f()/f(), 則在根附

12、近Newton法是局部收斂的, 并且是二階收斂的,即 p=2.但如果是f(x)=0的重根，則Newton法僅是線性收斂的 ,即 p=1. ( )( )( )f xxxfx2( )( )( )( )f x fxxfx1112EI第26頁(yè)/共57頁(yè)事實(shí)上，若事實(shí)上，若是是f(x)=0的重根，設(shè)其重?cái)?shù)為的重根，設(shè)其重?cái)?shù)為r, ( )1( )2()1( )( )()()()rrfxxxr f ( )( )1( )lim10,( )1xxxr ( )( )( )f xxxfx( )1( )2()1()()rrfxxr f(1)1( )1(1)2( )1211( )( )()( )()()()(1)!11

13、( )( )()( )()()()(2)!(1)!rrrrrrrrffxfxfxrrxffxfxfxrr第27頁(yè)/共57頁(yè)Newton迭代法的全局部收斂性 定理1.5 設(shè)f(x)在有根區(qū)間a, b上二階導(dǎo)數(shù)存在，且滿足 (1) f(a)f(b)0;則 Newton 迭代法收斂于f(x)=0在a, b內(nèi)的惟一根. 第28頁(yè)/共57頁(yè)例例 研究求研究求 的的NewtonNewton公式公式證明：對(duì)一切證明：對(duì)一切 , ,且序列且序列xk是單調(diào)遞是單調(diào)遞減的，從而迭代過程收斂減的，從而迭代過程收斂. . 證 因a0，x00,故xk0 (k=1,2,).因此對(duì)一切k1,均有 ,利用這一結(jié)果，得故xk+

14、1xk,即xk單調(diào)遞減.根據(jù)單調(diào)有界原理知,xk收斂a101(),0(0,1,2,)2kkkaxxxkx1,2,kkxa121()21()2kkkkkaxxxaxaaxkxa12/111122222kkkkkkxxa xaaxxxa第29頁(yè)/共57頁(yè)例 設(shè)a為正實(shí)數(shù)，試建立求 的Newton迭代公式，要求在迭代函數(shù)中不用除法運(yùn)算，并要求當(dāng)取初值x0滿足 時(shí)，此算法是收斂的. 解 考慮方程則 為此方程的根， ，用Newton法求此方程根的迭代公式為迭代函數(shù)不含除法運(yùn)算.遞推可得1a020 xa1( )0f xax21( )fxx 1a1()(2)(0,1,2,)()kkkkkkf xxxxaxk

15、fx2111(2)(1)(0,1,2,)kkkkaxaxaxaxk 201(1)(0,1,2,)kkaxaxk第30頁(yè)/共57頁(yè)解得當(dāng) 時(shí)， ，從而 故 ，此算法收斂.2011 (1) (0,1,2,)kkxaxka020 xa011ax20lim(1)0kkax1limkkxa第31頁(yè)/共57頁(yè)簡(jiǎn)化 Newton法與Newton下山法 簡(jiǎn)化 Newton法一般地，取C= f(x0). 若 是一階收斂的. Newton下山法其中為下山因子，的選取應(yīng)滿足條件: f(xk+1)f(xk)保證所得序列是收斂的.1(),0,1,2,kkkf xxxkC1()(01),0,1,2,()kkkkf xxx

16、kfx( )( )11,fxxC第32頁(yè)/共57頁(yè)重根情形 已知根的重?cái)?shù)r將Newton法修正為它是求r重根的二階收斂格式.記ek+1 = -xk+1 =記由f()=f()=f (r-1)()=0有G (j)()=0, j=0,1,2,r ; G (r+1)()=-f (r+1)()1()0,1,2,()kkkkf xxxrkfx()()kkkf xxrfx()()()()kkkkxfxrf xfx( )()( )( )G xx fxrf x( )( )(1)( )( )( )()( )( )jjjjGxrfxx fxjfx第33頁(yè)/共57頁(yè)在處將G(xk), f(xk)Taylor展開從而它

17、具有二階收斂格式.(1)11(1)211( )( )1221()()(1)!1(1)()()(1)!rrkrkkrrrkGeGreer rffer(1)12( )1( )lim0(1)( )rkrkkeGer rf第34頁(yè)/共57頁(yè) 根的重?cái)?shù)未知將Newton法修正為 其中u(x)=0單根就是f(x)=0的r重根，故它是求f(x)=0重根的二階收斂格式. 事實(shí)上 為u(x)=0單根.1()0,1,2,()kkkku xxxrku x( )( )( )f xu xfx1( )()( )( )( )()( )()( )rrrf xxg xu xfxr xg xxg x( )()( )()( )g

18、xxrg xxg x第35頁(yè)/共57頁(yè)例例 方程方程x4-4x2+4=0的根的根 = 是二重根，用下列方是二重根，用下列方法求根法求根 (1) Newton迭代迭代法法(2)修正的修正的Newton迭代迭代法法 (3)修正的修正的Newton迭代迭代法法 解 三種方法的迭代公式： Newton迭代法 修正的Newton迭代法 修正的Newton迭代法 )取初值x0=1.5,計(jì)算結(jié)果如表：計(jì)算三步方法(2)和方法(3)均達(dá)到10位有效數(shù)字，而牛頓法只有線性收斂，要達(dá)到同樣精度，需迭代30次.2kkkkxxxx4221212(2)2kkkkkxxxxx2122kkkkxxxxkxk方法(1)方法(

19、2)方法(3)1x11.4583333331.4166666671.4117647062x21.4366071431.4142156861.4142114383x31.4254976191.4142135621.414213562第36頁(yè)/共57頁(yè)弦截法 第37頁(yè)/共57頁(yè)弦截法 在方程f(x)=0的根附近任取兩初始近似根x0 ,x1 ，由迭代公式 逐次逼近f(x)=0的根 ，這種求根算法稱為弦 截法. 收斂階 ，效率指數(shù)111()(0,1,)()()kkkkkkkxxxxf xkf xf x251p152EI第38頁(yè)/共57頁(yè)迭代加速收斂的方法第39頁(yè)/共57頁(yè)Aitken加速收斂方法當(dāng)序列

20、xk為線性收斂時(shí)當(dāng)k較大時(shí), , ,稱為Aitken加速收斂方法1lim0kkkxCx21()kkxCx1()kkxCx2_211212kkkkkkkx xxxxxx221212kkkkkkx xxxxx121kkkkxxxx第40頁(yè)/共57頁(yè)Steffensen加速迭代法若xk為由不動(dòng)點(diǎn)迭代法得到的序列，又稱為Steffensen加速迭代法. 當(dāng)不動(dòng)點(diǎn)迭代函數(shù)(x)在根的某鄰域內(nèi)具有二階導(dǎo)數(shù)，()=L1,且L0，則Steffensen迭代法是2階收斂的.2_211212kkkkkkkx xxxxxx第41頁(yè)/共57頁(yè)利用加速方法確定根的重?cái)?shù)rNewton迭代法收斂緩慢時(shí)，表明有重根.當(dāng)根為重

21、根時(shí)，Newton迭代法為線性收斂，當(dāng)接近收斂時(shí)， ,利用加速公式有11lim1kkkaxaxr 221121212112kkkkkkkkkkkx xxxrxxxxxxx221111kkkkxerxe121kkkxrxx第42頁(yè)/共57頁(yè)解非線性方程組的 擬Newton迭代法第43頁(yè)/共57頁(yè) 非線性方程組的一般形式為令上述方程組可表示為 F(x)=00),(0),(0),(21212211nnnnxxxfxxxfxxxf,000,)()()()(21210nnxxxxxfxfxfxF第44頁(yè)/共57頁(yè) 給定非線性方程組F(x)=0，如果有x使得F(x)=0，則稱x為F(x)=0的解. 當(dāng)n=

22、1時(shí)，便是單個(gè)方程(非線性方程) f(x)=0第45頁(yè)/共57頁(yè)Newton法 若已知方程組F(x)=0的一個(gè)近似解xk=(x1k, x2k, xnk), 將F(x)的分量fi(x)在xk處用多元函數(shù)Taylor展開，取其線性部分有 F(x)F(xk)+F(xk)(x-xk ) 用線性方程組 F(xk)(x-xk )=F(xk)的解作為近似解便得解非線性方程組的Newton法 xk+1=xk F(xk)-1F(xk)記Ak= F(xk),有第46頁(yè)/共57頁(yè) xk+1=xk-Ak-1F(xk) 其中為F(x)的Jaccobi矩陣.111122221212( )nnnnnnfffxxxfffxx

23、xF xfffxxx第47頁(yè)/共57頁(yè)例用例用Newton法求解法求解方程組方程組取取x0=(1.5,1.0) 解 Jacobi矩陣其Newton法為由 x0=(1.5,1.0)逐次迭代求得 x1=(1.5,0.75) x2=(1.488095, 0.755952) x3 =(1.488034, 0.755983) x3的每一位都是有效數(shù)字.112122221212( ,)230( ,)250f x xxxfx xxx1212( )42F xxx21121221( )4128xF xxxx( )( )( )1212( )( )( )( )2( )2211122223128412()()5kkk

24、kkkkkkkxxxxxxxxxx第48頁(yè)/共57頁(yè)擬Newton法依據(jù)k的不同的取法可建立不同的擬Newton法. 任何nn秩m矩陣都能表示成UVT形式，其中U,V為秩m的nm矩陣. 若nn矩陣非奇異，則 (+UVT)-1=-1-1U(E+VT-1U)-1VT-1 (SMW公式)1-11111-()()()()()1kkkkkkkkkkkkkxxA F xAxxF xF xAAArankAm第49頁(yè)/共57頁(yè) 若Ak (對(duì)一切k)可逆,記Hk=Ak-1Ak+1-1 =(k+k)-1=(k+UkVkT)-1 =k-1k-1Uk(E+VkTk-1Uk)-1VkTk-1 與其互逆的迭代格式為111

25、11-() ()()(),()1kkkkkkkkkkkkkxxH F xHF xF xxxHHHrankHm第50頁(yè)/共57頁(yè)秩1擬Newton法 設(shè)Ak=ukvkT ,ukvkRn 記rk=xk+1-xk ,yk=F(xk+1)-F(xk), 有 Ak+1rk=yk, Ak+1=Ak+ukvkT, (Ak+ukvkT) rk=yk, ukvkTrk=ykAkrk它確定的Ak+1滿足擬Newton方程,從而建立了秩1擬Newton法T1()(1 )kkkkkkuyA rv rT1()(2 )kkkkkkkAyA rvv r11TT1T()1(),0,0,1,2,.kkkkkkkkkkkkkkxxA F xAAyA rvvrkvr第51頁(yè)/共57頁(yè) 若k非奇異，則 (SM公式) Hk+1=Hk+Hk得到與之互逆的秩1擬Newton法 NoImage11111()(1)kkkkkkkkkkkAu vAAu vAvAu1 )()1kkkkkkkkkkkkkkkkH u v HrH yv HHv H uv H y 代入(1TT1T()(),0kkkkkkkkkkkkkkkkkxxH F xv HHHrH yvH yv H y第52頁(yè)/共57頁(yè) 1.Broyden秩1方法 若取vk=rk0，于是得到一個(gè)秩1擬Newton法稱之為Broyden秩1方法.它具有超線