非线性方程求根的数值解法

非线性方程求根的数值解法第1页，共70页，2023年，2月20日，星期三第四章养老保险问题

——非线性方程求根的数值解法养老保险问题4.1非线性方程求根的数值方法4.2养老保险模型的求解4.3第2页，共70页，2023年，2月20日，星期三4.1.1问题的引入

养老保险是保险中的一种重要险种，保险公司将提供不同的保险方案供以选择，分析保险品种的实际投资价值。也就是说，如果已知所交保费和保险收入，则按年或按月计算实际的利率是多少？或者说，保险公司需要用你的保费实际至少获得多少利润才能保证兑现你的保险收益？4.1养老保险问题第3页，共70页，2023年，2月20日，星期三4.1.2模型分析

假设每月交费200元至60岁开始领取养老金，男子若25岁起投保，届时养老金每月2282元；如35岁起保，届时月养老金1056元；试求出保险公司为了兑现保险责任，每月至少应有多少投资收益率？这也就是投保人的实际收益率。第4页，共70页，2023年，2月20日，星期三4.1.3模型假设

这应当是一个过程分析模型问题。过程的结果在条件一定时是确定的。整个过程可以按月进行划分，因为交费是按月进行的。假设投保人到第月止所交保费及收益的累计总额为，每月收益率为，用分别表示60岁之前和之后每月交费数和领取数，N表示停交保险费的月份，M表示停领养老金的月份。第5页，共70页，2023年，2月20日，星期三4.1.4模型建立在整个过程中，离散变量的变化规律满足：在这里实际上表示从保险人开始交纳保险费以后，保险人账户上的资金数值。第6页，共70页，2023年，2月20日，星期三4.1.4模型建立

我们关心的是，在第M月时，FK能否为非负数？如果为正，则表明保险公司获得收益；如为负，则表明保险公司出现亏损。当为零时，表明保险公司最后一无所有，所有的收益全归保险人，把它作为保险人的实际收益。

从这个分析来看，引入变量FK，很好地刻画了整个过程中资金的变化关系；特别是引入收益率r，虽然它不是我们所求的保险人的收益率，但从问题系统环境中来看，必然要考虑引入另一对象——保险公司的经营效益，以此作为整个过程中各量变化的表现基础。第7页，共70页，2023年，2月20日，星期三4.1.5

模型求解在(4.1.4)中两式，取初始值，我们可以得到：再分别取，k=N和k=M，并利用FM=0可以求出：它是一个非线性方程。第8页，共70页，2023年，2月20日，星期三

代数方程求根问题是一个古老的数学问题。早在16世纪就找到了三次、四次方程的求根公式。但直到19世纪才证明了次的一般代数方程式是不能用代数公式求解的，因此需要研究用数值方法求得满足一定精度的代数方程式的近似解。

在工程和科学技术中许多问题常归结为求解非线性方程式问题。正因为非线性方程求根问题是如此重要和基础，因此它的求根问题很早就引起了人们的兴趣，并得到了许多成熟的求解方法。下面就让我们首先了解一下非线性方程的基本概念。第9页，共70页，2023年，2月20日，星期三4.2.1根的搜索相关定义定义4.2.1设有一个非线性方程，其中

为实变量的非线性函数。（1）如果

有使，则称为方程的根，或为的零点。（2）当

为多项式，即则称

为次代数方程，包含指数函数或者三角函数等特殊函数时，则称为特殊方程。（3）如果

，其中。为正整数，则称

为

的

重根。当

时称为的单根。4.2非线性方程求根的数值方法第10页，共70页，2023年，2月20日，星期三定理4.2.1

设

为具有复系数的

次代数方程，则

在复数域上恰有个根（重根计算个）。如果

为实系数方程，则复数根成对出现，即当:

为的复根，则

亦是的根。定理4.2.2

设在连续,且

，则存在，使得，即在内存在实零点。第11页，共70页，2023年，2月20日，星期三4.2.2逐步搜索法

对于方程，，为明确起见，设

,

，从区间左端点，出发按某个预定步长（如取

，

为正整数），一步一步地向右跨，每跨一步进行一次根的收索。即检查节点

上的函数值的符号，若，则即为方程解。若，则方程根在区间

