非线性方程数值解法详解课件.pptx

1、 第一章非线性方程和方程组的数值解法非线性方程根的概念 给定非线性方程f(x)=0n如果有使得f()=0，则称为f(x)=0的根或f(x)的零点.n设有正整数m使得f(x)=(x-)mg(x)且g()0，则当m2时，称为f(x)=0的m重根；当m=1时，称为f(x)=0的单根.n若为f(x)=0的m重根，则 f()=f()=f(m-1)()=0,f(m)()0n这里只讨论实根的求法.求根步骤 n（1）根的存在性.n（2）根的隔离.n（3）根的精确化.非线性方程求根的数值方法n二分法n迭代法 单点迭代法(不动点迭代，Newton迭代法)多点迭代法(弦截法）迭代法的一般理论n迭代法是一种逐次逼近的

2、方法，它的基本思想是通过构造一个递推关系式(迭代格式)，计算出根的近似值序列,并要求该序列收敛于方程的根.单点迭代法n将方程f(x)=0改写成等价形式 x=(x)(1)建立迭代公式 xk+1=(xk)(2)在根的附近任取一点x0，可得一序列 .若 收敛，即 ，且(x)连续，则对(2)两端取极限有=()，从而为方程(1)的根，也称为(x)的不动点，这种求根算法称为不动点迭代法（Picard迭代法）.(x)称为迭代函数.0kkx 0kkxlimkkx多点迭代法n建立迭代公式 xk+1=(xk-n+1,xk-2,xk-1,xk)(3)对于迭代法需要考虑一下几个主要问题n收敛性n收敛速度n计算效率迭代

3、法的局全收敛性 n定义1 设为f(x)=0的根，如果x0a,b，由迭代法产生的序列都收敛于根，则称该迭代法是全局收敛的。迭代法的局部收敛性 n定义定义2 设方程x=(x)根,如果存在的某个邻域:x-，对任意初值x0，迭代过程所产生的序列均收敛于根，则称该迭代法是局部收敛的.迭代过程的收敛速度 n定义定义3 记 ek=-xk，若则称迭代过程是p阶收敛的.特别地，当p=1时，称为线性收敛；当p1时，称为超线性收敛，当p=2时，称为平方收敛.p越大，收敛越快.1lim0kpkkeCe效率指数n定义定义3 称为效率指数.其中p表示迭代的收敛阶，表示每步迭代的计算量.EI越大，计算效率越高.1pEI 不

4、动点迭代法不动点迭代法的整体收敛性n定理1.1 设(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)的惟一根，且有误差估计式11011kkkkkLxxxLLxxxLn证 根的存在性 由(2)知(x)连续.令f(x)=x-(x),f(a)0,f(b)0,从而f(x)=0在a,b 上有根，即x=(x)在a,b 上有根.根的唯一性 设x=(x)在a,b 上有两根1,2，1 2，1-2=(1)-(2)L 1-2 与 L1矛盾.故1=2 序列的收敛性 xk+1-=(xk

5、)-()Lxk-,xk+1-Lk+1x0-由0L1有 limkkx 误差估计 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+xk+p-1-xk+p-2+xk+1-xk(Lp+Lp-1+L)xk-xk-1 =令p，有111pkkLLxxL11011kkkkkLxxxLLxxxLn定理1.2 设(x)在a,b上具有一阶导数，且(1)当xa,b时,(x)a,b；(1)xa,b，有(x)L1则对任意初值x0 a,b,迭代过程 xk+1=(xk)收敛于 x=

6、(x)的惟一根.不动点迭代法的局部收敛性及收敛阶n定理1.3 若(x)在方程x=(x)的根的邻域内有一阶连续的导数，且()1,则迭代过程xk+1=(xk)具有局部收敛性n证 由连续函数性质，存在的充分小邻域 :x-,使当x 时，有 (x)L1 由微分中值定理有 (x)=(x)()=()x-x-故(x)，由定理1.2知对任意初值x0 均收敛.n定理1.4 若(x)在方程x=(x)的根的邻域内有充分阶连续的导数，则迭代过程xk+1=(xk)是p阶收敛的充分且必要条件是 (j)()=0,j=1,2,p-1 (p)()0n证 充分性 必要性（略）1()1lim()0!kppkkxpx1(1)1()()

7、11()()()()()()()(1)!kkppppkkkxxxxxpp ()111()()!ppkkxxp例能不能用迭代法求解方程x=4-2x，如果不能时，试将方程改写成能用迭代法求解的形式.n方程为x-4+2x=0.设f(x)=x-4+2x，则f(1)0，f(x)=1+2x ln20,故方程f(x)=0仅在区间(1,2)内有唯一根.题中(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)，有 (

8、x)=由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区间内的唯一根.142kxkx1111114ln242 ln22ln2x例设F(x)=x+c(x2-3)，应如何选取c才能使迭xk+1=F(xk)代具有局部收敛性？n方程x=F(x)的根为 ，函数F(x)在根附近具有连续一阶导数，又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

9、30,Fc 12 3c ()20Fxc12 3例 设a0,x00,证明:迭代公式是计算 的三阶方法.n证 显然当a0，x00时，xk0（k=1,2,）.令 (x)=x(x2+3a)/(3x2+a)则故对 ，从而迭代收敛.设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()()()(3)11lim034k

10、kkkkkkkkkkkkkaxaxxaaxaxaxaxaxxaxaaaNewton迭代法Newton迭代法 n设有方程f(x)=0，在f(x)=0的根附近任取一点x0作为初始近似根，由迭代公式 逐次逼近方程f(x)=0的根，这种求根算法称为Newton法（切线法），此公式称为Newton迭代公式.1()(0,1,2,)()kkkkf xxxkfxNewton迭代法的收敛性及收敛阶nNewton法的迭代函数是从而 由此知若是f(x)=0的一个单根,f()=0,f()0,()=0,()=f()/f(),则在根附近Newton法是局部收敛的,并且是二阶收敛的,即 p=2.但如果是f(x)=0的重根，

11、则Newton法仅是线性收敛的,即 p=1.()()()f xxxfx2()()()()f x fxxfx1112EI事实上，若是f(x)=0的重根，设其重数为r,()1()2()1()()()()()rrfxxxr f()()1()lim10,()1xxxr ()()()f xxxfx()1()2()1()()rrfxxr f(1)1()1(1)2()1211()()()()()()()(1)!11()()()()()()()(2)!(1)!rrrrrrrrffxfxfxrrxffxfxfxrrNewton迭代法的全局部收敛性n定理1.5 设f(x)在有根区间a,b上二阶导数存在，且满足(1

12、)f(a)f(b)0;则 Newton 迭代法收敛于f(x)=0在a,b内的惟一根.例 研究求 的Newton公式证明：对一切 ,且序列xk是单调递减的，从而迭代过程收敛.n证 因a0，x00,故xk0(k=1,2,).因此对一切k1,均有 ,利用这一结果，得故xk+1xk,即xk单调递减.根据单调有界原理知,xk收敛a101(),0(0,1,2,)2kkkaxxxkx1,2,kkxa121()21()2kkkkkaxxxaxaaxkxa12/111122222kkkkkkxxa xaaxxxa例 设a为正实数，试建立求 的Newton迭代公式，要求在迭代函数中不用除法运算，并要求当取初值x0

13、满足 时，此算法是收敛的.n解 考虑方程则 为此方程的根，用Newton法求此方程根的迭代公式为迭代函数不含除法运算.递推可得1a020 xa1()0f xax21()fxx 1a1()(2)(0,1,2,)()kkkkkkf xxxxaxkfx2111(2)(1)(0,1,2,)kkkkaxaxaxaxk 201(1)(0,1,2,)kkaxaxk解得当 时，从而n故 ，此算法收敛.2011(1)(0,1,2,)kkxaxka020 xa011ax20lim(1)0kkax1limkkxa简化 Newton法与Newton下山法n简化 Newton法一般地，取C=f(x0).若 是一阶收敛的

14、.nNewton下山法其中为下山因子，的选取应满足条件:f(xk+1)f(xk)保证所得序列是收敛的.1(),0,1,2,kkkf xxxkC1()(01),0,1,2,()kkkkf xxxkfx()()11,fxxC重根情形n已知根的重数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()()(

15、1)()()()()()()jjjjGxrfxx fxjfx在处将G(xk),f(xk)Taylor展开从而它具有二阶收敛格式.(1)11(1)211()()1221()()(1)!1(1)()()(1)!rrkrkkrrrkGeGreer rffer(1)12()1()lim0(1)()rkrkkeGer rfn根的重数未知将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

16、xu xfxr xg xxg x()()()()()g xxrg xxg x例 方程x4-4x2+4=0的根=是二重根，用下列方法求根(1)Newton迭代法(1.3.11);(2)修正的Newton迭代法(1.5.2);(3)修正的Newton迭代法(1.5.4)n解 三种方法的迭代公式：Newton迭代法 修正的Newton迭代法(1.5.2)修正的Newton迭代法(1.5.4)取初值x0=1.5,计算结果如表：计算三步方法(2)和方法(3)均达到10位有效数字，而牛顿法只有线性收敛，要达到同样精度，需迭代30次.2kkkkxxxx4221212(2)2kkkkkxxxxx2122kkk

17、kxxxxkxk方法(1)方法(2)方法(3)1x11.4583333331.4166666671.4117647062x21.4366071431.4142156861.4142114383x31.4254976191.4142135621.414213562弦截法 弦截法 n在方程f(x)=0的根附近任取两初始近似根x0,x1，由迭代公式 逐次逼近f(x)=0的根，这种求根算法称为弦 截法.收敛阶 ，效率指数111()(0,1,)()()kkkkkkkxxxxf xkf xf x251p152EI迭代加速收敛的方法Aitken加速收敛方法当序列xk为线性收敛时当k较大时,称为Aitken加

18、速收敛方法1lim0kkkxCx21()kkxCx1()kkxCx2_211212kkkkkkkx xxxxxx221212kkkkkkx xxxxx121kkkkxxxxSteffensen加速迭代法若xk为由不动点迭代法得到的序列，又称为Steffensen加速迭代法.当不动点迭代函数(x)在根的某邻域内具有二阶导数，()=L1,且L0，则Steffensen迭代法是2阶收敛的.2_211212kkkkkkkx xxxxxx利用加速方法确定根的重数rNewton迭代法收敛缓慢时，表明有重根.当根为重根时，Newton迭代法为线性收敛，当接近收敛时，,利用加速公式有11lim1kkkaxax

19、r 221121212112kkkkkkkkkkkx xxxrxxxxxxx221111kkkkxerxe121kkkxrxx解非线性方程组的 拟Newton迭代法 n非线性方程组的一般形式为令上述方程组可表示为 F(x)=00),(0),(0),(21212211nnnnxxxfxxxfxxxf,000,)()()()(21210nnxxxxxfxfxfxFn给定非线性方程组F(x)=0，如果有x使得F(x)=0，则称x为F(x)=0的解.n当n=1时，便是单个方程(非线性方程)f(x)=0Newton法n若已知方程组F(x)=0的一个近似解xk=(x1k,x2k,xnk),将F(x)的分量

20、fi(x)在xk处用多元函数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),有 xk+1=xk-Ak-1F(xk)其中为F(x)的Jaccobi矩阵.111122221212()nnnnnnfffxxxfffxxxF xfffxxx例用Newton法求解方程组取x0=(1.5,1.0)n解 Jacobi矩阵其Newton法为由 x0=(1.5,1.0)逐次迭代求得 x1=(1.5,0.75)x2=(1.4880

21、95,0.755952)x3=(1.488034,0.755983)x3的每一位都是有效数字.112122221212(,)230(,)250f x xxxfx xxx1212()42F xxx21121221()4128xF xxxx()()()1212()()()()2()2211122223128412()()5kkkkkkkkkkxxxxxxxxxx拟Newton法依据k的不同的取法可建立不同的拟Newton法.n任何nn秩m矩阵都能表示成UVT形式，其中U,V为秩m的nm矩阵.若nn矩阵非奇异，则 (+UVT)-1=-1-1U(E+VT-1U)-1VT-1 (SMW公式)1-1111

