Abstract
We provide sufficient conditions for the convergence of the Steffensen method for solving the scalar equation \(f(x)=0\), without assuming differentiability of \(f\) at other points than the solution \(x^\ast\). We analyze the cases when the Steffensen method generates two sequences which approximate bilaterally the solution.
Author
Ion Păvăloiu
(Tiberiu Popoviciu Institute of Numerical Analysis)
Keywords
nonlinear equations in R; Aitken-Steffensen method; monotone iterations; bilateral approximations.
PDF-LaTeX file (on the journal website).
Cite this paper as:
I. Păvăloiu, Aitken-Steffensen-type methods for nonsmooth functions (III), Rev. Anal. Numér. Théor. Approx., 32 (2003) no. 1, pp. 73-77.
About this paper
Publisher Name
Print ISSN
1222-9024
Online ISSN
2457-8126
References
[1] Balazs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numer. Theor. Approx., 21 no. 2, pp. 111–117, 1992.
[2] Casulli, V. and Trigiante, D. The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25–44, 1977.
[3] Cobzas, S., Mathematical Analysis , Presa Universitara Clujeana, Cluj-Napoca, 1997 (in Romanian).
[4] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.
[5] Pavaloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens’s method, Mathematica (Cluj),35(58), no. 1, pp. 71–76, 1993.
[6] Pavaloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal.Numer. Theor. Approx., 23, no. 1, pp. 95–100, 1994.
[7] Pavaloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, nos. 1-2, pp. 69–82, 1995.
[8] Pavaloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal. Numer. Theor. Approx., 31, no. 1, pp. 111–116, 2002.
[9] Pavaloiu, I., Aitken–Steffensen type methods for nonsmooth functions (II) , Rev. Anal. Numer. Theor. Approx., 31, no. 2, pp. 203–206, 2002.
[10] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.
Paper (preprint) in HTML form
AITKEN-STEFFENSEN TYPE METHODS FOR NONSMOOTH FUNCTIONS (III)*
Abstract
We provide sufficient conditions for the convergence of the Steffensen method for solving the scalar equation f(x)=0f(x)=0, without assuming differentiability of ff at other points than the solution x^(**)x^{*}. We analyze the cases when the Steffensen method generates two sequences which approximate bilaterally the solution.
MSC 2000. 65H05.
Keywords. Aitken-Steffensen iterations.
Keywords. Aitken-Steffensen iterations.
1. INTRODUCTION
In this paper we consider the Steffensen method for approximating the solutions of the equations of the form
{:(1)f(x)=0:}\begin{equation*}
f(x)=0 \tag{1}
\end{equation*}
with f:[a,b]rarrR,a,b inR,a < bf:[a, b] \rightarrow \mathbb{R}, a, b \in \mathbb{R}, a<b. Let g:[a,b]rarrRg:[a, b] \rightarrow \mathbb{R} be such that the equation
{:(2)x-g(x)=0:}\begin{equation*}
x-g(x)=0 \tag{2}
\end{equation*}
is equivalent to (1).
As it is well known, the Steffensen method consists in approximating the solution x^(**)x^{*} of (1) by the sequence (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} given by
As it is well known, the Steffensen method consists in approximating the solution x^(**)x^{*} of (1) by the sequence (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} given by
{:(3)x_(n+1)=x_(n)-(f(x_(n)))/([x_(n),g(x_(n));f])","quad n=1","2","dots","x_(0)in[a","b]:}\begin{equation*}
x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n}, g\left(x_{n}\right) ; f\right]}, \quad n=1,2, \ldots, x_{0} \in[a, b] \tag{3}
\end{equation*}
We are interested in the following in the conditions under which the sequences (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} and (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1} are monotone, and offer bilateral approximations to x^(**)x^{*}. The importance of such sequences resides in the fact that at each iteration step we obtain a rigorous error bound. We shall construct the function gg without assuming that ff is differentiable on the whole interval [a,b][a, b]. In this sense, we shall use the divided differences of ff.
Regarding the monotony and convexity of the function ff we shall adopt the following definitions.
Definition 1. The function ff is nondecreasing (increasing) on [a,b][a, b] if [u,v;f] >= 0( > 0)AA u,v in[a,b][u, v ; f] \geq 0(>0) \forall u, v \in[a, b], while ff is nonincreasing (decreasing) if [u,v;f] <= 0( < 0)AA u,v in[a,b][u, v ; f] \leq 0(<0) \forall u, v \in[a, b].
Definition 2. The function ff is nonconcave (convex) on [a,b][a, b] if
[u,v,w;f] >= 0( > 0),quad AA u,v,w in[a,b][u, v, w ; f] \geq 0(>0), \quad \forall u, v, w \in[a, b]
and is nonconvex (concave) if
[u,v,w;f] <= 0( < 0),quad AA u,v,w in[a,b][u, v, w ; f] \leq 0(<0), \quad \forall u, v, w \in[a, b]
Consider the function p_(x_(0)):[a,b]\\{x_(0)}rarrRp_{x_{0}}:[a, b] \backslash\left\{x_{0}\right\} \rightarrow \mathbb{R} given by
{:(4)p_(x_(0))=[x_(0),x;f]:}\begin{equation*}
p_{x_{0}}=\left[x_{0}, x ; f\right] \tag{4}
\end{equation*}
Recall the following result:
Theorem 3. [3, p. 290].
a) If ff is nonconcave on [a,b][a, b] then p_(x_(0))p_{x_{0}} is nondecreasing on [a,b][a, b];
b) If ff is convex on [a,b][a, b] then p_(x_(0))p_{x_{0}} is increasing on [a,b][a, b];
c) If ff is nonconvex on [a,b][a, b] then p_(x_(0))p_{x_{0}} is nonincreasing on [a,b][a, b];
d) If ff is concave on [a,b][a, b] then p_(x_(0))p_{x_{0}} is decreasing on [a,b][a, b].
Theorem 3. [3, p. 290].
a) If ff is nonconcave on [a,b][a, b] then p_(x_(0))p_{x_{0}} is nondecreasing on [a,b][a, b];
b) If ff is convex on [a,b][a, b] then p_(x_(0))p_{x_{0}} is increasing on [a,b][a, b];
c) If ff is nonconvex on [a,b][a, b] then p_(x_(0))p_{x_{0}} is nonincreasing on [a,b][a, b];
d) If ff is concave on [a,b][a, b] then p_(x_(0))p_{x_{0}} is decreasing on [a,b][a, b].
Consider now u,v,w,t in[a,b]u, v, w, t \in[a, b] such that u <= min{v,w,t}u \leq \min \{v, w, t\} and t >= max{u,v,w}t \geq \max \{u, v, w\}. The following result is known:
Lemma 4. [8]. If ff is nonconcave (convex) on [a,b][a, b] then the following relation holds:
{:(5)[u","v;f] <= ( < )[w","t;f]","quad AA v","w in[u","t]","v!=w:}\begin{equation*}
[u, v ; f] \leq(<)[w, t ; f], \quad \forall v, w \in[u, t], v \neq w \tag{5}
\end{equation*}
An inequality analogous to (5) holds when ff is nonconvex (concave) on [a,b][a, b].
2. THE CONVERGENCE OF THE STEFFENSEN METHOD
We shall consider that ff obeys the following hypotheses:
i. ff is continuous at aa and bb;
ii. f(a)*f(b) < 0f(a) \cdot f(b)<0;
iii. ff is increasing on [a,b][a, b];
iv. ff is convex on [a,b][a, b] and ff is continuous at aa and bb;
v. ff is differentiable at x^(**)x^{*}, the solution of (1), and x^(**)in(a,b)x^{*} \in(a, b).
i. ff is continuous at aa and bb;
ii. f(a)*f(b) < 0f(a) \cdot f(b)<0;
iii. ff is increasing on [a,b][a, b];
iv. ff is convex on [a,b][a, b] and ff is continuous at aa and bb;
v. ff is differentiable at x^(**)x^{*}, the solution of (1), and x^(**)in(a,b)x^{*} \in(a, b).
Remark 1. Hypotheses iv. ensures the continuity of ff on (a,b)(a, b) (see, e.g. [3, p. 295]).
Remark 2. Hypotheses i.-iv. ensure the existence and the unicity of the solution x^(**)in(a,b)x^{*} \in(a, b) of equation (1).
Let alpha,beta in(a,b)\alpha, \beta \in(a, b) be such that f(alpha) < 0f(\alpha)<0 and f(beta) > 0f(\beta)>0 (their existence is ensured by hypotheses i.-iv.).
Consider the function g:[alpha,beta]rarrRg:[\alpha, \beta] \rightarrow \mathbb{R} given by
{:(6)g(x)=x-(f(x))/([a,alpha;f]):}\begin{equation*}
g(x)=x-\frac{f(x)}{[a, \alpha ; f]} \tag{6}
\end{equation*}
By iii. and iv. and Lemma 4 it follows that
{:(7)[u","v;g] < 0","quad AA u","v in(alpha","beta):}\begin{equation*}
[u, v ; g]<0, \quad \forall u, v \in(\alpha, \beta) \tag{7}
\end{equation*}
i.e., gg is decreasing.
We shall make the following hypotheses regarding the initial approximation x_(1)x_{1} in (3):
а) f(x_(1)) < 0f\left(x_{1}\right)<0;
b) g(x_(1)) < betag\left(x_{1}\right)<\beta.
We shall make the following hypotheses regarding the initial approximation x_(1)x_{1} in (3):
а) f(x_(1)) < 0f\left(x_{1}\right)<0;
b) g(x_(1)) < betag\left(x_{1}\right)<\beta.
Regarding the convergence of the Steffensen method (3) we prove the following result:
Theorem 5. Assume that ff obeys assumptions i.-v., that the function gg is given by (6) and x_(1)x_{1} obeys a) and b). Then the sequence (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} and (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1} generated by (3) satisfy the following properties:
j. the sequence (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} is increasing and bounded;
jj. the sequence (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1} is decreasing and bounded;
jjj. the following is true:
j. the sequence (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} is increasing and bounded;
jj. the sequence (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1} is decreasing and bounded;
jjj. the following is true:
{:(8)x_(n) < x^(**) < g(x_(n))","AA n inN:}\begin{equation*}
x_{n}<x^{*}<g\left(x_{n}\right), \forall n \in \mathbb{N} \tag{8}
\end{equation*}
Proof. By (6) we get that x^(**)=g(x^(**))x^{*}=g\left(x^{*}\right). Since x_(1) < x^(**)x_{1}<x^{*}, and gg is decreasing, it follows g(x_(1)) > g(x^(**))=x^(**)g\left(x_{1}\right)>g\left(x^{*}\right)=x^{*} and so x_(1) < x^(**) < g(x_(1))x_{1}<x^{*}<g\left(x_{1}\right).
We show now that x_(2)x_{2} given by (3) verifies x_(1) < x_(2) < x^(**)x_{1}<x_{2}<x^{*}. Since f(x_(1)) < 0f\left(x_{1}\right)<0 and ff is increasing, it follows x_(2)=x_(1)-(f(x_(1)))/([x_(1),g(x_(1));f]) > x_(1)x_{2}=x_{1}-\frac{f\left(x_{1}\right)}{\left[x_{1}, g\left(x_{1}\right) ; f\right]}>x_{1}. Further, it can be easily seen that the following identity holds:
x_(1)-(f(x_(1)))/([x_(1),g(x_(1));f])=g(x_(1))-(f(g(x_(1))))/([x_(1),g(x_(1));f]),x_{1}-\frac{f\left(x_{1}\right)}{\left[x_{1}, g\left(x_{1}\right) ; f\right]}=g\left(x_{1}\right)-\frac{f\left(g\left(x_{1}\right)\right)}{\left[x_{1}, g\left(x_{1}\right) ; f\right]},
whence, by (3) for n=1n=1 it follows x_(2) < g(x_(1))x_{2}<g\left(x_{1}\right), since f(g(x_(1))) > 0f\left(g\left(x_{1}\right)\right)>0 and [x_(1),g(x_(1));f] > 0\left[x_{1}, g\left(x_{1}\right) ; f\right]>0.
From the identity
{:[f(x_(2))=],[quad=f(x_(1))+[x_(1),g(x_(1));f](x_(2)-x_(1))+[x_(2),x_(1),g(x_(1));f](x_(2)-x_(1))(x_(2)-g(x_(1)))]:}\begin{aligned}
& f\left(x_{2}\right)= \\
& \quad=f\left(x_{1}\right)+\left[x_{1}, g\left(x_{1}\right) ; f\right]\left(x_{2}-x_{1}\right)+\left[x_{2}, x_{1}, g\left(x_{1}\right) ; f\right]\left(x_{2}-x_{1}\right)\left(x_{2}-g\left(x_{1}\right)\right)
\end{aligned}
taking into account (3) for n=1n=1 and the fact that ff is convex, we get f(x_(2)) <f\left(x_{2}\right)< 0 and so x_(2) < x^(**)x_{2}<x^{*}.
By x_(2) > x_(1)x_{2}>x_{1} it results g(x_(2)) < g(x_(1))g\left(x_{2}\right)<g\left(x_{1}\right). We prove that g(x_(2)) > x^(**)g\left(x_{2}\right)>x^{*}. Since x_(2) < x^(**)x_{2}<x^{*}, from the monotony of gg it follows g(x_(2)) > g(x^(**))=x^(**)g\left(x_{2}\right)>g\left(x^{*}\right)=x^{*}. In conclusion, we get
{:(9)x_(1) < x_(2) < x^(**) < g(x_(2)) < g(x_(1)):}\begin{equation*}
x_{1}<x_{2}<x^{*}<g\left(x_{2}\right)<g\left(x_{1}\right) \tag{9}
\end{equation*}
Assume now that for some n >= 2n \geq 2, the elements obtained by (3) verify:
{:(10)x_(1) < x_(2) < cdots < x_(n) < cdots < x^(**) < cdots < g(x_(n)) < cdots < g(x_(2)) < g(x_(1)).:}\begin{equation*}
x_{1}<x_{2}<\cdots<x_{n}<\cdots<x^{*}<\cdots<g\left(x_{n}\right)<\cdots<g\left(x_{2}\right)<g\left(x_{1}\right) . \tag{10}
\end{equation*}
Repeating the above reason for x_(1)=x_(n)x_{1}=x_{n} we get
{:(11)x_(n) < x_(n+1) < x^(**) < g(x_(n+1)) < g(x_(n)):}\begin{equation*}
x_{n}<x_{n+1}<x^{*}<g\left(x_{n+1}\right)<g\left(x_{n}\right) \tag{11}
\end{equation*}
From (10) and (11) one obtains the monotony of the sequences (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} and (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1}. Obviously, these sequence are bounded, so there exists bar(x)=lim_(n rarr oo)x_(n)\bar{x}= \lim _{n \rightarrow \infty} x_{n}, and lim_(n rarr oo)g(x_(n))=g( bar(x))\lim _{n \rightarrow \infty} g\left(x_{n}\right)=g(\bar{x}), since gg is continuous.
Passing to limit in (3) implies bar(x)= bar(x)-(f(( bar(x))))/([( bar(x)),g(( bar(x)));f])\bar{x}=\bar{x}-\frac{f(\bar{x})}{[\bar{x}, g(\bar{x}) ; f]} i.e. f( bar(x))=0f(\bar{x})=0, and so bar(x)=x^(**)\bar{x}=x^{*}.
Relations (11) imply the following a posteriori errors
{:(12)x^(**)-x_(n) <= g(x_(n))-x_(n)","quad n=1","2","dots:}\begin{equation*}
x^{*}-x_{n} \leq g\left(x_{n}\right)-x_{n}, \quad n=1,2, \ldots \tag{12}
\end{equation*}
Remark 3. Consider in (3) the function g:[alpha,beta]rarrRg:[\alpha, \beta] \rightarrow \mathbb{R},
{:(13)g(x)=x-(f(x))/([beta,b;f]):}\begin{equation*}
g(x)=x-\frac{f(x)}{[\beta, b ; f]} \tag{13}
\end{equation*}
If ff is concave on [alpha,beta][\alpha, \beta], then [u,v;f] > [beta,b;f],AA u,v in[alpha,beta][u, v ; f]>[\beta, b ; f], \forall u, v \in[\alpha, \beta] and so gg is decreasing on [alpha,beta][\alpha, \beta]. Suppose now that hypotheses iv. and a) resp. b) imposed on ff and gg are replaced by
iv ^(')^{\prime}. the function ff is concave on [a,b][a, b];
the initial value x_(1)x_{1} in (3) is such that
{:a^(')).f(x_(1)) > 0\left.\mathrm{a}^{\prime}\right) . f\left(x_{1}\right)>0;
b^(')\mathrm{b}^{\prime} ). g(x_(1)) > alphag\left(x_{1}\right)>\alpha, with gg given by (13).
Then the sequences (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} and (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1} have the following properties: j^(').(x_(n))_(n >= 1)\mathrm{j}^{\prime} .\left(x_{n}\right)_{n \geq 1} is decreasing;
jj^(').(g(x_(n)))_(n >= 1)\mathrm{jj}^{\prime} .\left(g\left(x_{n}\right)\right)_{n \geq 1} is increasing;
jjj^(').g(x_(n)) < x^(**) < x_(n),quad n=1,2,dots\mathrm{jjj}^{\prime} . g\left(x_{n}\right)<x^{*}<x_{n}, \quad n=1,2, \ldots
The proof of these properties is similar to that given for Theorem 5.
iv ^(')^{\prime}. the function ff is concave on [a,b][a, b];
the initial value x_(1)x_{1} in (3) is such that
{:a^(')).f(x_(1)) > 0\left.\mathrm{a}^{\prime}\right) . f\left(x_{1}\right)>0;
b^(')\mathrm{b}^{\prime} ). g(x_(1)) > alphag\left(x_{1}\right)>\alpha, with gg given by (13).
Then the sequences (x_(n))_(n >= 1)\left(x_{n}\right)_{n \geq 1} and (g(x_(n)))_(n >= 1)\left(g\left(x_{n}\right)\right)_{n \geq 1} have the following properties: j^(').(x_(n))_(n >= 1)\mathrm{j}^{\prime} .\left(x_{n}\right)_{n \geq 1} is decreasing;
jj^(').(g(x_(n)))_(n >= 1)\mathrm{jj}^{\prime} .\left(g\left(x_{n}\right)\right)_{n \geq 1} is increasing;
jjj^(').g(x_(n)) < x^(**) < x_(n),quad n=1,2,dots\mathrm{jjj}^{\prime} . g\left(x_{n}\right)<x^{*}<x_{n}, \quad n=1,2, \ldots
The proof of these properties is similar to that given for Theorem 5.
REFERENCES
[1] Balázs, M., A bilateral approximating method for finding the real roots of real equations, Rev. Anal. Numér. Théor. Approx., 21 no. 2, pp. 111-117, 1992.
[2] Casulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25-44, 1977.
[3] Cobzaş, S., Mathematical Analysis, Presa Universitară Clujeană, Cluj-Napoca, 1997 (in Romanian).
[4] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.
[5] Păvăloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens's method, Mathematica (Cluj), 35 (58), no. 1, pp. 71-76, 1993.
[6] Păvăloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 23, no. 1, pp. 95-100, 1994.
[7] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, nos. 1-2, pp. 69-82, 1995.
[8] Păvăloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal. Numér. Théor. Approx., 31, no. 1, pp. 111-116, 2002.
[9] Păvăloiu, I., Aitken-Steffensen type methods for nonsmooth functions (II), Rev. Anal. Numér. Théor. Approx., 31, no. 2, pp. 203-206, 2002.
[10] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.
[2] Casulli, V. and Trigiante, D., The convergence order for iterative multipoint procedures, Calcolo, 13, no. 1, pp. 25-44, 1977.
[3] Cobzaş, S., Mathematical Analysis, Presa Universitară Clujeană, Cluj-Napoca, 1997 (in Romanian).
[4] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, 1960.
[5] Păvăloiu, I., On the monotonicity of the sequences of approximations obtained by Steffensens's method, Mathematica (Cluj), 35 (58), no. 1, pp. 71-76, 1993.
[6] Păvăloiu, I., Bilateral approximations for the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 23, no. 1, pp. 95-100, 1994.
[7] Păvăloiu, I., Approximation of the roots of equations by Aitken-Steffensen-type monotonic sequences, Calcolo, 32, nos. 1-2, pp. 69-82, 1995.
[8] Păvăloiu, I., Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal. Numér. Théor. Approx., 31, no. 1, pp. 111-116, 2002.
[9] Păvăloiu, I., Aitken-Steffensen type methods for nonsmooth functions (II), Rev. Anal. Numér. Théor. Approx., 31, no. 2, pp. 203-206, 2002.
[10] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.
Received by the editors: March 12, 2003.
- *This work has been supported by the Romanian Academy under grant GAR 19/2003.
^(†){ }^{\dagger} "T. Popoviciu" Institute of Numerical Analysis, P.O. Box 68-1, 3400 Cluj-Napoca, Romania, e-mail: pavaloiu@ictp.acad.ro.