Analytic and empirical study of the rate of convergence of some iterative methods

Vasile Berinde$^{1,2}$, Abdul Rahim Khan$^{2}$ Mădălina Păcurar$^{3}$

April 15, 2015.

$^{1}$Department of Mathematics and Computer Science North University of Baia Mare Victorie1 76, 430072 Baia Mare, Romania, e-mail: vberinde@ubm.ro.

$^{2}$Department of Mathematics and Statistics King Fahd University of Petroleum and Minerals Dhahran, Saudi Arabia, e-mail: arahim@kfupm.edu.sa.

$^{3}$Department of Statistics, Analysis, Forecast and Mathematics Faculty of Economics and Bussiness Administration Babeş-Bolyai University of Cluj-Napoca 56-60 T. Mihali St., 400591 Cluj-Napoca, Romania, e-mail: madalina.pacurar@econ.ubbcluj.ro.

Dedicated to prof. I. Păvăloiu on the occasion of his 75th anniversary

We study analytically and empirically the rate of convergence of two $k$-step fixed point iterative methods in the family of methods

\begin{equation} \label{eq-1} x_{n+1}=T(x_{i_0+n-k+1},x_{i_1+n-k+1},\dots , x_{{i_{k-1}+n-k+1}}),\, n\geq k-1, \end{equation}

where $T: X^k \to X$ is a mapping satisfying some Presic type contraction conditions and $(i_0,i_1,\dots ,i_{k-1})$ is a permutation of $(0,1,\dots ,k-1)$.

We also consider the Picard iteration associated with the fixed-point problem $x=T(x,\dots ,x)$ and compare analytically and empirically the rate and speed of convergence of three iterative methods. Our approach opens a new perspective on the study of the rate of convergence/speed of convergence of fixed-point iterative methods and also illustrates the essential difference between them by means of some concrete numerical experiments.

MSC. 47H09, 47H10, 54H25. Keywords. metric space, contractive mapping, fixed point, $k$-step fixed point iterative method, rate of convergence.

1 Introduction

In the book [ 23 ] (see also [ 28 ] ), I. Păvăloiu studied some multistep iterative methods for solving the scalar equation

\begin{equation} \label{eq-1} x=\varphi (x) \end{equation}

where $\varphi \colon I\rightarrow I$ is a function and $I\subset \mathbb {R}$ is an interval. In order to solve 2, he considers a function $g\colon I^s\rightarrow I$, where $s\geq 1$ is an integer, and the restriction of $g$ to the diagonal of $I^s$ coincides with $\varphi $, that is,

\begin{equation} \label{eq-2} g(x,x,\dots ,x)=\varphi (x), \qquad \forall x\in I. \end{equation}

Then, by choosing $x_0,x_1,\dots ,x_{s-1}\in I$, one constructs the $s$-point iterative sequence $\{ x_n\} $ defined by

\begin{equation} \label{eq-3} x_{s+p}=g(x_p,x_{p+1},\dots ,x_{p+s-1}),\qquad p=0,1,\dots \end{equation}

The convergence of the iterative method 4 is established in Theorem 4.2.1 in [ 23 ] (Theorem 5.3.1 in [ 28 ] ), which essentially states that, if $\varphi $ and $g$ are defined as above and there exist constants $\alpha _i\in (0,1),\, i=1,2,\dots ,s$ satisfying

\begin{equation} \label{eq-4} \alpha _1+\alpha _2+\dots +\alpha _s<1 \end{equation}

such that

\begin{equation} \label{eq-5} |g(u_0,\dots ,u_{s-1})-g(u_1,\dots ,u_{s})|\leq \alpha _1 |u_0-u_1|+\dots +\alpha _{s} |u_{s-1}-u_s|,\end{equation}

for all $u_0,u_1,\dots ,u_{k\! -\! 1}\! \in \! I$, then the sequence $\{ x_n\} $ given by 4 converges to $\overline{x}\in I$, the unique solution of equation 2, for any initial values $x_0,x_1,\dots ,x_{s\! -\! 1}\in I$.

Subsequently, by considering the family of $s!$ iterative methods

\begin{equation} \label{eq-5a} x_{n+1}=g(x_{i_0+n-s+1},x_{i_1+n-s+1},\dots , x_{{i_{s-1}+n-s+1}}),\qquad n\geq s-1, \end{equation}

where $(i_0,i_1,\dots ,i_{s-1})$ is a permutation of $(0,1,\dots ,s-1)$, the authors in [ 23 ] and [ 28 ] search for a certain iterative method in that family for which the best error estimate is obtained (by means of Theorem 4.2.1 [ 23 ] ).

The conclusion (see Theorem 5.3.3 in [ 28 ] ) is that the optimal method in this respect corresponds to the particular method obtained from 7 in case of the permutation $(i_0,i_1,\dots ,i_{s-1})$ of $(0,1,\dots ,s-1)$ for which one has

\[ \alpha _{i_0}\geq \alpha _{i_1}\geq \dots \geq \alpha _{i_{s-1}}. \]

Starting from the fact that, in [ 23 ] and [ 28 ] , no direct proof is given of the fact that the methods in 7 are also convergent, our aim in this paper is quadruple:

First, to give a different proof of Theorem 4.2.1 in [ 23 ] (Theorem 5.3.1 in [ 28 ] ) in the more general case of mappings defined on a complete metric space $X$;
Second, to consider the one-point iterative method

\begin{equation} \label{eq-5b} y_{n+1}=g(y_{n},y_{n},\ldots ,y_{n}),\qquad n\geq 0, \end{equation}
8

and prove that it converges to $\overline{x}$, for any initial value $y_0$;
Third, to show analytically that all the three iterative methods mentioned above have linear rate of convergence;
Fourth, to define a suitable concept of speed of convergence and to show empirically that the rate of convergence and the speed of convergence are distinct concepts and, additionally, to present some examples that show that two methods having the same rate of convergence may exhibit a different speed of convergence.

2 Preliminaries

