 Applied Mathematics, 2011, 2, 816-823 doi:10.4236/am.2011.27109 Published Online July 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM Improved Ostrowski-Like Methods Based on Cubic Curve Interpolation Janak Raj Sharma1, Rangan Kumar Guha1, Rajni Sharma2 1Department of Mat hem at i cs, Sant Longowal Institute of Engineering and Technology, Longowal, India 2Department of Appli e d Sci en ces , D.A.V. Institute of Engineering and Techno logy Kabirnagar, Jalandhar, India E-mail: jrshira@yahoo.co.in, rangankguha@yahoo.com, rajni_gandher@yahoo.co.in Received December15, 2010; revised May 10, 2011; accepted May 13, 2011 Abstract In this paper, we derive two higher order multipoint methods for solving nonlinear equations. The method-ology is based on Ostrowski’s method and further developed by using cubic interpolation process. The adap-tation of this strategy increases the order of Ostrowski’s method from four to eight and its efficiency index from 1.587 to 1.682. The methods are compared with closest competitors in a series of numerical examples. Moreover, theoretical order of convergence is verified on the examples. Keywords: Nonlinear Equations, Ostrowski’s Method, Root-Finding, Order of Convergence, Cubic Interpolation1. Introduction Finding the root of a non-linear equation () 0fx is a common and important problem in science and engi-neering. Analytic methods for solving such equations are almost non-existent and therefore, it is only possible to obtain approximate solutions by relying on numerical methods based on iteration procedures. Traub  has classified numerical methods into two categories viz. 1) one-point iteration methods with and without memory, and 2) multipoint iteration methods with and without memory. Two important aspects related to these classes of methods are order of convergence and computational efficiency. Order of convergence shows the speed with which a given sequence of iterates converges to the root while the computational efficiency concerns with the economy of the entire process. Investigation of one – point iteration methods with and without memory, has demonstrated theoretical restrictions on the order and efficiency of these two classes of methods (see ). However, Kung and Traub  have conjectured that multipoint iteration methods without memory based on evaluations have optimal order . In particular, with three evaluations a method of fourth order can be constructed. The well-known Ostrowski’s method  is an example of fourth order multipoint methods without memory which is defined as n12n,iii ifxwxfx   1,2iiii ii ifw fxxwfxfx fw (1) where 0,1,2,i and 0x is the initial approximation sufficiently close to the required root. The method re-quires two function f and one derivative f evalua-tions per step and is seen to be efficient than classical Newton’s method. Recently, based on Ostrowski’s method (1) Grau and Díaz-Barrero  have developed a sixth order method requiring four evaluations, namely three f and one f per iteration. Sharma and Guha  have shown that there exists a family of such sixth order methods with equal number of evaluations. In the present paper, we derive two modified Os-trowski’s-type methods which improve the local order of convergence from four for Ostrowski’s method to eight for new methods. The important feature of these methods is that per step they require three evaluations of f and one evaluation of f. Thus, the new methods support the conjecture of Kung and Traub for eighth order methods based on four evaluations. The paper is organized in six sections. In Section 2, methods are developed and their eighth order conver-gence is established. In Section 3, computational effi- J. R. SHARMA ET AL. 817 ciency of the methods is discussed. Section 4 contains the numerical experimentations and comparison with some well known methods. Concluding remarks are given in Section 5. In Section 6, references are given. 2. The Methods and Their Convergence Method One Consider the Ost rowski schem e (1) now defined by  ,.2iii iiiii ii ifxwxfxfw fxzwfxfxfw (2) In what follows, we construct the method to obtain the approxim ation 1ix to the root by considering the cubic curve interpolation. Let 23,iiyx abxxcxxdxx i (3) be an interpolatory p ol y nom i a l of degree t h ree such that ,iiyxfx (4) ,iiyxfx (5) ,iiywfw (6) ,iiyzfz (7) and .iiyzfz (8) Our interest is to find the unknown parameters a, b, c and d introduced in the polynomial. In order to achieve that, we make use of the expressions (4) - (7) in (3). From (3), (4) and (5), it is easy to show that (),.iiafxbfx (9) Substituting the values of a and b in (3) then using (6) and (7), we obt ain after some simple calculati ons () ()1() ()iiii iii iifw fxcdw xfxwx wx , (10)   1.iiii iii iifz fxcdzxfxzx zx  (11) Solving these equations using Ostrowski iteration (2), we obtain     222,iiiiiii ifxfx fwcfwfx fw fxfw 3322,iiiiii ifxfx fwdHfxfw fxfw (13) where     322.iiiiiiiii iHfxfwfxfw fxfwfx fzfxfw . The tangent line to the curv e of cubic polyn omial (3) at the point ,iizyz is given by .iiiyyzy zxz  (14) Assuming that the root estimate 1ix is point of inter-section of the tangent line (14) with x-axis, then 10.iyx Thus , fr om (7), (8) and (14 ), we o btain 1.iii ifzxzyz (15) Now using the approximation (8) in (15), we can ob-tain the new improvement as given by 1.iii ifzxzfz (16) where i is the Ostrowski point. It is quite obvious that formula (16) together with (2) requires five evaluations per iteration. However, we can reduce the number of evaluations to four by utilizing the approximation (8). Therefore, (3) and (8) yield z  223iiii iifzyzbczxdzx. (17) Substituting the values of c and in (17), we obtain ,bd,iiifzyzfx (18) where      3212222.ii iiiiii iiiii iii iiiifwfwfxfx fzfwfxfxfwf wfzfx fxfwfx fwfwfxfxfw Then the formula (16) in its final form is given by 11,iii ifzxzfx  (19) where is the Ostrowski iteration (2) and iz is given in (18). 2H (12) Thus, we derive a multipoint method based on the composition of two sub steps, Ostrowski sub step (2) fol-lowed by (19) obtained by tangential cubic interpolation. It is straight forward to see that per step the method util-Copyright © 2011 SciRes. AM J. R. SHARMA ET AL. Copyright © 2011 SciRes. AM 818 izes four pieces of information namely- ,ifx ,ifx ifw and .ifz Since we are using the approxima-tion (8) for the derivative, therefore the error is given by (see ) Theorem 1. Let fx be a real valued function. As-suming that fx is sufficiently smooth in an interval I. If fx has a simple root I and 0x is suffi-ciently close to  then the method defined by (19) is of order eight.  2,4!ivii iiiffz yzzx zw i (20) where .iii iiimin,, ,max,,xwz xwz In order to show that the method is of order eight, we prove the fol-lowing theorem: Proof: Let ,iiex iiew and ˆiiez be errors in the ith iteration. Using Taylor’s series expan-sion of ifx about  and taking into account that f0 and 0,f we have 23456 723456,iiiiiiifxfeAeAeAeAeAeO ei (21) where  1!,2,3,kkAkff k Furthermore, we have 23456234 56123456iiiiiifxfAeAeAeAeAe Oe.i (22)  223 34222324322542332222 356765243 423232 223744106208513 1728335216.iii iiiiifx eAeAAeA AAAeAAA AAA AefxAAAAAAA AAAAAeOe  45i (23) Substitution of (23) in first step of (2), yields 223 3422232 4322542332222 356765243 423232 223744106208513 172833 5216.ii iiiieAeAAeAAAAeAAAAAAAeAAAAAAA AAAAAeOe     45i (24) Expanding ifw about  an d using ( 24) , we obtain  223 3422232 4322542332222 3567652434232 32223754 1062412513 1734377328.ii iiii45ifwfAeAAeAAAAeA AAAAAAeAAAAAAAAAAAAeOe  (25) Using Equations (21), ( 23) an d ( 25) , we obta i n   2233422232 4322542332222 35676524342 32 32222 363 4841242510 10 1615226.ii ii iii iiifx fw45iAeAAeAAAAeAAAAAAAfxfx fwAAAAAAAAAAAAeOe   e (26) From second step of (2) it follows that 34 224523242332222 3567524342 32 32 2ˆ22843 7121830 10.ii iiieAAAeAAAAAAeAAAA AAAAAAAeOe  (27) Expanding ifz about , we obtain 292ˆˆ ,iiifzfeAeOei (28) Using (27) in (28) , we get J. R. SHARMA ET AL. 819 34 224523242332222 35675243423232222843 7121830 10.ii iiif zfAAA eAAAAAAeAAAAAAAAAAAeO e 2, (29) Using the results of (21), (25) and ( 29) in        312222ii iiii i iiiiii iiiiii ifwfwfxfx fzfwfxfxfwfw fzfxfxfwfxfw fwfxfxfw     and simplifying, we get 22332 244223 43225423322124 341285179 3818.ii ii5iAeAAe AAAAeAAAAAA AeOe  (30) From (22) and (30 ), we get 34524 32 2122ifxfAAAAAe Oe.ii (31) Using (28) and (3 1) in 11,iii ifzxzfx  we find the er ror eq uation as give n by   29223122432234524 322234922432223338922 3224322 2 3222ˆˆˆˆˆˆ122122ˆˆ2222ii iiiiiiiiiiiiiiiieAeOeeeeeAe AAAAAeOeAAAAAe OeAeAAAAAeeOeAAAAAAAAA A AAeOeAA      22 8923223 4.iiAAAA AeOe49 (32) Thus Equation (32) establishes the maximum order of convergence equal to eight for the iteration scheme de-fined by (19). This completes the proof of the theorem. Remark 1. The error (20) is now given by  2ˆˆ.4!iviiii iiffzyz eeee  From (24), (27) and Taylor’s expansion of ivf about , we can obtain the error as  4542 .ii iifzyz AAeOe  (33) This shows that the error in derivative approximation is of order four. Remark 2. Upon using Taylor’s expansion ifz22ˆˆ12 iifAeO ei, in (33), we get 45242ˆ12 ,iiiyzfAe AAeOe that is 34 524 32 2122iiiyzfAAAAAeOe (34) which is same as obtained in equation (31) of .iiyzfx This verifies the correctness of error (33) and calculation of iyz. Remark 3. From the convergence theorem of iterative functions , if 1gx and 2gxp are two iterative functions of order 1 and 2, respectively, then the new composite iterative function p21gg xGxiz has the order 12 In our case, the Ostrowski method (2) comprising the first two steps, is of order four. Thus to produce eighth order method the formula (19) should be of order two (neglecting how is obtained). From (34), it turns out that .pp1.eˆˆAeˆf O3iif x2ˆ.Oei Also, the Taylor’s series expansion of the func-tion 2iiiiyzeffz On substitution and simplifying, we see that the Newton-like method (15) and hence (19), has the order two, thus verifying the con-vergence theorem on composition of two iterative func-tions to produce eighth order i t erative me thod. 2.2. Method Two Here we consider the inverse interpolation. Let Copyright © 2011 SciRes. AM J. R. SHARMA ET AL. 820 23,iiiFfxABfx fxCfx fxDfx fx  (35) be an inverse interpolatory polynomial of degree three such that ,iiFfx x (36) 1,iiFfx fx (37) ,iiFfw w (38) ,iiFfz z (39) and 1.iiFfz fz (40) From (36) and (37), we can calculate A and as given by B,1i.iAxB fx (41) Substituting the values of A and in (35), then using (38) and (39 ), we o btain B  21iiiiiiCDfw fxfwfxfw fx  (42) and    21.2iiiiii iiiiiC Dfzfxfz fxfw fxfzfxfxfwfx (43) The Equations (42) and (43) when solved, yield    211,iiiiiiii ifwCfxfw fxfw fxGfxfwfz  (44) 1,ii iDGfx fwfz (45) where      221.2iiiiiiiiiifwGfw fxfx fwfz fx fwfz fx  The tangent line to the curve of cubic polynomial (35) at the point ,iiFfzfz is given by .ii iFfxFfzF fzfxfz  The approximation to the ro ot 1ix is now obtained by intersecting this tangent line with x-axis. This yields 1,iii ifzxzfz (46) where   12123.iiiiiifz FfzBCfzfxDfz fx  From (40), (44 ) and (45), we have  11,iifzfx (47) where        2112.2iiiii iii iiiiiiifwfz fxfw fzfw fzfw fzfz fxfx fwfz fw fw i Hence, the iteration formula (46) is gi ven by 1,iii ifzxzfx  (48) where is the Ostrowski iteration (2) and iz is shown in (47). Thus, we obtain second modified Ostrowski-like me- thod (48) devel oped by t a ngen t i al i nverse i nte rpol at i on. I n this method also, the number of evaluations required is same as in the first method. Error in the approximation (40), likewise the error ( 20 ), can be given by   () 21,4!iiiviii iFfzfzffz fxfz fw (49) where    min, ,,max, ,.iiiiiifxfwfzfxfwfz Copyright © 2011 SciRes. AM J. R. SHARMA ET AL. Copyright © 2011 SciRes. AM 821In the following theorem we prove that the method is of order eight. Theorem 2. Under the hypotheses of theorem 1, the it-eration method defi ned by (4 8) is of order eig ht . Proof: Using (21), (25) and (29), after simple calcula-tions we find   223244 5232 432542232122146 28 410 622.iiiii iiiiii iifw fxfzfw fzfzfxfxfwiAeAAeAAAe AAAAAAeOe    (50) Also    22232 44523 24 326422321232445.iiiii i iii iifwfzfxfwfz fwfxiAeAAeAAAe AAAAAAeOe  (51) From (47) we know 1Equation (50)Equation (51) , which implies 23 24423 454232212 34577.ii iii5AeAe AeAAAAA AeOe  (52) From (22) and (52 ), we get 34 524 32 21177iiiAA AAAeOefx f. (53) Then using (28 ) and (5 3) in 1,iii ifzxzfx  we obtain the error equation 292 44512 422322244924223223492 24322233322 32243222 32ˆˆ ˆ177ˆˆ ˆ177ˆˆ7777iiii iiiii iiiiiiiiieeeAeOe AAAAAeOeeeAeAAAA Ae OeAeAAAAAeeOe8AAAAAA AA AAAAeOe     92228 922 322 346.iiAA AAA AAeOe  (54) This result shows the eighth order convergence of method (48). Remark 4. The error (49) upon using (21), (25) and (29) is given by   34521.4!iiiviiFfzfzFfAeOe  Expanding ivF about  and using the fact that  3()76532324415 10(0)4! 55,iviv fff fFfffAAAAf   we can obtain the error as  34 524 32 21155iiiiFfzfz.AAAAAeOef (55 in approximation (40) is of orRemark 5. Upon using Taylor’s expansion )This shows that the error der four. 1ifz 22ˆˆ112iifAeO ein (55), we get 3451ˆ125 5,Ae AAAAAeO e224322iiiiFfzfthat is  J. R. SHARMA ET AL. 822 34 524 32 21177iiiFfzAA AA AeOef, which is same as obtained in Equation (5 3) of .iiFfzf x This verifies calculations of rm (55) and error teiFfz. Remark 6. Since ˆ11ii ,Ffzfx fO  therefore, similar to remark 3, the iterative formula (48) combined with the Ostrowski iteration (2) verifies the iterative functions to prod uce ei g3. Computational Efficiency ieconvergence theorem on composition of twohth order iterat i ve met hod. In order to obtain an assessment of the efficiency of our methods we shall make use of Traub’s efficiency index (, Appendix C), according to which computational efficiency of an iterative method is given by 1cEp, where p is the order of the method and c is the cost per ction and derivative at is, iterative step of computing the funrequired by the iterative formula, th,jcc jc is the cost of evaluating jf for 0.j The value 0j simply gives the funct ion f. Designating Ostrowski’s method (1) as 4,M sixth order method  as 6M and present methods (19) and (48) as 8,1M and 8,2M, respectively. Assuming that the cost of evaluating  jf is 1, then for 8M we find effi- ciency index 148 1.682.E For 6M, 146 1.565 and similarly for E4,M 134esent m1hrethods are .587.E Com- the E values we find that te pparingbetter options t han bot h of 4M and 6M. 4. Numerical Illustrations In this section, weply the modified methods ap8,iM 1, 2i to solve some nonlar equaich not only illustrate the methods practically but also serve to check the validity of theoretical results we have derived. The performance is comp4inetions, whared with M and 6M. In mes order to compare the higher ordnecessary that we use higher preer ms itcision in computations. pre-ethod becoTherefore, the calculations are performed with high-cision arithmetic and terminated after three iterations. To check the theoretical order of convergence, we obtain the computational order of convergence (p) using the formula (see )  11ln .lniiiixxpxx Table 1. Performance of methods . Problem x0 3ax 3fx p 1f 1 4M 2.21*10–34 4.65*10–33 4.0 6M 7.09*10–103 1.49*101 6.0 0–18,1M 1.18*10–269 2.48*10–268 8.0 8,2M 6.43*10–204 7.35*10–202 8.0 2f 1 4M 3.50*10 5.63*10–2 –2224.0 6M 4.25*10–64 6.83*10–64 6.0 8,1M 7.26*10–171 1.17*10–170 8.0 8,2M 1.46*10–146 2.35*10–146 8.0 3f 4M 1.28*108 1.–7 805*10–7 4.0 6M 1.03*0–251 8.44*0–252 6.110 8,1M 2.25*10–635 1.85*10–635 8.0 8,2M 3.54*10–574 2.90*10–574 8.0 4f 1 4M 1.57*109 4.–2 934*10–2 4.0 6M 4.42*10–81 1.22*10–80 6.0 8,1M 2.33*10–298 6.44*10–298 8.0 8,2M 1.12*10–209 3.10*10–209 8.0 5f 0.5 4M 2.21*106 2.–2 621*10–2 4.0 6M 2.74*10–76 2.74*10–76 6.0 8,1M 2.53*10–232 2.53*10–232 8.0 8,2M 2.85*10–191 2.85*10–191 8.0 6f 2 4M 5.44*102 1.–3 135*10–3 4.0 6M 2.98*10–95 7.40*10–95 6.0 8,1M 1.10*10–268 2.72*10–268 8.0 8,2M 9.17*10–212 2.28*10–211 8.0 7f 1 4M 1.62*106 4.–3 693*10–3 4.0 6M 4.17*0–108 1.27*0–107 6.110 8,1M 1.00*10–269 3.04*10–269 8.0 8,2M 5.13*10–236 1.56*10–235 8.0 8f –1.5 4M 2.30*10–39 4.68*10–38 4.0 6M 1.36*0–108 2.76*0–107 6.110 8,1M 2.83*10–231 5.75*10–230 8.0 8,2M 2.11*10–233 4.28*10–232 8.0 We consider t h e fol l owi ng t e st pr obl ems: Copyright © 2011 SciRes. AM J. R. SHARMA ET AL. Copyright © 2011 SciRes. AM 823  21,  32152234352671 3196360.3459 482420sin2,1.8954942670339809,10 exp1.64284,g 1,sin1.4081534cosfx xfx xxfx xfx xxfx xfx xfxx 228, 0.51775736368245830,sin3cos 5,1.2076478271309189.xxxefx xexx  Table 1 shows the absolute difference , 0xx21,4x5, 1.6808055660 ,1 ,548158 ,79630610 499lo449164 212,x3x, the absolute value o f the function 3fx ). It can be obsblems, tand the computa-tional order of convergence (perved clearly that in all considered test prohe new methods 8,iM 1, 2i 4compute the results with higher precision than M and 6M. This superiority of 8,iM agreesis of order and efficiscussedin previous secti ons. 5.the pint iteratq alua with theoretical analysency di Conclusions In this work, we have obtained two multipoint methods of order eight using an additional evaluation of function at oed by Ostrowski’s method of order four for solving euations. Thus, one requires three evtions of the function f and one of its first-derivative f per full step and therefore, the efficiency of the meski’s method. The superiority of pre-orated by numerical resuldisplayed in the table 1. The computational order of con- ro of One-Point and Multipoint Iteration,” Journal of the Association for chinery, Vol. 21, No. 4, 1974, pp. 643-651. thods i better than Ostrowssent methods is also corrobts vergence (p) overwhelmingly supports the eighth order convergence ofour methods. These methods also pvide the examples of eighth order methods requiring four evaluations for Kung and Traub conjecture. Finally, we conclude the paper with the remarks that such higher or-der methods are useful in the numerical applications re-quiring high p r eci sion i n t hei r computations. 6. References  J. F. Traub, “Iterative Methods for the Solution of Equa-tions,” Prentice Hall, Englewood Cliffs, 1964.  H. T. Kung and J. F. Traub, “Optimal OrderComputing Madoi: 10.1145/321850.321860  A. M. Ostrowski, “Solutions of Equations and System of Equations,” Academic Press, New York, 1960.  M. Grau and J. L. Díaz-Barrero, “An Improvement to Ostrowski Root-Finding Method,” Applied Mathematics and Computation, Vol. 173, No. 1, 2006, pp. 450-456. doi:10.1016/j.amc.2005.04.043  J. R. Sharma and R. K. Guha, “A Family of Modified Ostrowski Methods with Accelerated Sixth Order Con-vergence,” Applied Mathematics and Computation, Vol. 190, No. 1, 2007, pp. 111-115. doi:10.1016/j.amc.2007.01.009  G. M. Phillips and P. J. Taylor, “Theory and Applications ers, Vol. 13, No. 8, 2000, of Numerical Analysis,” Academic Press, New York, 1996.  S. Weerakoon and T. G. I Fernando, “A Variant of New-ton’s Method with Accelerated Third-Order Conver-gence,” A pplied Mathematics Lettpp. 87-93. doi:10.1016/S0893-9659(00)00100-2