Bilateral approximations of solutions of equations by order three Steffensen-type methods

Ion Păvăloiu
(original), html, inverse interpolation, ISI/JCR, nonlinear equations in R, Numerical Analysis, paper, solving F(x)=0 iteratively

Abstract

We study the convergence of a method of Steffensen-type, which is obtained from the Lagrange polynomial of inverse interpolation with controlled nodes. Conditions are given such that the sequences bilaterally approximate the solution of an equation.

Author

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

Keywords

nonlinear equations in R; Steffensen type method; monotone iterations.

PDF

PDF-LaTeX file.

Cite this paper as:

I. Păvăloiu, Bilateral approximations of solutions of equations by order three Steffensen-type methods, Studia Univ. Babeş-Bolyai, Mathematica, vol. 51 (2006) no. 3, pp. 105-114.

About this paper

Journal

Studia Univ. Babeş-Bolyai, Mathematica

Publisher Name

Babes-Bolyai University

Article on the journal website

http://www.cs.ubbcluj.ro/~studia-m/2006-3/pavaloiu.pdf

Print ISSN

0252-1938

Online ISSN

2065-961x

References

[1] Costabile, F., Gualtieri, I.M., Luceri, R., A new iterative method for the computation of the solution of nonlinear equations, Numer. Algorithms, 28, pp. 87-100, 2001.

[2] Frontini, M., Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo 40, pp. 109-119, 2003.

[3] Grau, M., An improvement to the computing of nonlinear equation solutions, Numer. Algorithms. 34, pp.1-12, 2003.

[4] Ostrowski, A., Solution of Equations in Euclidian and Banach Spaces, Academic Press New York and London, 1973.

[5] Pavaloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova 1, 5, pp. 20-43,1997. 113

[6] Pavaloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32, 1-2, pp.69-82, 1995.

[7] Pavaloiu, I., Optimal problems concerning interpolation methods of solution of equations, Publications de L’Institut Mathematique 52 (66) pp 113-126, 1992.

[8] Pavaloiu, I., Optimal effiency index of a class of Hermite iterative methods, with two steps, Rev. Anal. Numer. Theor. Approx. 29, 1, pp. 83-89, 2000.

[9] Pavaloiu, I., Local convergence of general Steffensen type methods, Rev. Anal. Numer. Theor. Approx. 33,1, 79-86, 2004.

[10] Pavaloiu, I., Pop, N., Interpolation and Applications, Risoprint, Cluj-Napoca, 2005 (in Romanian).

[11] Traub, J.F., Iterative Methods for Solutions of Equations, Pretence-Hall Inc., Englewood Cliffs, New Jersey, 1964.

[12] Turowicz, B.A., Sur les derivees d’ordre superieur d’une function inverse, Ann. Polon. Math. 8 pp. 265-269, 1960.

Paper (preprint) in HTML form

2006-098-Pavaloiu-Studia-UBB-Math-Bilateral-approx.-order-3-Steffensen

BILATERAL APPROXIMATIONS OF SOLUTIONS OF EQUATIONS BY ORDER THREE STEFFENSEN-TYPE METHODS

ION PĂVĂLOIUDedicated to Professor Ştefan Cobzaş at his 60 th 60 th  60^("th ")60^{\text {th }}60th  anniversary

Abstract

The convergence of method of Steffensen-type which is obtained from the Lagrange polynomial of inverse interpolation with controlled nodes - is studied in this paper. Conditions are given sequences which bilaterally approximates the solution of an equation.

1. Introduction

