数值分析解非线性方程的迭代法PPT学习教案_第1页
数值分析解非线性方程的迭代法PPT学习教案_第2页
数值分析解非线性方程的迭代法PPT学习教案_第3页
数值分析解非线性方程的迭代法PPT学习教案_第4页
数值分析解非线性方程的迭代法PPT学习教案_第5页
已阅读5页,还剩29页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、会计学1 数值分析解非线性方程的迭代法数值分析解非线性方程的迭代法 ,得到新的有根区间a1,b1, 设(x)在区间a,b上连续且(a)(b)0 . 0 a b y x y=(x) 记a0=a,b0=b,计算 , 2 00 0 ba x 若|(x0)| ,则取x0 ;否则,若(a0)(x0)0,取a1=x0,b1=b0 而且有根区间a1,b1长度是有根区间a0,b0长度的一半, x0 再对有根区间a1,b1重复上面运算, 即: 计算 , 2 11 1 ba x 若|(x1)|, 则取x1; 否则,若(a1)(x1)0, 取a2=x1 ,b2=b1,得到新的有根区间a2,b2. x1 而且有根区间

2、a2,b2长度是有根区间a1,b1长度的一半.一直进行下去,直到求出有根区间ak,bk. 第1页/共34页 此时,再计算 . 2 kk k ba x 或者有|(xk)| ,或者有 11 00 2 11 2222 kk kkkk k abababab x 可见,k趋向无穷大时,xk收敛于 . 而且,若要|xk-| ,只要 1 2 k ab 1log 2 ab k或者 此时可取近似根xk . 在计算过程中,若出现|(xk)|1,或bk-ak2 .则可取xk作为方程(x)=0的近似根,终止运算. 用二分法求x3+4x-10=0在区间1,2内根的近似值,并估计误差. 第2页/共34页 解 这里(x)=

3、x3+4x-7, (1)(2)=-180,所以(x)=0在1,2区间有唯一根. 取x0=1.5,由于(x0)=2.375,得新有根区间1,1.5, x1=1.25,由于(x1)=-0.0468,得新有根区间1.25,1.5, x2=1.375,由于(x2)=1.0996,得新有根区间1.25,1.375, x3=1.3125,由于(x3)=0.511,得新有根区间1.25,1.3125, . x9=1.254882813,得有根区间1.254882813,1.255859375, x10=1.255371094, (x10)=-0.000105285 取x10=1.255371094作为方程根

4、的近似值,且有 00049. 0 2 254882813. 1255859375. 1 2 | 1010 10 ab x 第3页/共34页 只需k5ln210-115.61.即需取x16. 如果取精度=10-5,则要使 5 11 10 2 1 2 | kk k ab x 二分法要求函数在区间a,b上连续,且在区间两端点函数值符号相反,二分法运算简便、可靠、易于在计算机上实现。但是,若方程(x)=0在区间a,b上根多于1个时,也只能求出其中的一个根。另外,若方程(x)=0在区间a,b有重根时,也未必满足(a)(b)0. 而且由于二分法收敛的速度不是很快,一般不单独使用,而多用于为其他方法提供一个

5、比较好的初始近似值. 第4页/共34页 2.1 简单迭代法的一般形式 首先把方程(x)=0改写成等价(同解)形式 x=(x) (4.2) 得到迭代序列xk , 如果xk ,则有=(), 即是方程(x)=0的根. 取一个合适的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3) 这种求方程根的方法称为简单迭代法,或逐次逼近法.其中(x) 称为迭代函数 ,式(4.3)称为迭代格式. 若迭代序列xk 收敛 , 则称简单迭代法是收敛的. 第5页/共34页 解 改写原方程为等价方程 求方程x3-2x-3=0在1,2内的根. 3 32 xx ,建立迭代格式 , 2 , 1 , 0,

6、32 3 1 kxx kk 如果取初值x0=1.9 ,计算得 kxkkxk 0 1 2 3 4 5 1.9 1.89453647 1.89352114 1.89333233 1.89329722 1.89329069 6 7 8 9 10 1.89328947 1.89328925 1.89328921 1.89328920 1.89328920 第6页/共34页 由计算结果有,x10=x9,因此可取x10=1.89328920. 定义4.1 设(x)为定义在区间I上的函数, 且对任何xI,均有(x)I,则称(x)为I到自身上的映射. 方程也可改写成x=(x3-3)/2, 建立迭代格式 xk+

