Buletinul Ştiinţific al Universităţii din Baia Mare

Seria B, Matematică-Informatică, vol. XIII (1997), 107–116

ON THE CONVERGENCE ORDER
OF THE MULTISTEP METHODS

Ion Pǎvǎloiu

1. Introduction

In this paper we analyse some aspects concerning the convergence order of the iterative methods of interpolatory type for solving scalar equations. A unitary approach to these methods will enable us to analyse them and then to select among them those with the optimal convergence order.

2. Convergence order

Denote $I=\left[a,b\right],\;\,a,b\in{\mathbb{R}},\,a<b$ and consider the equation

(1)

f\left(x\right)=0

where $f:I\rightarrow{\mathbb{R}}$ . For the sake of the simplicity we shall suppose in the following that equation (1) has a unique solution $\bar{x}\in I$ . Let $g:I\rightarrow I$ be a function for which $\bar{x}$ is the unique fixed point on $I$ .

For the approximation of the solution of (1) there is generally considered, under certain conditions, a sequence $\left(x_{p}\right)_{p\geq 0}$ generated by:

(2)

x_{s+1}=g\left(x_{s}\right),\quad s=0,1,\ldots,\quad x_{0}\in I.

More generally, if $G:I^{k}\rightarrow I$ is a function of $k$ variables for which the restriction to the diagonal of the set $I^{k}$ coincides with $g,$ namely

G\left(x,x,\ldots,x\right)=g\left(x\right),\quad\text{for all }x\in I\text{,}

then there is considered the following iterative method:

(3)

x_{s+k}=G\left(x_{s},x_{s+1},\ldots,x_{s+k-1}\right),\quad s=0,1,\ldots,\;\;x_% {0},x_{1},\ldots,x_{k-1}\in I.

The convergence of the sequence $\left(x_{p}\right)_{p\geq 0}$ generated by (2) or (3) depends on certain properties of the functions $f$ and $g$ , respectively $G$ . The amount of time needed to obtain a convenient approximation $x_{p}$ of $\bar{x}$ depends both on the convergence order of the sequence $\left(x_{p}\right)_{p\geq 0}$ and on the amount of elementary operations that must be performed by the computer at each iteration step. In this paper we shall study only the first aspect of this problem, i.e. we shall deal with the convergence order.

We shall adopt as the convergence order a definition a little more generally then the one given by Ostrowski [3].

Consider an arbitrary sequence $\left(x_{p}\right)_{p\geq 0}$ satisfying, together with $f$ and $g$ , the following conditions:

a)

$x_{s}\in I$ and $g\left(x_{s}\right)\in I$ for $s=0,1,\ldots;$
b)

the sequences $\left(x_{p}\right)_{p\geq 0}$ and $\left(g(x_{p})\right)_{p\geq 0}$ converge to $\bar{x},$ the solution of equation (1);
c)

there exists $\,m\in{\mathbb{R}},\,m>0$ such that $0<\left|[x,y;f]\right|\leq m$ , for all $x,y\in I$ , where we have denoted by $\left[x,y;f\right]$ the first order divided difference of $f$ at the points $x$ and $y$ ;
d)

$f$ is differentiable at $\bar{x}.$

Definition 2.1.

The sequence $\left(x_{p}\right)_{p\geq 0}$ has the convergence order $\omega\in{\mathbb{R}}$ , $\omega\geq 1$ , with respect to the function $g$ , if there exists the limit:

(4)

\alpha=\lim_{p\rightarrow\infty}\frac{\ln\left|g\left(x_{p}\right)-\bar{x}% \right|}{\ln\left|x_{p}-\bar{x}\right|}

and $\alpha=\omega$ .

Remark 2.1.

If the elements of $\left(x_{p}\right)_{p\geq 0}$ are generated by the iterative method (2), then the convergence order defined above coincides with the one defined in [3]. ∎

For the determination of the convergence order of some classes of iterative methods we shall need in the following two lemmas:

Lemma 2.1.

If the sequence $\left(x_{p}\right)_{p\geq 0}$ and the functions $f$ and $g$ satisfy the properties a)–d) then the necessary and sufficient condition for the sequence $\left(x_{p}\right)_{p\geq 0}$ to have the convergence order $\omega\in{\mathbb{R}},\,\omega\geq 1$ with respect to the function $g$ is that the following limit to exist:

