On an Aitken-Steffensen-Newton type method

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

Abstract

We consider an Aitken-Steffensen type method in which the nodes are controlled by Newton and two-step Newton iterations.

We prove a local convergence result showing the -convergence order 7 of the iterations. Under certain supplementary conditions, we obtain monotone convergence of the iterations, providing an alternative to the usual ball attraction theorems.

Numerical examples show that this method may, in some cases, have larger (possibly sided) convergence domains than other methods with similar convergence orders.

Authors

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

Keywords

Cite this paper as

I. Păvăloiu, On an Aitken-Steffensen-Newton type method, Carpathian J. Math. 34 (2018) no. 1, pp. 85-92.

PDF

Scanned paper.

Scanned paper also available on JSTOR.

LaTeX-PDF version of the paper.

About this paper

Journal

Carpathian Journal of Mathematics

Publisher Name

Technical University Cluj-Napoca

JSTOR permalink

https://www.jstor.org/stable/90021606

Print ISSN

1584-2851

Online ISSN

1843-4401

Paper (preprint) in HTML form

2018-Pavaloiu-Carpathian-On-an-Aitken-Steffensen-Newton

On an Aitken-Steffensen-Newton type method

ION PĂVĂLOIU

Abstract

We consider an Aitken-Steffensen type method in which the nodes are controlled by Newton and two-step Newton iterations. We prove a local convergence result showing the q q qqq-convergence order 7 of the iterations. Under certain supplementary conditions, we obtain monotone convergence of the iterations, providing an alternative to the usual ball attraction theorems.

Numerical examples show that this method may, in some cases, have larger (possibly sided) convergence domains than other methods with similar convergence orders.

1. Introduction

