On the convergence order
of some Aitken–Steffensen type methods^∗

Ion Păvăloiu^†

(Date: April 13, 2003.)

Abstract.

In this note we make a comparative study of the convergence orders for the Steffensen, Aitken and Aitken–Steffensen methods. We provide some conditions ensuring their local convergence. We study the case when the auxiliary operators used have convergence orders $r_{1},r_{2}\in\mathbb{N}$ respectively. We show that the Steffensen, Aitken and Aitken–Steffensen methods have the convergence orders $r_{1}+1$ , $r_{1}+r_{2}$ and $r_{1}r_{2}+r_{1}$ respectively.

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

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

{amssubject}

47J25.

{keyword}

Steffensen, Aitken and Aitken–Steffensen iterations.

1. Introduction

It is well known that the Aitken–Steffensen type methods are meant to accelerate the convergence of some sequences converging to the solutions of operational equations [2], [3], [7]–[10], [13], [14] and [17].

Let $X$ be a Banach space and $F:D\subseteq X\rightarrow X$ a nonlinear mapping. Consider the equation

(1)

F\left(x\right)=\theta,

where $\theta$ is the null element of $X$ .

Additionally, consider the equations

(2)		$\displaystyle x$	$\displaystyle=\varphi_{1}\left(x\right),$
(3)		$\displaystyle x$	$\displaystyle=\varphi_{2}\left(x\right),$

which are assumed to be equivalent to (1), i.e., they have the same solutions.

As usually, $\mathcal{L}\left(X\right)$ stands for the set of linear operators from $X$ into itself. For $x,y,z\in X$ denote by $\left[x,y;F\right]\in\mathcal{L}\left(X\right)$ the first order divided difference of $F$ at the nodes $x$ and $y$ and by $\left[x,y,z;F\right]$ the second order divided difference of $F$ at $x, y, z$ ([8]–[10]).

For solving (1) we consider the sequences $\left(x_{n}\right)_{n\geq 0}$ generated by the following methods:

1. The Steffensen method:

(4)

x_{n+1}=x_{n}-\left[x_{n},\varphi_{1}\left(x_{n}\right);F\right]^{-1}F\left(x_% {n}\right),

$n=0,1,\ldots,\;x_{0}\in D;$

2. The Aitken method:

(5)

x_{n+1}=\varphi_{1}\left(x_{n}\right)-\left[\varphi_{1}\left(x_{n}\right),% \varphi_{2}\left(x_{n}\right);F\right]^{-1}F\left(\varphi_{1}\left(x_{n}\right% )\right),

$n=0,1,\ldots,\;x_{0}\in D;$

3. The Aitken–Steffensen method

(6)

x_{n+1}=\varphi_{1}\left(x_{n}\right)-\left[\varphi_{1}\left(x_{n}\right),% \varphi_{2}\left(\varphi_{1}\left(x_{n}\right)\right);F\right]^{-1}F\left(% \varphi_{1}\left(x_{n}\right)\right),

$n=0,1,\ldots,\;x_{0}\in D;$

Assume there exists $x^{\ast}\in D$ , the common solution for (1), (2) and (3), and that the mappings $\varphi_{1}$ , $\varphi_{2}$ are Fréchet differentiable at $x^{\ast}$ up to the orders $r_{1}$ and $r_{2}$ respectively, with

(7)

\varphi_{1}^{\left(i\right)}\left(x^{\ast}\right)=\theta_{i},\quad i=1,\ldots,% r_{1}-1,\ \varphi_{1}^{\left(r_{1}\right)}\left(x^{\ast}\right)\neq\theta_{r_{% 1}},

where $\theta_{i}$ , $i=1,\ldots,r_{1}$ are the null $i$ -linear mapping. Analogously, assume

(8)

\varphi_{2}^{\left(i\right)}\left(x^{\ast}\right)=\theta_{i},\quad i=1,\ldots,% r_{2}-1,\ \varphi_{2}^{\left(r_{2}\right)}\left(x^{\ast}\right)\neq\theta_{r_{% 2}}.

It is well known that relations (7) and (8) ensure that the iteration processes of the form

(9)

x_{n+1}=\varphi_{1}\left(x_{n}\right),\quad n=0,1,\ldots,\ \ x_{0}\in X,

and

(10)

x_{n+1}=\varphi_{2}\left(x_{n}\right),\quad n=0,1,\ldots,\;x_{0}\in X,

have the convergence orders $r_{1}$ , resp. $r_{2}$ .

In this note we show that the Steffensen method has the convergence order $r_{1}+1$ , the Aitken method $r_{1}+r_{2}$ , while the Aitken–Steffensen method $r_{1}\left(r_{2}+1\right)$ . We also provide conditions ensuring the local convergence of these sequences.

2. Local convergence