(5)

\lim_{p\rightarrow\infty}\frac{\ln\left|f\left(g\left(x_{p}\right)\right)% \right|}{\ln\left|f\left(x_{p}\right)\right|}=\beta,

and $\beta=\omega.$

Proof.

Supposing that one of the relations (4) or (5) holds and, taking into account the properties a)–d), we obtain:

	$\displaystyle\alpha$	$\displaystyle=$	$\displaystyle\lim\dfrac{\ln\left\|g\left(x_{p}\right)-\bar{x}\right\|}{\ln\left\|% x_{p}-\bar{x}\right\|}=\lim\dfrac{\ln\left\|f\left(g\left(x_{p}\right)\right)% \right\|-\ln\left\|\left[g\left(x_{p}\right),\bar{x};f\right]\right\|}{\ln\left\|f% \left(x_{p}\right)\right\|-\ln\left\|\left[x_{p},\bar{x};f\right]\right\|}$
		$\displaystyle=$	$\displaystyle\lim\dfrac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|}{\ln% \left\|f\left(x_{p}\right)\right\|}\cdot\frac{1-\dfrac{\ln\left\|\left[g\left(x_{% p}\right),\bar{x};f\right]\right\|}{\ln\left\|f\left(g\left(x_{p}\right)\right)% \right\|}}{1-\dfrac{\ln\left\|\left[x_{p},\bar{x};f\right]\right\|}{\ln\left\|f% \left(x_{p}\right)\right\|}}=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)% \right)\right\|}{\ln\left\|f\left(x_{p}\right)\right\|}=\beta.$

∎

Lemma 2.2.

If $\left(u_{p}\right)_{p\geq 0}$ is a sequence of real numbers that satisfies:

i.

the sequence $\left(u_{p}\right)_{p\geq 0}$ is convergent and $\lim\,u_{p}=0;$
ii.

there exist the nonnegative numbers $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ and a bounded sequence $\left(c_{p}\right)_{p\geq 0},\,c_{p}>0,\,\,p=0,1,\ldots$ for which $\,\inf\left\{c_{p}\right\}>0$ such that

(6) $u_{s+n+1}=c_{s}u_{s}^{\alpha_{1}}u_{s+1}^{\alpha_{2}}\ldots u_{s+n}^{\alpha_{n% +1}},\qquad s=0,1,\ldots;$
iii.

the sequence $\left(\frac{\ln\,u_{p+1}}{\ln\,u_{p}}\right)_{p\geq 0}$ is convergent and $\lim\frac{\ln\,u_{p+1}}{\ln\,u_{p}}=\omega.$

Then $\omega$ is the positive root of the equation:

t^{n+1}-\alpha_{n+1}t^{n}-\alpha_{n}t^{n-1}-\ldots-\alpha_{2}t-\alpha_{1}=0.

Proof.

From (6) we obtain

\lim_{s\rightarrow\infty}\frac{\ln u_{n+s+1}}{\ln u_{n+s}}=\lim_{s\rightarrow% \infty}\frac{\ln c_{s}}{\ln u_{n+s}}+\sum_{i=0}^{n}\alpha_{i+1}\lim_{s% \rightarrow\infty}\frac{\ln u_{s+i}}{\ln u_{s+n}}.

Taking into account the equalities

\lim_{s\rightarrow\infty}\frac{\ln c_{s}}{\ln u_{n+s}}=0\text{ and }\lim_{s% \rightarrow\infty}\frac{\ln u_{i+s}}{\ln u_{n+s}}=\tfrac{1}{\omega^{n-i}},% \qquad i=\overline{0,n}

we obviously have

\omega=\sum\limits_{i=0}^{n}\alpha_{i+1}\tfrac{1}{\omega^{n-i}},

i.e.,

\omega^{n+1}-\alpha_{n+1}\omega^{n}-\alpha_{n}\omega^{n-1}-\ldots-\alpha_{2}% \omega-\alpha_{1}=0.

∎

In the following we shall consider the equations:

(7)

P\left(t\right)=t^{n+1}-\alpha_{n+1}t^{n}-\alpha_{n}t^{n-1}-\ldots-\alpha_{2}t% -\alpha_{1}=0;

