第六章 非线性方程求根优秀PPT.ppt

《第六章 非线性方程求根优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第六章 非线性方程求根优秀PPT.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 非线性方程求根第一页，本课件共有58页*2第六章第六章 非线性方程求根非线性方程求根数 值 分 析（Numerical Analysis）第二页，本课件共有58页 非线性科学是当今科学发展的一个重要研究方向，而非线性方程的非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。无穷组解无穷组解无解无解一个解一个解两个解两个解四个解四个解一、引言一、引言*3第三页，本课件共有58页求根问题包括下面三个问题：求根问题包括下面三个问题：v 根的存在性根的存在性：即：即f(

2、x)=0有没有根？若有，有有没有根？若有，有 几个根？几个根？v 哪儿有根哪儿有根？确定有根区间？确定有根区间v 根的精确化根的精确化：已知一个根的近似值后，能否：已知一个根的近似值后，能否将它精确到足够精度？将它精确到足够精度？*4第四页，本课件共有58页【定理定理1】设函数设函数 f(x)在区间在区间a,b上连续上连续，如果如果f(a)f(b)0f(a)f(b)=0f(a)=0打印打印b,k打印打印a,k结束结束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m,ka=mb=m结束结束k=k+1是是是是否否否否 输入输入 k=012*第十二页，本课件共有58页【例例2】求方程

3、求方程 在区间在区间(1.0,1.5)内的一个内的一个实根，要求准确到小数点后的第二位。实根，要求准确到小数点后的第二位。kakbkxkf(xk)的符号的符号01.01.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-*13第十三页，本课件共有58页1 1简单迭代法简单迭代法f(x)=0 x=g(x)等价变换等价变换三、迭代法三、迭代法f(x)的根的根g(x)的不动点的不动点从一个初值从一个初值 x0 出发，计算

4、出发，计算 x1=g(x0),x2=g(x1),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*，使得，使得 ，且，且 g 连续，则由连续，则由 可知可知 x*=g(x*)，即，即x*是是 g 的不动点，也就是的不动点，也就是f 的根。的根。思思路路*14第十四页，本课件共有58页x1=0.4771x2=0.3939x6=0.3758x7=0.3758迭代过程的迭代过程的收敛性收敛性?【例例3】求方程求方程的一个根。的一个根。迭代格式迭代格式*15第十五页，本课件共有58页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0

5、 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1*16第十六页，本课件共有58页【定理定理2】如果如果 (x)满足下列条件满足下列条件（1 1）当）当x a,b时，时，(x)a,b（2 2）对任意）对任意x a,b，存在，存在0 L1时，称方法为时，称方法为超线性超线性收敛。收敛。v当当p=2时，称方法为时，称方法为平方平方（二次）收敛；（二次）收敛；34*第三十四页，本课件共有58页35【定理定理4】对于迭代过程对于迭代过程 ，如果，如果 在所求在所求根根 的附近连续的附近连续，且：，且：则该迭代过程在点则该迭代过程在点 附近是附近是p阶收敛阶收敛的。的。v 迭代过程收敛

6、速度依赖于迭代函数迭代过程收敛速度依赖于迭代函数 的选取；的选取；v 当当 时，时，则该迭代过程的收敛速度只可能是，则该迭代过程的收敛速度只可能是线线性性的；的；v 当当x*是单根时，是单根时，牛顿法牛顿法在在x*附近至少是附近至少是平方平方收敛的收敛的？*第三十五页，本课件共有58页注：注：注：注：Newton法的收敛性法的收敛性依赖于依赖于x0 的选取。的选取。x*x0 x0 x0*36第三十六页，本课件共有58页4、牛顿法的应用举例、牛顿法的应用举例对任给的对任给的正数正数a,应用牛顿法解二次方程应用牛顿法解二次方程 ，可导出开平方，可导出开平方 的值。的值。*37选取迭代格式为选取迭代

7、格式为这种迭代格式对任意的初值这种迭代格式对任意的初值 都是收敛的都是收敛的！【例例】求求 ，取，取x0=10第三十七页，本课件共有58页5、牛顿法的变形牛顿法的变形-牛顿下山法牛顿下山法计算：计算：使得具有单调性：使得具有单调性：满足这项要求的算法称之为满足这项要求的算法称之为下山法。下山法。v 将牛顿法和下山法结合起来使用，即可在将牛顿法和下山法结合起来使用，即可在下山法下山法保证保证函数函数值稳定值稳定下下降降的前提下，用的前提下，用牛顿法牛顿法加快收敛速度加快收敛速度。v 其中的其中的 称为称为下山因子下山因子。下山因子的选择是个逐步搜索的过程。从下山因子的选择是个逐步搜索的过程。从

