数值分析 第4章解非线性方程的迭代法)

1、第第4 4章章 非线性方程求根非线性方程求根 本章讨论求非线性方程 (x)=0 (4.1)的根的问题. 其中(x)是高次多项式函数或超越函数.如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2等等.1 二二 分分 法法 设(x)在区间a,b上连续且(a)(b)0,根据连续函数的介值定理,区间a,b上必有方程(x)=0的根,称a,b为方程(x)=0的有根区间. ,得到新的有根区间a1,b1, 设(x)在区间a,b上连续且(a)(b)0 .0abyxy=(x) 记a0=a,b0=b,计算,2000bax若|(x0)| ,则取x0 ;否则,若(a0)(x0)0,

2、取a1=x0,b1=b0 而且有根区间a1,b1长度是有根区间a0,b0长度的一半,x0再对有根区间a1,b1重复上面运算, 即: 计算,2111bax若|(x1)|, 则取x1; 否则,若(a1)(x1)0, 取a2=x1 ,b2=b1,得到新的有根区间a2,b2. x1 而且有根区间a2,b2长度是有根区间a1,b1长度的一半.一直进行下去,直到求出有根区间ak,bk.此时,再计算.2kkkbax 或者有|(xk)| ,或者有11002112222kkkkkkkababababx可见,k趋向无穷大时,xk收敛于 .而且,若要|xk-| ,只要12kab1log2abk或者此时可取近似根xk

3、 . 在计算过程中,若出现|(xk)|1,或bk-ak2 .则可取xk作为方程(x)=0的近似根,终止运算.例例1 用二分法求x3+4x-10=0在区间1,2内根的近似值,并估计误差. 解解 这里(x)=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

4、.254882813,得有根区间1.254882813,1.255859375,x10=1.255371094, (x10)=-0.000105285取x10=1.255371094作为方程根的近似值,且有 00049. 02254882813. 1255859375. 12|101010abx只需k5ln210-115.61.即需取x16. 如果取精度=10-5,则要使51110212|kkkabx 二分法要求函数在区间a，b上连续，且在区间两端点函数值符号相反，二分法运算简便、可靠、易于在计算机上实现。但是，若方程(x)=0在区间a，b上根多于1个时，也只能求出其中的一个根。另外，若方程(

5、x)=0在区间a，b有重根时，也未必满足(a)(b)0. 而且由于二分法收敛的速度不是很快,一般不单独使用,而多用于为其他方法提供一个比较好的初始近似值. 2.1 简单迭代法的一般形式简单迭代法的一般形式2 简简 单单 迭迭 代代 法法 首先把方程(x)=0改写成等价(同解)形式 x=(x) (4.2)得到迭代序列xk , 如果xk ,则有=(), 即是方程(x)=0的根.取一个合适的初始值x0,然后作迭代 xk+1=(xk) , k=0,1,2, (4.3) 这种求方程根的方法称为简单迭代法简单迭代法,或逐逐次逼近法次逼近法.其中(x) 称为迭代函数迭代函数 ,式(4.3)称为迭代格式迭代格

6、式. 若迭代序列xk 收敛 , 则称简单迭代法是收敛的简单迭代法是收敛的. 解解 改写原方程为等价方程 求方程x3-2x-3=0在1,2内的根.例例2 332 xx , ,建立迭代格式3123,0,1,2.kkxxk如果取初值x0=1.9 ,计算得kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.893289201.89328920 由计算结果有，x10=x9，因此可取x10=1.89328920. 定义定义4.14.1 设(x)为定义在区

7、间I I上的函数, 且对任何xI I,均有(x)I I,则称(x)为I I到自身上的映射到自身上的映射. 方程也可改写成x=(x3-3)/2, 建立迭代格式 xk+1=(x3k-3)/2 , k=0,1,2, 仍取初值x0=1.9, 则有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529可见,xk,此迭代格式是发散的.2.2 简单迭代法的收敛条件简单迭代法的收敛条件 定义定义4.24.2 设(x)为I I到自身上的映射,且存在0L1,使对任何x1,x2I,I,有|(x2)-(x1)| L|x2-x1|,则称(x)为I I上的压缩映射压缩映射, L称为Lip