We first note that Theorem 4.2.1 in [ 23 ] (Theorem 5.3.1 in [ 28 ] ) is a particular case of Prešić fixed point theorem, established in the general setting of a metric space [ 29 ] .

Indeed, let $(X,d)$ be a metric space and $T\colon X\rightarrow X$ a self mapping. Denote by $Fix\, (T):=\{ x\in X:\, Tx=x\} $ the set of fixed points of $T$.

If $(X,d)$ is complete and $T$ is a contraction, i.e., there exists a constant $\alpha \in [0,1)$ such that

\begin{equation} \label{2.1} d(Tx, Ty)\leq a\, d(x,y),\qquad \text{ for all}\; x,y\in X, \end{equation}

then, by the well known Banach contraction mapping principle (see [ 4 ] , for example), we know that $Fix\, (T)=\{ p\} $ and that, for any $x_0\in X$, the Picard iteration, that is, the sequence defined by $x_{n+1}=Tx_{n},\, n=0,1,\dots $, converges to $p$, as $n\rightarrow \infty $.

The Banach contraction mapping principle has been extended by Prešić [ 29 ] (see also [ 41 ] ), to mappings $f\colon X^k\rightarrow X$ satisfying a contractive condition that includes 9 in the particular case $k=1$.

Theorem 2.1 S. Prešić [ 29 ] , 1965

Let $(X,d)$ be a complete metric space, $k$ a positive integer, $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}\in \mathbb {R}_{+}, $ $\overset {k}{\underset {i=1}{\sum }}\alpha _{i}=\alpha {\lt}1$ and $f\colon X^k\rightarrow X$ a mapping satisfying

\begin{equation} \label{Cond_Presic} d\left(f(x_0,\dots ,x_{k-1}), f(x_1,\dots ,x_{k})\right)\leq \alpha _1 d(x_0,x_1)+\dots +\alpha _{k} d(x_{k-1},x_k),\end{equation}

for all $x_0,\dots ,x_k\in X$.

Then:

$f$ has a unique fixed point $\overline{x}$, that is, there exists a unique $x^* \in X$ such that $f(x^*,\dots ,x^*)=x^*$;
the sequence $\{ x_n\} _{n\geq 0}$ defined by

\begin{equation} \label{Rel_Sirkpasi} x_{n+1}=f(x_{n},\dots , x_{n-k+1}),\qquad n=k-1,k,k+1,\dots \end{equation}
11

converges to $\overline{x}$, for any $x_0,\dots ,x_{k-1}\in X$.

It is easy to see that, subject to a change of notation, Theorem 4.2.1 in [ 23 ] is obtained from Theorem 2.1 for $X=I\subset \mathbb {R}$ and that, in the particular case $k=1$, from Theorem 2.1, we get exactly the well-known Banach contraction mapping principle. In this case, the $k$-point iterative method (??) reduces to Picard iterations:

\begin{equation} \label{Picard} x_{n+1}=f(x_n),\qquad n=0,1,2,3,\dots , \end{equation}

Apart from applications in numerical analysis, Prešić fixed point theorem has other important applications in the study of global asymptotic stability of the equilibrium for nonlinear difference equations; see the paper [ 11 ] and the monograph [ 18 ] .

On the other hand, some other Prešić type fixed point theorems have been obtained in [ 12 ] , [ 18 ] , [ 19 ] , [ 17 ] , [ 21 ] , [ 30 ] , and for more general contractive type conditions in [ 8 ] , [ 9 ] and [ 11 ] , with some applications to nonlinear cyclic systems of equations and difference equations.

Theorem 2.1 and other similar results, like the ones in [ 12 ] , [ 19 ] , [ 17 ] , [ 30 ] , have important applications in the iterative solution of nonlinear equations; see [ 23 ] and [ 28 ] , [ 9 ] , [ 10 ] , as well as [ 31 ] - [ 40 ] .

Another important generalization of Theorem 2.1 was obtained by I.A. Rus [ 30 ] , for operators $T$ fulfilling the more general condition

\begin{equation} \label{Cond_PresicRus} d(T(x_0,\dots ,x_{k-1}), T(x_1,\dots ,x_{k}))\leq \varphi (d(x_0,x_1),\dots ,d(x_{k-1},x_k)),\end{equation}

for any $x_0,\dots ,x_k\in X$, where $\varphi :\mathbb R^k_+\rightarrow \mathbb R_+$ satisfies certain appropriate conditions.

Another important generalization of Prešić’s result was recently obtained by L. Cirić and S. Prešić in [ 12 ] , where, instead of (??) and its generalization (??), the following contraction condition is considered:

\begin{equation} \label{Cond_PresicCiric} d(T(x_0,\dots ,x_{k-1}), T(x_1,\dots ,x_{k}))\leq \lambda \max \{ d(x_0,x_1),\dots ,d(x_{k-1},x_k)\} ,\end{equation}

for any $x_0,\dots ,x_k\in X$, where $\lambda \in (0,1)$.

Other general Prešić type fixed point results have been very recently obtained by the third author in [ 18 ] - [ 21 ] based on alternative contractive conditions which are more general than ??, ?? and ??. For other related results, we refer to [ 31 ] - [ 40 ] .

The following lemmas will be useful in proving our main results in this paper.

Lemma 1

( [ 29 ] ) Let $k\in \mathbb {N},k\neq 0$ and $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}\in \mathbb {R}_{+}$ such that $\overset {k}{\underset {i=1}{\sum }}\alpha _{i}=\alpha {\lt}1$. If $\{ \Delta _{n}\} _{n\geq 1}$ is a sequence of positive numbers satisfying

\begin{equation} \label{LemaPresic_conditie} \Delta _{n+k}\leq \alpha _{1}\Delta _{n}+\alpha _{2}\Delta _{n+1}+\ldots +\alpha _{k}\Delta _{n+k-1},\quad n\geq 1, \end{equation}

then there exist $L{\gt}0$ and $\theta \in (0,1)$ such that

\begin{equation} \label{LemaPresic_concluzie} \Delta _{n}\leq L\cdot \theta ^{n},\qquad \text{ for all } n\geq 1. \end{equation}