8、开始反复将其减开始反复将其减半，如果能找到值半，如果能找到值 使得单调性条件成立，则称使得单调性条件成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”。保证全局收敛！保证全局收敛！*38第三十八页，本课件共有58页*39P161-162 5,7(1)(2),12,13作业作业第三十九页，本课件共有58页*40实验二 实验名称实验名称：函数逼近与数据拟合函数逼近与数据拟合 实验目的实验目的：考察学生综合运用考察学生综合运用 Matlab 进行编程的能力。进行编程的能力。根据最佳平方逼近及最根据最佳平方逼近及最 小二乘算法要求，自行设计编程方小二乘算法要求，自行设计编程方案，实现算法。

9、掌握案，实现算法。掌握 Matlab 中的中的 polyfit、lsqcurvefit、nlinfit等函数，并用这些函数解决实际问题等函数，并用这些函数解决实际问题第四十页，本课件共有58页*41实验任务：实验任务：v写出相应的写出相应的MATLAB程序程序v给出实验结果给出实验结果v对实验结果进行分析和讨论对实验结果进行分析和讨论v写出相应的实验报告写出相应的实验报告实验步骤实验步骤：v用用Matlab语言实现最佳平方逼近及最小二乘算法语言实现最佳平方逼近及最小二乘算法v X=0.1,0.2,0.15,0,-0.2,0.3,Y=0.95,0.84,0.86,1.06,1.50,0.72。用

10、以上数据拟合非线性函数。用以上数据拟合非线性函数y=aebx第四十一页，本课件共有58页五、弦截法与抛物线法五、弦截法与抛物线法421.引入引入 用牛顿法求方程用牛顿法求方程f(x)=0的根时，每步除计算的根时，每步除计算f(xk)外还要算外还要算f(xk)，当函数，当函数f(x)比较复杂时，计算比较复杂时，计算f(x)往往比较困难。那么我们能往往比较困难。那么我们能否利用已知的信息，例如：否利用已知的信息，例如：xk,xk-1，xk-2,及其函数值及其函数值f(xk),f(xk-1),f(xk-2),来回避导数值来回避导数值f(xk)的计算呢？的计算呢？本节的两种方法是建立在本节的两种方法是

11、建立在插值原理插值原理基础上的。回忆一下插值法！设基础上的。回忆一下插值法！设 是是 的一组近似根，我们利用函数值的一组近似根，我们利用函数值 构构造造插值多项式插值多项式Pr(x)，并适当选取用，并适当选取用Pr(x)=0的根作为方程的根作为方程f(x)=0的新的的新的近似根近似根xk+1。当当r=1时，就是弦截法，当时，就是弦截法，当r=2时，就是抛物线法。时，就是抛物线法。*第四十二页，本课件共有58页 设设 是是 的近似根，我们利用的近似根，我们利用 构造一次构造一次插值多项式插值多项式P1(x)，并用，并用P1(x)=0的根作为方程的根作为方程f(x)=0的新的的新的近似根近似根xk

12、+1，由于，由于因此有因此有:2、弦截法（割线法）、弦截法（割线法）差商？与导数的关系差商？与导数的关系？*43第四十三页，本课件共有58页这样导出的迭代公式这样导出的迭代公式(2)可以看做牛顿公式可以看做牛顿公式中的导数中的导数 用用差商差商 取代的结果取代的结果.(2)式有几何意义吗？式有几何意义吗？*44第四十四页，本课件共有58页Ox*xk+1xkPkxk-1yPk-1按按(2)式求得式求得xk+1实际上是两实际上是两点弦线点弦线 与与x轴交点的轴交点的横坐标。这种算法因此而横坐标。这种算法因此而形象地称为形象地称为弦截弦截(双点割线双点割线)法法.f(x)每步只用一个新点每步只用一个

13、新点xk的值，此的值，此方法称为方法称为单点割线法单点割线法。如果把如果把(2)式中的式中的xk-1改为改为x0，即迭代公式为，即：即迭代公式为，即：*45第四十五页，本课件共有58页v 线性化线性化v 切线法只用到前一步的函数值，而弦截法需要用到前两步的函切线法只用到前一步的函数值，而弦截法需要用到前两步的函数值。其收敛速度一般比牛顿法慢，但比线性收敛的方法快。在数值。其收敛速度一般比牛顿法慢，但比线性收敛的方法快。在与牛顿法具有同等的前提下，弦截法具有局部收敛性，并且收敛与牛顿法具有同等的前提下，弦截法具有局部收敛性，并且收敛阶阶v由于弦截法是两步法，它不属于不动点迭代，因此不能用由于弦截

14、法是两步法，它不属于不动点迭代，因此不能用不动点迭代理论证明它的收敛性。不动点迭代理论证明它的收敛性。*46【P154 P154 例例】用弦截法解方程用弦截法解方程 弦截法和切线法的弦截法和切线法的联系联系和和区别区别：第四十六页，本课件共有58页计算结果表计算结果表k xk xk-xk-10 0.5 1 0.6 0.12 0.56532 -0.034683 0.56709 0.001774 0.56714 0.00005从表中可以看出从表中可以看出弦截弦截法法的收敛速度也是相的收敛速度也是相当快的，迭代到第当快的，迭代到第4步步就得到精度就得到精度 的的结果。结果。解解1：*47第四十七页，

