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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第一章,非线性方程和方程组的数值解法,第一章非线性方程和方程组的数值解,1,非线性方程根的概念,给定非线性方程,f,(,x,)=0,如果有,使得,f,(,)=0,，则称,为,f,(,x,)=0,的根或,f,(,x,),的零点,.,设有正整数,m,使得,f,(,x,)=(,x,-,),m,g,(,x,),且,g,(,),0,，则当,m,2,时，称,为,f,(,x,)=0,的,m,重根；当,m,=1,时，称,为,f,(,x,)=0,的单根,.,若,为,f,(,x,)=0,的,m,重根，则,f,(,)=,f,(,)=,=,f,(,m,-1),(,)=0,f,(,m,),(,),0,这里只讨论实根的求法,.,非线性方程根的概念 给定非线性方程f(x)=0,2,求根步骤,（,1,）根的存在性,.,（,2,）根的隔离,.,（,3,）根的精确化,.,求根步骤 （1）根的存在性.,3,非线性方程求根的数值方法,二分法,迭代法,单点迭代法,(,不动点迭代，,Newton,迭代法,),多点迭代法,(,弦截法）,非线性方程求根的数值方法二分法,4,迭代法的一般理论,迭代法的一般理论,5,迭代法是一种逐次逼近的方法，它的基本思想是通过构造一个递推关系式,(,迭代格式,),，计算出根的近似值序列,并要求该序列收敛于方程的根,.,迭代法是一种逐次逼近的方法，它的基本思想是通过构造一个递推关,6,单点迭代法,将方程,f,(,x,)=0,改写成等价形式,x,=,(,x,),(1),建立迭代公式,x,k,+1,=,(,x,k,),(2),在根的附近任取一点,x,0,，可得一序列,.,若,收敛，即 ，且,(,x,),连续，则对,(2),两,端取极限有,=,(,),，从而,为方程,(1),的根，,也称为,(,x,),的不动点，这种求根算法称为不动点,迭代法（,Picard,迭代法）,.,(,x,),称为迭代函数,.,单点迭代法将方程f(x)=0改写成等价形式,7,多点迭代法,建立迭代公式,x,k,+1,=,(,x,k-n+,1, ,x,k-,2,x,k-,1,x,k,),(3),多点迭代法建立迭代公式,8,对于,迭代法,需要考虑一下几个主要问题,收敛性,收敛速度,计算效率,对于迭代法需要考虑一下几个主要问题,9,迭代法的局全收敛性,定义,1,设,为,f,(,x,)=0,的根，如果,x,0,a,b,，由迭代法产生的序列都收敛于根,，则称该迭代法是全局收敛的。,迭代法的局全收敛性 定义1 设为f(x)=0的根，如果x0,10,迭代法的局部收敛性,定义,2,设方程,x,=,(,x,),根,如果存在,的某个邻域,: ,x,-,，对任意初值,x,0,，,迭代过程,所产生的序列,均收敛于根,，则称该迭代法是局部收敛的,.,迭代法的局部收敛性 定义2 设方程x=(x) 根,11,迭代过程的收敛速度,定义,3,记,e,k,=,-,x,k,，若,则称迭代过程是,p,阶收敛的,.,特别地，当,p,=1,时，称为线性收敛；,当,p,1,时，称为超线性收敛，,当,p,=2,时，称为平方收敛,.,p,越大，收敛越快,.,迭代过程的收敛速度 定义3 记 ek = - xk ，若,12,效率指数,定义,3,称,为效率指数,.,其中,p,表示迭代的收敛阶，,表示,每步迭代的计算量,.,EI,越大，计算效率越高,.,效率指数定义3 称,13,不动点迭代法,不动点迭代法,14,不动点迭代法的整体收敛性,定理,1.1,设,(,x,),满足,(1),当,x,a,b,时，,(,x,),a,b,；,(2),x,1,x,2,a,b,，有,(,x,1,)-,(,x,2,),L,x,1,-,x,2,，,L,1,则对任意初值,x,0,a,b,迭代过程,x,k,+1,=,(,x,k,),收敛于,x,=,(,x,),的惟一根,，,且,有,误差,估计式,不动点迭代法的整体收敛性定理1.1 设(x)满足,15,证,根的存在性,由,(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,与,L,1,矛盾,.,故,1,=,2,序列的收敛性,x,k,+1,-,=,(,x,k,),-,(,),L,x,k,-, ,x,k,+1,-,L,k,+1,x,0,-,由,0,L,1,有,证 根的存在性,16,误差,估计,x,k,+1,-,x,k,=,(,x,k,),(,x,k-,1,),L,x,k,-,x,k,-1,x,k,+2,-,x,k,+1,=,(,x,k,+1,),(,x,k,),L,2,x,k,-,x,k,-1,x,k,+,p,-,x,k,+,p,-1,L,p,x,k,-,x,k,-1,x,k,+,p,-,x,k, ,x,k,+,p,-,x,k,+,p,-1,+,x,k,+,p,-1,-,x,k,+,p,-2,+ ,x,k,+1,-,x,k,(,L,p,+,L,p-,1,+,L,) ,x,k,-,x,k,-1,=,令,p,，有,误差估计,17,定理,1.2,设,(,x,),在,a,b,上具有一阶导数，且,(1),当,x,a,b,时,(,x,),a,b,；,(1),x,a,b,，有,(,x,),L,1,则对任意初值,x,0,a,b,迭代过程,x,k,+1,=,(,x,k,),收敛于,x,=,(,x,),的惟一根,.,定理1.2 设(x)在a, b上具有一阶导数，且,18,不动点迭代法的局部收敛性及收敛阶,定理,1.3,若,(,x,),在方程,x,=,(,x,),的根,的,邻,域内,有一阶连续的导数,，且,(,) 1,则迭代过程,x,k,+1,=,(,x,k,),具有局部收敛性,证,由连续函数性质，存在,的,充分小邻域,:,x,-,使当,x,时，有,(,x,),L,1,由微分中值定理有,(,x,),=,(,x,),(,),=,(,),x,-,x,-,故,(,x,),，由定理,1.2,知,对,任意初值,x,0,均收敛,.,不动点迭代法的局部收敛性及收敛阶定理1.3 若(x)在方,19,定理,1.4,若,(,x,),在方程,x,=,(,x,),的根,的,邻,域内,有,充分阶,连续的导数,，则迭代过程,x,k,+1,=,(,x,k,),是,p,阶收敛的充分且必要条件是,(,j,),(,)=0,j,=1,2,p,-1,(,p,),(,)0,定理1.4 若(x)在方程x=(x)的根的邻域内有充,20,证 充分性,必要性 （略）,证 充分性,21,例,能不能用迭代法求解方程,x,=4-2,x,，如果不能时，试将方程改写成能用迭代法求解的形式,.,方程为,x,-4+2,x,=0.,设,f(x,)=,x,-4+2,x,，则,f,(1)0,，,f,(,x,)= 1+2,x,ln20,故方程,f,(,x,)=0,仅在区间,(1, 2),内有唯一根,.,题中,(,x,)=,4-2,x,，当时,x,(1,2),时,(,x,),=,-2,x,ln2,2ln21,由,定理,1.2,不能用 来迭代求根,.,把原方程改写为,x,=ln(4-,x,)/ln2,此时,(,x,)=,ln(4-,x,)/ln2 ,则有,1,当,x,1,2,时，,(,x,)1,ln3/ln2,1,2,2,x,(1,2),，有,(,x,),=,由定理,1.2,知可用迭代公式,x,k,+1,=ln(4-,x,k,)/ln2,来求解,(1,2),区,间内的唯一根,.,例能不能用迭代法求解方程x=4-2x，如果不能时，试将方程,22,例设,F,(,x,)=,x,+,c,(,x,2,-3),，,应如何选取,c,才能使迭,x,k,+1,=,F,(,x,k,),代具有局部收敛性？,方程,x,=,F,(,x,),的根为 ，函数,F,(,x,),在根附,近具有连续一阶导数，又,F,(,x,)=1+2,cx,，,解 得,解 得,从而使迭代,x,k,+1,=,F,(,x,k,),具有局部收敛性,则 ，且,c,0,.,令 得,；,令 得,.,这时 为平方收敛,.,故当,c,取 时，这个迭代收敛较快,.,例设F(x)=x+c(x2-3)，应如何选取c才能使迭xk,23,例,设,a,0,x,0,0,证明,:,迭代公式是计算 的三阶方法,.,证,显然当,a,0,，,x,0,0,时，,x,k,0,（,k,=1,2,）,.,令,(,x,)=,x,(,x,2,+3,a,),/,(3,x,2,+,a,),则,故对 ，从而迭代收敛,.,设,x,k,的极限为,l,，则有,解得,.,由题知取,.,即迭代序列收敛于,.,故此迭代式确是求 的三阶方法,.,例 设a0,x00,证明:迭代公式是计算 的三,24,Newton,迭代法,Newton迭代法,25,Newton,迭代法,设有方程,f,(,x,)=0,，在,f,(,x,)=0,的根,附近任取一点,x,0,作为初始近似根，由迭代公式,逐次逼近方程,f,(,x,)=0,的根,，这种求根算法称为,Newton,法（切线法），此公式称为,Newton,迭代公式,.,Newton迭代法 设有方程f(x)=0，在f(x)=0的根,26,Newton,迭代法的收敛性及收敛阶,Newton,法的迭代函数是,从而,由此知若,是,f,(,x,)=0,的一个单根,f,(,)=0,f,(,),0,(,),=,0,(,),=,f,(,)/,f,(,),则在根,附近,Newton,法是局部收敛的,并且是二阶收敛的,即,p=,2,.,但如果,是,f,(,x,)=0,的重根，则,Newton,法仅是线性,收敛的,即,p=,1,.,Newton迭代法的收敛性及收敛阶Newton法的迭代函数是,27,事实上，若,是,f,(,x,)=0,的重根，设其重数为,r,事实上，若是f(x)=0的重根，设其重数为r,28,Newton,迭代法,的,全局部收敛性,定理,1.5,设,f,(,x,),在,有根,区间,a,b,上,二,阶导数,存在，且满足,(1),f,(,a,),f,(,b,)0;,则,Newton,迭代,法,收敛于,f,(,x,)=0,在,a,b,内的惟一,根,.,Newton迭代法的全局部收敛性定理1.5 设f(x)在有根,29,例,研究求 的,Newton,公式证明：对一切,且序列,x,k,是单调递减的，从而迭代过程收敛,.,证,因,a,0,，,x,0,0,故,x,k,0 (,k,=1,2,),.,因此对一切,k,1,均有,利用这一结果，得,故,x,k,+1,x,k,即,x,k,单调递减,.,根据单调有界原理知,x,k,收敛,例 研究求 的Newton公式证明：对一切,30,例 设,a,为正实数，试建立求 的,Newton,迭代公式，要求在迭代函数中不用除法运算，并要求当取初值,x,0,满足 时，此算法是收敛的,.,解 考虑方程,则 为此方程的根， ，用,Newton,法求,此方程根的迭代公式为,迭代函数不含除法运算,.,递推可得,例 设a为正实数，试建立求 的Newton迭代公式,31,解得,当 时， ，从而,故 ，此算法收敛,.,解得,32,简化,Newton,法与,Newton,下山法,简化,Newton,法,一般地，取,C,=,f,(,x,0,).,若 是一阶收敛的,.,Newton,下山法,其中,为下山因子，,的选取应满足条件,:,f,(,x,k+,1,),f,(,x,k,),保证所得序列是收敛的,.,简化 Newton法与Newton下山法简化 Newton法,33,重根情形,已知根的重数,r,将,Newton,法修正为,它是求,r,重根的二阶收敛格式,.,记,e,k,+1,=,-,x,k,+1,=,记,由,f,(,)=,f,(,)=,=,f,(,r,-1),(,)=0,有,G,(,j,),(,)=0,j,=0,1,2,r,;,G,(,r,+1),(,)=-,f,(,r,+1),(,),重根情形已知根的重数r,34,在,处将,G,(,x,k,),f,(,x,k,)Taylor,展开,从而它具有二阶收敛格式,.,在处将G(xk), f(xk)Taylor展开,35,根的重数未知,将,Newton,法修正为,其中,u,(,x,),=,0,单根就是,f,(,x,),=,0,的,r,重根，故它是求,f,(,x,),=,0,重根的,二阶收敛格式,.,事实上,为,u,(,x,),=,0,单根,.,根的重数未知,36,例 方程,x,4,-4,x,2,+4=0,的根,=,是二重根，用下列方法求根,(1),Newton,迭代,法,(1.3.11);,(2),修正的,Newton,迭代,法,(1.5.2);,(3),修正的,Newton,迭代,法,(1.5.4),解 三种方法的迭代公式：,Newton,迭代,法,修正的,Newton,迭代,法,(1.5.2),修正的,Newton,迭代,法,(1.5.4,),取初值,x,0,=1.5,计算结果如表：,计算三步方法,(2),和方法,(3),均达到,10,位有效数字，而牛顿法只有线性收敛,，要达到同样精度，需迭代,30,次,.,k,x,k,方法,(1),方法,(2),方法,(3),1,x,1,1.458333333,1.416666667,1.411764706,2,x,2,1.436607143,1.414215686,1.414211438,3,x,3,1.425497619,1.414213562,1.414213562,例 方程x4-4x2+4=0的根= 是二重根，用下,37,弦截法,弦截法,38,弦截法,在方程,f,(,x,)=0,的根,附近任取两初始近似根,x,0,x,1,，由迭代公式,逐次逼近,f,(,x,)=0,的根,，这种求根算法称为弦,截法,.,收敛阶 ，效率指数,弦截法 在方程f(x)=0的根附近任取两初始近似根x0 ,39,迭代加速收敛的方法,迭代加速收敛的方法,40,Aitken,加速收敛方法,当序列,x,k,为线性收敛时,当,k,较大时,称为,Aitken,加速收敛方法,Aitken加速收敛方法当序列xk为线性收敛时,41,Steffensen,加速迭代法,若,x,k,为由不动点迭代法得到的序列，,又称为,Steffensen,加速迭代法,.,当不动点迭代函数,(,x,),在根,的某,邻,域内,具,有,二,阶导数,，,(,)=,L,1,且,L,0,，,则,Steffensen,迭代法是,2,阶收敛的,.,Steffensen加速迭代法若xk为由不动点迭代法得到,42,利用加速方法确定根的重数,r,Newton,迭代法收敛缓慢时，表明有重根,.,当根,为重根时，,Newton,迭代法为线性收敛，,当接近收敛时，,利用加速公式有,利用加速方法确定根的重数rNewton迭代法收敛缓慢时，表明,43,解非线性方程组的,拟,Newton,迭代法,解非线性方程组的,44,非线性方程组的一般形式为,令,上述方程组可表示为,F,(,x,)=,0,非线性方程组的一般形式为,45,给定非线性,方程组,F,(,x,)=,0,，如果有,x,使得,F,(,x,)=,0,，则称,x,为,F,(,x,)=,0,的解,.,当,n,=1,时，,便是单个方程,(,非线性方程,),f,(,x,)=0,给定非线性方程组F(x)=0，如果有x使得F(x)=0，,46,Newton,法,若已知方程组,F,(,x,)=,0,的一个近似解,x,k,=(,x,1,k,x,2,k,x,n,k,),将,F,(,x,),的分量,f,i,(,x,),在,x,k,处用多元,函数,Taylor,展开，取其线性部分有,F,(,x,),F,(,x,k,)+,F,(,x,k,)(,x,-,x,k,),用线性方程组,F,(,x,k,)(,x,-,x,k,)=,F,(,x,k,),的解作为近似解便得解非线性方程组的,Newton,法,x,k,+1,=,x,k, ,F,(,x,k,),-1,F,(,x,k,),记,A,k,=,F,(,x,k,),有,Newton法若已知方程组F(x)=0的一个近似解,47,x,k,+1,=,x,k,-,A,k,-1,F,(,x,k,),其中,为,F,(,x,),的,Jaccobi,矩阵,.,xk+1=xk-Ak-1F(xk),48,例用,Newton,法求解,方程组取,x,0,=(1.5,1.0),解,Jacobi,矩阵,其,Newton,法,为,由,x,0,=(1.5,1.0),逐次迭代求得,x,1,=(1.5,0.75),x,2,=(1.488095, 0.755952),x,3,=(1.488034, 0.755983),x,3,的每一位都是有效数字,.,例用Newton法求解方程组取x0=(1.5,1.0),49,拟,Newton,法,依据,k,的不同的取法可建立不同的拟,Newton,法,.,任何,n,n,秩,m,矩阵都能表示成,UV,T,形式，其中,U,V,为秩,m,的,n,m,矩阵,.,若,n,n,矩阵,非奇异，则,(,+UV,T,),-1,=,-1,-1,U,(,E+V,T,-1,U,),-1,V,T,-1,(SMW,公式,),拟Newton法,50,若,A,k,(,对一切,k,),可逆,记,H,k,=A,k,-1,A,k,+1,-1,=,(,k,+,k,),-1,=,(,k,+U,k,V,k,T,),-1,=,k,-1,k,-1,U,k,(,E+V,k,T,k,-1,U,k,),-1,V,k,T,k,-1,与其互逆的迭代格式为,若Ak (对一切k)可逆,记Hk=Ak-1,51,秩,1,拟,Newton,法,设,A,k,=,u,k,v,k,T,u,k,v,k,R,n,记,r,k,=x,k,+1,-x,k,y,k,=F,(,x,k,+1,),-F,(,x,k,),有,A,k,+1,r,k,=y,k,A,k,+1,=A,k,+u,k,v,k,T, (,A,k,+u,k,v,k,T,),r,k,=y,k,u,k,v,k,T,r,k,=y,k,A,k,r,k,它确定的,A,k,+1,满足拟,Newton,方程,从而建立了秩,1,拟,Newton,法,秩1拟Newton法 设Ak=ukvkT ,ukvkR,52,若,k,非奇异，则,(SM,公式,),H,k,+1,=,H,k,+,H,k,得到与之互逆的秩,1,拟,Newton,法,若k非奇异，则,53,1.Broyden,秩,1,方法,若取,v,k,=r,k,0,，于是得到一个,秩,1,拟,Newton,法,称之为,Broyden,秩,1,方法,.,它具有超线性收敛速度,.,与其互逆的,秩,1,方法,1.Broyden秩1方法,54,2,.,对称,秩,1,方法,若取,v,k,=F,(,x,k,+1,),，,y,k,A,k,r,k,=F,(,x,k,+1,),F,(,x,k,),A,k,r,k,=F,(,x,k,+1,),=v,k,于是由,(2,o,),可得修正矩阵,A,k,对称，若,A,0,对称，所有,A,k,(,k=,0,1,2),都对称,从而得,到一个对称的,秩,1,方法,2.对称秩1方法,55,与其互逆的,秩,1,方法,与其互逆的秩1方法,56,例用逆,Broyden,方法求方程组的解，取,x,0,=(0,0),解,F,(,x,0,)=(-1,3.25),用逆,Broyden,方法迭代求解得,x,1,=(1.0625,-1),，,r,0,=(1.0625,-1),F,(,x,1,)=(1.12890625,2.12890625),y,0,=(2.12890625,-1.1210937),进行第二次迭代 ，迭代,11,次得解,x,11,=(1.54634088332, 1.39117631279),若用,Newton,法求解，取相同的初始值,x,0,，达到同一精度只需迭代,7,次，但它的计算量比逆,Broyden,方法,大得多,.,例用逆Broyden方法求方程组的解，取x0=(0,0,57,