第六章 非线性方程求根

第六章非线性方程求根第一页，共五十八页，2022年，8月28日*2第六章非线性方程求根数值分析（NumericalAnalysis）第二页，共五十八页，2022年，8月28日

非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。但是，非线性方程的求根非常复杂。无穷组解无解一个解两个解四个解一、引言*3第三页，共五十八页，2022年，8月28日求根问题包括下面三个问题：

根的存在性：即f(x)=0有没有根？若有，有几个根？

哪儿有根？确定有根区间

根的精确化：已知一个根的近似值后，能否将它精确到足够精度？*4第四页，共五十八页，2022年，8月28日【定理1】设函数f(x)在区间[a,b]上连续，如果f(a)

f(b)<0，

则方程f(x)=0在[a,b]内至少有一实根x*。

【定义1】如果存在使得，则称为方程#的根或函数的零点。*5第五页，共五十八页，2022年，8月28日若其中，为正整数，则当m=1时，称为方程#的单根或函数的单零点。称为方程#的m重根或函数的m重零点。当时，【定义2】*6第六页，共五十八页，2022年，8月28日abx*f(x)1．画出f(x)的略图，从而看出曲线与x轴交点的位置。2．从左端点x0=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。二、根的搜索(1)逐步搜索法7*第七页，共五十八页，2022年，8月28日【例1】考察方程的根。x00.51.01.5f(x)的符号－－－＋步长太大，有根区间太长，精度得不到保障。步长太小，搜索步数增多，计算量增大。*8如何选取合适的步长？第八页，共五十八页，2022年，8月28日abx1x2abx*(2)二分法什么时候停止？每次二分后，设有根区间[ak,bk]的中点作为根的近似值，则二分过程中得到近似根的一个序列，该序列必以根为极限。误差：*9f(x)第九页，共五十八页，2022年，8月28日算法步骤：1．计算f(x)在有解区间[a,b]端点处的值，f(a)，f(b)。2．计算f(x)在区间中点处的值f(x1)。3．判断若f(x1)=0，则x1即是根，否则检验：（1）若f(x1)与f(a)异号，则知解位于区间[a,x1]，

b1=x1,a1=a;（2）若f(x1)与f(a)同号，则知解位于区间[x1,b]，

a1=x1,b1=b。反复执行步骤2、3，便可得到一系列有根区间：

(a,b),(a1,b1),…,(ak,bk),…*10第十页，共五十八页，2022年，8月28日4、当时，则，即为根的近似①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢*11第十一页，共五十八页，2022年，8月28日定义f(x)f(a)

f(b)>0f(a)

f(b)=0f(a)=0打印b,k打印a,k结束是是是否否否m=(a+b)/2|a-b|<f(a)f(m)>0打印m,ka=mb=m结束k=k+1是是否否输入k=012*第十二页，共五十八页，2022年，8月28日【例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第十三页，共五十八页，2022年，8月28日1．简单迭代法f(x)=0x=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

的根。思路*14第十四页，共五十八页，2022年，8月28日x1=0.4771x2=0.3939 …x6=0.3758x7=0.3758迭代过程的收敛性?【例3】求方程的一个根。迭代格式*15第十五页，共五十八页，2022年，8月28日xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1*16第十六页，共五十八页，2022年，8月28日【定理2】如果

(x)满足下列条件 （1）当x[a,b]时，(x)[a,b]

（2）对任意x[a,b]，存在0<L<1，使

则迭代过程对任意初值x0[a,b]时，迭代序列xk+1=

(xk)

(k=0,1,…)收敛于x*,

[注]此处L可以看成是在区间[a,b]内的上界。迭代法的结束条件*17且有误差估计第十七页，共五十八页，2022年，8月28日求方程在内的根【例】。解：原方程可以等价变形为下列三种迭代格式*18第十八页，共五十八页，2022年，8月28日由迭代格式（1）

取初值得：

结果是发散的？！*19第十九页，共五十八页，2022年，8月28日由迭代格式（2）

取初值得

结果精确到4位有效数字，迭代到得到收敛结果。