15、本课件共有58页取初值取初值 x0=0.5，牛顿法迭代牛顿法迭代结果见下表结果见下表k 0 1 2 3xk 0.5 0.57102 0.56716 0.56714*48解解2：第四十八页，本课件共有58页【定理定理6.4】假设假设f(x)在根在根x*的邻域的邻域 内具有二阶连内具有二阶连续导数，且对于任意续导数，且对于任意 ，有，有 ，又初值，又初值 ，那，那么当么当邻域邻域 充分充分小时，弦截法将按阶小时，弦截法将按阶 收敛到根收敛到根x*。*49弦截法是超线性收敛的！弦截法是超线性收敛的！第四十九页，本课件共有58页3、抛物线法抛物线法设已知方程设已知方程f(x)=0的三个近似根的三个近似

16、根xk,xk-1,xk-2，我们以，我们以这三点为插值节点构造二次插值多项式这三点为插值节点构造二次插值多项式P2(x)，并适当，并适当选取选取P2(x)的一个零点的一个零点xk+1作为新的近似根，这样确定的作为新的近似根，这样确定的迭代过程称为迭代过程称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法.在几何在几何图形上图形上,这种方法的基本思想是用抛物线这种方法的基本思想是用抛物线y=P2(x)与与x轴轴的交点的交点xk+1作为所求根作为所求根x*的近似位置。的近似位置。*50第五十页，本课件共有58页yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O抛物线法的几

17、何意义抛物线法的几何意义*第五十一页，本课件共有58页下面推导抛物线法的计算公式。插值多项式下面推导抛物线法的计算公式。插值多项式有两个零点有两个零点式中式中P2(x)与与 x 轴有两个交点，取哪个点？轴有两个交点，取哪个点？在在xk,xk-1,xk-2三个近似值中，自然假定三个近似值中，自然假定xk更接近所更接近所求的根求的根x*，这时，为了保证精度，我们选，这时，为了保证精度，我们选(3)式中接近式中接近xk的一个值作为新的近似根的一个值作为新的近似根xk+1。为此，只要取根式前的符。为此，只要取根式前的符号与号与的符号相同的符号相同.*52第五十二页，本课件共有58页【例例】用抛物线法求

18、解方程用抛物线法求解方程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)式求得式求得以上计算表明，以上计算表明，抛物线法比弦截法收敛更快！抛物线法比弦截法收敛更快！*53第五十三页，本课件共有58页事实上事实上,在一定条件下可以证明在一定条件下可以证明,对于抛物线法，对于抛物线法，迭代误差有下列渐近关系式迭代误差有下列渐

19、近关系式由此式可见抛物线法也是由此式可见抛物线法也是超线性收敛超线性收敛的，其收敛的阶是的，其收敛的阶是p=1.840(是方程是方程3-2-1=0的根的根)，收敛速度比弦截法更接，收敛速度比弦截法更接近于牛顿法近于牛顿法.从从(3)式看出：即使式看出：即使 xk,xk-1,xk-2 均为实数，均为实数，xk+1也可以也可以是复数，所以抛物线法适用于求多项式的是复数，所以抛物线法适用于求多项式的实根实根和和复根复根。*54第五十四页，本课件共有58页六、代数方程求根六、代数方程求根v 如果如果f(x)是多项式，那么称是多项式，那么称f(x)=0为为代数方程代数方程。前面介绍的方程求根方法理论上适

20、用于代数方程。前面介绍的方程求根方法理论上适用于代数方程。但由于代数方程的特殊性，还有一些更为有效的方法。但由于代数方程的特殊性，还有一些更为有效的方法。1、多项式求值的秦九韶算法、多项式求值的秦九韶算法 设给定多项式设给定多项式其中系数其中系数 均为实数。均为实数。现用一次式现用一次式x-x0除以除以f(x)，商记为，商记为P(x)，余式为，余式为f(x0)。即：。即：如何如何 确定呢？确定呢？*55第五十五页，本课件共有58页我们可令我们可令将其带入上式，并比较两端同次幂的系数得：将其带入上式，并比较两端同次幂的系数得：因此：因此：所以：所以：秦九韶算法！秦九韶算法！编程计算！编程计算！*56第五十六页，本课件共有58页进一步地，我们考察进一步地，我们考察 的的Taylor展开式：展开式：与（与（5）式比较可得：）式比较可得：其中其中利用秦九韶算法可得：利用秦九韶算法可得：类似地，可依次求得类似地，可依次求得f(x)在点在点x0的各阶导数。的各阶导数。*57第五十七页，本课件共有58页2、代数方程的牛顿法、代数方程的牛顿法 对于多项式对于多项式其中系数其中系数 均为实数。均为实数。考察牛顿公式：考察牛顿公式：由上面讨论可求得：由上面讨论可求得：*58第五十八页，本课件共有58页