中，其宽度为。第12页，共70页，2023年，2月20日，星期三4.2.2逐步搜索法例4.2.1

考察方程

由于

则

在

内至少有一个根，设从

出发，以

为步长向右进行根的搜索。列表记录各节点函数值的符号。可见在

内必有一根。

表4.2.1

的符号x00.51.01.5的符号---+第13页，共70页，2023年，2月20日，星期三4.2.2逐步搜索法

易见此方法应用关键在步长的选择上。很明显，只要步长取得足够小，利用此法就可以得到任意精度的根，但缩小，搜索步数增多，从而使计算量增大，用此方法对高精度要求不合适。第14页，共70页，2023年，2月20日，星期三4.2.3二分法对非线性方程：

其中在连续且

无妨设

在内仅有一个零点。

求方程（）的实根的二分法过程，就是将逐步分半，检查函数值符号的变化，以便确定包含根的充分小区间。第15页，共70页，2023年，2月20日，星期三二分法的步骤如下：记

，

第1步：分半计算，将

分半。计算中点

及。若，则根必在

内，否则必在

内，（若

，则），于是得到长度一半的区间含根,即,且

。

第步（*分半计算）重复上述过程。第16页，共70页，2023年，2月20日，星期三设已完成第1步…第步，分半计算得到含根区间，且满足

,即

，

即

，

则第k步的分半计算：，且有：第17页，共70页，2023年，2月20日，星期三确定新的含根区间，即如果，则根必在内，否则必在

内，且有：

。总之，由上述二分法得到序列，由(4.2.2)有：。可用二分法求方程的实根的近似值到任意指定的精度，这是因为：设为给定精度要求，则由，可得分半计算次数k应满足：第18页，共70页，2023年，2月20日，星期三

二分法的优点是方法简单，且只要求连续即可，可用二分法求出在内全部实根，但二分法不能求复根及偶数重根，且收敛较慢，函数值计算次数较多。第19页，共70页，2023年，2月20日，星期三例4.2.2

用二分法求

在[1,2]内一个实根，且要求精确到小数点后第三位。（即）

解

由代入公式(4.2.3)，可确定所需分半次数为，计算结果部分如下表：（显然）。第20页，共70页，2023年，2月20日，星期三K81.1328131.1406251.1367190.02061991.1328131.1367191.1347660.4268415101.1328131.1347661.133789111.1337891.1347661.134277表4.2.2部分计算结果第21页，共70页，2023年，2月20日，星期三4.2.4迭代法

迭代法是一种逐次逼近法。它是求解代数方程，超越方程及方程组的一种基本方法，但存在收敛性及收敛快慢的问题。

用迭代法求解的近似根，首先需将此方程化为等价的方程：

然而将化为等价方程的方法是很多的。第22页，共70页，2023年，2月20日，星期三

例4.2.3

对方程可用不同的方法将其化为等价方程：

（1）

（2）第23页，共70页，2023年，2月20日，星期三定义4.2.2（迭代法）设方程为取方程根的一个初始近似，且按下述逐次代入法，构造一个近似解序列：

这种方法称为迭代法（或称为单点迭代法），称为迭代函数。若由迭代法产生序列

有极限存在，即，称为收敛或迭代过程

收敛，否则称迭代法不收敛。若连续，且，则

，

即

为方程

的解（称为函数的不动点），显然在由方程

转化为等价方程时，选择不同的迭代函数，就会产生不同的序列（即使初值选择一样）且这些序列的收敛情况也不会相同。第24页，共70页，2023年，2月20日，星期三例4.2.4对例4.2.1中方程考查用迭代法求根

由计算可以看出，我们选取的两个函数

，分别构造序列收敛情形不一样（初值都取为1），在中

收敛且，在中计算出

无定义。第25页，共70页，2023年，2月20日，星期三01.01.011.3414710.52359921.4738200.02360131.049530-0.49655541.497152-1.48776151.49728961.49730071.497300表4.2.3部分计算结果第26页，共70页，2023年，2月20日，星期三

因此对用迭代法求方程

的近似根，需要研究下述问题：

（1）如何选取迭代函数使迭代过程收敛。

（2）若收敛较慢时，怎样加速收敛。第27页，共70页，2023年，2月20日，星期三迭代法的几何意义：

