非线性方程求根

非线性方程求根第1页，共91页，2023年，2月20日，星期三问题驱动：全球定位系统（GPS）

人类对导航和定位的需求是伴随着人类整个文明历史的进步而发展的，中国古代“四大发明”之一的指南针是最早的定位仪器和系统，其后还有经纬仪以及近代的雷达。如图9.1.1所示全球定位系统（GPS）是基于卫星的导航系统，最早由美国和前苏联分别在80年代研制，并于1993年正式投入使用。现代社会中全球定位系统越来越深入到人们生活的方方面面。例如市场上出售的手持型GPS，定位的精度可以达到10米以内，这无疑给旅行者提供了方便；安装有GPS的儿童手表，家长在家里的计算机上可以追踪到孩子的位置，防止儿童走失；安装有GPS系统的汽车可以帮助新司机辨识道路等等。第2页，共91页，2023年，2月20日，星期三图6.1.1卫星定位示意图

美国和前苏联的GPS都包括有24颗卫星，它们不断地向地球发射信号报告当前位置和发出信号的时间，卫星分布如图6.1.2所示。它的基本原理是：在地球的任何一个位置，至少同时收到4颗以上卫星发射的信号。发射的信号，

设地球上一个点R，同时收到卫星

第3页，共91页，2023年，2月20日，星期三假设接收的信息如表6.1.1所示。请设法确定R点的位置。图6.1.2卫星分布图表6.1.1GPS导航问题可归结为求解非线性代数数方程组,当时就是单个方程.（6.1.1）

第4页，共91页，2023年，2月20日，星期三。.其中，可以是代数方程，也可以是超越方程。使成立的x

值称为方程的根，或称为计算中，如电路和电力系统计算、非线性力学、非线性微（积分）方程、非线性规划（优化）等众多领域中，问题的求解和模拟最终往往都要解决求根或优化问题。前一种情形要求出方程（组）的根；后一种情形则要求找出函数取最大或最小的点。即使是对实验数据进行拟合或数值求解微分方程，也总是将问题简化成上述两类问题。上述除少数特殊方程外，大多数非线性代数方程（组）很难使用解析法求解精确解，一般需要通过一些数值方法逼近方程的解。这里主要介绍单个方程的数值解法，方程组也可以采用类似的方法，将放在后面讨论。的零点。科学与工程第5页，共91页，2023年，2月20日，星期三1．根的存在性。方程有没有根？如果有，有几个根？2．根的搜索。这些根大致在哪里？如何把根隔离开？3．根的精确化。f(x)=0（6.2.1）第6页，共91页，2023年，2月20日，星期三1.根的存在性定理1：设函数f(x)在区间[a,b]上连续，如果f(a)

f(b)<0，

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

定义：如果存在使得，则称为方程（6.2.1）的根或函数的零点。第7页，共91页，2023年，2月20日，星期三m重根若其中，为正整数，则当m=1时，称为方程（6.2.1）的单根或函数的单零点。称为方程（6.2.1）的m重根或函数的m重零点。当时，第8页，共91页，2023年，2月20日，星期三2.根的搜索(1)图解法（利用作图软件如Matlab)(2)解析法(3)近似方程法(4)定步长搜索法第9页，共91页，2023年，2月20日，星期三abx*f(x)1．画出f(x)的略图，从而看出曲线与x轴交点的位置。2．从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。第10页，共91页，2023年，2月20日，星期三

开始读入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印结束否是继续扫描

第11页，共91页，2023年，2月20日，星期三例1：考察方程x00.51.01.5f(x)的符号－－－＋第12页，共91页，2023年，2月20日，星期三abx1x2ab或不能保证

x

的精度x*2xx*§1二分法第13页，共91页，2023年，2月20日，星期三

执行步骤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，便可得到一系列有根区间：

第14页，共91页，2023年，2月20日，星期三4、当时，停止；即为根的近似。当时，，即这些区间必将收缩于一点，也就是方程的根。在实际计算中，只要的区间长度小于预定容许误差就可以停止搜索，即然后取其中点作为方程的一个根的近似值。注：第15页，共91页，2023年，2月20日，星期三例2证明方程存在唯一的实根用二分法求出此根，要求误差不超过。解：记，则对任意