In order to approximate the solutions of scalar equations it is suitable to use iteration methods which lead to monotone sequences. Suppose that such a method generates two such sequences, i.e., an increasing sequence ( u n ) n ≥ 0 u n n ≥ 0 (u_(n))_(n >= 0)\left(u_{n}\right)_{n \geq 0}(un)n≥0 and a decreasing sequence ( v n ) n ≥ 0 v n n ≥ 0 (v_(n))_(n >= 0)\left(v_{n}\right)_{n \geq 0}(vn)n≥0. If both converge to the solution x ¯ x ¯ bar(x)\bar{x}x¯ of a given equation, then at each step one obtains the following error control:
max { x ¯ − u n , v n − x ¯ } ≤ v n − u n max x ¯ − u n , v n − x ¯ ≤ v n − u n max{( bar(x))-u_(n),v_(n)-( bar(x))} <= v_(n)-u_(n)\max \left\{\bar{x}-u_{n}, v_{n}-\bar{x}\right\} \leq v_{n}-u_{n}max{x¯−un,vn−x¯}≤vn−un
Such methods can be generated, for example, by combining simultaneously both Newton and chord methods [1], [2], [3], [10].
Conditions for Steffensen and Aitken-Steffensen methods which lead to monotone sequences which bilaterally approximate the root of a given equation, were studied in [6], [10].
It is known that both the Steffensen and Aitken-Steffensen methods are obtained from the chord method in which the interpolation nodes are controlled.
In this paper we shall consider a Steffensen-type method, obtained from the inverse interpolation polynomial of second degree, using three controlled interpolation nodes.
More exactly, consider the following 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 ∈ R , a < b f : [ a , b ] ⟶ R , a , b ∈ R , a < b f:[a,b]longrightarrowR,a,b inR,a < bf:[a, b] \longrightarrow \mathbb{R}, a, b \in \mathbb{R}, a<bf:[a,b]⟶R,a,b∈R,a<b.
Denote by F = f ( [ a , b ] ) F = f ( [ a , b ] ) F=f([a,b])F=f([a, b])F=f([a,b]) the range of f f fff for x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b].
Suppose that f : [ a , b ] ⟶ F f : [ a , b ] ⟶ F f:[a,b]longrightarrow Ff:[a, b] \longrightarrow Ff:[a,b]⟶F is a bijection, that is, there exists f − 1 : F ⟶ [ a , b ] f − 1 : F ⟶ [ a , b ] f^(-1):F longrightarrow[a,b]f^{-1}: F \longrightarrow [a, b]f−1:F⟶[a,b]
Let a 1 , a 2 , a 3 ∈ [ a , b ] , a i ≠ a j a 1 , a 2 , a 3 ∈ [ a , b ] , a i ≠ a j a_(1),a_(2),a_(3)in[a,b],a_(i)!=a_(j)a_{1}, a_{2}, a_{3} \in[a, b], a_{i} \neq a_{j}a1,a2,a3∈[a,b],ai≠aj, for i ≠ j , i ; j = 1 , 3 ― i ≠ j , i ; j = 1 , 3 ¯ i!=j,i;j= bar(1,3)i \neq j, i ; j=\overline{1,3}i≠j,i;j=1,3―, three distinct interpolation nodes and let b 1 = f ( a 1 ) , b 2 = f ( a 2 ) , b 3 = f ( a 3 ) b 1 = f a 1 , b 2 = f a 2 , b 3 = f a 3 b_(1)=f(a_(1)),b_(2)=f(a_(2)),b_(3)=f(a_(3))b_{1}=f\left(a_{1}\right), b_{2}=f\left(a_{2}\right), b_{3}=f\left(a_{3}\right)b1=f(a1),b2=f(a2),b3=f(a3). The inverse interpolation Lagrange polynomial for f − 1 f − 1 f^(-1)f^{-1}f−1 on the nodes b 1 , b 2 , b 3 ∈ F b 1 , b 2 , b 3 ∈ F b_(1),b_(2),b_(3)in Fb_{1}, b_{2}, b_{3} \in Fb1,b2,b3∈F is given by the following relation:
(2) L ( b 1 , b 2 , b 3 ; f − 1 ∣ 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 ) (2) L b 1 , b 2 , b 3 ; f − 1 ∣ 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 {:[(2)L(b_(1),b_(2),b_(3);f^(-1)∣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{align*} L\left(b_{1}, b_{2}, b_{3} ; f^{-1} \mid y\right)= & a_{1}+\left[b_{1}, b_{2} ; f^{-1}\right]\left(y-b_{1}\right) \tag{2}\\ & +\left[b_{1}, b_{2}, b_{3} ; f^{-1}\right]\left(y-b_{1}\right)\left(y-b_{2}\right) \end{align*}(2)L(b1,b2,b3;f−1∣y)=a1+[b1,b2;f−1](y−b1)+[b1,b2,b3;f−1](y−b1)(y−b2)
with the remainder given by:
(3) f − 1 ( y ) − L ( b 1 , b 2 , b 3 ; f − 1 ∣ y ) = [ y , b 1 , b 2 , b 3 ; f − 1 ] ( y − b 1 ) ( y − b 2 ) ( y − b 3 ) (3) f − 1 ( y ) − L b 1 , b 2 , b 3 ; f − 1 ∣ y = y , b 1 , b 2 , b 3 ; f − 1 y − b 1 y − b 2 y − b 3 {:(3)f^(-1)(y)-L(b_(1),b_(2),b_(3);f^(-1)∣y)=[y,b_(1),b_(2),b_(3);f^(-1)](y-b_(1))(y-b_(2))(y-b_(3)):}\begin{equation*} f^{-1}(y)-L\left(b_{1}, b_{2}, b_{3} ; f^{-1} \mid y\right)=\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) \tag{3} \end{equation*}(3)f−1(y)−L(b1,b2,b3;f−1∣y)=[y,b1,b2,b3;f−1](y−b1)(y−b2)(y−b3)
It is known that (2) is symmetric with respect to nodes order. Thus, if ( i 1 , i 2 , i 3 i 1 , i 2 , i 3 i_(1),i_(2),i_(3)i_{1}, i_{2}, i_{3}i1,i2,i3 ) is a permutation of ( 1 , 2 , 3 1 , 2 , 3 1,2,31,2,31,2,3 ), then the following relations are satisfied:
(4) L ( b 1 , b 2 , b 3 ; f − 1 ∣ y ) = a i 1 + [ b i 1 , b i 2 ; f − 1 ] ( y − b i 1 ) + [ b i 1 , b i 2 , b i 3 ; f − 1 ] ( y − b i 1 ) ( y − b i 2 ) (4) L b 1 , b 2 , b 3 ; f − 1 ∣ y = a i 1 + b i 1 , b i 2 ; f − 1 y − b i 1 + b i 1 , b i 2 , b i 3 ; f − 1 y − b i 1 y − b i 2 {:(4)L(b_(1),b_(2),b_(3);f^(-1)∣y)=a_(i_(1))+[b_(i_(1)),b_(i_(2));f^(-1)](y-b_(i_(1)))+[b_(i_(1)),b_(i_(2),)b_(i_(3));f^(-1)](y-b_(i_(1)))(y-b_(i_(2))):}\begin{equation*} L\left(b_{1}, b_{2}, b_{3} ; f^{-1} \mid y\right)=a_{i_{1}}+\left[b_{i_{1}}, b_{i_{2}} ; f^{-1}\right]\left(y-b_{i_{1}}\right)+\left[b_{i_{1}}, b_{i_{2},} b_{i_{3}} ; f^{-1}\right]\left(y-b_{i_{1}}\right)\left(y-b_{i_{2}}\right) \tag{4} \end{equation*}(4)L(b1,b2,b3;f−1∣y)=ai1+[bi1,bi2;f−1](y−bi1)+[bi1,bi2,bi3;f−1](y−bi1)(y−bi2)
Apart from (2), these relations lead to five more representations for Lagrange's polynomial.
In order to obtain a Steffensen-type method, and to approximate the solutions of equations (1), we shall consider one additional equation:
x − g ( x ) = 0 , g : [ a , b ] ⟶ [ a , b ] x − g ( x ) = 0 , g : [ a , b ] ⟶ [ a , b ] x-g(x)=0,quad g:[a,b]longrightarrow[a,b]x-g(x)=0, \quad g:[a, b] \longrightarrow[a, b]x−g(x)=0,g:[a,b]⟶[a,b]
which we shall assume is equivalent with (1).
If equation (1) has one root x ¯ ∈ [ a , b ] x ¯ ∈ [ a , b ] bar(x)in[a,b]\bar{x} \in[a, b]x¯∈[a,b], then obviously x ¯ = f − 1 ( 0 ) x ¯ = f − 1 ( 0 ) bar(x)=f^(-1)(0)\bar{x}=f^{-1}(0)x¯=f−1(0), and from (3) one obtains
x ¯ = L ( b 1 , b 2 , b 3 ; f − 1 ∣ 0 ) − [ 0 , b 1 , b 2 , b 3 ; f − 1 ] b 1 b 2 b 3 x ¯ = L b 1 , b 2 , b 3 ; f − 1 ∣ 0 − 0 , b 1 , b 2 , b 3 ; f − 1 b 1 b 2 b 3 bar(x)=L(b_(1),b_(2),b_(3);f^(-1)∣0)-[0,b_(1),b_(2),b_(3);f^(-1)]b_(1)b_(2)b_(3)\bar{x}=L\left(b_{1}, b_{2}, b_{3} ; f^{-1} \mid 0\right)-\left[0, b_{1}, b_{2}, b_{3} ; f^{-1}\right] b_{1} b_{2} b_{3}x¯=L(b1,b2,b3;f−1∣0)−[0,b1,b2,b3;f−1]b1b2b3
and if we neglect the remainder, we obtain:
(5) x ¯ ≃ L ( b 1 , b 2 , b 3 ; f − 1 ∣ 0 ) (5) x ¯ ≃ L b 1 , b 2 , b 3 ; f − 1 ∣ 0 {:(5) bar(x)≃L(b_(1),b_(2),b_(3);f^(-1)∣0):}\begin{equation*} \bar{x} \simeq L\left(b_{1}, b_{2}, b_{3} ; f^{-1} \mid 0\right) \tag{5} \end{equation*}(5)x¯≃L(b1,b2,b3;f−1∣0)
For divided differences of first and second order of f − 1 f − 1 f^(-1)f^{-1}f−1, one knows that [5], [7], [8], [10]:
(6) [ b 1 , b 2 ; f − 1 ] = 1 [ a 1 , a 2 ; f ] (6) b 1 , b 2 ; f − 1 = 1 a 1 , a 2 ; f {:(6)[b_(1),b_(2);f^(-1)]=(1)/([a_(1),a_(2);f]):}\begin{equation*} \left[b_{1}, b_{2} ; f^{-1}\right]=\frac{1}{\left[a_{1}, a_{2} ; f\right]} \tag{6} \end{equation*}(6)[b1,b2;f−1]=1[a1,a2;f]
and
(7) [ b 1 , b 2 ; b 3 ; f − 1 ] = − [ a 1 , a 2 , a 3 ; f ] [ a 1 , a 2 ; f ] [ a 1 , a 3 ; f ] [ a 2 , a 3 ; f ] (7) b 1 , b 2 ; b 3 ; f − 1 = − a 1 , a 2 , a 3 ; f a 1 , a 2 ; f a 1 , a 3 ; f a 2 , a 3 ; f {:(7)[b_(1),b_(2);b_(3);f^(-1)]=-([a_(1),a_(2),a_(3);f])/([a_(1),a_(2);f][a_(1),a_(3);f][a_(2),a_(3);f]):}\begin{equation*} \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_{1}, a_{3} ; f\right]\left[a_{2}, a_{3} ; f\right]} \tag{7} \end{equation*}(7)[b1,b2;b3;f−1]=−[a1,a2,a3;f][a1,a2;f][a1,a3;f][a2,a3;f]
Relations (2), (5), (6) and (7) lead to the following approximation of x ¯ x ¯ bar(x)\bar{x}x¯ :
(8) x ¯ ≃ 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 2 , a 3 ; f ] [ a 1 , a 3 ; f ] (8) x ¯ ≃ 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 2 , a 3 ; f a 1 , a 3 ; f {:(8) bar(x)≃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_(2),a_(3);f][a_(1),a_(3);f]):}\begin{equation*} \bar{x} \simeq 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_{2}, a_{3} ; f\right]\left[a_{1}, a_{3} ; f\right]} \tag{8} \end{equation*}(8)x¯≃a1−f(a1)[a1,a2;f]−[a1,a2,a3;f]f(a1)f(a2)[a1,a2;f][a2,a3;f][a1,a3;f]
or the equivalent formal representations from (4). Supposing that f f fff has third degree derivatives at each point from [ a , b ] [ a , b ] [a,b][a, b][a,b], then function f − 1 f − 1 f^(-1)f^{-1}f−1 has third degree derivatives at each point of F F FFF.
The following relation is satisfied for the third order derivative of f − 1 f − 1 f^(-1)f^{-1}f−1 [4], [10], [11], [12]:
(9) [ f − 1 ( y ) ] ′ ′ ′ = 3 [ f ′ ′ ( x ) ] 2 − f ′ ( x ) f ′ ′ ′ ( x ) [ f ′ ( x ) ] 5 (9) f − 1 ( y ) ′ ′ ′ = 3 f ′ ′ ( x ) 2 − f ′ ( x ) f ′ ′ ′ ( x ) f ′ ( x ) 5 {:(9)[f^(-1)(y)]^(''')=(3[f^('')(x)]^(2)-f^(')(x)f^(''')(x))/([f^(')(x)]^(5)):}\begin{equation*} \left[f^{-1}(y)\right]^{\prime \prime \prime}=\frac{3\left[f^{\prime \prime}(x)\right]^{2}-f^{\prime}(x) f^{\prime \prime \prime}(x)}{\left[f^{\prime}(x)\right]^{5}} \tag{9} \end{equation*}(9)[f−1(y)]′′′=3[f′′(x)]2−f′(x)f′′′(x)[f′(x)]5
where y = f ( x ) y = f ( x ) y=f(x)y=f(x)y=f(x).
Denote x n ∈ [ a , b ] x n ∈ [ a , b ] x_(n)in[a,b]x_{n} \in[a, b]xn∈[a,b] an approximation to the root x ¯ x ¯ bar(x)\bar{x}x¯ of (1).
We consider the following nodes in (8):
a 1 = x n , a 2 = g ( x n ) , a 3 = g ( g ( x n ) ) a 1 = x n , a 2 = g x n , a 3 = g g x n a_(1)=x_(n),a_(2)=g(x_(n)),a_(3)=g(g(x_(n)))a_{1}=x_{n}, a_{2}=g\left(x_{n}\right), a_{3}=g\left(g\left(x_{n}\right)\right)a1=xn,a2=g(xn),a3=g(g(xn))
Taking into account all six approximative representations of x ¯ x ¯ bar(x)\bar{x}x¯, obtained by permutations of set ( 1 , 2 , 3 1 , 2 , 3 1,2,31,2,31,2,3 ) one obtains the following representations for the Steffensen-type method.
If
D ( x n ) = [ x n , g ( x n ) , g ( g ( x n ) ) ; f ] [ x n , g ( x n ) ; f ] [ x n , g ( g ( x n ) ) ; f ] [ g ( x n ) , g ( g ( x n ) ) ; f ] D x n = x n , g x n , g g x n ; f x n , g x n ; f x n , g g x n ; f g x n , g g x n ; f D(x_(n))=([x_(n),g(x_(n)),g(g(x_(n)));f])/([x_(n),g(x_(n));f][x_(n),g(g(x_(n)));f][g(x_(n)),g(g(x_(n)));f])D\left(x_{n}\right)=\frac{\left[x_{n}, g\left(x_{n}\right), g\left(g\left(x_{n}\right)\right) ; f\right]}{\left[x_{n}, g\left(x_{n}\right) ; f\right]\left[x_{n}, g\left(g\left(x_{n}\right)\right) ; f\right]\left[g\left(x_{n}\right), g\left(g\left(x_{n}\right)\right) ; f\right]}D(xn)=[xn,g(xn),g(g(xn));f][xn,g(xn);f][xn,g(g(xn));f][g(xn),g(g(xn));f]
then the above considerations lead us to the following:
(10) x n + 1 = x n − f ( x n ) [ x n , g ( x n ) ; f ] − D ( x n ) f ( x n ) ⋅ f ( g ( x n ) ) ; (11) x n + 1 = x n − f ( x n ) [ x n , g ( g ( x n ) ) ; f ] − D ( x n ) f ( x n ) ⋅ f ( g ( g ( x n ) ) ) ; (12) x n + 1 = g ( x n ) − f ( g ( x n ) ) [ x n , g ( x n ) ; f ] − D ( x n ) f ( x n ) f ( g ( x n ) ) ; (13) x n + 1 = g ( x n ) − f ( g ( x n ) ) [ g ( x n ) , g ( g ( x n ) ) ; f ] − D ( x n ) f ( g ( x n ) ) f ( g ( g ( x n ) ) ) ; (14) x n + 1 = g ( g ( x n ) ) − f ( g ( g ( x n ) ) ) [ x n , g ( g ( x n ) ) ; f ] − D ( x n ) f ( x n ) f ( g ( g ( x n ) ) ) ; (15) x n + 1 = g ( g ( x n ) ) − f ( g ( g ( x n ) ) ) [ g ( x n ) , g ( g ( x n ) ) ; f ] − D ( x n ) f ( g ( x n ) ) f ( g ( g ( x n ) ) ) . (10) x n + 1 = x n − f x n x n , g x n ; f − D x n f x n ⋅ f g x n ; (11) x n + 1 = x n − f x n x n , g g x n ; f − D x n f x n ⋅ f g g x n ; (12) x n + 1 = g x n − f g x n x n , g x n ; f − D x n f x n f g x n ; (13) x n + 1 = g x n − f g x n g x n , g g x n ; f − D x n f g x n f g g x n ; (14) x n + 1 = g g x n − f g g x n x n , g g x n ; f − D x n f x n f g g x n ; (15) x n + 1 = g g x n − f g g x n g x n , g g x n ; f − D x n f g x n f g g x n . {:[(10)x_(n+1)=x_(n)-(f(x_(n)))/([x_(n),g(x_(n));f])-D(x_(n))f(x_(n))*f(g(x_(n)));],[(11)x_(n+1)=x_(n)-(f(x_(n)))/([x_(n),g(g(x_(n)));f])-D(x_(n))f(x_(n))*f(g(g(x_(n))));],[(12)x_(n+1)=g(x_(n))-(f(g(x_(n))))/([x_(n),g(x_(n));f])-D(x_(n))f(x_(n))f(g(x_(n)));],[(13)x_(n+1)=g(x_(n))-(f(g(x_(n))))/([g(x_(n)),g(g(x_(n)));f])-D(x_(n))f(g(x_(n)))f(g(g(x_(n))));],[(14)x_(n+1)=g(g(x_(n)))-(f(g(g(x_(n)))))/([x_(n),g(g(x_(n)));f])-D(x_(n))f(x_(n))f(g(g(x_(n))));],[(15)x_(n+1)=g(g(x_(n)))-(f(g(g(x_(n)))))/([g(x_(n)),g(g(x_(n)));f])-D(x_(n))f(g(x_(n)))f(g(g(x_(n)))).]:}\begin{align*} & x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n}, g\left(x_{n}\right) ; f\right]}-D\left(x_{n}\right) f\left(x_{n}\right) \cdot f\left(g\left(x_{n}\right)\right) ; \tag{10}\\ & x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n}, g\left(g\left(x_{n}\right)\right) ; f\right]}-D\left(x_{n}\right) f\left(x_{n}\right) \cdot f\left(g\left(g\left(x_{n}\right)\right)\right) ; \tag{11}\\ & x_{n+1}=g\left(x_{n}\right)-\frac{f\left(g\left(x_{n}\right)\right)}{\left[x_{n}, g\left(x_{n}\right) ; f\right]}-D\left(x_{n}\right) f\left(x_{n}\right) f\left(g\left(x_{n}\right)\right) ; \tag{12}\\ & x_{n+1}=g\left(x_{n}\right)-\frac{f\left(g\left(x_{n}\right)\right)}{\left[g\left(x_{n}\right), g\left(g\left(x_{n}\right)\right) ; f\right]}-D\left(x_{n}\right) f\left(g\left(x_{n}\right)\right) f\left(g\left(g\left(x_{n}\right)\right)\right) ; \tag{13}\\ & x_{n+1}=g\left(g\left(x_{n}\right)\right)-\frac{f\left(g\left(g\left(x_{n}\right)\right)\right)}{\left[x_{n}, g\left(g\left(x_{n}\right)\right) ; f\right]}-D\left(x_{n}\right) f\left(x_{n}\right) f\left(g\left(g\left(x_{n}\right)\right)\right) ; \tag{14}\\ & x_{n+1}=g\left(g\left(x_{n}\right)\right)-\frac{f\left(g\left(g\left(x_{n}\right)\right)\right)}{\left[g\left(x_{n}\right), g\left(g\left(x_{n}\right)\right) ; f\right]}-D\left(x_{n}\right) f\left(g\left(x_{n}\right)\right) f\left(g\left(g\left(x_{n}\right)\right)\right) . \tag{15} \end{align*}(10)xn+1=xn−f(xn)[xn,g(xn);f]−D(xn)f(xn)⋅f(g(xn));(11)xn+1=xn−f(xn)[xn,g(g(xn));f]−D(xn)f(xn)⋅f(g(g(xn)));(12)xn+1=g(xn)−f(g(xn))[xn,g(xn);f]−D(xn)f(xn)f(g(xn));(13)xn+1=g(xn)−f(g(xn))[g(xn),g(g(xn));f]−D(xn)f(g(xn))f(g(g(xn)));(14)xn+1=g(g(xn))−f(g(g(xn)))[xn,g(g(xn));f]−D(xn)f(xn)f(g(g(xn)));(15)xn+1=g(g(xn))−f(g(g(xn)))[g(xn),g(g(xn));f]−D(xn)f(g(xn))f(g(g(xn))).
From Newton's identity (3) one obtains the error representation:
(16) x ¯ − x n + 1 = − [ 0 , f ( x n ) , f ( g ( x n ) ) , f ( g ( g ( x n ) ) ) ; f − 1 ] f ( x n ) f ( g ( x n ) ) f ( g ( g ( x n ) ) ) (16) x ¯ − x n + 1 = − 0 , f x n , f g x n , f g g x n ; f − 1 f x n f g x n f g g x n {:(16) bar(x)-x_(n+1)=-[0,f(x_(n)),f(g(x_(n))),f(g(g(x_(n))));f^(-1)]f(x_(n))f(g(x_(n)))f(g(g(x_(n)))):}\begin{equation*} \bar{x}-x_{n+1}=-\left[0, f\left(x_{n}\right), f\left(g\left(x_{n}\right)\right), f\left(g\left(g\left(x_{n}\right)\right)\right) ; f^{-1}\right] f\left(x_{n}\right) f\left(g\left(x_{n}\right)\right) f\left(g\left(g\left(x_{n}\right)\right)\right) \tag{16} \end{equation*}(16)x¯−xn+1=−[0,f(xn),f(g(xn)),f(g(g(xn)));f−1]f(xn)f(g(xn))f(g(g(xn)))
From the mean value formulas for divided differences one obtains for a fixed x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b] the existence of η ∈ F η ∈ F eta in F\eta \in Fη∈F such that:
[ 0 , f ( x ) , f ( g ( x ) ) , f ( g ( g ( x ) ) ) ; f − 1 ] = [ f − 1 ( η ) ] 3 ! 0 , f ( x ) , f ( g ( x ) ) , f ( g ( g ( x ) ) ) ; f − 1 = f − 1 ( η ) 3 ! [0,f(x),f(g(x)),f(g(g(x)));f^(-1)]=([f^(-1)(eta)])/(3!)\left[0, f(x), f(g(x)), f(g(g(x))) ; f^{-1}\right]=\frac{\left[f^{-1}(\eta)\right]}{3!}[0,f(x),f(g(x)),f(g(g(x)));f−1]=[f−1(η)]3!
Since η ∈ F η ∈ F eta in F\eta \in Fη∈F and f f fff is a bijection, using (9) there results the existence of ξ ∈ [ a , b ] ξ ∈ [ a , b ] xi in[a,b]\xi \in[a, b]ξ∈[a,b] such that
[ 0 , f ( x ) , f ( g ( x ) ) , f ( g ( g ( x ) ) ) ; f − 1 ] = 3 [ f ′ ′ ( ξ ) ] 2 − f ′ ( ξ ) f ′ ′ ′ ( ξ ) 6 [ f ′ ( ξ ) ] 5 0 , f ( x ) , f ( g ( x ) ) , f ( g ( g ( x ) ) ) ; f − 1 = 3 f ′ ′ ( ξ ) 2 − f ′ ( ξ ) f ′ ′ ′ ( ξ ) 6 f ′ ( ξ ) 5 [0,f(x),f(g(x)),f(g(g(x)));f^(-1)]=(3[f^('')(xi)]^(2)-f^(')(xi)f^(''')(xi))/(6[f^(')(xi)]^(5))\left[0, f(x), f(g(x)), f(g(g(x))) ; f^{-1}\right]=\frac{3\left[f^{\prime \prime}(\xi)\right]^{2}-f^{\prime}(\xi) f^{\prime \prime \prime}(\xi)}{6\left[f^{\prime}(\xi)\right]^{5}}[0,f(x),f(g(x)),f(g(g(x)));f−1]=3[f′′(ξ)]2−f′(ξ)f′′′(ξ)6[f′(ξ)]5
Denote
(17) E ( x ) = 3 [ f ′ ′ ( x ) ] 2 − f ′ ( x ) f ′ ′ ′ ( x ) (17) E ( x ) = 3 f ′ ′ ( x ) 2 − f ′ ( x ) f ′ ′ ′ ( x ) {:(17)E(x)=3[f^('')(x)]^(2)-f^(')(x)f^(''')(x):}\begin{equation*} E(x)=3\left[f^{\prime \prime}(x)\right]^{2}-f^{\prime}(x) f^{\prime \prime \prime}(x) \tag{17} \end{equation*}(17)E(x)=3[f′′(x)]2−f′(x)f′′′(x)
so that we obtain from (16)
(18) x ¯ − x n + 1 = − E ( ξ n ) 6 [ f ′ ( ξ n ) ] 5 f ( x n ) f ( g ( x n ) ) f ( g ( g ( x n ) ) ) (18) x ¯ − x n + 1 = − E ξ n 6 f ′ ξ n 5 f x n f g x n f g g x n {:(18) bar(x)-x_(n+1)=-(E(xi_(n)))/(6[f^(')(xi_(n))]^(5))f(x_(n))f(g(x_(n)))f(g(g(x_(n)))):}\begin{equation*} \bar{x}-x_{n+1}=-\frac{E\left(\xi_{n}\right)}{6\left[f^{\prime}\left(\xi_{n}\right)\right]^{5}} f\left(x_{n}\right) f\left(g\left(x_{n}\right)\right) f\left(g\left(g\left(x_{n}\right)\right)\right) \tag{18} \end{equation*}(18)x¯−xn+1=−E(ξn)6[f′(ξn)]5f(xn)f(g(xn))f(g(g(xn)))
where ξ n ∈ [ a , b ] ξ n ∈ [ a , b ] xi_(n)in[a,b]\xi_{n} \in[a, b]ξn∈[a,b] is assigned to x = x n x = x n x=x_(n)x=x_{n}x=xn. The x n + 1 x n + 1 x_(n+1)x_{n+1}xn+1 term is given by each of the relations ( 10 ) − ( 15 ) ( 10 ) − ( 15 ) (10)-(15)(10)-(15)(10)−(15).

2. The convergence of Steffensen-type method

In this section we shall see that conditions for the Steffensen-type method of third order given by any relations (10)-(15), lead to sequences which bilaterally approximate the root of (1).
We suppose that g g ggg satisfies the following conditions:
a) there exists l ∈ R , 0 < l < 1 l ∈ R , 0 < l < 1 l inR,0 < l < 1l \in \mathbb{R}, 0<l<1l∈R,0<l<1 such that for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b] :
(19) | g ( x ) − g ( x ¯ ) | ≤ l | x − x ¯ | (19) | g ( x ) − g ( x ¯ ) | ≤ l | x − x ¯ | {:(19)|g(x)-g( bar(x))| <= l|x- bar(x)|:}\begin{equation*} |g(x)-g(\bar{x})| \leq l|x-\bar{x}| \tag{19} \end{equation*}(19)|g(x)−g(x¯)|≤l|x−x¯|
where x ¯ x ¯ bar(x)\bar{x}x¯ is the common root of (1) and x = g ( x ) x = g ( x ) x=g(x)x=g(x)x=g(x);
b) the function g g ggg is decreasing on [ a , b ] [ a , b ] [a,b][a, b][a,b];
c) the equations (1) and x = g ( x ) x = g ( x ) x=g(x)x=g(x)x=g(x) ar equivalent.
The following result holds:
Theorem 1. If functions f , g f , g f,gf, gf,g and element x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b] satisfy the conditions:
i 1 i 1 i_(1)\mathrm{i}_{1}i1. if x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b], then g ( x 0 ) ∈ [ a , b ] g x 0 ∈ [ a , b ] g(x_(0))in[a,b]g\left(x_{0}\right) \in[a, b]g(x0)∈[a,b];
ii 2 ii 2 ii_(2)\mathrm{ii}_{2}ii2. f f fff has third order derivatives on [ a , b ] [ a , b ] [a,b][a, b][a,b];
iii 3 . f ′ ( x ) > 0 , f ′ ′ ( x ) ≥ 0 3 . f ′ ( x ) > 0 , f ′ ′ ( x ) ≥ 0 _(3).f^(')(x) > 0,f^('')(x) >= 0{ }_{3} . f^{\prime}(x)>0, f^{\prime \prime}(x) \geq 03.f′(x)>0,f′′(x)≥0, for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b];
iv 1 iv 1 iv_(1)\operatorname{iv}_{1}iv1. E ( x ) ≤ 0 E ( x ) ≤ 0 E(x) <= 0E(x) \leq 0E(x)≤0 for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b], where E E EEE is given by (17);
v 1 v 1 v_(1)\mathrm{v}_{1}v1. function g g ggg satisfies a)-c);
vi 1 vi 1 vi_(1)\mathrm{vi}_{1}vi1. equation (1) has a root x ¯ ∈ [ a , b ] x ¯ ∈ [ a , b ] bar(x)in[a,b]\bar{x} \in[a, b]x¯∈[a,b].
Then the following properties are true:
j 1 j 1 j_(1)\mathrm{j}_{1}j1. The elements of sequence ( x n ) n ≥ 0 x n n ≥ 0 (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0}(xn)n≥0 generated by (10), where x 0 x 0 x_(0)x_{0}x0 satisfies i 1 i 1 i_(1)i_{1}i1, remain in [ a , b ] [ a , b ] [a,b][a, b][a,b] and for each n = 0 , 1 , … n = 0 , 1 , … n=0,1,dotsn=0,1, \ldotsn=0,1,…, the following relations are satisfied:
(20) x n ≤ x n + 1 ≤ x ¯ ≤ g ( x n + 1 ) ≤ g ( x n ) (20) x n ≤ x n + 1 ≤ x ¯ ≤ g x n + 1 ≤ g x n {:(20)x_(n) <= x_(n+1) <= bar(x) <= g(x_(n+1)) <= g(x_(n)):}\begin{equation*} x_{n} \leq x_{n+1} \leq \bar{x} \leq g\left(x_{n+1}\right) \leq g\left(x_{n}\right) \tag{20} \end{equation*}(20)xn≤xn+1≤x¯≤g(xn+1)≤g(xn)
if f ( x 0 ) < 0 f x 0 < 0 f(x_(0)) < 0f\left(x_{0}\right)<0f(x0)<0, or
(21) x n ≥ x n + 1 ≥ x ¯ ≥ g ( x n + 1 ) ≥ g ( x n ) (21) x n ≥ x n + 1 ≥ x ¯ ≥ g x n + 1 ≥ g x n {:(21)x_(n) >= x_(n+1) >= bar(x) >= g(x_(n+1)) >= g(x_(n)):}\begin{equation*} x_{n} \geq x_{n+1} \geq \bar{x} \geq g\left(x_{n+1}\right) \geq g\left(x_{n}\right) \tag{21} \end{equation*}(21)xn≥xn+1≥x¯≥g(xn+1)≥g(xn)
if f ( x 0 ) > 0 jj 1 . lim x n = lim g ( x n ) = x ¯ jjj 1 . max { | x n + 1 − x ¯ | , | g ( x n ) − x ¯ | } ≤ | x n + 1 − g ( x n ) | , for each n = 0 , 1 , …  if  f x 0 > 0 jj 1 . lim x n = lim g x n = x ¯ jjj 1 . max x n + 1 − x ¯ , g x n − x ¯ ≤ x n + 1 − g x n ,  for each  n = 0 , 1 , … {:[" if "f(x_(0)) > 0],[jj_(1). limx_(n)=lim g(x_(n))= bar(x)],[jjj_(1). max{|x_(n+1)-( bar(x))|,|g(x_(n))-( bar(x))|} <= |x_(n+1)-g(x_(n))|","" for each "n=0","1","dots]:}\begin{aligned} & \text { if } f\left(x_{0}\right)>0 \\ \mathrm{jj}_{1} . & \lim x_{n}=\lim g\left(x_{n}\right)=\bar{x} \\ \mathrm{jjj}_{1} . & \max \left\{\left|x_{n+1}-\bar{x}\right|,\left|g\left(x_{n}\right)-\bar{x}\right|\right\} \leq\left|x_{n+1}-g\left(x_{n}\right)\right|, \text { for each } n=0,1, \ldots \end{aligned} if f(x0)>0jj1.limxn=limg(xn)=x¯jjj1.max{|xn+1−x¯|,|g(xn)−x¯|}≤|xn+1−g(xn)|, for each n=0,1,…
Proof. Let x n ∈ [ a , b ] , n ≥ 0 x n ∈ [ a , b ] , n ≥ 0 x_(n)in[a,b],n >= 0x_{n} \in[a, b], n \geq 0xn∈[a,b],n≥0 for which g ( x n ) ∈ [ a , b ] g x n ∈ [ a , b ] g(x_(n))in[a,b]g\left(x_{n}\right) \in[a, b]g(xn)∈[a,b].
We consider first: f ( x n ) < 0 f x n < 0 f(x_(n)) < 0f\left(x_{n}\right)<0f(xn)<0, that is, x n < x ¯ x n < x ¯ x_(n) < bar(x)x_{n}<\bar{x}xn<x¯. Since g g ggg is decreasing and using g ( x ¯ ) = x ¯ g ( x ¯ ) = x ¯ g( bar(x))= bar(x)g(\bar{x})=\bar{x}g(x¯)=x¯ one obtains:
g ( x n ) > x ¯ g x n > x ¯ g(x_(n)) > bar(x)g\left(x_{n}\right)>\bar{x}g(xn)>x¯
and g ( g ( x n ) ) < x ¯ g g x n < x ¯ g(g(x_(n))) < bar(x)g\left(g\left(x_{n}\right)\right)<\bar{x}g(g(xn))<x¯.
Relation (19) implies:
| g ( g ( x n ) ) − x ¯ | ≤ l | g ( x n ) − x ¯ | ≤ l 2 | x n − x ¯ | g g x n − x ¯ ≤ l g x n − x ¯ ≤ l 2 x n − x ¯ |g(g(x_(n)))-( bar(x))| <= l|g(x_(n))-( bar(x))| <= l^(2)|x_(n)-( bar(x))|\left|g\left(g\left(x_{n}\right)\right)-\bar{x}\right| \leq l\left|g\left(x_{n}\right)-\bar{x}\right| \leq l^{2}\left|x_{n}-\bar{x}\right||g(g(xn))−x¯|≤l|g(xn)−x¯|≤l2|xn−x¯|
from which one obtains:
(22) a ≤ x n < g ( g ( x n ) ) < x ¯ < g ( x n ) ≤ b (22) a ≤ x n < g g x n < x ¯ < g x n ≤ b {:(22)a <= x_(n) < g(g(x_(n))) < bar(x) < g(x_(n)) <= b:}\begin{equation*} a \leq x_{n}<g\left(g\left(x_{n}\right)\right)<\bar{x}<g\left(x_{n}\right) \leq b \tag{22} \end{equation*}(22)a≤xn<g(g(xn))<x¯<g(xn)≤b
By use of iii 1 1 _(1)_{1}1, (22) and (10) one gets
(23) x n + 1 ≥ x n (23) x n + 1 ≥ x n {:(23)x_(n+1) >= x_(n):}\begin{equation*} x_{n+1} \geq x_{n} \tag{23} \end{equation*}(23)xn+1≥xn
The assumptions ii 1 − iv 1 ii 1 − iv 1 ii_(1)-iv_(1)\mathrm{ii}_{1}-\mathrm{iv}_{1}ii1−iv1 and from (22) and (18) we get
x ¯ − x n + 1 > 0 x ¯ − x n + 1 > 0 bar(x)-x_(n+1) > 0\bar{x}-x_{n+1}>0x¯−xn+1>0
i.e., x ¯ > x n + 1 x ¯ > x n + 1 bar(x) > x_(n+1)\bar{x}>x_{n+1}x¯>xn+1, that is f ( x n + 1 ) < 0 f x n + 1 < 0 f(x_(n+1)) < 0f\left(x_{n+1}\right)<0f(xn+1)<0.
Using (23) and assumption c c ccc ) on g g ggg one obtains g ( x n + 1 ) ≤ g ( x n ) g x n + 1 ≤ g x n g(x_(n+1)) <= g(x_(n))g\left(x_{n+1}\right) \leq g\left(x_{n}\right)g(xn+1)≤g(xn) and g ( x n + 1 ) > g ( x ¯ ) = x ¯ g x n + 1 > g ( x ¯ ) = x ¯ g(x_(n+1)) > g( bar(x))= bar(x)g\left(x_{n+1}\right)>g(\bar{x})=\bar{x}g(xn+1)>g(x¯)=x¯. Hence we have shown (20).
We consider now the case f ( x n ) > 0 f x n > 0 f(x_(n)) > 0f\left(x_{n}\right)>0f(xn)>0, that is x n > x ¯ x n > x ¯ x_(n) > bar(x)x_{n}>\bar{x}xn>x¯.
Taking in consideration (11) instead of (10) and by use of
g ( x n ) < x ¯ g x n < x ¯ g(x_(n)) < bar(x)g\left(x_{n}\right)<\bar{x}g(xn)<x¯
and g ( g ( x n ) ) > x ¯ g g x n > x ¯ g(g(x_(n))) > bar(x)g\left(g\left(x_{n}\right)\right)>\bar{x}g(g(xn))>x¯, one gets:
f ( g ( x n ) ) < 0 , f ( g ( g ( x n ) ) ) > 0 f g x n < 0 , f g g x n > 0 f(g(x_(n))) < 0,quad f(g(g(x_(n)))) > 0f\left(g\left(x_{n}\right)\right)<0, \quad f\left(g\left(g\left(x_{n}\right)\right)\right)>0f(g(xn))<0,f(g(g(xn)))>0
It is obvious to note relations (21).
Eventually, (20) and (21) show that 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 ( x n ) ) n ≥ 0 g x n n ≥ 0 (g(x_(n)))_(n >= 0)\left(g\left(x_{n}\right)\right)_{n \geq 0}(g(xn))n≥0 converge. Denote lim x n = a lim x n = a limx_(n)=a\lim x_{n}=alimxn=a, then,we obtain lim g ( x n ) = g ( a ) lim g x n = g ( a ) lim g(x_(n))=g(a)\lim g\left(x_{n}\right)=g(a)limg(xn)=g(a). Using (10) or (11) as n → ∞ n → ∞ n rarr oon \rightarrow \inftyn→∞, it results that f ( a ) = 0 f ( a ) = 0 f(a)=0f(a)=0f(a)=0 and therefore a = x ¯ a = x ¯ a= bar(x)a=\bar{x}a=x¯, the unique solution of (1) on [ a , b ] [ a , b ] [a,b][a, b][a,b].
Remark 2. Suppose the assumptions from Theorem 1 are satisfied and excepting i i i 1 i i i 1 iii_(1)i i i_{1}iii1, the following assumption holds.
f ′ ( x ) < 0 f ′ ( x ) < 0 f^(')(x) < 0f^{\prime}(x)<0f′(x)<0 and f ′ ′ ( x ) < 0 f ′ ′ ( x ) < 0 f^('')(x) < 0f^{\prime \prime}(x)<0f′′(x)<0 for each x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b] and consider instead of (1) the following equation:
(24) h ( x ) = 0 (24) h ( x ) = 0 {:(24)h(x)=0:}\begin{equation*} h(x)=0 \tag{24} \end{equation*}(24)h(x)=0
where h h hhh is given by h ( x ) = − f ( x ) h ( x ) = − f ( x ) h(x)=-f(x)h(x)=-f(x)h(x)=−f(x).
Note that Theorem 1 holds for (24).
The proof is obvious, since h ′ ( x ) > 0 h ′ ( x ) > 0 h^(')(x) > 0h^{\prime}(x)>0h′(x)>0 and h ′ ′ ( x ) > 0 h ′ ′ ( x ) > 0 h^('')(x) > 0h^{\prime \prime}(x)>0h′′(x)>0, for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b] and E ( x ) = 3 [ h ′ ′ ( x ) ] 2 − h ′ ( x ) h ′ ′ ( x ) < 0 E ( x ) = 3 h ′ ′ ( x ) 2 − h ′ ( x ) h ′ ′ ( x ) < 0 E(x)=3[h^('')(x)]^(2)-h^(')(x)h^('')(x) < 0E(x)=3\left[h^{\prime \prime}(x)\right]^{2}-h^{\prime}(x) h^{\prime \prime}(x)<0E(x)=3[h′′(x)]2−h′(x)h′′(x)<0, that is E E EEE remains invariant.
A result similar to Theorem 1 holds, for the case in which f f fff is decreasing and convex.
Theorem 3. If functions f , g f , g f,gf, gf,g and element x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b] satisfy the following conditions:
i 2 i 2 i_(2)\mathrm{i}_{2}i2. if x 0 ∈ [ a , b ] x 0 ∈ [ a , b ] x_(0)in[a,b]x_{0} \in[a, b]x0∈[a,b], then g ( x 0 ) ∈ [ a , b ] g x 0 ∈ [ a , b ] g(x_(0))in[a,b]g\left(x_{0}\right) \in[a, b]g(x0)∈[a,b];
ii 2 ii 2 ii_(2)\mathrm{ii}_{2}ii2. f f fff has third order derivative on [ a , b ] [ a , b ] [a,b][a, b][a,b];
iii. f ′ ( x ) < 0 f ′ ( x ) < 0 f^(')(x) < 0f^{\prime}(x)<0f′(x)<0 and f ′ ′ ( x ) > 0 f ′ ′ ( x ) > 0 f^('')(x) > 0f^{\prime \prime}(x)>0f′′(x)>0, for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b];
iv 2 iv 2 iv_(2)\mathrm{iv}_{2}iv2. E ( x ) ≤ 0 E ( x ) ≤ 0 E(x) <= 0E(x) \leq 0E(x)≤0, for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b];
v 2 v 2 v_(2)\mathrm{v}_{2}v2. function g g ggg satisfies a a aaa )-c);
vi 2 2 _(2){ }_{2}2. equation (1) has one root x ¯ ∈ [ a , b ] x ¯ ∈ [ a , b ] bar(x)in[a,b]\bar{x} \in[a, b]x¯∈[a,b].
Then ( x n ) n ≥ 0 x n n ≥ 0 (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0}(xn)n≥0 generated by (10) or (11), remains in [ a , b ] [ a , b ] [a,b][a, b][a,b], and relation j 1 − j j j 1 j 1 − j j j 1 j_(1)-jjj_(1)j_{1}- j j j_{1}j1−jjj1 from Theorem 1 are satisfied, when x 0 x 0 x_(0)x_{0}x0 satisfies i 2 i 2 i_(2)i_{2}i2.
Proof. The assumption iii 1 1 _(1){ }_{1}1 leads to D ( x ) < 0 D ( x ) < 0 D(x) < 0D(x)<0D(x)<0 for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b]. Let x n ∈ [ a , b ] , n ≥ 0 x n ∈ [ a , b ] , n ≥ 0 x_(n)in[a,b],n >= 0x_{n} \in[a, b], n \geq 0xn∈[a,b],n≥0, an element for which g ( x n ) ∈ [ a , b ] g x n ∈ [ a , b ] g(x_(n))in[a,b]g\left(x_{n}\right) \in[a, b]g(xn)∈[a,b].
If x n > x ¯ x n > x ¯ x_(n) > bar(x)x_{n}>\bar{x}xn>x¯, then f ( x n ) < 0 f x n < 0 f(x_(n)) < 0f\left(x_{n}\right)<0f(xn)<0 and g ( x n ) < x ¯ , g ( g ( x n ) ) > x ¯ g x n < x ¯ , g g x n > x ¯ g(x_(n)) < bar(x),g(g(x_(n))) > bar(x)g\left(x_{n}\right)<\bar{x}, g\left(g\left(x_{n}\right)\right)>\bar{x}g(xn)<x¯,g(g(xn))>x¯.
From (19) one gets
| g ( g ( x n ) ) − x ¯ | ≤ l 2 | x n − x ¯ | , g g x n − x ¯ ≤ l 2 x n − x ¯ , |g(g(x_(n)))-( bar(x))| <= l^(2)|x_(n)-( bar(x))|,\left|g\left(g\left(x_{n}\right)\right)-\bar{x}\right| \leq l^{2}\left|x_{n}-\bar{x}\right|,|g(g(xn))−x¯|≤l2|xn−x¯|,
that is the following relations hold:
a ≤ g ( x n ) < x ¯ < g ( g ( x n ) ) < x n ≤ b . a ≤ g x n < x ¯ < g g x n < x n ≤ b . a <= g(x_(n)) < bar(x) < g(g(x_(n))) < x_(n) <= b.a \leq g\left(x_{n}\right)<\bar{x}<g\left(g\left(x_{n}\right)\right)<x_{n} \leq b .a≤g(xn)<x¯<g(g(xn))<xn≤b.
From iii 2 , f ( x 2 ) < 0 2 , f x 2 < 0 _(2),f(x_(2)) < 0{ }_{2}, f\left(x_{2}\right)<02,f(x2)<0 and using D ( x n ) < 0 D x n < 0 D(x_(n)) < 0D\left(x_{n}\right)<0D(xn)<0, (10) one obtains
x n + 1 < x n . x n + 1 < x n . x_(n+1) < x_(n).x_{n+1}<x_{n} .xn+1<xn.
The assumptions ii 2 − iv 2 ii 2 − iv 2 ii_(2)-iv_(2)\mathrm{ii}_{2}-\mathrm{iv}_{2}ii2−iv2 and relations (22), and (18) imply
x ¯ − x n + 1 < 0 x ¯ − x n + 1 < 0 bar(x)-x_(n+1) < 0\bar{x}-x_{n+1}<0x¯−xn+1<0
that is, x n + 1 > x ¯ , f ( x n + 1 ) < 0 x n + 1 > x ¯ , f x n + 1 < 0 x_(n+1) > bar(x),f(x_(n+1)) < 0x_{n+1}>\bar{x}, f\left(x_{n+1}\right)<0xn+1>x¯,f(xn+1)<0. Obviously relations (21) hold.
Relations (20) and consequences jj 1 jj 1 jj_(1)\mathrm{jj}_{1}jj1 and jjj 1 jjj 1 jjj_(1)\mathrm{jjj}_{1}jjj1 are proven analogously to Theorem 1.
Remark 4. If f f fff is increasing and concave, that is, f ′ ( x ) > 0 f ′ ( x ) > 0 f^(')(x) > 0f^{\prime}(x)>0f′(x)>0 and f ′ ( x ) < 0 f ′ ( x ) < 0 f^(')(x) < 0f^{\prime}(x)<0f′(x)<0, then obviously h = − f h = − f h=-fh=-fh=−f is decreasing and convex.
If we replace in Theorem 3: function f f fff by function h h hhh, and if we take into account that function E E EEE remains invariant by this replacement, then we note that the statements of Theorem 3 remain true.