The next Lemma is due to Ostrowski ( [ 16 ] ) and can also be found in an extended form in [ 4 ] .

Lemma 2

Let $\{ a_n\} _{n\geq 0}$, $\{ b_n\} _{n\geq 0}$ be two sequences of positive real numbers and $q\in (0,1)$ such that:

$a_{n+1}\leq q \, a_{n}+b_{n},n\geq 0$;
$b_n\rightarrow 0$ as $n\rightarrow \infty $.

Then:

\[ \underset {n\rightarrow \infty }{\lim }a_{n}=0. \]

A more general form of the previous lemma has been obtained in [ 2 ] .

Lemma 3

Let $\{ a_n\} _{n\geq 0}$ be a sequence of positive real numbers and let $\{ b_n\} _{n\geq 0}$ be a sequence of non-negative real numbers for which there exist $q\in (0,1)$ and an integer $k\geq 0$ such that:

$a_{n+1}\leq q \, a_{n-k}+b_{n},\quad n\geq k$;
$\sum _{n=1}^{\infty } b_n {\lt}+\infty $.

Then:

\[ \sum _{n=1}^{\infty } a_n {\lt}+\infty . \]

Note that for $k=0$, by Lemma 3, we actually get the conclusion of Lemma 2, i.e.,

\[ \underset {n\rightarrow \infty }{\lim }a_{n}=0. \]

3 Main results

Our first main result is an improved version of Prešić fixed point theorem in [ 29 ] (Theorem 2.1); see also [ 18 ] .

Theorem 3.1

Let $(X,d)$ be a complete metric space, $k$ a positive integer and $f:X^k\rightarrow X$ a mapping for which there exist $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}\in \mathbb {R}_{+}, $ $\overset {k}{\underset {i=1}{\sum }}\alpha _{i}=\alpha {\lt}1$ such that

\begin{equation} \label{Cond_Presic-1} d(f(x_0,\dots ,x_{k-1}), f(x_1,\dots ,x_{k}))\leq \overset {k}{\underset {i=1}{\sum }}\alpha _i d(x_{i-1},x_i), \end{equation}

for all $x_0,\dots ,x_k\in X$.

Then:

$f$ has a unique fixed point $\overline{x}$, i.e., $f(\overline{x},\dots , \overline{x})=\overline{x}$;
the sequence $\{ y_{n}\} _{n\geq 0}$, defined by

\begin{equation} \label{Rel_Sir.yn.P} y_{n+1}=f(y_{n},y_{n},\ldots ,y_{n}), \quad n\geq 0,\end{equation}
18

converges to $\overline{x}$, for any $y_0\in X$;
the sequence $\{ x_{n}\} _{n\geq 0}$ defined by $x_{0},\ldots ,x_{k-1}\in X$ and

\begin{equation} \label{Rel_xn.P} x_{n+1}=f(x_{n-k+1},x_{n-k},\ldots ,x_{n}), \quad n\geq k-1, \end{equation}
19

also converges to $\overline{x}$, for all $x_{0},\ldots ,x_{k-1}\in X$.
the sequence $\{ z_{n}\} _{n\geq 0}$ defined by $z_{0},\ldots ,z_{k-1}\in X$ and

\begin{equation} \label{Rel_zn.P} z_{n+1}=f(z_{n},z_{n-1},\ldots ,x_{n-k+1}),\quad n\geq k-1, \end{equation}
20

converges to $\overline{x}$, for all $z_{0},\ldots ,z_{k-1}\in X$.
The following estimates hold:

\begin{equation} \label{estimate-1} d(y_{n},\overline{x})\leq \tfrac {\alpha ^{n}}{1-\alpha }\, d(y_{1},y_{0})\, ,\quad n=1,2,\dots ; \end{equation}
21

\begin{equation} \label{estimate-2} d(x_{n},\overline{x})\leq L\, \tfrac {\theta ^{n}}{1-\theta },\quad n=1,2,\dots ; \end{equation}
22

where $L{\gt}0$ and $\theta \in (0,1)$ are some constants.

\begin{equation} \label{estimate-3} d(z_{n},\overline{x})\leq L_1\, \tfrac {\theta _1^{i}}{1-\theta _1},\quad n=1,2,\dots ; \end{equation}
23

where $L_1{\gt}0$ and $\theta _1 \in (0,1)$ are some constants.

Proof â–¼

$1), 2)$ By considering the associate operator $F:X\rightarrow X, F(x)=f(x,\ldots ,x)$, for any $x\in X$ we have:

\begin{eqnarray*} & & d(F(x),F(y))= d(f(x,x,\ldots ,x),f(y,y,\ldots ,y))\leq \\ & & \ \ \leq d(f(x,\ldots ,x),f(x,\ldots ,x,y))+d(f(x,\ldots ,x,y),f(x,\ldots ,x,y,y))+\\ & & \quad \ +\ldots +\\ & & \quad \ +d(f(x,x,y,\ldots ,y),f(x,y,\ldots ,y))+d(f(x,y,\ldots ,y),f(y,\ldots ,y)). \end{eqnarray*}

By ?? we obtain:

\begin{eqnarray*} d(F(x),F(y))& \leq & \left[\alpha _{1}d(x,x)+\alpha _{2}d(x,x)+\ldots +\alpha _{k-1}d(x,x)+\alpha _{k}d(x,y)\right]+\\ & \quad +& \left[\alpha _{1}d(x,x)+\alpha _{2}d(x,x)+\ldots +\alpha _{k-1}d(x,y)+\alpha _{k}d(y,y)\right]+\\ & \quad +& \ldots +\\ & \quad +& \left[\alpha _{1}d(x,y)+\alpha _{2}d(y,y)+\ldots +\alpha _{k-1}d(y,y)+\alpha _{k}d(y,y)\right], \end{eqnarray*}

\[ d(F(x),F(y))\leq \overset {k}{\underset {i=1}{\sum }}\alpha _{i}d(x,y)=\alpha d(x,y), \]

for any $x,y\in X$, which shows that $F$ is a Banach contraction with constant $\alpha \in [0,1)$.

