Aitken-Steffensen-type methods
for nonsmooth functions (II)^∗

Ion Păvăloiu^†

(Date: January 16, 2002.)

Abstract.

We present some new conditions which assure that the Aitken-Steffensen method yields bilateral approximation for the solution of a nonlinear scalar equation. The auxiliary functions appearing in the method are constructed under the hypothesis that the nonlinear application is not differentiable on an interval containing the solution.

^∗This work has been supported by the Romanian Academy under grant GAR 45/2002.

^†“T. Popoviciu” Institute of Numerical Analysis, P.O. Box 68–1, 3400 Cluj-Napoca, Romania (pavaloiu@ictp.acad.ro).

{amssubject}

65H05.

{keyword}

Aitken-Steffensen iterations.

1. Introduction

In this note we continue the study of the convergence of the Aitken-Steffensen-type iterations

(1)

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,\quad x_{0}\in I

for solving

(2)

f\left(x\right)=0,

where $f:\left[a,b\right]\rightarrow\mathbb{R},\;a,b\in\mathbb{R},\;a<b.$

The functions $g_{1}$ and $g_{2}$ in (2) are chosen such that equations

(3)

\displaystyle x-g_{i}\left(x\right)

\displaystyle=0,\quad i=1,2,

to be equivalent to equation (1).

Under supplementary assumptions we shall show, as in [7], that (2) generates three monotone sequences, converging to the solution $\bar{x}$ of (1).

Regarding the monotonicity and convexity of $f$ we shall consider the notions introduced in [3]. We shall also use Theorem 1 and Lemma 2 from [8].

For defining the functions $g_{1}$ and $g_{2}$ , we shall consider $\alpha,\beta\in\mathbb{R}$ such that $a<\alpha<\beta<b$ and $f\left(\alpha\right)<0,\;f\left(\beta\right)>0,$ defining then:

(4)

\displaystyle g_{1}\left(x\right)

\displaystyle=x-\tfrac{f\left(x\right)}{\left[\beta,b;f\right]},\quad x\in% \left[\alpha,\beta\right],

(5)

\displaystyle g_{2}\left(x\right)

\displaystyle=x-\tfrac{f\left(x\right)}{\left[a,\alpha;f\right]},\quad x\in% \left[\alpha,\beta\right].

Regarding $f$ we shall make the following assumptions.

i.

$f\left(\alpha\right)\cdot f\left(\beta\right)<0;$
ii.

$f$ is increasing on $\left[a,b\right];$
iii.

$f$ is convex on $\left[a,b\right]$ and continuous at $a$ and $b$ ;
iv.

if $\bar{x}\in\left(a,b\right)$ is the solution of (1), then $f$ is differentiable at $\bar{x}$ .

Remarks.

1^∘ Hypothesiis iii. ensures the continuity of $f$ on $\left[a,b\right]$ , and therefore the existence of $\bar{x}$ . Hypothesis ii. ensures the uniqueness of $\bar{x}$ .

2^∘ From hypotheses ii, iii and [8, Lm. 1.1], it follows that for any $u,v\in\left(\alpha,\beta\right)$ one obtains

(6)

\left[u,v;g_{1}\right]>0\quad\text{and\quad}\left[u,v;g_{2}\right]<0,

i.e., $g_{1}$ is increasing and $g_{2}$ is decreasing on $\left(\alpha,\beta\right)$ . ∎

Let $x_{0}\in\left(\alpha,\beta\right)$ be such that

a)

$f\left(x_{0}\right)<0$
b)

$g_{2}\left(x_{0}\right)<\beta.$

2. The convergence of the Aitken-Steffensen-type iterations

We shall study in the following the convergence of the sequences $\left(x_{n}\right)_{n\geq 0}$ $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ to the solution $\bar{x}$ . We obtain the following result.

Theorem 1.

If the function $f$ verifies assumptions i–iv., the functions $g_{1}$ and $g_{2}$ are given by (4) and (5), and $x_{0}\in\left(\alpha,\beta\right)$ verifies a) and b), then the sequences $\left(x_{n}\right)_{n\geq 0},\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ and $\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ , generated by (2) satisfy:

j.

$\left(x_{n}\right)_{n\geq 0}$ is increasing;
jj.

$\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ is increasing;
jjj.

$\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ is decreasing;
jv.

for all $n\in\mathbb{N},\;$ one has

(7) $x_{n}<g_{1}\left(x_{n}\right)<x_{n+1}<\bar{x}<g_{2}\left(x_{n}\right).$

Proof.

