科学计算与数学建模科学计算与数学建模中南大学数学科学与计算技术学院中南大学数学科学与计算技术学院 养老保险问题养老保险问题第四章第四章 养老保险问题养老保险问题 非线性方程求根的数值解法非线性方程求根的数值解法养老保险问题养老保险问题4.1非线性方程求根的数值方法非线性方程求根的数值方法4.2养老保险模型的求解养老保险模型的求解4.34.1.1 4.1.1 问题的引入问题的引入 养养老老保保险险是是保保险险中中的的一一种种重重要要险险种种，保保险险公公司司将将提提供供不不同同的的保保险险方方案案供供以以选选择择，分分析析保保险险品品种种的的实实际际投投资资价价值值。也也就就是是说说，如如果果已已知知所所交交保保费费和和保保险险收收入入，则则按按年年或或按按月月计计算算实实际际的的利利率率是是多多少少？或或者者说说，保保险险公公司司需需要要用用你你的的保保费费实实际际至至少少获获得得多多少少利利润润才才能能保保证证兑兑现现你你的的保险收益？保险收益？4.1 4.1 养老保险问题养老保险问题4.1.2 4.1.2 模型分析模型分析 假设每月交费假设每月交费200200元至元至6060岁开始领取养老金，男子若岁开始领取养老金，男子若2525岁起投保，届时养老金每月岁起投保，届时养老金每月22822282元；如元；如3535岁起保，届岁起保，届时月养老金时月养老金10561056元；试求出保险公司为了兑现保险责任，元；试求出保险公司为了兑现保险责任，每月至少应有多少投资收益率？这也就是投保人的实际每月至少应有多少投资收益率？这也就是投保人的实际收益率。收益率。4.1.3 4.1.3 模型假设模型假设 这应当是一个过程分析模型问题。过程的结果在条这应当是一个过程分析模型问题。过程的结果在条件一定时是确定的。整个过程可以按月进行划分，因为件一定时是确定的。整个过程可以按月进行划分，因为交费是按月进行的。假设投保人到第月止所交保费及收交费是按月进行的。假设投保人到第月止所交保费及收益的累计总额为，每月收益率为，用分别表示益的累计总额为，每月收益率为，用分别表示6060岁之前岁之前和之后每月交费数和领取数，和之后每月交费数和领取数，N N表示停交保险费的月份，表示停交保险费的月份，M M表示停领养老金的月份。表示停领养老金的月份。4.1.4 4.1.4 模型建立模型建立v在整个过程中，离散变量的变化规律满足：在整个过程中，离散变量的变化规律满足：v在这里实际上表示从保险人开始交纳保险费以后，保险在这里实际上表示从保险人开始交纳保险费以后，保险人账户上的资金数值。人账户上的资金数值。 4.1.4 4.1.4 模型建立模型建立v 我们关心的是，在第我们关心的是，在第M M月时，月时， FK FK 能否为非负能否为非负 数？数？如果为正，则表明保险公司获得收益；如为负，则表明如果为正，则表明保险公司获得收益；如为负，则表明保险公司出现亏损。当为零时，表明保险公司最后一无保险公司出现亏损。当为零时，表明保险公司最后一无所有，所有的收益全归保险人，把它作为保险人的实际所有，所有的收益全归保险人，把它作为保险人的实际收益。收益。 v 从这个分析来看，引入变量从这个分析来看，引入变量FKFK，很好地刻画了整个，很好地刻画了整个过程中资金的变化关系；特别是引入收益率过程中资金的变化关系；特别是引入收益率 r r，虽然它，虽然它不是我们所求的保险人的收益率，但从问题系统环境中不是我们所求的保险人的收益率，但从问题系统环境中来看，必然要考虑引入另一对象来看，必然要考虑引入另一对象保险公司的经营效保险公司的经营效益，以此作为整个过程中各量变化的表现基础。益，以此作为整个过程中各量变化的表现基础。4.1.5 4.1.5 模型求解模型求解在在(4.1.4)(4.1.4)中两式，取初始值，我们可以得到：中两式，取初始值，我们可以得到：再分别取，再分别取，k=Nk=N和和k=Mk=M，并利用，并利用FM=0FM=0可以求出：可以求出：它是一个非线性方程。它是一个非线性方程。 代数方程求根问题是一个古老的数学问题。早在代数方程求根问题是一个古老的数学问题。早在1616世纪就找到了三次、四次方程的求根公式。但直到世纪就找到了三次、四次方程的求根公式。但直到1919世世纪才证明了纪才证明了 次的一般代数方程式是不能用代数公式次的一般代数方程式是不能用代数公式求解的，因此需要研究用数值方法求得满足一定精度的求解的，因此需要研究用数值方法求得满足一定精度的代数方程式的近似解。代数方程式的近似解。 在工程和科学技术中许多问题常归结为求解非线性方在工程和科学技术中许多问题常归结为求解非线性方程式问题。正因为非线性方程求根问题是如此重要和基程式问题。正因为非线性方程求根问题是如此重要和基础，因此它的求根问题很早就引起了人们的兴趣，并得础，因此它的求根问题很早就引起了人们的兴趣，并得到了许多成熟的求解方法。下面就让我们首先了解一下到了许多成熟的求解方法。下面就让我们首先了解一下非线性方程的基本概念。非线性方程的基本概念。4.2.1 根的搜索相关定义根的搜索相关定义定义定义4.2.1 4.2.1 设有一个非线性方程设有一个非线性方程 ，其中，其中 为实变为实变量量 的非线性函数。的非线性函数。（1 1）如果）如果 有使有使 ，则称，则称 为方程的根，或为为方程的根，或为 的零点。的零点。（2 2）当）当 为多项式，即为多项式，即 则称则称 为为 次代数方程，次代数方程， 包含指数函数或者三角包含指数函数或者三角函数等特殊函数时，则称函数等特殊函数时，则称 为特殊方程。为特殊方程。（3 3）如果）如果 ，其中，其中 。 为正整数，则为正整数，则称称 为为 的的 重根。当重根。当 时称时称 为为 的单根。的单根。4.2 4.2 非线性方程求根的数值方法非线性方程求根的数值方法定理定理 设设 为具有复系数的为具有复系数的 次代数方程，则次代数方程，则 在复数域上恰有在复数域上恰有 个根个根（ 重根计算重根计算 个）。如果个）。如果 为实系数方程，则复数根成对出现，即当为实系数方程，则复数根成对出现，即当: : 为为 的复根，则的复根，则 亦是亦是 的根。的根。定理定理4.2.2 4.2.2 设设 在在 连续连续, ,且且 ，则存，则存在在 ，使得，使得 ，即，即 在在 内存在实零点。内存在实零点。4.2.2 4.2.2 逐步搜索法逐步搜索法v 对于方程对于方程 ， ，为明确起见，设，为明确起见，设 , , ，从区间左端点，从区间左端点 ，出发按某个预定步长，出发按某个预定步长 （如取（如取 ， 为正整数），一步一步地向右跨，为正整数），一步一步地向右跨，每跨一步进行一次根的收索。即检查节点每跨一步进行一次根的收索。即检查节点 上的函数值上的函数值 的符号，若的符号，若 ，则，则 即即为方程解。若为方程解。若 ，则方程根在区间，则方程根在区间 中，其中，其宽度为宽度为 。 4.2.2 4.2.2 逐步搜索法逐步搜索法例例 考察方程考察方程 由于由于 则则 在在 内至少有一个根，内至少有一个根，设从设从 出发，以出发，以 为步长向右进行根的搜索。列为步长向右进行根的搜索。列表记录各节点函数值的符号。可见在表记录各节点函数值的符号。可见在 内必有一根。内必有一根。 表表 的符号的符号x00.51.01.5 的符号-+4.2.2 4.2.2 逐步搜索法逐步搜索法 易见此方法应用关键在步长易见此方法应用关键在步长 的选择上。的选择上。很明显，只要步长很明显，只要步长 取得足够小，利用此法就取得足够小，利用此法就可以得到任意精度的根，但可以得到任意精度的根，但 缩小，搜索步数缩小，搜索步数增多，从而使计算量增大，用此方法对高精度要增多，从而使计算量增大，用此方法对高精度要求不合适。求不合适。4.2.3 4.2.3 二分法二分法对非线性方程：对非线性方程： 其中其中 在在 连续且连续且 无妨设无妨设 在在 内仅有一个零点。内仅有一个零点。 求方程（求方程（ ）的实根）的实根 的二分法过程，的二分法过程，就是将就是将 逐步分半，检查函数值符号的变化，逐步分半，检查函数值符号的变化，以便确定包含根的充分小区间。以便确定包含根的充分小区间。二分法的步骤如下：二分法的步骤如下：记记 ， 第第1 1步：分半计算步：分半计算 ，将，将 分半。计算中点分半。计算中点 及及 。若。若 ，则根必在，则根必在 内，否则必在内，否则必在 内，（若内，（若 ，则，则 ），于是得到长度一半的区间），于是得到长度一半的区间 含根含根, ,即即 , ,且且 。 第第 步（步（* *分半计算）重复上述过程。分半计算）重复上述过程。设已完成第设已完成第1 1步步第第 步，分半计算得到含根步，分半计算得到含根区间区间 ，且满，且满足足 , ,即即 ， 即即 ， 则第则第k k步的分半计算：步的分半计算： ，且有：，且有：确定新的含根区间确定新的含根区间 ，即如果，即如果 ，则根必在则根必在 内，否则必内，否则必在在 内，且有：内，且有： 。总之，由上。总之，由上述二分法得到序列述二分法得到序列 ，由，由(4.2.2)(4.2.2)有：有： 。可用二分法求方程可用二分法求方程 的实根的实根 的近似值到的近似值到任意指定的精度，这是因为：设任意指定的精度，这是因为：设 为给定为给定精度要求，则由精度要求，则由 ，可得分，可得分半计算次数半计算次数k k应满足：应满足： 二分法的优点是方法简单，且只要求二分法的优点是方法简单，且只要求 连续即可，可用二分法求出连续即可，可用二分法求出 在在 内全部实根，但二分法不能求复根内全部实根，但二分法不能求复根及偶数重根，且收敛较慢，函数值计算次数较多。及偶数重根，且收敛较慢，函数值计算次数较多。 例例4.2.2 4.2.2 用二分法求用二分法求 在在1,21,2内一内一个实根，且要求精确到小数点后第三位。（即个实根，且要求精确到小数点后第三位。（即 ） 解解 由由 代入公式代入公式(4.2.3) (4.2.3) ，可确定所需分半次数为可确定所需分半次数为 ，计算结果部分如下表：，计算结果部分如下表：（显然（显然 ）。）。K81.132813 1.140625 1.136719 0.020619 91.132813 1.136719 1.134766 0.4268415 101.132813 1.134766 1.133789 111.133789 1.134766 1.134277 表表4.2.2 4.2.2 部分计算结果部分计算结果4.2.4 4.2.4 迭代法迭代法 迭代法迭代法是一种逐次逼近法。它是求解代数方程，超是一种逐次逼近法。它是求解代数方程，超越方程及方程组的一种基本方法，但存在收敛性及收敛越方程及方程组的一种基本方法，但存在收敛性及收敛快慢的问题。快慢的问题。 用用迭迭代代法法求求解解 的的近近似似根根，首首先先需需将将此此方方程化为等价的方程：程化为等价的方程： 然而将然而将 化为等价方程化为等价方程 的方法是很的方法是很多的。多的。 例例4.2.3 4.2.3 对方程对方程 可用不同的方法将其化为等价方程：可用不同的方法将其化为等价方程： （1 1） （2 2）定义定义4.2.2 （迭代法）（迭代法）设方程为设方程为 取方程根的一个初始近似取方程根的一个初始近似 ，且按下述逐次代入法，构造一个近似解序列：，且按下述逐次代入法，构造一个近似解序列： 这种方法称为迭代法（或称为单点迭代法），这种方法称为迭代法（或称为单点迭代法）， 称为迭代函数。称为迭代函数。若由迭代法产生序列若由迭代法产生序列 有极限存在，即有极限存在，即 ，称，称 为收为收敛或迭代过程敛或迭代过程 收敛，否则称迭代法不收敛。若收敛，否则称迭代法不收敛。若 连续，连续，且且 ，则，则 ， 即即 为方程为方程 的解（称的解（称 为函数为函数 的不动点），显然的不动点），显然在由方程在由方程 转化为等价方程转化为等价方程 时，选择不同的迭代时，选择不同的迭代函数函数 ，就会产生不同的序列，就会产生不同的序列 （即使初值（即使初值 选择一样）且选择一样）且这些序列的收敛情况也不会相同。这些序列的收敛情况也不会相同。例例4.2.4 4.2.4 对例中方程考查用迭代法求根对例中方程考查用迭代法求根 由计算可以看出，我们选取的两个函数由计算可以看出，我们选取的两个函数 ，分别构造序列分别构造序列 收敛情形不一样（初值都取为收敛情形不一样（初值都取为1 1），），在在 中中 收敛且收敛且 ，在，在 中计算出中计算出 无定义。无定义。0 1.0 1.0 11.341471 0.523599 21.473820 0.023601 31.049530 -0.496555 41.497152 -1.487761 51.497289 61.497300 71.497300 表表4.2.3 4.2.3 部分计算结果部分计算结果 因此对用迭代法求方程因此对用迭代法求方程 的近似根，的近似根，需要研究下述问题：需要研究下述问题： （1 1）如何选取迭代函数）如何选取迭代函数 使迭代过程使迭代过程 收敛。收敛。 （2 2）若）若 收敛较慢时，怎样加速收敛较慢时，怎样加速 收敛。收敛。 迭代法的几何意义：迭代法的几何意义： 从几何意义看，求方程从几何意义看，求方程 根的问题，是求曲线根的问题，是求曲线 与直线与直线 交点的横坐标交点的横坐标 ，当迭代函数，当迭代函数 的导数函数的导数函数 在根在根 处满足下述几种条件时，从几何上来看迭代过程处满足下述几种条件时，从几何上来看迭代过程 的收敛情况如图。的收敛情况如图。 从曲线从曲线 上一点上一点 出发，沿着平行于出发，沿着平行于x x轴方轴方向前进交向前进交 于一点于一点 再从点再从点 沿平行于沿平行于y y轴方向前进交轴方向前进交 于于 点，显然点，显然 的横坐标就是的横坐标就是 ，继续这过程就得到序，继续这过程就得到序列列 ，且从几何上观察知道在（，且从几何上观察知道在（1 1），（），（2 2）情况下）情况下 收敛于收敛于 ，在（，在（3 3），（），（4 4）情况）情况 不收敛于不收敛于 。 图图4.2.1 4.2.1 迭代法的几何意义图迭代法的几何意义图 由迭代法的几何定义知，为了保证迭代过程收敛，应该要求迭代函由迭代法的几何定义知，为了保证迭代过程收敛，应该要求迭代函数的导数满足条件数的导数满足条件 。当。当 时，原方程在时，原方程在 中可能中可能有几个根或迭代法不收敛，为此有关于迭代收敛性的定理。有几个根或迭代法不收敛，为此有关于迭代收敛性的定理。 定理定理4.2.3 4.2.3 设有方程设有方程 ， (1) (1) 设设 于于 一阶导数存在，一阶导数存在， (2) (2) 当当 时，有时，有 ， ( (3) 3) 满足条件：满足条件： 则有：则有： 在在 上有唯一解上有唯一解 ， 对任意选取初始值对任意选取初始值 ，迭代过程，迭代过程 收敛即收敛即 ， 误差估计误差估计证明证明 只证只证 ， ， 由定理条件由定理条件 ，当取，当取 时，则有时，则有 记误差记误差 ，由中值定理有：，由中值定理有： ，其中其中 在在 与与 之间，即之间，即 ，又由条件有：，又由条件有： ，由此递推可得：，由此递推可得： ，由，由 故故 。 由迭代公式由迭代公式 有：有： ，其中，其中c c在在 与与 之间，于是：之间，于是： 即即 。 由上面由上面 反复利用代入上式中有反复利用代入上式中有： 由定理由定理 结果可知，当计算得到的相邻两次迭代满足条件结果可知，当计算得到的相邻两次迭代满足条件 时，则误差时，则误差 。 因此在计算机上可利用因此在计算机上可利用 来控制算法终止，但要来控制算法终止，但要注意注意 时，即使时，即使 很小，误差很小，误差 仍然可能很大。仍然可能很大。 另外，当已知另外，当已知 及及 及给定精度要求及给定精度要求 时，利用定时，利用定理理 结果可确定使误差达到给定精度要求时所需要迭代次数结果可确定使误差达到给定精度要求时所需要迭代次数k k，事，事实上，由实上，由 解得：解得： 定理条件定理条件 ，在一般情况下，可能对大，在一般情况下，可能对大范围的含根区间不满足，而在根的邻近是成立的，为此有范围的含根区间不满足，而在根的邻近是成立的，为此有如下迭代过程的局部收敛性结果。如下迭代过程的局部收敛性结果。 定理定理4.2.4 4.2.4 （迭代法的局部收敛性）设给定方程（迭代法的局部收敛性）设给定方程 （1 1）设）设 为方程的解，为方程的解， （2 2）设）设 在在 的邻域内连续可微，且有的邻域内连续可微，且有 ，则对任意初值则对任意初值 （在（在 的邻域内），迭代过程的邻域内），迭代过程 ， 收敛于收敛于 。例例4.2.5 4.2.5 由迭代法解方程由迭代法解方程解解 (1)(1)显然有显然有 即知方程于即知方程于0,20,2及及-1.9,-1-1.9,-1内有根记为内有根记为 。 (2)(2)考察取初值考察取初值 迭代过程迭代过程 的收敛性，的收敛性，其中迭代函数为其中迭代函数为 ，显然，显然 ， ，及，及 为增函为增函数，则当数，则当 时，时， ，又由，又由 则有则有 。 于是由定理可知，当初值于是由定理可知，当初值 时，迭代过程时，迭代过程 收敛，如果要求收敛，如果要求 的近似根准确到小数点后第的近似根准确到小数点后第6 6位（即要位（即要求求 ）由计算结果可知）由计算结果可知 。且。且 ，则，则 ， 。 表表4.2.4 4.2.4 部分计算结果表部分计算结果表00.010.6931471820.99071046141.1461931151.1461932 (3)(3)为了求为了求-1.9,-1-1.9,-1内方程的根。由迭代方程内方程的根。由迭代方程 ，显，显然然 ，所以迭代过程，所以迭代过程 （初值（初值 ）不能保证收敛于）不能保证收敛于 。 (4)(4)若将方程转化为等价方程若将方程转化为等价方程 或或 则则 ，且，且 （ 时）时） 所以当选取所以当选取 时迭代过程时迭代过程 收敛。如取收敛。如取 ，则迭代则迭代1212次有次有 ，且，且 。 由此例可见，对于方程由此例可见，对于方程 ，迭代函数，迭代函数 取不同形式，取不同形式，相应的迭代法产生的相应的迭代法产生的 收敛情况也不一样，因此，我们应该选择收敛情况也不一样，因此，我们应该选择迭代函数时构造的迭代过程迭代函数时构造的迭代过程 收敛，且收敛较快。收敛，且收敛较快。关于迭代公式的加工：关于迭代公式的加工： 对于收敛的迭代过程，只要迭代足够多次，总可以使结果达到对于收敛的迭代过程，只要迭代足够多次，总可以使结果达到任意的精度。但有时迭代收敛缓慢，从而使计算量变得很大，因此任意的精度。但有时迭代收敛缓慢，从而使计算量变得很大，因此迭代过程的加速是一个很重要的课题。迭代过程的加速是一个很重要的课题。 设设 为根为根 的某个预测值，用迭代公式校正一次得：的某个预测值，用迭代公式校正一次得： 由中值定理：由中值定理： ， 介于介于 之间，若之间，若 改改变不大。近似地取某常数，则由变不大。近似地取某常数，则由 可以期望按上式右端求得的可以期望按上式右端求得的 是比更好的近似值。是比更好的近似值。 若将每得到一次改进值算作一步，并用若将每得到一次改进值算作一步，并用 和和 分别表示第分别表示第 步的校正值和改进值，则加速迭代计算方案如下：步的校正值和改进值，则加速迭代计算方案如下：校正：校正：改进：改进： 由于使用参数由于使用参数 ，这在实际应用中不方便，下面进行改进计算。，这在实际应用中不方便，下面进行改进计算。 设设 的某近似值的某近似值 ，将校正值，将校正值 再校正一次得：再校正一次得： ，由，由 与与 得：得： 由此得：由此得： 。这样将上式右端作为改。这样将上式右端作为改进公式就不再含有导数信息了。但需要用到两次迭代的结果进行加进公式就不再含有导数信息了。但需要用到两次迭代的结果进行加工。如果仍将得到一次改进值作为一步，则计算过程如下：工。如果仍将得到一次改进值作为一步，则计算过程如下： 上述处理过程称为（埃特金）方法。上述处理过程称为（埃特金）方法。4.2.5 Newton4.2.5 Newton公式公式 对于方程对于方程 ，应用迭代法时先要改写成，应用迭代法时先要改写成 ，即需要针对即需要针对 构造不同的合适的迭代函数构造不同的合适的迭代函数 ，显然可以取迭，显然可以取迭代函数为代函数为 ，相应迭代公式为，相应迭代公式为 。 一般地，这种迭代公式不一定收敛，或者速度很慢。对此公一般地，这种迭代公式不一定收敛，或者速度很慢。对此公式应用前面的加速技术具体格式为：式应用前面的加速技术具体格式为： 记记 ，则上二式可合并写为：，则上二式可合并写为： 。此公式称为简单的此公式称为简单的NewtonNewton公式，其迭代函数为：公式，其迭代函数为： 。又由于。又由于 为为 的近似值，而的近似值，而 ，因此，因此 实际上是实际上是 的近似值，故用的近似值，故用 代替上式中的代替上式中的 即得到下面的迭代函数：即得到下面的迭代函数： 。 相应的迭代公式为：相应的迭代公式为： ， 即为即为NewtonNewton公式。公式。4.2.6 Newton4.2.6 Newton法的几何意义法的几何意义 NewtonNewton法的基本思想法的基本思想就是将非线性方程就是将非线性方程 逐步线性化求逐步线性化求解，设解，设 有近似的根有近似的根 ，将，将 在在 处处 展开得：展开得： ，从而，从而 近似地表为：近似地表为： 。方程。方程 的根的根 即为曲线即为曲线 与与 轴焦点的横坐标。设轴焦点的横坐标。设 为为 的的 一个近似，过曲线一个近似，过曲线 上横坐标上横坐标 为为 的点的点 作曲线的切线，该切线作曲线的切线，该切线 与与 轴焦点的横坐标即为轴焦点的横坐标即为 的新近似的新近似 值值 ，它与，它与 轴交点的横坐标为：轴交点的横坐标为： ，因此，因此 NewtonNewton法亦称切线法。法亦称切线法。4.2.7 Newton4.2.7 Newton法的局部收敛性法的局部收敛性定义定义 设迭代过程设迭代过程 收敛于方程收敛于方程 的根的根 ，如果迭代误差如果迭代误差 ，当，当 时有：时有： 则称该迭代过程为则称该迭代过程为 阶收敛的。阶收敛的。定理定理 对迭代过程对迭代过程 如果如果 在在 附近连续，且：附近连续，且： 且且 ，则该迭代过程在，则该迭代过程在 附近是附近是 阶收敛的。阶收敛的。 证明证明 由于由于 ，则有前面关于迭代法的局部收敛性定理知：，则有前面关于迭代法的局部收敛性定理知：此迭代过程此迭代过程 具有局部收敛性。即具有局部收敛性。即 。将。将 在在 处处 展开，并注意到展开，并注意到 有：有： 而，而， 从而上式化为：从而上式化为： 即：即： 故知迭代过程具有故知迭代过程具有 阶收敛性。阶收敛性。 定理定理 表明迭代过程的收敛速度依赖于迭代函数表明迭代过程的收敛速度依赖于迭代函数 的选取，如果的选取，如果 时时 。则迭代过程只可能是线性收敛的。则迭代过程只可能是线性收敛的。 对于对于NewtonNewton法，由迭代函数为：法，由迭代函数为： 则则 ， 若若 为为 的一个单根。即的一个单根。即 ，则由上式知，则由上式知 。 由上面定理可知由上面定理可知NewtonNewton法在根法在根 的邻域内是平方收敛的（二阶收敛的邻域内是平方收敛的（二阶收敛 的）。的）。 特别地考察特别地考察NewtonNewton公式：设公式：设 二次连续可微，则二次连续可微，则 ， 在在 之间，特别地取之间，特别地取 ，注意，注意 ，则，则 设设 。两边同除以。两边同除以 ，得：，得： （注：（注： ），利用），利用NewtonNewton公式，即有：公式，即有： 当当 ，则，则 ， 或或 可见可见 （误差）与（误差）与 的误差的误差 的平方成比例。当初始误差的平方成比例。当初始误差 充分小时，以后迭代的误差将减少得非常快。反之充分小时，以后迭代的误差将减少得非常快。反之 ，则放大。则放大。NewtonNewton法每计算一步，需要计算一次函数值法每计算一步，需要计算一次函数值 和一次导数值和一次导数值 。 例例4.2.6 4.2.6 用用NewtonNewton法求解法求解 。 解解 显然显然 。则在。则在0,20,2内方程有一个根，求导内方程有一个根，求导 则则NewtonNewton公式为：公式为： 取取 ，迭代，迭代6 6次得近似根为次得近似根为 , , 。这。这表明，当初值表明，当初值 取值靠近取值靠近 时，时，NewtonNewton法收敛且收敛较快，否则法收敛且收敛较快，否则NewtonNewton法可能不收敛。法可能不收敛。 下面考虑下面考虑NewtonNewton法的误差估计，由中值定理有：法的误差估计，由中值定理有： ，当当 充分接近充分接近 时，有时，有 因此，用因此，用NewtonNewton法求方程单根法求方程单根 的近似根的近似根 的误差的误差 可用可用 来估计。来估计。 4.2.8 Newton4.2.8 Newton法应用举例法应用举例1. 1. 对对给给定定的的正正数数 ，应应用用NewtonNewton法法解解二二次次方方程程 可可导导出出求求开方值开方值 的计算格式：的计算格式： 可证明公式可证明公式 对任意函数初值对任意函数初值 都是收敛的。这是因为：都是收敛的。这是因为： 两式相除得：两式相除得： 利用此式递推可得：利用此式递推可得： （ 由由 可知：可知： ，则：，则： ）而）而 ， 故由公式知故由公式知 即迭代法恒收敛。）即迭代法恒收敛。） 例例 求求 的近似值，要求的近似值，要求 终止迭代。终止迭代。 解解 取取 经经6 6次迭代后：次迭代后： ， ， ，故，故 。 对给定正数对给定正数 ，应用，应用NewtonNewton法求解法求解 ，由此式可导出求，由此式可导出求 而不用除法的计算程序：而不用除法的计算程序： 。 这个算法对于没有设置除法操作的电子计算机是有用的。可以证明，这个算法对于没有设置除法操作的电子计算机是有用的。可以证明，此算法初值满足此算法初值满足 时是收敛的，这是因为：时是收敛的，这是因为： 即：即： ，令，令 ，有递推公式：，有递推公式： ，反复递推得：反复递推得： 。 当当 ，即，即 时，有时，有 即即 ，从，从而迭代法收敛。而迭代法收敛。 4.2.9 Newton4.2.9 Newton下山法下山法 NewtonNewton法收敛性依赖于法收敛性依赖于 初值的选取，如果初值的选取，如果 偏离偏离 较远，较远，则则NewtonNewton法可能发散。法可能发散。 例如，对方程例如，对方程 。求在。求在 附近的一个根附近的一个根 。若取初值若取初值 ，则由，则由NewtonNewton法：法： 计算得计算得 ，仅迭代，仅迭代3 3次即得有次即得有6 6位有效数字的近似值位有效数字的近似值 。但若取初值。但若取初值 则由同一则由同一NewtonNewton公公式计算得式计算得 ，这反而比，这反而比 更远离所求根更远离所求根 ，因此发散。为防止发散，对迭代过程加一下降要求：因此发散。为防止发散，对迭代过程加一下降要求： 满足这项要求的算法称为下山法。满足这项要求的算法称为下山法。 将将NewtonNewton法与下山法结合，即在下山法保证函数下降法与下山法结合，即在下山法保证函数下降条件下，用条件下，用NewtonNewton法加速收敛。为此，可将法加速收敛。为此，可将NewtonNewton计计 算结果算结果 与每一步近似值与每一步近似值 作加权均：作加权均： ，其中，其中 （ ）称为下山）称为下山 因子。选择下山因子因子。选择下山因子 以保证下降性。以保证下降性。 的选择方法是：由的选择方法是：由 反复减半的试探法，若能找反复减半的试探法，若能找到到 使下降性成立，则下山成功，否则下山失败，改变使下降性成立，则下山成功，否则下山失败，改变初值初值 重新开始。重新开始。 4.2.10 4.2.10 弦截法与弦截法与拋拋物法物法 NewtonNewton法法 每迭代一次计算函数值每迭代一次计算函数值 ，导，导数值数值 各一次，当各一次，当 函数本身比较复杂时，求导数值更加困难。函数本身比较复杂时，求导数值更加困难。 下面方法多利用以前各次计算的函数值下面方法多利用以前各次计算的函数值 来回避导来回避导数值数值 的计算，导出这种求根方法的基本原理是插值法。的计算，导出这种求根方法的基本原理是插值法。 设设 是是 的一组近似值，利用对应的函数值的一组近似值，利用对应的函数值 ，构造插值多项式，构造插值多项式 ，适当选取，适当选取 的一个根作为的一个根作为 的新的近似根的新的近似根 。这样就确定了一个迭代。这样就确定了一个迭代过程，记迭代函数为过程，记迭代函数为 ，则，则 ，下面具体考，下面具体考察察 （弦截法），（弦截法）， （拋拋物法）两种情形。物法）两种情形。 4.2.11 4.2.11 弦截法弦截法 设设 为为 的近似根，过点的近似根，过点 ， 构造构造一次插值多项式一次插值多项式 ，并用，并用 的根作为的根作为 的新的近似根的新的近似根 。由于。由于 则由则由 可得：可得： 另外，公式另外，公式(4.2.9)(4.2.9)也可以用导数也可以用导数 的差商的差商 近近似取代似取代NewtonNewton公式中的公式中的 ，同样得公式，同样得公式 。v弦截法的几何意义：弦截法的几何意义： 如图，曲线如图，曲线 上横坐标上横坐标为为 的点分别记为的点分别记为 ，则弦线则弦线 的斜率等于差商的斜率等于差商 。 的方程为：的方程为： 则按则按 求得的近似根求得的近似根 实际上是弦线实际上是弦线 与与 轴交点的轴交点的横坐标。因此这种算法称为弦截法，横坐标。因此这种算法称为弦截法，又称割线法。又称割线法。 弦截法与切线法（弦截法与切线法（NewtonNewton法）法）都是线性化方程，但两者有本质都是线性化方程，但两者有本质区别。区别。NewtonNewton切线法在计算切线法在计算 时只用到前一步的时只用到前一步的 及及 ，但要计算但要计算 ，而弦截法在计算，而弦截法在计算 时要用前面两步的结果时要用前面两步的结果 ，而不须计算导数。这种方法必须有两个启，而不须计算导数。这种方法必须有两个启动值动值 。 例例4.2.8 4.2.8 用割线法求解方程用割线法求解方程 在在 的根。的根。 解解 取初值取初值 ，则迭代，则迭代5 5次后有次后有 ， 。例子表明弦截法仍具有较快的收敛性。例子表明弦截法仍具有较快的收敛性。 定理定理 假设假设 在根在根 领域领域 内具有二阶连续导内具有二阶连续导 数，且对数，且对 有有 。又初值。又初值 ，那么当邻域，那么当邻域 充充 分小时，弦截法分小时，弦截法 将按阶将按阶 收敛到根收敛到根 。 ( (证明略证明略) ) 下面下面分析弦截法分析弦截法用于求解用于求解 时，时，对对AtkenAtken加速算法的几何解释：加速算法的几何解释： 为为 的近似根，的近似根， ， 在曲线上走了两点在曲线上走了两点 ， 引弦线引弦线 与直线与直线 交于一交于一点点 ，则，则 的横坐标（与纵坐标相等）的横坐标（与纵坐标相等）为：为： 此即为此即为AtkenAtken加速计算方法的公式。加速计算方法的公式。再看右图，所求的根再看右图，所求的根 是曲线是曲线 与与 的交点的交点 的横坐标，从图形上看，的横坐标，从图形上看，尽管迭代值尽管迭代值 比比 和和 更远偏离了更远偏离了 ，但按上式求得的但按上式求得的 却明显地扭转了这种却明显地扭转了这种发散的趋势。发散的趋势。4.2.12 4.2.12 拋拋物线法物线法 设已知设已知 的三个近似根为的三个近似根为 ，以这三点为节点，以这三点为节点构造二次插值多项式构造二次插值多项式 ，并适当选取，并适当选取 的一个零点的一个零点 作作为新的近似根。这样确定的迭代过程称为为新的近似根。这样确定的迭代过程称为拋拋物线法（亦称密勒法）。物线法（亦称密勒法）。 拋拋物线插值多项式为：物线插值多项式为： 有两个零点：有两个零点： 其中，其中， 其几何意义就是：用抛物线其几何意义就是：用抛物线 与与 轴的交点轴的交点 作为所作为所求根求根 的近似值。如右图。为了由的近似值。如右图。为了由 定出一个值定出一个值 ，需讨论，需讨论根式前正负符号的取舍问题在根式前正负符号的取舍问题在 三个近似根中，自三个近似根中，自然假定以然假定以 更接近所求的根更接近所求的根 ，这时为保证精度，选取这时为保证精度，选取 中较中较近近 的一个值作为新的近似根的一个值作为新的近似根 ，为此，只要令根式前的符号与为此，只要令根式前的符号与 的的符号相同。符号相同。 例例 用抛物线法求解方程用抛物线法求解方程 解解 取三个初值取三个初值 ， 计算计算 ， ， ， ， ， ， ， 从而：从而： 。 定理定理 若若 在根在根 的邻域的邻域 内内 有三节连续偏导数，有三节连续偏导数，且对且对 ，有，有 。又初值。又初值 ，那么当领域，那么当领域 充分小时，抛物线法充分小时，抛物线法(4.2.8)(4.2.8)将按阶将按阶 收敛于根收敛于根 。 可见抛物线法比弦截法的收敛性更接近于可见抛物线法比弦截法的收敛性更接近于NewtonNewton法。定理的证明法。定理的证明略。略。4.2.13 4.2.13 多项式求值的秦九韶算法多项式求值的秦九韶算法 多项式的重要特点之一是求值方便，设多项式的重要特点之一是求值方便，设 ，系数，系数 均为实数。用均为实数。用 除除 ，记其商为，记其商为 ，则其余项显然为，则其余项显然为 即即 令令 代入公式代入公式 后后与与 比较同项式系数，可得：比较同项式系数，可得： 从而有：从而有： 式提供了计算函数值式提供了计算函数值 的有效算法称为秦九韶法。这的有效算法称为秦九韶法。这种算法的优点是计算量小，结构紧凑，易编制计算机程序。种算法的优点是计算量小，结构紧凑，易编制计算机程序。 再看再看 的的 阶阶TaylorTaylor展开式：注意（对展开式：注意（对 次多项式）次多项式）更高阶导数为更高阶导数为0 0。 将它表示为将它表示为 可见导数值可见导数值 又可看作又可看作 用因子用因子 相除得出的余数，相除得出的余数，从而有：从而有： 式中式中 是是 次多项式。次多项式。令，令， 那么用秦九韶算法又可求出那么用秦九韶算法又可求出值值 。对应于此处的计算公式为：。对应于此处的计算公式为： 其中已由公式其中已由公式 计算出。计算出。 4.2.14 4.2.14 代数方程的代数方程的NewtonNewton法法 对对 考察考察NewtonNewton公式：公式： 根据公式根据公式 ， 即可求即可求 ， ，从而由公式，从而由公式 即可得即可得 。4.2.15 4.2.15 劈因子法劈因子法 关于关于NewtonNewton法对重根的处理。法对重根的处理。 定理定理4.2.8 4.2.8 设设 ，在点，在点 附近附近 有连续的有连续的 阶导数，则：阶导数，则： （证明略）。（证明略）。 若若 ，即，即 为为 的二重根，则可将的二重根，则可将NewtonNewton法中迭代函数改写法中迭代函数改写为：为： 则：则： 因此仍然能保证在因此仍然能保证在 领域内领域内 ，使算法具有二阶收敛性。在实，使算法具有二阶收敛性。在实际应用中对际应用中对 重根，迭代函数可改写成重根，迭代函数可改写成 ，但由于，但由于一般不能确定常数一般不能确定常数 ，则可考虑函数：，则可考虑函数： ，如果，如果 是正整数，是正整数， 。 则则 ，显然，显然 是是 的单重零点，故可的单重零点，故可得切线法（即得切线法（即NewtonNewton法）用于法）用于 ，得到二阶收敛的迭代函数：，得到二阶收敛的迭代函数： 或或 因此作为迭代函数即可找到根因此作为迭代函数即可找到根 ，收敛阶为，收敛阶为2 2阶。阶。 例例4.2.10 4.2.10 对于方程对于方程 是二重根用下面三是二重根用下面三种方法求根：种方法求根：v NewtonNewton法：法： v 即即v 有上面有上面 所确定的修改方法化简为：所确定的修改方法化简为： 三种方三种方法均取初值法均取初值 。计算结果为：。计算结果为：表表4.2.5 4.2.5 部分计算结果表部分计算结果表经经3 3次迭代，方法次迭代，方法2 2、3 3均达到精度。它们都是二阶收敛的方法。而方均达到精度。它们都是二阶收敛的方法。而方法法1 1是一阶的，要进行是一阶的，要进行3030次迭代才能达到同样的精度。次迭代才能达到同样的精度。 方法1方法2方法31.51.51.51.458333333 1.4166666671.4117647061.4366o7143 1.4142156861.4142114381.425497619 1.4142135621.4142135624.3 4.3 养老保险模型的求解养老保险模型的求解对中建立的养老保险模型，以对中建立的养老保险模型，以2525岁起保为例，假设男性平均寿命为岁起保为例，假设男性平均寿命为7575则则 ，初始值为，初始值为 ，我们可以得到：，我们可以得到： 在上面两式中，分别取和并利用可以求出：在上面两式中，分别取和并利用可以求出： 其中其中 利用利用MATLABMATLAB编程编写牛顿迭代法程序，令初值为编程编写牛顿迭代法程序，令初值为 ，迭代最大次，迭代最大次 数为数为1000010000，求出方程的根为：，求出方程的根为： 同样方法可以求出：同样方法可以求出：3535岁和岁和4545岁起保所获得的月利率分别为岁起保所获得的月利率分别为习习 题题 4 41 1、用迭代法求解如下方程在（、用迭代法求解如下方程在（1 1，2 2）内的实根）内的实根2 2、用、用NewtonNewton法求法求 的近似解的近似解3 3、用弦截法求方程、用弦截法求方程 在区间（在区间（1 1，2 2）内的）内的实根。实根。4 4、利用二分法求方程、利用二分法求方程 在在 内的根内的根中南大学数学科学与计算技术学院中南大学数学科学与计算技术学院