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

《非线性方程数值解法详解.pptx》由会员分享，可在线阅读，更多相关《非线性方程数值解法详解.pptx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性方程根的概念 给定非线性方程f(x)=0如果有使得f()=0，则称为f(x)=0的根或f(x)的零点.设有正整数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页非线性方程求根的数值方法二分法迭代法 单点迭代法(不动点迭代，Newton迭代法)多点迭代法(弦截法）第3页/共57页迭代法的一般理论第4页/共57页迭代法是一种逐次

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

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

4、.EI越大，计算效率越高.第12页/共57页不动点迭代法第13页/共57页不动点迭代法的整体收敛性定理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)的惟一根，且有误差估计式第14页/共57页证 根的存在性 由(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

5、=2 序列的收敛性 xk+1-=(xk)-()Lxk-,xk+1-Lk+1x0-由0L1有 第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+xk+p-1-xk+p-2+xk+1-xk(Lp+Lp-1+L)xk-xk-1 =令p，有第16页/共57页定理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)的惟一根.第17页/共57页不动点迭代法的局部收敛性及收敛阶定理1.3 若(x)在方程x=(x)的根的邻域内有一阶连续的导数，且()1,则迭代过程xk+1=(xk)具有局部收敛性证 由连续函数性质，存在的充分小邻域 :x-,使当x 时，有 (x)L1 由微分中值定理有 (x)=(x)()=()x-x-故(x)，由定理1.2知对任意初值x0 均收敛.第18页/共57页定理1.4 若(x)在方程x=(x)的根的邻域内有充分阶连续的导数，则迭代过程xk+1=(xk)是p阶收敛的充分且必要条件是 (j)()=0,j=1,2,p-1 (p)()0第19页/共57页证 充分性 必要性（略）第20页/共

7、57页例能不能用迭代法求解方程x=4-2x，如果不能时，试将方程改写成能用迭代法求解的形式.方程为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)，有 (x)=由定理1.2知可用迭代公式xk+1=ln(4-xk)/ln2来求解(1,2)区间内的唯一根.第21

8、页/共57页例设F(x)=x+c(x2-3)，应如何选取c才能使迭xk+1=F(xk)代具有局部收敛性？方程x=F(x)的根为 ，函数F(x)在根附近具有连续一阶导数，又F(x)=1+2cx，解 得解 得从而使迭代xk+1=F(xk)具有局部收敛性,则 ，且c0.令 得 ；令 得 .这时 为平方收敛.故当c取 时，这个迭代收敛较快.第22页/共57页例例 设设a0,x00,证明证明:迭代公式迭代公式是计算是计算 的三阶方法的三阶方法.证 显然当a0，x00时，xk0（k=1,2,）.令 (x)=x(x2+3a)/(3x2+a)则故对 ，从而迭代收敛.设xk的极限为l，则有解得 .由题知取 .即

9、迭代序列收敛于 .故此迭代式确是求 的三阶方法.第23页/共57页Newton迭代法第24页/共57页Newton迭代法 设有方程f(x)=0，在f(x)=0的根附近任取一点x0作为初始近似根，由迭代公式 逐次逼近方程f(x)=0的根，这种求根算法称为Newton法（切线法），此公式称为Newton迭代公式.第25页/共57页Newton迭代法的收敛性及收敛阶Newton法的迭代函数是从而 由此知若是f(x)=0的一个单根,f()=0,f()0,()=0,()=f()/f(),则在根附近Newton法是局部收敛的,并且是二阶收敛的,即 p=2.但如果是f(x)=0的重根，则Newton法仅是线

10、性收敛的,即 p=1.第26页/共57页事实上，若事实上，若是是f(x)=0的重根，设其重数为的重根，设其重数为r,第27页/共57页Newton迭代法的全局部收敛性定理1.5 设f(x)在有根区间a,b上二阶导数存在，且满足(1)f(a)f(b)0;则 Newton 迭代法收敛于f(x)=0在a,b内的惟一根.第28页/共57页例例 研究求研究求 的的NewtonNewton公式公式证明：对一切证明：对一切 ,且序列且序列xk是单调递是单调递减的，从而迭代过程收敛减的，从而迭代过程收敛.证 因a0，x00,故xk0(k=1,2,).因此对一切k1,均有 ,利用这一结果，得故xk+1xk,即x

11、k单调递减.根据单调有界原理知,xk收敛第29页/共57页例 设a为正实数，试建立求 的Newton迭代公式，要求在迭代函数中不用除法运算，并要求当取初值x0满足 时，此算法是收敛的.解 考虑方程则 为此方程的根，用Newton法求此方程根的迭代公式为迭代函数不含除法运算.递推可得第30页/共57页解得当 时，从而故 ，此算法收敛.第31页/共57页简化 Newton法与Newton下山法简化 Newton法一般地，取C=f(x0).若 是一阶收敛的.Newton下山法其中为下山因子，的选取应满足条件:f(xk+1)f(xk)保证所得序列是收敛的.第32页/共57页重根情形已知根的重数r将Ne