从几何意义看，求方程根的问题，是求曲线与直线交点的横坐标，当迭代函数的导数函数在根处满足下述几种条件时，从几何上来看迭代过程

的收敛情况如图4.2.1。

从曲线上一点出发，沿着平行于x轴方向前进交

于一点再从点沿平行于y轴方向前进交于点，显然的横坐标就是，继续这过程就得到序列，且从几何上观察知道在（1），（2）情况下收敛于，在（3），（4）情况不收敛于。第28页，共70页，2023年，2月20日，星期三图4.2.1迭代法的几何意义图第29页，共70页，2023年，2月20日，星期三

由迭代法的几何定义知，为了保证迭代过程收敛，应该要求迭代函数的导数满足条件

。当时，原方程在

中可能有几个根或迭代法不收敛，为此有关于迭代收敛性的定理4.2.3。

定理4.2.3设有方程

，(1)设于一阶导数存在，(2)

当时，有

，

(3)满足条件：则有：

在上有唯一解，

对任意选取初始值，迭代过程

收敛即，误差估计第30页，共70页，2023年，2月20日，星期三证明

只证，，

由定理条件

，当取时，则有记误差，由中值定理有：，其中

在与

之间，即，又由条件有：，由此递推可得：

，由

故。

由迭代公式有：，其中c在与之间，于是：

即

。第31页，共70页，2023年，2月20日，星期三

由上面

反复利用代入上式中有：

由定理结果可知，当计算得到的相邻两次迭代满足条件

时，则误差。

因此在计算机上可利用来控制算法终止，但要注意时，即使很小，误差

仍然可能很大。

另外，当已知及

及给定精度要求时，利用定理

结果可确定使误差达到给定精度要求时所需要迭代次数k，事实上，由

解得：

第32页，共70页，2023年，2月20日，星期三

定理条件，在一般情况下，可能对大范围的含根区间不满足，而在根的邻近是成立的，为此有如下迭代过程的局部收敛性结果。

定理4.2.4（迭代法的局部收敛性）设给定方程

（1）设为方程的解，

（2）设在的邻域内连续可微，且有

，则对任意初值（在的邻域内），迭代过程，

收敛于。第33页，共70页，2023年，2月20日，星期三例4.2.5由迭代法解方程第34页，共70页，2023年，2月20日，星期三解

(1)显然有即知方程于[0,2]及[-1.9,-1]内有根记为。

(2)考察取初值迭代过程的收敛性，其中迭代函数为，显然

，

，及为增函数，则当时，，又由则有

。

于是由定理4.2.4可知，当初值时，迭代过程收敛，如果要求的近似根准确到小数点后第6位（即要求）由计算结果可知。且则

，

。第35页，共70页，2023年，2月20日，星期三表4.2.4部分计算结果表00.010.6931471820.99071046141.1461931151.1461932第36页，共70页，2023年，2月20日，星期三

(3)为了求[-1.9,-1]内方程的根。由迭代方程

，显然，所以迭代过程（初值）不能保证收敛于。

(4)若将方程转化为等价方程

或则，且（

时）

所以当选取时迭代过程收敛。如取，则迭代12次有，且。

由此例可见，对于方程，迭代函数取不同形式，相应的迭代法产生的

收敛情况也不一样，因此，我们应该选择迭代函数时构造的迭代过程收敛，且收敛较快。第37页，共70页，2023年，2月20日，星期三关于迭代公式的加工：对于收敛的迭代过程，只要迭代足够多次，总可以使结果达到任意的精度。但有时迭代收敛缓慢，从而使计算量变得很大，因此迭代过程的加速是一个很重要的课题。设

为根

的某个预测值，用迭代公式校正一次得：

由中值定理：，介于之间，若改变不大。近似地取某常数，则由

可以期望按上式右端求得的是比更好的近似值。

若将每得到一次改进值算作一步，并用和分别表示第步的校正值和改进值，则加速迭代计算方案如下：校正：改进：由于使用参数，这在实际应用中不方便，下面进行改进计算。第38页，共70页，2023年，2月20日，星期三

设

的某近似值，将校正值

再校正一次得：，由与得：

由此得：

。这样将上式右端作为改进公式就不再含有导数信息了。但需要用到两次迭代的结果进行加工。如果仍将得到一次改进值作为一步，则计算过程如下：

