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.
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
Publisher Name
Babes-Bolyai University
Article on the journal website
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
BILATERAL APPROXIMATIONS OF SOLUTIONS OF EQUATIONS BY ORDER THREE STEFFENSEN-TYPE METHODS
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)\left(u_{n}\right)_{n \geq 0} and a decreasing sequence (v_(n))_(n >= 0)\left(v_{n}\right)_{n \geq 0}. If both converge to the solution bar(x)\bar{x} of a given equation, then at each step one obtains the following error control:
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}
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:}\begin{equation*}
f(x)=0 \tag{1}
\end{equation*}
where f:[a,b]longrightarrowR,a,b inR,a < bf:[a, b] \longrightarrow \mathbb{R}, a, b \in \mathbb{R}, a<b.
Denote by F=f([a,b])F=f([a, b]) the range of ff for x in[a,b]x \in[a, b].
Suppose that f:[a,b]longrightarrow Ff:[a, b] \longrightarrow F is a bijection, that is, there exists f^(-1):F longrightarrow[a,b]f^{-1}: F \longrightarrow [a, b]
Denote by F=f([a,b])F=f([a, b]) the range of ff for x in[a,b]x \in[a, b].
Suppose that f:[a,b]longrightarrow Ff:[a, b] \longrightarrow F is a bijection, that is, there exists f^(-1):F longrightarrow[a,b]f^{-1}: F \longrightarrow [a, b]
Let 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}, for i!=j,i;j= bar(1,3)i \neq j, i ; j=\overline{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\left(a_{1}\right), b_{2}=f\left(a_{2}\right), b_{3}=f\left(a_{3}\right). The inverse interpolation Lagrange polynomial for f^(-1)f^{-1} on the nodes b_(1),b_(2),b_(3)in Fb_{1}, b_{2}, b_{3} \in 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))]:}\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*}
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)):}\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*}
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} ) is a permutation of ( 1,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))):}\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*}
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,quad g:[a,b]longrightarrow[a,b]x-g(x)=0, \quad g:[a, b] \longrightarrow[a, b]
which we shall assume is equivalent with (1).
If equation (1) has one root bar(x)in[a,b]\bar{x} \in[a, b], then obviously bar(x)=f^(-1)(0)\bar{x}=f^{-1}(0), and from (3) one obtains
If equation (1) has one root bar(x)in[a,b]\bar{x} \in[a, b], then obviously bar(x)=f^(-1)(0)\bar{x}=f^{-1}(0), and from (3) one obtains
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}
and if we neglect the remainder, we obtain:
{:(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*}
For divided differences of first and second order of f^(-1)f^{-1}, one knows that [5], [7], [8], [10]:
{:(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*}
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]):}\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*}
Relations (2), (5), (6) and (7) lead to the following approximation of bar(x)\bar{x} :
{:(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*}
or the equivalent formal representations from (4). Supposing that ff has third degree derivatives at each point from [a,b][a, b], then function f^(-1)f^{-1} has third degree derivatives at each point of FF.
The following relation is satisfied for the third order derivative of f^(-1)f^{-1} [4], [10], [11], [12]:
{:(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*}
where y=f(x)y=f(x).
Denote x_(n)in[a,b]x_{n} \in[a, b] an approximation to the root bar(x)\bar{x} of (1).
We consider the following nodes in (8):
Denote x_(n)in[a,b]x_{n} \in[a, b] an approximation to the root bar(x)\bar{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\left(x_{n}\right), a_{3}=g\left(g\left(x_{n}\right)\right)
Taking into account all six approximative representations of bar(x)\bar{x}, obtained by permutations of set ( 1,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\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]}
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)))).]:}\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*}
From Newton's identity (3) one obtains the error representation:
{:(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*}
From the mean value formulas for divided differences one obtains for a fixed x in[a,b]x \in[a, b] the existence of eta in F\eta \in F such that:
[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!}
Since eta in F\eta \in F and ff is a bijection, using (9) there results the existence of xi in[a,b]\xi \in[a, b] such that
[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}}
Denote
{:(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*}
so that we obtain from (16)
{:(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*}
where xi_(n)in[a,b]\xi_{n} \in[a, b] is assigned to x=x_(n)x=x_{n}. The x_(n+1)x_{n+1} term is given by each of the relations (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 gg satisfies the following conditions:
a) there exists l inR,0 < l < 1l \in \mathbb{R}, 0<l<1 such that for all x in[a,b]x \in[a, b] :
a) there exists l inR,0 < l < 1l \in \mathbb{R}, 0<l<1 such that for all x in[a,b]x \in[a, b] :
{:(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*}
where bar(x)\bar{x} is the common root of (1) and x=g(x)x=g(x);
b) the function gg is decreasing on [a,b][a, b];
c) the equations (1) and x=g(x)x=g(x) ar equivalent.
b) the function gg is decreasing on [a,b][a, b];
c) the equations (1) and x=g(x)x=g(x) ar equivalent.
The following result holds:
Theorem 1. If functions f,gf, g and element x_(0)in[a,b]x_{0} \in[a, b] satisfy the conditions:
i_(1)\mathrm{i}_{1}. if x_(0)in[a,b]x_{0} \in[a, b], then g(x_(0))in[a,b]g\left(x_{0}\right) \in[a, b];
ii_(2)\mathrm{ii}_{2}. ff has third order derivatives on [a,b][a, b];
iii _(3).f^(')(x) > 0,f^('')(x) >= 0{ }_{3} . f^{\prime}(x)>0, f^{\prime \prime}(x) \geq 0, for all x in[a,b]x \in[a, b];
iv_(1)\operatorname{iv}_{1}. E(x) <= 0E(x) \leq 0 for all x in[a,b]x \in[a, b], where EE is given by (17);
v_(1)\mathrm{v}_{1}. function gg satisfies a)-c);
vi_(1)\mathrm{vi}_{1}. equation (1) has a root bar(x)in[a,b]\bar{x} \in[a, b].
Then the following properties are true:
j_(1)\mathrm{j}_{1}. The elements of sequence (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0} generated by (10), where x_(0)x_{0} satisfies i_(1)i_{1}, remain in [a,b][a, b] and for each n=0,1,dotsn=0,1, \ldots, the following relations are satisfied:
Theorem 1. If functions f,gf, g and element x_(0)in[a,b]x_{0} \in[a, b] satisfy the conditions:
i_(1)\mathrm{i}_{1}. if x_(0)in[a,b]x_{0} \in[a, b], then g(x_(0))in[a,b]g\left(x_{0}\right) \in[a, b];
ii_(2)\mathrm{ii}_{2}. ff has third order derivatives on [a,b][a, b];
iii _(3).f^(')(x) > 0,f^('')(x) >= 0{ }_{3} . f^{\prime}(x)>0, f^{\prime \prime}(x) \geq 0, for all x in[a,b]x \in[a, b];
iv_(1)\operatorname{iv}_{1}. E(x) <= 0E(x) \leq 0 for all x in[a,b]x \in[a, b], where EE is given by (17);
v_(1)\mathrm{v}_{1}. function gg satisfies a)-c);
vi_(1)\mathrm{vi}_{1}. equation (1) has a root bar(x)in[a,b]\bar{x} \in[a, b].
Then the following properties are true:
j_(1)\mathrm{j}_{1}. The elements of sequence (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0} generated by (10), where x_(0)x_{0} satisfies i_(1)i_{1}, remain in [a,b][a, b] and for each n=0,1,dotsn=0,1, \ldots, the following relations are satisfied:
{:(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*}
if f(x_(0)) < 0f\left(x_{0}\right)<0, or
{:(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*}
{:[" 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}
Proof. Let x_(n)in[a,b],n >= 0x_{n} \in[a, b], n \geq 0 for which g(x_(n))in[a,b]g\left(x_{n}\right) \in[a, b].
We consider first: f(x_(n)) < 0f\left(x_{n}\right)<0, that is, x_(n) < bar(x)x_{n}<\bar{x}. Since gg is decreasing and using g( bar(x))= bar(x)g(\bar{x})=\bar{x} one obtains:
We consider first: f(x_(n)) < 0f\left(x_{n}\right)<0, that is, x_(n) < bar(x)x_{n}<\bar{x}. Since gg is decreasing and using g( bar(x))= bar(x)g(\bar{x})=\bar{x} one obtains:
g(x_(n)) > bar(x)g\left(x_{n}\right)>\bar{x}
and g(g(x_(n))) < bar(x)g\left(g\left(x_{n}\right)\right)<\bar{x}.
Relation (19) implies:
Relation (19) implies:
|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|
from which one obtains:
{:(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*}
By use of iii _(1)_{1}, (22) and (10) one gets
{:(23)x_(n+1) >= x_(n):}\begin{equation*}
x_{n+1} \geq x_{n} \tag{23}
\end{equation*}
The assumptions ii_(1)-iv_(1)\mathrm{ii}_{1}-\mathrm{iv}_{1} and from (22) and (18) we get
bar(x)-x_(n+1) > 0\bar{x}-x_{n+1}>0
i.e., bar(x) > x_(n+1)\bar{x}>x_{n+1}, that is f(x_(n+1)) < 0f\left(x_{n+1}\right)<0.
Using (23) and assumption cc ) on gg one obtains g(x_(n+1)) <= g(x_(n))g\left(x_{n+1}\right) \leq g\left(x_{n}\right) and g(x_(n+1)) > g( bar(x))= bar(x)g\left(x_{n+1}\right)>g(\bar{x})=\bar{x}. Hence we have shown (20).
Using (23) and assumption cc ) on gg one obtains g(x_(n+1)) <= g(x_(n))g\left(x_{n+1}\right) \leq g\left(x_{n}\right) and g(x_(n+1)) > g( bar(x))= bar(x)g\left(x_{n+1}\right)>g(\bar{x})=\bar{x}. Hence we have shown (20).
We consider now the case f(x_(n)) > 0f\left(x_{n}\right)>0, that is x_(n) > bar(x)x_{n}>\bar{x}.
Taking in consideration (11) instead of (10) and by use of
Taking in consideration (11) instead of (10) and by use of
g(x_(n)) < bar(x)g\left(x_{n}\right)<\bar{x}
and g(g(x_(n))) > bar(x)g\left(g\left(x_{n}\right)\right)>\bar{x}, one gets:
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)>0
It is obvious to note relations (21).
Eventually, (20) and (21) show that sequences (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0} and (g(x_(n)))_(n >= 0)\left(g\left(x_{n}\right)\right)_{n \geq 0} converge. Denote limx_(n)=a\lim x_{n}=a, then,we obtain lim g(x_(n))=g(a)\lim g\left(x_{n}\right)=g(a). Using (10) or (11) as n rarr oon \rightarrow \infty, it results that f(a)=0f(a)=0 and therefore a= bar(x)a=\bar{x}, the unique solution of (1) on [a,b][a, b].
Eventually, (20) and (21) show that sequences (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0} and (g(x_(n)))_(n >= 0)\left(g\left(x_{n}\right)\right)_{n \geq 0} converge. Denote limx_(n)=a\lim x_{n}=a, then,we obtain lim g(x_(n))=g(a)\lim g\left(x_{n}\right)=g(a). Using (10) or (11) as n rarr oon \rightarrow \infty, it results that f(a)=0f(a)=0 and therefore a= bar(x)a=\bar{x}, the unique solution of (1) on [a,b][a, b].
Remark 2. Suppose the assumptions from Theorem 1 are satisfied and excepting iii_(1)i i i_{1}, the following assumption holds.
f^(')(x) < 0f^{\prime}(x)<0 and f^('')(x) < 0f^{\prime \prime}(x)<0 for each x in[a,b]x \in[a, b] and consider instead of (1) the following equation:
f^(')(x) < 0f^{\prime}(x)<0 and f^('')(x) < 0f^{\prime \prime}(x)<0 for each x in[a,b]x \in[a, b] and consider instead of (1) the following equation:
{:(24)h(x)=0:}\begin{equation*}
h(x)=0 \tag{24}
\end{equation*}
where hh is given by h(x)=-f(x)h(x)=-f(x).
Note that Theorem 1 holds for (24).
The proof is obvious, since h^(')(x) > 0h^{\prime}(x)>0 and h^('')(x) > 0h^{\prime \prime}(x)>0, for all x in[a,b]x \in[a, b] and 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)<0, that is EE remains invariant.
Note that Theorem 1 holds for (24).
The proof is obvious, since h^(')(x) > 0h^{\prime}(x)>0 and h^('')(x) > 0h^{\prime \prime}(x)>0, for all x in[a,b]x \in[a, b] and 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)<0, that is EE remains invariant.
A result similar to Theorem 1 holds, for the case in which ff is decreasing and convex.
Theorem 3. If functions f,gf, g and element x_(0)in[a,b]x_{0} \in[a, b] satisfy the following conditions:
i_(2)\mathrm{i}_{2}. if x_(0)in[a,b]x_{0} \in[a, b], then g(x_(0))in[a,b]g\left(x_{0}\right) \in[a, b];
ii_(2)\mathrm{ii}_{2}. ff has third order derivative on [a,b][a, b];
iii. f^(')(x) < 0f^{\prime}(x)<0 and f^('')(x) > 0f^{\prime \prime}(x)>0, for all x in[a,b]x \in[a, b];
iv_(2)\mathrm{iv}_{2}. E(x) <= 0E(x) \leq 0, for all x in[a,b]x \in[a, b];
v_(2)\mathrm{v}_{2}. function gg satisfies aa )-c);
vi _(2){ }_{2}. equation (1) has one root bar(x)in[a,b]\bar{x} \in[a, b].
Then (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0} generated by (10) or (11), remains in [a,b][a, b], and relation j_(1)-jjj_(1)j_{1}- j j j_{1} from Theorem 1 are satisfied, when x_(0)x_{0} satisfies i_(2)i_{2}.
i_(2)\mathrm{i}_{2}. if x_(0)in[a,b]x_{0} \in[a, b], then g(x_(0))in[a,b]g\left(x_{0}\right) \in[a, b];
ii_(2)\mathrm{ii}_{2}. ff has third order derivative on [a,b][a, b];
iii. f^(')(x) < 0f^{\prime}(x)<0 and f^('')(x) > 0f^{\prime \prime}(x)>0, for all x in[a,b]x \in[a, b];
iv_(2)\mathrm{iv}_{2}. E(x) <= 0E(x) \leq 0, for all x in[a,b]x \in[a, b];
v_(2)\mathrm{v}_{2}. function gg satisfies aa )-c);
vi _(2){ }_{2}. equation (1) has one root bar(x)in[a,b]\bar{x} \in[a, b].
Then (x_(n))_(n >= 0)\left(x_{n}\right)_{n \geq 0} generated by (10) or (11), remains in [a,b][a, b], and relation j_(1)-jjj_(1)j_{1}- j j j_{1} from Theorem 1 are satisfied, when x_(0)x_{0} satisfies i_(2)i_{2}.
Proof. The assumption iii _(1){ }_{1} leads to D(x) < 0D(x)<0 for all x in[a,b]x \in[a, b]. Let x_(n)in[a,b],n >= 0x_{n} \in[a, b], n \geq 0, an element for which g(x_(n))in[a,b]g\left(x_{n}\right) \in[a, b].
If x_(n) > bar(x)x_{n}>\bar{x}, then f(x_(n)) < 0f\left(x_{n}\right)<0 and 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}.
From (19) one gets
From (19) one gets
|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|,
that is the following relations hold:
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 .
From iii _(2),f(x_(2)) < 0{ }_{2}, f\left(x_{2}\right)<0 and using D(x_(n)) < 0D\left(x_{n}\right)<0, (10) one obtains
x_(n+1) < x_(n).x_{n+1}<x_{n} .
The assumptions ii_(2)-iv_(2)\mathrm{ii}_{2}-\mathrm{iv}_{2} and relations (22), and (18) imply
bar(x)-x_(n+1) < 0\bar{x}-x_{n+1}<0
that is, x_(n+1) > bar(x),f(x_(n+1)) < 0x_{n+1}>\bar{x}, f\left(x_{n+1}\right)<0. Obviously relations (21) hold.
Relations (20) and consequences jj_(1)\mathrm{jj}_{1} and jjj_(1)\mathrm{jjj}_{1} are proven analogously to Theorem 1.
Relations (20) and consequences jj_(1)\mathrm{jj}_{1} and jjj_(1)\mathrm{jjj}_{1} are proven analogously to Theorem 1.
Remark 4. If ff is increasing and concave, that is, f^(')(x) > 0f^{\prime}(x)>0 and f^(')(x) < 0f^{\prime}(x)<0, then obviously h=-fh=-f is decreasing and convex.
If we replace in Theorem 3: function ff by function hh, and if we take into account that function EE 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 ff, we give a method to determine auxiliary function gg, which could assure the control of interpolatory nodes.
If ff is a convex function, i.e. f^('')(x) > 0f^{\prime \prime}(x)>0, then for function gg we consider
{:(25)g(x)=x-(f(x))/(f^(')(x)):}\begin{equation*}
g(x)=x-\frac{f(x)}{f^{\prime}(x)} \tag{25}
\end{equation*}
If ff is a concave function, then we can set
{:(26)g(x)=x-(f(x))/(f^(')(b)):}\begin{equation*}
g(x)=x-\frac{f(x)}{f^{\prime}(b)} \tag{26}
\end{equation*}
Obviously in both cases we have g^(')(x) < 0g^{\prime}(x)<0 and thus function gg satisfies assumption b).
It is clear that function gg given by either (25) or (26), assures the equivalence of (1) and x=g(x)x=g(x), i.e., gg satisfies assumption cc ).
In order that gg also satisfies assumption aa ), it is enough that the following relations hold:
|1-(f^(')(x))/(f(a))| < 1\left|1-\frac{f^{\prime}(x)}{f(a)}\right|<1
for all x in[a,b]x \in[a, b], if ff is convex function, or
|1-(f^(')(x))/(f(b))| < 1\left|1-\frac{f^{\prime}(x)}{f(b)}\right|<1
for all x in[a,b]x \in[a, b], if ff 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.
[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.
- Received by the editors: 03.04.2006.
2000 Mathematics Subject Classification. 65H05.
Key words and phrases. Nonlinear equations in R\mathbb{R}, Steffensen methods.
This work has been supported by the Romanian Academy under grant GAR14/2005.