(8)

Q\left(t\right)=t^{n+1}-\alpha_{1}t^{n}-\alpha_{2}t^{n-1}-\ldots-\alpha_{n}t-% \alpha_{n+1}=0;

(9)

R\left(t\right)=t^{n+1}-\alpha_{i_{1}}t^{n}-\alpha_{i_{2}}t^{n-1}-\ldots-% \alpha_{i_{n}}t-\alpha_{i_{n+1}}=0,

where we shall suppose that $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ satisfy

(10)

\alpha_{i}\geq 0\quad i=\overline{1,n+1},\quad\textstyle\sum\limits_{i=1}^{n+1% }\alpha_{i}>1

(11)

\alpha_{n+1}\geq\alpha_{n}\geq\ldots\geq\alpha_{2}\geq\alpha_{1},

$i_{2},$ $i_{2},\ldots,i_{n+1}$ being an arbitrary permutation of the numbers $1,2,\ldots,n+1$ .

Lemma 2.3.

If $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ satisfy conditions (10) then any of the equations (9) has a unique solution $\omega>1$ . Moreover, if (11) holds and we denote by $a, b, c$ the positive solutions of (7), (8) and (9) then

(12)

1<b\leq c\leq a,

i.e. equation (7) has the greatest positive solution.

Proof.

Consider one of the $\left(n+1\right)!$ equations of the form (9), denote by $s$ the greatest natural number for which $\alpha_{i_{s}}\neq 0,$ i.e. $\alpha_{i_{s+1}}=\alpha_{i_{s+2}}=\ldots=\alpha_{i_{n+1}}=0$ and consider the function

\varphi\left(t\right)=\tfrac{R\left(t\right)}{t^{n-s+1}}.

We have $\varphi\left(1\right)=1-\alpha_{i_{1}}-\alpha_{i_{2}}-\ldots-\alpha_{i_{s}}<0$ and $\lim\limits_{t\rightarrow\infty}\varphi\left(t\right)=+\infty,$ whence it follows that the equation $R\left(t\right)=0$ has a solution greater than $1$ . Since the function $\psi\left(t\right)=\tfrac{R\left(t\right)}{t^{n+1}}$ is increasing in the variable $\tau=\frac{1}{t}$ , $\tau>0$ it follows that this solution is unique.

In order to prove (12) it will suffice to show that $R\left(b\right)\leq 0$ and $R\left(a\right)\geq 0$ . Indeed, since $Q\left(b\right)=0$ , we have:

	$\displaystyle R\left(b\right)=$	$\displaystyle R\left(b\right)-Q\left(b\right)$
	$\displaystyle=$	$\displaystyle\left(a_{1}-a_{i_{1}}\right)b^{n}+\left(a_{2}-a_{i_{2}}\right)b^{% n-1}+\ldots+\left(a_{n}-a_{i_{n}}\right)b+a_{n+1}-a_{i_{n+1}}$
	$\displaystyle=$	$\displaystyle\left(b-1\right)[\left(a_{1}-a_{i_{1}}\right)b^{n-1}+\left(a_{1}+% a_{2}-a_{i_{1}}-a_{i_{2}}\right)b^{n-2}+\ldots+$
		$\displaystyle+\left(a_{1}+a_{2}+\ldots+a_{n-1}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i% _{n-1}}\right)b+$
		$\displaystyle+\left(a_{1}+a_{2}+\ldots+a_{n}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{% n}}\right)],$

whence it follows that $R\left(b\right)<0,$ since $b>1$ and the inequalities

a_{1}+a_{2}+\ldots+a_{s}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{s}}\leq 0,\quad s=% \overline{1,n}

hold.

The inequality $R\left(a\right)\geq 0$ is proved in a similar manner. ∎

3. Iterative methods of interpolatory type

It is known that most of the iterative methods are obtained by inverse interpolation of Lagrange, Taylor or Hermite type.

Let $F=f\left(I\right)$ be the image of $I$ by $f$ . We shall suppose that $f$ is derivable on $I$ up to the order $n+1$ , and $f^{\prime}\left(x\right)\neq 0$ for all $x\in I$ . It then follows that $f:I\rightarrow F$ is invertible, so there exists $f^{-1}:F\rightarrow I$ . It is obvious that if $\bar{x}$ is the solution of (1) then

