AITKEN-STEFFENSEN TYPE METHODS FOR NONDIFFERENTIABLE FUNCTIONS (I)^∗

Ion Pǎvǎloiu^†

(Date: November 15, 2001.)

Abstract.

We study the convergence of the Aitken-Steffensen method for solving a scalar equation $f(x)=0$ . Under reasonable conditions (without assuming the differentiability of $f$ ) we construct some auxilliary functions used in these iterations, which generate bilateral sequences approximating the solution of the considered equation.

^∗This work was 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, e-mail: pavaloiu@ictp.acad.ro.

{amssubject}

65H05.

{keyword}

Aitken-Steffensen method, bilateral approximations.

1. INTRODUCTION

In this note we shall deal with the construction of the auxiliary functions appearing in the Aitken-Steffensen-type methods for solving the equation:

(1)

f\left(x\right)=0,

where $f:\left[a,b\right]\rightarrow\mathbb{R},\;a,b\in\mathbb{R},\;a<b$ . Since we shall not assume differentiability conditions on $f$ , we shall consider instead the first and second order divided differences of $f$ , denoted by $\left[u,v;f\right]$ , resp. $\left[u,v,w;f\right]$ , $u,v,w\in\left[a,b\right]$ .

Let $g,g_{i}:\left[a,b\right]\rightarrow\mathbb{R}$ , $i=1,2$ , be three functions such that the equations

(2)		$\displaystyle x-g\left(x\right)$	$\displaystyle=$	$\displaystyle 0\text{ }\ \ {\rm and}$
(3)		$\displaystyle x-g_{i}\left(x\right)$	$\displaystyle=$	$\displaystyle 0,\;i=1,2$

are equivalent to (1).

The following three Aitken-Steffensen methods are well known:

1. The Steffensen method, which generates two sequences, $\left(x_{n}\right)_{n\geq 1}$ and $\left(g\left(x_{n}\right)\right)_{n\geq 1}$ , by

(4)

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,\dots,\;x_{1}\in\left[a,b\right],

where $g$ is given by (2).

2. The Aitken method, which generates the sequences $\left(x_{n}\right)_{n\geq 1}$ , $\left(g_{i}\left(x_{n}\right)\right)_{n\geq 1}$ $i=1,2,$ by

(5)

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=1,2,% \dots,\;x_{n}\in\left[a,b\right],

with $g_{1},g_{2}$ given by (3).

3. The Aitken-Steffensen method, which generates the sequences $\left(x_{n}\right)_{n\geq 1}$ , $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 1}$ , and $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)_{n\geq 1}$ , by

(6)

x_{n+1}=g_{1}\left(x_{n}\right)-\frac{f\left(g_{1}\left(x_{n}\right)\right)}{% \left[g_{1}\left(x_{n}\right),g_{2}\left(g_{1}\left(x_{n}\right)\right);f% \right]},\ \ \ n=1,2,\dots,\;x_{1}\in\left[a,b\right].

A certain method presents an important advantage particularly when it yields sequences approximating the solution both from the left and from the right. In such a case we obtain a rigorous control if the error at each iteration step.

We shall study the choice of the functions $g,g_{1},g_{2}$ such that the above methods to yield bilateral approximations for the solution of (1).

Regarding the monotonicity and the convexity of the function $f$ we shall use the following definitions. The function $f$ is nondecreasing (increasing) on $\left[a,b\right]$ if $\left[u,v;f\right]\geq 0$ $\left(>0\right)$ for all $u,v\in\left[a,b\right]$ . The function $f$ is nonconcave (convex) on $\left[a,b\right]$ if $\left[u,v,w;f\right]\geq 0$ $\left(>0\right)$ for all $u,v,w\in\left[a,b\right]$ .

Let $x_{0}\in\left[a,b\right]$ and $p_{x_{0}}:\left[a,b\right]\;\backslash\;\left\{x_{0}\right\}\rightarrow\mathbb% {R}$ , given by

(7)

p_{x_{0}}\left(x\right)=\left[x_{0},x;f\right].

The following result was proved in [3, p. 290].

Theorem 1.

a)

If the function $f$ is nonconcave on $\left[a,b\right]$ , the $p_{x_{0}}$ is a nondecreasing function on $\left[a,b\right]\backslash\left\{x_{0}\right\}.$
b)