Let $S=\left\{x\in X:\left\|x-x^{\ast}\right\|\leq r\right\}$ be the ball with center at $x^{\ast}$ and with radius $r$ , and suppose $S\subseteq D$ .

The mappings $\varphi_{1}$ , $\varphi_{2}$ are assumed to obey the following hypotheses:

i)

the mapping $\varphi_{1}$ admits Fréchet derivatives up to the order $r_{1}\geq 1$ on $S$ , and

$\sup_{x\in S}\big\|\varphi_{1}^{\left(r_{1}\right)}\left(x\right)\big\|=L_{1}<% +\infty,$
ii)

the mapping $\varphi_{2}$ admits Fréchet derivatives up to the order $r_{2}\geq 1$ on $S$ , and

$\sup_{x\in S}\big\|\varphi_{2}^{\left(r_{2}\right)}\left(x\right)\big\|=L_{2}<% +\infty.$

The mapping $F$ is assumed to obey

i₁)

the linear mapping $\left[x,y;F\right]$ is invertible for all $x,y\in S$ , and

$\sup_{x,y\in S}\big\|\left[x,y;F\right]^{-1}\big\|=m<+\infty;$
ii₁)

the bilinear mapping $\left[x,y,z;F\right]$ is bounded for all $x,y,z\in S$ :

$\sup_{x,y,z\in S}\big\|\left[x,y,z;F\right]\big\|=M<+\infty.$

Regarding the convergence of the Steffensen method, we obtain the following result.

Theorem 2.1.

Assume that $\varphi_{1}$ obeys i) and (7), $F$ obeys i₁) and ii₁), and the initial approximation $x_{0}\in S$ is chosen such that

a)

$mM\left|x^{\ast}-x_{0}\right|<1;$
b)

$\frac{L_{1}}{r_{1}!}\left\|x^{\ast}-x_{0}\right\|^{r_{1}-1}\leq 1.$

Then the sequence $\left(x_{n}\right)_{n\geq 1}$ generated by (4) remains in $S$ and converges to $x^{\ast},$ satisfying

j₁)

$\left\|x^{\ast}-x_{n}\right\|\leq\big(\frac{MmL_{1}}{r_{1}!}\big)^{-\frac{1}{r% _{1}}}\rho_{0}^{p^{n}},\quad n=0,1,\ldots,$ where

$\rho_{0}=\big(\tfrac{MmL_{1}}{r_{1}!}\big)^{\frac{1}{r_{1}}}\left\|x^{\ast}-x_% {0}\right\|<1$

and $p=r_{1}+1;$
jj₁)

$\lim_{n\rightarrow\infty}x_{n}=x^{\ast}$ .

Proof.

Since $x_{0}\in S$ , then by the Taylor formula and by (7) and i) we get

(11)

\left\|\varphi_{1}\left(x_{0}\right)-x^{\ast}\right\|=\left\|\varphi_{1}\left(% x_{0}\right)-\varphi\left(x^{\ast}\right)\right\|\leq\tfrac{L_{1}}{r_{1}!}% \left\|x_{0}-x^{\ast}\right\|^{r_{1}},

whence, by b) it follows that

\left\|\varphi_{1}\left(x_{0}\right)-x^{\ast}\right\|\leq\left\|x^{\ast}-x_{0}% \right\|\leq r,

i.e., $\varphi_{1}\left(x_{0}\right)\in S$ . By the Newton identity,

	$\displaystyle\theta=F\left(x^{\ast}\right)=$	$\displaystyle F\left(x_{0}\right)+\left[x_{0},\varphi\left(x_{0}\right);F% \right]\left(x^{\ast}-x_{0}\right)$
		$\displaystyle+\left[x^{\ast},x_{0},\varphi\left(x_{0}\right);F\right]\left(x^{% \ast}-\varphi\left(x_{0}\right)\right)\left(x^{\ast}-x_{0}\right),$

and taking into account i₁), ii₁) and (4) for $n=0$ , we obtain

x^{\ast}-x_{1}=-\left[x_{0},\varphi\left(x_{0}\right);F\right]^{-1}\left[x^{% \ast},x_{0},\varphi\left(x_{0}\right);F\right]\left(x^{\ast}-\varphi\left(x_{0% }\right)\right)\left(x^{\ast}-x_{0}\right)

whence, using (11), a) and b), it follows that

(12)

\left\|x^{\ast}-x_{1}\right\|\leq\tfrac{MmL_{1}}{r_{1}!}\left\|x^{\ast}-x_{0}% \right\|^{r_{1}+1}\leq\left\|x^{\ast}-x_{0}\right\|\leq r,

i.e., $x_{1}\in S$ .

Assume now that $x_{1},\ldots,x_{n}\in S$ and denote

(13)

\rho_{i}=\big(\tfrac{MmL_{1}}{r_{1}!}\big)^{\frac{1}{r_{1}}}\left\|x^{\ast}-x_% {i}\right\|,\quad i=0,1,\ldots,n.