8、schitzLipschitz常数常数. 若(x)为I上的压缩映射,则(x)在I上连续. 定理定理4.24.2 若(x)为I到自身上的映射,且(x)C1(I), |(x)| L1,则(x)为I上的压缩映射. 证证 对任意x1,x2I,有 |(x2)-(x1)|=|()|x2-x1| L|x2-x1| 定义定义4.34.3 若(x)为I到自身上的映射,且I I满足,= (),则称为(x)的不动点不动点. . 定理定理4.34.3 若(x)为I上的压缩映射, 则(x)在I I上存在唯一的一个不动点,且对任何x0I,由迭代格式 xk+1=(xk) , k=0,1,2,产生的序列xk收敛于(x)的不动

9、点.定理定理4.1 证证 不妨设I=a,b,作函数(x)=(x)-x,由于xI时, (x)I,则(a)=(a)-a0,(b)=(b)-b0,由(x)的连续性, 必存在I, 使()=()-=0,即=(),就是(x)的不动点. 若,I均为(x)的不动点,则有 |-|=|()-()| L|-|-|所以只能=,即(x)在I上仅有一个不动点. 对任意x0I,有x1=(x0)I,递推得xkI,设是(x)的不动点,则 |xk+1-|=|(xk)-()| L|xk-| L2|xk-1-| Lk+1|x0-|所以xk. 若=(),而在I=-,+上(x)满足 |(x)-()| L|x-|这里L1为Lipschit