上述处理过程称为（埃特金）方法。第39页，共70页，2023年，2月20日，星期三4.2.5Newton公式

对于方程，应用迭代法时先要改写成，即需要针对

构造不同的合适的迭代函数，显然可以取迭代函数为，相应迭代公式为。一般地，这种迭代公式不一定收敛，或者速度很慢。对此公式应用前面的加速技术具体格式为：

第40页，共70页，2023年，2月20日，星期三

记，则上二式可合并写为：。此公式称为简单的Newton公式，迭代函数为：

。又由于

为的近似值，而，因此实际上是

的近似值，故用

代替上式中的即得到下面的迭代函数：

。

相应的迭代公式为：

，

即为Newton公式。第41页，共70页，2023年，2月20日，星期三4.2.6Newton法的几何意义

Newton法的基本思想就是将非线性方程逐步线性化求解，设有近似的根，将在处展开得：

从而

近似地表为：

。方程

的根即为曲线

与轴焦点的横坐标。设为

近似值，过曲线上横坐标

为的点作曲线的切线，该切线

与轴焦点的横坐标即为

的新近似

值

，它与轴交点的横坐标为：

，因此

Newton法亦称切线法。第42页，共70页，2023年，2月20日，星期三4.2.7Newton法的局部收敛性定义4.2.3

设迭代过程收敛于方程

的根，如果迭代误差，当时有：

则称该迭代过程为阶收敛的。定理4.2.5

对迭代过程

如果在附近连续，且：且，则该迭代过程在附近是阶收敛的。第43页，共70页，2023年，2月20日，星期三

证明

由于，则有前面关于迭代法的局部收敛性定理知：此迭代过程具有局部收敛性。即。将在处展开，并注意到

有：而，从而上式化为：

第44页，共70页，2023年，2月20日，星期三

即：

故知迭代过程具有阶收敛性。

定理4.2.5

表明迭代过程的收敛速度依赖于迭代函数

的选取，如果时。则迭代过程只可能是线性收敛的。

对于Newton法，由迭代函数为：则

，

若

为

的一个单根。即

，则由上式知

。

由上面定理可知Newton法在根的邻域内是平方收敛的（二阶收敛

的）。第45页，共70页，2023年，2月20日，星期三

特别地考察Newton公式：设二次连续可微，则

，在

之间，特别地取，注意，则

设。两边同除以，得：

（注：

），利用Newton公式，即有：

当，则，

或第46页，共70页，2023年，2月20日，星期三

可见（误差）与的误差的平方成比例。当初始误差

充分小时，以后迭代的误差将减少得非常快。反之

，则放大。Newton法每计算一步，需要计算一次函数值和一次导数值。

例4.2.6

用Newton法求解

。解显然

。则在[0,2]内方程有一个根，求导

则Newton公式为：

取

，迭代6次得近似根为

,。这表明，当初值取值靠近时，Newton法收敛且收敛较快，否则Newton法可能不收敛。第47页，共70页，2023年，2月20日，星期三

下面考虑Newton法的误差估计，由中值定理有：，当

充分接近时，有因此，用Newton法求方程单根的近似根的误差可用来估计。第48页，共70页，2023年，2月20日，星期三4.2.8Newton法应用举例1.对给定的正数，应用Newton法解二次方程可导出求开方值的计算格式：

可证明公式对任意函数初值

都是收敛的。这是因为：第49页，共70页，2023年，2月20日，星期三

两式相除得：

利用此式递推可得：

（由可知：，则：

）而，

故由公式知

即迭代法恒收敛。）第50页，共70页，2023年，2月20日，星期三

例4.2.7

求的近似值，要求终止迭代。

解

取

经6次迭代后：

，

，，故

。

对给定正数，应用Newton法求解

，由此式可导出求而不用除法的计算程序：

。

这个算法对于没有设置除法操作的电子计算机是有用的。可以证明，此算法初值满足时是收敛的，这是因为：

即：，令，有递推公式：，反复递推得：。

当，即时，有

即，从而迭代法收敛。第51页，共70页，2023年，2月20日，星期三4.2.9Newton下山法

Newton法收敛性依赖于

初值的选取，如果偏离较远，则Newton法可能发散。

例如，对方程。求在附近的一个根。若取初值，则由Newton法：

