第2章非线性方程求根PPT讲稿.ppt

第2章非线性方程求根第1页，共54页，编辑于2022年，星期一第二章第二章方程求根方程求根我们已经熟悉求解一元一次方程、一元二次方我们已经熟悉求解一元一次方程、一元二次方程以及某些特殊类型的高次代数方程或非线性方程以及某些特殊类型的高次代数方程或非线性方程的方法。这些方法都是代数解法程的方法。这些方法都是代数解法,求出的根是求出的根是方程的准确根。但是在许多实际问题中遇到的方方程的准确根。但是在许多实际问题中遇到的方程程,例如例如代数方程代数方程 x x3 3-x-1=0-x-1=0 或或超越方程超越方程 1引言引言第2页，共54页，编辑于2022年，星期一方程的形式很多方程的形式很多,我们主要讨论一元非线性方程我们主要讨论一元非线性方程,也即也即 f(x)=0(2-1)方方程程(2-1)(2-1)可可以以有有实实根根,也也可可以以有有复复根根或或者者单单根根或或重重根根。（具具体概念不再详述）。体概念不再详述）。当当f(x)f(x)为为二二次次多多项项式式时时，有有韦韦达达求求根根公公式式。同同样样对对于于f(x)f(x)为为三三、四四次次多多项项式式时时，都都可可以以用用求求根根公公式式求求出出根根来来。但但是是当当f(x)f(x)为为更更高高次次的的多多项项式式，或或是是超超越越函函数数时时，无无法法用用求求根根公公式式的的方方法法求求出根。出根。第3页，共54页，编辑于2022年，星期一然而，在实际情况下，我们仅需要获得给定精度的然而，在实际情况下，我们仅需要获得给定精度的近似解近似解。为此。为此在本章中，我们讨论在本章中，我们讨论求根近似解求根近似解的几种方法：的几种方法：f(x)=0（1 1）二分法或对分法）二分法或对分法（2 2）迭代法）迭代法（3 3）牛顿法）牛顿法（4 4）割线法）割线法第4页，共54页，编辑于2022年，星期一方程根的数值计算方程根的数值计算大致可分大致可分三个步骤三个步骤进行进行:(1)(1)判定根的判定根的存在性存在性。(2)(2)确定根的确定根的分布范围分布范围,即将每一个根用区间隔离开来。即将每一个根用区间隔离开来。(3)(3)根的根的精确化精确化,即根据根的初始近似值按某种方法逐步精确即根据根的初始近似值按某种方法逐步精确化化,直至满足预先要求的精度为止。直至满足预先要求的精度为止。第5页，共54页，编辑于2022年，星期一补充：基本概念补充：基本概念有根区间有根区间若若f(x)在在a,b上连续，且上连续，且f(a).f(b)0或或f(x)0)，则则f(x)在在a,b仅有一个实根，仅有一个实根，a,b称称为隔根区间。为隔根区间。2对分法（二分法）对分法（二分法）第6页，共54页，编辑于2022年，星期一1.前提条件前提条件设设f(x)=0满足满足（1）f(x)在在a,b上连续上连续（2）f(a).f(b)0或或f(x)=第11页，共54页，编辑于2022年，星期一例例1：用对分法求方程用对分法求方程f(x)=x3-1.8x2+0.15x+0.65=0在区间在区间0.5，1.25的一个实的一个实根。根。解解:(1)首先看是否满足二分法的前提条件首先看是否满足二分法的前提条件f(x)在在0.5，1.25区间上连续区间上连续f(0.5)=10f(1.25)=-1073741760f(a)f(b)0f(x)=3x2-3.6x+0.150连续，异号，单调，所以方程在此区间内仅有一个实根连续，异号，单调，所以方程在此区间内仅有一个实根x*(2)取取x0=(0.5+1.25)/2=0.875第12页，共54页，编辑于2022年，星期一n xnf(xn)的符号隔根区间00.875+(0.5 ,1.25)11.0625-(0.875 ,1.25)20.96875+(0.875 ,1.0625)31.015625-(0.96875,1.0625)40.9921875+(0.96875,1.015625)561.003906250.998046875-(0.9921875,1.015625）(0.9921875,1.00390625)故所求根的近似值为故所求根的近似值为:X6=(0.9921875+1.00390625)/2=0.998046875所产生的误差为：（根据式2-4得）|x*-x6|=1/27(1.25-0.5)=0.005859第13页，共54页，编辑于2022年，星期一二分法具有简单和易操作的优点，但缺点是收敛慢，不能求重根。二分法具有简单和易操作的优点，但缺点是收敛慢，不能求重根。4.计算步骤计算步骤输入有根区间的端点输入有根区间的端点a,b及预先给定的精度及预先给定的精度;(a+b)/2x;若若f(x)=0,则结束则结束若若f(a)f(x)0,则则xb,转向转向;否则否则xa,转向转向。若若b-a,则输出方程满足精度的根则输出方程满足精度的根x,结束结束;否则转向否则转向。第14页，共54页，编辑于2022年，星期一5、N-S图图第15页，共54页，编辑于2022年，星期一迭代法就是一种利用递推公式进行运算的方法，用其生成迭代法就是一种利用递推公式进行运算的方法，用其生成一个迭代数列，来逼近方程的根。一个迭代数列，来逼近方程的根。一、迭代格式一、迭代格式考察方程考察方程f(x)=0,将将f(x)=0改写改写为下列等价形式为下列等价形式x=(x)并可以做出下列的并可以做出下列的迭代格式迭代格式xk+1=(xk)k=0,1,2,(2-7)则则(x)称为迭代函数称为迭代函数3迭代法迭代法第16页，共54页，编辑于2022年，星期一从给定的初始近似根从给定的初始近似根x0出发出发,按迭代公式按迭代公式(2-7)可以得到一个可以得到一个数列数列x0,x1,x2,xk,如果如果(x)是连续的，且这个数列是连续的，且这个数列xk收敛到收敛到x*,则有则有则则x*就为就为f(x)的根的根，满足，满足x*=(x*)，称，称x*为为的一个不动点的一个不动点（即（即f(x)=0的根）。的根）。根据误差要求，计算到某一步，就可以把根据误差要求，计算到某一步，就可以把xk作为作为f(x)=0的近似值。的近似值。注意注意迭代法的三步曲迭代法的三步曲：改写改写迭代格式迭代格式求数列，且数列收敛，求数列，且数列收敛，(x)连续，则连续，则x*为原方程的根。为原方程的根。kkk第17页，共54页，编辑于2022年，星期一如如方程方程f(X)=X2+X16=0改写改写X=16-X2,则迭代函数则迭代函数(x)=16-X2，迭代公式迭代公式Xk+1=16-Xk2若若:则称则称Xk收敛，否则称收敛，否则称Xk发散发散第18页，共54页，编辑于2022年，星期一例例2求求f(x)=x2-2x-3=0在在0,4之间的一个实根之间的一个实根解解:首先可验证首先可验证 f(x)在在2，4有根有根3（1）将原方程变形为将原方程变形为x=取取(x)=构造迭代公式：构造迭代公式：Xk+1=(k=0,1,2.n)取初始值取初始值x0=4，代入得：，代入得：X1=3.316X2=3.014X3=3.034X4=3.011X5=3.004收敛于根收敛于根3第19页，共54页，编辑于2022年，星期一(2)如果取如果取x=，也即，也即(X)=仍取仍取x0=4按迭代公式按迭代公式xk+1=(k=0,1,2n)可得：可得：X1=6.5X2=19.626X3=191.0.发散发散还可构造还可构造x=x2x-3等等第20页，共54页，编辑于2022年，星期一可见，可见，对于方程对于方程f(x)=0可构造几种不同的迭代函数，即迭代可构造几种不同的迭代函数，即迭代格式不唯一，有的是收敛的，但有的是发散的，随着格式不唯一，有的是收敛的，但有的是发散的，随着k的增的增加，加，Xk并不能趋向一个固定的值，而是变得无穷大，我们不并不能趋向一个固定的值，而是变得无穷大，我们不禁要问：禁要问：迭代格式满足什么条件才能收敛于方程迭代格式满足什么条件才能收敛于方程f(x)=0的根的根?怎样加速其收敛？怎样加速其收敛？误差怎样估计？误差怎样估计？第21页，共54页，编辑于2022年，星期一二、迭代格式的收敛性二、迭代格式的收敛性定理定理1：设：设(x)在在a,b上具有连续的一阶导数，且满足下列条件：上具有连续的一阶导数，且满足下列条件：(1)对任意对任意xa,b，（x）a,b，(2)对任意对任意xa,b，存在常数，存在常数L(0,1)，使，使|(x)|L1，则则(1)方方程程x=(x)在在a,b上上有有唯唯一一的的根根x*,且且对对任任意意初初值值x0a,b,迭迭代代格格式式xk+1=(xk)k=0,1,2,均收敛于均收敛于x*；（2）（3）(k=1,2,)第22页，共54页，编辑于2022年，星期一定理定理1证明：证明：(1)因为因为对任意对任意xa,b，(x)a,b令令g(x)=x-(x)则有：则有：g(a)=a-(a)0,g(b)=b(b)0g(a)g(b)0若此两式中有一个等号成立若此两式中有一个等号成立，在在a,b就存在不动点就存在不动点a或或b,若两式中严格不等号成立若两式中严格不等号成立，则由则由的连续性知：的连续性知：必有必有x*a,b使使 x*-(x*)=0成立成立也即也即x*=（x*），x*就是就是的不动点的不动点(证明至少有一零点证明至少有一零点)第23页，共54页，编辑于2022年，星期一反证反证设设中有两个不动点中有两个不动点x1*x2*a,b则则|x1*-x2*|=|(x1*)-(x2*)|=|()|x1*-x2*|L|x1*-x2*|x1*-x2*|(已知已知0L=ln/lnL第26页，共54页，编辑于2022年，星期一例例2求求f(x)=x2-2x-3=0在在0，4之间的一个实根之间的一个实根解：解：首先可验证首先可验证f(x)在在2，4有根有根3（1）x=取取(X)=取初始值取初始值x0=4得迭代公式得迭代公式Xk+1=(k=0,1,2.n)可算得：可算得：X1=3.316X2=3.014X3=3.034X4=3.011X5=3.004第27页，共54页，编辑于2022年，星期一再来看上面的例子再来看上面的例子f(x)=x2-2x-3有根区间有根区间0，4（1）(X)=(X)=1/对对x0,4有有0(X)1所以所以(X)收敛收敛（满足定理（满足定理1的的2个条件）个条件）（2）(X)=有有(X)=x只在只在0,1内满足内满足(X)则称则称Xk为为P阶收敛，阶收敛，C称为渐进误差常数，称为渐进误差常数，当当P=1，2时时分别称分别称Xk为线形收敛为线形收敛及及平方收敛平方收敛第31页，共54页，编辑于2022年，星期一例例证明证明xk+1=xk(xk2+3a)/(3xk2+a)是计算是计算的三阶方法的三阶方法要证明要证明|xk+1-a|/|xk-a|3为常数为常数第32页，共54页，编辑于2022年，星期一定理定理3：设设x*为为的不动点的不动点，整数，整数p1,(p)在在x*某邻域存在且连续某邻域存在且连续,且满且满足足（k)(x*)=0(k=1,2,.p-1)(p)(x*)0则由则由Xk+1=(Xk)产生的序列产生的序列Xk在在x*的邻域是的邻域是p阶收敛的阶收敛的特别地，（特别地，（p26)(1)当当(x*)0，则为线形收敛，则为线形收敛（2）当）当(x*)=0，”(x*)0，则为平方收敛，则为平方收敛第33页，共54页，编辑于2022年，星期一例例考查考查取取(X)=1+1/x+1/x2时时，用用Xk+1=(Xk）求解）求解x3-x2-x-1=0在区间在区间1，2根的收敛性和收敛阶根的收敛性和收敛阶（x*=1.839)解：解：由由(X)=1+1/x+1/x2得知得知(X)=-（1/x2+2/x3)对任意对任意1，2区间上的区间上的x不满足不满足|(X)|1,也即不满足全局收敛定理也即不满足全局收敛定理但可验证但可验证：当：当x1.7,2时时|(X)|1若取若取x0=2可算出可算出x1=1.91293.x13=1.83929对对(X)=-（1/x2+2/x3)，显然显然(X*)0一阶收敛一阶收敛第34页，共54页，编辑于2022年，星期一二、加速收敛二、加速收敛1.迭代加速公式迭代加速公式设设xk+1*为近似值为近似值xk迭代后的结果迭代后的结果，x*为为x=(x)的根的根则则x*-xk+1*=(x*)-(xk)=()(x*-xk)设设(x)在求根范围内变化不大在求根范围内变化不大即即(x)L，|L|1所以所以x*-xk+1*L(x*-xk)整理得：整理得：x*-Lx*-xk+1*+Lxk+1*=Lxk+1*-Lxk（1-L）x*-（1-L）xk+1*=L（xk+1*-xk）x*-xk+1*(xk+1*-xK)第35页，共54页，编辑于2022年，星期一取第取第k+1次的近似值为次的近似值为:Xk+1=xk+1*+(xk+1*-xK)第36页，共54页，编辑于2022年，星期一得迭代加速公式得迭代加速公式（1）迭代迭代xk+1*=(xk)（2）改进改进Xk+1=xk+1*+(xk+1*-xK)（例（例p28）第37页，共54页，编辑于2022年，星期一2、Aitken加速公式（1）迭代）迭代yk=(xk)(2)校正校正zk=(yk)(3)改进改进xk+1=zk-可达到二阶收敛可达到二阶收敛第38页，共54页，编辑于2022年，星期一第五节、第五节、Newton迭代法迭代法（逐步线性法（逐步线性法,切线法）切线法）1、特点及构造、特点及构造牛顿法是迭代法的一种，牛顿法是迭代法的一种，在单根附近具有较高的收敛速度在单根附近具有较高的收敛速度基本思想：基本思想：（1）设设f(x)=0c2a,b且且f(a).f(b)0f(x)0对任意对任意xa,b(2)任取任取a,b中的一个初始值中的一个初始值xk(k=0,1)把把f(x)在在xk一阶一阶Taylor展开展开f(x)=f(xk)+f(xk)(x-xk)+f(xk)/2!(x-xk)2+(3)取其线性部分取其线性部分f(x)f(xk)+f(xk)(x-xk)=0作为作为f(x)的近似方程的近似方程第39页，共54页，编辑于2022年，星期一（4）由上式得）由上式得X=Xk 取取x作为新的近似值作为新的近似值xk+1得迭代公式得迭代公式-即为牛顿迭代公式即为牛顿迭代公式（x)=x-为迭代函数为迭代函数第40页，共54页，编辑于2022年，星期一2、收敛性、收敛性由由(x)的表达式得：的表达式得：|(x)|=因为因为f(x*)=0所以所以(x*)=0也即也即(x)在根的附近收敛很快在根的附近收敛很快（1）局部收敛定理）局部收敛定理(p30)设设f(x)存在，存在，且且f(x)在方程在方程f(x)=0的根的根x*附近不为零附近不为零，=L1,则则Newton迭代格式收敛迭代格式收敛若若|(x)|=第41页，共54页，编辑于2022年，星期一(2)全局收敛定理（全局收敛定理（p31大范围收敛定理）大范围收敛定理）设设f(x)在在a,b上满足上满足f(a)f(b)0则则Newton迭代序列收敛于迭代序列收敛于f(x)=0在在a,b的唯一根的唯一根-.保证有根保证有根-.保证单根保证单根-.保证凸凹性不变保证凸凹性不变-.保证收敛保证收敛第42页，共54页，编辑于2022年，星期一（3）若）若f(x*)=0,f(x*)0且且f在在x*邻域有二阶连续导数，且不变邻域有二阶连续导数，且不变号，则牛顿迭代法至少二阶收敛，且：号，则牛顿迭代法至少二阶收敛，且：k-第43页，共54页，编辑于2022年，星期一3、计算步骤、计算步骤切线法是非线性方程线性化的方法。其计算步骤为切线法是非线性方程线性化的方法。其计算步骤为:给出初始近似根给出初始近似根x0及精度及精度。计算计算若若x1-x0,则转向则转向;否则否则x1-x0,转向转向。输出满足精度的根输出满足精度的根x1,结束。结束。切线法的计算框图见下图切线法的计算框图见下图第44页，共54页，编辑于2022年，星期一第45页，共54页，编辑于2022年，星期一例例1用用Newton迭代法迭代法求方程求方程x-sinx=0.5在在1,2上的根上的根，使其精确到使其精确到104解解：f(x)=x-sinx0.5f(1)=-0.340f(x)=1-cosx0,f(x)=sinx0满足条件满足条件迭代公式迭代公式Xk+1=xk-(xk-sinxk0.5)/(1-cosxk)取取x0=2(f“(x0)f(x0)0)可求出可求出x1=1.5829x2=1.5009x3=1.4973x4=1.4973迭代迭代4次就达到精度要求次就达到精度要求第46页，共54页，编辑于2022年，星期一例例2用用Newton迭代法求方程迭代法求方程f(x)=x3-x-1在在x0=1.5附近的一附近的一个根个根，结果要求精确到结果要求精确到4位有效数字位有效数字解解：可验证有根可验证有根取取x0=1.5按迭代公式按迭代公式xk+1=xk-(xk3-xk-1)/(3xk2-1)计算计算x1=1.3478x2=1.3254x3=1.33072x4=1.3247x5=1.3247|x4x5|0)的平方根的平方根取取x0=2得：得：X1=1.75x2=1.73214,x3=1.7320508取取x*1.7321第49页，共54页，编辑于2022年，星期一4、重根情形、重根情形设设x*是是f(x)=0的的m重根重根（m1)则则f(x)=(xx*)mg(x)g(x*)0由由(x)=x可算出可算出(x)=1-1/m0且且|(x)|1此时，此时，Newton迭代法只能线性收敛迭代法只能线性收敛若改取若改取（1）(x)=xm易验证易验证(x*)=0此时，此时，Newton迭代法至少二阶收敛迭代法至少二阶收敛第50页，共54页，编辑于2022年，星期一（2）令令u(x)=f(x)/f(x)(x)=xu(x)/u(x)可以验证至少二阶收敛可以验证至少二阶收敛第51页，共54页，编辑于2022年，星期一6弦截法切切线线法法迭迭代代简简单单,收收敛敛速速度度也也较较快快,但但就就是是需需要要计计算算导导数数f(x),有有时时使使用用会会带带来来麻麻烦烦。弦弦截截法法用用差差商商近近似似代代替替导导数数,避避免免了了切线法的不足切线法的不足.第52页，共54页，编辑于2022年，星期一几何意义几何意义:用割线与用割线与x轴的交点代替曲线与轴的交点代替曲线与x轴的交点轴的交点第53页，共54页，编辑于2022年，星期一练习：练习：1、(x）=x+(x2-5),若使迭代法若使迭代法Xk+1=(Xk)K=0,1,2局部收敛到局部收敛到x*=5则则的取值范围是：？的取值范围是：？2、用迭代法、用迭代法xk+1=xk-(xk)f(xk)求方程求方程f(x)=x3-x2x1=0的根，若使迭代序列的根，若使迭代序列xk具有平方收敛，则具有平方收敛，则(xk)=？3、求、求x22x+1=0的根的的根的Newton迭代法是：？迭代法是：？其收敛阶是？其收敛阶是？第54页，共54页，编辑于2022年，星期一