Relations a) and b) imply $\rho_{0}<1$ , while (12) attracts

(14)

\rho_{1}\leq\rho_{0}^{p}.

Assume now that

(15)

\rho_{i+1}\leq\rho_{i}^{p},\quad i=0,\ldots,n-1.

From (14) and (15) we get

\rho_{i}\leq\rho_{0}^{p^{i}},\quad i=1,\ldots,n.

We prove now that $x_{n+1}\in S$ and $\rho_{n+1}\leq\rho_{n}^{p}$ . Applying the Taylor formula and taking into account the hypotheses,

(16)

\left\|\varphi_{1}\left(x_{n}\right)-\varphi_{1}\left(x^{\ast}\right)\right\|% \leq\tfrac{L_{1}}{r_{1}!}\left\|x_{n}-x^{\ast}\right\|^{r_{1}}.

The induction hypotheses also imply

(17)

\left\|x_{n}-x^{\ast}\right\|=\tfrac{\rho_{n}}{\left(\tfrac{MmL_{1}}{r_{1}!}% \right)^{\frac{1}{r_{1}}}}\leq\tfrac{\rho_{0}^{p^{n}}}{\left(\frac{MmL_{1}}{% \left(r_{1}!\right)}\right)^{\frac{1}{r_{1}}}}=\left\|x^{\ast}-x_{0}\right\|.

Replacing (17) in (16) and taking into account b) leads to

\left\|\varphi_{1}\left(x_{n}\right)-x^{\ast}\right\|\leq\tfrac{L_{1}}{r_{1}!}% \left\|x^{\ast}-x_{0}\right\|^{r_{1}}\leq r,

which shows that $\varphi_{1}\left(x_{n}\right)\in S$ .

The fact that $x_{n}$ , $\varphi_{1}\left(x_{n}\right)$ , $x^{\ast}\in S$ implies

	$\displaystyle\theta=F\left(x^{\ast}\right)=$	$\displaystyle F\left(x_{n}\right)+\left[x_{n},\varphi_{1}\left(x_{n}\right);F% \right]\left(x^{\ast}-x_{n}\right)$
		$\displaystyle+\left[x^{\ast},x_{n},\varphi_{1}\left(x_{n}\right);F\right]\left% (x^{\ast}-\varphi_{1}\left(x_{n}\right)\right)\left(x^{\ast}-x_{n}\right)$

whence

(18)

\left\|x^{\ast}-x_{n+1}\right\|\leq\tfrac{MmL_{1}}{r_{1}!}\left\|x^{\ast}-x_{n% }\right\|^{p}.

Denoting $\rho_{n+1}=\big(\frac{MmL_{1}}{r_{1}!}\big)^{\frac{1}{r_{1}}}\left\|x^{\ast}-x% _{n+1}\right\|$ , then by (18) we get

(19)

\rho_{n+1}\leq\rho_{n}^{p}\leq\rho_{0}^{p^{n+1}}.

It remains to show that $x_{n+1}\in S$ , which follows by (19) and (18):

\left\|x^{\ast}-x_{n+1}\right\|\leq\frac{\rho_{0}^{p^{n+1}}}{\big(\frac{MmL_{1% }}{r_{1}!}\big)^{\frac{1}{r_{1}}}}<\frac{\rho_{0}}{\big(\frac{MmL_{1}}{r_{1}}% \big)^{\frac{1}{r_{1}}}}\leq\left\|x^{\ast}-x_{0}\right\|\leq r.

Relation (19) implies conclusion (jj₁). ∎

We obtain the following result regarding the Aitken method.

Theorem 2.2.

Assume that the mappings $\varphi_{1}$ , $\varphi_{2}$ obey i) and (7), resp. ii) and (8), the mapping $F$ obeys i₁), i₂) and the initial approximation $x_{0}\in S$ is chosen such that

a^′)

$\frac{L_{1}}{r_{1}!}\left\|x^{\ast}-x_{0}\right\|^{r_{1}-1}\leq 1;$
b^′)

$\frac{L_{2}}{r_{2}!}\left\|x^{\ast}-x_{0}\right\|^{r_{2}-1}\leq 1;$
c^′)

$Mm\left\|x^{\ast}-x_{0}\right\|<1.$

Then the sequence generated by (5) remains in $S$ , converges to $x^{\ast}$ and, moreover, the following relations are true:

j₂)

$\left\|x_{n}-x^{\ast}\right\|\leq\big(\frac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\big)^{% \frac{1}{1-q}}\rho_{0}^{q^{n}},\quad n=1,2,\ldots,$ where

$\rho_{0}=\big(\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}\left\|x^% {\ast}-x_{0}\right\|<1$

and $q=r_{1}+r_{2};$
jj₂)