10、z常数,则当x0-,+时,有 (1) 由迭代xk+1=(xk)产生的迭代序列xkI; 推论推论 若(x)C1a,b,且满足 1.a(x)b, xa,b; 2.|(x)| L0, 使对任何xI=-, +都有|(x)| L1. 2.3 简单迭代法的误差分析与收敛阶简单迭代法的误差分析与收敛阶 推论推论 若=(),(x)在附近具有一阶连续导数,且|()|0, 当x0I=-, +时, 有 (1) 由迭代xk+1=(xk)产生的迭代序列xkI;lim)2(kkx (3) 是I上(x)的唯一不动点. 定理定理4.54.5 若(x)为I上压缩映射,则x0I,由迭代 xk+1=(xk) , k=0,1,2,

11、产生的迭代序列xk满足: 证证 |xk+1-xk|=|(xk)-(xk-1)| L|xk-xk-1| |xk+1-|=|(xk)-()| L|xk-|11kkkxxLLx011xxLLxkk |xk+1-xk|=|(xk+1-)-(xk-)| |xk-|-|xk+1-|(1-L)|xk-|01111.111xxLLxxLLxxLxkkkkkk 由误差估计式可见,对任一0,要使|xk-|, 只要LxxLkln)1 (ln01 求方程xex-1=0在0.5附近的根,精度要求=10-3. 解解 可以验证方程xex-1=0在区间0.5,0.6内仅有一个根.例例3 改写方程为x=e-x ,建立迭代格式,

12、 2 , 1 , 0,1kexkxk 由于(x)=e-x ,在0.5,0.6上有|(x)|e-0.50.61则称序列xk是p p阶收敛的阶收敛的, 称p是收敛阶收敛阶,C是渐近误差常渐近误差常数数. p=1称为线性收敛线性收敛;p1称超线性收敛超线性收敛;p=2称平方收敛平方收敛. 设(x)充分光滑, 由于 |ek+1|=|xk+1-|=|(xk)-()|=|(k)|ek|所以,当()0时,有0| )(|)(limlim1kkkkkee于是此时,迭代法是m阶收敛的.所以,当()0时,简单迭代法只具有线性收敛. 设()=()=(m-1)()=0,但(m)()0, 由于 |ek+1|=|xk+1-

13、|=|(xk)-()|mkkmem)(!1)(0| )(|!1)(!1limlim)()(1mkmkmkkkmmee所以mkkmmkmkkkxmxmxxx)(!1)()!1(1)(21)()()()(1)1(2 下面介绍AitkenAitken加速算法加速算法，此方法可对线性收敛的简单迭代法起到加速作用，而且可应用于其它数值方法中。假设 (1)(2)，则有 由于 xk+1-=(1)(xk-) xk+2-=(2)(xk+1-)121kkkkxxxx即 (xk+1-)2(xk-)(xk+2-) xk+12-2xk+1+2xkxk+2-(xk+xk+2)+2 解得 kkkkkkxxxxxx12212

14、2kkkkkkxxxxxx12212)(则,序列注意, 如果第k步发生zk-2yk+xk=0, 就终止计算, 取xk .如果记 kkkkkkkxxxxxxx12212)( kx 要比序列x k更快地收敛于 , 可构造如下的Aitken加速算法:, 2 , 1 , 0,2)(21kxyzxyxxkkkkkkk)(kkxy)(kkyz例例4 分别用简单迭代法和Aitken加速算法求方程x=1.6+0.99cosx在x0=/2附近的根.(=1.585471802)取x0= /2,计算结果如下k简单迭代法kAitken算法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.5

15、71091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078 NewtonNewton迭代法迭代法是求方程根的重要方法之一,其最大优点是在方程的单根附近具有平方收敛,而且Newton迭代法还可用来求方程的重根、复根及非线性方程组.3 Newton 迭代法迭代法 3.1 Newton迭代公式迭代公式 设(x)在有根区间a,b上二阶连续可微, x0是根的某个近似值, 因为200000)(2)()()()(xxfxxxfxfxf 取(x)(x0)+(x0)(x-x0)

16、,方程(x)=0近似为 (x0)+(x0)(x-x0)=0若(x0)0, 其解为)()(0001xfxfxx得到根的新的近似值x1 ,一般地,在xk附近线性化方程为 (xk)+(xk)(x-xk)=0设(xk)0, 其解为)4 . 4(, 2 , 1 , 0,)()(1kxfxfxxkkkk迭代格式(4.4)称为 NewtonNewton迭代法迭代法. . xyox0y=(x)x1x2直线 y=(x0)+(x0)(x-x0)就是 y-(x0)=(x0)(x-x0)Newton迭代法也叫切线法切线法. Newton迭代法相当于取迭代函数3.2 Newton迭代法的收敛性迭代法的收敛性)()()(

17、xfxfxx的简单迭代法. 因为222)()()()()()()(1)(xfxfxfxfxfxfxfx 如果是(x)=0的单根, 即()=0, 但()0, 则有()=0, 从而可知Newton迭代法在根附近是收敛的.因为2)(2)()()()(kkkkxxfxxxfxfxf 所以2)(2)()()()(kkkkkxfxxfxff 于是有2)()(2)()()(kkkkkkxxffxfxfx 21)()(2)(kkkkxxffx 21)(limkkkxx)(2)(limkkkxff )(2)(ff 可见, Newton迭代法至少是平方收敛的. 若记其中(212mMC M2=max|(x)|,m1

18、=min|(x)|. 则有 |xk+1-| C|xk-|2因此 C|xk+1-| (C|xk-|)2 (C|xk-1-|)4 )1(20|)|(kxC可见,当C|x0-|1, 即|x0-|1/2max|(x)|时,简化Newton迭代法对x0I收敛.通常取M=(x0). 简化Newton迭代法一般只具有线性收敛. 2. 2.割线法割线法 因为, 2 , 1 , 0,)()()(11kxxxfxfxfkkkkkoxyy=(x)x0 x1x2x3 为了简化计算(xk),采用迭代格式, 3 , 2 , 1,)()()()(111kxxxfxfxfxxkkkkkkk称为割线割线法法. . 若(x)在根

19、附近二次连续可微,且()0,可以证明割线法是收敛的,且有)(2)(lim11ffeeekkkk 割线法收敛的阶为.618. 1251p 3. 3.计算重根的计算重根的NewtonNewton迭代法迭代法 称是方程(x)=0的m重根,是指(x)=(x-)m h(x),其中h(x)在x=处连续且h()0, 若h(x)在处充分可微,则 ()=()=(m-1)()=0,(m)()0由于mmxhxxf11)()()(可见,恰是方程0)(1mxf 的单根.应用Newton迭代法可得:)()(1)(1111kmkmkkkxfxfmxfxx, 2 , 1 , 0,)()(kxfxfmxkkk称之为带参数带参数m m的的NewtonNewton迭代法迭代法, 它是求方程(x)=0的m重根的具有平方收敛的迭代法. 再看函数:( )() ( )( )() ( )( )( ) () ( )f xxh xu xxh xf xmh xxh x可见,恰是方程u(x)=0的单根, 应用Newton迭代法有)()(1kkkkxuxuxx这是求方程(x)=0