If $f$ is a convex function on $\left[a,b\right]$ , then $p_{x_{0}}$ is an increasing function on $\left[a,b\right]\backslash\left\{x_{0}\right\}.$

In other words, if $f$ is nonconcave (convex) on $\left[a,b\right]$ , then for all $x^{\prime},x^{\prime\prime}\in\left[a,b\right]\backslash\left\{x_{0}\right\},% \;x^{\prime}<x^{\prime\prime}$ one obtains

(8)

\left[x_{0},x^{\prime};f\right]\leq\left(<\right)\left[x_{0},x^{\prime\prime};% f\right].

Consider now $u,v,w,t\in\left[a,b\right]$ such that $u=\min\{u,v,w,t\}$ and $t=\max\{u,v,w,t\}.$ The following lemma holds.

Lemma 2.

If $f$ is nonconcave (convex) on $\left[a,b\right]$ , then for all $v,w\in\left(u,t\right)$ , $v\neq w,$ one has

(9)

\left[u,v;f\right]\leq\left(<\right)\left[w,t;f\right].

Proof..

We shall consider only the case $"\leq"$ , since the other one is similarly obtained. There an two alternatives:

Case I. $u<v<w<t$ . Taking into account the symmetry of the divided differences with respect to the nodes and Theorem 1 we get $\left[u,v;f\right]\leq\left[u,w;f\right]=\left[w,u;f\right]\leq\left[w,t;f% \right].$

Case II. $u<w<v<t$ . As above, we obtain: $\left[u,v;f\right]\leq\left[u,t;f\right]=\left[t,u;f\right]\leq\left[t,w;f% \right]=\left[w,t;f\right].$ ∎

2. THE CONVERGENCE OF THE AITKEN-STEFFENSEN-LIKE METHOD

We shall make the following assumptions on $f :$

i.

$f\left(a\right)\cdot f\left(b\right)<0;$
ii.

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

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

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

Remark 1.

Hypothesis iii. ensures the continuity of $f$ on $\left[a,b\right]$ (see [3, p. 295]). ∎

Remark 2.

Hypothesis i.–iii. ensure the existences and the uniqueness of the solution $\bar{x}\in\left(a,b\right)$ of the equation (1). ∎

Let $\alpha$ and $\beta$ be two numbers such that $a<\alpha<\beta<b,\;f\left(\alpha\right)<0$ and $f\left(\beta\right)>0$ . Consider the functions $g_{1},$ $g_{2}$ given by

(10)		$\displaystyle g_{1}\left(x\right)=x-\frac{f\left(x\right)}{\left[\beta,b;f% \right]},\quad x\in\left[\alpha,\beta\right]\;\;{\rm and}$
(11)		$\displaystyle g_{2}\left(x\right)=x-\frac{f\left(x\right)}{\left[a,\alpha;f% \right]},\quad x\in\left[\alpha,\beta\right].$

From hypotheses ii. iii. and applying Lemma 2 it follows that for all $u,v\in\left(\alpha,\beta\right)$

(12)

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

Consider now an initial approximation $x_{1}\in\left(\alpha,\beta\right)$ satisfying

a)

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

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

The following result holds regarding the convergence of the sequence (6).

Theorem 3.

If the function $f$ obeys i.–iv., the functions $g_{1}$ and $g_{2}$ are given by (10) resp. (11) and $x_{1}$ satisfies the assumptions a) and b), then the sequences $\left(x_{n}\right)_{n\geq 1}$ , $\left(g_{1}\left(x_{n}\right)\right)_{n\geq 1}$ and $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)_{n\geq 1}$ generated by (6) satisfy:

j.

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

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

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

for all $n\in\mathbb{N},$ $n\geq 1$ , the following relations hold:

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

Proof..

By ii. and a) it follows that $x_{1}<\bar{x}$ , and from $f\left(x_{1}\right)<0$ and $\left[\beta,b;f\right]>0$ we get $g_{1}\left(x_{1}\right)>x_{1}$ . Since $x_{1}<\bar{x}$ and $g_{1}$ is increasing, one obtains $g_{1}\left(x\right)<g_{1}\left(\bar{x}\right)=\bar{x},$ i.e., $x_{1}<g_{1}\left(x_{1}\right)<\bar{x}$ . On the other hand, by b) and (6) it follows

(14)

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