，因而，是严格单调的，最多有一个根，所以，有唯一实根又因为

第16页，共91页，2023年，2月20日，星期三用二分法求解，要使，只要解得，取。所以只要二等分7次，即可求得满足精度要求的根。计算过程如表6.2.1所示k

f(ak)及符号f(xk)及符号f(bk)及符号012345670(－)0(－)0(－)0(－)0.0625(－)0.0625(－)0.078125(－)0.0859375(－)0.5(+)0.25(+)0.125(+)0.0625(－)0.09375(+)0.078125(－)0.0859375(－)1(+)0.5(+)0.25(+)0.125(+)0.125(+)0.09375(+)0.09375(+)0.09375(+)表6.2.1所以，第17页，共91页，2023年，2月20日，星期三①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢

二分法的优缺点第18页，共91页，2023年，2月20日，星期三

问题虽然二分法计算简单，能够保证收敛，但是它对于方程单根存在区域信息要求太高，一般情况下很难实现，并且不能求偶重根、复根和虚根。在实际应用中，用来求解方程根的主要方法是迭代法。使用迭代法求解非线性代数方程的步骤为：(1)迭代格式的构造；(2)迭代格式的收敛性分析；(3)迭代格式的收敛速度与误差分析。§2

迭代法第19页，共91页，2023年，2月20日，星期三1．简单迭代法f(x)=0x=

(x)等价变换其中

(x)是连续函数。方程（6.3.1）称为不动点方程，满足（6.3.1）式的点称为不动点，这样就将求（6.3.1）的零点问题转化为求的不动点问题。称这种迭代格式为不动点迭代。以不动点方程为原型构造迭代格式第20页，共91页，2023年，2月20日，星期三解：从方程可以看出1是方程的一个根，在[0,1.5]之间。例3求方程的根：方法一：将方程等价变形为：取迭代初始值：迭代过程：显然迭代发散第21页，共91页，2023年，2月20日，星期三依此类推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000迭代过程：同样的方程不同的迭代公式有不同的结果什么形式的迭代法能够收敛呢?初值：等价方程变换为：方法二：收敛于1说明：①迭代函数不唯一；②迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。第22页，共91页，2023年，2月20日，星期三xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第23页，共91页，2023年，2月20日，星期三定理6.1：如果

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

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

则方程x=

(x)在[a,b]上有唯一的根x*,且对任意初值

x0[a,b]，迭代序列xk+1=

(xk)

(k=0,1,…)收敛于x*。(6.3.2)[注]

此处L可以看成是在区间[a,b]内的最大值。2．迭代过程的收敛性第24页，共91页，2023年，2月20日，星期三由递推公式：可以得到：微分中值定理定理的条件2证明：由得注：L越小，收敛越快。反复迭代：上公式即为：收敛于方程的根

第25页，共91页，2023年，2月20日，星期三3．迭代法的误差估计

在定理6.1的条件下，简单迭代法产生的迭代点列有如下误差估计式：停机准则。（6.3.3）或第26页，共91页，2023年，2月20日，星期三②①由收敛性证明得到的递推公式进行推理：注：只要前后两次迭代值的误差值足够小，即可保证近似值具有足够的精度，因此常常通过来判断是否满足迭代精度。第27页，共91页，2023年，2月20日，星期三求方程在内的根例4：。解：原方程可以等价变形为下列三个迭代格式第28页，共91页，2023年，2月20日，星期三由迭代格式（1）

取初值得

结果是发散的？！第29页，共91页，2023年，2月20日，星期三由迭代格式（2）

取初值得

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

十步才能得到收敛的结果！第30页，共91页，2023年，2月20日，星期三

由迭代格式（3）

取初值得

结果精确到四位有效数字，迭代到得到收敛结果。四步就能得到收敛的结果了！第31页，共91页，2023年，2月20日，星期三迭代格式（1）的迭代函数为

求导得

