数值分析非线性方程求根省公共课一等奖全国赛课获奖课件.pptx

上页上页下页下页 第4章 非线性方程求根4.1 实根对分法实根对分法4.2 迭代法及其收敛性迭代法及其收敛性4.3 牛顿法牛顿法4.4 弦截法弦截法4.5 解非线性方程组牛顿迭代法解非线性方程组牛顿迭代法第1页上页上页下页下页本章主要讨论本章主要讨论单变量非线性方程单变量非线性方程f(x)=0 (1.1)求根问题，这里求根问题，这里xR,f(x)Ca,b.比如比如代数方程代数方程 x5-x3+24x+1=0,超越方程超越方程 sin(5x2)+e-x=0.第2页上页上页下页下页 对于不高于对于不高于4次代数方程已经有求根公式，而次代数方程已经有求根公式，而高于高于4次代数方程则无准确求根公式，至于超越方次代数方程则无准确求根公式，至于超越方程程 就更无法求出其准确解，所以，怎样求得满足就更无法求出其准确解，所以，怎样求得满足一定精度要求方程近似根也就成为迫切需要处理一定精度要求方程近似根也就成为迫切需要处理问题，为此，我们介绍几个常见非线性方程近似问题，为此，我们介绍几个常见非线性方程近似求根方法求根方法.先介绍几个和非线性方程相关定义：先介绍几个和非线性方程相关定义：第3页上页上页下页下页方程方程f(x)=0根根x*，又称为函数又称为函数f(x)零点零点，它使得，它使得f(x*)=0，若，若f(x)可分解为可分解为f(x)=(x-x*)mg(x)，其中其中m为正整数，且为正整数，且g(x*)0.当当m=1时，则称时，则称x*为单为单根，若根，若m1称称x*为为(1.1)m重根重根，或，或x*为函数为函数f(x)m重零重零点点.若若x*是是f(x)m重零点重零点，且，且g(x)充分光滑，则充分光滑，则第4页上页上页下页下页4.1 4.1 实根对分法实根对分法对分法也称为二分法，是求方程近似解一个简单对分法也称为二分法，是求方程近似解一个简单直观方法。应用对分法前提条件是：直观方法。应用对分法前提条件是：设设f(x)在区间在区间a,b上连续上连续,f(a)f(b)0,则在则在 a,b内有方程根内有方程根.计算中经过对分区间缩小区间范围，搜索零计算中经过对分区间缩小区间范围，搜索零 点位置。点位置。第5页上页上页下页下页算法简述：算法简述：取取a,b中点中点 将区间一将区间一分为二分为二.若若 f(x0)=0,则则x0就是方程根就是方程根,不然判别根不然判别根 x*在在 x0 左侧左侧还是还是右侧右侧.若若f(a)f(x0)0,则则x*(a,x0),令令 a1=a,b1=x0;若若f(x0)f(b)0,则则x*(x0,b),令令 a1=x0,b1=b.不论出现哪种情况不论出现哪种情况,(a1,b1)均为均为新有根区间新有根区间,它它长度只有原有根区间长度二分之一长度只有原有根区间长度二分之一,到达了到达了压缩有根压缩有根区间区间目标目标.第6页上页上页下页下页 对压缩了有根区间对压缩了有根区间,又可实施一样步骤又可实施一样步骤,再压缩再压缩.如此重复进行如此重复进行,即可得一系列即可得一系列有根区间套有根区间套 因为每一区间都是前一区间二分之一，所以区间因为每一区间都是前一区间二分之一，所以区间an,bn长度为长度为若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去.当当 n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x*，显然，显然x*就是所求就是所求根根.第7页上页上页下页下页abx1x2ab什么时候停顿？什么时候停顿？或或x*第8页上页上页下页下页 例例例例1 1 用二分法求用二分法求 在在(1,2)内根，要求绝对误差不超出内根，要求绝对误差不超出 解解解解：f(1)=-50 -(1,2)+f(1.25)0 (1.25,1.375)f(1.313)0 (1.313,1.375)f(1.344)0 (1.344,1.375)f(1.360)0 (1.360,1.368)f(1.5)0 (1,1.5)第9页上页上页下页下页 二分法二分法优点优点是算法简单，且总是收敛，是算法简单，且总是收敛，缺点缺点是收是收敛太慢，故普通不单独将其用于求根，只是用其为根敛太慢，故普通不单独将其用于求根，只是用其为根求得一个很好近似值求得一个很好近似值.二分法计算步骤二分法计算步骤:第10页上页上页下页下页步骤步骤1 准备准备 计算函数计算函数f(x)在区间在区间a,b端点处值端点处值f(a),f(b).若若f(a)f(a+b)/2)0,则以则以(a+b)/2代替代替b，不然以，不然以(a+b)/2代替代替a.步骤步骤2 二分二分 计算函数计算函数f(x)在区间中点在区间中点(a+b)/2处处值值f(a+b)/2).步骤步骤3 判断判断 若若f(a+b)/2)=0，则，则(a+b)/2即是根，即是根，计算过程结束，不然检验计算过程结束，不然检验.重复执行步骤重复执行步骤2和步骤和步骤3，直到区间，直到区间a,b长度小长度小于允许误差于允许误差，此时中点，此时中点(a+b)/2即为所求近似根即为所求近似根.第11页上页上页下页下页4.2 4.2 迭代法迭代法f(x)=0 x=g(x)等价变换等价变换f(x)根根g(x)不动点不动点从一个初值从一个初值 x0 出发，计算出发，计算 x1=g(x0),x2=g(x1),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*使使得得 ，且，且 g 连续，则由连续，则由 可知可知 x*=g(x*)，即，即x*是是 g 不动点，也就是不动点，也就是f 根。根。第12页上页上页下页下页迭代法基本步骤以下：迭代法基本步骤以下：1、给出方程局部等价形式、给出方程局部等价形式2、取适当初值，产生迭代序列、取适当初值，产生迭代序列3、求极限、求极限易知，该值为方程根易知，该值为方程根.一定收敛吗？一定收敛吗？第13页上页上页下页下页分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x0=1进行进行迭代计算，结果以下：迭代计算，结果以下：解解 对方程进行以下三种变形：对方程进行以下三种变形：先看下面例子：先看下面例子：用迭代法求方程用迭代法求方程x4+2x2-x-3=0 在区在区间间1,1.2内实根内实根.第14页上页上页下页下页准确根准确根 x*=1.124123029。由此可见，将由此可见，将 f(x)=0化为等价方程化为等价方程x=(x)方式是不唯一。方式是不唯一。迭迭代公式不一样代公式不一样,收敛情况也不一样收敛情况也不一样.第二种公式比第一个公式第二种公式比第一个公式收敛快得多收敛快得多,而第三种公式而第三种公式不收敛不收敛.为此我们首先要研究为此我们首先要研究(x)不定点存在性及迭代法收敛性不定点存在性及迭代法收敛性.第15页上页上页下页下页 首先考查首先考查(x)在在a,b上不动点存在唯一性上不动点存在唯一性.定理定理1 设设(x)Ca,b满足以下两个条件：满足以下两个条件：1 对任意对任意xa,b有有a(x)b.2 存在正数存在正数La及及(b)0,f(b)=(b)-b0,由连续函数性质可知存在由连续函数性质可知存在 x*(a,b)使使 f(x*)=0，即即x*=(x*)，x*即为即为(x)不动点不动点.再证不动点再证不动点唯一性唯一性.设设x1*,x2*a,b都是都是(x)不动点，则由不动点，则由(2.4)得得引出矛盾，故引出矛盾，故(x)不动点只能是唯一不动点只能是唯一.证毕证毕.在在(x)不动点存在唯一情况下，可得到迭代法不动点存在唯一情况下，可得到迭代法(2.2)收敛一个收敛一个充分条件充分条件.第17页上页上页下页下页 定理定理2 设设(x)Ca,b满足定理满足定理1中两个条件，中两个条件，则对任意则对任意x0a,b，由，由(2.2)得到迭代序列得到迭代序列xk收敛收敛到不动点到不动点x*，并有，并有误差预计式误差预计式 证实证实 设设x*a,b是是(x)在在a,b上唯一不动点上唯一不动点,由条件由条件1，可知，可知xka,b，再由，再由(2.4)得得因因0L1时称时称超线性收敛超线性收敛，p=2时称时称平方收敛平方收敛.第27页上页上页下页下页 定理定理4 对于迭代过程对于迭代过程xk+1=(xk)，假如，假如(p)(x)在在所求根所求根x*邻近连续，而且邻近连续，而且则该迭代过程在则该迭代过程在x*邻近是邻近是p阶收敛阶收敛.证实证实 因为因为(x*)=0，依据定理，依据定理3马上能够断定迭马上能够断定迭代过程代过程xk+1=(xk)含有局部收敛性含有局部收敛性.再将再将(xk)在根在根x*处做泰勒展开处做泰勒展开,利用条件利用条件(2.4),则有则有注意到注意到(xk)=xk+1，(x*)=x*，由上式得，由上式得第28页上页上页下页下页所以对迭代误差，令所以对迭代误差，令k时有时有这表明迭代过程这表明迭代过程xk+1=(xk)确实为确实为p阶收敛阶收敛.证毕证毕.上述定理告诉我们，迭代过程收敛速度依赖于迭上述定理告诉我们，迭代过程收敛速度依赖于迭代函数代函数(x)选取选取.假如假如xa,b但但 (x)0时，则该时，则该迭代过程只可能是线性收敛迭代过程只可能是线性收敛.第29页上页上页下页下页三阶方法三阶方法.假设假设 x0 充分靠近充分靠近 x*,求求 证实证实 首先由泰勒展式可得首先由泰勒展式可得 例子例子 证实迭代公式证实迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三阶方法迭代公式是三阶方法.第30页上页上页下页下页由上述讨论可知，结构满足收敛定理条件等价形由上述讨论可知，结构满足收敛定理条件等价形式普通难于做到。要结构收敛迭代格式有两个要素：式普通难于做到。要结构收敛迭代格式有两个要素：1.等价形式等价形式2.初值选取初值选取下面我们开始介绍若干种迭代法结构方法下面我们开始介绍若干种迭代法结构方法第31页上页上页下页下页4.3 Newton 法 对于方程对于方程f(x)=0，能够结构各种迭代格式。牛顿，能够结构各种迭代格式。牛顿法其基本思想是将非线性方程法其基本思想是将非线性方程f(x)=0做做Taylor展开，展开，取其线性部分结构一个迭代格式。实质上是一个线性取其线性部分结构一个迭代格式。实质上是一个线性化方法，化方法，1.Newton法迭代公式法迭代公式 设已知方程设已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一阶泰勒多项式近似，表示为用一阶泰勒多项式近似，表示为第32页上页上页下页下页当当f(x0)0时，方程时，方程f(x)=0可用线性方程可用线性方程(切线切线)近近似代替，即似代替，即 f(x0)+f(x0)(x-x0)=0.(4.1)解此线性方程得解此线性方程得得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)迭代公式迭代公式.第33页上页上页下页下页牛顿法有显然牛顿法有显然几何意义几何意义，方程，方程f(x)=0根根x*可解释可解释为曲线为曲线y=f(x)与与x轴交点横坐标轴交点横坐标.设设xk是根是根x*某个近似某个近似值，过曲线值，过曲线y=f(x)上横坐标为上横坐标为xk点点Pk引切线，并将该引切线，并将该切线与切线与x轴交点横坐标轴交点横坐标xk+1作为作为x*新近似值新近似值.注意到切注意到切线方程为线方程为这么求得值这么求得值xk+1必满足必满足(4.1),从而就是牛顿公从而就是牛顿公式式(4.2)计算结果计算结果.因为因为这种几何背景，所以牛顿这种几何背景，所以牛顿迭代法也称迭代法也称切线法切线法.xyx*xky=f(x)xk+1PkPk+1xk+2第34页上页上页下页下页2.牛顿迭代法收敛性牛顿迭代法收敛性设设x*是是f(x)一个单根，即一个单根，即f(x*)=0，f(x*)0,有有牛顿迭代法迭代函数为牛顿迭代法迭代函数为由定理由定理4(2.9)式可得式可得(4.3)式式第35页上页上页下页下页由此得到，当由此得到，当x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x*邻邻近是近是二阶二阶(平方平方)收敛收敛.关于关于x*为为重根重根时，牛顿迭代法在根时，牛顿迭代法在根x*邻近收敛性邻近收敛性在后面讨论在后面讨论.定理定理(局部收敛性局部收敛性)设设f C2a,b,若若x*为为f(x)在在a,b上根，且上根，且f(x*)0，则存在，则存在x*邻域邻域U,使得任取使得任取初值初值x0 U，牛顿法产生序列，牛顿法产生序列xk收敛到收敛到x*，且满足，且满足即有下面局部收敛性定理即有下面局部收敛性定理.第36页上页上页下页下页(1)选定初值选定初值x0,计算计算f(x0),f (x0)计算步骤计算步骤(2)按公式按公式 迭代迭代 得新近似值得新近似值xk+1(3)对于给定允许精度对于给定允许精度，假如假如 则终止迭代，取则终止迭代，取 ;不然不然k=k+1，再转再转 步骤步骤(2)计算计算允许精度允许精度最大迭代最大迭代次数次数迭代信息迭代信息第37页上页上页下页下页 解解 将原方程化为将原方程化为xex=0，则，则牛顿迭代公式为牛顿迭代公式为取取 x0=0.5，迭代得，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.f(x)=xex，f(x)=1+ex，例例1 用牛顿迭代法求方程用牛顿迭代法求方程x=ex在在x=0.5附近根附近根.第38页上页上页下页下页例题例题2 2：用Newton法求方程 根,要求迭代格式一：迭代格式一：迭代格式二：迭代格式二：取初值取初值x x0 00.00.0,计算以下：计算以下：对迭代格式一对迭代格式一:the iterative number is 27,the numerical solution is 0.442852706对迭代格式二对迭代格式二:the iterative number is 3,the numerical solution is 0.442854401第39页上页上页下页下页例3.求函数 正实根。精度要求：从图形中我们能够从图形中我们能够看出：看出：在在x=7和和x=8 之之间有一单根；间有一单根；在在x=1和和x=2 之之间有一重根。间有一重根。用用Matlab画图，查看根分布情形画图，查看根分布情形第40页上页上页下页下页初值x08.0 时,计算是单根,The iterative number is 28,The numerical solution is 7.600001481初值x01.0,计算是重根,The iterative number is 1356,The numerical solution is 1.198631981取初值x08.0,用牛顿迭代公式计算以下：取初值x01.0,用牛顿迭代公式计算以下：第41页上页上页下页下页重根情形重根情形当当x*为为f(x)m(m0)重根重根时，则时，则f(x)可表为可表为 f(x)=(x-x*)mg(x).其中其中g(x*)0，此时用牛顿迭代法，此时用牛顿迭代法(4.2)求求x*依然收敛，依然收敛，只是只是收敛速度将大大减慢收敛速度将大大减慢.实际上，因为迭代公式实际上，因为迭代公式令令ek=xkx*，则，则第42页上页上页下页下页可见用牛顿法求方程重根时仅为可见用牛顿法求方程重根时仅为线性收敛线性收敛.从而有从而有两种两种提升求重根收敛速度提升求重根收敛速度方法方法：1)取以下迭代函数取以下迭代函数得到迭代公式得到迭代公式第43页上页上页下页下页下面介绍一个下面介绍一个求重数求重数m方法方法，令，令则则求求m重根含有重根含有2阶收敛阶收敛.但要知道但要知道x*重数重数m.由式由式得得所以得预计所以得预计m式子为式子为第44页上页上页下页下页对对f(x)=(x-x*)mg(x),g(x*)0，令函数，令函数则为求则为求(x)=0单根单根x*问题，对它用牛顿法是二阶问题，对它用牛顿法是二阶(平方平方)收敛收敛.其迭代函数为其迭代函数为2)将求重根问题化为求单根问题将求重根问题化为求单根问题.从而结构出迭代方法为从而结构出迭代方法为第45页上页上页下页下页 例例8 用牛顿迭代法求函数用牛顿迭代法求函数 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95附近之根附近之根.解解 取取x0=0.95 用牛顿迭代法求用牛顿迭代法求得得xk见右表见右表.可可见见xk收敛很慢收敛很慢.kxkkm01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511第46页上页上页下页下页由重根数由重根数m=2,用用(4.13)式加速法，作式加速法，作求得求得 x0=0.95,x1=0.9988559,x2=x3=1.收敛速度大大加紧于直接用牛顿迭代公式收敛速度大大加紧于直接用牛顿迭代公式.第47页上页上页下页下页4.4 弦截法将将NewtonNewton迭代中导数，用差商代替，有格式迭代中导数，用差商代替，有格式是是2 2步格式。收敛速度比步格式。收敛速度比NewtonNewton迭代慢迭代慢x0 x1切线切线 割线割线 第48页上页上页下页下页课外：课外：抛物线法抛物线法设已知方程设已知方程f(x)=0三个近似根三个近似根xk,xk-1,xk-2，我们以，我们以这三点为节点结构二次插值多项式这三点为节点结构二次插值多项式p2(x)，并适当选取，并适当选取p2(x)一个零点一个零点xk+1作为新近似根，这么确定迭代过程作为新近似根，这么确定迭代过程称为称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法.在几何图形在几何图形上上,这种方法基本思想是用抛物线这种方法基本思想是用抛物线y=p2(x)与与x轴交点轴交点xk+1作为所求根作为所求根x*近似位置近似位置.第49页上页上页下页下页Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1抛物线法抛物线法几何意义几何意义见下面图形见下面图形.第50页上页上页下页下页现在推导抛物线法计算公式现在推导抛物线法计算公式.插值多项式插值多项式有两个零点有两个零点式中式中因了在因了在(5.3)式定出一个值式定出一个值xk+1，我们需要讨论根，我们需要讨论根式前正负号取舍问题式前正负号取舍问题.在在xk,xk-1,xk-2三个近似值中，自然假定三个近似值中，自然假定xk更靠近更靠近所求根所求根x*，这时，为了确保精度，我们选，这时，为了确保精度，我们选(5.3)式中式中靠近靠近xk一个值作为新近似根一个值作为新近似根xk+1.为此，只要取根式为此，只要取根式前符号与前符号与符号相同符号相同.第51页上页上页下页下页 例例11 用抛物线法求解方程用抛物线法求解方程f(x)=xex-1=0.解解 取取x0=0.5,x1=0.6,x2=0.56532开始，计算得开始，计算得f(x0)=-0.175639,f(x1)=0.093271,f(x2)=-0.005031.fx1,x0=2.68910,fx2,x1=2.83373,fx2,x1,x0=2.21418.故故代入代入(5.3)式求得式求得以上计算表明，抛物线法比弦截法收敛更加快以上计算表明，抛物线法比弦截法收敛更加快.第52页上页上页下页下页实际上实际上,在一定条件下能够证实在一定条件下能够证实,对于抛物线法，对于抛物线法，迭代误差有以下渐近关系式迭代误差有以下渐近关系式由此式可见抛物线法也是超线性收敛，其收敛阶是由此式可见抛物线法也是超线性收敛，其收敛阶是p=1.840(是方程是方程3-2-1=0根根)，收敛速度比弦截法更，收敛速度比弦截法更靠近于牛顿法靠近于牛顿法.从从(5.3)式看到，即使式看到，即使 xk,xk-1,xk-2 均为实数，均为实数，xk+1也能够是复数，所以抛物线法适合用于求多项式实也能够是复数，所以抛物线法适合用于求多项式实根和复根根和复根.第53页上页上页下页下页4.5 4.5 解非线性方程组牛顿迭代法解非线性方程组牛顿迭代法考查方程组考查方程组其中其中f1,fn均为均为(x1,xn)多元函数多元函数.若用向量记号若用向量记号记记x=(x1,xn)TRn,F=(f1,fn)T,(6.1)就可写成就可写成 F(x)=0.(6.2)第54页上页上页下页下页当当n2，且，且 f1,fn 中最少有一个是自变量中最少有一个是自变量 x1,xn 非线性函数，则称方程组非线性函数，则称方程组(6.1)为为非线性方程组非线性方程组.非非线性方程组求根问题是前面介绍方程线性方程组求根问题是前面介绍方程(即即n=2)求根直求根直接推广，实际上只要把前面介绍接推广，实际上只要把前面介绍单变量函数单变量函数f(x)看成看成向量函数向量函数F(x)，则可得，则可得向量方程向量方程(6.2)一个近似根一个近似根x(k)=(x1(k),.,xn(k)T，将函数，将函数F(x)分量分量fi(x)(i=1,n)在在x(k)用多元函数泰勒展开，并取其线性部分，则可表用多元函数泰勒展开，并取其线性部分，则可表示为示为.第55页上页上页下页下页令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组其中其中称为称为F(x)雅可比雅可比(Jacobi)矩阵矩阵.第56页上页上页下页下页求解线性方程组求解线性方程组(6.3)，并记解为，并记解为x(k+1)，则得，则得这就是这就是解非线性方程组解非线性方程组(6.2)牛顿迭代法牛顿迭代法.例例12 求解方程组求解方程组给定初值给定初值x(0)=(1.5,1.0)T，用牛顿法求解，用牛顿法求解.解解 先求先求Jacobi矩阵矩阵第57页上页上页下页下页用牛顿法用牛顿法(6.5)得得即即第58页上页上页下页下页由由x(0)=(1.5,1.0)T逐次迭代得到逐次迭代得到x(3)每一位都是有效数字每一位都是有效数字.第59页