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

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

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

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

4、，稱為平方收斂. p越大，收斂越快.1lim0kpkkeCe第11頁/共57頁效率指數(shù) 定義3 稱為效率指數(shù). 其中p表示迭代的收斂階，表示每步迭代的計算量. EI越大，計算效率越高.1pEI 第12頁/共57頁不動點迭代法第13頁/共57頁不動點迭代法的整體收斂性 定理1.1 設(shè)(x)滿足 (1)當xa, b時，(x)a, b ； (2)x1, x2a, b ，有 (x1)-(x2)L x1-x2 ， L1 則對任意初值x0 a, b, 迭代過程 xk+1=(xk)收斂于 x=(x)的惟一根 ，且有誤差估計式11011kkkkkLxxxLLxxxL第14頁/共57頁 證 根的存在性 由(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頁/共57頁 誤差估計 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頁/共57頁 定理1.2 設(shè)(x)在a, b上具有一階導(dǎo)數(shù)，且 (1)當xa, b時, (x)a, b ； (1) xa, b ，有(x)L1則對任意初值x0 a, b, 迭代過程 xk+1=(xk)收斂于 x=(x)的惟一根. 第17頁/共57頁不動點迭代法的局部收斂性及收斂階 定理1.3 若(x)在方程x=(x)的根的鄰域內(nèi)有一階連續(xù)的導(dǎo)數(shù)，且() 1,則迭代過程xk+1=(xk)具有局部收斂性 證 由連續(xù)函數(shù)性質(zhì)，存在的充分小

7、鄰域 : x-, 使當x 時，有 (x)L1 由微分中值定理有 (x)=(x)()=()x-x- 故(x)，由定理1.2知對任意初值x0 均收斂.第18頁/共57頁 定理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頁/共57頁 證 充分性 必要性 （略）1( )1lim( )0!kppkkxpx1(1)1( )()11( )( )()( )()( )()(1)!kkppppkkkxxxxxpp ( )111()()!ppkkxxp第20頁/共57頁例能不能用迭代

8、法求解方程x=4-2x，如果不能時，試將方程改寫成能用迭代法求解的形式. 方程為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，當時x(1,2)時, (x)=-2xln22ln21 ,由定理1.2不能用 來迭代求根. 把原方程改寫為x=ln(4-x)/ln2, 此時(x)=ln(4-x)/ln2 , 則有 1當x1,2時， (x)1,ln3/ln2 1,2 2x(1,2) ，有 (x)= 由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2來求解(1,2)區(qū)間內(nèi)的

9、唯一根. 142kxkx1111114ln242 ln22ln2x第21頁/共57頁例設(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. 令 得 ；令 得 .這時 為平方收斂.故當c取 時，這個迭代收斂較快. 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頁

10、/共57頁例例 設(shè)設(shè)a0,x00, ,證明證明: :迭代公式迭代公式是計算是計算 的三階方法的三階方法. . 證 顯然當a0，x00時，xk0（k=1,2,）.令 (x)=x(x2+3a)/(3x2+a)則故對 ，從而迭代收斂.設(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頁/共57頁Newton迭代法第24頁/共57頁Newton迭代法 設(shè)有方程f(x)=0，在f(x)=0的根附近任取一點x0作為初始近似根，由迭代公式 逐次逼近方程f(x)=0的根 ，這種求根算法稱為Newton法（切線法），此公式稱為Newton迭代公式.1()(0,1,2,)()kkkkf xxxkfx第25頁/共57頁Newton迭代法的收斂性及收斂階 Newton法的迭代函數(shù)是從而 由此知若是f(x)=0的一個單根, f()=0, f()0, ()=0, ()=f()/f(), 則在根附

12、近Newton法是局部收斂的, 并且是二階收斂的,即 p=2.但如果是f(x)=0的重根，則Newton法僅是線性收斂的 ,即 p=1. ( )( )( )f xxxfx2( )( )( )( )f x fxxfx1112EI第26頁/共57頁事實上，若事實上，若是是f(x)=0的重根，設(shè)其重數(shù)為的重根，設(shè)其重數(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頁/共57頁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頁/共57頁例例 研究求研究求 的的NewtonNewton公式公式證明：對一切證明：對一切 , ,且序列且序列xk是單調(diào)遞是單調(diào)遞減的，從而迭代過程收斂減的，從而迭代過程收斂. . 證 因a0，x00,故xk0 (k=1,2,).因此對一切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頁/共57頁例 設(shè)a為正實數(shù)，試建立求 的Newton迭代公式，要求在迭代函數(shù)中不用除法運算，并要求當取初值x0滿足 時，此算法是收斂的. 解 考慮方程則 為此方程的根， ，用Newton法求此方程根的迭代公式為迭代函數(shù)不含除法運算.遞推可得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頁/共57頁解得當 時， ，從而 故 ，此算法收斂.2011 (1) (0,1,2,)kkxaxka020 xa011ax20lim(1)0kkax1limkkxa第31頁/共57頁簡化 Newton法與Newton下山法 簡化 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頁/共57頁重根情形 已知根的重數(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頁/共57頁在處將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頁/共57頁 根的重數(shù)未知將Newton法修正為 其中u(x)=0單根就是f(x)=0的r重根，故它是求f(x)=0重根的二階收斂格式. 事實上 為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頁/共57頁例例 方程方程x4-4x2+4=0的根的根 = 是二重根，用下列方是二重根，用下列方法求根法求根 (1) Newton迭代迭代法法(2)修正的修正的Newton迭代迭代法法 (3)修正的修正的Newton迭代迭代法法 解 三種方法的迭代公式： Newton迭代法 修正的Newton迭代法 修正的Newton迭代法 )取初值x0=1.5,計算結(jié)果如表：計算三步方法(2)和方法(3)均達到10位有效數(shù)字，而牛頓法只有線性收斂，要達到同樣精度，需迭代30次.2kkkkxxxx4221212(2)2kkkkkxxxxx2122kkkkxxxxkxk方法(1)方法(

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

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

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

22、1時，便是單個方程(非線性方程) f(x)=0第45頁/共57頁Newton法 若已知方程組F(x)=0的一個近似解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頁/共57頁 xk+1=xk-Ak-1F(xk) 其中為F(x)的Jaccobi矩陣.111122221212( )nnnnnnfffxxxfffxx

23、xF xfffxxx第47頁/共57頁例用例用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頁/共57頁擬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頁/共57頁 若Ak (對一切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頁/共57頁秩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頁/共57頁 若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頁/共57頁 1.Broyden秩1方法 若取vk=rk0，于是得到一個秩1擬Newton法稱之為Broyden秩1方法.它具有超線