当时故迭代格式（1）是发散的。分析:第32页，共91页，2023年，2月20日，星期三

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

当时由第33页，共91页，2023年，2月20日，星期三知当时，

所以迭代格式（2）是收敛的。第34页，共91页，2023年，2月20日，星期三迭代格式（3）的迭代函数为当时

第35页，共91页，2023年，2月20日，星期三由时，

知当所以迭代格式（3）也是收敛的。第36页，共91页，2023年，2月20日，星期三结论:

通过以上算例可以看出对迭代函数所得到的若小于1，则收敛；且上界越小收敛速度越快。求导，的上界若是大于1，则迭代格式发散；第37页，共91页，2023年，2月20日，星期三迭代法的计算步骤(P145页)：（1）准备提供迭代初始值（2）迭代计算迭代值（3）控制

转（2）；停，第38页，共91页，2023年，2月20日，星期三4．迭代过程的局部收敛性定义6.1定理6.2若存在的某个邻域R：则称迭代过程使迭代过程对任意初值均收敛，在邻近具有局部收敛性。则迭代过程在邻近具有局部收敛性。设为方程的根，在的邻近连续且第39页，共91页，2023年，2月20日，星期三

5.加速收敛技术

L越小迭代法的收敛速度越快，因此，可以从寻找较小的L来改进迭代格式以加快收敛速度。思路(1).松弛法引入待定参数，将

作等价变形为（6.3.4）将方程右端记为，则得到新的迭代格式第40页，共91页，2023年，2月20日，星期三由定理6.1知为了使新的迭代格式比原来迭代格式收敛得更快，只要满足且越小，所获取的L就越小，迭代法收敛的就越快，因此我们希望。第41页，共91页，2023年，2月20日，星期三可取

，若记则（6.3.4）式可改写为

称为松弛因子，这种方法称为松弛法。为使迭代速度加快，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，在实际应用中不便使用，具有一定局限性。若迭代法是线性收敛的，当计算不方便时，可以采用埃特金加速公式。第42页，共91页，2023年，2月20日，星期三(2).埃特金加速公式设迭代法是线性收敛，由定义知成立，故当时有由此可得的近似值（6.3.5）第43页，共91页，2023年，2月20日，星期三由此获得比和更好的近似值，利用（6.3.5）序列的方法称为(3).Steffensen加速法：

将Aitken加速公式与不动点迭代相结合，可得（6.3.6）式构造埃特金（Aitken）加速方法。利用（6.3.6）式构造序列的方法称为Steffensen加速方法。即每进行两次不动点迭代，就执行一次Aitken加速。第44页，共91页，2023年，2月20日，星期三例5试用简单迭代法和Steffensen加速法求方程在附近的根，精确至四位有效数。解：记，简单迭代法公式为：计算得kxkkxkkxk00.570.5584380140.567118810.606530680.5664094150.567157120.545239290.5675596160.567135430.5797031100.5669072170.567147740.5600646110.5672772180.567140750.5711721120.567067360.5648629130.5671863第45页，共91页，2023年，2月20日，星期三Aitken加速公式计算得所以,。第46页，共91页，2023年，2月20日，星期三§3牛顿法一、牛顿法的迭代公式考虑非线性方程原理：将非线性方程线性化—Taylor展开取x0

x*，将f(x)在x0

做一阶Taylor展开:，在x0

和x

之间。第47页，共91页，2023年，2月20日，星期三将(x*

x0)2

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

C1，且每步迭代都有，而且则

x*就是f(x)的根。公式（6.4.1）称为牛顿迭代公式。(6.4.1)构造迭代公式第48页，共91页，2023年，2月20日，星期三x*x0x1x2xyf(x)二、牛顿法的几何意义第49页，共91页，2023年，2月20日，星期三定理：设f(x)在[a,b]上存在二阶连续导数且满足下列条件： （1）f(a)