We are interested in solving the nonlinear equation
(1.1) f ( x ) = 0 (1.1) f ( x ) = 0 {:(1.1)f(x)=0:}\begin{equation*} f(x)=0 \tag{1.1} \end{equation*}(1.1)f(x)=0
where f : [ a , b ] → R f : [ a , b ] → R f:[a,b]rarrRf:[a, b] \rightarrow \mathbb{R}f:[a,b]→R is given. We consider two auxiliary functions 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] such that the above equation is equivalent to the following ones
(1.2) x − g i ( x ) = 0 , i = 1 , 2 (1.2) x − g i ( x ) = 0 , i = 1 , 2 {:(1.2)x-g_(i)(x)=0","quad i=1","2:}\begin{equation*} x-g_{i}(x)=0, \quad i=1,2 \tag{1.2} \end{equation*}(1.2)x−gi(x)=0,i=1,2
We assume
A) equation (1.1) has a solution x ∗ ∈ ] a , b [ x ∗ ∈ a , b [ {:x^(**)in]a,b[\left.x^{*} \in\right] a, b[x∗∈]a,b[.
Obviously, x ∗ x ∗ x^(**)x^{*}x∗ is a fixed point of g 1 g 1 g_(1)g_{1}g1 and g 2 g 2 g_(2)g_{2}g2.
A well-known method for approximating x ∗ x ∗ x^(**)x^{*}x∗ is the chord method:
x n + 1 = x n − f ( x n ) [ x n − 1 , x n ; f ] , n = 0 , 1 , … , x 0 , x 1 ∈ [ a , b ] x n + 1 = x n − f x n x n − 1 , x n ; f , n = 0 , 1 , … , x 0 , x 1 ∈ [ a , b ] x_(n+1)=x_(n)-(f(x_(n)))/([x_(n-1),x_(n);f]),quad n=0,1,dots,x_(0),x_(1)in[a,b]x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n-1}, x_{n} ; f\right]}, \quad n=0,1, \ldots, x_{0}, x_{1} \in[a, b]xn+1=xn−f(xn)[xn−1,xn;f],n=0,1,…,x0,x1∈[a,b]
where [ x , y ; f x , y ; f x,y;fx, y ; fx,y;f ] denotes the first order divided difference of f f fff at the nodes x , y x , y x,yx, yx,y.
If one of the nodes in the above formula is controlled by g 1 g 1 g_(1)g_{1}g1, one obtains the Steffensen method, given by (see [1], [2], [4], [5], [8], [10], [11], [18], [22], [24], [25])
x n + 1 = x n − f ( x n ) [ x n , g 1 ( x n ) ; f ] , n = 0 , 1 , … , x 0 ∈ [ a , b ] x n + 1 = x n − f x n x n , g 1 x n ; f , n = 0 , 1 , … , x 0 ∈ [ a , b ] x_(n+1)=x_(n)-(f(x_(n)))/([x_(n),g_(1)(x_(n));f]),quad n=0,1,dots,x_(0)in[a,b]x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n}, g_{1}\left(x_{n}\right) ; f\right]}, \quad n=0,1, \ldots, x_{0} \in[a, b]xn+1=xn−f(xn)[xn,g1(xn);f],n=0,1,…,x0∈[a,b]
The Aitken method is obtained if in the above relation f ( x ) f ( x ) f(x)f(x)f(x) is replaced by h ( x ) = x − g 2 ( x ) h ( x ) = x − g 2 ( x ) h(x)=x-g_(2)(x)h(x)=x-g_{2}(x)h(x)=x−g2(x) (see [1], [14], [16]).
A more general Aitken-type method was studied in [16], [17], [21]:
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 ] 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 ] x_(n+1)=g_(1)(x_(n))-(f(g_(1)(x_(n))))/([g_(1)(x_(n)),g_(2)(x_(n));f]),quad n=0,1,dots,x_(0)in[a,b]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]}, \quad n=0,1, \ldots, x_{0} \in[a, b]xn+1=g1(xn)−f(g1(xn))[g1(xn),g2(xn);f],n=0,1,…,x0∈[a,b]
Some even more general methods, called Aitken-Steffensen, have been studied in [17], [20]:
x n + 1 = g 1 ( x n ) − f ( g 1 ( x n ) ) [ g 1 ( x n ) , g 2 ( g 1 ( x n ) ) ; f ] , n = 0 , 1 , … , x 0 ∈ [ a , b ] x n + 1 = g 1 x n − f g 1 x n g 1 x n , g 2 g 1 x n ; f , n = 0 , 1 , … , x 0 ∈ [ a , b ] x_(n+1)=g_(1)(x_(n))-(f(g_(1)(x_(n))))/([g_(1)(x_(n)),g_(2)(g_(1)(x_(n)));f]),quad n=0,1,dots,x_(0)in[a,b]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(g_{1}\left(x_{n}\right)\right) ; f\right]}, \quad n=0,1, \ldots, x_{0} \in[a, b]xn+1=g1(xn)−f(g1(xn))[g1(xn),g2(g1(xn));f],n=0,1,…,x0∈[a,b]
Considering the inverse interpolatory polynomial of degree 2, one can obtain methods similar to the above ones, studied in [19]-[20]. In this paper we consider again this polynomial. We assume that J = f ( [ a , b ] ) J = f ( [ a , b ] ) J=f([a,b])J=f([a, b])J=f([a,b]) and that f : [ a , b ] → J f : [ a , b ] → J f:[a,b]rarr Jf:[a, b] \rightarrow Jf:[a,b]→J is bijective, so there exists the inverse of f , f − 1 : J → [ a , b ] f , f − 1 : J → [ a , b ] f,f^(-1):J rarr[a,b]f, f^{-1}: J \rightarrow[a, b]f,f−1:J→[a,b]. Obviously, x ∗ = f − 1 ( 0 ) x ∗ = f − 1 ( 0 ) x^(**)=f^(-1)(0)x^{*}=f^{-1}(0)x∗=f−1(0). Let a i ∈ [ a , b ] a i ∈ [ a , b ] a_(i)in[a,b]a_{i} \in[a, b]ai∈[a,b] and b i = f ( a i ) b i = f a i b_(i)=f(a_(i))b_{i}=f\left(a_{i}\right)bi=f(ai), i = 1 , 2 , 3 i = 1 , 2 , 3 i=1,2,3i=1,2,3i=1,2,3.
Denote by P P PPP the interpolation polynomial for f − 1 f − 1 f^(-1)f^{-1}f−1, determined by the nodes b 1 , b 2 , b 3 b 1 , b 2 , b 3 b_(1),b_(2),b_(3)b_{1}, b_{2}, b_{3}b1,b2,b3 and values a 1 , a 2 , a 3 a 1 , a 2 , a 3 a_(1),a_(2),a_(3)a_{1}, a_{2}, a_{3}a1,a2,a3 (see, e.g., [19]-[20]):
(1.3) P ( y ) = a 1 + [ b 1 , b 2 ; f − 1 ] ( y − b 1 ) + [ b 1 , b 2 , b 3 ; f − 1 ] ( y − b 1 ) ( y − b 2 ) . (1.3) P ( y ) = a 1 + b 1 , b 2 ; f − 1 y − b 1 + b 1 , b 2 , b 3 ; f − 1 y − b 1 y − b 2 . {:(1.3)P(y)=a_(1)+[b_(1),b_(2);f^(-1)](y-b_(1))+[b_(1),b_(2),b_(3);f^(-1)](y-b_(1))(y-b_(2)).:}\begin{equation*} P(y)=a_{1}+\left[b_{1}, b_{2} ; f^{-1}\right]\left(y-b_{1}\right)+\left[b_{1}, b_{2}, b_{3} ; f^{-1}\right]\left(y-b_{1}\right)\left(y-b_{2}\right) . \tag{1.3} \end{equation*}(1.3)P(y)=a1+[b1,b2;f−1](y−b1)+[b1,b2,b3;f−1](y−b1)(y−b2).
The solution x ∗ x ∗ x^(**)x^{*}x∗ can be approximated by
(1.4) P ( 0 ) = a 1 − [ b 1 , b 2 ; f − 1 ] b 1 + [ b 1 , b 2 , b 3 ; f − 1 ] b 1 b 2 , (1.4) P ( 0 ) = a 1 − b 1 , b 2 ; f − 1 b 1 + b 1 , b 2 , b 3 ; f − 1 b 1 b 2 , {:(1.4)P(0)=a_(1)-[b_(1),b_(2);f^(-1)]b_(1)+[b_(1),b_(2),b_(3);f^(-1)]b_(1)b_(2)",":}\begin{equation*} P(0)=a_{1}-\left[b_{1}, b_{2} ; f^{-1}\right] b_{1}+\left[b_{1}, b_{2}, b_{3} ; f^{-1}\right] b_{1} b_{2}, \tag{1.4} \end{equation*}(1.4)P(0)=a1−[b1,b2;f−1]b1+[b1,b2,b3;f−1]b1b2,
and taking into account that the divided differences of order 1 and 2 satisfy respectively the following relations:
[ b i , b j ; f − 1 ] = 1 [ a i , a j ; f ] , i , j = 1 , 3 ― , i ≠ j [ b 1 , b 2 , b 3 ; f − 1 ] = − [ a 1 , a 2 , a 3 ; f ] [ a 1 , a 2 ; f ] [ a 2 , a 3 ; f ] [ a 1 , a 3 ; f ] b i , b j ; f − 1 = 1 a i , a j ; f , i , j = 1 , 3 ¯ , i ≠ j b 1 , b 2 , b 3 ; f − 1 = − a 1 , a 2 , a 3 ; f a 1 , a 2 ; f a 2 , a 3 ; f a 1 , a 3 ; f {:[[b_(i),b_(j);f^(-1)]=(1)/([a_(i),a_(j);f])","quad i","j= bar(1,3)","i!=j],[[b_(1),b_(2),b_(3);f^(-1)]=-([a_(1),a_(2),a_(3);f])/([a_(1),a_(2);f][a_(2),a_(3);f][a_(1),a_(3);f])]:}\begin{aligned} {\left[b_{i}, b_{j} ; f^{-1}\right] } & =\frac{1}{\left[a_{i}, a_{j} ; f\right]}, \quad i, j=\overline{1,3}, i \neq j \\ {\left[b_{1}, b_{2}, b_{3} ; f^{-1}\right] } & =-\frac{\left[a_{1}, a_{2}, a_{3} ; f\right]}{\left[a_{1}, a_{2} ; f\right]\left[a_{2}, a_{3} ; f\right]\left[a_{1}, a_{3} ; f\right]} \end{aligned}[bi,bj;f−1]=1[ai,aj;f],i,j=1,3―,i≠j[b1,b2,b3;f−1]=−[a1,a2,a3;f][a1,a2;f][a2,a3;f][a1,a3;f]
relation (1.4) becomes
P ( 0 ) = a 1 − f ( a 1 ) [ a 1 , a 2 ; f ] − [ a 1 , a 2 , a 3 ; f ] f ( a 1 ) f ( a 2 ) [ a 1 , a 2 ; f ] [ a 1 , a 3 ; f ] [ a 2 , a 3 ; f ] . P ( 0 ) = a 1 − f a 1 a 1 , a 2 ; f − a 1 , a 2 , a 3 ; f f a 1 f a 2 a 1 , a 2 ; f a 1 , a 3 ; f a 2 , a 3 ; f . P(0)=a_(1)-(f(a_(1)))/([a_(1),a_(2);f])-([a_(1),a_(2),a_(3);f]f(a_(1))f(a_(2)))/([a_(1),a_(2);f][a_(1),a_(3);f][a_(2),a_(3);f]).P(0)=a_{1}-\frac{f\left(a_{1}\right)}{\left[a_{1}, a_{2} ; f\right]}-\frac{\left[a_{1}, a_{2}, a_{3} ; f\right] f\left(a_{1}\right) f\left(a_{2}\right)}{\left[a_{1}, a_{2} ; f\right]\left[a_{1}, a_{3} ; f\right]\left[a_{2}, a_{3} ; f\right]} .P(0)=a1−f(a1)[a1,a2;f]−[a1,a2,a3;f]f(a1)f(a2)[a1,a2;f][a1,a3;f][a2,a3;f].
Given an approximation x n ∈ [ a , b ] x n ∈ [ a , b ] x_(n)in[a,b]x_{n} \in[a, b]xn∈[a,b] for x ∗ x ∗ x^(**)x^{*}x∗, we take a 1 = x n , a 2 = g 1 ( x n ) , a 3 = g 2 ( x n ) a 1 = x n , a 2 = g 1 x n , a 3 = g 2 x n a_(1)=x_(n),a_(2)=g_(1)(x_(n)),a_(3)=g_(2)(x_(n))a_{1}=x_{n}, a_{2}=g_{1}\left(x_{n}\right), a_{3}=g_{2}\left(x_{n}\right)a1=xn,a2=g1(xn),a3=g2(xn), and we obtain the next approximation by
(1.5) x n + 1 = x n − f ( x n ) [ x n , g 1 ( x n ) ; f ] − [ x n , g 1 ( x n ) , g 2 ( x n ) ; f ] f ( x n ) f ( g 1 ( x n ) ) [ x n , g 1 ( x n ) ; f ] [ x n , g 2 ( x n ) ; f ] [ g 1 ( x n ) , g 2 ( x n ) ; f ] . (1.5) x n + 1 = x n − f x n x n , g 1 x n ; f − x n , g 1 x n , g 2 x n ; f f x n f g 1 x n x n , g 1 x n ; f x n , g 2 x n ; f g 1 x n , g 2 x n ; f . {:(1.5)x_(n+1)=x_(n)-(f(x_(n)))/([x_(n),g_(1)(x_(n));f])-([x_(n),g_(1)(x_(n)),g_(2)(x_(n));f]f(x_(n))f(g_(1)(x_(n))))/([x_(n),g_(1)(x_(n));f][x_(n),g_(2)(x_(n));f][g_(1)(x_(n)),g_(2)(x_(n));f]).:}\begin{equation*} x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n}, g_{1}\left(x_{n}\right) ; f\right]}-\frac{\left[x_{n}, g_{1}\left(x_{n}\right), g_{2}\left(x_{n}\right) ; f\right] f\left(x_{n}\right) f\left(g_{1}\left(x_{n}\right)\right)}{\left[x_{n}, g_{1}\left(x_{n}\right) ; f\right]\left[x_{n}, g_{2}\left(x_{n}\right) ; f\right]\left[g_{1}\left(x_{n}\right), g_{2}\left(x_{n}\right) ; f\right]} . \tag{1.5} \end{equation*}(1.5)xn+1=xn−f(xn)[xn,g1(xn);f]−[xn,g1(xn),g2(xn);f]f(xn)f(g1(xn))[xn,g1(xn);f][xn,g2(xn);f][g1(xn),g2(xn);f].
In [19] we have studied the case when in (1.5) is taken g 1 ( x ) = x − λ f ( x ) , λ ∈ R g 1 ( x ) = x − λ f ( x ) , λ ∈ R g_(1)(x)=x-lambda f(x),lambda inRg_{1}(x)=x-\lambda f(x), \lambda \in \mathbb{R}g1(x)=x−λf(x),λ∈R a fixed parameter, and 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 have obtained conditions assuring the monotone convergence of the sequences ( x n ) n ≥ 0 x n n ≥ 0 (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0}(xn)n≥0 and ( g 1 ( x n ) ) n ≥ 0 g 1 x n n ≥ 0 (g_(1)(x_(n)))_(n >= 0)\left(g_{1}\left(x_{n}\right)\right)_{n \geq 0}(g1(xn))n≥0.
In this paper we consider the case when g 1 g 1 g_(1)g_{1}g1 is given by the the Newton iteration
g 1 ( x ) = x − f ( x ) f ′ ( x ) g 1 ( x ) = x − f ( x ) f ′ ( x ) g_(1)(x)=x-(f(x))/(f^(')(x))g_{1}(x)=x-\frac{f(x)}{f^{\prime}(x)}g1(x)=x−f(x)f′(x)
while g 2 g 2 g_(2)g_{2}g2 is given by the two-step Newton iteration: 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)).
From (1.5) we therefore obtain the following iterations:
(1.6) y n = x n − f ( x n ) f ′ ( x n ) , z n = y n − f ( y n ) f ′ ( y n ) , x n + 1 = x n − f ( x n ) [ x n , y n ; f ] − [ x n , y n , z n ; f ] f ( x n ) f ( y n ) [ x n , y n ; f ] [ x n , z n ; f ] [ y n , z n ; f ] , n = 0 , 1 , … , x 0 ∈ [ a , b ] (1.6) y n = x n − f x n f ′ x n , z n = y n − f y n f ′ y n , x n + 1 = x n − f x n x n , y n ; f − x n , y n , z n ; f f x n f y n x n , y n ; f x n , z n ; f y n , z n ; f , n = 0 , 1 , … , x 0 ∈ [ a , b ] {:[(1.6)y_(n)=x_(n)-(f(x_(n)))/(f^(')(x_(n)))","],[z_(n)=y_(n)-(f(y_(n)))/(f^(')(y_(n)))","],[x_(n+1)=x_(n)-(f(x_(n)))/([x_(n),y_(n);f])-([x_(n),y_(n),z_(n);f]f(x_(n))f(y_(n)))/([x_(n),y_(n);f][x_(n),z_(n);f][y_(n),z_(n);f])","quad 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)}, \tag{1.6}\\ z_{n} & =y_{n}-\frac{f\left(y_{n}\right)}{f^{\prime}\left(y_{n}\right)}, \\ x_{n+1} & =x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n}, y_{n} ; f\right]}-\frac{\left[x_{n}, y_{n}, z_{n} ; f\right] f\left(x_{n}\right) f\left(y_{n}\right)}{\left[x_{n}, y_{n} ; f\right]\left[x_{n}, z_{n} ; f\right]\left[y_{n}, z_{n} ; f\right]}, \quad n=0,1, \ldots, x_{0} \in[a, b] \end{align*}(1.6)yn=xn−f(xn)f′(xn),zn=yn−f(yn)f′(yn),xn+1=xn−f(xn)[xn,yn;f]−[xn,yn,zn;f]f(xn)f(yn)[xn,yn;f][xn,zn;f][yn,zn;f],n=0,1,…,x0∈[a,b]
which we call Aitken-Steffensen-Newton iterations.
At this point we notice that the above formula has six equivalent writings, since the interpolation polynomial P P PPP is the same, no matter the order of the three interpolation nodes. We shall use this fact in the proof of Theorem 3.2.
In Section 2 we provide a local convergence result for these iterates, while in Section 3 we obtain monotone convergence of the iterates under certain supplementary conditions
(Fourier type, convexity) on f f fff. The last section contains some numerical examples, which confirm the theory.

2. Local convergence of the iterations

