数值分析迭代法

1、1第二节第二节 迭代法迭代法2 2009, Henan Polytechnic University2 它是一种逐次逼近的方法它是一种逐次逼近的方法, ,用某个固定公式反用某个固定公式反复校正根的近似值复校正根的近似值, ,使之逐步精确化，最后得到满足使之逐步精确化，最后得到满足精度要求的结果。精度要求的结果。3 2009, Henan Polytechnic University36.2.1 迭代法的基本思想迭代法的基本思想 为求解非线性方程为求解非线性方程f(x)=0的根，先将其写成便于的根，先将其写成便于迭代的等价方程迭代的等价方程)(x )(xx 其中其中 为为x的连续函数的连续函数。

2、4 2009, Henan Polytechnic University4 即如果数即如果数 使使 f(x)=0, , 0 x)(xx )(01xx 任取一个初值任取一个初值 , ,代入式代入式 的的右端右端, , 得到得到则也有则也有反之反之, , 若若 ,则也有则也有再将再将 代入式代入式 的右端的右端, , 1x)(xx 得到得到 )(12xx 0)( f)( )( 5 2009, Henan Polytechnic University5),(),(3423xxxx 上式称为求解非线性方程的简单迭代公式上式称为求解非线性方程的简单迭代公式, , 依此类推依此类推, , 得到一个数列得到

3、一个数列其一般表示其一般表示 )(x 称称 为迭代函数为迭代函数 。), 2 , 1 , 0(),(1 nxxnn 6 2009, Henan Polytechnic University6 例例1 1 试用迭代法求方程试用迭代法求方程 在区间在区间(1，2)内的实根。内的实根。31 xx01)(3 xxxf311 kkxx解：由解：由 建立迭代关系建立迭代关系计算结果如下计算结果如下: :k=0,1,2,3.7 2009, Henan Polytechnic University7精确到小数点后五位精确到小数点后五位kk01.551.3247611.3572161.3247321.33086

4、71.3247231.3258881.3247241.324945102132472. 1 xkxkx8 2009, Henan Polytechnic University8但如果由但如果由 建立迭代公式建立迭代公式13 xx,.2 , 1131 kxxkk 5 . 10 x 2.3751 x 12.392 x kx仍取仍取 ，则有，则有显然结果越来越大，显然结果越来越大， 是发散序列是发散序列9 2009, Henan Polytechnic University9（全局收敛定理）（全局收敛定理）,)(bax 在在设设 为为常常数数）LLxbax(1| )( |,)2( 0111011|3

5、(,)2( ,)()1(xxLLxxLLxxxbaxbaxxnnnnnn ）（）收收敛敛到到；有有唯唯一一根根在在方方程程则则：;)(1bxabxa 时时，）当当（6.2.2 收敛性分析收敛性分析10 2009, Henan Polytechnic University10存在唯一性存在唯一性做辅助函数做辅助函数)()(xxx ，则有，则有0)(, 0)( ba 所以，存在点所以，存在点*)(*0*)(.,.*,xxxtsx 若若*)*(*xx ，则有：则有：*xx 又，又，1 L*xx *)*(*)(xx *)*)( xx *xxL 11 2009, Henan Polytechnic Un

6、iversity11,0bax 则则*1xxk *1xxk 所以，任意的初值都收敛所以，任意的初值都收敛*)()(xxk *)( xxk *12xxLk *xxLk *01xxLk 12 2009, Henan Polytechnic University12误差估计误差估计nnxx 1)()(1 nnxx 212 nnxxL1 nnxxL01xxLn nnxx 1)()(1 nnxx 1nnxx nnxLx nxL)1(13 2009, Henan Polytechnic University13nnnxxLx 111 注：注：L越小，收敛越快。越小，收敛越快。11 nnxxLL011xxL

7、Ln 14 2009, Henan Polytechnic University14例例2 2 证明函数证明函数 在区间在区间11，22上满足迭代收敛条件。上满足迭代收敛条件。31)( xx 上上严严格格单单调调增增函函数数。是是区区间间所所以以因因为为,)(2 , 1 0)1(31)(32baxxxx 证明：证明：15 2009, Henan Polytechnic University15 2 , 11431|)1(31| )(|332 xLxx 又又23)2(12)1(33 ，而而）。满满足足条条件件（，所所以以即即1)(2 , 1)2(),1(x ）。满满足足条条件件（所所以以2)(x

8、 满满足足收收敛敛条条件件。在在故故2 , 11)x(3 x 16 2009, Henan Polytechnic University16若取迭代函数若取迭代函数 不满足定理，故不能肯定不满足定理，故不能肯定 收敛到方程的根。收敛到方程的根。 1)x(3 x 2 , 13|3| )(|2 xxx 因因为为,.1 , 0)(1 nxxnn 17 2009, Henan Polytechnic University17 定理定理 设设 是方程是方程 的根，如果满足的根，如果满足条件条件 ：（1 1）迭代函数）迭代函数 在在 的邻域可导；的邻域可导；（2 2）在）在 的某个邻域的某个邻域 ，对于任

9、，对于任意意 ，有，有 )(xx 局部收敛性局部收敛性 )(x Sx xxS1)( Lx 18 2009, Henan Polytechnic University18 则对于任意的初始值则对于任意的初始值 ，由迭代公式，由迭代公式 产生的数列产生的数列 收敛于方程的根。收敛于方程的根。（这时称迭代法在（这时称迭代法在 的的S S邻域具有局部收敛性。）邻域具有局部收敛性。） nx)(1nnxx Sx 0 19 2009, Henan Polytechnic University19例例3 3 设设 ，要使迭代过程，要使迭代过程 局部收敛到局部收敛到 , ,求求 的取值范围。的取值范围。解：解：

10、 由在根由在根 邻域具有局部收敛性时，邻域具有局部收敛性时， 收敛条件收敛条件 )5()(2 xaxx )(1kkxx 5* xa)5()(2 xaxx axx21)( 5* x20 2009, Henan Polytechnic University201521)(* ax 15211 a0522 a所以所以 051 a21 2009, Henan Polytechnic University21 实际计算中当然不可能也没必要无穷多步地做实际计算中当然不可能也没必要无穷多步地做下去下去, , 对预先给定的精度要求对预先给定的精度要求，只要某个，只要某个n满足满足即可结束计算并取即可结束计算并

11、取 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。)( x 1nnxxnx 22 2009, Henan Polytechnic University22xyy = xx*y=g(x)x0p0 x1p1 xyy = xx*y=g(x)x0p0 x1p1简单迭代收敛情况的几何解释简单迭代收敛情况的几何解释23 2009, Henan Polytechnic University23定义定义 设迭代过程设迭代过程 收敛于收敛于 的的根根 , ,记迭代误差记迭代误差若存在常数若存在常数p（p1）和和c（c0），），使使 )(1kkxx )(xx *xkkxxe *ce

12、epkkk 1lim则称序列则称序列 是是 p 阶收敛的阶收敛的, ,c称渐近误差常数。特别称渐近误差常数。特别地地, ,p=1时称为线性收敛时称为线性收敛, ,p=2时称为平方收敛。时称为平方收敛。1 p 2时称为超线性收敛。时称为超线性收敛。 kx6.2.3 迭代法的收敛速度迭代法的收敛速度24 2009, Henan Polytechnic University24 数数p的大小反映了迭代法收敛的速度的慢，的大小反映了迭代法收敛的速度的慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。对迭代法收敛速度的一种度量。 25

13、2009, Henan Polytechnic University25定理定理 设迭代过程设迭代过程 , ,若若 在所求根在所求根 的邻域连续且的邻域连续且 则迭代过程在则迭代过程在 邻域是邻域是p阶收敛的。阶收敛的。)(1kkxx )()(xp *x0)(, 0)()()(*)(*)1(* xxxxpp *x0)(* x *x1)(* x )(1kkxx )(kx *x证证: : 由于由于所以所以 有局部收敛性有局部收敛性, , 将将 在在 处处泰勒展开泰勒展开即在即在 邻域邻域 , ,26 2009, Henan Polytechnic University26pkpkkkxxpxxxx

14、xxxx)(!1)(! 21)()()(*)(2* 根据已知条件得根据已知条件得 pkpkxxpxx)(!1)()(*)(* 由迭代公式由迭代公式 )(1kkxx 及及)(*xx 有有pkpkxxpxx)(!)(*)(*1 0!)(lim*)(1 pxeeppkkk 27 2009, Henan Polytechnic University27例例4 4 已知迭代公式已知迭代公式 收敛于收敛于证明该迭代公式平方收敛。证明该迭代公式平方收敛。21132kkkxxx 3*3 x2132)(xxx 436)(232)(xxxx ，证证: : 迭代公式相应的迭代函数为迭代公式相应的迭代函数为将将 代入

15、，代入，根据定理可知，迭代公式平方收敛。根据定理可知，迭代公式平方收敛。3*3 x032336)(0)(33* xx ，28 2009, Henan Polytechnic University28为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度, , 可设法可设法 提高初值的精度以减少迭代的次数提高初值的精度以减少迭代的次数 提高收敛的阶数提高收敛的阶数 p29 2009, Henan Polytechnic University29（1 1）迭代）迭代- -加速公式（加权法）加速公式（加权法）设设 是根是根 的某个近似值的某个近似值, ,用迭代公式校正一次得用迭代公式校

16、正一次得 kx*x)(1kkxx )(*xx )()()(*1*kkkxxxxxx ),(*kxx 6.2.4 迭代过程的加速迭代过程的加速又又根据中值定理有根据中值定理有30 2009, Henan Polytechnic University30可见可见, ,若将迭代值若将迭代值 与与 加权平均加权平均, ,则可得到的则可得到的 1 kxkxkkkxLLxLx 11111是比是比 更好的近似根更好的近似根1 kx)(*1*kkxxLxx kkxLLxLx 1111*则有：则有：当当 范围不大时范围不大时, ,设设 变化不大变化不大, ,其估计值为其估计值为L L )(*kxx )( 31

17、2009, Henan Polytechnic University31迭代：迭代： 改进：改进： 或合并写成：或合并写成： )(1_kkxx kkkxLLxLx 1111_1 kkkLxxLx )(111 32 2009, Henan Polytechnic University32例例5 5 用加权法加速技术求方程用加权法加速技术求方程 在在0.50.5附近的一个根。附近的一个根。xex 5 . 00 x 6 . 05 . 05 . 05 . 0 eexx 取取L=-0.6=-0.6，建立如下迭代公式建立如下迭代公式解：解： 因为在因为在 附近附近33 2009, Henan Polyte

18、chnic University33仍取仍取 , ,逐次计算得逐次计算得 =0.56658 =0.56714 。迭代迭代4 4次便可得到精度次便可得到精度 的的结果结果, ,而不用加速技术需迭代而不用加速技术需迭代1818次次, ,效果显著。效果显著。 5 . 00 x1x4x410 kxkxkxexexkk6 . 06 . 116 . 0)6 . 0(111 34 2009, Henan Polytechnic University34（2 2）埃特金）埃特金（Aitken）方法方法 在加权法中在加权法中, , 估计估计L L的值有时不太方便。假的值有时不太方便。假设在求得设在求得 以后以后, , 先求出先求出kx)(1kkxx )(*xx )()()(*1xxLxxxxkkk 由由 利用中值定理可得利用中值定理可得( ( 在求根区间变化不大在求根区间变化不大,