7、1=(xk3-3)/2 , k=0,1,2, 仍取初值x0=1.9, 则有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529 可见,xk,此迭代格式是发散的. 定义4.2 设(x)为I到自身上的映射,且存在0L1,使对任何x1,x2I,有|(x2)-(x1)| L|x2-x1|,则称(x)为I上的压缩映射, L称为Lipschitz常数. 第7页/共34页 若(x)为I上的压缩映射,则(x)在I上连续. 定理4.2 若(x)为I到自身上的映射,且(x)C1(I), |(x)| L1,则(x)为I上的压缩映射. 证 对任意x1,x2I,有 |(x2)-(x1

8、)|=|()|x2-x1| L|x2-x1| 定义4.3 若(x)为I到自身上的映射,且I满足,= (),则称为(x)的不动点. 定理4.3 若(x)为I上的压缩映射, 则(x)在I上存 在唯一的一个不动点,且对任何x0I,由迭代格式 xk+1=(xk) , k=0,1,2, 产生的序列xk收敛于(x)的不动点. 第8页/共34页 证 不妨设I=a,b,作函数(x)=(x)-x,由于xI时, (x)I,则(a)=(a)-a0,(b)=(b)-b0,由(x)的连续性, 必存在I, 使()=()-=0,即=(),就是(x)的不动点. 若,I均为(x)的不动点,则有 |-|=|()-()| L|-|

9、-| 所以只能=,即(x)在I上仅有一个不动点. 对任意x0I,有x1=(x0)I,递推得xkI,设是(x) 的不动点,则 |xk+1-|=|(xk)-()| L|xk-| L2|xk-1-| Lk+1|x0-| 所以xk. 第9页/共34页 若=(),而在I=-,+上(x)满足 |(x)-()| L|x-| 这里L1为Lipschitz常数,则当x0-,+时,有 (1) 由迭代xk+1=(xk)产生的迭代序列xkI; 推论 若(x)C1a,b,且满足 1.a(x)b, xa,b; 2.|(x)| L0, 使对任何xI=-, +都有|(x)| L1. 推论 若=(),(x)在附近具有一阶连续导