10步才能得到收敛的结果！*20第二十页，共五十八页，2022年，8月28日

由迭代格式（3）

取初值得

结果精确到4位有效数字，迭代到得到收敛结果。4步就能得到收敛的结果了！*21第二十一页，共五十八页，2022年，8月28日迭代格式（1）的迭代函数为

求导得

当时故迭代格式（1）是发散的。结果分析:*22第二十二页，共五十八页，2022年，8月28日

迭代格式（2）的迭代函数为

当时由*23第二十三页，共五十八页，2022年，8月28日知当时，

所以迭代格式（2）是收敛的。*24第二十四页，共五十八页，2022年，8月28日迭代格式（3）的迭代函数为当时

*25第二十五页，共五十八页，2022年，8月28日由时，

知当所以迭代格式（3）也是收敛的。*26第二十六页，共五十八页，2022年，8月28日【结论】

通过以上算例可以看出对迭代函数所得到的若小于1，则收敛；且上界越小收敛速度越快。求导，的上界若是大于1，则迭代格式发散；*27【定义】若存在的某个邻域，使迭代过程对于任意初值均收敛，则称迭代过程在邻近具有局部收敛性。【定理3】设为方程的根，在的邻近连续且,则迭代过程在邻近具有局部收敛性。第二十七页，共五十八页，2022年，8月28日*28P1611,3作业第二十八页，共五十八页，2022年，8月28日2．迭代公式的加工29对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度。但有的迭代过程收敛缓慢，计算量很大，因此我们需要对迭代过程加速。加速思想设是根的某个预测值，用迭代公式得由微分中值定理可得：假定改变不大，近似取某个近似值，则由得：可以期望是比更好的近似值（改进值）。*第二十九页，共五十八页，2022年，8月28日30校正：改进：缺点：其中要用到的有关信息，实际使用不便！再次修改：由联立得：因此：校正：改进：再校正：艾特肯方法！*第三十页，共五十八页，2022年，8月28日1.牛顿法的迭代公式原理：将非线性方程线性化—Taylor展开取x0

x*，将f(x)在x0

做一阶Taylor展开:，在x0

和x

之间。*31四、牛顿法（切线法）

考虑非线性方程将x=x*代入第三十一页，共五十八页，2022年，8月28日将(x*

x0)2

看成高阶小量，则有：只要f

C1，且每步迭代都有f'(xk)0，而且则

x*就是f(x)的根。公式（1）称为牛顿迭代公式。(1)构造迭代公式*32P151Newton法的计算步骤！第三十二页，共五十八页，2022年，8月28日x*x0x1x2xyf(x)2、牛顿法的几何意义*33第三十三页，共五十八页，2022年，8月28日

3．牛顿法的收敛性【定义】由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得

（C为非零常数）则称序列{xk}收敛于x*的收敛速度是p阶的，或称该方法具有p

阶收敛速度。当p=1时，称该方法为线性（一次）收敛；当p>1时，称方法为超线性收敛。当p=2时，称方法为平方（二次）收敛；34*第三十四页，共五十八页，2022年，8月28日35【定理4】对于迭代过程，如果在所求根的附近连续，且：则该迭代过程在点附近是p阶收敛的。

迭代过程收敛速度依赖于迭代函数的选取；

当时，，则该迭代过程的收敛速度只可能是线性的；

当x*是单根时，牛顿法在x*附近至少是平方收敛的？？？*第三十五页，共五十八页，2022年，8月28日注：Newton法的收敛性依赖于x0

的选取。x*x0x0x0*36第三十六页，共五十八页，2022年，8月28日4、牛顿法的应用举例对任给的正数a,应用牛顿法解二次方程，可导出开平方的值。

*37选取迭代格式为这种迭代格式对任意的初值都是收敛的！【例】求，取x0=10第三十七页，共五十八页，2022年，8月28日5、牛顿法的变形--牛顿下山法计算：使得具有单调性：满足这项要求的算法称之为下山法。将牛顿法和下山法结合起来使用，即可在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度。