3. Determination of the auxiliary function

In the following, by use of function f f fff, we give a method to determine auxiliary function g g ggg, which could assure the control of interpolatory nodes.
If f f fff is a convex function, i.e. f ′ ′ ( x ) > 0 f ′ ′ ( x ) > 0 f^('')(x) > 0f^{\prime \prime}(x)>0f′′(x)>0, then for function g g ggg we consider
(25) g ( x ) = x − f ( x ) f ′ ( x ) (25) g ( x ) = x − f ( x ) f ′ ( x ) {:(25)g(x)=x-(f(x))/(f^(')(x)):}\begin{equation*} g(x)=x-\frac{f(x)}{f^{\prime}(x)} \tag{25} \end{equation*}(25)g(x)=x−f(x)f′(x)
If f f fff is a concave function, then we can set
(26) g ( x ) = x − f ( x ) f ′ ( b ) (26) g ( x ) = x − f ( x ) f ′ ( b ) {:(26)g(x)=x-(f(x))/(f^(')(b)):}\begin{equation*} g(x)=x-\frac{f(x)}{f^{\prime}(b)} \tag{26} \end{equation*}(26)g(x)=x−f(x)f′(b)
Obviously in both cases we have g ′ ( x ) < 0 g ′ ( x ) < 0 g^(')(x) < 0g^{\prime}(x)<0g′(x)<0 and thus function g g ggg satisfies assumption b).
It is clear that function g g ggg given by either (25) or (26), assures the equivalence of (1) and x = g ( x ) x = g ( x ) x=g(x)x=g(x)x=g(x), i.e., g g ggg satisfies assumption c c ccc ).
In order that g g ggg also satisfies assumption a a aaa ), it is enough that the following relations hold:
| 1 − f ′ ( x ) f ( a ) | < 1 1 − f ′ ( x ) f ( a ) < 1 |1-(f^(')(x))/(f(a))| < 1\left|1-\frac{f^{\prime}(x)}{f(a)}\right|<1|1−f′(x)f(a)|<1
for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b], if f f fff is convex function, or
| 1 − f ′ ( x ) f ( b ) | < 1 1 − f ′ ( x ) f ( b ) < 1 |1-(f^(')(x))/(f(b))| < 1\left|1-\frac{f^{\prime}(x)}{f(b)}\right|<1|1−f′(x)f(b)|<1
for all x ∈ [ a , b ] x ∈ [ a , b ] x in[a,b]x \in[a, b]x∈[a,b], if f f fff is a concave function.

References

[1] Costabile, F., Gualtieri, I.M., Luceri, R., A new iterative method for the computation of the solution of nonlinear equations, Numer. Algorithms, 28, pp. 87-100, 2001.
[2] Frontini, M., Hermite interpolation and a new iterative method for the computation of the roots of non-linear equations, Calcolo 40, pp. 109-119, 2003.
[3] Grau, M., An improvement to the computing of nonlinear equation solutions, Numer. Algorithms. 34, pp.1-12, 2003.
[4] Ostrowski, A., Solution of Equations in Euclidian and Banach Spaces, Academic Press New York and London, 1973.
[5] Păvăloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova 1, 5, pp. 20-43,1997.
[6] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32, 1-2, pp.69-82, 1995.
[7] Păvăloiu, I., Optimal problems concerning interpolation methods of solution of equations, Publications de L'Institut Mathematique 52 (66) pp 113-126, 1992.
[8] Păvăloiu, I., Optimal effiency index of a class of Hermite iterative methods, with two steps, Rev. Anal. Numer. Theor. Approx. 29, 1, pp. 83-89, 2000.
[9] Păvăloiu, I., Local convergence of general Steffensen type methods, Rev. Anal. Numér. Théor. Approx. 33,1, 79-86, 2004.
[10] Păvăloiu, I., Pop, N., Interpolation and Applications, Risoprint, Cluj-Napoca, 2005 (in Romanian).
[11] Traub, J.F., Iterative Methods for Solutions of Equations, Pretence-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[12] Turowicz, B.A., Sur les derivées d'ordre superieur d'une function inverse, Ann. Polon. Math. 8 pp. 265-269, 1960.

"T. Popoviciu" Institute of Numerical Analysis, P.O. Box 68-1, Cluj-Napoca, RomaniaE-mail address: pavaloiu@ictp.acad.ro, web.ictp.acad.ro/pavaloiu

  1. Received by the editors: 03.04.2006.
    2000 Mathematics Subject Classification. 65H05.
    Key words and phrases. Nonlinear equations in R R R\mathbb{R}R, Steffensen methods.
    This work has been supported by the Romanian Academy under grant GAR14/2005.
2006

Related Posts