(13)

\bar{x}=f^{-1}\left(0\right).

In order to determine an approximation $\tilde{x}$ of $\bar{x}$ it is sufficient to determine a function $h$ which approximates $f^{-1}$ on a neighborhood $V_{0}$ of $y=0.$

(14)

f^{-1}\left(y\right)=h\left(y\right)+R\left(f^{-1},y\right),\quad\forall y\in V% _{0},

then we can consider that $\tilde{x}\approx\bar{x}$ with the error

(15)

\left|\bar{x}-\tilde{x}\right|=\left|R\left(f^{-1},0\right)\right|,\text{ % where }\tilde{x}=h\left(0\right).

A simple and efficient method for constructing functions that approximate $f^{-1}$ on $V_{0}$ is the inverse interpolation. The most general method of this type is the method that lead us to the Hermite inverse interpolatory polynomial.

In order to construct the Hermite inverse interpolatory polynomial in its most general form we must know both the values of $f^{-1}$ and the values of the derivatives of $f^{-1}$ at some precized points from $V_{0}$ .

Concerning the successive derivatives of $f^{-1}$ we shall rely on the following lemma:

Lemma 3.1.

[6]. If $f:I\rightarrow F$ is derivable up to the order $n+1$ and $f^{\prime}\left(x\right)\neq 0$ for all $x\in I$ , then there exists $f^{-1}:F\rightarrow I$ and the following equality holds:

(16)

\left(f^{-1}\right)^{\left(k\right)}\left(y\right)=\sum\tfrac{\left(2k-i_{1}-2% \right)\left(-1\right)^{k+i_{1}-1}}{i_{2}!i_{3}!\ldots i_{k}!\left[f^{\prime}% \left(x\right)\right]^{2k-1}}\textstyle\prod\limits_{j=1}^{k}\left(\tfrac{f^{% \left(j\right)}\left(x\right)}{j!}\right)^{i_{j}},

where $y=f\left(x\right)$ and the above sum extends on all nonnegative integer solutions of the system

\left\{\begin{array}[]{l}i_{2}+2i_{3}+3i_{4}+\ldots+\left(k-1\right)i_{k}=k-1% \\ i_{1}+i_{2}+\ldots+i_{k}=k-1.\end{array}\right.

Let $x_{i}\in I,\;$ $i=\overline{1,n+1}$ be $n+1$ interpolation nodes and $a_{1},a_{2},\ldots,a_{n+1}\geq 1$ , $n+1$ natural numbers. Denote by $m+1$ their sum:

(17)

a_{1}+a_{2}+\ldots+a_{n+1}=m+1.

We also denote $y_{i}=f\left(x_{i}\right),\,i=\overline{1,n+1}$ and so $f^{-1}\left(y_{i}\right)=x_{i}$ .

For the construction of the Hermite inverse interpolatory polynomial we consider as interpolation nodes the numbers $y_{i}\in F$ , $i=\overline{1,n+1}$ , and we need a polynomial

H\left(y_{1},a_{1};y_{2},a_{2};\ldots;y_{n+1},a_{n+1};f^{-1}\mid y\right)=H% \left(y\right)

which satisfies

(18)

H^{\left(j\right)}\left(y_{i}\right)=\left(f^{-1}\right)^{\left(j\right)}\left% (y_{i}\right),\quad j=\overline{0,a_{i}-1},\quad i=\overline{1,n+1}.

It is well known that such a polynomial has the following form

			$\displaystyle H\left(y_{1},a_{1};y_{2},a_{2};\ldots;y_{n+1},a_{n+1};f^{-1}\mid y% \right)=$
		$\displaystyle=$	$\displaystyle\sum\limits_{i=1}^{n+1}\sum\limits_{j=0}^{a_{i}-1}\sum\limits_{k=% 0}^{a_{i}-j-1}\left(f^{-1}\right)^{\left(j\right)}\left(y_{i}\right)\tfrac{1}{% k!j!}\left[\tfrac{\left(y-y_{i}\right)^{a_{i}}}{\omega\left(y\right)}\right]_{% y=y_{i}}^{\left(k\right)}\cdot\tfrac{\omega\left(y\right)}{\left(y-y_{i}\right% )^{a_{i}-j-k}},$

where

(20)

\omega\left(y\right)=\textstyle\prod\limits_{i=1}^{n+1}\left(y-y_{i}\right)^{a% _{i}}.

The following equality holds:

(21)

f^{-1}\left(y\right)=H\left(y_{1},a_{1};y_{2},a_{2};\ldots;y_{n+1},a_{n+1};f^{% -1}\mid y\right)+R\left(f^{-1},y\right)

where

(22)

R\left(f^{-1},y\right)=\tfrac{\left(f^{-1}\right)^{\left(m+1\right)}\left(% \theta\right)}{\left(m+1\right)!}\omega\left(y\right),

$\theta$ being a point belonging to the smallest interval determined by the points $y,y_{1},$ $y_{2},\ldots,y_{n+1}$ .

From (3), for $a_{1}=a_{2}=\ldots=a_{n+1}=1$ , there is obtained the Lagrange inverse interpolatory polynomial, i.e.

L\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1}y\right)=\sum\limits_{i=1}^{n+1}\tfrac% {x_{i}\omega\left(y\right)}{\left(y-y_{i}\right)\omega^{\prime}\left(y_{i}% \right)},