Consequently, by Banach contraction mapping principle, $F$ has a unique fixed point $\overline{x}\in X$ that can be obtained by means of the Picard iterations corresponding to $F$ starting from any $x_0\in X$, which thus proves $1)$ and $2)$.

$3)$ We prove now that the $k$-step iteration method $\{ x_n\} _{n\geq 0}$, defined by (??) converges to the unique fixed point $\overline{x}$ of $f$. For $n\geq k$ we have:

\begin{eqnarray} \nonumber & & d(x_{n},x_{n+1})=d(f(x_{n-k},x_{n-k+1},\ldots ,x_{n-1}),f(x_{n-k+1},x_{n-k+2},\ldots ,x_{n}))\leq \\ \label{Rel_delta.n.P} & & \ \leq \alpha _{1}d(x_{n-k},x_{n-k+1})+\alpha _{2}d(x_{n-k+1},x_{n-k+2})+\ldots +\alpha _{k}d(x_{n-1},x_{n}). \end{eqnarray}

\[ \Delta _{n}=d(x_{n-1},x_{n}),\quad n\geq 1, \]

then, by (??), we obtain that the sequence $\{ \Delta _n\} _{n\geq 1}$ satisfies:

\[ \Delta _{n+1}\leq \alpha _{1}\Delta _{n-k+1}+\alpha _{2}\Delta _{n-k+2}+\ldots +\alpha _{k}\Delta _{n},\quad n\geq 1, \]

where $\alpha _{1},\alpha _{2},\ldots ,\alpha _{k}{\gt}0$ and $\overset {k}{\underset {i=1}{\sum }}\alpha _{i}=\alpha {\lt}1$.

By Lemma 1, there exist $L{\gt}0$ and $\theta \in (0,1)$ such that $\Delta _{n}\leq L\theta ^{n},n\geq 1$, that is,

\begin{equation} \label{bla} d(x_{n-1},x_{n})\leq L\theta ^{n},\quad n\geq 1. \end{equation}

For $n\geq 1$ and $p\geq 1$, by (25) we obtain:

\begin{eqnarray*} d(x_{n},x_{n+p})& \leq & d(x_{n},x_{n+1})+d(x_{n+1},x_{n+2})+\ldots +d(x_{n+p-1},x_{n+p})\leq \\ & \leq & L\theta ^{n+1}+L\theta ^{n+2}+\ldots +L\theta ^{n+p}=\\ & =& L\theta ^{n+1}\left(1+\theta +\theta ^{2}+\ldots +\theta ^{p-1}\right), \end{eqnarray*}

\begin{equation} \label{Cauchy} d(x_{n},x_{n+p})\leq L\theta ^{n+1}\dfrac {1-\theta ^{p}}{1-\theta },\quad n\geq 1,p\geq 1. \end{equation}

Since $\theta \in (0,1)$, it follows that $\{ x_{n}\} _{n\geq 0}$ is a Cauchy sequence, which in the complete metric space $(X,d)$ is convergent.

We prove that $\{ x_{n}\} _{n\geq 0}$ in fact converges to $\overline{x}$, the unique fixed point of $f$. Indeed, for $n\geq 0$ we have:

\begin{align} & d(x_{n+1},\overline{x})\leq d(f(x_{n-k+1},x_{n-k+2},\ldots ,x_{n}),f(\overline{x},\overline{x},\ldots ,\overline{x}))\nonumber \\ & \leq d(f(x_{n-k+1},x_{n-k+2},\ldots ,x_{n}),f(x_{n-k+2},x_{n-k+3},\ldots ,x_{n},\overline{x}))+\nonumber \\ & \quad +d(f(x_{n-k+2},x_{n-k+3},\ldots ,x_{n},\overline{x}),f(x_{n-k+3},x_{n-k+4},\ldots ,x_{n},\overline{x},\overline{x}))+\nonumber \\ & \quad +\ldots +d(f(x_{n},\overline{x},\ldots ,\overline{x}),f(\overline{x},\overline{x},\ldots ,\overline{x}))\label{eq-mare}, \end{align}

so by (??) we obtain:

\begin{eqnarray*} & & d(x_{n+1},\overline{x})\leq [\alpha _{1}d(x_{n-k+1},x_{n-k+2})+\ldots +\alpha _{k-1}d(x_{n-1},x_{n})+\alpha _{k}d(x_{n},\overline{x})]+\\ & & \ \ \ \ +[\alpha _{1}d(x_{n-k+2},x_{n-k+3})+\ldots +\alpha _{k-1}d(x_{n},\overline{x})+\alpha _{k}d(\overline{x},\overline{x})]+\\ & & \ \ \ \ +\ldots +\\ & & \ \ \ \ +[\alpha _{1}d(x_{n},\overline{x})+\alpha _{2}d(\overline{x},\overline{x})+\ldots +\alpha _{k}d(\overline{x},\overline{x})]. \end{eqnarray*}

Now using (25) it follows that:

\begin{eqnarray*} & & d(x_{n+1},\overline{x})\leq [\alpha _{1}L\theta ^{n-k+2}+\alpha _{2}L\theta ^{n-k+3}+\ldots +\alpha _{k-1}L\theta ^{n}+\alpha _{k}d(x_{n},\overline{x})]+\\ & & \ \ \ \ +[\alpha _{1}L\theta ^{n-k+3}+\alpha _{2}L\theta ^{n-k+4}+\ldots +\alpha _{k-2}L\theta ^{n}+\alpha _{k-1}d(x_{n},\overline{x})+\alpha _{k}\cdot 0]+\\ & & \ \ \ \ +\ldots \\ & & \ \ \ \ +[\alpha _{1}d(x_{n},\overline{x})+0]=\\ & & \ \ =\alpha _{1}L\theta ^{n-k+2}+(\alpha _{1}+\alpha _{2})L\theta ^{n-k+3}+\ldots +(\alpha _{1}+\alpha _{2}+\ldots +\alpha _{k-1})L\theta ^{n}+\\ & & \ \ \ \ +(\alpha _{1}+\alpha _{2}+\ldots +\alpha _{k})d(x_{n},\overline{x}). \end{eqnarray*}

