On an Aitken-Newton type method

Ion Păvăloiu
(original), divided differences, inverse interpolation, JCR/ISI, local convergence, Newton method, nonlinear equations in R, Numerical Analysis, paper, solving F(x)=0 iteratively

Abstract

We study the solving of nonlinear equations by an iterative method of Aitken type, which has the interpolation nodes controlled by the Newton method. We obtain a local convergence result which shows that the q-convergence order of this method is 6 and its efficiency index is \(\sqrt[5]6\), which is higher than the efficiency index of the Aitken or Newton methods. Monotone sequences are obtained for initial approximations farther from the solution, if they satisfy the Fourier condition and the nonlinear mapping satisfies monotony and convexity assumptions on the domain.

Authors

Ion Păvăloiu (Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Ion Păvăloiu

Emil Cătinaş (Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Emil Cătinaş

Keywords

Nonlinear equations in R; Aitken method; Newton method; inverse interpolatory polynomials; divided differences; monotone sequences.

Paper coordinates

I. Păvăloiu, E. Cătinaş, On an Aitken-Newton type method, Numer. Algor., 62 (2013) no. 2, pp. 253-260
10.1007/s11075-012-9577-7

PDF

https://ictp.acad.ro/wp-content/uploads/2026/01/2013-Pavaloiu-Catinas-Numer-Algor-On-an-Aitken-Newton-type-method.pdf

About this paper

Journal

Numerical Algorithms

Publisher Name

Springer

DOI

10.1007/s11075-012-9577-7

Print ISSN

1017-1398

Online ISSN

1572-9265

Google Scholar Profile

link soon.

  1. Amat, S., Busquier, S.: A two step Steffenssen’s method under modified convergence conditions. J. Math. Anal. Appl. 324, 1084–1092 (2006) Article MathSciNet MATH Google Scholar

  2. Beltyukov, B.A.: An analogue of the Aitken–Steffensen method with controlled step. URSS Comput. Math. Math. Phys. 27(3), 103–112 (1987) Article MathSciNet Google Scholar

  3. Chun, C.: A geometric construction of iterative formulas of order three. Appl. Math. Lett. 23, 512–516 (2010) Article MathSciNet MATH Google Scholar

  4. Cordero, A., Torregrosa, J.R.: Variants of Newton’s method for functions of several variables. Appl. Math. Comput. 183, 199–2008 (2006) Article MathSciNet MATH Google Scholar

  5. Cordero, A., Torregrosa, J.R.: Variants of Newton’s method using fifth order quadrature formulas. Appl. Math. Comput. 190, 686–698 (2007) Article MathSciNet MATH Google Scholar

  6. Cordero A., Torregrosa R.J.: A class of Steffenssen type method with optimal order of convergence. Appl. Math. Comput. 217, 7653–7659 (2011) Article MathSciNet MATH Google Scholar

  7. Hongmin, R., Qingbio, W., Welhong, B.: A class of two-step Steffensen type methods with fourth order convergence. Appl. Math. Comput. 209(2), 206–210 (2009) Article MathSciNet MATH Google Scholar

  8. Jain, P.: Steffensen type method for solving non-linear equations. Appl. Math. Comput. 194, 527–533 (2007) Article MathSciNet MATH Google Scholar

  9. Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970) MATH Google Scholar

  10. Ostrowski, M.A.: Solution of Equations in Euclidian and Banach Spaces. Academic Press, New York and London (1973) Google Scholar

  11. Păvăloiu, I.: Approximation of the root of equations by Aitken–Steffensen-type monotonic sequences. Calcolo 32, 69–82 (1995) Article MathSciNet MATH Google Scholar

  12. Păvăloiu, I., Cătinaş, E.: On a Steffensen–Hermite method of order three. Appl. Math. Comput. 215(7), 2663–2672 (2009) Article MathSciNet MATH Google Scholar

  13. Păvăloiu, I., Cătinaş, E.: On a Steffensen type method. In: Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Proceedings, pp. 369–375 (2007)

  14. Păvăloiu, I.: Optimal algorithms, concerning the solving of equations by interpolation. In: Popoviciu, E. (ed.) Research on Theory of Allure, Approximation, Convexity and Optimization, Editura Srima, Cluj-Napoca, pp. 222–248 (1999)

  15. Păvăloiu, I.: Aitken–Steffensen-type method for nondifferentiable functions (I). Rev. Anal. Numér. Theor. Approx. 31(1), 109–114 (2002) MATH Google Scholar

  16. Păvăloiu, I.: Aitken–Steffensen-type method for nonsmooth functions (II). Rev. Anal. Numér. Théor. Approx. 31(2), 195–198 (2002) MATH Google Scholar

  17. Păvăloiu, I.: Aitken–Steffensen-type method for nonsmooth functions (III). Rev. Anal. Numér. Théor. Approx. 32(1), 73–78 (2003) MATH Google Scholar

  18. Quan, Z., Peng, Z., Li, Z., Wenchao, M.: Variants of Steffensen secant method and applications. Appl. Math. Comput. 216(12), 3486–3496 (2010) Article MathSciNet MATH Google Scholar

  19. Sharma, R.J.: A composite thid order Newton–Steffensen method for solving nonlinear equations. Appl. Math. Comput. 169, 242–246 (2005) Article MathSciNet MATH Google Scholar

  20. Traub, Y.F.: Iterative Method for Solution of Equations. Prentice-Hall, Englewood Cliffs, NJ (1964) Google Scholar

  21. Weerakoon, S., Fernando, T.G.I.: A variant of Newton’s method with accelerated third-order convergence. Appl. Math. Lett. 13(8), 87–93 (2000) Article MathSciNet MATH Google Scholar

Paper (preprint) in HTML form

s11075-012-9577-7

On an Aitken-Newton type method

Ion Păvăloiu • Emil Cătinaş

Abstract

We study the solving of nonlinear equations by an iterative method of Aitken type, which has the interpolation nodes controlled by the Newton method. We obtain a local convergence result which shows that the q q qqq-convergence order of this method is 6 and its efficiency index is 6 5 6 5 root(5)(6)\sqrt[5]{6}65, which is higher than the efficiency index of the Aitken or Newton methods. Monotone sequences are obtained for initial approximations farther from the solution, if they satisfy the Fourier condition and the nonlinear mapping satisfies monotony and convexity assumptions on the domain.

Keywords Nonlinear equations • Aitken method • Newton method • Monotone convergence

1 Introduction

In this note we study an Aitken type method, for which the interpolation nodes are given by two iterations of Newton type. We show that this method has the q q qqq-convergence order 6 and it requires 5 function evaluations at each step. This implies that the efficiency index of this method is 6 5 6 5 root(5)(6)\sqrt[5]{6}65, which is greater than 2 2 sqrt2\sqrt{2}2 (the efficiency index of the Newton and of the Aitken method) [10, 14, 20].
Consider the equation
(1) f ( x ) = 0 (1) f ( x ) = 0 {:(1)f(x)=0:}\begin{equation*} f(x)=0 \tag{1} \end{equation*}(1)f(x)=0
where f : [ a , b ] → R , a < b f : [ a , b ] → R , a < b f:[a,b]rarrR,a < bf:[a, b] \rightarrow \mathbb{R}, a<bf:[a,b]→R,a<b and assume
α ) α ) alpha)\alpha)α) this equation has a solution x ∗ ∈ ] a , b [ x ∗ ∈ a , b [ {:x^(**)in]a,b[\left.x^{*} \in\right] a, b[x∗∈]a,b[.
We consider two more equations
x − g 1 ( x ) = 0 (2) x − g 2 ( x ) = 0 x − g 1 ( x ) = 0 (2) x − g 2 ( x ) = 0 {:[x-g_(1)(x)=0],[(2)x-g_(2)(x)=0]:}\begin{align*} & x-g_{1}(x)=0 \\ & x-g_{2}(x)=0 \tag{2} \end{align*}x−g1(x)=0(2)x−g2(x)=0
g 1 , g 2 : [ a , b ] → [ a , b ] g 1 , g 2 : [ a , b ] → [ a , b ] g_(1),g_(2):[a,b]rarr[a,b]g_{1}, g_{2}:[a, b] \rightarrow[a, b]g1,g2:[a,b]→[a,b], and we assume they are equivalent to (1).
The Aitken method consists in constructing the sequence ( x n ) n ≥ 0 x n n ≥ 0 (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0}(xn)n≥0 given by [1-3, 6-8, 10-19],
(3) x n + 1 = g 1 ( x n ) − f ( g 1 ( x n ) ) [ g 1 ( x n ) , g 2 ( x n ) ; f ] , n = 0 , 1 , … , x 0 ∈ [ a , b ] , (3) x n + 1 = g 1 x n − f g 1 x n g 1 x n , g 2 x n ; f , n = 0 , 1 , … , x 0 ∈ [ a , b ] , {:(3)x_(n+1)=g_(1)(x_(n))-(f(g_(1)(x_(n))))/([g_(1)(x_(n)),g_(2)(x_(n));f])","n=0","1","dots","x_(0)in[a","b]",":}\begin{equation*} x_{n+1}=g_{1}\left(x_{n}\right)-\frac{f\left(g_{1}\left(x_{n}\right)\right)}{\left[g_{1}\left(x_{n}\right), g_{2}\left(x_{n}\right) ; f\right]}, n=0,1, \ldots, x_{0} \in[a, b], \tag{3} \end{equation*}(3)xn+1=g1(xn)−f(g1(xn))[g1(xn),g2(xn);f],n=0,1,…,x0∈[a,b],
where [ x , y ; f ] [ x , y ; f ] [x,y;f][x, y ; f][x,y;f] stands for the first order divided difference of f f fff at x x xxx and y y yyy. We suppose that f f fff is derivable on [ a , b ] [ a , b ] [a,b][a, b][a,b] and we consider the function
(4) g 1 ( x ) = x − f ( x ) f ′ ( x ) (4) g 1 ( x ) = x − f ( x ) f ′ ( x ) {:(4)g_(1)(x)=x-(f(x))/(f^(')(x)):}\begin{equation*} g_{1}(x)=x-\frac{f(x)}{f^{\prime}(x)} \tag{4} \end{equation*}(4)g1(x)=x−f(x)f′(x)
Denoting
g 2 ( x ) = g 1 ( g 1 ( x ) ) , g 2 ( x ) = g 1 g 1 ( x ) , g_(2)(x)=g_(1)(g_(1)(x)),g_{2}(x)=g_{1}\left(g_{1}(x)\right),g2(x)=g1(g1(x)),
we are lead to the following Aitken-type iterative method
y n = x n − f ( x n ) f ′ ( x n ) z n = y n − f ( y n ) f ′ ( y n ) (5) x n + 1 = z n − f ( z n ) [ y n , z n ; f ] , n = 0 , 1 , … , x 0 ∈ [ a , b ] , y n = x n − f x n f ′ x n z n = y n − f y n f ′ y n (5) x n + 1 = z n − f z n y n , z n ; f , n = 0 , 1 , … , x 0 ∈ [ a , b ] , {:[y_(n)=x_(n)-(f(x_(n)))/(f^(')(x_(n)))],[z_(n)=y_(n)-(f(y_(n)))/(f^(')(y_(n)))],[(5)x_(n+1)=z_(n)-(f(z_(n)))/([y_(n),z_(n);f])","n=0","1","dots","x_(0)in[a","b]","]:}\begin{align*} y_{n} & =x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \\ z_{n} & =y_{n}-\frac{f\left(y_{n}\right)}{f^{\prime}\left(y_{n}\right)} \\ x_{n+1} & =z_{n}-\frac{f\left(z_{n}\right)}{\left[y_{n}, z_{n} ; f\right]}, n=0,1, \ldots, x_{0} \in[a, b], \tag{5} \end{align*}yn=xn−f(xn)f′(xn)zn=yn−f(yn)f′(yn)(5)xn+1=zn−f(zn)[yn,zn;f],n=0,1,…,x0∈[a,b],
which we call the Aitken-Newton method.
In Section 2 we provide a local convergence result for this method, and we show a similar result which holds for the Newton method: if f f fff maintains its monotony and convexity on a larger domain, and the initial approximation obeys the Fourier condition, then the iterates converge monotonically to the solution. These properties, together with the fact that the efficiency index of this method is shown that is higher than the efficiency index of the Newton or Aitken methods, justify the study of this method.

2 Convergence of the method

We obtain the following local convergence result.
Theorem 1 Assume α α alpha\alphaα ) and
β β beta\betaβ ) there exists an open interval I , x ∗ ∈ I ⊆ ] a , b [ I , x ∗ ∈ I ⊆ a , b [ {:I,x^(**)in I sube]a,b[\left.I, x^{*} \in I \subseteq\right] a, b[I,x∗∈I⊆]a,b[ such that f f fff is two times differentiable on I I III, with f ′ ′ f ′ ′ f^('')f^{\prime \prime}f′′ continuous at x ∗ x ∗ x^(**)x^{*}x∗.
Then there exists an interval J ⊆ I J ⊆ I J sube IJ \subseteq IJ⊆I such that for any initial approximation x 0 ∈ J x 0 ∈ J x_(0)in Jx_{0} \in Jx0∈J, the iterations (5) are well defined, remain in J J JJJ and converge to x ∗ x ∗ x^(**)x^{*}x∗ with q q qqq-order at least 6 .
Proof The first and second relations in (5) imply the existence of θ n θ n theta_(n)\theta_{n}θn and η n η n eta_(n)\eta_{n}ηn in the interior of the intervals determined by x n x n x_(n)x_{n}xn and x ∗ x ∗ x^(**)x^{*}x∗, resp. y n y n y_(n)y_{n}yn and x ∗ x ∗ x^(**)x^{*}x∗ such that
(6) x ∗ − y n = − f ′ ′ ( θ n ) 2 f ′ ( x n ) ( x ∗ − x n ) 2 , n = 0 , 1 , … (7) x ∗ − z n = − f ′ ′ ( η n ) 2 f ′ ( y n ) ( x ∗ − y n ) 2 , n = 0 , 1 , … (6) x ∗ − y n = − f ′ ′ θ n 2 f ′ x n x ∗ − x n 2 , n = 0 , 1 , … (7) x ∗ − z n = − f ′ ′ η n 2 f ′ y n x ∗ − y n 2 , n = 0 , 1 , … {:[(6)x^(**)-y_(n)=-(f^('')(theta_(n)))/(2f^(')(x_(n)))(x^(**)-x_(n))^(2)","n=0","1","dots],[(7)x^(**)-z_(n)=-(f^('')(eta_(n)))/(2f^(')(y_(n)))(x^(**)-y_(n))^(2)","n=0","1","dots]:}\begin{align*} & x^{*}-y_{n}=-\frac{f^{\prime \prime}\left(\theta_{n}\right)}{2 f^{\prime}\left(x_{n}\right)}\left(x^{*}-x_{n}\right)^{2}, n=0,1, \ldots \tag{6}\\ & x^{*}-z_{n}=-\frac{f^{\prime \prime}\left(\eta_{n}\right)}{2 f^{\prime}\left(y_{n}\right)}\left(x^{*}-y_{n}\right)^{2}, n=0,1, \ldots \tag{7} \end{align*}(6)x∗−yn=−f′′(θn)2f′(xn)(x∗−xn)2,n=0,1,…(7)x∗−zn=−f′′(ηn)2f′(yn)(x∗−yn)2,n=0,1,…
The third relation in (5) and the Newton identity imply that
(8) x ∗ − x n + 1 = − [ x ∗ , y n , z n ; f ] [ y n , z n ; f ] ( x ∗ − z n ) ( x ∗ − y n ) , n = 0 , 1 , … (8) x ∗ − x n + 1 = − x ∗ , y n , z n ; f y n , z n ; f x ∗ − z n x ∗ − y n , n = 0 , 1 , … {:(8)x^(**)-x_(n+1)=-([x^(**),y_(n),z_(n);f])/([y_(n),z_(n);f])(x^(**)-z_(n))(x^(**)-y_(n))","n=0","1","dots:}\begin{equation*} x^{*}-x_{n+1}=-\frac{\left[x^{*}, y_{n}, z_{n} ; f\right]}{\left[y_{n}, z_{n} ; f\right]}\left(x^{*}-z_{n}\right)\left(x^{*}-y_{n}\right), n=0,1, \ldots \tag{8} \end{equation*}(8)x∗−xn+1=−[x∗,yn,zn;f][yn,zn;f](x∗−zn)(x∗−yn),n=0,1,…
Relations (6)-(8) lead to
(9) x ∗ − x n + 1 = − [ x ∗ , y n , z n ; f ] f ′ ′ ( η n ) ⋅ ( f ′ ′ ( θ n ) ) 3 16 [ y n , z n ; f ] f ′ ( y n ) ( f ′ ( x n ) ) 3 ( x ∗ − x n ) 6 , n = 0 , 1 , … , (9) x ∗ − x n + 1 = − x ∗ , y n , z n ; f f ′ ′ η n ⋅ f ′ ′ θ n 3 16 y n , z n ; f f ′ y n f ′ x n 3 x ∗ − x n 6 , n = 0 , 1 , … , {:(9)x^(**)-x_(n+1)=-([x^(**),y_(n),z_(n);f]f^('')(eta_(n))*(f^('')(theta_(n)))^(3))/(16[y_(n),z_(n);f]f^(')(y_(n))(f^(')(x_(n)))^(3))(x^(**)-x_(n))^(6)","n=0","1","dots",":}\begin{equation*} x^{*}-x_{n+1}=-\frac{\left[x^{*}, y_{n}, z_{n} ; f\right] f^{\prime \prime}\left(\eta_{n}\right) \cdot\left(f^{\prime \prime}\left(\theta_{n}\right)\right)^{3}}{16\left[y_{n}, z_{n} ; f\right] f^{\prime}\left(y_{n}\right)\left(f^{\prime}\left(x_{n}\right)\right)^{3}}\left(x^{*}-x_{n}\right)^{6}, n=0,1, \ldots, \tag{9} \end{equation*}(9)x∗−xn+1=−[x∗,yn,zn;f]f′′(ηn)⋅(f′′(θn))316[yn,zn;f]f′(yn)(f′(xn))3(x∗−xn)6,n=0,1,…,
which shows the assertion, provided that x 0 x 0 x_(0)x_{0}x0 is sufficiently close to x ∗ x ∗ x^(**)x^{*}x∗.
Under supplementary conditions on f f fff we obtain the following result.
Theorem 2 If f f fff and x 0 x 0 x_(0)x_{0}x0 verify α α alpha\alphaα ), and
β ′ ) f β ′ f {:beta^('))quad f\left.\beta^{\prime}\right) \quad fβ′)f is two times differentiable on [ a , b ] [ a , b ] [a,b][a, b][a,b], with f ′ ′ f ′ ′ f^('')f^{\prime \prime}f′′ continuous at x ∗ x ∗ x^(**)x^{*}x∗;
γ) x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] quadx_(0)in[a,b]\quad x_{0} \in[a, b]x0∈[a,b] verifies the Fourier condition: f ( x 0 ) f ′ ′ ( x 0 ) > 0 f x 0 f ′ ′ x 0 > 0 f(x_(0))f^('')(x_(0)) > 0f\left(x_{0}\right) f^{\prime \prime}\left(x_{0}\right)>0f(x0)f′′(x0)>0 (see [10]),
and, moreover,
i 1 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i 1 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i_(1).quadf^(')(x) > 0,AA x in[a,b];\mathrm{i}_{1} . \quad f^{\prime}(x)>0, \forall x \in[a, b] ;i1.f′(x)>0,∀x∈[a,b];
ii. f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] quadf^('')(x) >= 0,AA x in[a,b]\quad f^{\prime \prime}(x) \geq 0, \forall x \in[a, b]f′′(x)≥0,∀x∈[a,b],
then the sequences ( x n ) n ≥ 0 , ( y n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0 and ( z n ) n ≥ 0 z n n ≥ 0 (z_(n))_(n >= 0)\left(z_{n}\right)_{n \geq 0}(zn)n≥0 generated by (5), remain in [ a , b a , b a,ba, ba,b ] and obey
j 1 . x n > y n > z n > x n + 1 > x ∗ , n = 0 , 1 , … j 1 . x n > y n > z n > x n + 1 > x ∗ , n = 0 , 1 , … j_(1).quadx_(n) > y_(n) > z_(n) > x_(n+1) > x^(**),n=0,1,dots\mathrm{j}_{1} . \quad x_{n}>y_{n}>z_{n}>x_{n+1}>x^{*}, n=0,1, \ldotsj1.xn>yn>zn>xn+1>x∗,n=0,1,…;
jj 1 . lim x n = lim y n = lim z n = x ∗ jj 1 . lim x n = lim y n = lim z n = x ∗ jj_(1).quad limx_(n)=limy_(n)=limz_(n)=x^(**)\mathrm{jj}_{1} . \quad \lim x_{n}=\lim y_{n}=\lim z_{n}=x^{*}jj1.limxn=limyn=limzn=x∗.
Proof By α α alpha\alphaα ) and i 1 i 1 i_(1)i_{1}i1 it follows that x ∗ x ∗ x^(**)x^{*}x∗ is the unique solution of (1). Let x n ∈ ] a , b [ x n ∈ a , b [ {:x_(n)in]a,b[\left.x_{n} \in\right] a, b[xn∈]a,b[ be an approximation which verifies the relation f ( x n ) f ′ ′ ( x n ) > 0 f x n f ′ ′ x n > 0 f(x_(n))f^('')(x_(n)) > 0f\left(x_{n}\right) f^{\prime \prime}\left(x_{n}\right)>0f(xn)f′′(xn)>0. Then by i i 1 i i 1 ii_(1)i i_{1}ii1 it follows that f ( x n ) > 0 f x n > 0 f(x_(n)) > 0f\left(x_{n}\right)>0f(xn)>0, which, together with i 1 i 1 i_(1)i_{1}i1 lead to x n > x ∗ x n > x ∗ x_(n) > x^(**)x_{n}>x^{*}xn>x∗.
From i 1 , i i 1 i 1 , i i 1 i_(1),ii_(1)i_{1}, i i_{1}i1,ii1 and relation (6) we have x ∗ − y n ≤ 0 x ∗ − y n ≤ 0 x^(**)-y_(n) <= 0x^{*}-y_{n} \leq 0x∗−yn≤0, i.e. y n ≥ x ∗ y n ≥ x ∗ y_(n) >= x^(**)y_{n} \geq x^{*}yn≥x∗. Analogously, from (7) and (8) it follows z n ≥ x ∗ z n ≥ x ∗ z_(n) >= x^(**)z_{n} \geq x^{*}zn≥x∗ and x n + 1 ≥ x ∗ x n + 1 ≥ x ∗ x_(n+1) >= x^(**)x_{n+1} \geq x^{*}xn+1≥x∗.
The first relation in (5) and f ( x n ) > 0 , f ′ ( x n ) > 0 f x n > 0 , f ′ x n > 0 f(x_(n)) > 0,f^(')(x_(n)) > 0f\left(x_{n}\right)>0, f^{\prime}\left(x_{n}\right)>0f(xn)>0,f′(xn)>0 imply that y n < x n y n < x n y_(n) < x_(n)y_{n}<x_{n}yn<xn. Analogously, the second relation in (5) leads to z n < y n z n < y n z_(n) < y_(n)z_{n}<y_{n}zn<yn, while the third relation in (5) to x n + 1 < z n x n + 1 < z n x_(n+1) < z_(n)x_{n+1}<z_{n}xn+1<zn. Conclusion j 1 j 1 j_(1)j_{1}j1 is therefore proved. Moreover, it is clear that the elements of the sequences ( x n ) n ≥ 0 , ( y n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0 and ( z n ) n ≥ 0 z n n ≥ 0 (z_(n))_(n >= 0)\left(z_{n}\right)_{n \geq 0}(zn)n≥0 remain in the interval [ x ∗ , x 0 ] ⊂ [ a , b ] x ∗ , x 0 ⊂ [ a , b ] [x^(**),x_(0)]sub[a,b]\left[x^{*}, x_{0}\right] \subset[a, b][x∗,x0]⊂[a,b]. By j 1 j 1 j_(1)j_{1}j1 it follows that these three sequences are convergent.
Let lim x n = ℓ lim x n = ℓ limx_(n)=ℓ\lim x_{n}=\elllimxn=ℓ. Relation j 1 j 1 j_(1)j_{1}j1 implies that lim y n = lim z n = ℓ lim y n = lim z n = ℓ limy_(n)=limz_(n)=ℓ\lim y_{n}=\lim z_{n}=\elllimyn=limzn=ℓ. The first relation in (5) attracts that ℓ = ℓ − f ( ℓ ) f ′ ( ℓ ) ℓ = ℓ − f ( ℓ ) f ′ ( ℓ ) ℓ=ℓ-(f(ℓ))/(f^(')(ℓ))\ell=\ell-\frac{f(\ell)}{f^{\prime}(\ell)}ℓ=ℓ−f(ℓ)f′(ℓ), so f ( ℓ ) = 0 f ( ℓ ) = 0 f(ℓ)=0f(\ell)=0f(ℓ)=0, i.e., ℓ = x ∗ ℓ = x ∗ ℓ=x^(**)\ell=x^{*}ℓ=x∗. ◻ ◻ ◻\square◻
The following immediate consequence holds.
Corollary 3 If f f fff and x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b] verify α α alpha\alphaα ), β ′ β ′ beta^(')\beta^{\prime}β′ ), γ γ gamma\gammaγ ) and, moreover
i. f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; quadf^(')(x) < 0,AA x in[a,b];\quad f^{\prime}(x)<0, \forall x \in[a, b] ;f′(x)<0,∀x∈[a,b];
ii i 2 f ′ ′ ( x ) ≤ 0 , ∀ x ∈ [ a , b ] 2 f ′ ′ ( x ) ≤ 0 , ∀ x ∈ [ a , b ] _(2)quadf^('')(x) <= 0,AA x in[a,b]_{2} \quad f^{\prime \prime}(x) \leq 0, \forall x \in[a, b]2f′′(x)≤0,∀x∈[a,b],
then the elements of the sequences ( x n ) n ≥ 0 , ( y n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0, and ( z n ) n ≥ 0 z n n ≥ 0 (z_(n))_(n >= 0)\left(z_{n}\right)_{n \geq 0}(zn)n≥0 generated by (5) remain in the interval [ a , b ] [ a , b ] [a,b][a, b][a,b] and satisfy the conclusions j 1 j 1 j_(1)j_{1}j1 and j j 1 j j 1 jj_(1)j j_{1}jj1 of Theorem 2.
It is easy to see that if instead of (1) we consider
(10) − f ( x ) = 0 (10) − f ( x ) = 0 {:(10)-f(x)=0:}\begin{equation*} -f(x)=0 \tag{10} \end{equation*}(10)−f(x)=0
then function h : [ a , b ] → R h : [ a , b ] → R h:[a,b]rarrRh:[a, b] \rightarrow \mathbb{R}h:[a,b]→R given by relation
h ( x ) = − f ( x ) h ( x ) = − f ( x ) h(x)=-f(x)h(x)=-f(x)h(x)=−f(x)
verifies hypothesis of Theorem 2.
Theorem 4 If f f fff and x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b] verify α ) , β ′ ) , γ α , β ′ , γ {: alpha),beta^(')),gamma\left.\left.\alpha\right), \beta^{\prime}\right), \gammaα),β′),γ ) and, moreover,
i 3 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i 3 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i_(3).quadf^(')(x) > 0,AA x in[a,b];\mathrm{i}_{3} . \quad f^{\prime}(x)>0, \forall x \in[a, b] ;i3.f′(x)>0,∀x∈[a,b];
ii. f ′ ′ ( x ) ≤ 0 , ∀ x ∈ [ a , b ] f ′ ′ ( x ) ≤ 0 , ∀ x ∈ [ a , b ] f^('')(x) <= 0,AA x in[a,b]f^{\prime \prime}(x) \leq 0, \forall x \in[a, b]f′′(x)≤0,∀x∈[a,b],
then the elements of the sequences ( x n ) n ≥ 0 , ( y n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0 and ( z n ) n ≥ 0 z n n ≥ 0 (z_(n))_(n >= 0)\left(z_{n}\right)_{n \geq 0}(zn)n≥0 generated by (5) remain in [ a , b ] [ a , b ] [a,b][a, b][a,b] and, moreover, obey
j 3 . x n < y n < z n < x n + 1 < x ∗ , n = 0 , 1 , … j 3 . x n < y n < z n < x n + 1 < x ∗ , n = 0 , 1 , … j_(3).quadx_(n) < y_(n) < z_(n) < x_(n+1) < x^(**),n=0,1,dots\mathrm{j}_{3} . \quad x_{n}<y_{n}<z_{n}<x_{n+1}<x^{*}, n=0,1, \ldotsj3.xn<yn<zn<xn+1<x∗,n=0,1,…, ;
jj 3 . lim x n = lim y n = lim z n = x ∗ jj 3 . lim x n = lim y n = lim z n = x ∗ jj_(3).quad limx_(n)=limy_(n)=limz_(n)=x^(**)\mathrm{jj}_{3} . \quad \lim x_{n}=\lim y_{n}=\lim z_{n}=x^{*}jj3.limxn=limyn=limzn=x∗.
The proof of this result is similar to the proof of Theorem 2.
If we replace (1) by (10) then we obtain:
Corollary 5 If f f fff and x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b] verify hypothesis α α alpha\alphaα ), β ′ β ′ beta^(')\beta^{\prime}β′ ), γ γ gamma\gammaγ ) and, moreover,
i n . f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; i n . f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; i_(n).quadf^(')(x) < 0,AA x in[a,b];\mathrm{i}_{n} . \quad f^{\prime}(x)<0, \forall x \in[a, b] ;in.f′(x)<0,∀x∈[a,b];
ii n . f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] ii n . f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] ii_(n).quadf^('')(x) >= 0,AA x in[a,b]\mathrm{ii}_{n} . \quad f^{\prime \prime}(x) \geq 0, \forall x \in[a, b]iin.f′′(x)≥0,∀x∈[a,b],
then the elements of the sequences ( x n ) n ≥ 0 , ( y n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0 and ( z n ) n ≥ 0 z n n ≥ 0 (z_(n))_(n >= 0)\left(z_{n}\right)_{n \geq 0}(zn)n≥0 generated by (5) remain in [ a , b ] [ a , b ] [a,b][a, b][a,b] and satisfy the statements j 3 j 3 j_(3)j_{3}j3 and j j 3 j j 3 jj_(3)j j_{3}jj3 of Theorem 4.
Remark 6 Relations (9) show us that the Aitken-Newton method has the q q qqq-convergence order at least 6 (it is exactly 6 if f ′ ′ ( x ∗ ) ≠ 0 f ′ ′ x ∗ ≠ 0 f^('')(x^(**))!=0f^{\prime \prime}\left(x^{*}\right) \neq 0f′′(x∗)≠0, see [9]). In order to obtain x n + 1 x n + 1 x_(n+1)x_{n+1}xn+1 from x n x n x_(n)x_{n}xn in (5) we need to perform the following function evaluations: f ( x n ) , f ′ ( x n ) , f ( y n ) , f ′ ( y n ) f x n , f ′ x n , f y n , f ′ y n f(x_(n)),f^(')(x_(n)),f(y_(n)),f^(')(y_(n))f\left(x_{n}\right), f^{\prime}\left(x_{n}\right), f\left(y_{n}\right), f^{\prime}\left(y_{n}\right)f(xn),f′(xn),f(yn),f′(yn) and f ( z n ) f z n f(z_(n))f\left(z_{n}\right)f(zn), i.e., 5 function evaluations. This shows that the efficiency index of this method is 6 5 6 5 root(5)(6)\sqrt[5]{6}65 which is greater than of Aitken or Newton method.
Remark 7 Under additional information on the bounds of the size of derivatives, one can obtain obtain some a posteriori error estimations of the error:
(11) | x ∗ − x n + 1 | ≤ M 2 m | x n + 1 − y n | | x n + 1 − z n | , n = 0 , 1 , … (11) x ∗ − x n + 1 ≤ M 2 m x n + 1 − y n x n + 1 − z n , n = 0 , 1 , … {:(11)|x^(**)-x_(n+1)| <= (M)/(2m)|x_(n+1)-y_(n)||x_(n+1)-z_(n)|","n=0","1","dots:}\begin{equation*} \left|x^{*}-x_{n+1}\right| \leq \frac{M}{2 m}\left|x_{n+1}-y_{n}\right|\left|x_{n+1}-z_{n}\right|, n=0,1, \ldots \tag{11} \end{equation*}(11)|x∗−xn+1|≤M2m|xn+1−yn||xn+1−zn|,n=0,1,…
where
m ≤ min x ∈ [ a , b ] | f ′ ( x ) | , M ≥ max x ∈ [ a , b ] | f ′ ′ ( x ) | m ≤ min x ∈ [ a , b ]   f ′ ( x ) , M ≥ max x ∈ [ a , b ]   f ′ ′ ( x ) m <= min_(x in[a,b])|f^(')(x)|,M >= max_(x in[a,b])|f^('')(x)|m \leq \min _{x \in[a, b]}\left|f^{\prime}(x)\right|, M \geq \max _{x \in[a, b]}\left|f^{\prime \prime}(x)\right|m≤minx∈[a,b]|f′(x)|,M≥maxx∈[a,b]|f′′(x)|
In order to prove them, we consider the Newton identity,
f ( x n + 1 ) = f ( y n ) + [ y n , z n ; f ] ( x n + 1 − y n ) + + [ x n + 1 , y n , z n ; f ] ( x n + 1 − y n ) ( x n + 1 − z n ) , n = 0 , 1 , … f x n + 1 = f y n + y n , z n ; f x n + 1 − y n + + x n + 1 , y n , z n ; f x n + 1 − y n x n + 1 − z n , n = 0 , 1 , … {:[f(x_(n+1))=f(y_(n))+[y_(n),z_(n);f](x_(n+1)-y_(n))+],[+[x_(n+1),y_(n),z_(n);f](x_(n+1)-y_(n))(x_(n+1)-z_(n))","n=0","1","dots]:}\begin{aligned} f\left(x_{n+1}\right)= & f\left(y_{n}\right)+\left[y_{n}, z_{n} ; f\right]\left(x_{n+1}-y_{n}\right)+ \\ & +\left[x_{n+1}, y_{n}, z_{n} ; f\right]\left(x_{n+1}-y_{n}\right)\left(x_{n+1}-z_{n}\right), n=0,1, \ldots \end{aligned}f(xn+1)=f(yn)+[yn,zn;f](xn+1−yn)++[xn+1,yn,zn;f](xn+1−yn)(xn+1−zn),n=0,1,…
whence, taking into acount (5), we get
f ( x n + 1 ) − f ( x ∗ ) = [ x n + 1 , y n , z n ; f ] ( x n + 1 − y n ) ( x n + 1 − z n ) , n = 0 , 1 , … , f x n + 1 − f x ∗ = x n + 1 , y n , z n ; f x n + 1 − y n x n + 1 − z n , n = 0 , 1 , … , f(x_(n+1))-f(x^(**))=[x_(n+1),y_(n),z_(n);f](x_(n+1)-y_(n))(x_(n+1)-z_(n)),n=0,1,dots,f\left(x_{n+1}\right)-f\left(x^{*}\right)=\left[x_{n+1}, y_{n}, z_{n} ; f\right]\left(x_{n+1}-y_{n}\right)\left(x_{n+1}-z_{n}\right), n=0,1, \ldots,f(xn+1)−f(x∗)=[xn+1,yn,zn;f](xn+1−yn)(xn+1−zn),n=0,1,…,
or
x n + 1 − x ∗ = [ x n + 1 , y n , z n ; f ] [ x ∗ , x n + 1 ; f ] ( x n + 1 − y n ) ( x n + 1 − z n ) , n = 0 , 1 , … x n + 1 − x ∗ = x n + 1 , y n , z n ; f x ∗ , x n + 1 ; f x n + 1 − y n x n + 1 − z n , n = 0 , 1 , … x_(n+1)-x^(**)=([x_(n+1),y_(n),z_(n);f])/([x^(**),x_(n+1);f])(x_(n+1)-y_(n))(x_(n+1)-z_(n)),n=0,1,dotsx_{n+1}-x^{*}=\frac{\left[x_{n+1}, y_{n}, z_{n} ; f\right]}{\left[x^{*}, x_{n+1} ; f\right]}\left(x_{n+1}-y_{n}\right)\left(x_{n+1}-z_{n}\right), n=0,1, \ldotsxn+1−x∗=[xn+1,yn,zn;f][x∗,xn+1;f](xn+1−yn)(xn+1−zn),n=0,1,…
The mean value formulas for divided differences lead to (11).
These estimations can be applied in connection to any of the results proved above.

3 Numerical examples

Example 8 Consider the equation
f ( x ) = e x + sin ⁡ x − 2 , x ∈ [ 0 , 1 ] f ( x ) = e x + sin ⁡ x − 2 , x ∈ [ 0 , 1 ] f(x)=e^(x)+sin x-2,x in[0,1]f(x)=e^{x}+\sin x-2, x \in[0,1]f(x)=ex+sin⁡x−2,x∈[0,1]
The derivatives of f f fff are given by
f ′ ( x ) = e x + cos ⁡ x > 0 , x ∈ [ 0 , 1 ] f ′ ′ ( x ) = e x − sin ⁡ x f ′ ( x ) = e x + cos ⁡ x > 0 , x ∈ [ 0 , 1 ] f ′ ′ ( x ) = e x − sin ⁡ x {:[f^(')(x)=e^(x)+cos x > 0","quad x in[0","1]],[f^('')(x)=e^(x)-sin x]:}\begin{aligned} f^{\prime}(x) & =e^{x}+\cos x>0, \quad x \in[0,1] \\ f^{\prime \prime}(x) & =e^{x}-\sin x \end{aligned}f′(x)=ex+cos⁡x>0,x∈[0,1]f′′(x)=ex−sin⁡x
Some elementary considerations on f ′ ′ f ′ ′ f^('')f^{\prime \prime}f′′ show that f ′ ′ ( x ) > 0 , x ∈ [ 0 , 1 ] f ′ ′ ( x ) > 0 , x ∈ [ 0 , 1 ] f^('')(x) > 0,x in[0,1]f^{\prime \prime}(x)>0, x \in[0,1]f′′(x)>0,x∈[0,1]. Since f f fff is continuous, f ′ ( x ) > 0 , x ∈ [ 0 , 1 ] f ′ ( x ) > 0 , x ∈ [ 0 , 1 ] f^(')(x) > 0,x in[0,1]f^{\prime}(x)>0, x \in[0,1]f′(x)>0,x∈[0,1] and f ( 0 ) = − 1 , f ( 1 ) = e + sin ⁡ 1 − 2 > 0 f ( 0 ) = − 1 , f ( 1 ) = e + sin ⁡ 1 − 2 > 0 f(0)=-1,f(1)=e+sin 1-2 > 0f(0)=-1, f(1)=e+\sin 1-2>0f(0)=−1,f(1)=e+sin⁡1−2>0, it follows that f f fff has a unique solution on [ 0 , 1 ] [ 0 , 1 ] [0,1][0,1][0,1].
Taking x 0 = 1 x 0 = 1 x_(0)=1x_{0}=1x0=1, the hypotheses of Theorem 2 are satisfied.
Table 1 Numerical results when solving e x + sin ⁡ x − 2 = 0 e x + sin ⁡ x − 2 = 0 e^(x)+sin x-2=0e^{x}+\sin x-2=0ex+sin⁡x−2=0
n n nnn x n x n x_(n)x_{n}xn y n y n y_(n)y_{n}yn z n z n z_(n)z_{n}zn f ( x n ) f x n f(x_(n))f\left(x_{n}\right)f(xn)
0 1.000000000000000 e + 0 1.000000000000000 e + 0 1.000000000000000e+01.000000000000000 \mathrm{e}+01.000000000000000e+0 5.213403278939761 e − 1 5.213403278939761 e − 1 5.213403278939761e-15.213403278939761 \mathrm{e}-15.213403278939761e−1 4.498799895489901 e − 1 4.498799895489901 e − 1 4.498799895489901e-14.498799895489901 \mathrm{e}-14.498799895489901e−1 1.5 e + 0 1.5 e + 0 1.5e+01.5 \mathrm{e}+01.5e+0
1 4.486920253023863 e − 1 4.486920253023863 e − 1 4.486920253023863e-14.486920253023863 \mathrm{e}-14.486920253023863e−1 4.486719164440748 e − 1 4.486719164440748 e − 1 4.486719164440748e-14.486719164440748 \mathrm{e}-14.486719164440748e−1 4.486719163512726 e − 1 4.486719163512726 e − 1 4.486719163512726e-14.486719163512726 \mathrm{e}-14.486719163512726e−1 4.9 e − 5 4.9 e − 5 4.9e-54.9 \mathrm{e}-54.9e−5
2 4.486719163512727 e − 1 4.486719163512727 e − 1 4.486719163512727e-14.486719163512727 \mathrm{e}-14.486719163512727e−1 0
n x_(n) y_(n) z_(n) f(x_(n)) 0 1.000000000000000e+0 5.213403278939761e-1 4.498799895489901e-1 1.5e+0 1 4.486920253023863e-1 4.486719164440748e-1 4.486719163512726e-1 4.9e-5 2 4.486719163512727e-1 0| $n$ | $x_{n}$ | $y_{n}$ | $z_{n}$ | $f\left(x_{n}\right)$ | | :--- | :--- | :--- | :--- | :--- | | 0 | $1.000000000000000 \mathrm{e}+0$ | $5.213403278939761 \mathrm{e}-1$ | $4.498799895489901 \mathrm{e}-1$ | $1.5 \mathrm{e}+0$ | | 1 | $4.486920253023863 \mathrm{e}-1$ | $4.486719164440748 \mathrm{e}-1$ | $4.486719163512726 \mathrm{e}-1$ | $4.9 \mathrm{e}-5$ | | 2 | $4.486719163512727 \mathrm{e}-1$ | | | 0 |
In Table 1 we present the results obtained in double precision using MATLAB.
One can easily verify that min x ∈ [ 0 , 1 ] | f ′ ( x ) | = 2 min x ∈ [ 0 , 1 ]   f ′ ( x ) = 2 min_(x in[0,1])|f^(')(x)|=2\min _{x \in[0,1]}\left|f^{\prime}(x)\right|=2minx∈[0,1]|f′(x)|=2 and max x ∈ [ 0 , 1 ] | f ′ ′ ( x ) | ≤ e max x ∈ [ 0 , 1 ]   f ′ ′ ( x ) ≤ e max_(x in[0,1])|f^('')(x)| <= e\max _{x \in[0,1]}\left|f^{\prime \prime}(x)\right| \leq emaxx∈[0,1]|f′′(x)|≤e.
Taking into account (11) we get
| x ∗ − x 2 | ≤ e 4 | x 2 − y 1 | ⋅ | x 2 − z 1 | . x ∗ − x 2 ≤ e 4 x 2 − y 1 ⋅ x 2 − z 1 . |x^(**)-x_(2)| <= (e)/(4)|x_(2)-y_(1)|*|x_(2)-z_(1)|.\left|x^{*}-x_{2}\right| \leq \frac{e}{4}\left|x_{2}-y_{1}\right| \cdot\left|x_{2}-z_{1}\right| .|x∗−x2|≤e4|x2−y1|⋅|x2−z1|.
The quantity in the right hand side is majorized by 7.0 e − 27 7.0 e − 27 7.0e-277.0 \mathrm{e}-277.0e−27, which, together with the fact that f ( x 2 ) = 0 f x 2 = 0 f(x_(2))=0f\left(x_{2}\right)=0f(x2)=0, shows that in this particular case, x ∗ x ∗ x^(**)x^{*}x∗ can be computed with accuracy higher than the machine epsilon.

Example 9

f ( x ) = ln ⁡ ( x 2 + x + 2 ) − x + 1 = 0 , x ∈ [ 4 , 5 ] . f ( x ) = ln ⁡ x 2 + x + 2 − x + 1 = 0 , x ∈ [ 4 , 5 ] . f(x)=ln(x^(2)+x+2)-x+1=0,x in[4,5].f(x)=\ln \left(x^{2}+x+2\right)-x+1=0, x \in[4,5] .f(x)=ln⁡(x2+x+2)−x+1=0,x∈[4,5].
We have
f ′ ( x ) = − x 2 + x − 1 x 2 + x + 2 < 0 , for x ∈ [ 4 , 5 ] ; f ′ ′ ( x ) = − 2 x 2 − 2 x + 1 ( x 2 + x + 2 ) 2 < 0 , for x ∈ [ 4 , 5 ] ; f ′ ( x ) = − x 2 + x − 1 x 2 + x + 2 < 0 ,  for  x ∈ [ 4 , 5 ] ; f ′ ′ ( x ) = − 2 x 2 − 2 x + 1 x 2 + x + 2 2 < 0 ,  for  x ∈ [ 4 , 5 ] ; {:[f^(')(x)=(-x^(2)+x-1)/(x^(2)+x+2) < 0","" for "x in[4","5];],[f^('')(x)=(-2x^(2)-2x+1)/((x^(2)+x+2)^(2)) < 0","" for "x in[4","5];]:}\begin{aligned} & f^{\prime}(x)=\frac{-x^{2}+x-1}{x^{2}+x+2}<0, \text { for } x \in[4,5] ; \\ & f^{\prime \prime}(x)=\frac{-2 x^{2}-2 x+1}{\left(x^{2}+x+2\right)^{2}}<0, \text { for } x \in[4,5] ; \end{aligned}f′(x)=−x2+x−1x2+x+2<0, for x∈[4,5];f′′(x)=−2x2−2x+1(x2+x+2)2<0, for x∈[4,5];
f ( 4 ) = ln ⁡ 22 − 3 > 0 f ( 4 ) = ln ⁡ 22 − 3 > 0 f(4)=ln 22-3 > 0f(4)=\ln 22-3>0f(4)=ln⁡22−3>0 and f ( 5 ) = ln ⁡ 32 − 4 < 0 f ( 5 ) = ln ⁡ 32 − 4 < 0 f(5)=ln 32-4 < 0f(5)=\ln 32-4<0f(5)=ln⁡32−4<0.
We take x 0 = 5 x 0 = 5 x_(0)=5x_{0}=5x0=5, so hypotheses of Corollary 3 are verified. The obtained results are presented in Table 2.
In this case we have min x ∈ [ 4 , 5 ] | f ′ ( x ) | > 1 3 min x ∈ [ 4 , 5 ]   f ′ ( x ) > 1 3 min_(x in[4,5])|f^(')(x)| > (1)/(3)\min _{x \in[4,5]}\left|f^{\prime}(x)\right|>\frac{1}{3}minx∈[4,5]|f′(x)|>13 and max x ∈ [ 4 , 5 ] | f ′ ′ ( x ) | ≤ 1 8 max x ∈ [ 4 , 5 ]   f ′ ′ ( x ) ≤ 1 8 max_(x in[4,5])|f^('')(x)| <= (1)/(8)\max _{x \in[4,5]}\left|f^{\prime \prime}(x)\right| \leq \frac{1}{8}maxx∈[4,5]|f′′(x)|≤18, whence, by (11) we get
| x ∗ − x 2 | ≤ 3 16 | x 2 − y 1 | ⋅ | x 2 − z 1 | . x ∗ − x 2 ≤ 3 16 x 2 − y 1 ⋅ x 2 − z 1 . |x^(**)-x_(2)| <= (3)/(16)|x_(2)-y_(1)|*|x_(2)-z_(1)|.\left|x^{*}-x_{2}\right| \leq \frac{3}{16}\left|x_{2}-y_{1}\right| \cdot\left|x_{2}-z_{1}\right| .|x∗−x2|≤316|x2−y1|⋅|x2−z1|.
The quantity in the right hand side is majorized by 1.4 e − 31 1.4 e − 31 1.4e-311.4 \mathrm{e}-311.4e−31, which, together with the fact that f ( x 2 ) = 0 f x 2 = 0 f(x_(2))=0f\left(x_{2}\right)=0f(x2)=0 shows that in this example too x ∗ x ∗ x^(**)x^{*}x∗ is computed with accuracy higher than the machine epsilon.
Table 2 Numerical results when solving ln ⁡ ( x 2 + x + 2 ) − x + 1 = 0 ln ⁡ x 2 + x + 2 − x + 1 = 0 ln(x^(2)+x+2)-x+1=0\ln \left(x^{2}+x+2\right)-x+1=0ln⁡(x2+x+2)−x+1=0
n n nnn x n x n x_(n)x_{n}xn y n y n y_(n)y_{n}yn z n z n z_(n)z_{n}zn f ( x n ) f x n f(x_(n))f\left(x_{n}\right)f(xn)
0 5.000000000000000 e + 0 5.000000000000000 e + 0 5.000000000000000e+05.000000000000000 \mathrm{e}+05.000000000000000e+0 4.185883280456726 e + 0 4.185883280456726 e + 0 4.185883280456726e+04.185883280456726 \mathrm{e}+04.185883280456726e+0 4.152656878948953 e + 0 4.152656878948953 e + 0 4.152656878948953e+04.152656878948953 \mathrm{e}+04.152656878948953e+0 − 5.3 e − 1 − 5.3 e − 1 -5.3e-1-5.3 \mathrm{e}-1−5.3e−1
1 4.152590868900850 e + 0 4.152590868900850 e + 0 4.152590868900850e+04.152590868900850 \mathrm{e}+04.152590868900850e+0 4.152590736757159 e + 0 4.152590736757159 e + 0 4.152590736757159e+04.152590736757159 \mathrm{e}+04.152590736757159e+0 4.152590736757158 e + 0 4.152590736757158 e + 0 4.152590736757158e+04.152590736757158 \mathrm{e}+04.152590736757158e+0 − 7.9 e − 8 − 7.9 e − 8 -7.9e-8-7.9 \mathrm{e}-8−7.9e−8
2 4.152590736757158 e + 0 4.152590736757158 e + 0 4.152590736757158e+04.152590736757158 \mathrm{e}+04.152590736757158e+0 0
n x_(n) y_(n) z_(n) f(x_(n)) 0 5.000000000000000e+0 4.185883280456726e+0 4.152656878948953e+0 -5.3e-1 1 4.152590868900850e+0 4.152590736757159e+0 4.152590736757158e+0 -7.9e-8 2 4.152590736757158e+0 0| $n$ | $x_{n}$ | $y_{n}$ | $z_{n}$ | $f\left(x_{n}\right)$ | | :--- | :--- | :--- | :--- | :--- | | 0 | $5.000000000000000 \mathrm{e}+0$ | $4.185883280456726 \mathrm{e}+0$ | $4.152656878948953 \mathrm{e}+0$ | $-5.3 \mathrm{e}-1$ | | 1 | $4.152590868900850 \mathrm{e}+0$ | $4.152590736757159 \mathrm{e}+0$ | $4.152590736757158 \mathrm{e}+0$ | $-7.9 \mathrm{e}-8$ | | 2 | $4.152590736757158 \mathrm{e}+0$ | | | 0 |
We make the following comments regarding the convergence order of the obtained sequences. Since they are monotonic in these two examples, the quotient convergence factors [9, ch. 9] can be determined by (9), taking into account the mean value formulas for divided differences, as
(12) Q 6 { x k } = lim k → ∞ | x k + 1 − x ∗ | | x k − x ∗ | 6 = ( f ′ ′ ( x ∗ ) ) 5 32 ( f ′ ( x ∗ ) ) 5 (12) Q 6 x k = lim k → ∞   x k + 1 − x ∗ x k − x ∗ 6 = f ′ ′ x ∗ 5 32 f ′ x ∗ 5 {:(12)Q_(6){x_(k)}=lim_(k rarr oo)(|x_(k+1)-x^(**)|)/(|x_(k)-x^(**)|^(6))=((f^('')(x^(**)))^(5))/(32(f^(')(x^(**)))^(5)):}\begin{equation*} Q_{6}\left\{x_{k}\right\}=\lim _{k \rightarrow \infty} \frac{\left|x_{k+1}-x^{*}\right|}{\left|x_{k}-x^{*}\right|^{6}}=\frac{\left(f^{\prime \prime}\left(x^{*}\right)\right)^{5}}{32\left(f^{\prime}\left(x^{*}\right)\right)^{5}} \tag{12} \end{equation*}(12)Q6{xk}=limk→∞|xk+1−x∗||xk−x∗|6=(f′′(x∗))532(f′(x∗))5
Therefore, since in both examples f ′ ′ ( x ∗ ) ≠ 0 f ′ ′ x ∗ ≠ 0 f^('')(x^(**))!=0f^{\prime \prime}\left(x^{*}\right) \neq 0f′′(x∗)≠0, the q q qqq-convergence order is exactly 6 . However, the above quantity requires the knowledge of the solution x ∗ x ∗ x^(**)x^{*}x∗. In [4] and [5], the asymptotical constant Q 6 { x k } Q 6 x k Q_(6){x_(k)}Q_{6}\left\{x_{k}\right\}Q6{xk} was approximated by some quantities computable at each step:
(13) | x k + 1 − x k | | x k − x k − 1 | 6 , k = 1 , 2 , … (13) x k + 1 − x k x k − x k − 1 6 , k = 1 , 2 , … {:(13)(|x_(k+1)-x_(k)|)/(|x_(k)-x_(k-1)|^(6))","k=1","2","dots:}\begin{equation*} \frac{\left|x_{k+1}-x_{k}\right|}{\left|x_{k}-x_{k-1}\right|^{6}}, k=1,2, \ldots \tag{13} \end{equation*}(13)|xk+1−xk||xk−xk−1|6,k=1,2,…
In Example 8, formula (12) (with x ∗ x ∗ x^(**)x^{*}x∗ considered as x 2 x 2 x_(2)x_{2}x2 ) yields the value 6.3e-4, while formula (13) for k = 1 k = 1 k=1k=1k=1 yields 7.1 e − 4 7.1 e − 4 7.1e-47.1 \mathrm{e}-47.1e−4, i.e., two close quantities. These values are also close in Example 9, where we obtain 1.0e-6, respectively 3.5e-7.
Some other formulas to determine the convergence order were considered in [21]:
p ≈ ln ⁡ | ( x k + 1 − x ∗ ) / ( x k − x ∗ ) | ln ⁡ | ( x k − x ∗ ) / ( x k − 1 − x ∗ ) | , k = 1 , 2 , … p ≈ ln ⁡ x k + 1 − x ∗ / x k − x ∗ ln ⁡ x k − x ∗ / x k − 1 − x ∗ , k = 1 , 2 , … p~~(ln|(x_(k+1)-x^(**))//(x_(k)-x^(**))|)/(ln|(x_(k)-x^(**))//(x_(k-1)-x^(**))|),k=1,2,dotsp \approx \frac{\ln \left|\left(x_{k+1}-x^{*}\right) /\left(x_{k}-x^{*}\right)\right|}{\ln \left|\left(x_{k}-x^{*}\right) /\left(x_{k-1}-x^{*}\right)\right|}, k=1,2, \ldotsp≈ln⁡|(xk+1−x∗)/(xk−x∗)|ln⁡|(xk−x∗)/(xk−1−x∗)|,k=1,2,…
subsequently approximated in [5] by
p ≈ ln ⁡ | ( x k + 1 − x k ) / ( x k − x k − 1 ) | ln ⁡ | ( x k − x k − 1 ) / ( x k − 1 − x k − 2 ) | , k = 2 , 3 , … p ≈ ln ⁡ x k + 1 − x k / x k − x k − 1 ln ⁡ x k − x k − 1 / x k − 1 − x k − 2 , k = 2 , 3 , … p~~(ln|(x_(k+1)-x_(k))//(x_(k)-x_(k-1))|)/(ln|(x_(k)-x_(k-1))//(x_(k-1)-x_(k-2))|),k=2,3,dotsp \approx \frac{\ln \left|\left(x_{k+1}-x_{k}\right) /\left(x_{k}-x_{k-1}\right)\right|}{\ln \left|\left(x_{k}-x_{k-1}\right) /\left(x_{k-1}-x_{k-2}\right)\right|}, k=2,3, \ldotsp≈ln⁡|(xk+1−xk)/(xk−xk−1)|ln⁡|(xk−xk−1)/(xk−1−xk−2)|,k=2,3,…
but since in the presented examples the solution was approximated in only three steps (the convergence order is high), we cannot use these formulas.

References

  1. Amat, S., Busquier, S.: A two step Steffenssen's method under modified convergence conditions. J. Math. Anal. Appl. 324, 1084-1092 (2006)
  2. Beltyukov, B.A.: An analogue of the Aitken-Steffensen method with controlled step. URSS Comput. Math. Math. Phys. 27(3), 103-112 (1987)
  3. Chun, C.: A geometric construction of iterative formulas of order three. Appl. Math. Lett. 23, 512-516 (2010)
  4. Cordero, A., Torregrosa, J.R.: Variants of Newton's method for functions of several variables. Appl. Math. Comput. 183, 199-2008 (2006)
  5. Cordero, A., Torregrosa, J.R.: Variants of Newton's method using fifth order quadrature formulas. Appl. Math. Comput. 190, 686-698 (2007)
  6. Cordero A., Torregrosa R.J.: A class of Steffenssen type method with optimal order of convergence. Appl. Math. Comput. 217, 7653-7659 (2011)
  7. Hongmin, R., Qingbio, W., Welhong, B.: A class of two-step Steffensen type methods with fourth order convergence. Appl. Math. Comput. 209(2), 206-210 (2009)
  8. Jain, P.: Steffensen type method for solving non-linear equations. Appl. Math. Comput. 194, 527-533 (2007)
  9. Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)
  10. Ostrowski, M.A.: Solution of Equations in Euclidian and Banach Spaces. Academic Press, New York and London (1973)
  11. Păvăloiu, I.: Approximation of the root of equations by Aitken-Steffensen-type monotonic sequences. Calcolo 32, 69-82 (1995)
  12. Păvăloiu, I., Cătinaş, E.: On a Steffensen-Hermite method of order three. Appl. Math. Comput. 215(7), 2663-2672 (2009)
  13. Păvăloiu, I., Cătinaş, E.: On a Steffensen type method. In: Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Proceedings, pp. 369-375 (2007)
  14. Păvăloiu, I.: Optimal algorithms, concerning the solving of equations by interpolation. In: Popoviciu, E. (ed.) Research on Theory of Allure, Approximation, Convexity and Optimization, Editura Srima, Cluj-Napoca, pp. 222-248 (1999)
  15. Păvăloiu, I.: Aitken-Steffensen-type method for nondifferentiable functions (I). Rev. Anal. Numér. Theor. Approx. 31(1), 109-114 (2002)
  16. Păvăloiu, I.: Aitken-Steffensen-type method for nonsmooth functions (II). Rev. Anal. Numér. Théor. Approx. 31(2), 195-198 (2002)
  17. Păvăloiu, I.: Aitken-Steffensen-type method for nonsmooth functions (III). Rev. Anal. Numér. Théor. Approx. 32(1), 73-78 (2003)
  18. Quan, Z., Peng, Z., Li, Z., Wenchao, M.: Variants of Steffensen secant method and applications. Appl. Math. Comput. 216(12), 3486-3496 (2010)
  19. Sharma, R.J.: A composite thid order Newton-Steffensen method for solving nonlinear equations. Appl. Math. Comput. 169, 242-246 (2005)
  20. Traub, Y.F.: Iterative Method for Solution of Equations. Prentice-Hall, Englewood Cliffs, NJ (1964)
  21. Weerakoon, S., Fernando, T.G.I.: A variant of Newton's method with accelerated third-order convergence. Appl. Math. Lett. 13(8), 87-93 (2000)
  1. I. Păvăloiu ⋅ E. Cătinaş ( ⊠ ⊠ ⊠\boxtimes⊠ )
    "Tiberiu Popoviciu" Institute of Numerical Analysis, Romanian Academy, P.O. Box 68-1, Cluj-Napoca, Romania
    e-mail: ecatinas@ictp.acad.ro
    I. Păvăloiu
    e-mail: pavaloiu@ictp.acad.ro
2013

Related Posts