and for $n=0$ , again (3) gives the Taylor inverse interpolatory polynomial:

T\left(y_{1},f^{-1}y\right)=\sum\limits_{j=0}^{m}\tfrac{1}{j!}\left(f^{-1}% \right)^{\left(j\right)}\left(y_{1}\right)\left(y-y_{1}\right)^{j}.

Let $x_{s},x_{s+1},\ldots,x_{s+n}\in I$ be $n+1$ approximations for the solution $\bar{x}$ of equation (1). Then another approximation $x_{s+n+1}$ can be obtained by

(23)

x_{s+n+1}=H\left(y_{s},a_{1};y_{s+1},a_{2};\ldots;y_{s+n},a_{n+1};f^{-1}\mid 0% \right),\,\quad s=1,2,\ldots

where the function $H$ is given by (3) and the polynomial $\omega_{s}$ is given by

\omega_{s}\left(y\right)=\textstyle\prod\limits_{i=s}^{n+s}\left(y-y_{i}\right% )^{a_{i}},\qquad s=1,2,\ldots

It can be easily seen that, taking into account (21),

(24)

\left|f\left(x_{n+s+1}\right)\right|=\left|f^{\prime}\left(\beta_{s}\right)% \right|\tfrac{\left|\left(f^{-1}\right)^{m+1}\left(\theta_{s}\right)\right|}{% \left(m+1\right)!}\textstyle\prod\limits_{i=0}^{n}\left|f\left(x_{s+i}\right)% \right|^{a_{i+1}},\qquad s=1,2,\ldots,

if the sequence $\left(x_{p}\right)_{p\geq 0}$ is generated by (23). For all $s\geq 1$ , the numbers $\theta_{s}$ belong to the smallest interval determined by $0,y_{s},y_{s+1},\ldots,y_{s+n}$ and $\beta_{s}$ are numbers belonging to the open intervals determined by $\bar{x}$ and $x_{s+n+1}$ .

Supposing that

c_{s}=\left|f^{\prime}\left(\beta_{s}\right)\right|\tfrac{\left(f^{-1}\right)^% {\left(m+1\right)}\left(\theta_{s}\right)}{\left(m+1\right)!},\qquad s=1,2,\ldots

verify the hypotheses of Lemma 2.2 and, moreover, $\lim\limits_{s\rightarrow\infty}f\left(x_{s}\right)=0$ , then, taking into account Lemma 2.1, it follows that the convergence order of method (23) is given by the positive solution of equation

(25)

t^{n+1}-a_{n+1}t^{n}-a_{n}t^{n-1}-\ldots-a_{2}t-a_{1}=0.

If $a_{1}=a_{2}=\ldots=a_{n+1}=q,$ then the corresponding iterative method from (23) has the convergence order $\omega_{n+1}\left(q\right)$ given by the positive solution of the equation:

t^{n+1}-qt^{n}-qt^{n-1}-\ldots-qt-q=0.

In [5] there is shown that the number $\omega_{n}\left(q\right)$ satisfies

$a^{\prime}$ )

$\omega_{n}\left(q\right)<\omega_{n+1}\left(q\right),\quad\quad n=1,2,\ldots;$
$b^{\prime}$ )