Finally we obtain that:

\begin{align*} d(x_{n+1},\overline{x})& \leq \alpha d(x_{n},\overline{x})+L\theta ^{n}[\alpha _{1}\theta ^{2-k}+(\alpha _{1}+\alpha _{2})\theta ^{3-k}+\ldots +\notag \\ & \quad +(\alpha _{1}+\alpha _{2}+\ldots +\alpha _{k-2})\theta +(\alpha _{1}+\alpha _{2}+\ldots +\alpha _{k-1})],\quad n\geq 1, \end{align*}

where $\theta \in (0,1)$. This inequality shall lead to estimate

\begin{equation} \label{Rel_rate.P} d(x_{n+1},\overline{x})\leq \alpha d(x_{n},\overline{x})+M\cdot \theta ^{n},n\geq 0, \end{equation}

where

\[ M\! =\! L[\alpha _{1}\theta ^{2-k}+(\alpha _{1}+\alpha _{2})\theta ^{3-k}+\ldots +(\alpha _{1}+\alpha _{2}+\ldots +\alpha _{k-2})\theta +(\alpha _{1}+\alpha _{2}+\ldots +\alpha _{k-1})] \]

is a fixed positive number (since $k$ is fixed). Considering

\begin{eqnarray*} & & a_{n}=d(x_{n},\overline{x}),\\ & & \ \ q=\alpha \in [0,1)\\ & & b_{n}=M\theta ^{n},\quad n\geq 1, \end{eqnarray*}

the conditions of Lemma 2 are fulfilled, so by its conclusion

\[ d(x_{n},\overline{x})\rightarrow 0,\quad n\rightarrow \infty . \]

Consequently, the sequence $\{ x_{n}\} _{n\geq 0}$ converges to $\overline{x}$, the unique fixed point of $f$.

$4)$ First, we observe that for

\[ \Delta _n=d(z_n,z_{n-1}), \quad n\geq 1, \]

proceeding as in the previous case, we obtain by Lemma 1, that there exist $L_1{\gt}0$ and $\theta _1\in (0,1)$ such that $\Delta _{n}\leq L_1\theta _1^{n},\ n\geq 1$, that is,

\begin{equation} \label{bla-1} d(z_{n-1},z_{n})\leq L_1\theta _1^{n},\quad n\geq 1. \end{equation}

Next, in a similar way to the case of $\{ x_{n}\} _{n\geq 0}$ but by following slightly different computations, we find that

\[ d(z_{n+1},\overline{x})\leq \alpha d(z_{n-k+1},\overline{x})+M_1\, \theta _1^n, \]

for a certain constant $M_1{\gt}0$.

Now, simply use Lemma 3 to get the conclusion that the sequence $\{ z_{n}\} _{n\geq 0}$ converges to $\overline{x}$, too.

$5)$ The error estimate 21 follows by the Banach contraction mapping principle in the form given in [ 4 ] , while the estimates 22 and 23 are obtained by 26 and its version for $\{ z_{n}\} _{n\geq 0}$, respectively, by letting $p\rightarrow \infty $.

Proof â–¼

4 Rate of convergence versus speed of convergence

As before, let $\{ x_{n}\} _{n\geq 0}$ be a convergent sequence with limit $\overline{x}$. If, for some $r$, we have

\[ \lim _{n\rightarrow \infty }\tfrac {d(\bar{x}_{n+1},\bar{x}^*)}{[d(\bar{x}_{n},\bar{x}^*)]^r}=\lambda {\lt}+\infty , \]

then $r$ is called the rate of convergence of $\{ x_{n}\} _{n\geq 0}$, while $\lambda $ is termed as its asymptotic error; see [ 15 ] for more details.

If $r=1$, we say that the convergence of $\{ x_{n}\} _{n\geq 0}$ is linear, if $r=2$, we say that the convergence is quadratic, while, for $1{\lt}r{\lt}2$, we say that the convergence is superlinear.

Now, let $\{ x_{n}\} _{n\geq 0}$ and $\{ y_{n}\} _{n\geq 0}$ be two convergent sequences with the same limit $\overline{x}$. If

\[ \lim _{n\rightarrow \infty }\tfrac {d(\bar{x}_{n},\bar{x}^*)}{d(y_{n},\bar{x}^*)}=\beta {\lt}+\infty , \]

exists and $\beta =0$, then we say that $\{ x_{n}\} _{n\geq 0}$ converges faster than $\{ y_{n}\} _{n\geq 0}$ to $\overline{x}$, and if $\beta \neq 0$, we say that $\{ x_{n}\} _{n\geq 0}$ and $\{ y_{n}\} _{n\geq 0}$ have the same speed of convergence.

Clearly, if $\beta =\infty $, then $\{ y_{n}\} _{n\geq 0}$ converges faster than $\{ x_{n}\} _{n\geq 0}$ to $\overline{x}$ (for more details see [ 1 ] , [ 3 ] , [ 4 ] ).

This concept of convergence can be defined in a more general context, when $\{ x_{n}\} _{n\geq 0}$ and $\{ y_{n}\} _{n\geq 0}$ are convergent sequences with different limits, $\overline{x}$ and $\overline{y}$, respectively; see [ 1 ] and [ 4 ] .

Example 4.1

If we consider the sequences $\{ a_{n}\} _{n\geq 0}$, $\{ b_{n}\} _{n\geq 0}$, $\{ c_{n}\} _{n\geq 0}$ given by

\[ a_n=\tfrac {1}{n+1},\, \quad b_n=\tfrac {1}{2^n},\, \quad c_n=2^{-2^n}, \]

then, obviously, $a_n\rightarrow 0$, $b_n\rightarrow 0$ and $c_n\rightarrow 0$, as $n\rightarrow \infty $, and since

\[ a)\, \lim _{n\rightarrow \infty }\tfrac {a_{n+1}}{a_n}=1,\quad b)\, \lim _{n\rightarrow \infty }\tfrac {b_{n+1}}{b_n}=\tfrac {1}{2},\quad c)\, \lim _{n\rightarrow \infty }\tfrac {b_{n}}{a_n}=0, \]