计算得

，仅迭代3次即得有6位有效数字的近似值。但若取初值则由同一Newton公式计算得，这反而比更远离所求根，因此发散。为防止发散，对迭代过程加一下降要求：

满足这项要求的算法称为下山法。第52页，共70页，2023年，2月20日，星期三

将Newton法与下山法结合，即在下山法保证函数下降条件下，用Newton法加速收敛。为此，可将Newton计

算结果

与每一步近似值作加权均：

，其中（）称为下山

因子。选择下山因子以保证下降性。的选择方法是：由

反复减半的试探法，若能找到使下降性成立，则下山成功，否则下山失败，改变初值

重新开始。第53页，共70页，2023年，2月20日，星期三4.2.10弦截法与拋物法

Newton法

每迭代一次计算函数值，导数值各一次，当函数本身比较复杂时，求导数值更加困难。

下面方法多利用以前各次计算的函数值来回避导数值的计算，导出这种求根方法的基本原理是插值法。设是的一组近似值，利用对应的函数值，构造插值多项式，适当选取

的一个根作为的新的近似根

。这样就确定了一个迭代过程，记迭代函数为，则，下面具体考察（弦截法），（拋物法）两种情形。第54页，共70页，2023年，2月20日，星期三4.2.11弦截法

设为的近似根，过点，构造一次插值多项式，并用的根作为的新的近似根。由于

则由

可得：

另外，公式(4.2.9)也可以用导数的差商近似取代Newton公式中的，同样得公式。第55页，共70页，2023年，2月20日，星期三弦截法的几何意义：

如图，曲线上横坐标为的点分别记为，则弦线的斜率等于差商

。

的方程为：

则按

求得的近似根实际上是弦线与轴交点的横坐标。因此这种算法称为弦截法，又称割线法。第56页，共70页，2023年，2月20日，星期三

弦截法与切线法（Newton法）都是线性化方程，但两者有本质区别。Newton切线法在计算时只用到前一步的及，但要计算，而弦截法在计算

时要用前面两步的结果

，而不须计算导数。这种方法必须有两个启动值。

例4.2.8用割线法求解方程在

的根。

解取初值，则迭代5次后有

，

。例子表明弦截法仍具有较快的收敛性。

定理4.2.6

假设在根领域内具有二阶连续导

数，且对有。又初值，那么当邻域充

分小时，弦截法将按阶收敛到根。

(证明略)第57页，共70页，2023年，2月20日，星期三

下面分析弦截法用于求解

时，对Atken加速算法的几何解释：

为

的近似根，

，在曲线上走了两点，

引弦线

与直线

交于一点

，则的横坐标（与纵坐标相等）为：

此即为Atken加速计算方法的公式。再看右图，所求的根是曲线

与

的交点

的横坐标，从图形上看，尽管迭代值

比

和

更远偏离了

，但按上式求得的

却明显地扭转了这种发散的趋势。第58页，共70页，2023年，2月20日，星期三4.2.12

拋物线法

设已知的三个近似根为，以这三点为节点构造二次插值多项式，并适当选取

的一个零点作为新的近似根。这样确定的迭代过程称为拋物线法（亦称密勒法）。拋物线插值多项式为：有两个零点：其中，第59页，共70页，2023年，2月20日，星期三

其几何意义就是：用抛物线

与轴的交点作为所求根的近似值。如右图。为了由

定出一个值，需讨论根式前正负符号的取舍问题在

三个近似根中，自然假定以更接近所求的根，这时为保证精度，选取

中较近的一个值作为新的近似根，为此，只要令根式前的符号与的符号相同。第60页，共70页，2023年，2月20日，星期三

例4.2.9

用抛物线法求解方程

解取三个初值，

计算

，

，

，

，

，，

，

从而：。第61页，共70页，2023年，2月20日，星期三

定理4.2.7

若在根的邻域内有三节连续偏导数，且对，有。又初值，那么当领域充分小时，抛物线法(4.2.8)将按阶

收敛于根。

可见抛物线法比弦截法的收敛性更接近于Newton法。定理的证明略。第62页，共70页，2023年，2月20日，星期三4.2.13多项式求值的秦九韶算法

多项式的重要特点之一是求值方便，设，系数均为实数。用除，记其商为，则其余项显然