迭代法个税计算器在线计算

迭代法开方法Newton法改进的牛顿法埃特金方法BUCT计算方法Ch04方程求根的迭代法程勇buctcourse@163.
comhttp://www.
buct.
edu.
cnDept.
ofComputerBeijingUniversityofChemicalTechnologySept.
19,2019YongChengComputingMethodsCh04方程求根的迭代法1/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT提纲1Ch01概论2Ch02插值方法3Ch03数值积分4Ch04方程求根的迭代法5Ch05线性方程组的迭代法6Ch06线性方程组的直接法7Ch07常微分方程的差分法YongChengComputingMethodsCh04方程求根的迭代法2/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT本章提纲迭代法开方法Newton法改进的牛顿法埃特金方法YongChengComputingMethodsCh04方程求根的迭代法3/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT迭代法绪论中已经介绍过算法设计的校正思想.
迭代法是求解方程近似根的一种方法,这种方法的关键是确定迭代函数φ(x)(将方程f(x)=0变换为x=φ(x)),建立迭代格式xk+1=φ(xk),然后从给定的初值x0出发迭代出一系列的近似值x1,x2,xk,直到逼近方程的根x,直到满足精度要求|xk+1xk|0,求开方值√a就是要求解二次方程x2a=0(1)为此可使用校正技术从预报值生成校正值来逐步逼近方程的解.
设给定某个预报值xk,希望借助于某种简单方法确定校正量x,使校正值xk+1=xk+x(2)更好的满足方程,即:x2k+2xkx+(x)2≈a(3)成立.
设校正值x是个小量,舍去高阶小量(x)2后令:x2k+2xkx=aYongChengComputingMethodsCh04方程求根的迭代法6/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT开方公式(续)从中解出x,得:x=ax2k2xk代入上式,即可求出开方公式:xk+1=12(xk+axk)k=1,2,3,···上述演绎过程表明开方法的设计思想是逐步线性化,即将二次方程的求解化归为一次方程求解过程的重复.
YongChengComputingMethodsCh04方程求根的迭代法7/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT开方算法开方算法任给初值x0>0,反复利用迭代公式即可获得满足精度要求的开方值:{x0>0xk+1=12(xk+axk)k=1,2,3,···直到|xk+1xk|0均收敛,即limk→∞xk→√a或表示为迭代误差limk→∞ek=limk→∞|xk√a|→0YongChengComputingMethodsCh04方程求根的迭代法10/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT开方公式的收敛性证明证明:由xk+1=12(xk+axk)可得xk+1√a=12xk(xk√a)2同理xk+1+√a=12xk(xk+√a)2两式相除xk+1√axk+1+√a=(xk√a)2(xk+√a)2=(xk√axk+√a)2YongChengComputingMethodsCh04方程求根的迭代法11/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT开方公式的收敛性证明(续)这样有:xk√axk+√a=(xk1√axk1+√a)2=(xk2√axk2+√a)22(x0√ax0+√a)2k令q=|x0√ax0+√a|,显然当x0>0时,有00;则由迭代公式确定的牛顿迭代法序列{xk}收敛于f(x)在[a,b]上的唯一根x.
YongChengComputingMethodsCh04方程求根的迭代法16/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT牛顿法的收敛性(续)Newton迭代法的收敛性依赖于x0的选取.
YongChengComputingMethodsCh04方程求根的迭代法17/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT牛顿法例子例题:用牛顿法求下面方程的根:f(x)=x3+2x2+10x20=0解:因f′(x)=3x2+4x+10所以迭代公式为xk+1=xkf(xk)f′(xk)=xkx3k+2x2k+10xk203x2k+4xk+10取x0=1,x1=x0x30+2x20+10x0203x20+4x0+10YongChengComputingMethodsCh04方程求根的迭代法18/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT牛顿法例子(续)接上x1=113+2·12+10·1203·12+4·1+10=1.
411764706同理,可求x2,x3,计算结果列于下表.
kxk11.
41176470621.
36933647131.
36880818941.
368808108从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果,精度为107.
YongChengComputingMethodsCh04方程求根的迭代法19/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT迭代过程的收敛速度定义:p阶收敛如果迭代误差ek=xxk当k→∞时成立:ek+1epk→c(c=0的常数)则称迭代过程是p阶收敛的.
当p=1时称线性收敛,当p=2时称平方收敛,当1定理Newton迭代法xk+1=xkf(xk)f′(xk)在f(x)=0的单根x临近为平方收敛.
YongChengComputingMethodsCh04方程求根的迭代法20/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCTNewton迭代法分析Newton迭代法优缺点:Newton迭代法逻辑结构简单、收敛速度很快(平方收敛),但它通常依赖初值x0的选取,如果初值x0选择不当,将导致迭代发散或产生无限循环;此外,每一步迭代都需要计算导数值f′(x),有时计算f′(x)是不方便的.
基于这两点,产生了几种Newton迭代法的变形形式.
1牛顿下山法;2弦截法;3快速弦截法;YongChengComputingMethodsCh04方程求根的迭代法21/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT牛顿法例子一般地说,Newton法的收敛性依赖于初值x0的选取,如果x0偏离解x较远,则Newton法可能发散或产生无限循环.
例题:用Newton求方程x3x1=0在x=1.
5附近的一个根.
解:因f′(x)=3x21可得牛顿迭代公式:xk+1=xkf(xk)f′(xk)=xkx3kxk13x2k1YongChengComputingMethodsCh04方程求根的迭代法22/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT牛顿法例子(续)分别取x0=1.
5和x0=0.
6,计算结果如下表.
kxkxk01.
50.
611.
3478317.
9000021.
3252011.
9468031.
324727.
98551941.
32472由上表可知道,当x0=0.
6时结果偏离所求的根,不收敛(发散)或收敛较慢.
YongChengComputingMethodsCh04方程求根的迭代法23/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCTNewton下山法为了防止迭代发散,通常对迭代过程再附加一项要求,即保证函数值单调下降:|f(xk+1)|<|f(xk)|满足这项要求的算法称下山法.
将Newton法与下山法结合使用,即在下山法保证迭代函数值稳定下降的前提下,用Newton法加快速度,即可得到如下Newton下山法:xk+1=xkλf(xk)f′(xk)其中0<λ<1,称下山因子,在迭代过程中通过适当地选取λ以使下山条件|f(xk+1)|<|f(xk)|满足.
下山因子的选择是个逐步探索的过程,从λ=1开始反复将因子λ的值减半进行试算,一旦单调条件|f(xk+1)|<|f(xk)|满足,则称为"下山成功".
反之,如果在上述过程中找不到使下山条件|f(xk+1)|<|f(xk)|成立的下山因子λ,则称"下山失败",这时需另选初值x0重算.
YongChengComputingMethodsCh04方程求根的迭代法24/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT下山法例子例题:使用下山法求方程f(x)=x3–x–1=0的根,取x0=0.
6.
解:迭代公式如下:xk+1=xkλf(xk)f′(xk)=xkλx3kxk13x2k1牛顿下山法的计算结果:kλxk010.
611251.
14063211.
36681311.
32628411.
32472YongChengComputingMethodsCh04方程求根的迭代法25/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT弦截法牛顿法要计算f′(x),现用f(x)的值近似f′(x):认为切线斜率近似等于割线斜率.
f′(xk)≈f(xk)f(x0)xkx0xk+1=xkf(xk)f(xk)f(x0)(xkx0)迭代函数为:φ(x)=xf(x)f(x)f(x0)(xx0)单点弦截法为线性收敛.
YongChengComputingMethodsCh04方程求根的迭代法26/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT弦截法几何意义YongChengComputingMethodsCh04方程求根的迭代法27/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT快速弦截法快速弦截法也称为两点弦截法.
认为切线斜率近似等于割线斜率.
f′(xk)≈f(xk)f(xk1)xkxk1xk+1=xkf(xk)f(xk)f(xk1)(xkxk1)快速弦截法需要2个初值x0和x1,其收敛阶1.
618.
YongChengComputingMethodsCh04方程求根的迭代法28/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT快速弦截法例子例题:使用Newton法和快速弦截法求方程xex–1=0的根.
解:使用Newton法和快速弦截法,迭代公式分别如下:xk+1=xkf(xk)f′(xk)=xkxkexk1exk+xkexkxk+1=xkf(xk)(xkxk1)f(xk)f(xk1)kxkxk00.
50.
510.
571020.
620.
567160.
56531530.
567140.
56709440.
567140.
567143YongChengComputingMethodsCh04方程求根的迭代法29/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT埃特金迭代公式xk+1=φ(xk)xk+1=φ(xk+1)xk+1=xk+1(xk+1xk+1)2xk+12xk+1+xkYongChengComputingMethodsCh04方程求根的迭代法30/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT本章小结迭代法思想;开方法;Newton法;Newton法的改进;迭代过程的加速;YongChengComputingMethodsCh04方程求根的迭代法31/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT练习题1编程实现开方法.
2编程实现Newton法.
YongChengComputingMethodsCh04方程求根的迭代法32/33迭代法开方法Newton法改进的牛顿法埃特金方法BUCT谢谢!
Author:ChengYongAddress:Dept.
ofComputerBeijingUniversityofChemicalTechnologyBeijing,100029,ChinaEmail:buctcourse@163.
comYongChengComputingMethodsCh04方程求根的迭代法33/33