### Paper Menu >>

### Journal Menu >>

Self-accelerating two-step Steffensen-type methods with memory and their applications on the solution of nonlinear BVPs Quan Zheng, Xiuhui Guo, Fengxi Huang College of Sciences, North China University of Technology, Beijing 100144, China zhengq@ncut.edu.cn (Q. Zheng) Abstract—In this paper, seven self-accelerating iterative methods with memory are derived from an optimal two-step Steffensen-type method without memory for solving nonlinear equations, their orders of convergence are proved to be increased from 4 to 26 , (517) / 2 ,5 and (533) / 2 , numerical examples are demonstrat-ed demonstrated to verify the theoretical results, and applications for solving systems of nonlinear equations and BVPs of nonlinear ODEs are illustrated. Keywords-Nonlinear equation; Newton's method; Steffensen-type method; Derivative free; Super convergence 1. Introduction Considering iterative methods to solve a nonlinear equation () 0fx , the most famous method is Newton’s method (NM, see [1]): 1 () ,1, 2,..., () n nn n fn f x xx x c (1) where 0 x is an initial guess of the root. If the derivative () n fx c is replaced by the divided difference (())() () [, ()] fx fxfx nn n fx n fx xfx nn n , Newton's method becomes Steffensen’s method (SM, see [1]). Steffensen’s method is a tough competitor of Newton’s method since it is derivative free. Because Kung and Traub conjectured in 1974 that a multipoint iteration based on m evaluations with- out memory has optimal order 1 2m of convergence (see [2]), NM and SM are one-step methods of optimal order without memory. The efficiency index of them is 2 1.4142 . Further, a parametric Steffensen’s method (PSM) was suggested in Section 8.4 in [3]: 1 () ,0,1, 2,... [, ()] n nn nnnn fx xx n fx xfx E (2) convergent with the asymptotic convergence constant (1( ))( ) 2() fa f a n fa E ccc c . If 1 () , nfa E | c PSM can have smaller error. Therefore, by defining 1111 1/ [,()] nnnnn fx xfx EE at the previous iteration recursively as the iteration proceeds, a self-accelerating Steffensen’s method (SASM) was proposed in Section 8.6 in [3]: 1 () [, ()] 1 [,] 11 , , nn n fx n fx xfx nnn n fx z nn xx E E ° ° ® ° ° ¯ (3) where 00 (())sign fx E c , or 00 0 1/ [ ,( )]fx xfx , etc. SASM is a derivative-free one-step method with memory. It only uses two new evaluations of the function per step to achieve convergence of order 2 1 2.4142| , and has efficiency index 2 1 1.5538| . Some other optimal multipoint Steffensen-type methods without memory were derived in [4-7]. General optimal derivative-free iterative methods for solving nonlinear equations were introduced in [2] and [7]. Two-step self- accelerating Steffensen-type methods were investigated in [8- 10]. Steffensen-type methods and their applications in the solution of non-linear systems and nonlinear differential equa- tions were discussed in the literature (see [1, 3, 4, 8, 9]). This work suggests seven self-accelerating iterative methods with memory for solving nonlinear equations in section 2, proves their high orders of super convergence in section 3, demonstrates examples and applications in section 4, and makes conclusions in section 5. 2. The self-accelerating methods By using second-order Newtonian interpolation 2()Nx after an iteration of SM to approximate ()fx and find the root of 2 () 0Nx to approximate the exact root, we obtain a parametric Steffensen-type method (PSTM): 1 () [,] () [, ][,][,] , . nn nn fx n fx z nn fy n fx yfy zfxz nnnnnn yx xy ° ° ® ° ° ¯ (4) where () nnnn zx fx E . PSTM is an optimal two-step meth-od without memory (see [5, 7]). Supported by Beijing Natural Science Foundation (No. 1122014). Open Journal of Applied Sciences Supplement：2012 world Congress on Engineering and Technology 70 Cop y ri g ht © 2012 SciRes. Theorem 2.1 (see [7]) Let :fD Ro be a sufficiently different- iable function with a simple root ,aDDR be an open set, 0 x be close enough to a , then the method (4) is at least of fourth-order, and satisfies the error equation 22 4 5 1223 (1( ))[]() nn nn efaccceOe E c , (5) where () () !() ,,0,1, 2,... k knn fa kfa cexan c From PSTM and its error equation, in order to achieve super fourth-order convergence, the free parameters n E should tend to 1/( )fa c .Therefore, we propose six self-accelerating Steffensen-type methods (SASTMs) with memory as follows: compute (4) with 1 11 1 () [,] nn nn ifx z EE { (SASTM1) (6) 2 11 1 () [, ] nn nn ii fx y EE { (SASTM2) (7) 3 11 1 () [,] nn nn iii fy z EE { (SASTM3) (8) 4 1 1 () [,] nn nn iv fxx EE { (SASTM4) (9) 5 1 1 () [,] nn nn vfz x EE { (SASTM5) (10) 6 1 1 () [,] nn nn vi fy x EE { (SASTM6) (11) By Newton’s interpolation formula on points n x , 1n y and 1n x as Follows: 1111 ()( )[ ,]()[ ,,]()() nnnnnnnnn Nxfxfx yxxfx yxxxxy using 1/( ) nn Nx E c we propose the seventh self-accelerating Steffensen-type methods: compute (4) with 7 1111 1 () [,][, ][, ] nn nnnnnn vii fx yfxxfyx EE { . (SASTM7) (12) 3. The convergence Theorem 3.1. Let :fD Ro be sufficiently differentiable near a simple root ,aDDR be an open set, 0 x be close enough to a , then SASTM1, SASTM2 and SASTM4 achieve the convergence of order 26 , SASTM3 and SASTM5 achieve the convergence of order (517) / 2 ,SASTM6 achieves fifth- order convergence, and SASTM7 achieves the convergence of order (533) / 2 . Proof. Using Taylor formula and denoting z nn eza and y nn eya , for SASTM1, we have (1())() z nnnn efaeoe E c , () [,] ()(2())() 2 nnnnn fa fxzfaf aeoe E cc cc . Hence, 11 121 1 1[1(2())]() () nnnn face oe fa EE c c . By substituting it into Eq. (5), we obtain 12324224 1122311 (2( ))[]() nn nnnn efaccceeoee E c . For SASTM2, we have 22 2 (1( ))() y nn nn efaceoe E c , () 1() 2 [, ]() nnn n o fafx yfaee cc c , 2 21 1 1 () [1]() nnn fa ce oe E c . By substituting 2 n E into Eq. (5), we obtain 32 4224 1223 11 [] () nnnnn eccceeoee . For SASTM4, we have 111 () 1() 2 [,] () nnn n o fafxxfaee cc c , and obtain the same error equation as the above. By solving 2 42rr , the convergence of order 26 4.4495| is proved for SASTM1, 2 and 4. For SASTM3 and 5, if n z converges to a with order p and n x Converges to a with order r as: () zpp nnn n eCeoe and 1 () rr nnnn eDeoe , then 111 () zp rprp nnnnn eCDeoe , 22 1111 () rrr nnnn n eDDeoe . So, we have 1 [,][,,] , [,] [,] [,] [, ][, ,]() yz nn nn nn nn nn nn y ynn nn nnnnn nn fx aefxza ee ee fx zfx z fyae ee fx yfx yzyx Cop y ri g ht © 2012 SciRes.71 2 [,,] [,] [, ,][, ,]() [, ][, ,]() [, ,][,,,] [, ][, ,]() [,,] [,] [, ,][, ,,] [ () y n y n z nn fx z a nn fx z nn y fx yafx y zee nnnnn nn y fx yfx y zee nnnnn nn yz fx y zefx y zaee nnnnnnn nn y fx yfx y zee nnnnn nn fx z a nn fx z nn fx yz fxyza nnn nnn f e e ee u ,] [,,]() . y xyfxyz ee nnnnn nn For SASTM3, 21 1 21111 [,][,] 11 [,] 11 () (), z nn zz nn nn pr pr nnn n fyzfx a n nn fyz nn ee ce eoe e cCD eoe 2222 24 122111 231 3224 2424 2231111 ()()() () (). pr pr nnnn n pr pr nnn n eccCDeccoe cc cCDeoe For SASTM5, we have the same results 21111 () zprpr nnnn n ecCDeoe , 3224 2424 1223111 1 () () pr pr nnnnn ecccCDe oe . Comparing the exponents of 1n e in the expression of z n e and 1n e respectively, we have respectively, we have 2 , 24. rpp r rpr ® ¯ From its non-trivial solution (117 )/ 2p and (517) / 2,r we prove that SASTM3 and 5 achieve the same convergence of order (517)/ 24.5616| . For SASTM6 and 7, if () ypp nnnn eCeoe and 1() rr nnnn eDeoe , then 22 11 1 1111 (), (). yp rprp nnnnn rr r nnnn n eCDe oe eDDeoe So, for SASTM6, 21111 222 2 2111 1 (), (), zprpr nnnnn yprpr nnnn n ecCDe oe ecCDe oe 3224 2424 1223111 1 () (), pr pr nnnnn ecccCDe oe and establish 2 2, 24. rp pr rpr ® ¯ From its non-trivial solution 5/2p and 5,r we prove that SASTM6 achieves fifth-order convergence. For SASTM7, we have 11111 1111 1111 11 1111 11 3111 1 [, ,][, ,]() [,][, ][, ] [, ,][, ,,] [,][, ][, ] (), yy znnnnn nn n n n nnnnn n y nn nnnnnnn n nnnnn n pr pr nnnn fx yaefx yxee ee fxyfxxfyx fx yxefx yxaeee fxyfxxfyx cCD eoe e 22121 231111 222 4242242 12323 1111 (), () (), yprpr nnnnn pr pr nnnnn ccCD eoe eccccCDe oe and establish 2 21, 242. rp pr rpr ® ¯ From its non-trivial solution (533) / 4p and (533) / 25.3723r | , we prove that SASTM7 achieves the convergence of order (533) / 2 . Each of SASTMs is a two-step derivative-free method with memory and only uses three new evaluations of the function per step to achieve super fourth-order convergence. SASTM1, 2 and 4 have the same efficiency index 3261.6448| . SASTM3 and 5 have the same efficiency index 3(517) / 21.6585| . SASTM 6 and 7 have the efficiency indices 3 5 1.7100| and 3(533)/ 21.7514,| respectively. Whereas, two self-accelerating methods proposed -- uses three new evaluations of the function per iteration to achieve the super fourth-order convergence of order 26 and its efficiency index is only 3 261.6448| . 4. Numerical examples In the examples,NM,SM,PSM,SASM, PSTM and SASTMs are compared with each other. The computational order of convergence is defined as: 1 12 log(|| / ||). log(|| / ||) nn nn ee COC ee where 0 1, 1,2,...,7. i i E Example 1. Numerical results in Table I agree with theoretical results in the theorems. TABLE I. 2 0 ( )31,0,0.2 x fxx exax Method n 1 2 3 4 NM || n e COC .533e-2 .356e-5 .158e-11 .312e-24 2.01691 2.00030 2.00000 SM || n e COC .282e-1 .513e-3 .165e-6 .170e-13 2.04367 2.00830 2.00009 72 Cop y ri g ht © 2012 SciRes. PSM (1) n E { || n e COC .134e-1 .677e-4 .172e-8 .111e-17 1.95757 2.00059 2.00000 SASM || n e COC .282e-1 .160e-4 .131e-12 .433e-32 3.81335 2.49109 2.40945 PSTM (1) n E { || n e COC .468e-4 .389e-18 .186e-74 .977e-300 3.87748 4.00000 4.00000 PSTM (1) n E { || n e COC .595e-4 .366e-18 .525e-75 .222e-302 4.02926 4.00000 4.00000 SASTM1 || n e COC .468e-4 .414e-21 .441e-98 .331e-440 4.69620 4.51372 4.44480 SASTM2 || n e COC .468e-4 .135e-22 .371e-104 .175e-467 5.10548 4.39945 4.45460 SASTM3 || n e COC .468e-4 .317e-21 .228e-100 .956e-462 4.72820 4.60962 4.56612 SASTM4 || n e COC .468e-4 .104e-22 .132e-104 .166e-469 5.13642 4.39102 4.45547 SASTM5 || n e COC .468e-4 .302e-21 .180e-100 .324e-462 4.73383 4.60889 4.56606 SASTM6 || n e COC .468e-4 .195e-24 .691e-127 .384e-639 5.61230 5.02717 5.00000 SASTM7 || n e COC .468e-4 .810e-27 .207e-148 .679e-802 6.26819 5.34210 5.37438 Example 2. Consider to solve a boundary-value problem of ODEs as the following: 2 1 1 2 1, (0)1, (1)(). yy yyee cc c ° ® ° ¯ Let 4N and use the methods to solve the nonlinear system () 0Fs G with 00s G by the multiple shooting method (see [4, 9]). The numerical results are showed in Table II. TABLE II. FOR THE MULTIPLE SHOOTING METHOD Method n 1 2 3 4 SM ||() || n Fs G || || n yy || || n yy cc .560e-1 .149e-3 .994e-10 .203e-21 .283e-1 .584e-4 .326e-5 .326e-5 .585e-1 .143e-3 .459e-5 .458e-5 PSTM ||() || n Fs G || || n yy || || n yy cc .271e-3 .124e-17 .219e-76 .336e-311 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .459e-5 .459e-5 .458e-5 SASTM1 ||() || n Fs G || || n yy || || n yy cc .271e-3 .154e-4 .280e-9 .301e-15 .142e-3 .230e-5 .326e-5 .326e-5 .346e-3 .129e-4 .458e-5 .458e-5 SASTM2 ||() || n Fs G || || n yy || || n yy cc .271e-3 .135e-21 .289e-99 .118e-446 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .459e-5 .459e-5 .458e-5 SASTM3 ||() || n Fs G || || n yy || || n yy cc .271e-3 .764e-20 .236e-95 .121e-439 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .459e-5 .459e-5 .458e-5 SASTM4 ||() || n Fs G || || n yy || || n yy cc .271e-3 .446e-22 .131e-102 .711e-462 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .459e-5 .459e-5 .458e-5 SASTM5 ||() || n Fs G || || n yy || || n yy cc .271e-3 .996e-20 .897e-95 .564e-437 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .459e-5 .459e-5 .458e-5 SASTM6 ||()|| n Fs G || || n yy || || n yy cc .271e-3 .135e-21 .289e-99 .118e-446 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .459e-5 .459e-5 .458e-5 SASTM7 ||() || n Fs G || || n yy || || n yy cc .271e-3 .446e-22 .131e-102 .711e-462 .142e-3 .326e-5 .326e-5 .326e-5 .346e-3 .458e-5 .458e-5 .458e-5 5. Conclusions In this work, we derive seven self-accelerating Steffensen- type methods with memory for solving nonlinear equations and establish the comparative advantage of high efficiency theoretically and numerically. The suggested self-accelerating methods without derivative are convenient to be applied in the multiple shooting method for solving boundary-value problems of nonlinear ODEs, where derivatives are difficult to be obtained. REFERENCES [1] J.M. Ortega, W.G. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. [2] H.T. Kung, J.F. Traub, Optimal order of one-point and multipoint iteration, J. Assoc. Comput. Math. 21 (1974) 634-651. [3] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1964. [4] -fensen’s type method in Banach spaces with applications on boundary- value problems, J. Comput. Appl. Math. 216 (2008) 243-250. [5] W. Bi, H. Ren, Q. Wu, A class of two-step Steffensen type methods with fourth-order convergence, Appl. Math. Comput. 209 (2009) 206-210. [6] F. Soleymani, S.K. Vanani, Optimal Steffensen-type meth-ods with eighth order of convergence, Comput. Math. Appl. 62 (2011) 4619-4626. [7] Q. Zheng, J. Li, F. Huang, An optimal Steffensen-type family for solving nonlinear equations, Appl. Math. Comput. 217 (2011) 9592-9597. [8] Q. Zheng, J. Wang, P. Zhao, L. Zhang, A Steffensen-like method and its higher-order variants, Appl. Math. Comput. 214 (2009) 10-16. [9] Q. Zheng, P. Zhao, L. Zhang, W. Ma, Variants of Steffensen- secant method and applications, Appl. Math. Comput. 216 (2010) 3486-3496. [10] -point methods with and without memory for solving nonlinear equations, Appl. Math. Comput. 217 (2010) 1887-1895. Cop y ri g ht © 2012 SciRes.73 |