it follows that $\{ a_{n}\} _{n\geq 0}$ and $\{ b_{n}\} _{n\geq 0}$ have the same rate of convergence (linear). However, $\{ b_{n}\} _{n\geq 0}$ converges faster than $\{ a_{n}\} _{n\geq 0}$ to $0$.

Moreover, since

\[ \lim _{n\rightarrow \infty }\tfrac {c_{n+1}}{(c_n)^2}=1, \]

it follows that the sequence $\{ c_{n}\} _{n\geq 0}$ has quadratic rate of convergence and, as an immediate consequence, converges faster than both $\{ a_{n}\} _{n\geq 0}$ and $\{ b_{n}\} _{n\geq 0}$.

If we now use the proof of Theorem 3.1 and the complete form of the Banach contraction principle – see for example [ 4 ] – then we obtain for the sequences $\{ x_{n}\} _{n\geq 0}$ and $\{ y_{n}\} _{n\geq 0}$ the following error estimates:

\begin{equation} \label{eq-33} d(y_{n+1},\overline{x})\leq \alpha d(y_{n},\overline{x}), \quad n\geq 0; \end{equation}

\begin{equation} \label{eq-34} d(x_{n+1},\overline{x})\leq \alpha d(x_{n},\overline{x})+M\cdot \theta ^{n},\quad n\geq 0, \end{equation}

where $M{\gt}0$ and $\theta \in (0,1)$ are constant, and also

\begin{equation} \label{eq-35} d(z_{n+1},\overline{x})\leq \alpha d(z_{n},\overline{x})+M_1\cdot \theta _1^{n},\quad n\geq 0. \end{equation}

Thus, the estimates 29-31 show that the sequences $\{ x_{n}\} _{n\geq 0}$, $\{ y_{n}\} _{n\geq 0}$ and $\{ z_{n}\} _{n\geq 0}$ have all linear rate of convergence, while the estimates 21-23 offer information on the speed of convergence of these sequences.

In the proof of Lemma 1 in [ 29 ] , we note that $\theta $ in 22 is the unique positive root of the polynomial equation

\[ t^k-\alpha _1 \, t^{k-1}-\dots -\alpha _{k-1}\, t-\alpha _k=0, \]

while $\theta _1$ in 23 is the unique positive root of the polynomial equation

\[ t^k-\alpha _k \, t^{k-1}-\dots -\alpha _{2}\, t-\alpha _1=0. \]

Therefore, in view of the estimates 22-23, to compare the iterative methods $\{ x_{n}\} _{n\geq 0}$, $\{ y_{n}\} _{n\geq 0}$ and $\{ z_{n}\} _{n\geq 0}$, it suffices to establish the order relation between the constants

\[ \alpha , \theta , \theta _1\in (0,1). \]

5 Examples and concluding remarks

The following example illustrates Theorem 3.1.

Example 5.1

Let $X=\mathbb {R}$ with the usual metric and $f\colon X^2\rightarrow X$ be defined by

\[ f(x,y)=\tfrac {x+2y}{4},\quad \forall (x,y)\in X^2. \]

It is easy to check that $f$ satisfies condition ?? (with $\alpha _1=\tfrac {1}{4}$, $\alpha _2=\tfrac {1}{2}$), condition ?? (with $\varphi (t_1,t_2)=\tfrac {1}{4}t_1+\tfrac {1}{2}t_2$), as well as condition ?? (with $\lambda =\tfrac {3}{4}$).

Consider the sequence $\{ x_n\} $

\[ x_{n+1}=\tfrac {x_n+2x_{n-1}}{4},\quad n\geq 1, \]

corresponding to the identity permutation $(0,1)$. Then we have

\[ x_n=c_1\Big(\tfrac {1-\sqrt{33}}{8}\Big)^n+c_2\Big(\tfrac {1+\sqrt{33}}{8}\Big)^n, \quad n\geq 1, \]

where $c_1$ and $c_2$ are some constants. Consider now the sequence $\{ z_n\} $

\[ z_{n+1}=\tfrac {2 z_n+z_{n-1}}{4},\quad n\geq 1, \]

corresponding to the permutation $(1,0)$ of $(0,1)$. Similarly, we obtain

\[ z_n=a_1\Big(\tfrac {1-\sqrt{5}}{4}\Big)^n+a_2\Big(\tfrac {1+\sqrt{5}}{4}\Big)^n, \quad n\geq 1, \]

where $a_1$ and $a_2$ are some constants. Now, considering the sequence $\{ y_n\} $ given by $y_0\in X$ and

\[ y_{n+1}=\tfrac {3}{4} y_n\geq 0, \]

we get

\[ y_n=\Big(\tfrac {3}{4}\Big)^n y_0,\quad n\geq 0. \]

Since

\[ \Big|\tfrac {1-\sqrt{5}}{4}\Big| {\lt}\Big|\tfrac {1-\sqrt{33}}{8} \Big|{\lt}\tfrac {3}{4} {\lt}\tfrac {1+\sqrt{5}}{4} {\lt}\tfrac {1+\sqrt{33}}{8}, \]

we have

\[ \lim _{n\rightarrow \infty }\tfrac {x_n}{y_n}=c_1\cdot \lim _{n\rightarrow \infty }\Big(\tfrac {1-\sqrt{33}}{6}\Big)^n+c_2\cdot \lim _{n\rightarrow \infty }\Big(\tfrac {1+\sqrt{33}}{6}\Big)^n=+\infty ; \]

\[ \lim _{n\rightarrow \infty }\tfrac {z_n}{y_n}=a_1\cdot \lim _{n\rightarrow \infty }\Big(\tfrac {1-\sqrt{5}}{3}\Big)^n+a_2\cdot \lim _{n\rightarrow \infty }\Big(\tfrac {1+\sqrt{5}}{3}\Big)^n=+\infty ; \]

and

