第四章 养老保险问题 - 非线性方程求根的数值解法
更新时间:2024-04-02 20:06:01 阅读量: 综合文库 文档下载
第四章 养老保险问题
——非线性方程求根的数值解法
4.1 养老保险问题
4.1.1 问题的引入
养老保险是保险中的一种重要险种,保险公司将提供不同的保险方案以供选择,分析保险品种的实际投资价值。也就是说,如果已知所交保费和保险收入,则按年或按月计算实际的利率是多少?或者说,保险公司需要用你的保费至少获得多少利润才能保证兑现你的保险收益?
4.1.2 模型分析
假设每月交费200元至60岁开始领取养老金。某男子25岁起投保,届时养老金每月2282元;如果其35岁起保,届时月养老金1056元。试求出保险公司为了兑现保险责任,每月至少应有多少投资收益率?这也就是投保人的实际收益率。
4.1.3 模型假设
这应当是一个过程分析模型问题。过程的结果在条件一定时是确定的。整个过程可以按月进行划分,因为交费是按月进行的。假设投保人到第k月为止,所交保费及收益的累计总额为Fk,每月收益率为r,用p、q表示60岁之前每月所交的费用和60岁之后每月所领取的费用,N表示停交保险费的月份,M表示停领养老金的月份。
4.1.4 模型建立
在整个过程中,离散变量Fk的变化规律满足: ??Fk??Fk(1?r)?p,k?0,1,...,N?1?Fk?1?Fk(1?r)?q,k?N,...,M?1 (4.1.1)
在公式(4.1.1)中Fk实际上表示从保险人开始交纳保险费以后,保险人账户上的资金数值。我们关心的是,在第M月时,FM能否为非负数?如果为正,则表明保险公司获得收益;若为负,则表明保险公司出现亏损;当为零时,表明保险公司最后一无所有,所有的收益全归保险人,把它作为保险人的实际收益。从这个分析结果来看,引入变量Fk,很好地刻画了整个过程中资金的变化关系。特别是引入收益率r ,虽然它不是我们所求的保险人的收益率,但从问题的系统环境中来看,必然要考虑引入另一对象——保险公司的经营效益,以此作为整个过程中各量变化的表现基础。
86
4.1.5 模型求解
在(4.1.1)中两式,取初始值F0?0,我们可以得到:
Fk?F0(1?r)?Fk?FN(`1?r)k?Nkpr[(1?r)?1],k?0,1,2,..,Nqrk
[(1?r)k?N??1],k?N?1,...,M再分别取,k?N,和k?M,并利用FM?0可以求出:
(1?r)M?(1?qp)(1?r)M?N?qp?0
它是一个非线性方程。因此求解该模型,就转换为一个求非线性方程的问题。
众所周知,代数方程求根问题是一个古老的数学问题。早在16世纪就找到了三次、四次方程的求根公式。但直到19世纪才证明了n?5次的一般代数方程是不能用代数公式求解的,因此需要研究用数值方法求得满足一定精度的代数方程的近似解。
在工程和科学技术中许多问题常归结为求解非线性方程的问题。正因为非线性方程求根问题是如此重要的基础,因此它的求根问题很早就引起了人们的兴趣,并得到了许多成熟的求解方法。下面我们介绍非线性方程的基本概念与重要解法。
4.2 非线性方程求根的数值方法
4.2.1 根的搜索相关定义
定义4.2.1 设有一个非线性方程f?x??0,其中f(x)为实变量x的非线性函数。 (1)如果有x?使f(x?)?0,则称x?为方程的根,或为f?x?的零点。 (2)当f?x?为多项式,即
f(x)?anx?an?1xnn?1???ax?a0,?an?0?
则称f(x)?0为n次代数方程。当f(x)包含指数函数或者三角函数等特殊函数时,则称f(x)?0为特殊方程。
(3)如果f(x)?(x?x?)mg(x),其中g(x?)?0。m为正整数,则称x?为f(x)?0的m重根。当m?1时,称x?为f(x)?0的单根。
87
定理4.2.1 设f(x)?0为具有复系数的n次代数方程,则f(x)?0在复数域上恰有 。如果f(x)?0为实系数方程,则复数根成对出现,即n个根(r重根计算r个)
当:??i????0?为f(x)?0的复根,则??i?亦是f(x)?0的复根。
定理4.2.2设f(x)在?a,b?连续,且f(a)?f(b)?0,则存在x???a,b?,使得
f(x)?0,即f??x?在(a,b)内存在零点。
4.2.2 逐步搜索法
对于方程f?x??0,x??a,b?,为明确起见,设f?a??0,f(b)?0,从区
间左端点x0?a出发按某个预定步长h(如取h?b?aN,N为正整数),一步一步
地向右跨,每跨一步进行一次根的搜索。即检查节点xk?a?kh上的函数值f?xk?的符号,若f?xk??0,则xk即为方程解;若f?xk??0,则方程根在区间[xk?1,xk]中,其宽度为h。
例4.2.1 考察方程f?x??x3?x?1?0
?由于f?0???1?0,f?2??5x?00 则f?x?在?0,2?内至少有一个根,设从
出发,以h?0.5为步长向右进行根的搜索。列表记录各节点函数值的符号,
如表4.2.1所示。可见方程在?1.0,1.5?内必有一根。
表4.2.1f?x?的符号
x f(x)的符号 0 - 0.5 - 1.0 - 1.5 + 易见,此方法应用关键在步长h的选择上。很明显,只要步长h取得足够小,利用此法就可以得到任意精度的根,但h缩小,搜索步数增多,从而使计算量增大,用此方法对高精度要求不简便。
4.2.3 二分法
对非线性方程:
f?x??0 ?4.2.?1
其中f?x?在?a,b?上连续且设f?a??f?b??0,不妨设f?x?在?a,b?内仅有一个零
88
点。
求方程(4.2.1)的实根x?的二分法的过程,就是将?a,b?逐步分半,检查函数值符号的变化,以便确定包含根的充分小区间。
二分法的步骤如下:记a1?a,b1?b 第1步:
分半计算?k?1?,即将[a1,b1]分半。计算中点x1?f(a1)?f(x1)?0?a1?b12及f?x1?。若
?[a2,b2],则根必在[a1,x1]内,否则必在[x1,b1]?[a2,b2]内(若
则x?x1),于是得到长度一半的区间[a2,b2]含根,即f(a2)f(b2)?0f(x1)?0,且b2?a2?12(b1?a1)。
,
第k步:(*分半计算)重复上述过程。
设已完成第1步?第k?1步,分半计算得到含根区间
[a1b,1?]a[b,??]?akbk[2212k?1?fbk(?),即x?[ak,bk],,且]满足f(ak),
bk?ak?(b?a),则第k步的分半计算:xk?x?xk??ak?bk2,且有:
?4.2?. 2bk?ak2?12k?b?a?
确定新的含根区间[ak?1,bk?1],即如果f(ak)f(xk)?0,则根必在
[ak,xk]?[ak?1,bk?1]内,否则必在[xk,bk]?[ak?1,bk?1]内,且有:bk?1?ak?1?12k(b?a)。
总之,由上述二分法得到序列?xk?,由(4.2.2)有:limxk?x?。
k??可用二分法求方程f(x)?0的实根x?的近似值到任意指定的精度,这是因为:
设?>0为给定精度要求,则由x??xk?足:
k?b?a2k??,可得分半计算次数k应满
?ln?b?a??ln??ln2 ?4.2?. 3 二分法的优点是方法简单,且只要求f(x)连续即可。可用二分法求出f(x)?0在?a,b?内的全部实根,但二分法不能求复根及偶数重根,且收敛较慢,函数值计算次数较多。
89
2?内一个实根,且要求精确到小数点后例4.2.2 用二分法求f(x)?x6?x?1在?1,第三位。(即x*?xk?12?10?3)
解 :由??0.5?10?3代入式(4.2.3),其中(a?1,b?2),可确定所需分半次数为
k?11,计算结果部分如表
4.2.2所示(显然f(1)??1?0,f(2)?0)。
bk表4.2.2 部分计算结果
ak k 8 9 10 11 1.132813 1.132813 1.132813 1.133789 xk f(xk) 1.140625 1.136719 1.134766 1.134766 1.136719 1.134766 1.133789 1.134277 0.020619 0.4268415 ?0.00959799?0.0045915 4.2.4 迭代法
迭代法是一种逐次逼近法。它是求解代数方程、超越方程及方程组的一种
基本方法,但存在是否收敛及收敛快慢的问题。
用迭代法求解f(x)?0的近似根,首先需将此方程化为等价的方程:
x?g(x) (4.2.4)
然而将f(x)?0化为等价方程 (4.2.4)的方法是很多的。 例4.2.3 对方程f(x)?x?sinx?0.5?0
可用不同的方法将其化为等价方程:
(1)x?sinx?0.5?g1(x) (2)x?sin?1?x?0.5??g2(x) 定义4.2.2 (迭代法)设方程为x?g(x)
(1)取方程根的一个初始近似x0,且按下述逐次代入法,构造一个近似解序列:
x1?g?x0?,x2?g?x1?,?xk?1?g?xk? (4.2. 5
这种方法称为迭代法(或称为单点迭代法),g(x)称为迭代函数。
*(2)若由迭代法产生序列?xk?有极限存在,即limxk?x,称?xk?为收敛或迭代
k??*过程 (4.2.5收)敛,否则称迭代法不收敛。若g(x)连续,且limxk?x,则
k??x?limxk?1?limg(x?)gkk??k????k??limx?k?gx(,即)x??为方程 (4.2.4)的解(称x?为函
90
数g?x?的不动点),显然在由方程f(x)?0转化为等价方程x?g(x)时,选择不同的迭代函数g(x),就会产生不同的序列?xk?(即使初值x0选择一样)且这些序列的收敛情况也不一定相同。
例4.2.4 对例4.2.1中方程考查用迭代法求根
?a??b?xk?1?sinxk?0.5,k?0,1,2,?xk?1?sin?1?xk?0.5?,k?0,1,2,?
由计算可以看出,我们选取的两个函数g1?x?,g2?x?,分别构造序列?xk?收敛情形不一样(初值都取为1),在(a)中?xk?收敛且x??1.497300,在(b)中计算出sin?1?x4?0.5??sin?1??1.987761?无定义。部分计算结果如下表4.2.3:
表4.2.3 部分计算结果
k (a)xk (b) xk ?a?f(xk) 0 1 2 3 4 5 6 7 1.0 1.341471 1.473820 1.049530 1.497152 1.497289 1.497300 1.497300 1.0 0.523599 0.023601 -0.496555 -1.487761 ?3.6?10?7 因此对用迭代法求方程f(x)?0的近似根,需要研究下述问题: (1) 如何选取迭代函数g(x)使迭代过程xk?1?g?xk?收敛。 (2) 若?xk?收敛较慢时,怎样加速?xk?收敛。
迭代法的几何意义:求方程x?g(x)根的问题,是求曲线y?g(x)与直线
y?x交点的横坐标x?,当迭代函数g(x)的导数函数g'?x?在根x?处满足下述几
种条件时,从几何上来看迭代过程xk?1?g?xk?的收敛情况如图4.2.1。 从曲线y?g(x)上一点p0?x0,g?x0??出发,沿着平行于x轴方向前进交y?x于一点Q0再从Q0点沿平行于y轴方向前进交y?g(x)于p1点,显然p1的横坐标就是x1?g?x0?,继续这过程就得到序列{xk},且从几何上观察知道在(1),(2)
91
情况下{xk}收敛于x*,在(3),(4)情况{xk}不收敛于x*。
图4.2.1 迭代法的几何意义图
由迭代法的几何定义知,为了保证迭代过程收敛,应该要求迭代函数的导数
满足条件g'(x)?1。当x?[a,b]时,原方程在[a,b]中可能有几个根或迭代法不收敛,为此有关于迭代收敛性的定理4.2.3。 定理4.2.3 设有方程x?g(x), (1) 设g(x)于[a,b]一阶导数存在, (2) 当x?[a,b]时,有g(x)?[a,b],
(3) g'(x)满足条件:g'(x)?L?1,?x?[a,b],则有:
1 x?g(x)在[a,b]上有唯一解x,
?*?收敛即2 对任意选取初始值x0?[a,b],迭代过程xk?1?g(xk),k?0,1,...lim xk?x*,
11?Lxk?1?xk3? x*?xk?,
Lk4 误差估计式: x?xk??*1?Lx1?x0,(k?1,2,...)。
92
证明:( 只证2? ,3?,4?)
?2 由定理条件(2),当取x0?[a,b]时,
则有xk?[a,b],?k(ek?x?xkx?**1,,2记误差
,由中值定理有:
*k?1x?(g)x?(kg)x?'(g)c(,?xk*)x其中c在x*与xk之间,即c?[a,b],又由
条件(3)有:x*?xk?1?g('c)x?*xk?Lx?x*kx?xk?Lx?xk?1?Lx?xk?**2*,由此递推可得:
?...?Lx?x2k**0?L?1limx?x,由故。 k03? 由迭代公式xk?1?g(xk)有:
'xk?1?xk?g(xk)?g(xk?1)?g(c)(xk?xk?1)?Lxk?xk?1,其中c在xk?1与xk之间,
*于是:
xk?1?xk?x?xk?(x?xk?1)?x?xk?x?xk?1 ?x?xk-Lx?xk?(1-L)x?xk ******
即x*?xk?11?Lxk?1?xk?L1?Lxk?xk?1。
?4 由上面xk?1?xk?Lxk?xk?1反复利用代入上式中有:
x?xk?*11?LL2xk?1?xk?L1?Lxk?xk?1Lk
x1?x0 ?1?Lxk?1?xk?2?...?1?L由定理结果3?可知,当计算得到的相邻两次迭代满足条件xk?1?xk??时,则误差x*?xk?11?L?。
因此在计算机上可利用xk?1?xk??来控制算法终止,但要注意L?1时,即使xk?1?xk很小,但误差x*?xk可能很大。
另外,当已知x0,x1及L(L?1)及给定精度要求?时,利用定理结果4?可确定
93
使误差达到给定精度要求时所需要迭代次数k,事实上,由x*?xk解得:
k?(ln??lnx1?x01?L?Lk1?Lx1?x0??
)/lnL (4.2 .6定理条件g'(x)?L?1,x?[a,b],在一般情况下,可能对大范围的含根区间不满足,而在根的附近是成立的,为此有如下迭代过程的局部收敛性结果。 定理4.2.4 (迭代法的局部收敛性)设给定方程x?g(x), (1)设x*为方程的解,
(2)设g(x)在x*的邻域内连续可微,且有g'(x*)?1,则对任意初值x0(在x*的邻域内),迭代过程xk?1?g(x),k?0,1,...收敛于x*。 例4.2.5 由迭代法解方程f(x)?x?ln(x?2)?0
解 (1)显然有f(0)f(2)?0,f?(1.9f)?(1)?即知方程于0[0,2]及[?1.9,?1]内有根
?记为x1?,x2。
(2)考察取初值x0?[0,2]迭代过程xk?1?ln(xk?2)的收敛性,其中迭代函数为
g1(x)?ln(x?2),显然g1(0)?ln(2)?0.693?0,g1(2)?ln(4)?1.368?2,及g1(x)1x?)为增函数,则当0?x?2时,0?g1(g(x)?''2又由g(x)?,
x?2则有
1x?2?g1(0)?'12?1(?x?[0,2])。于是由定理
4.2.4可知,当初值x0??0,2?时,迭代过程xk?1?ln(xk?2)收敛,如果要求x1?的近似根准确到小数点后第6位
94
(即要求x1??xk?12?10?6)由计算结果可知x15?x14?10?7。且L??712,则
*,x1?x14?1.1461931f(x14)?0.8?10。
表4.2.4 部分计算结果表
k0 1 2 ? xk?1?ln(xk?2) 0.0 0.69314718 0.99071046 ? 14 15 1.1461931 1.1461932 (3)为了求[?1.,?9g1(x)?'内1方程的根。由迭代方程xk?1?lnx(k?*2,)显然
1x?2?g(x2)?1*'xk(?,所以迭代过程xk?1?ln*2)初值(
x0?[?1.9?,x0x2。 1)不能保证收敛于?x]2,xx?(4)若将方程转化为等价方程e?x?2或x?e?2?g2(x)则g'2(x)?ex,且
g2(x)?g2(?1)?0.386?1''(x?[?1.9,?1]时),g2(x)?[?1.9,?1]所以当选取
xkx0?[?1.9?,时1]迭代过程xk?1?e*?2收敛。如取x0??1,则迭代12次有
?8x2?x12??1.8414056,且60f(x12)?0.2?10。
由此例可见,对于方程 f(x)?0,迭代函数g(x)取不同形式,相应的迭代法产生的{xk}的收敛情况也不一样。因此,我们应该选择迭代函数的迭代过程
xk?1?g(xk)收敛,且收敛较快。
关于迭代公式的加工:
对于收敛的迭代过程,只要迭代足够多次,总可以使结果达到任意的精度。但有时迭代收敛缓慢,从而使计算量变得很大,因此迭代过程的加速是一个很重要的课题。
设x0为根x*的某个预测值,用迭代公式校正一次得:
x1?g(x0)
由中值定理:x1?x*?g'(?)(x0?x*),?介于x*,x0之间,若g'(x)改变不大。近
95
似地取某常数L,则由x1?x*?L(x0?x*)?x*?右端求得的x2?11?Lx1?L1?Lx0?x1?L1?L11?Lx1?L1?Lx0可以期望按上式
(x1?x0)是比x1更好的近似值。
若将每得到一次改进值算作一步,并用x和xk分别表示第k步的校正值和改进值,则加速迭代计算方案如下: 校正: xk?1?g(xk) 改进: xk?1?xk?1?L1?L(xk?1? xk)
由于使用参数L,这在实际应用中不方便,下面进行改进计算。
设x*的某近似值x0,将校正值x1?g(x0)再校正一次得:x2?g(x1),由
x2?x?L(x1?x)**与(x1?x)?L(x0?x)得:
**x1?xx2?x**?x0?xx1?x**由此得:
x?*x0x2?x21x0?2x1?x2?x2?(x2?x1)x0?2x1?x22。这样将上式右端作为改进公式就不再含有导
数信息了。但需要用到两次迭代的结果进行加工。如果仍将得到一次改进值作为一步,则计算过程如下:
??校正:?k?1?g(xk) x???k?1) xk?1?g(x?再校正:?2?k?1)(x?xk?1?改进: xk?1?xk?1???k?1?xkxk?1?2x?上述处理过程称为Aitken(埃特金)方法。
4.2.5 Newton公式
对于方程f(x)?0,应用迭代法时先要改写成x?g(x),即需要针对f(x)构
造不同的合适的迭代函数g(x),显然可以取迭代函数为g(x)?x?f(x),相应迭代公式为xk?1?xk?f(xk)。
一般地,这种迭代公式不一定收敛,或者速度很慢。对此公式应用前面的加
速技术。具体格式为:
?xk?1?xk?f(xk)? ?L(xk?1?xk)?xk?1?xk?1??1?L 96
记M?L?1,则上二式可合并写为:xk?1?xk?公式,其迭代函数为:g(x)?x?f(x)Mf(xk)M。此公式称为简单的Newton
。又由于L为g'(x)的近似值,而
''g(x)?x?f(x),因此M?L?1实际上是f(x)的近似值,故用f(x)代替上式中
的M即得到下面的迭代函数:g(x)?x?f(xk)f(xk)'f(x)f(x)'。相应的迭代公式为:
xk?1?xk?,即为Newton公式。
4.2.6 Newton法的几何意义
Newton法的基本思想就是将非线性方程f(x)?0逐步线性化求解,设有近似的根xkf(x)?0Taylor,将f(x)在xk处
展开得:
'f(x)?f(xk)?f(xk)(x?xk)
从而f(x)?0近似地表为:
f(xk)?f(xk)(x?xk)?0。方程f(x)?0'的根x*即为曲线y?f(x)与x轴交点
的横坐标。设xk为x*的一个近似,过曲线y?f(x)上横坐标为xk的点pk作曲线的切线,该切线与x轴焦点的横坐标即为x*的新近似值xk?1,它与x轴交点的横坐标为:xk?1?xk?f(xk)/f'(xk),因此Newton法,亦称切线法。
4.2.7 Newton法的局部收敛性
定义4.2.3 设迭代过程xk?1?g(xk)收敛于方程x?g(x)的根x*,如果迭代误差
ek?xk?x*,当k??时有:
ek?1ekp?c (c?0,为常数)则称该迭代过程为p阶收
敛的。
定理4.2.5 对迭代过程xk?1?g(xk),如果g(p)(x)在x*附近连续,且:
g(x
'*)?gx(?)''*?...(p-1)gx(?且)g0(x)?097
*(p)*,则该迭代过程在x附近是p阶收敛
的。
证明: 由于g'(x*)?0?1,则由前面关于迭代法的局部收敛性定理知:此迭代过程xk?1?g(xk)具有局部收敛性,即xk?0。将g(xk)在x*处Taylor展开,并注意到g'(x*)?...? g(p-1)(x*)?0有:
g(xk)?g(x)?*g(p)(?k)p!(xk?x),?k?[ xk, x]
**而,
xk?1?g(xk), x?g( x)
**从而上式化为:
xk?1?x?*g(p)(?k)p!(xk?x)
*p即:
ek?1ekp?xk?1?x**p(xk?x)?g(p)(?k)p!?g(p)(x)*p!
故知迭代过程具有p阶收敛性。
定理4.2.5表明迭代过程的收敛速度依赖于迭代函数g(x)的选取,如果
x?[a,b]时g(x)?0,则迭代过程只可能是线性收敛的。
' 对于Newton法,由迭代函数:
g(x)?x-f(x)f(x)'
则
g(x)?1?'[f(x)]?f(x)f(x)[f(x)]'2'2''?f(x)f(x)[f(x)]'2'',
若x*为f(x)的一个单根,即f(x*)?0,f'?x*??0,则由上式知g'(x*)?0。由上面定理可知Newton法在根x*的邻域内是平方收敛的(二阶收敛的)。
特别地考察Newton公式: 设f(x)二次连续可微,则
'f(x)?f(xk)?f(xk)(x?xk)?
98
f(?)2!''(x?xk),
2**?在?x,xk?之间,特别地取x?x,注意f(x)?0,则
0?f(x)?f(xk)?f(xk)(x?xk)?*'*f(?)2!?'(x?xk)
*2设f(xk)?0两边同除以f(xk),得:x?xk?''*f(xk)f(xk)'f(?)2f(xk)'''(x?xk)*2(注:
xk?f(xk)f(xk)',利用?xk?1)
Newton公式,即有:
x?xk?1(x?xk)*2*??f(?)2f(xk)*'''?mk
f(?)2f(xk)'''当k??,则???''2f(x)k2(f)xf(?)''''*f(x)*,或x?xk?1?ek?1??(x?xk)?mkek*22,
可见ek?1(误差)与xk的误差ek的平方成比例。当初始误差e0?x*?x0充分小时,以后迭代的误差将减少得非常快。反之e0?1,则放大。Newton法每计算一步,需要计算一次函数值f(xk)和一次导数值f'(xk)。 例4.2.6 用Newton法求解f(x)?e?x4(2?x)?1?0。
?x4解 :显然f(0)f(2)?0。则在[0,2]内方程有一个根,求导f'(x)?e?xk(x?6)/4,
则Newton公式为:xk?1?xk?f(xk)f(xk)'?xk?ee4?xk4(2?xk)?1(xk?6)/4。取x0?1.0,迭代6次
得近似根为x*?0.783596,f(x*)??3.8?10?6。这表明,当初值x0取值靠近x*时,Newton法收敛且收敛较快,否则Newton法可能不收敛。
下面考虑Newton法的误差估计,由中值定理有:
f(xk)?f(xk)?f(x)?f(?k)(xk?x),
*'*当xk充分接近x时,有x?xk??**f(xk)f(?k)'??f(xk)f(xk)'Newton?xk?1?xk。因此,用Newton
法求方程单根x*的近似根xk的误差ek?x*?xk可用xk?1?xk来估计。
99
4.2.8 Newton法应用举例
(1) 对给定的正数C,应用Newton法解二次方程x2?C?0可导出求开方值C的计算格式:
xk?1?12(xk?Cxk)
(4.2. 7可证明公式(4.2.7)对任意函数初值x0?0都是收敛的。这是因为:
??xk?1????x?k?1??C?C?12xk12xk(xk?(xk?C)C)2
2两式相除得:
xk?1?xk?1?CC?(xk?xk?CC)
2利用此式递推可得:
xk?1?xk?1?CCCCk?(x0?x0?CC)2k?q2k?xk?22kC?C2q2k1?q2k
(由xk?1?xk?1?CC?(x0?x0?2)2k可知:xk?2q2k1?q1?qkC,则:
xk?C?(xk?C)q?C1?q2k)。而?x0?0,q?x0?x0?CC?1。故由公式知
xk?) C(k??)即迭代法恒收敛。
例4.2.7 求10的近似值,要求xk?1?xk?10?6终止迭代。 解 xk?1?12(xk?10xk?7)取x0?1.0经6次迭代后:x5?3.16227767,x6?3.16227766,
x6?x5?0.1?10故10?3.16227766。
1x?C?0(2) 对给定正数C,应用Newton法求解除法的计算程序:xk?1?xk(2?Cxk)。
,由此式可导出求
1C而不用
这个算法对于没有设置除法操作的电子计算机是有用的。可以证明,此算法
100
初值满足0?x0?2C时是收敛的,这是因为:
xk?1?1C?xk(2?Cxk)?1C??C(xk?1C)2,
即:1?Cxk?1?(1?Cxk)2,令rk?1?Cxk,由递推公式rk?1?rk2反复递推,得:
2rk?r0。
k当r0?1?Cx0?1,即0?x0?2C时,有rk?0即xk?1C,从而迭代法收敛。
4.2.9 Newton下山法
Newton法收敛性依赖于初值x0的选取,如果x0偏离x*较远,则Newton法可能发散。例如,对方程x3?x?1?0。求在x?1.5附近的一个根x*。若取初值
x0?1.5,则由
.34x27?83Newton
,x3?1法:
xk?1?xk?xk?xk?13x?12k3,计算得
x1?1.,3253次即得有20,仅迭代1.324726位有效数字的近似值
x3。但若取初值x0?0.6则由同一Newton公式计算得x1?17.9,这反而比x0?0.6更远离所求根x*?1.32472,因此发散。为防止发散,对迭代过程加一下降要求:
f(xk?1)?f(xk),满足这项要求的算法称为下山法。
将Newton法与下山法结合,即在下山法保证函数下降条件下,用Newton法加速收敛。为此,可将Newton计算结果xk?1?xk?f(xk)f(xk)'与每一步近似值xk作
加权平均:xk?1??xk?1?(1??)xk,其中?(0???1)成为下山因子。选择下山因子?以保证下降性。
?的选择方法是:由??1反复减半的试探法,若能找到?使下降性成立,则下山成功,否则下山失败,改变初值x0重新开始。
4.2.10 弦截法与拋物法
Newton法xk?1?xk?f(xk)f(xk)'每迭代一次计算函数值f(xk)、导数值f'(xk)各一
次,当函数f本身比较复杂时,求导数值更加困难。
101
下面方法多利用以前各次计算的函数值f(xk),f(xk?1),?来回避导数值
f(xk)的计算,导出这种求根方法的基本原理是插值法。
'设xk,xk?1,?,xk?r是f(x)?0的一组近似值,利用对应的函数值
f(x),f(kx?),k?1构造插值多项式适当选取pr(x)?0的一个根作f,?kx(,)pr(x),r为f(x)?0的新的近似根xk?1。这样就确定了一个迭代过程,记迭代函数为g,则xk?1?g(xk,xk?1,?,xk?r),下面具体考察r?1(弦截法),r?2(拋物法)两种情形。
4.2.11 弦截法
设xk,xk?1为f(x)?0的近似根,过点(xk,f(xk)),(xk?1,f(xk?1))构造一次插值多项式p1(x),并用p1(x)?0的根作为f(x)?0的新的近似根xk?1。由于
p1(x)?f(xk)?f(xk)?f(xk?1)xk?xk?1(x?xk)
(4.2. 8
则由p1(x)?0可得:
xk?1?xk?f(xk)f(xk)?f(xk?1)(xk?xk?1) (4.2. 9另外,公式(4.2.9)也可以用导数f'(x)的差商公式中的f'(x),同样得公式 (4.2.9)。
f(xk)?f(xk?1)xk?xk?1近似取代Newton
弦截法的几何意义:曲线y?f(x)上横坐标为xk,xk?1的点分别记为pk,pk?1,则弦线pkpk?1的斜率等于差商
f(xk)?f(xk?1)xk?xk?1f(xk)?f(xk?1)xk?xk?1。pkpk?1的方程为:
f(x)?(x?xk)?0,则按 (4.2.9)求得的近似根xk?1实际上是弦线
pkpk?1与x轴交点的横坐标。因此这种算法称为弦截法,又称割线法。
弦截法与切线法(Newton法)都是线性化方程,但两者有本质区别。Newton切线法在计算xk?1时只用到前一步的xk及f(xk),但要计算f'(xk),而弦截法在
102
计算xk?1时要用前面两步的结果xk,xk?1,f(xk),f(xk?1),而不需计算导数。这种方法必须有两个启动值x0,x1。
例4.2.8 用割线法求解方程f(x)?x3?3x2?x?9?0在(?2,?1.5)的根。 解 取初值x0??2,x1??1,则迭代5次后有x6??1.525102,f(x6)?0.000000。例子表明弦截法仍具有较快的收敛性。
定理4.2.6 假设f(x)在根x*邻域?:x?x*??内具有二阶连续导数,且对?x??有f'(x)?0。又初值x0,x1??,那么当邻域?充分小时,弦截法(4.2.9)将按阶
P?1?25?1.618收敛到根x*。(证明略)
下面分析弦截法用于求解x?g(x)时,对Atken加速算法的几何解释:
x0为x?g(x)的近似根,x1?g(x0),
在曲线上走了两点
x1),p1(,引弦线x1,x)p0p1与直线
x2?g(x1)p0(x0,y?x交于一点p2',则p2'的横坐标(与
x2?x1x1?x0(x3?x0)?x3?x0x2?x12纵坐标相等)为:x3?x1?x0?2x1?x2此即为Atken加速计
算方法的公式。由图可以看出,所求的根x*是曲线y?g(x)与y?x的交点p*的横坐标,从图形上看,尽管迭代值x2比x0和x1更远偏离了x*,但按上式求得的x3却明显地扭转了这种发散的趋势。
4.2.12 抛物线法
设已知f(x)?0的三个近似根为xk,xk?1,xk?2,以这三点为节点构造二次插值多项式p2(x),并适当选取p2(x)的一个零点xk?1作为新的近似根。这样确定的迭代过程称为拋物线法(亦称密勒法)。
拋物线插值多项式为:
p2?x??f?xk??f?xk,xk?1??x?xk??f?xk,xk?1,xk?2??x?xk??x?xk?1?
103
有两个零点:
xk?1?xk?2f?xk?????4f?xk?f?xk,xk?1,xk?2?2 (4.2.10)
其中,
??f?xk,xk?1??f?xk,xk?1,xk?2??xk?xk?1?
其几何意义就是:用抛物线y?p2(x)与x轴的交点xk?1作为所根x*的近似值。为了由定出一个值xk?1,需讨论根式前正负(4.2.10)符号的取舍问题在xk,xk?1,xk?2三个近似根中,自然假定以xk更接近所求的根x*,这时
为保证精度,选取(4.2.10)中较近xk的一个值作为新的近似根xk?1,为此,只要令根式前的符号与?的符号相同。 例4.2.9 用抛物线法求解方程
f(x)?xe?1?0
x解 取三个初值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,??f[x2,x1]?f[x2,x1,x0](x2,x1)?2.75694,从而:
x3?x2?2f(x2)????4f(x2)f[x2,x1,x0]2?0.56714。
定理4.2.7 若f(x)在根x*的邻域?内?x?x*???有三阶连续偏导数,且对
?x??)0?,,有f'(x又初值x0,x1,x2??,那么当邻域?充分小时,抛物线法(4.2.8)
将按阶p?1.840收敛于根x*。
可见抛物线法比弦截法收敛阶更接近于Newton法,定理的证明略。
4.2.13 多项式求值的秦九韶算法
多项式的重要特点之一是求值方便,设f(x)?a0xn?a1xn?1???an?1x?an,系数ai(0?i?n)均为实数。用x?x0除f(x),记其商为p(x),则其余项显然为f(x0)
104
即
f(x)?f(x0)?(x?x0)p(x) (4.2.1 1令p(x)?b0xn?1?b1xn?2???bn?2x?bn?1代入公式(4.2.11)后与f(x)比较同项式系数,可得:
?a0?b0? 1?i?n?1 ?ai?bi?x0bi?1?a?f(x)?xb00n?1?n从而有:
?b0?a0? 1?i?n?1 ?bi?ai?x0bi?1??f(x0)?an?x0bn?1?bn (4.2.1 2这种算法的优点是(4.2.12)式提供了计算函数值f(x0)的有效算法称为秦九韶法。计算量小,结构紧凑,易编制计算机程序。
再看f(x)的n阶Taylor展开式:注意(对n次多项式)更高阶导数为0。
'f(x)?f(x0)?f(x0)(x?x0)?f(x0)2!''(x?x0)???2f(x0)n!n(x?x0)
n将它表示为:
f(x)?f(x0)?(x?x0)p(x)
则有:
p(x)?f(x0)?'f(x0)2!''(x?x0)???f(x0)n!n(x?x0)n?1?b0xn?1?b1xn?2???bn?2x?bn?1 可见导数值f'(x0)又可看作p(x)用因子x?x0相除得出的余数,从而有:
p(x)?f(x0)?(x?x0)q(x),式中q(x)是n?2次多项式。令q(x)?c0x'n?2?c1xn?3???cn?3x?cn?2
那么用秦九韶算法又可求出值f'(x0)。对应于此处的计算公式为:
?c0?b0? 1?i?n?2 ?ci?bi?x0ci?1?'?f(x0)?cn?1?bn?1?x0cn?2 (4.2.13)
其中bi已由公式(4.2.12)计算出。
105
4.2.14 代数方程的Newton法
对f(x)?a0xn?a1xn?1?a2xn?2???an?1x?an?0,考察Newton公式:
xk?1?xk?f(xk)f(xk)' (4.2. 1'根据公式(4.2.12),从而由公式(4.2.14)即可得xk?1。 (4.2.13)即可求f(xk),f(xk),
4.2.15 劈因子法
关于Newton法对重根的处理。
定理4.2.8 设f(x)?(x??)mh(x),h(x)?0,在点x附近f(x)有连续的m?2阶导数,则:
limx??f(x)f(x)[f(x)]'2''?1?1m
若m?2,即?为f(x)的二重根,则可将Newton法中迭代函数改写为:
g(x)?x?2f(x)f(x)',则:
2[f(x)]?2f(x)f(x)[f(x)]'2'2''g(x)?1?'??1?2f(x)f(x)[f(x)]12'2''
g(x)?lim[?1?2x??'f(x)f(x)[f(x)]'2'']??1?2(1?)?0
因此仍然能保证在?领域内g'(?)?1,使算法具有二阶收敛性。在实际应用中对于m重根,迭代函数可改写成g(x)?x?f(x)f(x)'mf(x)f(x)',但由于一般不能确定常数m,
则可考虑函数?(x)?。如果f(x)?(x??)mh(x),m?2是正整数,h(?)?0,
则?(x)?(x??)h(x)[mh(x)?(x??)h(x)]',显然?是?(x)的单重零点,故可将切线法(即
Newton法)用于?(x),得到二阶收敛的迭代函数:
g(x)?x??(x)?(x)'
106
或
g(x)?x?f(x)f(x)[f(x)]?f(x)f(x)'2''' 5 (4.2.1将此作为迭代函数即可找到根?,收敛阶为2阶。
例4.2.10 对于方程f(x)?x4?4x2?4?0,x*?2是二重根。用下面三种方法求根:
(1) Newton法:xk?1?xk?xk?24xk2;
xk?22xk2(2) ?(x)?x?mf(x)/f(x),m?2即xk?1?xk?';
xk?22xk2(3) 由上面(4.2.15)所确定的修改方法化简为:xk?1?xk?值x0?1.5。计算结果为:
表4.2.5 部分计算结果表
x 方法1 x1 x2 x3 x4 三种方法均取初
方法2 1.5 1.416666667 1.414215686 1.414213562 方法3 1.5 1.411764706 1.414211438 1.414213562 1.5 1.458333333 1.4366o7143 1.425497619 经3次迭代,方法2、3均达到10?9精度。它们都是二阶收敛的方法。而方法1是一阶的,要进行30次迭代才能达到同样的精度。
4.3 养老保险模型的求解
对4.2中建立的养老保险模型,以25岁起保为例,假设男性平均寿命为75岁,则p?200,q?2282;N?420,M?600,初始值为F0?0,我们可以得到:
Fk?F0(1?r)?Fk?FN(`1?r)k?Nkpr[(1?r)?1],k?0,1,2,..,Nqrk
[(1?r)k?N??1],k?N?1,...,M在上面两式中,分别取k?N和k?M并利用FM?0可以求出:
107
(1?r)M?(1?qp)(1?r)M?N?qp?0
在上述介绍的非线性方程求根法中选取牛顿法进行求解,利用迭代公式:
rk?1?rk?f(rk)f(rk)'
其中f(r)?(1?r)600?12.41(1?r)180?11.41,f'(r)?600(1?r)599?12.41?180(1?r)179
利用MATLAB编程编写牛顿迭代法程序,令初值为r0?0,迭代最大次数为10000,求出方程的根为:
同样方法可以求出:35岁和45岁起保所获得的月利率分别为
r?0.00485r?0.00461,r?0.00413
习 题 4
1.用迭代法求解如下方程在(1,2)内的实根
f(x)?x?x?1?0。
32.用Newton法求f(x)?x?cosx?0的近似解。
3.用弦截法求方程f(x)?x3?x?1?0在区间(1,2)内的实根。 4.利用二分法求方程2sin?x?cos?x?0在[0,1]内的根(??0.01)。
108
正在阅读:
第四章 养老保险问题 - 非线性方程求根的数值解法04-02
14天突破4级01-06
合同书格式02-25
单纯形法的灵敏度分析与对偶10-15
江苏省淮安市2014届高三5月信息卷物理试题 Word版含答案01-15
2014兰州事业单位成绩查询丨成绩排名丨面试时间(14)04-14
部编版六年级下学期数学强化训练练习期末模拟试卷 - 图文12-22
安徽华能龙头扶贫企业汇报材料20110605-30
新常态下法学实践教学远程互动平台应用研究12-29
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 求根
- 解法
- 非线性
- 第四章
- 养老保险
- 方程
- 数值
- 问题
- 南 京 铁 道 职 业 技 术 学 院 寒 假 值 班 表
- 物业管理风险防范与紧急事件处理手册
- 首都机场T1-3航站楼航空公司列表
- 毕节市七星关区合管中心基本情况
- 基础会计学模拟题1
- 至爱亲情主题学习
- 《财务与会计》押题试卷(三)
- 数字逻辑电路与系统设计分习题及解答蒋立平主编
- 江苏省调味品企业名录229家
- 数据结构与算法分析 复习试卷B2
- 华南理工大学研究生入学物理化学复习精简笔记
- HP EML 磁带机更换磁带 - 图文
- 职业病危害事故专项应急预案
- 青年突击队授旗仪式活动新闻稿
- 山东人民版品德与社会六年级下册全册教案
- 国际金融学复习大纲含答案
- 第一章 货币与货币制度
- 2015年粉笔模考第十二季试题
- 新员工入职礼
- 世界未解案件之谜查尔斯·林白三世绑架案