$\lim_{n\rightarrow\infty}x_{n}=x^{\ast}$ .

Proof.

From i), ii), (7) and (8) it results

(20)

\left\|x^{\ast}-\varphi_{1}\left(x_{0}\right)\right\|\leq\tfrac{L_{1}}{r_{2}!}% \left\|x^{\ast}-x_{0}\right\|^{r_{1}},

whence, by a^′) it follows that $\varphi_{1}\left(x_{0}\right)\in S$ . Analogously, for $\varphi_{2}$ we get

(21)

\left\|x^{\ast}-\varphi_{2}\left(x_{0}\right)\right\|\leq\tfrac{L_{2}}{r_{2}!}% \left\|x^{\ast}-x_{0}\right\|^{r_{2}},

i.e., $\varphi_{2}\left(x_{0}\right)\in S.$

The Newton identity for $F$ ,

	$\displaystyle\theta=F\left(x^{\ast}\right)=$	$\displaystyle F\left(\varphi_{1}\left(x_{0}\right)\right)+\left[\varphi_{1}% \left(x_{0}\right),\varphi_{2}\left(x_{0}\right);F\right]\left(x^{\ast}-% \varphi_{1}\left(x_{0}\right)\right)$
		$\displaystyle+\left[x^{\ast},\varphi_{1}\left(x_{0}\right),\varphi_{2}\left(x_% {0}\right);F\right]\left(x^{\ast}-\varphi_{2}\left(x_{0}\right)\right)\left(x^% {\ast}-\varphi_{1}\left(x_{0}\right)\right)$

by (5) for $n=0$ , (20), (21), implies

(22)		$\displaystyle\left\\|x_{1}-x^{\ast}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-\varphi_{2}\left(x_{0}\right)\right\\|\left\\|x^% {\ast}-\varphi_{1}\left(x_{0}\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\left\\|x^{\ast}-x_{0}\right\\|^{% r_{1}+r_{2}}.$

Denoting $r_{1}+r_{2}=q$ and

(23)

\rho_{k}=\big(\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}\left\|x^% {\ast}-x_{k}\right\|,\quad k=0,1,

then, by (22) we get

(24)

\rho_{1}\leq\rho_{0}^{q}.

From a^′), b^′) and c^′) we obtain that $x_{1}\in S$ and

(25)

\rho_{0}<1.

The fact that $x_{1}\in S$ is implied by relations (24) and (25):

(26)

\left\|x_{1}-x^{\ast}\right\|\leq\frac{\rho_{0}^{q}}{\big(\frac{MmL_{1}L_{2}}{% r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}}<\frac{\rho_{0}}{\big(\frac{MmL_{1}L_{2}}{r% _{1}!r_{2}!}\big)^{\frac{1}{q-1}}}=\left\|x_{0}-x^{\ast}\right\|\leq r.

It remains to show that $\varphi_{1}\left(x_{1}\right)$ , $\varphi_{2}\left(x_{1}\right)\in S$ . Using a^′) and (26), we have

	$\displaystyle\left\\|x^{\ast}-\varphi_{1}\left(x_{1}\right)\right\\|\leq$	$\displaystyle\tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{1}\right\\|^{r_{1}}$
	$\displaystyle\leq$	$\displaystyle\tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{1}}$
	$\displaystyle\leq$	$\displaystyle\tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{1}-1}\left% \\|x^{\ast}-x_{0}\right\\|$
	$\displaystyle\leq$	$\displaystyle r$

and, analogously, (26) and b^′) imply

\left\|x^{\ast}-\varphi_{2}\left(x_{1}\right)\right\|\leq\tfrac{L_{2}}{r_{2}!}% \left\|x^{\ast}-x_{1}\right\|^{r_{2}}\leq\tfrac{L_{2}}{r_{2}!}\left\|x^{\ast}-% x_{0}\right\|^{r_{2}}\leq r.

Assume $x_{0},x_{1},\ldots,x_{k}\in S$ and $\varphi_{i}\left(x_{s}\right)\in S,\ i=1,2,$ $s=0,\ldots,k$ .

Denote

(27)

\rho_{i}=\big(\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}\left\|x^% {\ast}-x_{i}\right\|,\quad i=1,\ldots,k

and assume that

(28)

\rho_{i+1}\leq\rho_{i}^{q},\quad i=1,\ldots,k-1.

Relations (28), together with (24) show that the following inequalities are verified:

(29)

\rho_{i}\leq\rho_{0}^{q^{i}},\quad i=1,\ldots,k.

We show now that $x_{k+1}\in S$ . Similarly to (22), one immediately deduces that

(30)

\left\|x_{k+1}-x^{\ast}\right\|\leq\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\left\|x^% {\ast}-x_{k}\right\|^{q}.

Denoting

(31)

\rho_{k+1}=\big(\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}\left\|% x^{\ast}-x_{k}\right\|,