f(b)<0； （2）f’(x)0； （3）f(x)在区间[a,b]上不变号； （4）取x0[a,b]，使得f(x)f(x0)>0则由（6.4.1）确定的牛顿迭代序列{xk}二阶收敛于f(x)在[a,b]上的唯一单根x*。三、牛顿法的收敛性1.牛顿法收敛的条件第50页，共91页，2023年，2月20日，星期三第51页，共91页，2023年，2月20日，星期三注：Newton法的收敛性依赖于x0

的选取。x*x0x0x0Newton法是局部收敛的算法！第52页，共91页，2023年，2月20日，星期三2.迭代过程的收敛速度

设由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得

（C为非零常数）定义6.2：则称序列{xk}收敛于x*的收敛速度是p阶的，或称该方法具有p阶收敛速度。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1<p<2或C=0,p=1时，称方法为超线性收敛。

第53页，共91页，2023年，2月20日，星期三3.迭代法收敛阶的判别定理6.3

如果在附近的某个领域内有p()阶连续导数，且则迭代格式在

附近是p阶局部收敛的，且有第54页，共91页，2023年，2月20日，星期三4.牛顿迭代法的局部收敛性与收敛速度

,且即在包含的一个区间二阶连续可导，则Newton迭代法至少二阶收敛，值得注意的是，当充分光滑且是的重根时，的附近是线性收敛的。即且其中，为牛顿迭代函数。法在牛顿即若是

的一个单根，第55页，共91页，2023年，2月20日，星期三例6用牛顿法求方程的根：解：由牛顿迭代公式：取初值x0=0.5注：可与P146页例6.4比较，牛顿法的收敛速度比较快的。得第56页，共91页，2023年，2月20日，星期三并得出了是该方程的一个根，无人知道他用什么方法得出的，在当时这是一个非常有名的结果，试用牛顿法求出此结果。解：记则当时，，又所以有唯一实根

，并改写例7Leonardo于1225年研究了方程第57页，共91页，2023年，2月20日，星期三用牛顿迭代格式所以，。第58页，共91页，2023年，2月20日，星期三注：牛顿迭代法的优缺点:优点:公式简单,使用方便,易于编程,收敛速度快,易于求解缺点:计算量大,每次迭代都要计算函数值与导数值.5.牛顿法的计算步骤：1步准备2步迭代3步控制4步修改若迭代次数>N，或方法失败，否则，继续。否则转4步第59页，共91页，2023年，2月20日，星期三6.牛顿法应用举例设C>0,解：令

f(x)=x2–C收敛分析：ek+1ek2平方根迭代公式①求正数平方根算法：若则第60页，共91页，2023年，2月20日，星期三例8求解：取x0=10,c=15,

迭代三次便有很好的结果注：求正数平方根算法是局部收敛的，它要求初值>0第61页，共91页，2023年，2月20日，星期三②求倒数算法：用牛顿法解方程不用除法有一定的实际意义解：收敛分析：ek+1ek求倒数算法要求初值x0满足：第62页，共91页，2023年，2月20日，星期三四、求m重根的牛顿法-修正牛顿法修正格式一：构造迭代格式(6.4.2)注：重数m的确定则迭代格式（6.4.2)

至少2阶收敛。

设

令

则第63页，共91页，2023年，2月20日，星期三修正格式二：

令

则是的单根，

即构造迭代格式(6.4.3)则迭代格式（6.4.3)

至少2阶收敛。第64页，共91页，2023年，2月20日，星期三由于Newton迭代法的收敛性依赖于初值的选取，如果离方程的根较远，则Newton迭代法可能发散。为了防止迭代发散，可以将Newton迭代法与下山法结合起来使用，放宽初值的选取范围，即将（6.4.1）式修改为：其中，称为下山因子，选择下山因子时，希望满足下山法具有的单调性，即这种算法称为Newton下山法。在实际应用中，可选择。五、牛顿法的变形1、牛顿下山法第65页，共91页，2023年，2月20日，星期三2.牛顿下山法的计算步骤：（1）选取初始近似值x0；（2）取下山因子

=1；（3）计算（4）计算f(xk+1)，并比较与的大小，分以下二种情况 1）若，则当时，取x*