By $\left[\beta,b;f\right]>0$ and $f\left(x_{0}\right)<0$ it follows $g_{1}\left(x_{0}\right)>x_{0}$ , while by $x_{0}<\bar{x}$ and the fact that $g_{1}$ is increasing it follows $g_{1}\left(x_{0}\right)<g_{1}\left(\bar{x}\right)=\bar{x}$ , i.e. $g_{1}\left(x_{0}\right)<\bar{x}$ .

Now, since $x_{0}<\bar{x}$ , $g_{2}$ is decreasing one gets $g_{2}\left(x_{0}\right)>g_{2}\left(\bar{x}\right)=\bar{x}$ , i.e. the following relations hold:

(8)

x_{0}<g_{1}\left(x_{0}\right)<\bar{x}<g_{2}\left(x_{0}\right).

Let $x_{1}=g_{1}\left(x_{0}\right)-\frac{f\left(g_{1}\left(x_{0}\right)\right)}{% \left[g_{1}\left(x_{0}\right),g_{2}\left(x_{0}\right);f\right]},$ since $f\left(g_{1}\left(x_{0}\right)\right)<0$ implies $g_{1}\left(x_{0}\right)<x_{1}$ .

From the identity

	$\displaystyle f\left(x_{1}\right)=$	$\displaystyle f\left(g_{1}\left(x_{0}\right)\right)+\left[g_{1}\left(x_{0}% \right),g_{2}\left(x_{0}\right);f\right]\left(x_{1}-g_{1}\left(x_{0}\right)% \right)+$
		$\displaystyle+\left[x_{1},g_{1}\left(x_{0}\right),g_{2}\left(x_{0}\right);f% \right]\left(x_{1}-g_{1}\left(x_{0}\right)\right)\left(x_{1}-g_{2}\left(x_{0}% \right)\right)$

taking into account the convexity of $f$ and relation (1), we get $f\left(x_{1}\right)<0$ , i.e. $x_{1}<\bar{x}.$

By the above relations and by (8) it follows

x_{0}<g_{1}\left(x_{0}\right)<x_{1}<\bar{x}<g_{2}\left(x_{0}\right),

which shows that (7) is verified for $n=0.$

Repeating this reason, the induction shows that (7) holds for $n\in\mathbb{N}$ . This attracts in turn that the sequences $\left(x_{n}\right)_{n\geq 0}$ and $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ are increasing, i.e., statements j and jj.

We show next that $\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ is decreasing. Indeed, by $x_{n}<x_{n+1}$ for $n\in\mathbb{N}$ we get $g_{2}\left(x_{n}\right)>g_{2}\left(x_{n+1}\right)$ since $g_{2}$ is decreasing. Inequalities $x_{n}<\bar{x}$ , $n\in\mathbb{N}$ , show that $g_{2}\left(x_{n}\right)>g_{2}\left(\bar{x}\right)=\bar{x}$ .

Let us notice that the sequences $\left(x_{n}\right)_{n\geq 0}$ , $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 0}$ , $\left(g_{2}\left(x_{n}\right)\right)_{n\geq 0}$ are monotone and bounded, so they converge. Let $l_{1}=\lim x_{n}$ , $l_{2}=\lim g_{1}\left(x_{n}\right)$ and $l_{3}=\lim g_{2}\left(x_{n}\right)$ . We show that $l_{1}=l_{2}=l_{3}=\bar{x}.$

We prove first that $l_{1}=l_{2}$ . Assume the contrary, $l_{1}\neq l_{2}$ , e.g. $l_{1}<l_{2}$ . Obviously, $l_{1}=\sup_{n\in\mathbb{N}}\left\{x_{n}\right\}$ and $l_{2}=\sup_{n\in\mathbb{N}}\left\{g_{1}\left(x_{n}\right)\right\}.$ Let $0<\varepsilon<l_{2}-l_{1}$ be a positive number. Then there exists $n_{\varepsilon}\in\mathbb{N}$ such that $g_{1}\left(x_{n}\right)>l_{2}-\varepsilon$ for $n>n_{\varepsilon}$ .

This implies that

x_{n+1}>g_{1}\left(x_{n}\right)>l_{2}-\varepsilon>l_{1}

so $l_{1}$ is not the exact upper bound of the elements of the sequence $\left(x_{n}\right)_{n\geq 0}$ . Hence, clearly, $l_{1}=l_{2}=l$ ,

l=\lim x_{n}=\lim g_{1}\left(x_{n}\right)=g_{1}\left(l\right),

i.e., $l=\bar{x}$ . Since $\lim x_{n}=\bar{x}$ , it follows that

\lim g_{2}\left(x_{n}\right)=g_{2}\left(\bar{x}\right)=\bar{x},