其中的称为下山因子。下山因子的选择是个逐步搜索的过程。从开始反复将其减半，如果能找到值使得单调性条件成立，则称“下山成功”，否则“下山失败”。保证全局收敛！*38第三十八页，共五十八页，2022年，8月28日*39P161-1625,7(1)(2),12,13作业第三十九页，共五十八页，2022年，8月28日*40实验二

实验名称：函数逼近与数据拟合实验目的：考察学生综合运用Matlab进行编程的能力。根据最佳平方逼近及最小二乘算法要求，自行设计编程方案，实现算法。掌握Matlab中的polyfit、lsqcurvefit、nlinfit等函数，并用这些函数解决实际问题第四十页，共五十八页，2022年，8月28日*41实验任务：写出相应的MATLAB程序给出实验结果对实验结果进行分析和讨论写出相应的实验报告实验步骤：用Matlab语言实现最佳平方逼近及最小二乘算法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第四十一页，共五十八页，2022年，8月28日五、弦截法与抛物线法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)的计算呢？本节的两种方法是建立在插值原理基础上的。回忆一下插值法！设是的一组近似根，我们利用函数值构造插值多项式Pr(x)，并适当选取用Pr(x)=0的根作为方程f(x)=0的新的近似根xk+1。当r=1时，就是弦截法，当r=2时，就是抛物线法。

*第四十二页，共五十八页，2022年，8月28日设是的近似根，我们利用构造一次插值多项式P1(x)，并用P1(x)=0的根作为方程f(x)=0的新的近似根xk+1，由于因此有:2、弦截法（割线法）差商？与导数的关系？*43第四十三页，共五十八页，2022年，8月28日这样导出的迭代公式(2)可以看做牛顿公式中的导数用差商取代的结果.(2)式有几何意义吗？*44第四十四页，共五十八页，2022年，8月28日Ox*xk+1xkPkxk-1yPk-1按(2)式求得xk+1实际上是两点弦线与x轴交点的横坐标。这种算法因此而形象地称为弦截(双点割线)法.f(x)每步只用一个新点xk的值，此方法称为单点割线法。如果把(2)式中的xk-1改为x0，即迭代公式为，即：*45第四十五页，共五十八页，2022年，8月28日线性化

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

弦截法和切线法的联系和区别：第四十六页，共五十八页，2022年，8月28日计算结果表k

xk

xk-xk-100.510.60.120.56532-0.0346830.567090.0017740.567140.00005从表中可以看出弦截法的收敛速度也是相当快的，迭代到第4步就得到精度的结果。解1：*47第四十七页，共五十八页，2022年，8月28日取初值x0=0.5，牛顿法迭代结果见下表k0123xk0.50.571020.567160.56714*48解2：第四十八页，共五十八页，2022年，8月28日【定理6.4】假设f(x)在根x*的邻域内具有二阶连续导数，且对于任意，有，又初值，那么当邻域充分小时，弦截法将按阶收敛到根x*。*49弦截法是超线性收敛的！第四十九页，共五十八页，2022年，8月28日3、

抛物线法

设已知方程f(x)=0的三个近似根xk,xk-1,xk-2，我们以这三点为插值节点构造二次插值多项式P2(x)，并适当选取P2(x)的一个零点xk+1作为新的近似根，这样确定的迭代过程称为抛物线法，亦称为密勒(Müller)法.在几何图形上,这种方法的基本思想是用抛物线y=P2(x)与x轴的交点xk+1作为所求根x*的近似位置。*50第五十页，共五十八页，2022年，8月28日yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O抛物线法的几何意义*第五十一页，共五十八页，2022年，8月28日下面推导抛物线法的计算公式。插值多项式有两个零点式中P2(x)与x

轴有两个交点，取哪个点？在xk,xk-1,xk-2三个近似值中，自然假定xk更接近所求的根x*，这时，为了保证精度，我们选(3)式中接近xk的一个值作为新的近似根xk+1。为此，只要取根式前的符号与ω的符号相同.*52第五十二页，共五十八页，2022年，8月28日【例】用抛物线法求解方程f(x)=xex-1=0。

解：取x0=0.5,x1=0.6,x2=0.56532开始，计算得f(x0)=