then by (30) and (29) we deduce

(32)

\rho_{k+1}\leq\rho_{0}^{q^{k+1}},

i.e., (29) holds also for $i=k+1$ .

From (30), (31) and (32) we get

(33)

\left\|x_{k+1}-x^{\ast}\right\|\leq\frac{\rho_{0}^{q^{k+1}}}{\big(\frac{MmL_{1% }L_{2}}{r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}}\leq\frac{\rho_{0}}{\big(\frac{MmL_% {1}L_{2}}{r_{1}!r_{2}!}\big)^{\frac{1}{q-1}}}\leq\left\|x^{\ast}-x_{0}\right\|% \leq r,

i.e., $x_{k+1}\in S.$ It remains to prove that $\varphi_{1}\left(x_{k+1}\right)$ , $\varphi_{2}\left(x_{k+1}\right)\in S$ .

The Taylor formula leads to the relations

\left\|x^{\ast}-\varphi_{1}\left(x_{k+1}\right)\right\|\leq\tfrac{L_{1}}{r_{1}% !}\left\|x^{\ast}-x_{k+1}\right\|^{r_{1}}

and

\left\|x^{\ast}-\varphi_{2}\left(x_{k+1}\right)\right\|\leq\tfrac{L_{2}}{r_{2}% !}\left\|x^{\ast}-x_{k+1}\right\|^{r_{2}}.

By (33), we get $\left\|x^{\ast}-x_{k+1}\right\|\leq\left\|x^{\ast}-x_{0}\right\|$ and so, from a^′) and b^′),

\left\|x^{\ast}-\varphi_{1}\left(x_{k+1}\right)\right\|\leq\tfrac{L_{1}}{r_{1}% !}\left\|x^{\ast}-x_{0}\right\|^{r_{1}}\leq r

and, analogously

\left\|x^{\ast}-\varphi_{2}\left(x_{k+1}\right)\right\|\leq\tfrac{L_{2}}{r_{2}% !}\left\|x^{\ast}-x_{0}\right\|^{r_{1}}\leq r

i.e., $\varphi_{1}\left(x_{k+1}\right),$ $\varphi_{2}\left(x_{k+1}\right)\in S.$

According to the induction principle, relations (29) are true for all $i\in\mathbb{N},$ so

\left\|x_{n}-x^{\ast}\right\|\leq\tfrac{1}{\big(\frac{MmL_{1}L_{2}}{r_{1}!r_{2% }!}\big)^{\frac{1}{q-1}}}\rho_{0}^{q^{n}}

whence, since $\rho_{0}<1$ , $\lim_{n\rightarrow\infty}\left\|x_{n}-x^{\ast}\right\|=0,$ i.e., $\lim_{n\rightarrow\infty}x_{n}=x^{\ast}.$ ∎

Finally, the following result holds for the Aitken–Steffensen method.

Theorem 2.3.

Under the hypotheses of Theorem 2.2, the sequence $\left(x_{n}\right)_{n\geq 0}$ , generated by (6) remains in the ball $S$ , and converge to $x^{\ast}$ such that:

j₃)

$\left\|x^{\ast}-x_{n}\right\|\leq L^{\frac{1}{1-s}}\rho_{0}^{s^{n}}$ ,
where $\rho_{0}=L^{\frac{1}{s-1}}\left\|x^{\ast}-x_{0}\right\|$ , $L=mM\big(\frac{L_{1}}{r_{1}!}\big)^{r_{2}+1}\frac{L_{2}}{r_{2}!}$ , $n=0,1,\ldots,$ and $s=r_{1}r_{2}+r_{1};$
jj₃)

$\lim_{n\rightarrow\infty}x_{n}=x^{\ast}$ .

{proof*}

Assume that $x_{0}\in S$ verifies a^′)–c^′). We show first that $\varphi_{1}\left(x_{0}\right)$ , $\varphi_{2}\left(\varphi_{1}\left(x_{0}\right)\right)\in S$ . For $\varphi_{1}$ we have

(34)

\left\|x^{\ast}-\varphi_{1}\left(x_{0}\right)\right\|\leq\tfrac{L_{1}}{r_{1}!}% \left\|x^{\ast}-x_{0}\right\|^{r_{1}}\leq\left\|x^{\ast}-x_{0}\right\|\leq r

i.e., $\varphi_{1}\left(x_{0}\right)\in S$ . Next, taking into account (34), we get

	$\displaystyle\left\\|x^{\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{0}\right)% \right)\right\\|\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\left\\|x^{\ast}-\varphi_{1}\left(x_{0}\right% )\right\\|$
	$\displaystyle\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\tfrac{L_{1}^{r_{2}}}{\left(r_{1}!\right)^{r% _{2}}}\left\\|x^{\ast}-x_{0}\right\\|^{r_{1}r_{2}}$
	$\displaystyle=$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\big[\tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_% {0}\right\\|^{r_{1}-1}\big]^{r_{2}}\left\\|x^{\ast}-x_{0}\right\\|^{r_{2}}$
	$\displaystyle\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{2}}$
	$\displaystyle\leq$	$\displaystyle\left\\|x^{\ast}-x_{0}\right\\|$
	$\displaystyle\leq$	$\displaystyle r.$