since $\bar{x}$ is the unique solution of equation $x-g_{2}\left(x\right)=0.$ ∎

The above relations show that we have a control of the error at each iteration step, justified by

\bar{x}-x_{n+1}<g_{2}\left(x_{n}\right)-x_{n+1},\quad\ {\rm or}\ \ \bar{x}-x_{% n+1}<g_{2}\left(x_{n}\right)-g_{1}\left(x_{n}\right),\quad n=0,1,\ldots

The identity

	$\displaystyle 0=f\left(\bar{x}\right)=$	$\displaystyle f\left(g_{1}\left(x_{n}\right)\right)+\left[g_{1}\left(x_{n}% \right),g_{2}\left(x_{n}\right);f\right]\left(\bar{x}-g_{1}\left(x_{n}\right)% \right)+$
		$\displaystyle+\left[\bar{x},g_{1}\left(x_{n}\right),g_{2}\left(x_{n}\right);f% \right]\left(\bar{x}-g_{1}\left(x_{n}\right)\right)\left(\bar{x}-g_{2}\left(x_% {n}\right)\right)$

relation (7), and the hypotheses of the above theorem lead to

(9)

\bar{x}-x_{n+1}=-\frac{\left[\bar{x},g_{1}\left(x_{n}\right),g_{2}\left(x_{n}% \right);f\right]}{\left[g_{1}\left(x_{n}\right),g_{2}\left(x_{n}\right);f% \right]}\left(\bar{x}-g_{1}\left(x_{n}\right)\right)\left(\bar{x}-g_{2}\left(x% _{n}\right)\right).

Further, by Lemma 2 from [8] we get

(10)

\displaystyle\bar{x}-g_{1}\left(x_{n}\right)=\left[x_{n},\bar{x};g_{1}\right]% \left(\bar{x}-x_{n}\right)

(11)

\displaystyle\bar{x}-g_{2}\left(x_{n}\right)=\left[x_{n},\bar{x},g_{2}\right]% \left(\bar{x}-x_{n}\right)

and, taking into account (4) and (5),

\left[x_{n},\bar{x};g_{1}\right]=1-\tfrac{\left[x_{n},\bar{x};f\right]}{\left[% \beta,b;f\right]}<1-\tfrac{\left[a,\alpha;f\right]}{\left[\beta,b;f\right]}=1-% q<1.

Analogously,

\left[\bar{x},x_{n};g_{2}\right]=1-\tfrac{\left[\bar{x},x_{n};f\right]}{\left[% a,\alpha;f\right]}>1-\tfrac{\left[\beta,b;f\right]}{\left[a,\alpha,;\right]}=% \tfrac{\left[\beta,b;f\right]}{\left[a,\beta;f\right]}\Big(\tfrac{\left[a,% \alpha;f\right]}{[\beta,b;f]}-1\Big)=\tfrac{1}{q}(q-1)

where we have denoted $\left[a,\alpha;f\right]/\left[\beta,b;f\right]=q>0$ and by Lemma 2 from [8] $q<1.$ This relation, together with the decreasing of $g_{2}$ lead to $-\left[\bar{x},x_{n};g_{2}\right]<\tfrac{1}{q}\left(1-q\right),$ i.e., $\big|[\bar{x},x_{n};g_{2}]\big|<\tfrac{1}{q}\left(1-q\right).$

Denoting $M=\max_{u,v\in\left[\alpha.\beta\right]}\big|\left[\bar{x},u,v;f\right]\big|$ and $m=\left[a,\alpha;f\right]$ , by (9) we get

\left|\bar{x}-x_{n+1}\right|<\tfrac{M\left(1-q\right)^{2}}{mq}\left|\bar{x}-x_% {n}\right|^{2},\;n=1,2,\ldots

which characterizes the convergence order of the studied methods.

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, no. 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] Traub, F. J., Iterative Methods for the Solution of Equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964.

Aitken-Steffensen-type methods for nonsmooth functions (II)

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Aitken-Steffensen-type methods
for nonsmooth functions (II)^∗

Abstract.

1. Introduction

Remarks.

2. The convergence of the Aitken-Steffensen-type iterations

Theorem 1.

Proof.

References

Related Posts

Aitken-Steffensen-type methods for nonsmooth functions (II)

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

Aitken-Steffensen-type methods for nonsmooth functions (II)∗

Abstract.

1. Introduction

Remarks.

2. The convergence of the Aitken-Steffensen-type iterations

Theorem 1.

Proof.

References

Related Posts

Aitken-Steffensen-type methods
for nonsmooth functions (II)^∗