Since $g_{1}\left(x_{1}\right)<\bar{x}$ we get $f\left(g_{1}\left(x_{1}\right)\right)<0$ and hence $x_{2}>g\left(x_{1}\right).$ The fact that $g_{2}$ is decreasing and $g_{1}\left(x_{1}\right)<\bar{x}$ imply that $g_{2}\left(g_{1}\left(x_{1}\right)\right)>g_{2}\left(\bar{x}\right)=\bar{x}.$ It follows that $f\left(g_{2}\left(g_{1}\left(x_{1}\right)\right)\right)>0$ , and taking into account the equality

g_{1}\left(x_{1}\right)-\textstyle\frac{f\left(g_{1}\left(x_{1}\right)\right)}% {\left[g_{1}\left(x_{1}\right),g_{2}\left(g_{1}\left(x_{1}\right)\right);f% \right]}=g_{2}\left(g_{1}\left(x_{1}\right)\right)-\textstyle\frac{f\left(g_{2% }\left(g_{1}\left(x_{1}\right)\right)\right)}{\left[g_{1}\left(x_{1}\right),g_% {2}\left(g_{1}\left(x_{1}\right)\right);f\right]}=x_{2}

it follows that $x_{2}<g_{2}\left(g_{1}\left(x_{1}\right)\right)$ and hence the following identity is true

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

whence, taking into account the following facts: $f$ is convex, $x_{2}>g_{1}\left(x_{1}\right),$ $x_{2}<g_{2}\left(g_{1}\left(x_{1}\right)\right)$ and (14), it follows that $f\left(x_{2}\right)<0$ , i.e., $x_{2}<\bar{x}.$

The inequality $x_{1}<x_{2}$ and the fact that $g_{1}$ is increasing imply that $g_{1}\left(x_{1}\right)<g_{1}\left(x_{2}\right)$ . Since $g_{2}$ is decreasing we get $g_{2}\left(g_{1}\left(x_{1}\right)\right)>g_{2}\left(g_{1}\left(x_{2}\right)\right)$ . From $x_{2}<\bar{x}$ it follows that $g_{1}\left(x_{2}\right)<\bar{x}$ and $g_{2}\left(g_{1}\left(x_{2}\right)\right)>g_{2}\left(\bar{x}\right)=\bar{x}.$

Obviously, the above reason may be applied for any $x_{n}$ , $n\geq 2$ , so that the induction principle completes the proof.∎

The sequences $\left(x_{n}\right)_{n\geq 1},\left(g_{1}\left(x_{n}\right)\right)_{n\geq 1}$ and $\left(g_{2}\left(g_{1}\left(x_{n}\right)\right)\right)_{n\geq 1}$ are monotone and bounded, and therefore they converge.

Let $x^{\ast}=\lim x_{n}$ , hence $x^{\ast}=\sup_{n\in\mathbb{N}}\left\{x_{n}\right\}$ , and let $b=\sup_{n\in\mathbb{N}}\left\{g_{1}\left(x_{n}\right)\right\}.$ We shall prove that $x^{\ast}=b.$ The relations $x^{\ast}<b$ and $x^{\ast}>b$ cannot hold, since, as implied by (13), we get

x_{n}<g_{1}\left(x_{n}\right)<x_{n+1}<g_{1}\left(x_{n+1}\right),\quad n=1,2,\dots

which lead to conclusions contradicting the definition of the exact upper bound. Therefore, the following relations are true: $x^{\ast}=\lim g_{1}\left(x_{n}\right)=g_{1}\left(x^{\ast}\right),$ whence, taking into account the equivalence of (1) and (3), it follows that $x^{\ast}=\bar{x}$ . The equality $\bar{x}=g_{2}\left(\bar{x}\right)$ implies $\lim g_{2}\left(g_{1}\left(x_{n}\right)\right)=g_{2}\left(g_{1}\left(\bar{x}% \right)\right)=g_{2}\left(\bar{x}\right)=\bar{x}.$

The three sequences have the same limit $\bar{x},$ which is the solution of (1).

By (13) we obtain

\bar{x}-x_{n+1}\leq g_{2}\left(g_{1}\left(x_{n}\right)\right)-x_{n+1},\;

and

\;\bar{x}-x_{n+1}\leq g_{2}\left(g_{1}\left(x_{n}\right)\right)-g_{1}\left(x_{% n}\right),\;n\in{\mathbb{N}}^{*},

which provide a control of the error at each iteration step.

In a forthcoming work we shall present some results regarding the convergence of the Steffensen and Aitken methods.