$\max\left\{q,\frac{n+1}{n+2}\left(q+1\right)\right\}<\omega_{n+1}\left(q\right% )<q+1;$
$c^{\prime}$ )

$\lim\omega_{n}\left(q\right)=q+1.$

For $q=1,$ the properties $a^{\prime}$ )– $c^{\prime}$ ) can be found in [3].

For $n=0$ , the corresponding iterative method has the form

	$\displaystyle x_{s+1}=$	$\displaystyle x_{s}-\tfrac{\left(f^{-1}\right)^{\prime}\left(y_{s}\right)}{1!}% f\left(x_{s}\right)+\tfrac{1}{2!}\left(f^{-1}\right)^{\prime\prime}\left(y_{s}% \right)f^{2}\left(x_{s}\right)+\ldots$
		$\displaystyle+\left(-1\right)^{m}\tfrac{1}{m!}\left(f^{-1}\right)^{\left(m% \right)}\left(y_{s}\right)f^{m}\left(x_{s}\right),\qquad s=1,2,\ldots,$

i.e., the Chebyshev method. It can be easily seen that the convergence order of this method is $m+1$ .

We propose ourselves to find bounds for the convergence order $\omega$ of (23), i.e for the solutions of (25). First we shall prove the following lemma.

Lemma 3.2.

The positive root $\omega$ of equation (23) satisfies

(26)

\left(m+1\right)^{\alpha}\leq\omega\leq 1+\max_{1\leq i\leq n}\left\{a_{i}% \right\},

where

\alpha=\frac{m+1}{\left(n+1\right)\left(m+1\right)-\sum\limits_{i=1}^{n+1}% \left(i-1\right)a_{i}}.

Proof.

Let $\beta=\left(m+1\right)^{\alpha}$ and $P_{n+1}\left(t\right)=t^{n+1}-a_{n+1}t^{n}-\ldots-a_{2}t-a_{1}.$ For the first part of inequality (26) it will suffice to show that $P_{n+1}\left(\beta\right)\leq 0$ . Using the inequality between the geometric and the arithmetic mean, i.e.

\frac{\sum\limits_{i=1}^{n+1}p_{i}\alpha_{i}}{\sum\limits_{i=1}^{n+1}p_{i}}% \geq\left(\textstyle\prod\limits_{i=1}^{n+1}\alpha_{i}^{p_{i}}\right)^{\frac{1% }{\textstyle\sum\limits_{i=1}^{n+1}p_{i}}},\qquad\alpha_{i}>0,\quad p_{i}\geq 0% ,\ \ i=\overline{1,n+1},\ \ \textstyle\sum\limits_{i=1}^{n+1}p_{i}>0,

we obtain

	$\displaystyle P_{n+1}\left(\beta\right)$	$\displaystyle=\beta^{n+1}-\sum\limits_{i=1}^{n+1}a_{i}\beta^{i-1}=\beta^{n+1}-% \frac{\sum\limits_{i=1}^{n+1}a_{i}\alpha^{i-1}}{\sum\limits_{i=1}^{n+1}a_{i}}% \cdot\sum\limits_{i=1}^{n+1}a_{i}$
		$\displaystyle\leq\beta^{n+1}-\left(\sum\limits_{i=1}^{n+1}a_{i}\right)\left(% \prod\limits_{i=1}^{n+1}\beta^{\left(i-1\right)a_{i}}\right)^{\frac{1}{\sum% \limits_{i=1}^{n+1}a_{i}}}$
		$\displaystyle=\beta^{n+1}-\left(m+1\right)\left(\prod\limits_{i=1}^{n+1}\beta^% {\left(i-1\right)a_{i}}\right)^{\frac{1}{m+1}}=0,$

for $\beta=\left(m+1\right)^{\alpha}$ .

For the second inequality in (26) it easily comes that $P_{n+1}\left(a\right)\geq 0$ for $a=1+\max\limits_{1\leq i\leq n+1}\left\{a_{i}\right\}$ . ∎

4. Interpolatory methods having optimal convergence order

To each permutation of the set $\left\{1,2,\ldots,n+1\right\}$ there corresponds an iterative method of the form