\[ \lim _{n\rightarrow \infty }\tfrac {x_n}{z_n}=\lim _{n\rightarrow \infty }\tfrac {c_1\Big(\tfrac {1-\sqrt{33}}{8}\Big)^n+c_2\Big(\tfrac {1+\sqrt{33}}{8}\Big)^n}{a_1\Big(\tfrac {1-\sqrt{5}}{4}\Big)^n+a_2\Big(\tfrac {1+\sqrt{5}}{4}\Big)^n} \]

\[ =\tfrac {c_2}{a_2}\cdot \lim _{n\rightarrow \infty }\Big(\tfrac {1+\sqrt{33}}{2+2\sqrt{5}}\Big)^n =+\infty , \]

as $c_1,c_2,a_1,a_2\neq 0$.

These calculations prove that the sequence $\{ y_n\} $ converges faster than $\{ z_n\} $ to $0$, $\{ z_n\} $ converges faster than $\{ x_n\} $, and $\{ y_n\} $ converges faster than $\{ z_n\} $, although all the three sequences have the same (linear) rate of convergence.

We thus can conclude that the above numerical tests confirm the theoretical results obtained in Păvăloiu [ 23 ] . Indeed, amongst the $k!$ iterative methods of the form

\begin{equation} \label{eq-5u} x_{n+1}=f(x_{i_0+n-k+1},x_{i_1+n-k+1},\dots , x_{{i_{k-1}+n-k+1}}),\quad n\geq k-1, \end{equation}

where $(i_0,i_1,\dots ,i_{k-1})$ is a permutation of $(0,1,\dots ,k-1)$, the optimal method is $\{ z_n\} $, which corresponds to the permutation $(i_0,i_1,\dots ,i_{k\! -\! 1})$ of $(0,1,\dots ,k\! -\! 1)$ for which one has

\[ \alpha _{i_0}\geq \alpha _{i_1}\geq \dots \geq \alpha _{i_{k-1}}. \]

This also shows that, especially in the case of fixed point iteration procedures, which have generally linear rate a convergence, in order to decide about the fastest iterative method, we have to take into consideration the speed of convergence, usually deduced from the error estimates of the form 21-23.

An interesting conclusion that follows from the above example, is that, in this particular case, the one-point algorithm $\{ y_n\} $ converges faster than the two two-step algorithms $\{ x_n\} $ and $\{ z_n\} $.

The problem is to study if this claim is valid in general. In view of 21-23, it would be sufficiently to show that

\[ 0{\lt}\alpha {\lt}\theta _1{\lt}\theta {\lt}1, \]

which is a result similar to that given by Theorem 5.3.2 in [ 28 ] .

We invite the reader to carry out all the calculations for the function $f$ in the next example.

Example 5.2

Let $X=\mathbb {R}$ with the usual metric and $f\colon X^3\rightarrow X$ be defined by

\[ f(x,y,z)=\tfrac {x-2y+3z}{7},\quad \forall (x,y,z)\in X^3, \]

which obviously satisfies condition ?? with $\alpha _1=\tfrac {1}{7}$, $\alpha _2=\tfrac {2}{7}$ and $\alpha _3=\tfrac {3}{7}$.

Acknowledgements

The first author’s research was done during his visit of Department of Mathematics and Statistics, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia (December 2014-January 2015). He gratefully thanks Professor Abdul Rahim Khan and Dr. Al-Attas, the Chairman of the Department of Mathematics and Statistics, for the excellent conditions they offered during the visit.

Bibliography