22、1-()()()()()1kkkkkkkkkkkkkxxA F xAxxF xF xAAArankAmn若Ak(对一切k)可逆,记Hk=Ak-1Ak+1-1=(k+k)-1=(k+UkVkT)-1 =k-1k-1Uk(E+VkTk-1Uk)-1VkTk-1 与其互逆的迭代格式为11111-()()()(),()1kkkkkkkkkkkkkxxH F xHF xF xxxHHHrankHm秩1拟Newton法 设Ak=ukvkT,ukvkRn 记rk=xk+1-xk,yk=F(xk+1)-F(xk),有 Ak+1rk=yk,Ak+1=Ak+ukvkT,(Ak+ukvkT)rk=yk,ukvkTr

23、k=ykAkrk它确定的Ak+1满足拟Newton方程,从而建立了秩1拟Newton法T1()(1)kkkkkkuyA rv rT1()(2)kkkkkkkAyA rvv r11TT1T()1(),0,0,1,2,.kkkkkkkkkkkkkkxxA F xAAyA rvvrkvrn若k非奇异，则 (SM公式)Hk+1=Hk+Hk得到与之互逆的秩1拟Newton法 11111()(1)kkkkkkkkkkkAu vAAu vAvAu1)()1kkkkkkkkkkkkkkkkH u v HrH yv HHv H uv H y 代入(1TT1T()(),0kkkkkkkkkkkkkkkkkxxH

24、F xv HHHrH yvH yv H yn1.Broyden秩1方法n若取vk=rk0，于是得到一个秩1拟Newton法称之为Broyden秩1方法.它具有超线性收敛速度.n与其互逆的秩1方法11T1T()()(),0,1,2,.()kkkkkkkkkkkkxxA F xrAAyA rkrr1TT1T()()(),0()kkkkkkkkkkkkkkkkkxxH F xrHHHrH yr H yrH yn2.对称秩1方法n若取vk=F(xk+1)，ykAkrk=F(xk+1)F(xk)Akrk=F(xk+1)=vk于是由(2o)可得修正矩阵Ak对称，若A0对称，所有Ak(k=0,1,2)都对称

25、,从而得到一个对称的秩1方法T()()()kkkkkkkkkkkyA rAyA ryA rr11TT1T()()(),()0,0,1,2,.()kkkkkkkkikkKkkkkikkkxxA F xyA rAAyA ryA rrkyA rrn与其互逆的秩1方法1TT1T()()(),()0,0,1,2.()kkkkkkkkkkkkkkkkkkkkxxH F xrH yHHrH yrH yykrH yy例用逆Broyden方法求方程组的解，取x0=(0,0)n解F(x0)=(-1,3.25)n用逆Broyden方法迭代求解得 x1=(1.0625,-1)，r0=(1.0625,-1),F(x1)=(1.12890625,2.12890625),y0=(2.12890625,-1.1210937),进行第二次迭代，迭代11次得解 x11=(1.54634088332,1.39117631279)若用Newton法求解，取相同的初始值x0，达到同一精度只需迭代7次，但它的计算量比逆Broyden方法大得多.025.341)(222121221xxxxxxxF11221()2421xF xxx0001()41AF x0100.250.25()10HF x10.35574410.27219320.52249910.1002162H