We end with some remarks.

Remark 3.

Since $f$ is convex, then in (10), resp. (11) we may replace the divided differences $\left[a,\alpha;f\right]$ and $\left[\beta,b;f\right]$ by $f_{r}^{\prime}\left(a\right)$ , resp. $f_{l}^{\prime}\left(b\right).$ ∎

Remark 4.

The following relations hold:

\left|\bar{x}-x_{n+1}\right|\leq\frac{l^{3}m\left[\beta,b;f\right]}{\left[a,% \alpha;f\right]^{2}}\left|\bar{x}-x_{n}\right|^{2},\quad n=1,2,\dots,

where $l=1-\frac{\left[a,\alpha;f\right]}{\left[\beta,b;f\right]}$ and $m=\sup\big\{\left[u,v,w;f\right]:u,v,w\in\left[\alpha,\beta\right]\big\}.$

{proof*}

Consider the following identities:

	$\displaystyle 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(g_{1}\left(x_{n}\right)\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(g_{1}\left(x_{n% }\right)\right);f\right]\left(\bar{x}-g_{1}\left(x_{n}\right)\right)\left(\bar% {x}-g_{2}\left(g_{1}\left(x_{n}\right)\right)\right),$

whence, by (6) and $f\left(\bar{x}\right)=0$ , we get

(15)

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

Next, $g_{1}$ and $g_{2}$ obey the following identities:

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

From the definitions of $g_{1}$ and $g_{2}$ we deduce

(18)

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

and

	$\displaystyle\left[g_{1}\left(x_{n}\right),g_{1}\left(\bar{x}\right);g_{2}\right]$	$\displaystyle=1-\textstyle\frac{\left[g_{1}\left(x_{n}\right),\bar{x};f\right]% }{\left[\alpha,a;f\right]}$
		$\displaystyle>1-\textstyle\frac{\left[\beta,b;f\right]}{\left[\alpha,a;f\right% ]}=\textstyle\frac{\left[\beta,b;f\right]}{\left[\alpha,a;f\right]}\left(\frac% {\left[\alpha,a;f\right]}{\left[\beta,b;f\right]}-1\right)=-l\textstyle\frac{% \left[\beta,b;f\right]}{\left[\alpha,a;f\right]},$

whence $-\left[g_{1}\left(x_{n}\right),g_{1}\left(\bar{x}\right);g_{2}\right]<l\frac{% \left[\beta,b;f\right]}{\left[\alpha,a;f\right]}.$

Since $g_{2}$ is nondecreasing we get

(19)

\big|\left[g_{1}\left(x_{n}\right),g_{1}\left(\bar{x}\right);g_{2}\right]\big|% <l\frac{\left[\beta,b;f\right]}{\left[\alpha,a;f\right]}.

According to Lemma 2

\left[g_{1}\left(x_{n}\right),g_{2}\left(g_{1}\left(x_{n}\right)\right);f% \right]>\left[\alpha,a;f\right],\quad n=1,2,\dots

and by (15)–(19) we finally get

\left|\bar{x}-x_{n+1}\right|\leq\frac{ml^{3}\left[\beta,b;f\right]}{\left[a,% \alpha;f\right]^{2}}\left|\bar{x}-x_{n}\right|^{2},\quad n=1,2,\dots\displayqed

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

Aitken-Steffensen-type methods for nondifferentiable functions (I)

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 NONDIFFERENTIABLE FUNCTIONS (I)^∗

Abstract.

1. INTRODUCTION

Theorem 1.

Lemma 2.

Proof..

2. THE CONVERGENCE OF THE AITKEN-STEFFENSEN-LIKE METHOD

Remark 1.

Remark 2.

Theorem 3.

Proof..

Remark 3.

Remark 4.

References

Related Posts

Aitken-Steffensen-type methods for nondifferentiable functions (I)

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 NONDIFFERENTIABLE FUNCTIONS (I)∗

Abstract.

1. INTRODUCTION

Theorem 1.

Lemma 2.

Proof..

2. THE CONVERGENCE OF THE AITKEN-STEFFENSEN-LIKE METHOD

Remark 1.

Remark 2.

Theorem 3.

Proof..

Remark 3.

Remark 4.

References

Related Posts

AITKEN-STEFFENSEN TYPE METHODS FOR NONDIFFERENTIABLE FUNCTIONS (I)^∗