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

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

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

2、包括下面三个问题：v 根的存在性根的存在性：即：即f(x)=0有没有根？若有，有有没有根？若有，有 几个根？几个根？v 哪儿有根哪儿有根？确定有根区间？确定有根区间v 根的精确化根的精确化：已知一个根的近似值后，能否：已知一个根的近似值后，能否将它精确到足够精度？将它精确到足够精度？*4第4页，共58页，编辑于2022年，星期三【定理定理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是是是是否

3、否否否 输入输入 k=012*第12页，共58页，编辑于2022年，星期三【例例2】求方程求方程 在区间在区间(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第13页，共58页，编辑于2022年，星期三1 1简单迭代法简单迭代法f(x)=0 x=g(x)等价变

4、换等价变换三、迭代法三、迭代法f(x)的根的根g(x)的不动点的不动点从一个初值从一个初值 x0 出发，计算出发，计算 x1=g(x0),x2=g(x1),xk+1=g(xk),若若 收敛，即存在收敛，即存在 x*，使得，使得 ，且，且 g 连续，则由连续，则由 可知可知 x*=g(x*)，即，即x*是是 g 的不动点，也就是的不动点，也就是f 的根。的根。思思路路*14第14页，共58页，编辑于2022年，星期三x1=0.4771x2=0.3939x6=0.3758x7=0.3758迭代过程的迭代过程的收敛性收敛性?【例例3】求方程求方程的一个根。的一个根。迭代格式迭代格式*15第15页，共

5、58页，编辑于2022年，星期三xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1*16第16页，共58页，编辑于2022年，星期三【定理定理2】如果如果 (x)满足下列条件满足下列条件（1 1）当）当x a,b时，时，(x)a,b（2 2）对任意）对任意x a,b，存在，存在0 L1时，称方法为时，称方法为超线性超线性收敛。收敛。v当当p=2时，称方法为时，称方法为平方平方（二次）收敛；（二次）收敛；34*第34页，共58页，编辑于2022年，星期三35【定理定理

6、4】对于迭代过程对于迭代过程 ，如果，如果 在所求在所求根根 的的附近连续附近连续，且：，且：则该迭代过程在点则该迭代过程在点 附近是附近是p阶收敛阶收敛的。的。v 迭代过程收敛速度依赖于迭代函数迭代过程收敛速度依赖于迭代函数 的选取；的选取；v 当当 时，时，则该迭代过程的收敛速度只可能是，则该迭代过程的收敛速度只可能是线性线性的；的；v 当当x*是单根时，是单根时，牛顿法牛顿法在在x*附近至少是附近至少是平方平方收敛的收敛的？*第35页，共58页，编辑于2022年，星期三注：注：注：注：Newton法的收敛性法的收敛性依赖于依赖于x0 的选取。的选取。x*x0 x0 x0*36第36页，共

7、58页，编辑于2022年，星期三4、牛顿法的应用举例、牛顿法的应用举例对任给的对任给的正数正数a,应用牛顿法解二次方程应用牛顿法解二次方程 ，可导出开平方，可导出开平方 的值。的值。*37选取迭代格式为选取迭代格式为这种迭代格式对任意的初值这种迭代格式对任意的初值 都是收敛的都是收敛的！【例例】求求 ，取，取x0=10第37页，共58页，编辑于2022年，星期三5、牛顿法的变形牛顿法的变形-牛顿下山法牛顿下山法计算：计算：使得具有单调性：使得具有单调性：满足这项要求的算法称之为满足这项要求的算法称之为下山法。下山法。v 将牛顿法和下山法结合起来使用，即可在将牛顿法和下山法结合起来使用，即可在下

8、山法下山法保证保证函数函数值稳定值稳定下下降降的前提下，用的前提下，用牛顿法牛顿法加快收敛速度加快收敛速度。v 其中的其中的 称为称为下山因子下山因子。下山因子的选择是个逐步搜索的过程。从下山因子的选择是个逐步搜索的过程。从 开始反复将其减半，如开始反复将其减半，如果能找到值果能找到值 使得单调性条件成立，则称使得单调性条件成立，则称“下山成功下山成功”，否则，否则“下山下山失败失败”。保证全局收敛！保证全局收敛！*38第38页，共58页，编辑于2022年，星期三*39P161-162 5,7(1)(2),12,13作业作业第39页，共58页，编辑于2022年，星期三*40实验二 实验名称实验

9、名称：函数逼近与数据拟合函数逼近与数据拟合 实验目的实验目的：考察学生综合运用考察学生综合运用 Matlab 进行编程的能力。根据进行编程的能力。根据最佳平方逼近及最最佳平方逼近及最 小二乘算法要求，自行设计编程方案，实现小二乘算法要求，自行设计编程方案，实现算法。掌握算法。掌握 Matlab 中的中的 polyfit、lsqcurvefit、nlinfit等函数，等函数，并用这些函数解决实际问题并用这些函数解决实际问题第40页，共58页，编辑于2022年，星期三*41实验任务：实验任务：v写出相应的写出相应的MATLAB程序程序v给出实验结果给出实验结果v对实验结果进行分析和讨论对实验结果进

10、行分析和讨论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。用以上数据拟合非线性函数。用以上数据拟合非线性函数y=aebx第41页，共58页，编辑于2022年，星期三五、弦截法与抛物线法五、弦截法与抛物线法421.引入引入 用牛顿法求方程用牛顿法求方程f(x)=0的根时，每步除计算的根时，每步除计算f(xk)外还要算外还要算f(xk)，当，当函数函数f(x)比较复杂时，计算比较复杂时

11、，计算f(x)往往比较困难。那么我们能否利用已知往往比较困难。那么我们能否利用已知的信息，例如：的信息，例如：xk,xk-1，xk-2,及其函数值及其函数值f(xk),f(xk-1),f(xk-2),来回来回避导数值避导数值f(xk)的计算呢？的计算呢？本节的两种方法是建立在本节的两种方法是建立在插值原理插值原理基础上的。回忆一下插值法！基础上的。回忆一下插值法！设设 是是 的一组近似根，我们利用函数值的一组近似根，我们利用函数值 构造构造插值多项式插值多项式Pr(x)，并适当选取用，并适当选取用Pr(x)=0的根作为方程的根作为方程f(x)=0的新的的新的近似根近似根xk+1。当当r=1时，

12、就是弦截法，当时，就是弦截法，当r=2时，就是抛物线法。时，就是抛物线法。*第42页，共58页，编辑于2022年，星期三 设设 是是 的近似根，我们利用的近似根，我们利用 构造一次插值构造一次插值多项式多项式P1(x)，并用，并用P1(x)=0的根作为方程的根作为方程f(x)=0的新的近似根的新的近似根xk+1，由于，由于因此有因此有:2、弦截法（割线法）、弦截法（割线法）差商？与导数的关系？差商？与导数的关系？*43第43页，共58页，编辑于2022年，星期三这样导出的迭代公式这样导出的迭代公式(2)可以看做牛顿公式可以看做牛顿公式中的导数中的导数 用用差商差商 取代的结果取代的结果.(2)

13、式有几何意义吗？式有几何意义吗？*44第44页，共58页，编辑于2022年，星期三Ox*xk+1xkPkxk-1yPk-1按按(2)式求得式求得xk+1实际上是两实际上是两点弦线点弦线 与与x轴交点的轴交点的横坐标。这种算法因此而横坐标。这种算法因此而形象地称为形象地称为弦截弦截(双点割线双点割线)法法.f(x)每步只用一个新点每步只用一个新点xk的值，此的值，此方法称为方法称为单点割线法单点割线法。如果把如果把(2)式中的式中的xk-1改为改为x0，即，即迭代公式为，即：迭代公式为，即：*45第45页，共58页，编辑于2022年，星期三v 线性化线性化v 切线法只用到前一步的函数值，而弦截法

14、需要用到前两步的函切线法只用到前一步的函数值，而弦截法需要用到前两步的函数值。其收敛速度一般比牛顿法慢，但比线性收敛的方法快。在数值。其收敛速度一般比牛顿法慢，但比线性收敛的方法快。在与牛顿法具有同等的前提下，弦截法具有局部收敛性，并且收敛与牛顿法具有同等的前提下，弦截法具有局部收敛性，并且收敛阶阶v由于弦截法是两步法，它不属于不动点迭代，因此不能用不由于弦截法是两步法，它不属于不动点迭代，因此不能用不动点迭代理论证明它的收敛性。动点迭代理论证明它的收敛性。*46【P154 P154 例例】用弦截法解方程用弦截法解方程 弦截法和切线法的弦截法和切线法的联系联系和和区别区别：第46页，共58页，

15、编辑于2022年，星期三计算结果表计算结果表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第47页，共58页，编辑于2022年，星期三取初值取初值 x0=0.5，牛顿法迭代牛顿法迭代结果见下表结果见下表k 0 1 2 3xk 0.5 0.57102 0.56716 0.56714*48解解2：第48页，共58页，编辑于202

16、2年，星期三【定理定理6.4】假设假设f(x)在根在根x*的邻域的邻域 内具有二阶连续内具有二阶连续导数，且对于任意导数，且对于任意 ，有，有 ，又初值，又初值 ，那么当，那么当邻邻域域 充分充分小时，弦截法将按阶小时，弦截法将按阶 收敛到根收敛到根x*。*49弦截法是超线性收敛的！弦截法是超线性收敛的！第49页，共58页，编辑于2022年，星期三3、抛物线法抛物线法设已知方程设已知方程f(x)=0的三个近似根的三个近似根xk,xk-1,xk-2，我们以这，我们以这三点为插值节点构造二次插值多项式三点为插值节点构造二次插值多项式P2(x)，并适当选取，并适当选取P2(x)的一个零点的一个零点x

17、k+1作为新的近似根，这样确定的迭代过程称为作为新的近似根，这样确定的迭代过程称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法.在几何图形上在几何图形上,这种方这种方法的基本思想是用抛物线法的基本思想是用抛物线y=P2(x)与与x轴的交点轴的交点xk+1作为所作为所求根求根x*的近似位置。的近似位置。*50第50页，共58页，编辑于2022年，星期三yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O抛物线法的几何意义抛物线法的几何意义*第51页，共58页，编辑于2022年，星期三下面推导抛物线法的计算公式。插值多项式下面推导抛物线法的计算公式。插值多项式有两个零点有

18、两个零点式中式中P2(x)与与 x 轴有两个交点，取哪个点？轴有两个交点，取哪个点？在在xk,xk-1,xk-2三个近似值中，自然假定三个近似值中，自然假定xk更接近所求的更接近所求的根根x*，这时，为了保证精度，我们选，这时，为了保证精度，我们选(3)式中接近式中接近xk的一个值的一个值作为新的近似根作为新的近似根xk+1。为此，只要取根式前的符号与。为此，只要取根式前的符号与的符的符号相同号相同.*52第52页，共58页，编辑于2022年，星期三【例例】用抛物线法求解方程用抛物线法求解方程f(x)=xex-1=0。解：解：取取x0=0.5,x1=0.6,x2=0.56532开始，计算得开始

19、，计算得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第53页，共58页，编辑于2022年，星期三事实上事实上,在一定条件下可以证明在一定条件下可以证明,对于抛物线法，迭代对于抛物线法，迭代误差有下列渐近关系式误差有下列渐近关系式由此式可见抛物线法也是由此式可见抛物线法也是超线性收敛超线性收敛的，其收敛的阶是的，其收敛的阶是p=1

20、.840(是方程是方程3-2-1=0的根的根)，收敛速度比弦截法更接，收敛速度比弦截法更接近于牛顿法近于牛顿法.从从(3)式看出：即使式看出：即使 xk,xk-1,xk-2 均为实数，均为实数，xk+1也可以也可以是复数，所以抛物线法适用于求多项式的是复数，所以抛物线法适用于求多项式的实根实根和和复根复根。*54第54页，共58页，编辑于2022年，星期三六、代数方程求根六、代数方程求根v 如果如果f(x)是多项式，那么称是多项式，那么称f(x)=0为为代数方程代数方程。前面介绍的方程求根方法理论上适用于代数方程。但由前面介绍的方程求根方法理论上适用于代数方程。但由于代数方程的特殊性，还有一些

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