1: V. Berinde, Despre ordinul de convergenţă al şirurilor de numere reale, Gazeta Matematică, 103 (1998) no. 4, pp. 146–153 (in Romanian).
2: V. Berinde, The generalized ratio test revisited, Bul. Ştiinţ. Univ. Baia Mare, Fasc. Mat.-Inf., 16 (2000) no. 2, pp. 303–306.
3: V. Berinde, Picard iteration converges faster than Mann iteration for a class of quasi-contractive operators, Fixed Point Theory Appl., 2004, no. 2, pp. 97–105. $\includegraphics[scale=0.1]{ext-link.png}$
4: V. Berinde, Iterative Approximation of Fixed Points, Springer, Berlin Heidelberg New York, 2007. $\includegraphics[scale=0.1]{ext-link.png}$
5: V. Berinde, A note on a difference inequality used in the iterative approximation of fixed points, Creat. Math. Inform., 18 (2009) no. 1, pp. 6–9.
6: V. Berinde, On a family of first order difference inequalities used in the iterative approximation of fixed points, Creat. Math. Inform., 18 (2009) no. 2, pp. 110–122.
7: V. Berinde, Approximating common fixed points of noncommuting discontinuous weakly contractive mappings in metric spaces, Carpathian J. Math., 25 (2009) no. 1, pp. 13–22.
8: V. Berinde and M. Păcurar, An iterative method for approximating fixed points of Prešić nonexpansive mappings, Rev. Anal. Numér. Théor. Approx., 38 (2009) no. 2, pp. 144–153. $\includegraphics[scale=0.1]{ext-link.png}$
9: V. Berinde and M. Păcurar, Two elementary applications of some Prešić type fixed point theorems, Creat. Math. Inform., 20 (2011) no. 1, pp. 32–42.
10: V. Berinde and M. Păcurar, O metodă de tip punct fix pentru rezolvarea sistemelor ciclice, Gazeta Matematică, Seria B, 116 (2011) no. 3, pp. 113–123.
11: Y.-Z. Chen, A Prešić type contractive condition and its applications, Nonlinear Anal., 71 (2009) no. 12, e2012–e2017. $\includegraphics[scale=0.1]{ext-link.png}$
12: L.B. Cirić and S.B. Prešić, On Prešić type generalization of the Banach contraction mapping principle, Acta Math. Univ. Comenianae, 76 (2007) no. 2, pp. 143-147.
13: R. Kannan, Some results on fixed points, Bull. Calcutta Math. Soc., 10 (1968), pp. 71–76.
14: A.R. Khan, V. Kumar, and N. Hussain, Analytical and numerical treatment of Jungck-type iterative schemes, Appl. Math. Comput., 231 (2014), pp. 521–535. $\includegraphics[scale=0.1]{ext-link.png}$
15: J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equation in Several Variables, Academic Press, New York, 1970.
16: A.M. Ostrowski, The round-off stability of iterations, Zeit. Angev. Math. Mech., 47 (1967) No. 2, pp. 77–81. $\includegraphics[scale=0.1]{ext-link.png}$
17: M. Păcurar, Approximating common fixed points of Prešić-Kannan type operators by a multi-step iterative method, An. Ştiinţ,. Univ. “Ovidius” Constanţa Ser. Mat., 17 (2009) no. 1, pp. 153–168.
18: M. Păcurar, Iterative Methods for Fixed Point Approximation, Risoprint, Cluj-Napoca, 2010.
19: M. Păcurar, A multi-step iterative method for approximating fixed points of Prešić-Kannan operators, Acta Math. Univ. Comen. New Ser., 79 (2010), no. 1, pp. 77–88.
20: M. Păcurar, A multi-step iterative method for approximating common fixed points of Prešić-Rus type operators on metric spaces, Stud. Univ. Babeş-Bolyai Math., 55 (2010) no. 1, pp. 149–162.
21: M. Păcurar, Fixed points of almost Prešić operators by a $k$-step iterative method, An. Ştiint,. Univ. Al. I. Cuza Iaşi, Ser. Noua, Mat. 57 (2011), Supliment, pp. 199–210. $\includegraphics[scale=0.1]{ext-link.png}$
22: M. Păcurar, Common fixed points for almost Prešić type operators, Carpathian J. Math., 28 (2012) no. 1, pp. 117–126.
23: I. Păvăloiu, Rezolvarea ecuaţiilor prin interpolare, Editura Dacia, Cluj-Napoca, 1981.
24: I. Păvăloiu, Sur l’ordre de convergence des méthodes d’itération, Mathematica, 23(46) (1981), pp. 261–272.
25: I. Păvăloiu, La convergence de certaines méthodes iteratives pour résoudre certaines équations opératorielles, Seminar on Functional Analysis and Numerical Methods, Preprint 86-1, Univ. Babes-Bolyai Cluj-Napoca, (1986), pp. 127–132.
26: I. Păvăloiu, Sur l’approximation des racines des équations dans un espace métrique, Seminar on Functional Analysis and Numerical Methods, Preprint 89-1, Univ. Babes-Bolyai, Cluj-Napoca, (1989), pp. 95–104.
27: I. Păvăloiu, On the convergence order of the multistep methods, Bul. Stiint. Univ. Baia Mare Ser. B, 13 (1997) nos. 1–2, pp. 107–116.
28: I. Păvăloiu and N. Pop, Interpolare şi aplicaţii, Risoprint, Cluj-Napoca, 2005 (in Romanian).
29: S.B. Prešić, Sur une classe d’ inéquations aux différences finites et sur la convergence de certaines suites, Publ. Inst. Math. (Beograd)(N.S.), 5(19) (1965), pp. 75–78.
30: I.A. Rus, An iterative method for the solution of the equation $x=f(x,\ldots ,x)$, Rev. Anal. Numér. Théor. Approx., 10 (1981) no. 1, pp. 95–100. $\includegraphics[scale=0.1]{ext-link.png}$
31: S. Shukla, Prešić type results in 2-Banach spaces, Afr. Mat., 25 (2014) no. 4, pp. 1043–1051. $\includegraphics[scale=0.1]{ext-link.png}$
32: S. Shukla and N. Shahzad, $G$-Prešić operators on metric spaces endowed with a graph and fixed point theorems, Fixed Point Theory Appl., 2014, 2014:127, 10 pp. $\includegraphics[scale=0.1]{ext-link.png}$
33: S. Shukla and R. Sen, Set-valued Prešić-Reich type mappings in metric spaces, Rev. R. Acad. Cienc. Exactas Fs. Nat. Ser. A Math. RACSAM, 108 (2014) no. 2, pp. 431–440.
34: S. Shukla, Set-valued Prešić-Ćirić type contraction in $0$-complete partial metric spaces, Mat. Vesnik 66 (2014) no. 2, pp. 178–189.
35: S. Shukla, S. Radenović and S. Pantelić, Some fixed point theorems for Prešić-Hardy-Rogers type contractions in metric spaces, J. Math., 2013, Art. ID 295093, 8 pp. $\includegraphics[scale=0.1]{ext-link.png}$
36: G.M. Eshaghi, S., Pirbavafa, M., Ramezani, C., Park and D.Y. Shin, Prešić-Kannan-Rus fixed point theorem on partially order metric spaces, Fixed Point Theory, 15 (2014) no. 2, pp. 463–474.
37: T. Nazir and M. Abbas, Common fixed point of Prešić type contraction mappings in partial metric spaces, J. Nonlinear Anal. Optim., 5 (2014) no. 1, pp. 49–55.
38: N.V. Luong and N.X. Thuan, Some fixed point theorems of Prešić-Ćirić type, Acta Univ. Apulensis Math. Inform., 30 (2012), pp. 237–249.
14: M.S. Khan, M. Berzig and B. Samet, Some convergence results for iterative sequences of Prešić type and applications, Adv. Difference Equ., 2012, 2012:38, 12 pp. $\includegraphics[scale=0.1]{ext-link.png}$
39: R. George, K.P. Reshma and R.A. Rajagopalan, Generalised fixed point theorem of Prešić type in cone metric spaces and application to Markov process, Fixed Point Theory Appl., 2011, 2011:85, 8 pp. $\includegraphics[scale=0.1]{ext-link.png}$
40: R. George and M.S. Khan, On Prešić type extension of Banach contraction principle, Int. J. Math. Anal. (Ruse), 5 (2011) nos. 21–24, pp. 1019–1024.
41: H.J. Weinitschke, Über eine Klasse von Iterationsverfahren, Numer. Math., 6 (1964), pp. 395–404 (in German). $\includegraphics[scale=0.1]{ext-link.png}$