We shall denote by I a 1 , a 2 , a 3 I a 1 , a 2 , a 3 I_(a_(1),a_(2),a_(3))I_{a_{1}, a_{2}, a_{3}}Ia1,a2,a3 the smallest open interval determined by the numbers a 1 , a 2 , a 3 ∈ [ a , b ] a 1 , a 2 , a 3 ∈ [ a , b ] a_(1),a_(2),a_(3)in[a,b]a_{1}, a_{2}, a_{3} \in[a, b]a1,a2,a3∈[a,b] and by E f E f E_(f)E_{f}Ef the following expression
E f ( x ) := 3 f ′ ′ ( x ) 2 − f ′ ( x ) f ′ ′ ′ ( x ) . E f ( x ) := 3 f ′ ′ ( x ) 2 − f ′ ( x ) f ′ ′ ′ ( x ) . E_(f)(x):=3f^('')(x)^(2)-f^(')(x)f^(''')(x).E_{f}(x):=3 f^{\prime \prime}(x)^{2}-f^{\prime}(x) f^{\prime \prime \prime}(x) .Ef(x):=3f′′(x)2−f′(x)f′′′(x).
We obtain the following local convergence result.
Theorem 2.1. Assume that hypotheses A A AAA ) and
B) f ∈ C 3 [ a , b ] f ∈ C 3 [ a , b ] f inC^(3)[a,b]f \in C^{3}[a, b]f∈C3[a,b], and f ′ ( x ) ≠ 0 , ∀ x ∈ [ a , b ] f ′ ( x ) ≠ 0 , ∀ x ∈ [ a , b ] f^(')(x)!=0,AA x in[a,b]f^{\prime}(x) \neq 0, \forall x \in[a, b]f′(x)≠0,∀x∈[a,b],
hold. Then the Aitken-Steffensen-Newton method converges locally to x ∗ x ∗ x^(**)x^{*}x∗, i.e., for any x 0 x 0 x_(0)x_{0}x0 sufficiently close to x ∗ x ∗ x^(**)x^{*}x∗, the iterations ( 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.6) are well defined and converge to x ∗ x ∗ x^(**)x^{*}x∗. Moreover, the following estimates hold:
(2.7) x ∗ − x n + 1 = E f ( ξ n ) f ′ ′ ( θ n ) 3 f ′ ′ ( μ n ) f ′ ( α n ) f ′ ( β n ) f ′ ( γ n ) 96 f ′ ( ξ n ) 5 f ′ ( x n ) 3 f ′ ( y n ) ( x ∗ − x n ) 7 (2.7) x ∗ − x n + 1 = E f ξ n f ′ ′ θ n 3 f ′ ′ μ n f ′ α n f ′ β n f ′ γ n 96 f ′ ξ n 5 f ′ x n 3 f ′ y n x ∗ − x n 7 {:(2.7)x^(**)-x_(n+1)=(E_(f)(xi_(n))f^('')(theta_(n))^(3)f^('')(mu_(n))f^(')(alpha_(n))f^(')(beta_(n))f^(')(gamma_(n)))/(96f^(')(xi_(n))^(5)f^(')(x_(n))^(3)f^(')(y_(n)))(x^(**)-x_(n))^(7):}\begin{equation*} x^{*}-x_{n+1}=\frac{E_{f}\left(\xi_{n}\right) f^{\prime \prime}\left(\theta_{n}\right)^{3} f^{\prime \prime}\left(\mu_{n}\right) f^{\prime}\left(\alpha_{n}\right) f^{\prime}\left(\beta_{n}\right) f^{\prime}\left(\gamma_{n}\right)}{96 f^{\prime}\left(\xi_{n}\right)^{5} f^{\prime}\left(x_{n}\right)^{3} f^{\prime}\left(y_{n}\right)}\left(x^{*}-x_{n}\right)^{7} \tag{2.7} \end{equation*}(2.7)x∗−xn+1=Ef(ξn)f′′(θn)3f′′(μn)f′(αn)f′(βn)f′(γn)96f′(ξn)5f′(xn)3f′(yn)(x∗−xn)7
with some ξ n ∈ I x ∗ , x n , y n , z n , θ n , α n ∈ I x ∗ , x n , μ n , β n ∈ I x ∗ , y n , γ n ∈ I x ∗ , z n ξ n ∈ I x ∗ , x n , y n , z n , θ n , α n ∈ I x ∗ , x n , μ n , β n ∈ I x ∗ , y n , γ n ∈ I x ∗ , z n xi_(n)inI_(x^(**),x_(n),y_(n),z_(n)),theta_(n),alpha_(n)inI_(x^(**),x_(n)),mu_(n),beta_(n)inI_(x^(**),y_(n)),gamma_(n)inI_(x^(**),z_(n))\xi_{n} \in I_{x^{*}, x_{n}, y_{n}, z_{n}}, \theta_{n}, \alpha_{n} \in I_{x^{*}, x_{n}}, \mu_{n}, \beta_{n} \in I_{x^{*}, y_{n}}, \gamma_{n} \in I_{x^{*}, z_{n}}ξn∈Ix∗,xn,yn,zn,θn,αn∈Ix∗,xn,μn,βn∈Ix∗,yn,γn∈Ix∗,zn; this shows that the method attains convergence with q q qqq-order at least 7 , with asymptotic constant given by
C = E f ( x ∗ ) f ′ ′ ( x ∗ ) 4 96 f ′ ( x ∗ ) 6 C = E f x ∗ f ′ ′ x ∗ 4 96 f ′ x ∗ 6 C=(E_(f)(x^(**))f^('')(x^(**))^(4))/(96f^(')(x^(**))^(6))\mathcal{C}=\frac{E_{f}\left(x^{*}\right) f^{\prime \prime}\left(x^{*}\right)^{4}}{96 f^{\prime}\left(x^{*}\right)^{6}}C=Ef(x∗)f′′(x∗)496f′(x∗)6
Proof. We suppose for the moment 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 [ a , b ] [ a , b ] [a,b][a, b][a,b].
The remainder of the interpolation polynomial P P PPP in (1.3) is known that satisfies
f − 1 ( y ) − P ( y ) = [ y , b 1 , b 2 , b 3 ; f − 1 ] ( y − b 1 ) ( y − b 2 ) ( y − b 3 ) f − 1 ( y ) − P ( y ) = y , b 1 , b 2 , b 3 ; f − 1 y − b 1 y − b 2 y − b 3 f^(-1)(y)-P(y)=[y,b_(1),b_(2),b_(3);f^(-1)](y-b_(1))(y-b_(2))(y-b_(3))f^{-1}(y)-P(y)=\left[y, b_{1}, b_{2}, b_{3} ; f^{-1}\right]\left(y-b_{1}\right)\left(y-b_{2}\right)\left(y-b_{3}\right)f−1(y)−P(y)=[y,b1,b2,b3;f−1](y−b1)(y−b2)(y−b3)
so we obtain
(2.8) x ∗ − x n + 1 = − [ 0 , f ( x n ) , f ( y n ) , f ( z n ) ; f − 1 ] f ( x n ) f ( y n ) f ( z n ) , n = 0 , 1 , … (2.8) x ∗ − x n + 1 = − 0 , f x n , f y n , f z n ; f − 1 f x n f y n f z n , n = 0 , 1 , … {:(2.8)x^(**)-x_(n+1)=-[0,f(x_(n)),f(y_(n)),f(z_(n));f^(-1)]f(x_(n))f(y_(n))f(z_(n))","quad n=0","1","dots:}\begin{equation*} x^{*}-x_{n+1}=-\left[0, f\left(x_{n}\right), f\left(y_{n}\right), f\left(z_{n}\right) ; f^{-1}\right] f\left(x_{n}\right) f\left(y_{n}\right) f\left(z_{n}\right), \quad n=0,1, \ldots \tag{2.8} \end{equation*}(2.8)x∗−xn+1=−[0,f(xn),f(yn),f(zn);f−1]f(xn)f(yn)f(zn),n=0,1,…
The mean value formula for divided differences yields:
[ 0 , f ( x n ) , f ( y n ) , f ( z n ) ; f − 1 ] = ( f − 1 ( η n ) ) ′ ′ ′ 6 0 , f x n , f y n , f z n ; f − 1 = f − 1 η n ′ ′ ′ 6 [0,f(x_(n)),f(y_(n)),f(z_(n));f^(-1)]=((f^(-1)(eta_(n)))^('''))/(6)\left[0, f\left(x_{n}\right), f\left(y_{n}\right), f\left(z_{n}\right) ; f^{-1}\right]=\frac{\left(f^{-1}\left(\eta_{n}\right)\right)^{\prime \prime \prime}}{6}[0,f(xn),f(yn),f(zn);f−1]=(f−1(ηn))′′′6
where η n ∈ I 0 , f ( x n ) , f ( y n ) , f ( z n ) η n ∈ I 0 , f x n , f y n , f z n eta_(n)inI_(0,f(x_(n)),f(y_(n)),f(z_(n)))\eta_{n} \in I_{0, f\left(x_{n}\right), f\left(y_{n}\right), f\left(z_{n}\right)}ηn∈I0,f(xn),f(yn),f(zn). Since f f fff has derivatives up to order 3 on [ a , b ] [ a , b ] [a,b][a, b][a,b] and f ′ ( x ) ≠ 0 f ′ ( x ) ≠ 0 f^(')(x)!=0f^{\prime}(x) \neq 0f′(x)≠0, ∀ x ∈ [ a , b ] ∀ x ∈ [ a , b ] AA x in[a,b]\forall x \in[a, b]∀x∈[a,b], then f − 1 f − 1 f^(-1)f^{-1}f−1 is three times derivable and (see, e.g., [19])
(2.9) ( f − 1 ( η n ) ) ′ ′ ′ = 3 f ′ ′ ( ξ n ) 2 − f ′ ( ξ n ) f ′ ′ ′ ( ξ n ) f ′ ( ξ n ) 5 = E f ( ξ n ) f ′ ( ξ n ) 5 (2.9) f − 1 η n ′ ′ ′ = 3 f ′ ′ ξ n 2 − f ′ ξ n f ′ ′ ′ ξ n f ′ ξ n 5 = E f ξ n f ′ ξ n 5 {:(2.9)(f^(-1)(eta_(n)))^(''')=(3f^('')(xi_(n))^(2)-f^(')(xi_(n))f^(''')(xi_(n)))/(f^(')(xi_(n))^(5))=(E_(f)(xi_(n)))/(f^(')(xi_(n))^(5)):}\begin{equation*} \left(f^{-1}\left(\eta_{n}\right)\right)^{\prime \prime \prime}=\frac{3 f^{\prime \prime}\left(\xi_{n}\right)^{2}-f^{\prime}\left(\xi_{n}\right) f^{\prime \prime \prime}\left(\xi_{n}\right)}{f^{\prime}\left(\xi_{n}\right)^{5}}=\frac{E_{f}\left(\xi_{n}\right)}{f^{\prime}\left(\xi_{n}\right)^{5}} \tag{2.9} \end{equation*}(2.9)(f−1(ηn))′′′=3f′′(ξn)2−f′(ξn)f′′′(ξn)f′(ξn)5=Ef(ξn)f′(ξn)5
where ξ n = f − 1 ( η n ) ∈ [ a , b ] ξ n = f − 1 η n ∈ [ a , b ] xi_(n)=f^(-1)(eta_(n))in[a,b]\xi_{n}=f^{-1}\left(\eta_{n}\right) \in[a, b]ξn=f−1(ηn)∈[a,b]. One can show that in fact ξ n ∈ I x ∗ , x n , y n , z n ξ n ∈ I x ∗ , x n , y n , z n xi_(n)inI_(x^(**),x_(n),y_(n),z_(n))\xi_{n} \in I_{x^{*}, x_{n}, y_{n}, z_{n}}ξn∈Ix∗,xn,yn,zn.
Combining the above relations, (2.8) leads to
(2.10) x ∗ − x n + 1 = − E f ( ξ n ) 6 f ′ ( ξ n ) 5 f ( x n ) f ( y n ) f ( z n ) , n = 0 , 1 , … (2.10) x ∗ − x n + 1 = − E f ξ n 6 f ′ ξ n 5 f x n f y n f z n , n = 0 , 1 , … {:(2.10)x^(**)-x_(n+1)=-(E_(f)(xi_(n)))/(6f^(')(xi_(n))^(5))f(x_(n))f(y_(n))f(z_(n))","quad n=0","1","dots:}\begin{equation*} x^{*}-x_{n+1}=-\frac{E_{f}\left(\xi_{n}\right)}{6 f^{\prime}\left(\xi_{n}\right)^{5}} f\left(x_{n}\right) f\left(y_{n}\right) f\left(z_{n}\right), \quad n=0,1, \ldots \tag{2.10} \end{equation*}(2.10)x∗−xn+1=−Ef(ξn)6f′(ξn)5f(xn)f(yn)f(zn),n=0,1,…
The Lagrange Theorem ensures the existence of α n ∈ I x ∗ , x n , β n ∈ I x ∗ , y n , γ n ∈ I x ∗ , z n α n ∈ I x ∗ , x n , β n ∈ I x ∗ , y n , γ n ∈ I x ∗ , z n alpha_(n)inI_(x^(**),x_(n)),beta_(n)inI_(x^(**),y_(n)),gamma_(n)inI_(x^(**),z_(n))\alpha_{n} \in I_{x^{*}, x_{n}}, \beta_{n} \in I_{x^{*}, y_{n}}, \gamma_{n} \in I_{x^{*}, z_{n}}αn∈Ix∗,xn,βn∈Ix∗,yn,γn∈Ix∗,zn such that
f ( x n ) = f ′ ( α n ) ( x n − x ∗ ) , f ( y n ) = f ′ ( β n ) ( y n − x ∗ ) , f ( z n ) = f ′ ( γ n ) ( z n − x ∗ ) , f x n = f ′ α n x n − x ∗ , f y n = f ′ β n y n − x ∗ , f z n = f ′ γ n z n − x ∗ , f(x_(n))=f^(')(alpha_(n))(x_(n)-x^(**)),quad f(y_(n))=f^(')(beta_(n))(y_(n)-x^(**)),quad f(z_(n))=f^(')(gamma_(n))(z_(n)-x^(**)),f\left(x_{n}\right)=f^{\prime}\left(\alpha_{n}\right)\left(x_{n}-x^{*}\right), \quad f\left(y_{n}\right)=f^{\prime}\left(\beta_{n}\right)\left(y_{n}-x^{*}\right), \quad f\left(z_{n}\right)=f^{\prime}\left(\gamma_{n}\right)\left(z_{n}-x^{*}\right),f(xn)=f′(αn)(xn−x∗),f(yn)=f′(βn)(yn−x∗),f(zn)=f′(γn)(zn−x∗),
and therefore the error (2.10) becomes
(2.11) x ∗ − x n + 1 = E f ( ξ n ) 6 f ′ ( ξ n ) 5 f ′ ( α n ) f ′ ( β n ) f ′ ( γ n ) ( x ∗ − x n ) ( x ∗ − y n ) ( x ∗ − z n ) (2.11) x ∗ − x n + 1 = E f ξ n 6 f ′ ξ n 5 f ′ α n f ′ β n f ′ γ n x ∗ − x n x ∗ − y n x ∗ − z n {:(2.11)x^(**)-x_(n+1)=(E_(f)(xi_(n)))/(6f^(')(xi_(n))^(5))f^(')(alpha_(n))f^(')(beta_(n))f^(')(gamma_(n))(x^(**)-x_(n))(x^(**)-y_(n))(x^(**)-z_(n)):}\begin{equation*} x^{*}-x_{n+1}=\frac{E_{f}\left(\xi_{n}\right)}{6 f^{\prime}\left(\xi_{n}\right)^{5}} f^{\prime}\left(\alpha_{n}\right) f^{\prime}\left(\beta_{n}\right) f^{\prime}\left(\gamma_{n}\right)\left(x^{*}-x_{n}\right)\left(x^{*}-y_{n}\right)\left(x^{*}-z_{n}\right) \tag{2.11} \end{equation*}(2.11)x∗−xn+1=Ef(ξn)6f′(ξn)5f′(αn)f′(βn)f′(γn)(x∗−xn)(x∗−yn)(x∗−zn)
From the first and second relation in (1.6) it follows that there exists θ n ∈ I x ∗ , x n θ n ∈ I x ∗ , x n theta_(n)inI_(x^(**),x_(n))\theta_{n} \in I_{x^{*}, x_{n}}θn∈Ix∗,xn and μ n ∈ I x ∗ , y n μ n ∈ I x ∗ , y n mu_(n)inI_(x^(**),y_(n))\mu_{n} \in I_{x^{*}, y_{n}}μn∈Ix∗,yn such that
x ∗ − y n = − f ′ ′ ( θ n ) 2 f ′ ( x n ) ( x ∗ − x n ) 2 , x ∗ − z n = − f ′ ′ ( μ n ) 2 f ′ ( y n ) ( x ∗ − y n ) 2 , n = 0 , 1 , … x ∗ − y n = − f ′ ′ θ n 2 f ′ x n x ∗ − x n 2 , x ∗ − z n = − f ′ ′ μ n 2 f ′ y n x ∗ − y n 2 , n = 0 , 1 , … x^(**)-y_(n)=-(f^('')(theta_(n)))/(2f^(')(x_(n)))(x^(**)-x_(n))^(2),quadx^(**)-z_(n)=-(f^('')(mu_(n)))/(2f^(')(y_(n)))(x^(**)-y_(n))^(2),quad n=0,1,dotsx^{*}-y_{n}=-\frac{f^{\prime \prime}\left(\theta_{n}\right)}{2 f^{\prime}\left(x_{n}\right)}\left(x^{*}-x_{n}\right)^{2}, \quad x^{*}-z_{n}=-\frac{f^{\prime \prime}\left(\mu_{n}\right)}{2 f^{\prime}\left(y_{n}\right)}\left(x^{*}-y_{n}\right)^{2}, \quad n=0,1, \ldotsx∗−yn=−f′′(θn)2f′(xn)(x∗−xn)2,x∗−zn=−f′′(μn)2f′(yn)(x∗−yn)2,n=0,1,…
These relations imply (2.7), as well as the rest of the statements.
It can be easily proved that the elements of all sequences ( x n ) n ≥ 0 , ( y n ) n ≥ 0 , ( z n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 , z n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0),(z_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0},\left(z_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0,(zn)n≥0, ( μ n ) n ≥ 0 , ( ξ n ) n ≥ 0 , ( θ n ) n ≥ 0 μ n n ≥ 0 , ξ n n ≥ 0 , θ n n ≥ 0 (mu_(n))_(n >= 0),(xi_(n))_(n >= 0),(theta_(n))_(n >= 0)\left(\mu_{n}\right)_{n \geq 0},\left(\xi_{n}\right)_{n \geq 0},\left(\theta_{n}\right)_{n \geq 0}(μn)n≥0,(ξn)n≥0,(θn)n≥0 are well defined if x 0 x 0 x_(0)x_{0}x0 is chosen sufficiently close to x ∗ x ∗ x^(**)x^{*}x∗.
The q q qqq-convergence order p p ppp of the method (see, e.g., [14] for definitions and properties) is at least 7 , and since at each iteration step one computes d = 5 d = 5 d=5d=5d=5 function evaluations ( f ( x n ) , f ′ ( x n ) , f ( y n ) , f ′ ( y n ) , f ( z n ) ) f x n , f ′ x n , f y n , f ′ y n , f z n (f(x_(n)),f^(')(x_(n)),f(y_(n)),f^(')(y_(n)),f(z_(n)))\left(f\left(x_{n}\right), f^{\prime}\left(x_{n}\right), f\left(y_{n}\right), f^{\prime}\left(y_{n}\right), f\left(z_{n}\right)\right)(f(xn),f′(xn),f(yn),f′(yn),f(zn)), the efficiency index of the method (see, e.g., [15] for definitions) is E = p 1 d = 7 1 5 ≈ 1.47 E = p 1 d = 7 1 5 ≈ 1.47 E=p^((1)/(d))=7^((1)/(5))~~1.47E=p^{\frac{1}{d}}=7^{\frac{1}{5}} \approx 1.47E=p1d=715≈1.47. This value is greater than 2 1 2 ≈ 1.41 2 1 2 ≈ 1.41 2^((1)/(2))~~1.412^{\frac{1}{2}} \approx 1.41212≈1.41 and 3 1 3 ≈ 1.44 3 1 3 ≈ 1.44 3^((1)/(3))~~1.443^{\frac{1}{3}} \approx 1.44313≈1.44 which correspond to the Newton method, resp. the generalized Steffensen method (see [19]).

3. Monotone convergence

In order to study the monotone convergence of the method, we consider the Fourier condition:
C) the initial approximation x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b] verifies 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) \cdot f^{\prime \prime}\left(x_{0}\right)>0f(x0)⋅f′′(x0)>0.
We obtain the following results.
Theorem 3.2. If f f fff satisfies assumptions A A AAA )- C C CCC ) and, moreover
i 1 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i 1 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i_(1).f^(')(x) > 0,AA x in[a,b];i_{1} . f^{\prime}(x)>0, \forall x \in[a, b] ;i1.f′(x)>0,∀x∈[a,b];
i i 1 i i 1 ii_(1)i i_{1}ii1. f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] f^('')(x) >= 0,AA x in[a,b]f^{\prime \prime}(x) \geq 0, \forall x \in[a, b]f′′(x)≥0,∀x∈[a,b];
iii 1 . E f ( x ) ≥ 0 , ∀ x ∈ [ a , b ] 1 . E f ( x ) ≥ 0 , ∀ x ∈ [ a , b ] _(1).E_(f)(x) >= 0,AA x in[a,b]_{1} . E_{f}(x) \geq 0, \forall x \in[a, b]1.Ef(x)≥0,∀x∈[a,b],
(1) 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 (1.6) remain in [ a , b ] [ a , b ] [a,b][a, b][a,b] and satisfy:
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).x_(n) > y_(n) > z_(n) > x_(n+1) > x^(**),n=0,1,dotsj_{1} . x_{n}>y_{n}>z_{n}>x_{n+1}>x^{*}, n=0,1, \ldotsj1.xn>yn>zn>xn+1>x∗,n=0,1,…,
j j 1 . lim x n = lim y n = lim z n = x ∗ j j 1 . lim x n = lim y n = lim z n = x ∗ jj_(1).limx_(n)=limy_(n)=limz_(n)=x^(**)j j_{1} . \lim x_{n}=\lim y_{n}=\lim z_{n}=x^{*}jj1.limxn=limyn=limzn=x∗.
Moreover, as soon as the iterates ( x n ) n ≥ 0 x n n ≥ 0 (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0}(xn)n≥0 become sufficiently close to the solution, they obey also the conclusions of Theorem 2.1.
Proof. By i 1 i 1 i_(1)i_{1}i1 ) and B B BBB ) it follows that the solution x ∗ x ∗ x^(**)x^{*}x∗ is unique in ] a , b [ ] a , b ]a,b[:}] a, b\left[\right.]a,b[. Let x n ∈ [ a , b ] x n ∈ [ a , b ] x_(n)in[a,b]x_{n} \in[a, b]xn∈[a,b] be an approximation for x ∗ x ∗ x^(**)x^{*}x∗, which satisfies C C CCC ). From i i 1 i i 1 ii_(1)i i_{1}ii1 ) we have f ( x n ) > 0 f x n > 0 f(x_(n)) > 0f\left(x_{n}\right)>0f(xn)>0 and, by i 1 i 1 i_(1)i_{1}i1 ), x n > x ∗ x n > x ∗ x_(n) > x^(**)x_{n}>x^{*}xn>x∗. Relations A A AAA ), i 1 i 1 i_(1)i_{1}i1 ), i i 1 i i 1 ii_(1)i i_{1}ii1 ) attract, by first relation in (1.6), that y n < x n y n < x n y_(n) < x_(n)y_{n}<x_{n}yn<xn and y n > x ∗ y n > x ∗ y_(n) > x^(**)y_{n}>x^{*}yn>x∗. A similar reasoning leads to x ∗ < z n < y n x ∗ < z n < y n x^(**) < z_(n) < y_(n)x^{*}<z_{n}<y_{n}x∗<zn<yn and f ( z n ) > 0 f z n > 0 f(z_(n)) > 0f\left(z_{n}\right)>0f(zn)>0. The last relation in (1.6), together with (2.8), (2.9), i 1 i 1 i_(1)i_{1}i1 ) and i i i 1 i i i 1 iii_(1)i i i_{1}iii1 ) imply that x n + 1 > x ∗ x n + 1 > x ∗ x_(n+1) > x^(**)x_{n+1}>x^{*}xn+1>x∗. The inequality x n + 1 < z n x n + 1 < z n x_(n+1) < z_(n)x_{n+1}<z_{n}xn+1<zn is obtained from the equivalent writing of the interpolation polynomial, i.e.
x n + 1 = z n − f ( z n ) [ z n , y n ; f ] − [ z n , y n , x n ; f ] f ( z n ) f ( y n ) [ z n , y n ; f ] [ z n , x n ; f ] [ y n , x n ; f ] x n + 1 = z n − f z n z n , y n ; f − z n , y n , x n ; f f z n f y n z n , y n ; f z n , x n ; f y n , x n ; f x_(n+1)=z_(n)-(f(z_(n)))/([z_(n),y_(n);f])-([z_(n),y_(n),x_(n);f]f(z_(n))f(y_(n)))/([z_(n),y_(n);f][z_(n),x_(n);f][y_(n),x_(n);f])x_{n+1}=z_{n}-\frac{f\left(z_{n}\right)}{\left[z_{n}, y_{n} ; f\right]}-\frac{\left[z_{n}, y_{n}, x_{n} ; f\right] f\left(z_{n}\right) f\left(y_{n}\right)}{\left[z_{n}, y_{n} ; f\right]\left[z_{n}, x_{n} ; f\right]\left[y_{n}, x_{n} ; f\right]}xn+1=zn−f(zn)[zn,yn;f]−[zn,yn,xn;f]f(zn)f(yn)[zn,yn;f][zn,xn;f][yn,xn;f]
By induction, we show j 1 j 1 j_(1)j_{1}j1 ). It remains to show j j 1 j j 1 jj_(1)j j_{1}jj1 ), which follows by passing to limit in the first relation in (1.6), and taking into account j 1 j 1 j_(1)j_{1}j1 ).
Remark 3.1. We notice that the above result allows a possibly larger convergence domain of the iterates, compared to conditions required by Theorem 2.1 (as is the case when we consider the Newton method and the Fourier condition). The same observation applies to the subsequent results.
Theorem 3.3. If f f fff obeys assumptions A A AAA )- C C CCC ), i i i 1 i i i 1 iii_(1)i i i_{1}iii1 ) and, moreover,
i 2 . f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; i 2 . f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; i_(2).f^(')(x) < 0,AA x in[a,b];i_{2} . f^{\prime}(x)<0, \forall x \in[a, b] ;i2.f′(x)<0,∀x∈[a,b];
i i 2 . f ′ ′ ( x ) ≤ 0 , ∀ x ∈ [ a , b ] i i 2 . f ′ ′ ( x ) ≤ 0 , ∀ x ∈ [ a , b ] ii_(2).f^('')(x) <= 0,AA x in[a,b]i i_{2} . f^{\prime \prime}(x) \leq 0, \forall x \in[a, b]ii2.f′′(x)≤0,∀x∈[a,b],
(1) then the same conclusions hold as in Theorem 3.2.
Proof. Instead of (1.1) we consider h ( x ) = 0 h ( x ) = 0 h(x)=0h(x)=0h(x)=0, with h = − f h = − f h=-fh=-fh=−f, and we take into account that E f = E − f E f = E − f E_(f)=E_(-f)E_{f}=E_{-f}Ef=E−f. ◻ ◻ ◻\square◻
In the case when f ′ f ′ f^(')f^{\prime}f′ and f ′ ′ f ′ ′ f^('')f^{\prime \prime}f′′ have different signs, we obtain the following results.
Theorem 3.4. If f f fff satisfies A ) − C A ) − C A)-CA)-CA)−C ), i i i 1 i i i 1 iii_(1)i i i_{1}iii1 ) and, moreover,
i 3 . f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; i 3 . f ′ ( x ) < 0 , ∀ x ∈ [ a , b ] ; i_(3).f^(')(x) < 0,AA x in[a,b];i_{3} . f^{\prime}(x)<0, \forall x \in[a, b] ;i3.f′(x)<0,∀x∈[a,b];
i i 3 i i 3 ii_(3)i i_{3}ii3. f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] f ′ ′ ( x ) ≥ 0 , ∀ x ∈ [ a , b ] f^('')(x) >= 0,AA x in[a,b]f^{\prime \prime}(x) \geq 0, \forall x \in[a, b]f′′(x)≥0,∀x∈[a,b],
(1) then the elements of ( x n ) n ≥ 0 , ( y n ) n ≥ 0 , ( z n ) n ≥ 0 x n n ≥ 0 , y n n ≥ 0 , z n n ≥ 0 (x_(n))_(n >= 0),(y_(n))_(n >= 0),(z_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0},\left(y_{n}\right)_{n \geq 0},\left(z_{n}\right)_{n \geq 0}(xn)n≥0,(yn)n≥0,(zn)n≥0 remain in [ a , b ] [ a , b ] [a,b][a, b][a,b] and 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).x_(n) < y_(n) < z_(n) < x_(n+1) < bar(x)^(**),n=0,1,dots;j_{3} . x_{n}<y_{n}<z_{n}<x_{n+1}<\bar{x}^{*}, n=0,1, \ldots ;j3.xn<yn<zn<xn+1<x¯∗,n=0,1,…;
j j 3 . lim x n = lim y n = lim z n = x ∗ j j 3 . lim x n = lim y n = lim z n = x ∗ jj_(3).limx_(n)=limy_(n)=limz_(n)=x^(**)j j_{3} . \lim x_{n}=\lim y_{n}=\lim z_{n}=x^{*}jj3.limxn=limyn=limzn=x∗.
Moreover, as soon as the iterates ( x n ) n ≥ 0 x n n ≥ 0 (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0}(xn)n≥0 become sufficiently close to the solution, they obey also the conclusions of Theorem 2.1.
The proof is similar to the proof of Theorem 3.2.
Theorem 3.5. If f f fff satisfies A ) − C A ) − C A)-CA)-CA)−C ), i i i 1 i i i 1 iii_(1)i i i_{1}iii1 ) and
i 4 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i 4 . f ′ ( x ) > 0 , ∀ x ∈ [ a , b ] ; i_(4).f^(')(x) > 0,AA x in[a,b];i_{4} . f^{\prime}(x)>0, \forall x \in[a, b] ;i4.f′(x)>0,∀x∈[a,b];
i i 4 i i 4 ii_(4)i i_{4}ii4. 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],
(1) then the same conclusions hold as in Theorem 3.4.
The proof is obtained as in the proof of Theorem 3.3.