10、数,且 |()|0, 当x0I=-, +时, 有 (1) 由迭代xk+1=(xk)产生的迭代序列xkI; ;lim)2( k k x (3) 是I上(x)的唯一不动点. 定理4.5 若(x)为I上压缩映射,则x0I,由迭代 xk+1=(xk) , k=0,1,2, 产生的迭代序列xk满足: 第11页/共34页 证 |xk+1-xk|=|(xk)-(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|xk-| 1 1 kkk xx L L x 01 1 xx L L x k k |xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk

11、-| 0111 111 1 xx L L xx L L xx L x k kkkkk 由误差估计式可见,对任一0,要使|xk-|, 只要 L xx L kln )1 ( ln 01 第12页/共34页 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解 可以验证方程xex-1=0在区间0.5,0.6内仅有一个根. 改写方程为x=e-x ,建立迭代格式 , 2 , 1 , 0, 1 kex k x k 由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61 则称序列xk是p阶收敛的, 称p是收敛阶,C是渐近误差常数. p=1称为线性收敛;p1称超线性收敛;p=2称平方

12、收敛. 设(x)充分光滑, 由于 |ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek| 所以,当()0时,有 0| )(|)(limlim 1 k k k k k e e 第15页/共34页 于是 此时,迭代法是m阶收敛的. 所以,当()0时,简单迭代法只具有线性收敛. 设()=()=(m-1)()=0,但(m)()0, 由于 |ek+1|=|xk+1-|=|(xk)-()| m kk m e m )( ! 1 )( 0| )(| ! 1 )( ! 1 limlim )()(1 m k m k m k k k mm e e 所以 m kk mm k m kkk x m x m x

13、xx )( ! 1 )( )!1( 1 )( 2 1 )()()( )(1)1( 2 下面介绍Aitken加速算法,此方法可对线性收敛的简单迭代法起到加速作用,而且可应用于其它数值方法中。 第16页/共34页 假设 (1)(2),则有 由于 xk+1-=(1)(xk-) xk+2-=(2)(xk+1-) 12 1 k k k k x x x x 即 (xk+1-)2(xk-)(xk+2-) xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2 解得 kkk kkk xxx xxx 12 2 12 2 kkk kk k xxx xx x 12 2 1 2 )( 第17页/共34页 则,

14、序列 注意, 如果第k步发生zk-2yk+xk=0, 就终止计算, 取xk . 如果记 kkk kk kk xxx xx xx 12 2 1 2 )( k x 要比序列x k更快地收敛于 , 可构造如下的Aitken加速算法: , 2 , 1 , 0, 2 )( 2 1 k xyz xy xx kkk kk kk )( kk xy )( kk yz 分别用简单迭代法和Aitken加速算法求方程 x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802) 第18页/共34页 取x0= /2,计算结果如下 k 简单迭代法 k Aitken算法 xk|xk-xk-1|xk|xk-

15、xk-1| 0 1 2 3 4 1.57080 1.6 1.57109 1.59971 1.57138 0.0292 0.02891 0.02862 0.02833 0 1 2 1.5707963 1.58547258 1.58547180 0.01467628 0.00000078 第19页/共34页 Newton迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组. 3.1 Newton迭代公式 设(x)在有根区间a,b上二阶连续可微, x0是根的某个近似值, 因为 2 0 0 000 )( 2 )( )(

16、)()(xx f xxxfxfxf 取(x)(x0)+(x0)(x-x0),方程(x)=0近似为 (x0)+(x0)(x-x0)=0 若(x0)0, 其解为 第20页/共34页 )( )( 0 0 01 xf xf xx 得到根的新的近似值x1 ,一般地,在xk附近线性化方程为 (xk)+(xk)(x-xk)=0 设(xk)0, 其解为 )4 . 4(, 2 , 1 , 0, )( )( 1 k xf xf xx k k kk 迭代格式(4.4)称为 Newton 迭代法. x y o x0 y=(x) x1 x2 直线 y=(x0)+(x0)(x-x0) 就是 y-(x0)=(x0)(x-x

17、0) Newton迭代法也叫切线法. 第21页/共34页 Newton迭代法相当于取迭代函数 )( )( )( xf xf xx 的简单迭代法. 因为 22 2 )( )()( )( )()()( 1)( xf xfxf xf xfxfxf x 如果是(x)=0的单根, 即()=0, 但()0, 则有()=0, 从而可知Newton迭代法在根附近是收敛的. 因为 2 )( 2 )( )()()( kkkk xx f xxxfxfxf 所以 2 )( 2 )( )()()( k k kkk x f xxfxff 第22页/共34页 于是有 2 )( )(2 )( )( )( k k k k k

18、k x xf f xf xf x 2 1 )( )(2 )( k k k k x xf f x 2 1 )( lim k k k x x )(2 )( lim k k k xf f )(2 )( f f 可见, Newton迭代法至少是平方收敛的. 若记 其中( 2 1 2 m M C M2=max|(x)|,m1=min|(x)|. 则有 |xk+1-| C|xk-|2 因此 C|xk+1-| (C|xk-|)2 (C|xk-1-|)4 1 2 0 |)|( K xC 可见,当C|x0-|1, 即|x0-|1/2max|(x)| 时,简化Newton迭代法对x0I收敛.通常取M=(x0).

19、简化Newton迭代法一般只具有线性收敛. 2.割线法 因为 , 2 , 1 , 0, )()( )( 1 1 k xx xfxf xf kk kk k 第26页/共34页 o x y y=(x) x0 x1 x2 x3 为了简化计算(xk),采用迭代格式 , 3 , 2 , 1,)( )()( )( 1 1 1 kxx xfxf xf xx kk kk k kk 称为割线法. 若(x)在根附近二次连续可微,且()0,可以证明割线法是收敛的,且有 )(2 )( lim 1 1 f f ee e kk k k 割线法收敛的阶为 .618. 1 2 51 p 3.计算重根的Newton迭代法 第2

20、7页/共34页 称是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=处连续且h()0, 若h(x)在处充分可微,则 ()=()=(m-1)()=0,(m)()0 由于 mm xhxxf 11 )()()( 可见,恰是方程 0)( 1 m xf 的单根.应用Newton迭代法可得: )()( 1 )( 1 1 1 1 k m k m k kk xfxf m xf xx , 2 , 1 , 0, )( )( k xf xf mx k k k 称之为带参数m的Newton迭代法, 它是求方程(x)=0m重根的具有平方收敛的迭代法. 再看函数: 第28页/共34页 )()()( )()( )( )( )( xhxxmh xhx xf xf xu 可见,恰是方程u(x)=0的单根, 应用Newton迭代法有 )( )( 1 k k kk xu xu xx 这是求方程(x)=0重根的具有平方收敛的迭代法,而且不需知道根

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论