12、wton法修正为它是求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)()第33页/共57页在处将G(xk),f(xk)Taylor展开从而它具有二阶收敛格式.第34页/共57页根的重数未知将Newton法修正为 其中u(x)=0单根就是f(x)=0的r重根，故它是求f(x)=0重根的二阶收敛格式.事实上 为u(x)=0单根.第35页/共57页例例 方程方程x4-4x2+4=0的根的根=是二重根，用下列方是二重根，用下列方法求根法求根(1)Newton迭代迭代法法(2)修正的修正的Ne

13、wton迭代迭代法法(3)修正的修正的Newton迭代迭代法法 解 三种方法的迭代公式：Newton迭代法 修正的Newton迭代法 修正的Newton迭代法)取初值x0=1.5,计算结果如表：计算三步方法(2)和方法(3)均达到10位有效数字，而牛顿法只有线性收敛，要达到同样精度，需迭代30次.kxk方法(1)方法(2)方法(3)1x11.4583333331.4166666671.4117647062x21.4366071431.4142156861.4142114383x31.4254976191.4142135621.414213562第36页/共57页弦截法 第37页/共57页弦截法

14、 在方程f(x)=0的根附近任取两初始近似根x0,x1，由迭代公式 逐次逼近f(x)=0的根，这种求根算法称为弦 截法.收敛阶 ，效率指数第38页/共57页迭代加速收敛的方法第39页/共57页Aitken加速收敛方法当序列xk为线性收敛时当k较大时,称为Aitken加速收敛方法第40页/共57页Steffensen加速迭代法若xk为由不动点迭代法得到的序列，又称为Steffensen加速迭代法.当不动点迭代函数(x)在根的某邻域内具有二阶导数，()=L1,且L0，则Steffensen迭代法是2阶收敛的.第41页/共57页利用加速方法确定根的重数rNewton迭代法收敛缓慢时，表明有重根.当根

15、为重根时，Newton迭代法为线性收敛，当接近收敛时，,利用加速公式有第42页/共57页解非线性方程组的 拟Newton迭代法第43页/共57页 非线性方程组的一般形式为令上述方程组可表示为 F(x)=0第44页/共57页给定非线性方程组F(x)=0，如果有x使得F(x)=0，则称x为F(x)=0的解.当n=1时，便是单个方程(非线性方程)f(x)=0第45页/共57页Newton法若已知方程组F(x)=0的一个近似解xk=(x1k,x2k,xnk),将F(x)的分量fi(x)在xk处用多元函数Taylor展开，取其线性部分有 F(x)F(xk)+F(xk)(x-xk)用线性方程组 F(xk)

16、(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矩阵.第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的每一位都是有效数字.第48页/共57页拟Newton法依据k的不同的取法可建立不同的

17、拟Newton法.任何nn秩m矩阵都能表示成UVT形式，其中U,V为秩m的nm矩阵.若nn矩阵非奇异，则 (+UVT)-1=-1-1U(E+VT-1U)-1VT-1 (SMW公式)第49页/共57页若Ak(对一切k)可逆,记Hk=Ak-1Ak+1-1=(k+k)-1=(k+UkVkT)-1 =k-1k-1Uk(E+VkTk-1Uk)-1VkTk-1 与其互逆的迭代格式为第50页/共57页秩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

18、k=ykAkrk它确定的Ak+1满足拟Newton方程,从而建立了秩1拟Newton法第51页/共57页若k非奇异，则 (SM公式)Hk+1=Hk+Hk得到与之互逆的秩1拟Newton法 第52页/共57页1.Broyden秩1方法若取vk=rk0，于是得到一个秩1拟Newton法称之为Broyden秩1方法.它具有超线性收敛速度.与其互逆的秩1方法第53页/共57页2.对称秩1方法若取vk=F(xk+1)，ykAkrk=F(xk+1)F(xk)Akrk=F(xk+1)=vk于是由(2o)可得修正矩阵Ak对称，若A0对称，所有Ak(k=0,1,2)都对称,从而得到一个对称的秩1方法第54页/共

19、57页与其互逆的秩1方法第55页/共57页例用逆例用逆Broyden方法求方程组方法求方程组的解，取的解，取x0=(0,0)解F(x0)=(-1,3.25)用逆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方法大得多.第56页/共57页感谢您的观看！第57页/共57页