第四章 养老保险问题——非线性方程求根的数值解法

第四章非线性方程数值求解基本内容1. 知道方程的分类2. 了解如何作根的搜索3. 不动点迭代的操作:x =(p(x)- > x k+l =(p(x k ), k=0, 1•••4.收敛性定理：有2个不同意义下的收敛定理。

全局收敛：(1)定义域条件：XG [a,b]时，[a y b]；(2) Lipschitz 条件：|(p(x)-(p(y) |< L|x-y |,Vx,ye [a 9b] o (1) (/)E C [a,b] (2) (p(x) < L < 1,XG [a,h]局部收敛：(p(x) = 0(F)=..…=0"7(F) = 0, 0”(F)丰 0 则为m 阶收敛，lim 电~ = Q 迭代加速松弛法Aitken 法和 Steffenson 法牛顿法7. 割线法8. 代数方程求根一.基本题型之一：给定非线性方程组，选择适当的解法求出近似根基本解法有二分法，不动点迭代法，牛顿法(也是不动点迭代的一屮)和割线法等，有 时需要用有关的加速法。

1.用二分法求解方程2'x 4-2cosx=0,使精度|<10-2,并估计最小二分次数。

解：设 /(x) = 2-x + 2cosxo 因为/(l) = 2_1+2cosl>0, /(2) = 2-2+2cos2< 0 , 故在[1,2]中，方程有零点。

又因 / (x) = -2~v In 2- 2sin x,而 /(l) = -2_1 ln2-2sinl<0, f(2) = -T 1 ln2-2sin2<0,由单调性可知，/(兀)在[1,2]屮有唯一零点。

(1) 先估计二分最少次数。

题目要求|无-无_】|<10一2,这与教材中的精度要求(1) (2)b-a是不一样的，故不能直接用教材里给出的估讣迭代次数的公式，需要另行推导，请同学们注 意此类“陷阱因为I 兀一无（V 寫，X 严答g 二 叽；几,所以要根据两种可能情况来确定忑-忑T 的大小：（注：下图中打印的同学未能把无等打在la k _v b k _｛］的中点，所以大 家看得时候要当心一一周国标）情况一I ------------------------------------------------- -------------------------------------------------%\ 林-] bk-Xak 无bk情况二「k>6f 即最小二分次数为6次。

非线性方程求根的数值方法林一明（广西民族大学数计学院04数本1班, 南宁 530006）摘要: 本文讨论非线性方程的数值解，阐述了二分法、三分法、冒泡法、简单迭代法和牛顿迭代法原理。

并对非线性方程的数值例子进行了近似计算，并比较了它们的收敛速度。

关键词: 非线性方程；二分法；迭代法；收敛性Numerical Method of the Root for SolvingNonlinear EquationLin Yiming(College of Mathematics and Computer Science,Guangxi University for Nationalities, Nanning 530006) Abstract: In this paper, we study numerical solution of the nonlinear equation, the procedures of dichotomy, rule of thirds, bubble method, the simple iterate method and the Newton iterate method are expounded, And has carried on the approximate calculation to the nonlinear equation, and compare their convergence rate.Keywords: nonlinear equation；dichotomy；iteration method；convergence0 引言代数方程求根问题是个古老的数学问题，在19世纪，理论上就证明了n≥5次一般代数方程不能用代数公式求解，超越方程和工程及科学技术中的许多问题都难以求得精确解，这些方程都归类为非线性方程。

因此，需要研究用数值方法求得满足一定代数精度的非线性方程的近似解。

第四章 养老保险问题 ——非线性方程求根地数值解法4.1 养老保险问题4.1.1问题地引入养老保险是保险中地一种重要险种,保险公司将提供不同地保险方案以供选择,分析保险品种地实际投资价值.也就是说,如果已知所交保费和保险收入,则按年或按月计算实际地利率是多少？或者说,保险公司需要用你地保费至少获得多少利润才能保证兑现你地保险收益？4.1.2模型分析假设每月交费200元至60岁开始领取养老金.某男子25岁起投保,届时养老金每月2282元；如果其35岁起保,届时月养老金1056元.试求出保险公司为了兑现保险责任,每月至少应有多少投资收益率？这也就是投保人地实际收益率.4.1.3模型假设这应当是一个过程分析模型问题.过程地结果在条件一定时是确定地.整个过程可以按月进行划分,因为交费是按月进行地.假设投保人到第k 月为止,所交保费及收益地累计总额为k F ,每月收益率为r ,用q p 、表示60岁之前每月所交地费用和60岁之后每月所领取地费用,N 表示停交保险费地月份,M 表示停领养老金地月份.4.1.4模型建立在整个过程中,离散变量k F 地变化规律满足：11(1),0,1,...,1(1),,...,1k k k k F F r p k N F F r q k N M ++=++=-⎧⎨=+-=-⎩(4.1.1> 在公式<4.1.1）中k F 实际上表示从保险人开始交纳保险费以后,保险人账户上地资金数值.我们关心地是,在第M 月时,M F 能否为非负数？如果为正,则表明保险公司获得收益；若为负,则表明保险公司出现亏损；当为零时,表明保险公司最后一无所有,所有地收益全归保险人,把它作为保险人地实际收益.从这个分析结果来看,引入变量k F ,很好地刻画了整个过程中资金地变化关系.特别是引入收益率r ,虽然它不是我们所求地保险人地收益率,但从问题地系统环境中来看,必然要考虑引入另一对象——保险公司地经营效益,以此作为整个过程中各量变化地表现基础.4.1.5模型求解在(4.1.1>中两式,取初始值00=F ,我们可以得到：MN k r r qr F F N k r r pr F F N k N k N k k k k ,...,1],1)1[()1(`,..,2,1,0],1)1[()1(0+=-+-+==-+++=-- 再分别取,,N k =和M k =,并利用0=M F 可以求出：0)1)(1()1(=+++-+-pqr p q r N M M 它是一个非线性方程.因此求解该模型,就转换为一个求非线性方程地问题.众所周知,代数方程求根问题是一个古老地数学问题.早在16世纪就找到了三次、四次方程地求根公式.但直到19世纪才证明了5n ≥次地一般代数方程是不能用代数公式求解地,因此需要研究用数值方法求得满足一定精度地代数方程地近似解.在项目和科学技术中许多问题常归结为求解非线性方程地问题.正因为非线性方程求根问题是如此重要地基础,因此它地求根问题很早就引起了人们地兴趣,并得到了许多成熟地求解方法.下面我们介绍非线性方程地基本概念与重要解法.4.2非线性方程求根地数值方法4.2.1根地搜索相关定义定义4.2.1设有一个非线性方程()0f x =,其中()f x 为实变量x 地非线性函数. <1）如果有x *使()0f x *=,则称x *为方程地根,或为()f x 地零点. <2）当()f x 为多项式,即()110(),0n n n n n f x a x a x ax a a --=++++≠则称()0f x =为n 次代数方程.当()f x 包含指数函数或者三角函数等特殊函数时,则称()0f x =为特殊方程.<3）如果()()()m f x x x g x *=-,其中()0g x *≠.m 为正整数,则称x *为()0f x =地m 重根.当1m =时,称x *为()0f x =地单根.定理 4.2.1设()0f x =为具有复系数地n 次代数方程,则()0f x =在复数域上恰有n 个根<r 重根计算r 个）.如果()0f x =为实系数方程,则复数根成对出现,即当：()0i αββ+≠为()0f x =地复根,则i αβ-亦是()0f x =地复根.定理4.2.2设()f x 在[],a b 连续,且()()0f a f b ⋅<,则存在(),x a b *∈,使得()0f x *=,即()f x 在(,)a b 内存在零点.4.2.2逐步搜索法对于方程()0f x =,[],x a b ∈,为明确起见,设()0f a <,()0f b >,从区间左端点0x a =出发按某个预定步长h <如取b ah N-=,N 为正整数）,一步一步地向右跨,每跨一步进行一次根地搜索.即检查节点k x a kh =+上地函数值()k f x 地符号,若()0k f x =,则k x 即为方程解；若()0k f x >,则方程根在区间1[,]k k x x -中,其宽度为h .例4.2.1考察方程()310f x x x =--=因为()()010,250f f =-<=> 则()f x 在()0,2内至少有一个根,设从0x =出发,以0.5h =为步长向右进行根地搜索.列表记录各节点函数值地符号,如表4.2.1所示.可见方程在[]1.0,1.5内必有一根.表4.2.1()f x 地符号用此法就可以得到任意精度地根,但h 缩小,搜索步数增多,从而使计算量增大,用此方法对高精度要求不简便.4.2.3二分法对非线性方程：()0 f x =()4.2.1其中()f x 在[],a b 上连续且设()()0f a f b ⋅<,不妨设()f x 在[],a b 内仅有一个零点.求方程(4.2.1>地实根x *地二分法地过程,就是将[],a b 逐步分半,检查函数值符号地变化,以便确定包含根地充分小区间. 二分法地步骤如下：记1a a =,1b b = 第1步：分半计算()1k =,即将11[a ,b ]分半.计算中点1112a b x +=及()1f x .若11()()0f a f x ⋅<,则根必在1122[,][,]a x a b ∆内,否则必在1122[,][,]x b a b ∆内<若1()0f x =,则1x x *=）,于是得到长度一半地区间22[,]a b 含根,即22()()0f a f b <,且22111()2b a b a -=-.第k 步：<*分半计算）重复上述过程.设已完成第1步第1k -步,分半计算得到含根区间1122[,][,][,]k k a b a b a b ⊃⊃⊃,且满足()()0k k f a f b <,即[,]k k x a b *∈,11()2k k k b a b a --=-,则第k 步地分半计算：2k k k a b x +=,且有： ()122k k k k b a x x b a *--≤=-() 4.2.2确定新地含根区间11[,]k k a b ++,即如果()()0k k f a f x <,则根必在11[,][,]k k k k a x a b ++∆内,否则必在11[,][,]k k k k x b a b ++∆内,且有：111()2k k k b a b a ++-=-.总之,由上述二分法得到序列{}k x ,由(4.2.2>有：lim k k x x *→∞=.可用二分法求方程()0f x =地实根x *地近似值到任意指定地精度,这是因为：设0ε>为给定精度要求,则由2k k b ax x ε*--≤<,可得分半计算次数k 应满足：()()ln ln ln 2b a k ε-->() 4.2.3二分法地优点是方法简单,且只要求()f x 连续即可.可用二分法求出()0f x =在[],a b 内地全部实根,但二分法不能求复根及偶数重根,且收敛较慢,函数值计算次数较多.例4.2.2用二分法求6()1f x x x =--在[]12，内一个实根,且要求精确到小数点后第三位.<即*31102k x x --<⨯）解：由30.510ε-=⨯代入式(4.2.3>,其中1,2)a b ==（,可确定所需分半次数为11k =,计算结果部分如表4.2.2所示<显然(1)10,(2)0f f =-<>）.4.2.4迭代法迭代法是一种逐次逼近法.它是求解代数方程、超越方程及方程组地一种基本方法,但存在是否收敛及收敛快慢地问题.用迭代法求解()0f x =地近似根,首先需将此方程化为等价地方程：() x g x = (4.2.4)然而将()0f x =化为等价方程 (4.2.4)地方法是很多地. 例4.2.3对方程()sin 0.50f x x x =--=可用不同地方法将其化为等价方程：<1）1sin 0.5()x x g x =+∆<2）()12sin 0.5()x x g x -=-∆ 定义4.2.2<迭代法）设方程为()x g x =<1）取方程根地一个初始近似0x ,且按下述逐次代入法,构造一个近似解序列：()()()10211,, k k x g x x g x x g x +=== (4.2.5)这种方法称为迭代法<或称为单点迭代法）,()g x 称为迭代函数.<2）若由迭代法产生序列{}k x 有极限存在,即*lim k k x x →∞=,称{}k x 为收敛或迭代过程 (4.2.5)收敛,否则称迭代法不收敛.若()g x 连续,且*lim k k x x →∞=,则()1lim lim ()lim ()k k k k k k x x g x g x g x **+→∞→∞→∞====,即x *为方程 (4.2.4)地解<称x *为函数()g x 地不动点）,显然在由方程()0f x =转化为等价方程()x g x =时,选择不同地迭代函数()g x ,就会产生不同地序列{}k x <即使初值0x 选择一样）且这些序列地收敛情况也不一定相同.例4.2.4对例4.2.1中方程考查用迭代法求根()()()111sin 0.5,0,1,2,sin0.5,0,1,2,k k k k a x x k b x x k +-+=+==-=由计算可以看出,我们选取地两个函数()()12,g x g x ,分别构造序列{}k x 收敛情形不一样<初值都取为1）,在()a 中{}k x 收敛且 1.497300x *≈,在()b 中计算出()()114sin 0.5sin 1.987761x ---=-无定义.部分计算结果如下表4.2.3：表4.2.3 部分计算结果因此对用迭代法求方程()0f x =地近似根,需要研究下述问题： （1） 如何选取迭代函数()g x 使迭代过程()1k k x g x +=收敛. （2） 若{}k x 收敛较慢时,怎样加速{}k x 收敛.迭代法地几何意义：求方程()x g x =根地问题,是求曲线()y g x =与直线y x =交点地横坐标x *,当迭代函数()g x 地导数函数()'x g 在根x *处满足下述几种条件时,从几何上来看迭代过程()1k k x g x +=地收敛情况如图4.2.1.从曲线()y g x =上一点()()000,p x g x 出发,沿着平行于x 轴方向前进交y x =于一点0Q 再从0Q 点沿平行于y 轴方向前进交()y g x =于1p 点,显然1p 地横坐标就是()10x g x =,继续这过程就得到序列{}k x ,且从几何上观察知道在<1）,<2）情况下{}k x 收敛于*x ,在(3>,(4>情况{}k x 不收敛于*x .图4.2.1 迭代法地几何意义图由迭代法地几何定义知,为了保证迭代过程收敛,应该要求迭代函数地导数满足条件'()1g x <.当[,]x a b ∈时,原方程在[,]a b 中可能有几个根或迭代法不收敛,为此有关于迭代收敛性地定理4.2.3.定理4.2.3设有方程g()x x =, （1） 设g()x 于[a,b]一阶导数存在, （2） 当[a,b]x ∈时,有g()[a,b]x ∈,（3） 'g ()x 满足条件：'()1,[,],g x L x a b ≤<∀∈则有：1g()x x =在[,]a b 上有唯一解*x ,2对任意选取初始值0[,]x a b ∈,迭代过程1(),k 0,1,...k k x g x +==收敛即*k lim x x =,3*111k k k x x x x L+-≤--, 4误差估计式：*10 ,(1,2, (1)k L x x x x k L-≤-=-.证明：<只证2,3,4）2由定理条件(2>,当取0[,]x a b ∈时,则有[,],(1,2,...)k x a b k ∈=,记误差*k k e x x =-,由中值定理有：**'*1()()()()k k k x x g x g x g c x x +-=-=-,其中c 在*x 与k x 之间,即[,]c a b ∈,又由条件(3>有：*'**1()k k kx x g c x x L x x +-≤-≤-,由此递推可得：**2**120...k k k k x x L x x L x x L x x ---≤-≤-≤≤-,由01L <<故*k lim x x =.3由迭代公式1()k k x g x +=有：'1111()()()()k k k k k k k k x x g x g x g c x x L x x +----=-=-≤-,其中c 在1k x -与k x 之间,于是：****111***() -L x (1-L)k k k k k k k k k x x x x x x x x x x x x x x x +++-=---≥---≥--=-即*11111k k k k k Lx x x x x x L L+--≤-≤---. 4由上面11k k k k x x L x x +--≤-反复利用代入上式中有：*1121210111L ...11k k k k k kk k Lx x x x x x L LLx x x x L L +----≤-≤---≤-≤≤--- 由定理结果3可知,当计算得到地相邻两次迭代满足条件1k k x x ε+-<时,则误差*11k x x Lε-<-. 因此在计算机上可利用1k k x x ε+-<来控制算法终止,但要注意1L ≈时,即使1k k x x +-很小,但误差*k x x -可能很大.另外,当已知01,x x 及(1)L L <及给定精度要求ε时,利用定理结果4可确定使误差达到给定精度要求时所需要迭代次数k ,事实上,由*101kk L x x x x Lε-=-<-解得：10(ln ln)/ln 1x x k L Lε->-- (4.2.6) 定理条件'()1,[,]g x L x a b ≤<∈,在一般情况下,可能对大范围地含根区间不满足,而在根地附近是成立地,为此有如下迭代过程地局部收敛性结果.定理4.2.4<迭代法地局部收敛性）设给定方程g()x x =, <1）设*x 为方程地解,<2）设g()x 在*x 地邻域内连续可微,且有'*()1g x <,则对任意初值0x <在*x 地邻域内）,迭代过程1()k x g x +=,0,1,...k =收敛于*x . 例4.2.5由迭代法解方程()ln(2)0f x x x =-+=解 (1>显然有(0)(2)0,( 1.9)(1)0f f f f <--<即知方程于[0,2]及[ 1.9,1]--内有根记为12,x x **.(2>考察取初值0[0,2]x ∈迭代过程1ln(2)k k x x +=+地收敛性,其中迭代函数为1()ln(2)g x x =+,显然1(0)ln(2)0.6930g =≈>,1(2)ln(4) 1.3682g =≈<,及1()g x 为增函数,则当02x ≤≤时,10()2g x ≤≤,又由'1()2g x x =+则有''111()(0)1([0,2])22g x g x x =≤=<∀∈+.于是由定理4.2.4可知,当初值[]00,2x ∈时,迭代过程1ln(2)k k x x +=+收敛,如果要求1x *地近似根准确到小数点后第6位<即要求611102k x x *--≤⨯）由计算结果可知7151410x x --≈.且12L =,则*114 1.1461931x x -=,714()0.810f x -≈⨯.(3>为了求[ 1.91]--，内方程地根.由迭代方程1ln(2)k k x x +=+,显然''*121()()12g x g x x =>>+,所以迭代过程1ln(2)k k x x +=+<初值*002[ 1.9,1],x x x ∈--≠）不能保证收敛于*2x .(4>若将方程转化为等价方程e 2xx =+或22()xx e g x ∆=-=则'2g ()x x e =,且''22g ()g (1)0.3861x ≤-≈<<[ 1.9,1]x ∈--时）,2()[ 1.9,1]g x ∈--所以当选取0[ 1.9,1]x ∈--时迭代过程k 12k x x e +=-收敛.如取01x =-,则迭代12次有*212 1.841405660x x ≈=-,且812()0.210f x -≈⨯.由此例可见,对于方程 ()0f x =,迭代函数()g x 取不同形式,相应地迭代法产生地{}k x 地收敛情况也不一样.因此,我们应该选择迭代函数地迭代过程1()k k x g x +=收敛,且收敛较快.关于迭代公式地加工：对于收敛地迭代过程,只要迭代足够多次,总可以使结果达到任意地精度.但有时迭代收敛缓慢,从而使计算量变得很大,因此迭代过程地加速是一个很重要地课题. 设0x 为根*x 地某个预测值,用迭代公式校正一次得：10()x g x =由中值定理：*'*10()()x x g x x ξ-=-,ξ介于*0x x ，之间,若'()g x 改变不大.近似地取某常数L ,则由***10101()11L x x L x x x x x L L-≈-⇒≈---可以期望按上式右端求得地2101101()111L Lx x x x x x L L L=-=+----是比1x 更好地近似值. 若将每得到一次改进值算作一步,并用x 和k x 分别表示第k 步地校正值和改进值,则加速迭代计算方案如下： 校正：k 1 ()k x g x +=改进：k 111k ( )1k k Lx x x x L+++=+-- 因为使用参数L ,这在实际应用中不方便,下面进行改进计算. 设*x 地某近似值0x ,将校正值10()x g x =再校正一次得：21()x g x =,由**21()x x L x x -≈-与**10()()x x L x x -≈-得：**01**21x x x x x x x x--≈--由此得：2*02121201201222x x x x x x x x x x x x x --≈=--+-+2（）.这样将上式右端作为改进公式就不再含有导数信息了.但需要用到两次迭代地结果进行加工.如果仍将得到一次改进值作为一步,则计算过程如下：k 11k 1k 1k 1k 12k 1k 1k 1 () () 2k k k x g x x g x x x x x x x x +++++++++⎧⎪=⎪⎪=⎨⎪-⎪=-⎪-+⎩校正：再校正：（）改进： 上述处理过程称为Aitken <埃特金）方法.4.2.5Newton 公式对于方程()0f x =,应用迭代法时先要改写成()x g x =,即需要针对()f x 构造不同地合适地迭代函数()g x ,显然可以取迭代函数为()()g x x f x =+,相应迭代公式为1()k k k x x f x +=+.一般地,这种迭代公式不一定收敛,或者速度很慢.对此公式应用前面地加速技术.具体格式为：1111()()1k k k k k k k x x f x Lx x x x L++++=+⎧⎪⎨=+-⎪⎩- 记1M L =-,则上二式可合并写为：1()k k k f x x x M+=-.此公式称为简单地Newton 公式,其迭代函数为：()()f x g x x M=-.又因为L 为'()g x 地近似值,而()()g x x f x =+,因此1M L =-实际上是'()f x 地近似值,故用'()f x 代替上式中地M 即得到下面地迭代函数：'()()()f xg x x f x =-.相应地迭代公式为：1'()()k k k k f x x x f x +=-,即为Newton 公式.4.2.6Newton 法地几何意义Newton 法地基本思想就是将非线性方程()0f x =逐步线性化求解,设()0f x =有近似地根k x ,将()f x 在k x 处Taylor 展开得：'()()()()k k k f x f x f x x x ≈+-从而()0f x =近似地表为：'()()()0k k k f x f x x x +-=.方程()0f x =地根*x 即为曲线()y f x =与x 轴交点地横坐标.设k x 为*x 地一个近似,过曲线()y f x =上横坐标为k x 地点k p 作曲线地切线,该切线与x 轴焦点地横坐标即为*x 地新近似值1k x +,它与x 轴交点地横坐标为：'1()/()k k k k x x f x f x +=-,因此Newton 法,亦称切线法.4.2.7Newton 法地局部收敛性定义 4.2.3设迭代过程1()k k x g x +=收敛于方程()x g x =地根*x ,如果迭代误差*k k e x x =-,当k →∞时有：1(0,)k p ke c c e +→≠为常数则称该迭代过程为p 阶收敛地.定理 4.2.5对迭代过程k 1(),k x g x +=如果()()p g x 在*x 附近连续,且：'*''*(p-1)*g ()g ()...g ()0x x x ====且(p)*g ()0x ≠,则该迭代过程在x 附近是p 阶收敛地.证明：因为'*g ()01x =<,则由前面关于迭代法地局部收敛性定理知：此迭代过程1()k k x g x +=具有局部收敛性,即0k x →.将()k g x 在*x 处Taylor 展开,并注意到'*(p-1)*g ()... g ()0x x ===有：()***()()()(),[ , ] !p k k k k k g g x g x x x x x p ξξ=+-∈而,**k 1(), ( )k x g x x g x +==从而上式化为：()**k 1()()!p p k k g x x x x p ξ+-=-即：*()()*1k 1p *k ()e ()e ()!!p p k k pk x x g g x x x p p ξ++-==→- 故知迭代过程具有p 阶收敛性.定理 4.2.5表明迭代过程地收敛速度依赖于迭代函数()g x 地选取,如果[,]x a b ∈时'()0g x ≠,则迭代过程只可能是线性收敛地.对于Newton 法,由迭代函数：'()()-()f xg x x f x = 则'2''''''2'2[()]()()()()g ()1[()][()]f x f x f x f x f x x f x f x -=-=, 若*x 为()f x 地一个单根,即()*'*()00f x f x =≠，,则由上式知'*()0g x =.由上面定理可知Newton 法在根*x 地邻域内是平方收敛地<二阶收敛地）.特别地考察Newton 公式： 设()f x 二次连续可微,则'''2()()()()()()2!k k k k f f x f x f x x x x x ξ=+-+-,ξ在(),k x x 之间,特别地取*x x =,注意*()0f x =,则'*'**2()0()()()()()2!k k k k f f x f x f x x x x x ξ==+-+-设'()0k f x ≠两边同除以'()k f x ,得：''**2''()()()()2()k k k k k f x f x x x x f x f x ξ=---<注：1'()()k k k k f x x x f x +-=）,利用Newton 公式,即有： *''1*2'()()2()k k k k x x f m x x f x ξ+-=--当k →∞,则''''*''*()()2()2()k f f x f x f x ξ-→-,或''**2211'()()2()k k k k kk f x x e x x m e f x ξ++-==--=,可见1k e +<误差）与k x 地误差k e 地平方成比例.当初始误差*00e x x =-充分小时,以后迭代地误差将减少得非常快.反之01e >,则放大.Newton 法每计算一步,需要计算一次函数值()k f x 和一次导数值'()k f x .例4.2.6用Newton 法求解4()(2)10x f x ex -=--=.解：显然(0)(2)0f f <.则在[0,2]内方程有一个根,求导'4()(6)/4x f x ex -=-,则Newton 公式为：41'4()(2)1()(6)/4kk x k k k k k x k k f x e x x x x f x e x -+---=-=--.取0 1.0x =,迭代6次得近似根为*0.783596x ≈,*6() 3.810f x -≈-⨯.这表明,当初值0x 取值靠近*x 时,Newton 法收敛且收敛较快,否则Newton 法可能不收敛.下面考虑Newton 法地误差估计,由中值定理有：*'*()()()()()k k k k f x f x f x f x x ξ=-=-,当k x 充分接近*x 时,有*1''()()()()Newtonk k k k k k k f x f x x x x x f f x ξ+-=-≈-=-.因此,用Newton 法求方程单根*x 地近似根k x 地误差*k k e x x =-可用1k k x x +-来估计.4.2.8Newton 法应用举例(1>对给定地正数C ,应用Newton 法解二次方程20x C -=计算格式：11() 2k k kCx x x +=+ (4.2.7)可证明公式(4.2.7)对任意函数初值00x >都是收敛地.这是因为：21211(21(2k k k k k k x x x x x x ++⎧=-⎪⎪⎨⎪=⎪⎩两式相除得：2=利用此式递推可得：22kkkk q x =⇒=<2k=可知：kk x =则：2(kkk k x x q ==）.而00x ∀>,1q =<.故由公式知)k x k →∞即迭代法恒收敛.）例4.2.7,要求6110k k x x -+-<终止迭代. 解1110()2k k kx x x +=+取0 1.0x =经6次迭代后：5 3.16227767x =,6 3.16227766x =,7650.110x x --=⨯3.16227766≈.(2>对给定正数C ,应用Newton 法求解10C x -=,由此式可导出求1C 而不用除法地计算程序：1(2)k k k x x Cx +=-.这个算法对于没有设置除法操作地电子计算机是有用地.可以证明,此算法初值满足020x C<<时是收敛地,这是因为：21111(2)()k k k k x x Cx C x C C C+-=--=--,即：211(1)k k Cx Cx +-=-,令1k k r Cx =-,由递推公式21k k r r +=反复递推,得：20kk r r =.当0011r Cx =-<,即020x C <<时,有0k r →即1k x C→,从而迭代法收敛. 4.2.9Newton 下山法Newton 法收敛性依赖于初值0x 地选取,如果0x 偏离*x 较远,则Newton 法可能发散.例如,对方程310x x --=.求在 1.5x =附近地一个根*x .若取初值0 1.5x =,则由Newton法：312131k k k k k x x x x x +--=--,计算得1231.34783, 1.32520, 1.32472x x x ===,仅迭代3次即得有6位有效数字地近似值3x .但若取初值00.6x =则由同一Newton 公式计算得117.9x =,这反而比00.6x =更远离所求根* 1.32472x =,因此发散.为防止发散,对迭代过程加一下降要求：1()()k k f x f x +<,满足这项要求地算法称为下山法.将Newton 法与下山法结合,即在下山法保证函数下降条件下,用Newton 法加速收敛.为此,可将Newton 计算结果1'()()k k k k f x x x f x +=-与每一步近似值k x 作加权平均：11(1)k k k x x x λλ++=+-,其中λ<01λ<≤）成为下山因子.选择下山因子λ以保证下降性.λ地选择方法是：由1λ=反复减半地试探法,若能找到λ使下降性成立,则下山成功,否则下山失败,改变初值0x 重新开始.4.2.10弦截法与拋物法Newton 法1'()()k k k k f x x x f x +=-每迭代一次计算函数值()k f x 、导数值'()k f x 各一次,当函数f 本身比较复杂时,求导数值更加困难.下面方法多利用以前各次计算地函数值1(),(),k k f x f x -来回避导数值'()k f x 地计算,导出这种求根方法地基本原理是插值法.设1,,,k k k r x x x --是()0f x =地一组近似值,利用对应地函数值1(),(),,()k k k r f x f x f x --,构造插值多项式()r p x ,适当选取()0r p x =地一个根作为()0f x =地新地近似根1k x +.这样就确定了一个迭代过程,记迭代函数为g ,则11(,,,)k k k k r x g x x x +--=,下面具体考察1r =<弦截法）,2r =<拋物法）两种情形.4.2.11弦截法设1,k k x x -为()0f x =地近似根,过点(,())k k x f x ,11(,())k k x f x ++构造一次插值多项式1()p x ,并用1()0p x =地根作为()0f x =地新地近似根1k x +.因为111()()()()() k k k k k k f x f x p x f x x x x x ---=+--(4.2.8)则由1()0p x =可得：111()() ()()k k k k k k k f x x x x x f x f x +--=--- (4.2.9)另外,公式(4.2.9>也可以用导数'()f x 地差商11()()k k k k f x f x x x ----近似取代Newton公式中地'()f x ,同样得公式 (4.2.9).弦截法地几何意义：曲线()y f x =上横坐标为1,k k x x -地点分别记为1,k k p p -,则弦线1k k p p -地斜率等于差商11()()k k k k f x f x x x ----.1k k p p -地方程为：11()()()()0k k k k k f x f x f x x x x x ---+-=-,则按 (4.2.9)求得地近似根1k x +实际上是弦线1k k p p -与x 轴交点地横坐标.因此这种算法称为弦截法,又称割线法.弦截法与切线法<Newton 法）都是线性化方程,但两者有本质区别.Newton 切线法在计算1k x +时只用到前一步地k x 及()k f x ,但要计算'()k f x ,而弦截法在计算1k x +时要用前面两步地结果11,,(),()k k k k x x f x f x --,而不需计算导数.这种方法必须有两个启动值01,x x .例4.2.8用割线法求解方程32()390f x x x x =--+=在(2, 1.5)--地根.解取初值012,1x x =-=-,则迭代5次后有6 1.525102x =-,6()0.000000f x ≈.例子表明弦截法仍具有较快地收敛性.定理 4.2.6假设()f x 在根*x 邻域*:x x δ∆-≤内具有二阶连续导数,且对x ∀∈∆有'()0f x ≠.又初值01,x x ∈∆,那么当邻域∆充分小时,弦截法(4.2.9)将按阶151.6182P +=≈收敛到根*x .(证明略>下面分析弦截法用于求解()x g x =时,对Atken 加速算法地几何解释：x 为()x g x =地近似根,10()x g x =,21()x g x =在曲线上走了两点001112(,),(,)p x x p x x ,引弦线01p p 与直线y x =交于一点'2p ,则'2p 地横坐标<与纵坐标相等）为：2021213130310012()2x x x x x x x x x x x x x x x --=+-⇒=--+此即为Atken 加速计算方法地公式.由图可以看出,所求地根*x 是曲线()y g x =与y x =地交点*p 地横坐标,从图形上看,尽管迭代值2x 比0x 和1x 更远偏离了*x ,但按上式求得地3x 却明显地扭转了这种发散地趋势.4.2.12 抛物线法设已知()0f x =地三个近似根为12,,k k k x x x --,以这三点为节点构造二次插值多项式2()p x ,并适当选取2()p x 地一个零点1k x +作为新地近似根.这样确定地迭代过程称为拋物线法<亦称密勒法）.拋物线插值多项式为：()()[]()[]()()21121,,,k k k k k k k k k p x f x f x x x x f x x x x x x x ----=+-+--有两个零点：()()[]121224,,k k k k k k k f x x x f x f x x x ωω+--=-±-(4.2.10)其中,[][]()1121,,,k k k k k k k f x x f x x x x x ω----=+-其几何意义就是：用抛物线2()y p x =与x 轴地交点1k x +作为所根*x 地近似值.为了由(4.2.10)定出一个值1k x +,需讨论根式前正负符号地取舍问题在12,,k k k x x x --三个近似根中,自然假定以k x 更接近所求地根*x ,这时为保证精度,选取(4.2.10)中较近k x 地一个值作为新地近似根1k x +,为此,只要令根式前地符号与ω地符号相同.例4.2.9用抛物线法求解方程()10x f x xe =-=解取三个初值0120.5,0.6,0.56532x x x ===,计算0()0.175639f x =-,1()0.093271f x =-,2()0.005031f x =-,10[,] 2.68910f x x =,21[,] 2.83373f x x =,210[,,] 2.21418f x x x =,2121021[,][,,](,) 2.75694f x x f x x x x x ω=+=,从而：232222102()0.567144()[,,]f x x x f x f x x x ωω=-=±-.定理4.2.7若()f x 在根*x 地邻域∆内()*x x δ-<有三阶连续偏导数,且对x ∀∈∆,有'()0f x ≠,又初值012,,x x x ∈∆,那么当邻域∆充分小时,抛物线法(4.2.8>将按阶1.840p =收敛于根*x .可见抛物线法比弦截法收敛阶更接近于Newton 法,定理地证明略.4.2.13多项式求值地秦九韶算法多项式地重要特点之一是求值方便,设1011()n n n n f x a x a x a x a --=++++,系数(0)i a i n ≤≤均为实数.用0x x -除()f x ,记其商为()p x ,则其余项显然为0()f x 即00()()()() f x f x x x p x =+-(4.2.11)令120121()n n n n p x b x b x b x b ----=++++代入公式(4.2.11)后与()f x 比较同项式系数,可得：0001001 11()i i i nn a b a b x b i n a f x x b--=⎧⎪=-≤≤-⎨⎪=-⎩ 从而有：0001001 1 1 ()i i i n n nb a b a x b i n f x a x bb --⎧=⎪=+≤≤-⎨⎪=+⎩(4.2.12) (4.2.12)式提供了计算函数值0()f x 地有效算法称为秦九韶法.这种算法地优点是计算量小,结构紧凑,易编制计算机程序.再看()f x 地n 阶Taylor 展开式：注意<对n 次多项式）更高阶导数为0.'''20000000()()()()()()()()2!!n n f x f x f x f x f x x x x x x x n ≡+-+-++-将它表示为：00()()()()f x f x x x p x =+-则有：'''112000000121()()()()()()2!!n n n n n n f x f x p x f x x x x x b x b x b x b n -----=+-++-=++++可见导数值'0()f x 又可看作()p x 用因子0x x -相除得出地余数,从而有：'00()()()()p x f x x x q x =+-,式中()q x 是2n -次多项式.令230132()n n n n q x c x c x c x c ----=++++那么用秦九韶算法又可求出值'0()f x .对应于此处地计算公式为：0001'0110212()i i i n n n c b c b x c i n f x c b x c ----⎧=⎪=+≤≤-⎨⎪=+⎩(4.2.13) 其中i b 已由公式(4.2.12)计算出.4.2.14 代数方程地Newton 法对120121()0n n n n n f x a x a x a x a x a ---=+++++=,考察Newton 公式：1'()()k k k k f x x x f x +=-(4.2.14) 根据公式(4.2.12),(4.2.13)即可求()k f x ,'()k f x ,从而由公式(4.2.14)即可得1k x +.4.2.15劈因子法关于Newton 法对重根地处理.定理4.2.8设()()(),()0m f x x h x h x α=-≠,在点x 附近()f x 有连续地2m +阶导数,则：'''2()()1lim 1[()]x f x f x f x mα→=- 若2m =,即α为()f x 地二重根,则可将Newton 法中迭代函数改写为：'2()()()f xg x x f x =-,则： '2''''''2'22[()]2()()()()()112[()][()]f x f x f x f x f x g x f x f x -=-=-+ ''''2()()1()lim[12]12(1)0[()]2x f x f x g x f x α→=-+=-+-= 因此仍然能保证在α领域内'()1g α<,使算法具有二阶收敛性.在实际应用中对于m 重根,迭代函数可改写成'()()()mf x g x x f x =-,但因为一般不能确定常数m ,则可考虑函数'()()()f x x f x μ=.如果()()(),2m f x x h x m α=-≥是正整数,()0h α≠,则'()()()[()()()]x h x x mh x x h x αμα-=+-,显然α是()x μ地单重零点,故可将切线法<即Newton 法）用于()x μ,得到二阶收敛地迭代函数：'()()()x g x x x μμ=- 或''2''()()() [()]()()f x f xg x x f x f x f x =-- (4.2.15) 将此作为迭代函数即可找到根α,收敛阶为2阶.例 4.2.10对于方程42*()440,f x x x x =-+==是二重根.用下面三种方法求根：(1> Newton 法：2124k k k kx x x x +-=-； (2> '()()/(),2x x mf x f x m ϕ=-=即2122k k k k x x x x +-=-； (3> 由上面(4.2.15)所确定地修改方法化简为：2122k k k kx x x x +-=-三种方法均取初值0 1.5x =.计算结果为：经3次迭代,方法2、3均达到910-精度.它们都是二阶收敛地方法.而方法1是一阶地,要进行30次迭代才能达到同样地精度.4.3养老保险模型地求解对4.2中建立地养老保险模型,以25岁起保为例,假设男性平均寿命为75岁,则200,2282;420,600p q N M ====,初始值为00=F ,我们可以得到：M N k r r q r F F N k r r p r F F N k N k N k k k k ,...,1],1)1[()1(`,..,2,1,0],1)1[()1(0+=-+-+==-+++=-- 在上面两式中,分别取k N =和M k =并利用0=M F 可以求出：0)1)(1()1(=+++-+-pq r p q r N M M 在上述介绍地非线性方程求根法中选取牛顿法进行求解,利用迭代公式：1'()()k k k k f r r r f r +=-其中600180()(1)12.41(1)11.41f r r r =+-++,'599179()600(1)12.41180(1)f r r r =+-⨯+ 利用MATLAB 编程编写牛顿迭代法程序,令初值为00r =,迭代最大次数为10000,求出方程地根为：00485.0=r同样方法可以求出：35岁和45岁起保所获得地月利率分别为00413.0,00461.0==r r习题 41．用迭代法求解如下方程在(1,2)内地实根3()10f x x x =--=.2．用Newton 法求()cos 0f x x x =-=地近似解.3．用弦截法求方程3()10f x x x =--=在区间(1,2)内地实根.4．利用二分法求方程2sin cos 0x x ππ+=在[0,1]内地根(0.01)ε=.。

非线性方程数值解法及其应用摘要:数值计算方法主要研究如何运用计算机去获得数学问题的数值解的理论和算法。

本文主要介绍非线性方程的数值解法以及它在各个领域的应用。

是直接从方程出发，逐步缩小根的存在区间，或逐步将根的近似值精确化，直到满足问题对精度的要求。

我将从二分法、Steffensen加速收敛法、Newton迭代法、弦截法来分析非线性方程的解法及应用。

关键字：非线性方程;二分法；Steffensen加速收敛法；代数Newton法；弦截法一、前言随着科技技术的飞速发展，科学计算越来越显示出其重要性。

科学计算的应用之广已遍及各行各业，例如气象资料的分析图像，飞机、汽车及轮船的外形设计，高科技研究等都离不开科学计算。

因此经常需要求非线性方程 f(x) = O的根。

方程f(x) = O 的根叫做函数f(x)的零点。

由连续函数的特性知：若f(x)在闭区间[a，b]上连续，且f(a)·f(b)<O，则f(x) = O在开区间(a,b)内至少有一个实根。

这时称[a,b]为方程f(x) = O的根的存在区间。

本文主要是对在区间[1.2]的根的数值解法进行分析，介绍了非线性方程数值解法的四种方法，从而得到在实际问题中遇到非线性方程根的求解问题的解决方法。

二、非线性方程的数值解法1、二分法二分法的基本思想是将方程根的区间平分为两个小区间，把有根的小区间再平分为两个更小的区间，进一步考察根在哪个更小的区间内。

如此继续下去，直到求出满足精度要求的近似值。

设函数f(x)在区间[a,b]上连续，且f(a)·f(b)<O，则[a,b]是方程f(x)=O 的根的存在区间，设其内有一实根，记为。

取区间[a,b]的中点，并计算，则必有下列三种情况之一成立：(1)= O,就是方程的根；(2)f(a)·f()<O，方程的根位于区间[a,]之中，此时令，；(3)f()·f(b)<O，方程的根位于区间[,b]之中，此时令。

非线性函数方程根的求解法
一、问题提出
设方程f(x)=x 3
- 3x –1=0 有三个实根 x *1=1.8793 , x *2=-0.34727 ,x *3=-1.53209
现采用下面六种不同迭代格式，求 f(x)=0的根 x *1 或x *2 1、 x = 2
13x x + 2、 x = 3
13-x 3、 x = 313+x
4、 x = 3
12-x 5、 x = x
13+ 6、 x = x - ()1133123---x x x
二、要求
1、编制一个程序进行运算，最后分析每种迭代格式的敛散情况；
2、用事后误差估计k k x x -+1〈ε来控制迭代次数，并且打印出迭代的次数；
3、初始值的选取对迭代收敛有何影响；
4、分析迭代收敛和发散的原因。

三、目的和意义
1、通过实验进一步了解方程求根的算法；
2、认识选择迭代格式的重要性；
3、掌握迭代算法和精度控制；
4、明确迭代收敛性与初值选取的关系。

四、附加实验内容（可选做）
1、用二分法求方程013
=--x x 在[1,2]的近似根，准确到10-2；
2、分别用牛顿法和弦截法解方程01=-x xe ，准确到10-5；。

2013-10-221第四章非线性方程(组)求解4.1 方程求根与二分法4.2 不动点迭代法及其收敛性4.3 迭代收敛的加速方法4.4 牛顿法4.5 抛物线法4.6 多项式零点4.7 非线性方程组的数值解法2013-10-222¾代数方程：110=+++−n n n a xa x a "¾超越方程：包含超越函数（如sinx ，lnx ）的方程。

¾非线性方程：n (≥2)次的代数方程和超越方程。

方程分类:方程根的特点:•n 次代数方程有且只有n 个根(包括复根、重根）•5次以上的代数方程没有求根公式，一般采用数值方法。

•超越方程有无根、有几个根通常难以判断4.1.1引言2013-10-223何时终止?1k k x x ε+−<()k f x ε<或2013-10-2242013-10-2252013-10-2262013-10-22712+k xx 2013-10-2282013-10-229(x) 2013-10-22102013-10-22112013-10-22122013-10-2213*|x −2013-10-22142013-10-22152013-10-2216||k ke →∞16k2013-10-22172013-10-22182013-10-22192013-10-2220)) 2013-10-22212013-10-22222013-10-22232013-10-22242013-10-22252013-10-2226附近的根,2013-10-22272013-10-22282013-10-22292013-10-22302013-10-22312013-10-22322013-10-22332013-10-22342013-10-2235x k x k +1,)1(1k k x x λλ−++]1,0[∈λx，以这三点为节点构造二次插值多项2013-10-22362013-10-22372013-10-2238•要求多项式的值，应先计算最内层多项式：2013-10-22392013-10-22402013-10-22412013-10-2242其中f 1,",f n 均为(x 1,",x n )的多元函数. 若用向量记号记x =(x 1,",x n )T ∈R n ,F =(f 1,",f n )T , 可写成：F (x )=0. 考察方程组.0),,(.........................,0),,(111⎪⎩⎪⎨⎧==n n n x x f x x f ""当n ≥2，且f 1,",f n 中至少有一个是自变量x 1,",x n 的非线性函数，则称方程组为非线性方程组。

第四章 非线性方程和方程组的数值解法教学目标：1.了解并掌握非线性方程的根的相关概念，如m 重根、有根区间等概念；2.掌握逐步搜索法和二分法（区间对分法）的基本思想及步骤，了解这两种方法的适用性及缺点，能应用其求解简单的非线性方程；3.了解迭代法的分类，理解并掌握不动点迭代法的概念及相关收敛性定理，掌握全局收敛性及局部收敛性联系及区别，理解收敛阶和计算效率的相关概念的来历及含义；4.了解迭代加速的思想，掌握加权法（松弛法）、Aitken 以及Steffensen 加速方法的思想及相关理论、计算公式；5.理解并掌握Newton 迭代法及求重根的修正Newton 迭代法的思想、实现步骤以及相关理论；6.理解Newton 迭代法的相关变形方法的提出及实现步骤，如简化Newton 法（平行弦法）、Newton 下山法、拟Newton 法和Steffensen 方法；7、理解割线法和Muller 法提出的背景及实现步骤，掌握相关的理论。

教学重点：1.逐步搜索法和二分法（区间对分法）的基本思想及步骤；2.不动点迭代法的概念及相关收敛性定理；3.迭代加速的思想及三种实现方式；4. Newton 迭代法及相关变形或改进的迭代法的思想及步骤。

教学难点：1..不动点迭代法的概念及相关收敛性定理；2.迭代加速的思想及三种实现方式；3. Newton 迭代法及相关变形或改进的迭代法的思想及步骤。

教学方法：教具：§4.1 问题的提出非线性科学是当今科学发展的一个重要研究方向，而非线性方程的求根也成了一个不可缺的内容。

但是，非线性方程的求根非常复杂。

本章重点讨论单个方程的求根方法，对于非线性方程组的解法仅作一些简单的介绍。

这是因为单个方程的求根问题比非线性方程组更普遍。

另外非线性方程组的求解是个难度比较大的问题，许多近代研究集中在这个问题上。

非线性方程和方程组的数值解法主要是迭代法。

一般的非线性方程组可以写成()0F x =，其中F 和x 都是n 维向量。

第四讲：（2）非线性方程数值解法在实际物理问题中，例如如何知道热平衡时的温度，力平衡时的力的大小等平衡量，需要求解平衡方程。

对于不能解析求解的代数方程就需要数值求解。

本讲只讨论单变量的代数方程()0f x = （4.2-1）为了求解满足方程的变量x ，即方程的根，有时需要用图示的方法大体了解解的位置。

下面介绍几种求方程（4.2.1）根的方法。

4.2.1二分法（Bisection Method ）方程根附近的性质是()f x 要改变符号，一般来说，如果()f x 在区间[,]l u x x 是连续的实函数，并且()l f x 和()u f x 有相反的符号，即()()0l u f x f x ⋅< （4.2-2）那么在区间[,]l u x x 内至少有一个实根。

一般采用增量搜寻的方法来确定函数变号的间隔，例如[,]l u x x ；然后将这个间隔分成更小的许多子间隔来确定函数变号的位置（即根）。

怎样再细分间隔[,]l u x x ，通常采用的一种方法是对分区间套的方法，即二分法。

二分法求根步骤：① 通过满足条件()()0l u f x f x ⋅<，确定有根区间[,]l u x x② 估算根：()/2r l u x x x =+，如果100%new oldr r a newrx x eps x ε-=<, 那么new r x 为解 ③ 做下面的计算，确定根在那个子区间(a) 如果()()0l r f x f x ⋅<，那么根在区间[,]l r x x ，设u r x x =，返回到② (b)否那么()()0l r f x f x ⋅>，那么根在区间[,]r u x x ，设l r x x =，返回到②二分法求根示意图※================================================================※例题4.2-1用二分法计算方程2ln()0x e x x -=的在区间（1，2）的根。