4. Numerical examples

We present some examples, solved using Matlab in double precision, and we compare the studied method to other methods. In order to obtain smaller tables, we used the format short command in Matlab, and for better legibility we used the \numprint LaTeX command and package. It is worth mentioning that such choice may lead to results that appear integers, while they are not (e.g., the value of y 4 y 4 y_(4)y_{4}y4 in Table 4 is shown to be 2 , while f ( y 4 ) f y 4 f(y_(4))f\left(y_{4}\right)f(y4) should be 0 ); the explanation resides in the rounding made in the conversion process.
We shall consider the Aitken-Newton method introduced in [16]:
(4.12) y n = x n − f ( x n ) f ′ ( x n ) z n = y n − f ( y n ) f ′ ( y n ) x n + 1 = z n − f ( z n ) [ z n , y n ; f ] − [ z n , y n , y n ; f ] f ( z n ) f ( y n ) [ y n , z n ; f ] 2 f ′ ( y n ) , n = 0 , 1 , … (4.12) y n = x n − f x n f ′ x n z n = y n − f y n f ′ y n x n + 1 = z n − f z n z n , y n ; f − z n , y n , y n ; f f z n f y n y n , z n ; f 2 f ′ y n , n = 0 , 1 , … {:[(4.12)y_(n)=x_(n)-(f(x_(n)))/(f^(')(x_(n)))],[z_(n)=y_(n)-(f(y_(n)))/(f^(')(y_(n)))],[x_(n+1)=z_(n)-(f(z_(n)))/([z_(n),y_(n);f])-([z_(n),y_(n),y_(n);f]f(z_(n))f(y_(n)))/([y_(n),z_(n);f]^(2)f^(')(y_(n)))","quad n=0","1","dots]:}\begin{align*} y_{n} & =x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \tag{4.12}\\ 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[z_{n}, y_{n} ; f\right]}-\frac{\left[z_{n}, y_{n}, y_{n} ; f\right] f\left(z_{n}\right) f\left(y_{n}\right)}{\left[y_{n}, z_{n} ; f\right]^{2} f^{\prime}\left(y_{n}\right)}, \quad n=0,1, \ldots \end{align*}(4.12)yn=xn−f(xn)f′(xn)zn=yn−f(yn)f′(yn)xn+1=zn−f(zn)[zn,yn;f]−[zn,yn,yn;f]f(zn)f(yn)[yn,zn;f]2f′(yn),n=0,1,…
It has the q q qqq-convergence order 8 , the efficiency index 8 5 ≈ 1.51 8 5 ≈ 1.51 root(5)(8)~~1.51\sqrt[5]{8} \approx 1.5185≈1.51, and similar monotone convergence of the iterates as obtained in Theorems 3.2-3.5. However, the numerical examples performed in double precision arithmetic show a slight better convergence of this method over the Aitken-Steffensen-Newton method studied in this paper.
Example 4.1. Consider the following equation (see, e.g., [6])
f ( x ) = e x sin ⁡ x + ln ⁡ ( x 2 + 1 ) , x ∗ = 0 . f ( x ) = e x sin ⁡ x + ln ⁡ x 2 + 1 , x ∗ = 0 . f(x)=e^(x)sin x+ln(x^(2)+1),quadx^(**)=0.f(x)=e^{x} \sin x+\ln \left(x^{2}+1\right), \quad x^{*}=0 .f(x)=exsin⁡x+ln⁡(x2+1),x∗=0.
The largest interval to study the monotone convergence of our method by Theorems 3.2-3.5 is [ a , b ] := [ x ∗ , 1.54 … ] [ a , b ] := x ∗ , 1.54 … [a,b]:=[x^(**),1.54 dots][a, b]:=\left[x^{*}, 1.54 \ldots\right][a,b]:=[x∗,1.54…], since f ′ ′ f ′ ′ f^('')f^{\prime \prime}f′′ vanishes at b b bbb (being positive on [ a , b ] [ a , b ] [a,b][a, b][a,b] ). The Fourier
condition D) holds on [ a , b ] [ a , b ] [a,b][a, b][a,b] (and does not hold for x ⟨ a ) , E f ( x ) > 0 x ⟨ a ) , E f ( x ) > 0 x(:a),E_(f)(x) > 0x\langle a), E_{f}(x)>0x⟨a),Ef(x)>0 on [ a , b ] [ a , b ] [a,b][a, b][a,b], while the derivatives f ′ , f ′ ′ f ′ , f ′ ′ f^('),f^('')f^{\prime}, f^{\prime \prime}f′,f′′ are positive on this interval. The conclusions of Theorem 3.2 apply.
The Aitken-Newton-Steffensen method leads to the following results, presented in Table 1.
n n nnn x n x n x_(n)x_{n}xn f ( x n ) f x n f(x_(n))f\left(x_{n}\right)f(xn) y n y n y_(n)y_{n}yn f ( y n ) f y n f(y_(n))f\left(y_{n}\right)f(yn) z n z n z_(n)z_{n}zn f ( z n ) f z n f(z_(n))f\left(z_{n}\right)f(zn)
0 1.54 5.8778 0.51233 1.0513 0.17152 0.2316
1 0.066475 0.075401 0.0070915 0.0071922 9.8028 ⋅ 10 − 05 9.8028 ⋅ 10 − 05 9.8028*10^(-05)9.8028 \cdot 10^{-05}9.8028⋅10−05 9.8047 ⋅ 10 − 05 9.8047 ⋅ 10 − 05 9.8047*10^(-05)9.8047 \cdot 10^{-05}9.8047⋅10−05
2 2.9348 ⋅ 10 − 07 2.9348 ⋅ 10 − 07 2.9348*10^(-07)2.9348 \cdot 10^{-07}2.9348⋅10−07 2.9348 ⋅ 10 − 07 2.9348 ⋅ 10 − 07 2.9348*10^(-07)2.9348 \cdot 10^{-07}2.9348⋅10−07 1.7224 ⋅ 10 − 13 1.7224 ⋅ 10 − 13 1.7224*10^(-13)1.7224 \cdot 10^{-13}1.7224⋅10−13 1.7224 ⋅ 10 − 13 1.7224 ⋅ 10 − 13 1.7224*10^(-13)1.7224 \cdot 10^{-13}1.7224⋅10−13 8.8984 ⋅ 10 − 26 8.8984 ⋅ 10 − 26 8.8984*10^(-26)8.8984 \cdot 10^{-26}8.8984⋅10−26 8.8984 ⋅ 10 − 26 8.8984 ⋅ 10 − 26 8.8984*10^(-26)8.8984 \cdot 10^{-26}8.8984⋅10−26
n x_(n) f(x_(n)) y_(n) f(y_(n)) z_(n) f(z_(n)) 0 1.54 5.8778 0.51233 1.0513 0.17152 0.2316 1 0.066475 0.075401 0.0070915 0.0071922 9.8028*10^(-05) 9.8047*10^(-05) 2 2.9348*10^(-07) 2.9348*10^(-07) 1.7224*10^(-13) 1.7224*10^(-13) 8.8984*10^(-26) 8.8984*10^(-26)| $n$ | $x_{n}$ | $f\left(x_{n}\right)$ | $y_{n}$ | $f\left(y_{n}\right)$ | $z_{n}$ | $f\left(z_{n}\right)$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | 1.54 | 5.8778 | 0.51233 | 1.0513 | 0.17152 | 0.2316 | | 1 | 0.066475 | 0.075401 | 0.0070915 | 0.0071922 | $9.8028 \cdot 10^{-05}$ | $9.8047 \cdot 10^{-05}$ | | 2 | $2.9348 \cdot 10^{-07}$ | $2.9348 \cdot 10^{-07}$ | $1.7224 \cdot 10^{-13}$ | $1.7224 \cdot 10^{-13}$ | $8.8984 \cdot 10^{-26}$ | $8.8984 \cdot 10^{-26}$ |
Table 1. Aitken-Newton-Steffensen iterates, f ( x ) = e x sin ⁡ x + ln ⁡ ( x 2 + 1 ) f ( x ) = e x sin ⁡ x + ln ⁡ x 2 + 1 f(x)=e^(x)sin x+ln(x^(2)+1)f(x)=e^{x} \sin x+\ln \left(x^{2}+1\right)f(x)=exsin⁡x+ln⁡(x2+1).
The Aitken-Newton method 4.12 leads to the results presented in Table 2.
n n nnn x n x n x_(n)x_{n}xn f ( x n ) f x n f(x_(n))f\left(x_{n}\right)f(xn) y n y n y_(n)y_{n}yn f ( y n ) f y n f(y_(n))f\left(y_{n}\right)f(yn) z n z n z_(n)z_{n}zn f ( z n ) f z n f(z_(n))f\left(z_{n}\right)f(zn)
0 1.54 5.8778 0.51233 1.0513 0.17152 0.2316
1 0.048016 0.052662 0.0039166 0.0039473 3.0245 ⋅ 10 − 05 3.0245 ⋅ 10 − 05 3.0245*10^(-05)3.0245 \cdot 10^{-05}3.0245⋅10−05 3.0246 ⋅ 10 − 05 3.0246 ⋅ 10 − 05 3.0246*10^(-05)3.0246 \cdot 10^{-05}3.0246⋅10−05
2 3.4821 ⋅ 10 − 09 3.4821 ⋅ 10 − 09 3.4821*10^(-09)3.4821 \cdot 10^{-09}3.4821⋅10−09 3.4821 ⋅ 10 − 09 3.4821 ⋅ 10 − 09 3.4821*10^(-09)3.4821 \cdot 10^{-09}3.4821⋅10−09 3.6375 ⋅ 10 − 17 3.6375 ⋅ 10 − 17 3.6375*10^(-17)3.6375 \cdot 10^{-17}3.6375⋅10−17 3.6375 ⋅ 10 − 17 3.6375 ⋅ 10 − 17 3.6375*10^(-17)3.6375 \cdot 10^{-17}3.6375⋅10−17 0 0
n x_(n) f(x_(n)) y_(n) f(y_(n)) z_(n) f(z_(n)) 0 1.54 5.8778 0.51233 1.0513 0.17152 0.2316 1 0.048016 0.052662 0.0039166 0.0039473 3.0245*10^(-05) 3.0246*10^(-05) 2 3.4821*10^(-09) 3.4821*10^(-09) 3.6375*10^(-17) 3.6375*10^(-17) 0 0| $n$ | $x_{n}$ | $f\left(x_{n}\right)$ | $y_{n}$ | $f\left(y_{n}\right)$ | $z_{n}$ | $f\left(z_{n}\right)$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | 1.54 | 5.8778 | 0.51233 | 1.0513 | 0.17152 | 0.2316 | | 1 | 0.048016 | 0.052662 | 0.0039166 | 0.0039473 | $3.0245 \cdot 10^{-05}$ | $3.0246 \cdot 10^{-05}$ | | 2 | $3.4821 \cdot 10^{-09}$ | $3.4821 \cdot 10^{-09}$ | $3.6375 \cdot 10^{-17}$ | $3.6375 \cdot 10^{-17}$ | 0 | 0 |
Table 2. Aitken-Newton iterates, f ( x ) = e x sin ⁡ x + ln ⁡ ( x 2 + 1 ) f ( x ) = e x sin ⁡ x + ln ⁡ x 2 + 1 f(x)=e^(x)sin x+ln(x^(2)+1)f(x)=e^{x} \sin x+\ln \left(x^{2}+1\right)f(x)=exsin⁡x+ln⁡(x2+1).
The convergence may be not very fast for initial approximations away from the solution.
It is worth noting that the method converges for − 0.3 ≤ x 0 ≤ x 1 ∗ − 0.3 ≤ x 0 ≤ x 1 ∗ -0.3 <= x_(0) <= x_(1)^(**)-0.3 \leq x_{0} \leq x_{1}^{*}−0.3≤x0≤x1∗ too (local convergence near x ∗ = 0 x ∗ = 0 x^(**)=0x^{*}=0x∗=0 assured by Theorem 2.1), despite the Fourier condition does not hold. For x 0 = − 0.3 x 0 = − 0.3 x_(0)=-0.3x_{0}=-0.3x0=−0.3 one obtains y 0 = − 2.4 … < 0 y 0 = − 2.4 … < 0 y_(0)=-2.4 dots < 0y_{0}=-2.4 \ldots<0y0=−2.4…<0, then z 0 = − 0.14 … < 0 , x 1 = 0.37 … z 0 = − 0.14 … < 0 , x 1 = 0.37 … z_(0)=-0.14 dots < 0,x_(1)=0.37 dotsz_{0}=-0.14 \ldots<0, x_{1}=0.37 \ldotsz0=−0.14…<0,x1=0.37… and the rest of the iterates remain positive, converging monotonically to x 1 ∗ x 1 ∗ x_(1)^(**)x_{1}^{*}x1∗. For x 0 = − 0.4 x 0 = − 0.4 x_(0)=-0.4x_{0}=-0.4x0=−0.4, the method converges to another solution of the equation, x 2 ∗ = − 0.603 … x 2 ∗ = − 0.603 … x_(2)^(**)=-0.603 dotsx_{2}^{*}=-0.603 \ldotsx2∗=−0.603…
The optimal method introduced by Cordero, Torregrosa and Vassileva in [9] has a smaller convergence domain to the right of x 1 ∗ x 1 ∗ x_(1)^(**)x_{1}^{*}x1∗, since the iterates converge for x 0 = 1.48 x 0 = 1.48 x_(0)=1.48x_{0}=1.48x0=1.48 ( x 4 = 1.3741 ⋅ 10 − 32 x 4 = 1.3741 ⋅ 10 − 32 x_(4)=1.3741*10^(-32)x_{4}=1.3741 \cdot 10^{-32}x4=1.3741⋅10−32 ), while for x 0 = 1.49 x 0 = 1.49 x_(0)=1.49x_{0}=1.49x0=1.49 the iterates jump over x 1 ∗ x 1 ∗ x_(1)^(**)x_{1}^{*}x1∗ and converge to x 2 ∗ x 2 ∗ x_(2)^(**)x_{2}^{*}x2∗; in fact, the initial approximation 1.442 does not lead to convergence (see [16]).
The Kou-Wang method (formula (25) in [12]) converges for x 0 = 1.48 ( x 4 = 0 ) x 0 = 1.48 x 4 = 0 x_(0)=1.48(x_(4)=0)x_{0}=1.48\left(x_{4}=0\right)x0=1.48(x4=0) and diverges for x 0 = 1.49 x 0 = 1.49 x_(0)=1.49x_{0}=1.49x0=1.49 (see [16]).
Example 4.2. Consider the following equation (see, e.g., [23])
f ( x ) = ( x − 2 ) ( x 10 + x + 1 ) e − x − 1 , x ∗ = 2 . f ( x ) = ( x − 2 ) x 10 + x + 1 e − x − 1 , x ∗ = 2 . f(x)=(x-2)(x^(10)+x+1)e^(-x-1),quadx^(**)=2.f(x)=(x-2)\left(x^{10}+x+1\right) e^{-x-1}, \quad x^{*}=2 .f(x)=(x−2)(x10+x+1)e−x−1,x∗=2.
The largest interval to study the monotone convergence of our method by Theorems 3.2-3.5 is [ a , b ] := [ x ∗ , 7.9 … ] [ a , b ] := x ∗ , 7.9 … [a,b]:=[x^(**),7.9 dots][a, b]:=\left[x^{*}, 7.9 \ldots\right][a,b]:=[x∗,7.9…], since f ′ ′ f ′ ′ f^('')f^{\prime \prime}f′′ vanishes at b b bbb (being positive on [ a , b ] [ a , b ] [a,b][a, b][a,b] ).
The Fourier condition C) holds on [ a , b ] [ a , b ] [a,b][a, b][a,b] (and does not hold for x < a x < a x < ax<ax<a ), E f ( x ) > 0 E f ( x ) > 0 E_(f)(x) > 0E_{f}(x)>0Ef(x)>0 on [ a , b ] [ a , b ] [a,b][a, b][a,b], while both the derivatives f ′ , f ′ ′ f ′ , f ′ ′ f^('),f^('')f^{\prime}, f^{\prime \prime}f′,f′′ are positive on this interval. The conclusions of Theorem 3.2 apply.
It is interesting to note that in [23, Rem. 6] Petković observed that the methods studied there have a small convergence domain to the left of the solution: the choice of x 0 = 1.8 x 0 = 1.8 x_(0)=1.8x_{0}=1.8x0=1.8 caused a bad convergence behavior of those iterates. We believe that this behavior may be explained by the fact that the derivative of f f fff vanishes at x = 1.78 … x = 1.78 … x=1.78 dotsx=1.78 \ldotsx=1.78…
The Aitken-Newton method leads to the results presented in Table 3. The iterates converge even for x 0 > 7.9 x 0 > 7.9 x_(0) > 7.9x_{0}>7.9x0>7.9 (and to the left of the solution as well, but for x 0 x 0 x_(0)x_{0}x0 higher than 1.81). Of course the convergence may be not very fast when the initial approximations are away from the solution.
In Table 4 we present the iterates generated by the Aitken-Newton method 4.12.
n n nnn x n x n x_(n)x_{n}xn f ( x n ) f x n f(x_(n))f\left(x_{n}\right)f(xn) y n y n y_(n)y_{n}yn f ( y n ) f y n f(y_(n))f\left(y_{n}\right)f(yn) z n z n z_(n)z_{n}zn f ( z n ) f z n f(z_(n))f\left(z_{n}\right)f(zn)
0 7.9 761907.1334 5.6028 148982.786 4.6615 44837.6641
1 4.207 20996.7099 3.6606 6787.2126 3.2321 2226.1658
2 2.9783 1005.7591 2.6824 331.2687 2.4439 107.8214
3 2.3038 47.0566 2.153 14.0054 2.0547 3.4655
4 2.0171 0.9347 2.0011 0.055388 2 0.00023597
5 2 1.0223 ⋅ 10 − 07 1.0223 ⋅ 10 − 07 1.0223*10^(-07)1.0223 \cdot 10^{-07}1.0223⋅10−07 2 0
Table 3. Aitken-Newton iterates, f ( x ) = ( x − 2 ) ( x 10 + x + 1 ) e − x − 1 f ( x ) = ( x − 2 ) x 10 + x + 1 e − x − 1 f(x)=(x-2)(x^(10)+x+1)e^(-x-1)f(x)=(x-2)\left(x^{10}+x+1\right) e^{-x-1}f(x)=(x−2)(x10+x+1)e−x−1.
n x_(n) f(x_(n)) y_(n) f(y_(n)) z_(n) f(z_(n)) 0 7.9 761907.1334 5.6028 148982.786 4.6615 44837.6641 1 4.207 20996.7099 3.6606 6787.2126 3.2321 2226.1658 2 2.9783 1005.7591 2.6824 331.2687 2.4439 107.8214 3 2.3038 47.0566 2.153 14.0054 2.0547 3.4655 4 2.0171 0.9347 2.0011 0.055388 2 0.00023597 5 2 1.0223*10^(-07) 2 0 Table 3. Aitken-Newton iterates, f(x)=(x-2)(x^(10)+x+1)e^(-x-1). | $n$ | $x_{n}$ | $f\left(x_{n}\right)$ | $y_{n}$ | $f\left(y_{n}\right)$ | $z_{n}$ | $f\left(z_{n}\right)$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | 7.9 | 761907.1334 | 5.6028 | 148982.786 | 4.6615 | 44837.6641 | | 1 | 4.207 | 20996.7099 | 3.6606 | 6787.2126 | 3.2321 | 2226.1658 | | 2 | 2.9783 | 1005.7591 | 2.6824 | 331.2687 | 2.4439 | 107.8214 | | 3 | 2.3038 | 47.0566 | 2.153 | 14.0054 | 2.0547 | 3.4655 | | 4 | 2.0171 | 0.9347 | 2.0011 | 0.055388 | 2 | 0.00023597 | | 5 | 2 | $1.0223 \cdot 10^{-07}$ | 2 | 0 | | | | Table 3. Aitken-Newton iterates, $f(x)=(x-2)\left(x^{10}+x+1\right) e^{-x-1}$. | | | | | | |
n n nnn x n x n x_(n)x_{n}xn f ( x n ) f x n f(x_(n))f\left(x_{n}\right)f(xn) y n y n y_(n)y_{n}yn f ( y n ) f y n f(y_(n))f\left(y_{n}\right)f(yn) z n z n z_(n)z_{n}zn f ( z n ) f z n f(z_(n))f\left(z_{n}\right)f(zn)
0 7.9 761907.1334 5.6028 148982.786 4.6615 44837.6641
1 4.0818 16594.4155 3.5637 5385.3696 3.1548 1769.5473
2 2.8568 655.665 2.5841 215.3342 2.3658 69.4249
3 2.2125 24.0727 2.0909 6.6087 2.0232 1.3004
4 2.0026 0.13254 2 0.0013264 2 1.3712 ⋅ 10 − 07 1.3712 ⋅ 10 − 07 1.3712*10^(-07)1.3712 \cdot 10^{-07}1.3712⋅10−07
5 2 − 1.1353 ⋅ 10 − 14 − 1.1353 ⋅ 10 − 14 -1.1353*10^(-14)-1.1353 \cdot 10^{-14}−1.1353⋅10−14 2 0
Table 4. Aitken-Newton iterates, f ( x ) = ( x − 2 ) ( x 10 + x + 1 ) e − x − 1 f ( x ) = ( x − 2 ) x 10 + x + 1 e − x − 1 f(x)=(x-2)(x^(10)+x+1)e^(-x-1)f(x)=(x-2)\left(x^{10}+x+1\right) e^{-x-1}f(x)=(x−2)(x10+x+1)e−x−1.
n x_(n) f(x_(n)) y_(n) f(y_(n)) z_(n) f(z_(n)) 0 7.9 761907.1334 5.6028 148982.786 4.6615 44837.6641 1 4.0818 16594.4155 3.5637 5385.3696 3.1548 1769.5473 2 2.8568 655.665 2.5841 215.3342 2.3658 69.4249 3 2.2125 24.0727 2.0909 6.6087 2.0232 1.3004 4 2.0026 0.13254 2 0.0013264 2 1.3712*10^(-07) 5 2 -1.1353*10^(-14) 2 0 Table 4. Aitken-Newton iterates, f(x)=(x-2)(x^(10)+x+1)e^(-x-1). | $n$ | $x_{n}$ | $f\left(x_{n}\right)$ | $y_{n}$ | $f\left(y_{n}\right)$ | $z_{n}$ | $f\left(z_{n}\right)$ | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | 0 | 7.9 | 761907.1334 | 5.6028 | 148982.786 | 4.6615 | 44837.6641 | | 1 | 4.0818 | 16594.4155 | 3.5637 | 5385.3696 | 3.1548 | 1769.5473 | | 2 | 2.8568 | 655.665 | 2.5841 | 215.3342 | 2.3658 | 69.4249 | | 3 | 2.2125 | 24.0727 | 2.0909 | 6.6087 | 2.0232 | 1.3004 | | 4 | 2.0026 | 0.13254 | 2 | 0.0013264 | 2 | $1.3712 \cdot 10^{-07}$ | | 5 | 2 | $-1.1353 \cdot 10^{-14}$ | 2 | 0 | | | | Table 4. Aitken-Newton iterates, $f(x)=(x-2)\left(x^{10}+x+1\right) e^{-x-1}$. | | | | | | |
The optimal method introduced by Cordero, Torregrosa and Vassileva in [9] converges to x ∗ x ∗ x^(**)x^{*}x∗ for x 0 = 6.46 x 0 = 6.46 x_(0)=6.46x_{0}=6.46x0=6.46 and it does not for x 0 = 6.47 x 0 = 6.47 x_(0)=6.47x_{0}=6.47x0=6.47, as shown in [16] .
The optimal method introduced by Liu and Wang (formula (18) in [13]) converges to x ∗ = 2 x ∗ = 2 x^(**)=2x^{*}=2x∗=2 for x 0 = 2.359 x 0 = 2.359 x_(0)=2.359x_{0}=2.359x0=2.359 (it needs 5 iterates) but for x 0 = 2.36 x 0 = 2.36 x_(0)=2.36x_{0}=2.36x0=2.36 it converges to another solution, x 1 ∗ = 1512.626 … x 1 ∗ = 1512.626 … x_(1)^(**)=1512.626 dotsx_{1}^{*}=1512.626 \ldotsx1∗=1512.626…. The results are presented in [16].
Among the optimal methods in [23] (the methods with convergence orders higher than 8 were corrected in a subsequent Corrigendum paper), the modified Ostrowski and Maheshwari methods behave very well for this example (we have studied the convergence only to the right of the solution). The modified Euler-like method has a small domain of convergence (in R R R\mathbb{R}R ), since it converges to x ∗ x ∗ x^(**)x^{*}x∗ for x 0 = 2.15 x 0 = 2.15 x_(0)=2.15x_{0}=2.15x0=2.15, while for x 0 = 2.16 x 0 = 2.16 x_(0)=2.16x_{0}=2.16x0=2.16 it generates square roots of negative numbers. Matlab has the feature of implicitly dealing with complex numbers, and the iterates finally converge (in C C C\mathbb{C}C ) to the solution (see [16]).
Conclusions. The sufficient conditions for guaranteed convergence of the method studied by us may theoretically lead to larger convergence domains (especially sided convergence intervals) than from estimates of attraction balls, while a few examples shown that these domains are larger than those corresponding to some optimal methods of order 8. The performances of the studied method are comparable to those of the Aitken-Steffensen-Newton method studied in [16].

References

[1] Amat, S. and Busquier, S., A two-step Steffensen's method under modified convergence conditions, J. Math. Anal. Appl., 324 (2006), 1084-1092
[2] Amat, S., Busquier, S. and Candela, V., A class of quasi-Newton generalized Steffensen methods on Banach space, J. Comput. Appl. Math., 149 (2002), 397-406
[3] Argyros, I. K. and Hilout, S., On the local convergence of fast two-step Newton-like methods for solving nonlinear equations J. Comput. Appl. Math., 245 (2013), 1-9
[4] Beltyukov, B. A., An analogue of the Aitken-Steffensen method with controlled step, URSS Comput. Math. Math. Phys., 27 (1987), No. 3, 103-112
[5] Cătinaș, E., On some Steffensen-type iterative methods for a class of nonlinear equations, Rev. Anal. Numér. Théor. Approx., 24 (1995), No. 1-2, 37-43
[6] Chun, C., Certain improvements of Chebyshev-Halley methods with accelerated fourth-order convergence, Appl. Math. Comput., 189 (2007), No. 1, 597-601
[7] Chun, C., A geometric construction of iterative formulas of order three, Appl. Math. Lett., 23 (2010), 512-516
[8] Cordero, A. and Torregrosa, R. J., A class of Steffensen type method with optimal order of convergence, Appl. Math. Comput., 217 (2011), 7653-7659
[9] Cordero, A., Torregrosa, J. R. and Vassileva, M. P., A family of modified Ostrowski's methods with optimal eighth order of convergence, Appl. Math. Lett., 24 (2011), No. 12, 2082-2086
[10] Hongmin, R., Qinghio, W. and Weihong, B., A class of two-step Steffensen type methods with fourth order convergence, Appl. Math. Comput., 209 (2009), No. 2, 206-210
[11] Jain, P., Steffensen type method for solving nonlinear equations, Appl. Math. Comput., 194 (2007), 527-533
[12] Kou, J. and Wang, X., Some improvements of Ostrowski's method, Appl. Math. Lett., 23 (2010), No. 1, 92-96
[13] Liu, L. and Wang, X., Eighth-order methods with high efficiency index for solving nonlinear equations, Appl. Math. Comput., 215 (2010), No. 9, 3449-3454
[14] Ortega, J. M. and Rheinboldt, W. C., Iterative Solution on Nonlinear Equations in Several Variables, Academic Press, New York, 1970
[15] Ostrowski, M. A., Solution of equations and systems of equations, Academic Press, New York, 1982
[16] Păvăloiu, I., and Cătinaş, E., On a robust Aitken-Newton method based on the Hermite polynomial, Appl. Math. Comput., 287-288 (2016), 224-231
[17] Păvăloiu, I., Approximation of the root of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32 (1995), No. 1-2, 69-82
[18] Păvăloiu, I., Bilateral approximations of solutions of equations by order three Steffensen-type methods, Studia. Univ. "Babeş-Bolyai", Mathematica (Cluj), LI (2006), No. 3, 87-94
[19] Păvăloiu, I., and Cătinaş, E., On a Steffensen-Hermite method of order three, Appl. Math. Comput., 215 (2009), 2663-2672
[20] Păvăloiu, I. and Cătinaș, E., Bilateral approximations for some Aitken-Steffensen-Hermite type method of order three, Appl. Math. Comput., 217 (2011), 5838-5846
[21] Păvăloiu, I. and Cătinaș, E., On an Aitken-Newton-type method, Numer. Algor., 62 (2013), No. 2, 253-260
[22] Păvăloiu, I. and Cătinaș, E., On a Newton-Steffensen-type method, Appl. Math. Lett., 26 (2013), No. 6, 659-663
[23] Petković, M. S., On a general class of multipoint root-finding methods of high computational efficiency, SIAM J. Numer. Anal., 47 (2010), No. 6, 4402-4414
[24] Quan, Z., Peng, Z. and Wenchao, M., Variant of Steffensen secant method and applications, Appl. Math. Comput, 216 (2010), No. 12, 3486-3496
[25] Sharma, J. R., A composite third order Newton-Steffensen method for solving nonlinear equations, Appl. Math. Comput., 169 (2005), 342-346
[26] Zhanlav, T., Chuluunbaatar, O. and Ulziibayar, V., Two-sided approximation for some Newtons type methods, Appl. Math. Comp., 236 (2014), 239-246
Tiberiu Popoviciu Institute of Numerical Analysis
Romanian Academy
P.O. Box 68-1, Romania
E-mail address: pavaloiu@ictp.acad.ro
  1. Received: 22.09.2017. In revised form: 20.01.2018. Accepted: 27.01.2018
    2010 Mathematics Subject Classification. 65H05.
    Key words and phrases. nonlinear equations, Aitken-Steffensen method, Newton method, inverse interpolatory polynomial, monotone convergence.
2018

Related Posts