We prove now that $x_{1}\in S.$ Analogously to (21), we get

(35)		$\displaystyle\left\\|x_{1}-x^{\ast}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-\varphi_{1}\left(x_{0}\right)\right\\|\left\\|x^% {\ast}-\varphi_{2}(\varphi_{1}\left(x_{0}\right))\right\\|$
	$\displaystyle\leq$	$\displaystyle Mm\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}+1}\tfrac{L_{2}}{r_{2}!}% \left\\|x^{\ast}-x_{0}\right\\|^{r_{1}r_{2}+r_{1}}.$

As it can be easily noticed, the previous relation may also be written as

(36)		$\displaystyle\left\\|x_{1}-x^{\ast}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-x_{0}\right\\|\big[\tfrac{L_{1}}{r_{1}!}\left\\|% x^{\ast}-x_{0}\right\\|^{r_{1}-1}\big]^{r_{2}}$
		$\displaystyle\cdot\tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{1}-1}% \tfrac{L_{2}}{r_{2}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{2}-1}\left\\|x^{\ast}-x_% {0}\right\\|,$

whence, by a^′)–c^′), it follows that $\left\|x_{1}-x^{\ast}\right\|\leq r,$ i.e., $x_{1}\in S.$ Further, denote $s=r_{1}r_{2}+r_{1},$ $L=Mm\big(\frac{L_{1}}{r_{1}!}\big)^{r_{2}+1}\frac{L_{2}}{r_{2}!},$ and so inequality (35) becomes

\left\|x_{1}-x^{\ast}\right\|\leq L\left\|x^{\ast}-x_{0}\right\|^{s},

and, for $L^{\frac{1}{s-1}}\left\|x^{\ast}-x_{0}\right\|=\rho_{0},$ it reads as

(37)

\rho_{1}\leq\rho_{0}^{s},

with $\rho_{1}=L^{\frac{1}{s-1}}\left\|x^{\ast}-x_{1}\right\|.$

Next, we show that $\varphi_{1}\left(x_{1}\right)$ , $\varphi_{2}\left(\varphi_{1}\left(x_{1}\right)\right)\in S.$ From (36) we have that

(38)

\left\|x^{\ast}-x_{1}\right\|\leq\left\|x^{\ast}-x_{0}\right\|.

For $\varphi_{1}\left(x_{1}\right)$ we obtain

\left\|x^{\ast}-\varphi_{1}\left(x_{1}\right)\right\|\leq\tfrac{L_{1}}{r_{1}!}% \left\|x^{\ast}-x_{1}\right\|^{r_{1}}\leq\tfrac{L_{1}}{r_{1}!}\left\|x^{\ast}-% x_{0}\right\|^{r_{1}}\leq r,

while for $\varphi_{2}\left(\varphi_{1}\left(x_{1}\right)\right)$ we deduce

	$\displaystyle\left\\|x^{\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{1}\right)% \right)\right\\|\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}}\left% \\|x^{\ast}-x_{1}\right\\|^{r_{1}r_{2}}$
	$\displaystyle=$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\left\\|x^{\ast}-x_{1}\right\\|^{r_{2}-1}\big[% \tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{1}\right\\|^{r_{1}-1}\big]^{r_{2}}\left% \\|x^{\ast}-x_{1}\right\\|$

whence, taking into account (38) and a^′), b^′), it follows

\left\|x^{\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{1}\right)\right)\right\|\leq r

i.e., $\varphi_{2}\left(\varphi_{1}\left(x_{1}\right)\right)\in S.$

Assume now that $x_{0},\ldots,x_{k}\in S,$ $\varphi_{1}\left(x_{0}\right),\ldots,\varphi_{1}\left(x_{k}\right)\in S,$ $\varphi_{2}\left(\varphi_{1}\left(x_{0}\right)\right),\ldots,$ $\varphi_{2}\left(\varphi_{1}\left(x_{k}\right)\right)\in S$ . Denote $\rho_{i}=L^{\frac{1}{s-1}}\left\|x^{\ast}-x_{i}\right\|,$ $i=0,\ldots,k$ and also suppose that

(39)

\rho_{i+1}\leq\rho_{i}^{s},\quad i=0,\ldots,k-1

which, by (37), becomes

(40)

\rho_{i}\leq\rho_{0}^{s^{i}},\quad i=1,\ldots,k.