xk+1，计算过程结束；当时，则把xk+1作为新的近似值，并返回到（3）。2）若，则当≤且|f(xk+1)|<，取x*

xk，计算过程结束；否则若≤，而时，则把xk+1加上一个适当选定的小正数，即取xk+1+作为新的xk值，并转向（3）重复计算；当＞且时，则将下山因子缩小一半，取/2代入，并转向（3）重复计算。第66页，共91页，2023年，2月20日，星期三【例9】求方程f(x)=x3–x–1=0的根。

x0

=0.6牛顿下山法的计算结果：kxk010.611/251.14063211.36681311.32628411.32472第67页，共91页，2023年，2月20日，星期三牛顿迭代法每迭代一次都需计算函数值和导数值计算量比较大；且迭代过程中计算时，仅利用了点的信息，而没有充分利用已经求出的；在导数计算比较麻烦或难以求出时，

迭代格式构造(2)构造方法：将Newton迭代格式中的导数用差商代替。1、割线法：(1)构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；设法避开导数值的计算，因此可以采用离散牛顿法（割线法）。

一个自然的想法就是在充分利用“旧信息”的同时，§4弦截法与抛物线法第68页，共91页，2023年，2月20日，星期三（1）割线法的几何意义x0x1切线

割线

切线斜率

割线斜率x2割线法迭代格式：第69页，共91页，2023年，2月20日，星期三（2）割线法的局部收敛性与收敛速度

设，在,且的某一邻域内二阶连续可微，当时，由割线法产生的序列收敛于，且收敛阶至少为1.312。

割线法是超线性收敛的！第70页，共91页，2023年，2月20日，星期三2、双点弦截法：切线斜率

割线斜率初值x0

和x1。x0x1x2第71页，共91页，2023年，2月20日，星期三双点弦截法的局部收敛性与收敛速度

设，在,且的某一邻域内二阶连续可微，且对任意的则当时，由弦截法产生的序列收敛于且收敛阶至少为1.618。定理6.5，双点弦截法也是超线性收敛的！第72页，共91页，2023年，2月20日，星期三计算结果k

xk

xk-xk-100.510.60.120.56532-0.0346830.567090.0017740.567140.00005从表中可以看出弦截法的收敛速度也是相当快的，迭代到第4步就得到精度的结果.例10用弦截法解方程第73页，共91页，2023年，2月20日，星期三双点弦截法的计算步骤：1步准备2步迭代3步控制4步修改若迭代次数>N，失败，否则，继续。否则转4步；第74页，共91页，2023年，2月20日，星期三3.抛物线法此迭代过程称为抛物线法，亦称为密勒(Müller)法.（1）基本思想：以f(x)=0的三个近似根xk,xk-1,xk-2为插值节点构造二次插值多项式P2(x)，并以的零点作为的一个新的近似根。第75页，共91页，2023年，2月20日，星期三yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O（2）抛物线法的几何意义第76页，共91页，2023年，2月20日，星期三（3）抛物线法计算公式的推导：两个零点：其中，P2(x)与x

轴有两个交点,取哪个点为f(x)的根的近似？

注：在xk,xk-1,xk-2三个近似值中，自然假定xk更接近x*，为保证精度，我们选上式中接近xk的一个值作为新的近似根xk+1.为此，只要取根式前的符号与ω的符号相同.第77页，共91页，2023年，2月20日，星期三yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O第78页，共91页，2023年，2月20日，星期三例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.f[x1,x0]=2.68910,f[x2,x1]=2.83373,f[x2,x1,x0]=2.21418.故：代入公式以上计算表明，抛物线法比弦截法收敛更快！求得第79页，共91页，2023年，2月20日，星期三抛物线法的迭代误差有下列渐近关系式

由此式可见抛物线法也是超线性收敛的，其收敛阶是p=1.840(是方程λ3-λ2-λ-1=0的根)，收敛速度比弦截法更接近于牛顿法.（5）抛物线法的计算步骤（P156页）（4）抛物线法的局部收敛性与误差估计第80页，共91页，2023年，2月20日，星期三

如果f(x)是多项式，那么