(27)		$\displaystyle x_{n+2}=$	$\displaystyle H\left(y_{i_{1}},a_{i_{1}};y_{i_{2}},a_{i_{2}};\ldots;y_{i_{n+1}% },a_{i_{n+1}};f^{-1}0\right)$
	$\displaystyle x_{n+s+2}=$	$\displaystyle H\left(y_{i_{1}+s},a_{i_{1}};y_{i_{2}+s},a_{i_{2}};\ldots;y_{i_{% n+1}+s},a_{i_{n+1}};f^{-1}0\right),\quad s=1,2,\ldots$

There are $\left(n+1\right)!$ iterative methods. Lemma 2.3 offers the possibility to establish which method of the form (27) has the optimal convergence order.

Theorem 4.1.

Among the $\left(n+1\right)!$ iterative methods of the form ${\rm(\ref{4.1})}$ the method with the highest convergence order is the one for which

a_{i_{1}}\leq a_{i_{2}}\leq\ldots\leq a_{i_{n+1}}.

The proof of the above theorem is obtained as a directly consequence of Lemma 2.3.

In the following we shall apply the results of Theorem 4.1 to a particular case. For $n=1$ , by (23) we obtain two iterative methods:

(28)		$\displaystyle x_{3}$	$\displaystyle=H\left(y_{1},a_{1};y_{2},a_{2};f^{-1}\,0\right),\quad x_{1},x_{2% }\in I,\,y_{1}=f\left(x_{1}\right),\,y_{2}=f\left(x_{2}\right)$
	$\displaystyle x_{n+1}$	$\displaystyle=H\left(y_{n-1},a_{1};y_{n},a_{2};f^{-1}\,0\right),\quad n=3,4,\ldots$

and

(29)		$\displaystyle x_{3}$	$\displaystyle=H\left(y_{1},a_{2};y_{2},a_{1};f^{-1}0\right),\quad x_{1},x_{2}% \in I,\;\,y_{1}=f\left(x_{1}\right),\;\,y_{2}=f\left(x_{2}\right).$
	$\displaystyle x_{n+1}$	$\displaystyle=H\left(y_{n-1},a_{2};y_{n},a_{1};f^{-1}\,0\right),\quad n=3,4,\ldots$

The convergence order $\omega_{1}$ of method (28) is given by the positive solution of

t^{2}-\alpha_{2}t-\alpha_{1}=0

and for (29) the convergence order is the solution of

t^{2}-\alpha_{1}t-\alpha_{2}=0\text{.}

It is easily seen that if $\alpha_{2}\geq\alpha_{1}$ then $\omega_{2}\leq\omega_{1}$ , and so the iterative method (28) has a greater convergence order than the one of (29).

References

[1] R. Brent, S. Winograd, F. Wolfe, Optimal iterative processes for root-finding., Numer. Math. 20 (1973), 327–341.
[2] H.T. Kung, J.F. Traub, Optimal order and efficiency for iterations with two evaluations, Numer. Anal., Vol. 13, 1, (1976), 84–99.
[3] A.M. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York and London, (1966).
[4] I. Pǎvǎloiu, ^†^†margin: available soon,
refresh and click here $\rightarrow$ Optimal problems concerning interpolation methods of solution of equations, Publ. Inst. Math., 52 (66) (1992), 113–126.
[5] J.F. Traub , Iterative Methods for Solution of Equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, (1964).
[6] B.A. Turowicz, Sur les derivées d’ordre superieur d’une fonction inverse, Ann. Polon. Math. 8 (1960), 265–269.

Romanian Academy

”T. Popoviciu” Institute of Numerical Analysis

P.O. Box 68,

3400, Cluj-Napoca

Romania

Posts by Ion Păvăloiu

Abstract

Author

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Article on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

ON THE CONVERGENCE ORDER OF THE MULTISTEP METHODS

1. Introduction

2. Convergence order

Definition 2.1.

Remark 2.1.

Lemma 2.1.

Proof.

Lemma 2.2.

Proof.

Lemma 2.3.

Proof.

3. Iterative methods of interpolatory type

Lemma 3.1.

Lemma 3.2.

Proof.

4. Interpolatory methods having optimal convergence order

Theorem 4.1.

References

Related Posts

ON THE CONVERGENCE ORDER
OF THE MULTISTEP METHODS