We show now that $x_{k+1}\in S.$ Using the hypotheses of the theorem and the Newton identity, it can be easily shown that

	$\displaystyle\left\\|x^{\ast}-x_{k+1}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-\varphi_{1}\left(x_{k}\right)\right\\|\left\\|x^% {\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{k}\right)\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle Mm\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}+1}\tfrac{L_{2}}{r_{2}!}% \left\\|x^{\ast}-x_{0}\right\\|^{r_{1}r_{2}+r_{1}}$

i.e., by denoting $\rho_{k+1}L^{\frac{1}{s-1}}\left\|x^{\ast}-x_{k+1}\right\|,$

\rho_{k+1}\leq\rho_{k}^{s}.

By (40), this leads to

\rho_{k+1}\leq\rho_{0}^{s^{k+1}},

and since $\rho_{0}<1,$ we get

\rho_{k+1}\leq\rho_{0}.

Further,

\left\|x_{k+1}-x^{\ast}\right\|\leq\left\|x_{0}-x^{\ast}\right\|\leq r,

which shows that $x_{k+1}\in S.$ Now, we show that $\varphi_{1}\left(x_{k+1}\right),\varphi_{2}\left(\varphi_{1}\left(x_{k+1}% \right)\right)\in S.$ First, taking into account a^′),

\left\|x^{\ast}-\varphi_{1}\left(x_{k+1}\right)\right\|\leq\tfrac{L_{1}}{r_{1}% !}\left\|x^{\ast}-x_{k}\right\|^{r_{1}}\leq\tfrac{L_{1}}{r_{1}!}\left\|x^{\ast% }-x_{0}\right\|^{r_{1}}\leq r,

and, finally,

	$\displaystyle\left\\|x^{\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{k+1}\right)% \right)\right\\|\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}}\left% \\|x^{\ast}-x_{k+1}\right\\|^{r_{1}r_{2}}$
	$\displaystyle\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}}\left% \\|x^{\ast}-x_{0}\right\\|^{r_{1}r_{2}}$
	$\displaystyle\leq$	$\displaystyle r.\alignqed$

Inequalities j₁), j₂), j₃) from this conclusions of Theorems 2.1, 2.2, resp. 2.3 characterize the convergence orders of the methods (4), (5), resp. (6).

The numbers $r_{1}$ , resp. $r_{2}$ represent as we have already specified, the convergence orders of the iteration methods given by (9), resp. (10).

We also notice the following facts.

Remark 2.1.

If $r_{1}=r_{2}=1$ , then the three studied methods have the same convergence order: $p=q=s=2.$

Remark 2.2.

Regarding method (6), we may also consider the following iterations instead:

(41)

x_{n+1}=\varphi_{2}\left(x_{n}\right)-\left[\varphi_{2}\left(x_{n}\right),% \varphi_{1}\left(\varphi_{2}\left(x_{n}\right)\right);F\right]^{-1}F\left(% \varphi_{2}\left(x_{n}\right)\right)

having the same convergence order $r_{1}r_{2}+r_{2}$ . Consequently, if $r_{2}>r_{1}$ , then (41) is preferred instead of (6).

References

[1]
[2] Argyros, I. K., A new convergence theorem for the Steffensen method in Banach space and applications, Rev. Anal. Numér. Théor. Approx., 29, no. 2, pp. 119–127, 2000.
[3] Argyros, I. K., An error analysis for the Steffensen method under generalized Zabrejko–Nguen-type assumptions, Rev. Anal. Numér. Théor. Approx., 25, nos. 1–2, pp. 11–22, 1996.
[4] Argyros, I. K., Polynomial Operator Equations in Abstract Spaces and Applications, CRC Press LLC, Boca Raton, Florida, 1998.
[5] Argyros, I. K. and Szidarovszky, F., The theory and Applications of Iteration Methods, C.R.C. Press, Boca Raton, Florida, 1993.
[6] Balǎzs, M. and Goldner, G., On the approximate solutions of equations in Hilbert space by a Steffensen-type method, Rev. Anal. Numér. Théor. Approx., 17, no. 1, pp. 19–23, 1998.
[7] Cătinaş, E., On some Steffensen-type iterative methods for a class of nonlinear equations, Rev. Anal. Numér. Théor. Approx., 24, nos. 1–2, pp. 37–43, 1995.
[8] Cătinaş, E. and Păvăloiu, I., On some interpolatory iterative methods for the second degree polynomial operators (I), Rev. Anal. Numér. Théor. Approx., 27, no. 1, pp. 33–45, 1998.
[9] Cătinaş, E. and Păvăloiu, I., On some interpolatory iterative methods for the second degree polynomial operators (II), Rev. Anal. Numér. Théor. Approx., 28, no. 2, pp. 133–144, 1999.
[10] Păvăloiu, I., Introduction to the Theory of Approximating the Solutions of Equations, Ed. Dacia, Cluj, 1986 (in Romanian).
[11] Păvăloiu, I., Optimal efficiency index for iterative methods of interpolatory type, Computer Science Journal of Moldova, 5, 1 (13), pp. 20–43, 1997.
[12] Păvăloiu, I., Approximation of the roots of equations by Aitken–Steffensen-type monotonic sequence, Calcolo, 32, nos. 1–2, pp. 69–82, 1995.
[13] Păvăloiu, I., Sur la méthode de Steffensen pour la résolution des équations opèrationnelles non linéaires, Rev. Roum. Math. Pure et Appl., XIII, no. 6, pp. 857–861, 1968.
[14] Păvăloiu, I., Sur une généralisation de la methode de Steffensen, Rev. Anal. Numér. Théor. Approx., 21, no. 1, pp. 56–65, 1992.
[15] 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.
[16] Păvăloiu, I., On the monotonicity of the sequence of approximations obtained by Steffensen method, Mathematica (Cluj), 35 (58), pp. 171–176, 1993.
[17] Păvăloiu, I., On a Halley–Steffensen method for approximating the solutions of scalar equations, Rev. Anal. Numér. Théor. Approx., 30, no. 1, pp. 69–74, 2001.
[18] Popoviciu, T., Sur la délimitation de l’erreur dans l’approximation des racines d’une équation par interpolation linéaire ou quadratique, Rev. Roumaine Math. Pures Appl., 13, pp. 75–78, 1968.
[19]

(22)		$\displaystyle\left\\|x_{1}-x^{\ast}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-\varphi_{2}\left(x_{0}\right)\right\\|\left\\|x^% {\ast}-\varphi_{1}\left(x_{0}\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle\tfrac{MmL_{1}L_{2}}{r_{1}!r_{2}!}\left\\|x^{\ast}-x_{0}\right\\|^{% r_{1}+r_{2}}.$

(35)		$\displaystyle\left\\|x_{1}-x^{\ast}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-\varphi_{1}\left(x_{0}\right)\right\\|\left\\|x^% {\ast}-\varphi_{2}(\varphi_{1}\left(x_{0}\right))\right\\|$
	$\displaystyle\leq$	$\displaystyle Mm\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}+1}\tfrac{L_{2}}{r_{2}!}% \left\\|x^{\ast}-x_{0}\right\\|^{r_{1}r_{2}+r_{1}}.$

(36)		$\displaystyle\left\\|x_{1}-x^{\ast}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-x_{0}\right\\|\big[\tfrac{L_{1}}{r_{1}!}\left\\|% x^{\ast}-x_{0}\right\\|^{r_{1}-1}\big]^{r_{2}}$
		$\displaystyle\cdot\tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{1}-1}% \tfrac{L_{2}}{r_{2}!}\left\\|x^{\ast}-x_{0}\right\\|^{r_{2}-1}\left\\|x^{\ast}-x_% {0}\right\\|,$

	$\displaystyle\left\\|x^{\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{1}\right)% \right)\right\\|\leq$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}}\left% \\|x^{\ast}-x_{1}\right\\|^{r_{1}r_{2}}$
	$\displaystyle=$	$\displaystyle\tfrac{L_{2}}{r_{2}!}\left\\|x^{\ast}-x_{1}\right\\|^{r_{2}-1}\big[% \tfrac{L_{1}}{r_{1}!}\left\\|x^{\ast}-x_{1}\right\\|^{r_{1}-1}\big]^{r_{2}}\left% \\|x^{\ast}-x_{1}\right\\|$

	$\displaystyle\left\\|x^{\ast}-x_{k+1}\right\\|\leq$	$\displaystyle Mm\left\\|x^{\ast}-\varphi_{1}\left(x_{k}\right)\right\\|\left\\|x^% {\ast}-\varphi_{2}\left(\varphi_{1}\left(x_{k}\right)\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle Mm\big(\tfrac{L_{1}}{r_{1}!}\big)^{r_{2}+1}\tfrac{L_{2}}{r_{2}!}% \left\\|x^{\ast}-x_{0}\right\\|^{r_{1}r_{2}+r_{1}}$

On the convergence order of some Aitken-Steffensen type methods

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

On the convergence order
of some Aitken–Steffensen type methods^∗

Abstract.

1. Introduction

2. Local convergence

Theorem 2.1.

Proof.

Theorem 2.2.

Proof.

Theorem 2.3.

Remark 2.1.

Remark 2.2.

References

Related Posts

On the convergence order of some Aitken-Steffensen type methods

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

On the convergence order of some Aitken–Steffensen type methods∗

Abstract.

1. Introduction

2. Local convergence

Theorem 2.1.

Proof.

Theorem 2.2.

Proof.

Theorem 2.3.

Remark 2.1.

Remark 2.2.

References

Related Posts

On the convergence order
of some Aitken–Steffensen type methods^∗