OPTIMAL EFFICIENCY INDEXES FOR ITERATIVE METHODS OF INTERPOLATORY TYPE ^†^†thanks: AMS Subject Classification (1991): Primary 65Y20, 68Q25, 65H05.^†^†thanks: This work has been supported by the Romanian Academy of Sciences.

Abstract

The paper is concerned with the order of convergence and the efficiency index of iterative methods of interpolatory type for solving scalar equations. Some classes of such methods are presented and then, using well defined criteria, the methods having the optimal efficiency index (i.e. those who practically are the most efficient) are determined. For these methods the efficiency indexes are effectively determined.

1 Introduction

In this paper we propose a unitary approach concerning the computational complexity for the numerical solving of scalar equations by iterative methods of interpolatory type. We shall consider some classes of such methods from which, using well defined criteria, we shall choose the optimal ones.

As a measure for the complexity of a method we shall adopt the efficiency index (see [4]).

For this purpose we shall start by presenting some general considerations concerning the convergence order and the efficiency index of an iterative method. Then we shall specify the interpolatory methods to be studied. Finally, we shall select from the interpolatory classes those having the highest efficiency index, and for the classes for which the selection method can’t be applied, we shall give delimitations for the efficiency index.

2 The convergence order and the efficiency index

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

(1)

f\left(x\right)=0

where $f:I\rightarrow{\mathbf{R}}$ . In the following we shall suppose, for simplicity, that the equation $\left(2.1\right)$ has a unique solution $\overline{x}\in I$ . Let $g:I\rightarrow I$ be a function having a unique fixed point in the interval $I$ , which coincides with $\overline{x}.$

For the approximation of the root $\overline{x}$ of equation $\left(2.1\right)$ , under certain conditions, we may consider the elements of the sequence $\left(x_{p}\right)_{p\geq 0}$ generated by the following iterative process

(2)

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

More generally, if $G:I^{k}\rightarrow I$ is a function of $k$ variables whose restriction to the diagonal of the set $I^{k}$ coincides with $g,$ i.e.

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

then we may consider the following iterative process:

(3)

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

The convergence of the sequence $\left(x_{p}\right)_{p\geq 0}$ generated by $\left(2.2\right)$ or $\left(2.3\right)$ depends on certain properties of the functions $f$ and $g$ , respectively $G$ . The amount of time needed by a computer to obtain a suitable approximation of $\overline{x}$ , depends both on the convergence order of the sequence $\left(x_{p}\right)_{p\geq 0}$ and on the number of elementary operations that must be performed at each iteration step in $\left(2.2\right)$ or $\left(2.3\right)$ . Concerning the convergence order, it can be exactly computed in almost all the cases. Hence it remains to solve the difficult problem of determining the number of elementary operations that must be performed at each iteration step. A general approach to this problem of course can’t be successful. That’s why A.M. Ostrowski proposed in [4] a simplification of this problem, by considering the number of function evaluations at each iteration step. At first sight this approach seems to be strange, taking into account that some functions may be more complicated and others may be simpler from the computational standpoint. But our purpose is to compare different methods applied to the same equation, and such an approach can give results.

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

a): $x_{s}\in I$ and $g\left(x_{s}\right)\in I$ for $s=0,1,...;$
b): the sequences $\left(x_{p}\right)_{p\geq 0}$ and $\left(g(x_{p})\right)_{p\geq 0}$ are convergent and $\lim x_{p}=\lim g(x_{p})=\\ =\overline{x},$ where $\,\overline{x}$ is the solution of $\left(2.1\right);$
c): For all $x,y\in I,0<\left|[x,y;f]\right|\leq m,\,m\in{\mathbf{R}},\,m>0$ , where we have denoted by $\left[x,y;f\right]$ the first order divided difference of $f$ on the nodes $x$ and $y$ ;
d): $f$ is derivable at $\overline{x}.$

Definition 2.0.1

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

(4)

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

and $\alpha=\omega$ .

Remark 2.0.1

If the sequence $\left(x_{p}\right)_{p\geq 0}$ is generated by the iterative method $\left(2.2\right)$ , then the Definition 2.1. reduces to the known one [4].

For a unitary treatment of the determination of the convergence order of the studied methods, we shall use the following lemmas.

Lemma 2.0.0

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{\mathbf{R}},\,\omega\geq 1,$ with respect to the function $g$ is that the following limit exists:

(5)

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

and $\beta=\omega.$

Proof. Supposing that one of the equalities $\left(2.4\right)$ or $\left(2.5\right)$ is true and taking into account the properties a) - d), we obtain:

\lim\dfrac{\ln\left|g\left(x_{p}\right)-\overline{x}\right|}{\ln\left|x_{p}-% \overline{x}\right|}=\lim\dfrac{\ln\left|f\left(g\left(x_{p}\right)\right)% \right|-\ln\left|\left[g\left(x_{p}\right),\overline{x};f\right]\right|}{\ln% \left|f\left(x_{p}\right)\right|-\ln\left|\left[x_{p},\overline{x};f\right]% \right|}=

=\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),% \overline{x};f\right]\right|}{\ln\left|f\left(g\left(x_{p}\right)\right)\right% |}}{1-\dfrac{\ln\left|\left[x_{p},\overline{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|}.

Lemma is proved.

Lemma 2.0.0

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

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

ii. There exist the nonnegative real numbers $\alpha_{1},...,\alpha_{n+1}$ and a bounded sequence $\left(c_{p}\right)_{p\geq 0}$ with $c_{s}>0$ for all $s=0,1,...,$ and $\,0<\inf\left\{c_{p}\right\}$ such that the elements of $\left(u_{p}\right)_{p\geq 0}$ satisfy

(6)

u_{s+n+1}=c_{s}u_{s}^{\alpha_{1}}u_{s+1}^{\alpha_{2}}...u_{s+n}^{\alpha_{n+1}}% ,\,\;s=0,1,...;

iii. The sequence $\frac{\ln\,u_{p+1}}{\ln\,u_{p}}$ is convergent and $\omega=\lim\frac{\ln\,u_{p+1}}{\ln\,u_{p}}>0.$

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

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

Proof. From $\left(2.6\right)$ 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}}.

But it can be easily seen that

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

whence it follows that $\;\omega=\sum\limits_{i=0}^{n}\alpha_{i+1}\frac{1}{\omega^{n-i}},$ i.e. $\omega^{n+1}-\sum\limits_{i=0}^{n}\alpha_{i+1}\omega^{i}=0.$ Lemma is proved.

We shall denote in the following by $m_{p}$ the number of function evaluations that must be performed at each iteration step $p$ in $\left(2.2\right)$ , respectively $\left(2.3\right),$ for $p=0,1,...\,$ .

In the hypotheses of Lemma 2.1 and taking into account the definition given in [4], we have:

Definition 2.0.2

The real number $E$ is called the efficiency index of the iterative method $\left(2.2\right)$ or $\left(2.3\right)$ if there exists

L=\lim\left(\frac{\ln\left|f\left(x_{p+1}\right)\right|}{\ln\left|f\left(x_{p}% \right)\right|}\right)^{\frac{1}{m_{p}}}

and $L=E.$

Remark 2.0.2

If for the methods $\left(2.2\right)$ and $\left(2.3\right)$ there exists a natural number $s_{0}$ such that $m_{s}=r$ for all $s>s_{0}$ and $\omega$ is the convergence order of these methods, then the efficiency index $E$ is given by the following expression:

(7)

E=\omega^{\frac{1}{r}}.

3 Iterative methods of interpolatory type

In the following we shall briefly present the Lagrange-Hermite-type inverse interpolatory polynomial. It is well known that this leads us to general classes of iterative methods from which, by suitable particularizations we obtain usual methods as Newton’s method, chord’s method, Chebyshev’s method, etc.

For the sake of simplicity we prefer to treat separately the Hermite polynomial and the Lagrange polynomial, though the last is a particular case of the first.

As we shall see, a suitable choice of the nodes enables us to improve the convergence orders of Lagrange-Hermite-type methods. We shall call such methods Steffensen-type methods.

3.1 Lagrange-type inverse interpolation

Denote by $F=f\left(I\right)$ the range of $f$ for $x\in I.$ Suppose $f$ is $n+1$ times differentiable and $f^{\prime}\left(x\right)\neq 0$ for all $x\in I$ . It follows that $f$ is invertible and there exists $f^{-1}:F\rightarrow I.$ Consider $n+1$ interpolation nodes in $I$ :

(8)

x_{1},x_{2},...,x_{n+1},\,\,x_{i}\neq x_{j},\,\text{for }i,j=\overline{1,n+1},% \;i\neq j.

In the above hypotheses it follows that the solution $\overline{x}$ of equation $\left(2.1\right)$ is given by

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

Using the Lagrange interpolatory polynomial for the function $f^{-1}$ at the nodes $f\left(x_{1}\right),...,f\left(x_{n+1}\right)$ we shall determine an approximation for $f^{-1}\left(0\right)$ , i.e. for $\overline{x}.$

Denote $y_{i}=f\left(x_{i}\right),\,\,\,\,i=\overline{1,n+1}$ and let $L\left(y_{1},y_{2},...,y_{n+1};f^{-1}\mid y\right)\,$ be the mentioned polynomial, which is known to have the form

L\left(y_{1},y_{2},...,y_{n+1};f^{-1}\mid y\right)=\sum_{i=1}^{n}\frac{x_{i}% \omega_{1}\left(y\right)}{\left(y-y_{i}\right)\omega_{1}^{\prime}\left(y_{i}% \right)},

where $\omega_{1}\left(y\right)=\prod\limits_{i=1}^{n+1}\left(y-y_{i}\right).$

The following equality holds

(9)

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

where

R\left(f^{-1},y\right)=\frac{\left[f^{-1}\left(\theta_{1}\right)\right]^{\left% (n+1\right)}}{\left(n+1\right)!}\omega_{1}\left(y\right)

and $\min\left\{y,f\left(x_{1}\right),...,f\left(x_{n+1}\right)\right\}<\theta_{1}<% \max\left\{y,f\left(x_{1}\right),...,f\left(x_{n+1}\right)\right\}.$

It is also known that in the mentioned hypotheses concerning the derivability of $f$ on $I$ , the function $f^{-1}$ admits derivatives of any order $k$ , $1\leq k\leq n+1$ for all $y\in F$ and the following equality holds [4], [8]:

(10)

\begin{array}[]{c}\left[f^{-1}\left(y\right)\right]^{\left(k\right)}=\mathop{% \displaystyle\sum}\frac{\left(2k-i_{1}-2\right)!\left(-1\right)^{k+i_{1}-1}}{i% _{2}!i_{3}!...i_{k}!\left[f^{\prime}\left(x\right)\right]^{2k-1}}\left(\frac{f% ^{\prime}\left(x\right)}{1!}\right)^{i_{1}}\left(\frac{f^{{}^{\prime\prime}}% \left(x\right)}{2!}\right)^{i_{2}}...\left(\frac{f^{\left(k\right)}\left(x% \right)}{k!}\right)^{i_{k}},\\ k=\overline{1,n+1}\end{array}

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

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

From $\left(3.1.2\right)$ , neglecting $R\left(f^{-1},0\right)$ we obtain the following approximation for $\bar{x}$

\bar{x}\simeq L\left(y_{1},y_{2},...,y_{n+1};f^{-1}\mid 0\right).

Denoting

x_{n+2}=L\left(y_{1},y_{2},...,y_{n+1};f^{-1}\mid 0\right),

we obtain

\left|x_{n+2}-\bar{x}\right|=\frac{\left|\left[f^{-1}\left(\theta_{1}^{\prime}% \right)\right]^{\left(n+1\right)}\right|}{\left(n+1\right)!}\left|\omega_{1}% \left(0\right)\right|,

where $\min\left\{0,f\left(x_{1}\right),...,f\left(x_{n+1}\right)\right\}<\theta_{1}^% {\prime}<\max\left\{0,f\left(x_{1}\right),...,f\left(x_{n+1}\right)\right\}.$

It is clear that if $x_{s},x_{s+1},...,x_{s+n}$ are $n+1$ distinct approximations of the solution $\bar{x}$ of equation $\left(2.1\right)$ then a new approximation $x_{s+n+1}$ can be obtained as above, i.e.

(11)

x_{s+n+1}=L\left(y_{s},y_{s+1},...,y_{s+n};f^{-1}\mid 0\right)\,\,s=1,2,...

with the error estimate given by

(12)

\left|x_{s+n+1}-\bar{x}\right|=\frac{\left|\left[f^{-1}\left(\theta_{s}^{% \prime}\right)\right]^{\left(n+1\right)}\right|}{\left(n+1\right)!}\prod_{i=0}% ^{n}\left|f\left(x_{s+i}\right)\right|,\quad\quad\,\,\,s=1,2,...

where $\theta_{s}^{\prime}$ belongs to the smallest open interval containing $0,f\left(x_{s}\right),...,f\left(x_{s+n}\right).$

If we replace in $\left(3.1.5\right)$ $\left|x_{s+n+1}-\bar{x}\right|=\frac{\left|f\left(x_{s+n+1}\right)\right|}{% \left|f^{\prime}\left(\alpha_{s}\right)\right|},$ we obtain for the sequence $\left(f\left(x_{p}\right)\right)_{p\geq 0}$ the relations:

(13)

\left|f\left(x_{s+n+1}\right)\right|=\left|f^{\prime}\left(\alpha_{s}\right)% \right|\frac{\left|\left[f^{-1}\left(\theta_{s}^{\prime}\right)\right]^{\left(% n+1\right)}\right|}{\left(n+1\right)!}\mathop{\displaystyle\prod}_{i=0}^{n}% \left|f\left(x_{s+i}\right)\right|,

where $\alpha_{s}$ belongs to the open interval determined by $\bar{x}$ and $x_{s+n+1}$ .

Suppose that $c_{s}=\left|f^{\prime}\left(\alpha_{s}\right)\right|\frac{\left|\left[f^{-1}% \left(\theta_{s}^{\prime}\right)\right]^{\left(n+1\right)}\right|}{\left(n+1% \right)!},s\in{\mathbf{N}},$ satisfies the hypotheses of Lemma 2.1 and that the sequence $\left(f\left(x_{p}\right)\right)_{p\geq 0}$ , converges to zero, where $\left(x_{p}\right)_{p\geq 0}$ is generated by $\left(3.1.4\right)$ . Then the convergence order of this sequence is equal to the positive solution of the equation:

t^{n+1}-t^{n}-t^{n-1}-...-t-1=0

Considering the set of all equations of the above form for $n\geq 1,\,n\in{\mathbf{N}}$ , and denoting by $\omega_{n+1}$ its corresponding positive solution it is known that the following relations hold [4]:

a^′): $\frac{2\left(n+1\right)}{n+2}<\omega_{n+1}<2\quad\quad n=1,2,...;$
b^′): $\omega_{n}<\omega_{n+1}\quad n=1,2,...;$
c^′): $\lim\omega_{n}=2$ .

3.2 Hermite-type inverse interpolation

Consider in the following, besides the interpolation nodes $\left(3.1.1\right)$ , $n+1$ natural numbers $a_{1},a_{2},...,a_{n+1},$ where $a_{i}\geq 1,\;i=\overline{1,n+1}$ and

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

We shall suppose here too, for simplicity, that $f$ is $m+1$ times differentiable on $I$ . From this and from $f^{\prime}\left(x\right)\neq 0$ for all $x\in I$ , it follows, by $\left(3.1.3\right)$ , that $f^{-1}$ is also $m+1$ times differentiable on $F$ . Denoting $y_{i}=f\left(x_{i}\right)$ , $i=\overline{1,n+1},$ the Hermite polynomial for the nodes $y_{i},\;i=\overline{1,n+1},$ with multiplicity orders $a_{i},\;i=\overline{1,n+1},$ has the following form:

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

=\mathop{\displaystyle\sum}\limits_{i=1}^{n+1}\mathop{\displaystyle\sum}% \limits_{j=0}^{a_{i}-1}\mathop{\displaystyle\sum}\limits_{k=0}^{a_{i}-j-1}% \left[f^{-1}\left(y_{i}\right)\right]^{\left(j\right)}\frac{1}{k!j!}\left[% \frac{\left(y-y_{i}\right)^{a_{i}}}{\omega_{1}\left(y\right)}\right]_{y=y_{i}}% ^{\left(k\right)}\frac{\omega_{1}\left(y\right)}{\left(y-y_{i}\right)^{a_{i}-j% -k}}

where

(14)

\omega_{1}\left(y\right)=\prod_{i=1}^{n+1}\left(y-y_{i}\right)^{a_{i}}.

If $x_{s},x_{s+1},...,x_{s+n}$ are $n+1$ distinct approximations of the solution $\bar{x}$ of the equation $\left(2.1\right)$ , then the next approximation $x_{s+n+1}$ can be obtained as before in the following way:

(15)

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

where, as in $\left(3.2.1\right),$

\omega_{s}\left(y\right)=\prod_{i=s}^{s+n}\left(y-y_{i}\right)^{a_{i}}.

It can be easily seen that the following equality holds:

(16)

\left|f\left(x_{s+n+1}\right)\right|=\left|f^{\prime}\left(\beta_{s}\right)% \right|\frac{\left|\left[f^{-1}\left(\theta_{s}^{\prime\prime}\right)\right]^{% \left(m+1\right)}\right|}{\left(m+1\right)!}\mathop{\displaystyle\prod}_{i=0}^% {n}\left|f\left(x_{s+i}\right)\right|^{a_{i+1}},\;s=1,2,...,

where $\theta_{s}^{\prime\prime}$ belongs to the smallest open interval containing $0,y_{s},y_{s+1},...,y_{s+n}$ and $\beta_{s}$ belongs to the open interval determined by $\bar{x}$ and $x_{s+n+1}$ .

If we suppose that $c_{s}=\left|f^{\prime}\left(\beta_{s}\right)\right|\frac{\left|\left[f^{-1}% \left(\theta_{s}^{\prime\prime}\right)\right]^{\left(m+1\right)}\right|}{\left% (m+1\right)!},\,s\in{\mathbf{N},}$ verifies the hypotheses of Lemma 2.1 and, moreover, $\lim\limits_{s\rightarrow\infty}f\left(x_{s}\right)=0$ , then it is clear that the convergence order of the method $\left(3.2.2\right)$ is given by the positive solution of the equation

(17)

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

In the following we shall consider the following particular cases of $\left(3.2.2\right)$ :

For $a_{1}=a_{2}=...=a_{n+1}=q,$ from $\left(3.2.2\right)$ we obtain

(18)

x_{s+n+1}=H\left(y_{s},q;y_{s+1},q;...;y_{s+n},q;f^{-1}\mid 0\right),

method having the convergence order given by the positive solution of the equation

(19)

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

Let $\gamma_{n+1}\left(q\right)$ denote the positive solution of equation $\left(3.2.6\right)$ . It is easy to prove that the following properties hold $\left(\text{see [7]}\right):$

a^′′): $\gamma_{n}\left(q\right)<\gamma_{n+1}\left(q\right)\quad\quad n=1,2,...;$
b^′′): $\max\left\{q,\frac{n+1}{n+2}\left(q+1\right)\right\}<\gamma_{n+1}\left(q\right% )<q+1\quad n=1,2,...;$
c^′′): $\lim\limits_{n\rightarrow\infty}\gamma_{n}\left(q\right)=q+1.$

Taking $n=0$ in $\left(3.2.2\right)$ we obtain again Chebyshev’s method, i.e.

(20)

\begin{array}[]{c}x_{s+1}=x_{s}-\frac{\left[f^{-1}\left(y_{s}\right)\right]^{{% }^{\prime}}}{1!}f\left(x_{s}\right)+\frac{\left[f^{-1}\left(y_{s}\right)\right% ]^{{}^{\prime\prime}}}{2!}f^{2}\left(x_{s}\right)+...\\ +\left(-1\right)^{m}\frac{\left[f^{-1}\left(y_{s}\right)\right]^{\left(m\right% )}}{m!}f^{m}\left(x_{s}\right),\quad s=1,2,...,\end{array}

where $y_{s}=f\left(x_{s}\right),$ the convergence order being $m+1$ .

Concerning the positive solution of equation $\left(3.2.4\right)$ we state the following lemma.

Lemma 3.2.0

The positive solution $\delta_{n+1}$ of equation $\left(3.2.4\right)$ verifies the relations:

(21)

\left(m+1\right)^{\frac{m+1}{\left(n+1\right)\left(m+1\right)-\sum\limits_{i=1% }^{n+1}\left(i-1\right)a_{i}}}\leq\delta_{n+1}\leq 1+\max_{1\leq i\leq n+1}% \left\{a_{i}\right\},\;\,n=1,2,...

Proof. Let

(22)

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

It is sufficient to prove that $P_{n+1}\left(\alpha\right)\leq 0,$ where $P_{n+1}\left(t\right)=t^{n+1}-a_{n+1}t^{n}-...-a_{2}t-a_{1}.$ We shall use for this the inequality between the arithmetic mean and the geometric mean, i.e.

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

Using this inequality we obtain

\begin{array}[]{c}P_{n+1}\left(\alpha\right)=\alpha^{n+1}-\sum\limits_{i=1}^{n% +1}a_{i}\alpha^{i-1}=\alpha^{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}\leq\\ \leq\alpha^{n+1}-\left(\sum\limits_{i=1}^{n+1}a_{i}\right)\left(\prod\limits_{% i=1}^{n+1}\alpha^{\left(i-1\right)a_{i}}\right)^{\frac{1}{\sum\limits_{i=1}^{n% +1}a_{i}}}=\alpha^{n+1}-\left(m+1\right)\left(\prod\limits_{i=1}^{n+1}\alpha^{% \left(i-1\right)a_{i}}\right)^{\frac{1}{m+1}}=\\ =\alpha^{n+1}-\left(m+1\right)\left(\alpha^{\sum\limits_{i=1}^{n+1}\left(i-1% \right)a_{i}}\right)^{\frac{1}{m+1}}=\alpha^{\frac{\sum\limits_{i=1}^{n+1}% \left(i-1\right)a_{i}}{m+1}}\left[\alpha^{n+1-\frac{\sum\limits_{i=1}^{n+1}% \left(i-1\right)a_{i}}{m+1}}-\left(m+1\right)\right]=0,\end{array}

i.e. $P_{n+1}\left(\alpha\right)\leq 0.$

Remark 3.2.3

It can be easily seen that the number $\alpha$ given by $\left(3.2.9\right)$ can be exprimed using $P_{n+1}^{\prime}\left(1\right)$ :

\alpha=\left(m+1\right)^{\frac{m+1}{m\left(n+1\right)+P_{n+1}^{\prime}\left(1% \right)}}.

The second part of relations $\left(3.2.8\right)$ follows easily from the inequality $P_{n+1}\left(a\right)>0,$ where $a=1+\max\limits_{1\leq i\leq n+1}\left\{a_{i}\right\}.$

3.3 Steffensen-type iterative methods

The convergence orders of methods (3.1.4), (3.2.2), respectively (3.2.5) can be improved if the interpolation nodes in the corresponding formulae are chosen in a special way. For this purpose we consider a continuous function $\varphi:I\rightarrow I$ , whose unique fixed point in the interval $I$ is $\bar{x}$ . We also suppose that $f$ and $\varphi$ verify the equality

(23)

f\left(\varphi\left(x\right)\right)=g\left(x\right)\cdot f\left(x\right),\quad% \text{for all }x\in I,

where $g:I\rightarrow{\mathbf{R}}$ , $g\left(x\right)\neq 0$ for all $x\in I$ .

Let $x_{s}\in I$ be an approximation of the solution $\bar{x}$ . Denote $u_{s}=x_{s},$ $u_{s+1}=\varphi\left(u_{s}\right),\;u_{s+2}=\varphi\left(u_{s+1}\right),...,\,% u_{s+n}=\varphi\left(u_{s+n-1}\right)$ and $\bar{y}_{s}=f\left(u_{s}\right),\,\bar{y}_{s+1}=f\left(u_{s+1}\right),...,$ $\bar{y}_{s+n}=f\left(u_{s+n}\right).$

Considering now as interpolation nodes the numbers $\bar{y}_{s},\bar{y}_{s+1},...,\bar{y}_{s+n},$ by $\left(3.1.4\right)$ we obtain

(24)

x_{s+1}=L\left(\bar{y}_{s},\bar{y}_{s+1},...,\bar{y}_{s+n};f^{-1}\mid 0\right)% \quad s=0,1,...,\quad x_{1}\in I,

and from $\left(3.2.2\right)$ we have

(25)

\quad\quad x_{s+1}=H\left(\bar{y}_{s},a_{1};\bar{y}_{s+1},a_{2};...;\bar{y}_{s% +n},a_{n+1};f\mid 0\right),\quad s=0,1,...,\quad x_{1}\in I.

The iterative methods $\left(3.3.2\right)$ and $\left(3.3.3\right)$ are generalizations of the Steffensen’s method, which can be obtained from $\left(3.3.2\right)$ for $n=1$ (see [4], [5]).

From $\left(3.3.1\right)$ one obtains the following representations for $\bar{y}_{s+i},\,i=\overline{1,n}$ :

\bar{y}_{s+i}=f\left(u_{s+i}\right)=p_{s,i-1}f\left(x_{s}\right),\quad i=1,2,.% ..,n,

where

p_{s,i-1}=\prod\limits_{j=s}^{s+i-1}g\left(u_{j}\right).

Considering $\left(3.1.6\right)$ we obtain:

(26)

\begin{array}[]{c}\left|f\left(x_{s+1}\right)\right|=\left|f^{\prime}\left(% \alpha_{s}^{\prime}\right)\right|\frac{\left|\left(f^{-1}\left(\mu_{s}\right)% \right)^{\left(n+1\right)}\right|}{\left(n+1\right)!}\mathop{\displaystyle% \prod}\limits_{i=1}^{s+1}\left|p_{s,i-1}\right|\cdot\left|f\left(x_{s}\right)% \right|^{n+1},\\ \;s=0,1,...,\end{array}

and, analogously, from $\left(3.2.3\right)$ we get

(27)

\left|f\left(x_{s+1}\right)\right|=\left|f^{\prime}\left(\beta_{s}^{\prime}% \right)\right|\frac{\left|\left[f^{-1}\left(\mu_{s}^{\prime}\right)\right]^{% \left(m+1\right)}\right|}{\left(m+1\right)!}\prod\limits_{i=1}^{n+1}\left|p_{s% ,i-1}\right|^{a_{i}}\cdot\left|f\left(x_{s}\right)\right|^{m+1}.

In the relations $\left(3.3.4\right)$ and $\left(3.3.5\right),$ $\alpha_{s}^{\prime}$ and $\beta_{s}^{\prime}$ are contained in the open interval determined by $\bar{x}$ and $x_{s+1}$ from $\left(3.3.2\right)$ and $\left(3.3.3\right)$ respectively and $\mu_{s}$ and $\mu_{s}^{\prime}$ belong to the smallest open interval containing $0,\bar{y}_{s},\bar{y}_{s+1},...,\bar{y}_{s+n}$ from $\left(3.3.2\right),$ respectively $\left(3.3.3\right)$ .

If we suppose that the sequences $\left(u_{s}\right)_{s\geq 0}$ and $\left(v_{s}\right)_{s\geq 0}$ given by

\begin{array}[]{c}u_{s}=\left|f^{\prime}\left(\alpha_{s}^{\prime}\right)\right% |\frac{\left|\left[f^{-1}\left(\mu_{s}\right)\right]^{\left(n+1\right)}\right|% }{\left(n+1\right)!}\prod\limits_{i=1}^{n+1}\left|p_{s,i-1}\right|,\\ v_{s}=\left|f^{\prime}\left(\beta_{s}^{\prime}\right)\right|\frac{\left|\left[% f^{-1}\left(\mu_{s}^{\prime}\right)\right]^{\left(m+1\right)}\right|}{\left(m+% 1\right)!}\prod\limits_{i=1}^{n+1}\left|p_{s,i-1}\right|^{a_{i}}\end{array}

are bounded and $\inf\left\{u_{s}\right\}\neq 0,$ respectively $\inf\left\{v_{s}\right\}\neq 0,$ then we clearly have that the convergence orders of methods $\left(3.3.2\right),$ respectively $\left(3.3.3\right)$ are equal to $n+1$ , respectively $m+1$ .

Remark 3.3.4

For the way of choosing the function $\varphi$ with the mentioned properties see for example [5].

4 Optimal efficiency

We shall analyze in the following the efficiency index of each of the methods described and in the hypotheses adopted below we shall determine the optimal methods, i.e. those having the highest efficiency index.

As we have seen, the formulae for computing the derivatives of $f^{-1}$ have a complicated form and they depend on the successive derivatives of $f$ . Though, in the case where the orders of the derivatives of $f^{-1}$ are low, the values of these derivatives are obtained by only a few elementary operations. Taking into account the generality of the problem we shall consider each computation of the values of any derivative of $f^{-1}$ by $\left(3.1.3\right)$ as a single function evaluation. For similar reasons we shall also consider each computation of the inverse interpolatory polynomials as a single function evaluation.

As it will follow from our reasonings, the methods having the optimal efficiency index are generally the simple ones, using one or two interpolation nodes and the derivatives of $f^{-1}$ up to the second order.

Remark that in our case we can use for the efficiency index the relation $\left(2.7\right)$ .

4.1 Optimal Chebyshev-type methods

Observe that for passing from the $s$ -th iteration step to the $s+1$ , in method $\left(3.2.7\right)$ must be performed the following evaluations:

f\left(x_{s}\right),f^{\prime}\left(x_{s}\right),...,f^{\left(m\right)}\left(x% _{s}\right),

i.e. $m+1$ values.

Then, by $\left(3.1.3\right),$ we perform the following $m$ function evaluations:

\left[f^{-1}\left(y_{s}\right)\right]^{\prime},\left[f^{-1}\left(y_{s}\right)% \right]^{\prime\prime},...,\left[f^{-1}\left(y_{s}\right)\right]^{\left(m% \right)},

where $y_{s}=f\left(x_{s}\right).$ Finally, for the right hand expression of relation $\left(3.2.7\right)$ we perform another function evaluation, so that $2\left(m+1\right)$ function evaluations must be performed.

By $\left(2.7\right)$ the efficiency index of method $\left(3.2.7\right)$ has the form

E\left(m\right)=\left(m+1\right)^{\frac{1}{2\left(m+1\right)}},\quad E:{% \mathbf{N}}\rightarrow{\mathbf{R}.}

Considering the function $h:\left(0,+\infty\right)\rightarrow{\mathbf{R}},\;h\left(t\right)=t^{\frac{1}{% 2t}}$ , we observe that it attains its maximum at $t=e$ , so that the maximum value of $E$ is attained for $m=2$ . We have proved the following result:

Theorem 4.1.4

Among the Chebyshev-type iterative methods having the form $\left(3.2.7\right)$ the method with the highest efficiency index is the third order method, i.e.

(28)

x_{s+1}=x_{s}-\frac{f\left(x_{s}\right)}{f^{\prime}\left(x_{s}\right)}-\frac{1% }{2}\frac{f^{\prime\prime}\left(x_{s}\right)f^{2}\left(x_{s}\right)}{\left[f^{% \prime}\left(x_{s}\right)\right]^{3}},\quad s=0,1,...,\quad x_{0}\in I.

In the following table some approximate values of $E$ are listed :

m	1 2 3 4 5
E(m)	1.1892 1.2009 1.1892 1.1746 1.1610

Table 4.1.1

We note that $E\left(2\right)\simeq 1.2009.$

4.2 The efficiency of Lagrange-type methods

We shall study the methods of the form $\left(3.1.4\right)$ , for which the convergence order verifies $a^{\prime})-c^{\prime})$ from $3.1 .$ Taking into account Remark 2.2, it can be easily seen that we can use relation $\left(2.7\right)$ for the efficiency index of these methods. For each $s+n+1$ step $,\,s\geq 2,$ in $\left(3.1.4\right)$ in order to pass to the next step, only $f\left(x_{s+n+1}\right)$ must be evaluated, the other values from $\left(3.1.4\right)$ being already computed. We have also another function evaluation in computing the right-hand side of relation $\left(3.1.4\right)$ . So there are needed two function evaluations. Taking into account that the convergence order $\omega_{n+1}$ of each method satisfies $a^{\prime})-c^{\prime})$ , and denoting by $E_{n+1}$ the corresponding efficiency index, we have

E_{n+1}=\omega_{n+1}^{\frac{1}{2}},\quad n=1,2,...;

E_{n}<E_{n+1},\quad n=2,3,...

and

\lim E_{n}=\sqrt{2}.

We have proved:

Theorem 4.2.5

For the class of iterative methods of the form $\left(3.1.4\right)$ the efficiency index is increasing with respect to the number of interpolation nodes, and we have the equality

\lim E_{n}=\sqrt{2}.

4.3 Optimal Hermite-type particular methods

We shall study the class of iterative methods of the form $\left(3.2.5\right)$ for $q>1$ . Taking into account the remarks from 4.2. it is clear that we can use again relation $\left(2.7\right)$ for the efficiency index.

If $x_{n+j}$ is an approximation for the solution $\bar{x}$ obtained by $\left(3.2.5\right)$ then for passing to the following iteration step we need

f\left(x_{n+j}\right),f^{\prime}\left(x_{n+j}\right),...,f^{\left(q-1\right)}% \left(x_{n+j}\right),

i.e. $q$ function evaluations. Then, by $\left(3.1.3\right)$ we must compute the derivatives of the inverse function $\left[f\left(y_{n+j}\right)^{-1}\right]^{\left(i\right)},$ $i=\overline{1,q-1}$ , where $y_{n+j}=f\left(x_{n+j}\right)$ . Another function evaluation is needed for computing the right hand side of relation $\left(3.2.5\right)$ . We totally have $2q$ function evaluations, the other values in $\left(3.2.5\right)$ being already computed.

By $a^{\prime\prime})-b^{\prime\prime})$ from 3.2. and denoting by $E\left(\gamma_{n+1}\left(q\right),q\right)$ the efficiency of this method, we get:

(29)

E\left(\gamma_{n+1}\left(q\right),q\right)>E\left(\gamma_{n}\left(q\right),q% \right)\quad n\geq 1,\quad q>1;

(30)

\begin{array}[]{c}\left(\max\left\{q,\frac{n+1}{n+2}\left(q+1\right)\right\}% \right)^{\frac{1}{2q}}<E\left(\gamma_{n+1}\left(q\right),q\right)<\left(q+1% \right)^{\frac{1}{2q}},\\ \;n\geq 1,\quad q>1.\end{array}

For a fixed $q$ , by $\left(4.3.1\right)$ it follows that the efficiency index is an increasing function with respect to $n$ and

\lim E\left(\gamma_{n}\left(q\right),q\right)=\left(q+1\right)^{\frac{1}{2q}}.

In the following we shall study $E\left(\gamma_{n}\left(q\right),q\right)$ as a function of $q>1$ and $n\geq 2$ , $q,n\in{\mathbf{N}}$ .

By $\left(4.3.2\right)$ we have

q^{\frac{1}{2q}}<E\left(\gamma_{n+1}\left(q\right),q\right)<\left(q+1\right)^{% \frac{1}{2q}},\text{ for }q\geq n+1

and

(31)

\left[\frac{n+1}{n+2}\left(q+1\right)\right]^{\frac{1}{2q}}<E\left(\gamma_{n+1% }\left(q\right),q\right)<\left(q+1\right)^{\frac{1}{2q}},\text{ for }q<n+1.

For $q\geq n+1$ consider the functions $h:\left(0,+\infty\right)\rightarrow{\mathbf{R}}$ , $h\left(t\right)=t^{\frac{1}{2t}}$ and $l:\left(0,+\infty\right)\rightarrow{\mathbf{R}},\,l\left(t\right)=\left(t+1% \right)^{\frac{1}{2t}}.$

Some elementary considerations show that $h$ and $l$ satisfy $\lim\limits_{t\searrow 0}h\left(t\right)=0,\,\lim\limits_{t\rightarrow\infty}h% \left(t\right)=1,$ $h$ is increasing on $\left(0,e\right)$ and decreasing on $\left(e,+\infty\right)$ and $\lim\limits_{t\searrow 0}l\left(t\right)=e^{\frac{1}{2}},\,\lim\limits_{t% \rightarrow\infty}l\left(t\right)=1,$ $l$ is decreasing on $\left(0,\infty\right)$ . The maximum value of $h$ is $h\left(e\right)=e^{\frac{1}{2e}}$ .

Let $\bar{t}$ be the solution of the equation

(32)

\left(t+1\right)^{\frac{1}{2t}}-e^{\frac{1}{2e}}=0.

It can be easily seen that $\bar{t}$ exists and it is the unique solution for equation $\left(4.3.4\right).$ For $t>\bar{t}$ , $l\left(t\right)>e^{\frac{1}{2e}},$ so it is clear that the maximum value of $E\left(\gamma_{n+1}\left(q\right),q\right)$ can be obtained for $q\leq\bar{t},\,q\in{\mathbf{N}}$ . It is easy to prove that $\bar{t}\in\left(4,5\right)$ and $\bar{t}\simeq 4.76.$ Taking into account the properties of $h$ and $l$ it is clear that in order to determine the greatest value of $E\left(\gamma_{n+1}\left(q\right),q\right)$ it will be sufficient to consider only those $q\in{\mathbf{N}}\,$ verifying $\,1<q\leq 4$ , and $n\leq q-1$ .

Table 4.3.1. contains the approximate values of the efficiency indexes corresponding to these values of $q$ and $n .$

q $\backslash$ n	1	2	3
2	1.2856
3	1.2487	1.2573
4	1.2175	1.2218	1.2226

Table 4.3.1

The highest value for the efficiency index is hence obtained for $q=2$ and $n=1$ . We shall precise explicitly the method $\left(3.2.5\right)$ for these values. For this purpose it is convenient to use the divided differences on multiple nodes. The following table contains the divided differences for the inverse function $f^{-1}$ on the nodes $y_{s}=f\left(x_{s}\right),$ $y_{s+1}=f\left(x_{s+1}\right)$ having the multiplicity orders 2.

$f(x)$	$x$	$[u,v;f^{-1}]$	$[u,v,w;f^{-1}]$	$[u,v,w,z;f^{-1}]$
$y_{s}$	$x_{s}$	$\cdot$	$\cdot$	$\cdot$
$y_{s}$	$x_{s}$	$[y_{s},y_{s};f^{-1}]$	$\cdot$	$\cdot$
$y_{s+1}$	$x_{s+1}$	$[y_{s},y_{s+1};f^{-1}]$	$[y_{s},y_{s},y_{s+1};f^{-1}]$	$\cdot$
$y_{s+1}$	$x_{s+1}$	$[y_{s+1},y_{s+1};f^{-1}]$	$[y_{s},y_{s+1,}y_{s+1};f^{-1}]$	$[y_{s},y_{s},y_{s+1}y_{s+1};f^{-1}]$

Table 4.3.2

Here $[y_{s},y_{s};f^{-1}]=\frac{1}{f^{\prime}\left(x_{s}\right)},\,[y_{s+1},y_{s+1}% ;f^{-1}]=\frac{1}{f^{\prime}\left(x_{s+1}\right)}$ and $[y_{s},y_{s+1};f^{-1}]=\frac{1}{[x_{s},x_{s+1};f]},$ and the other divided differences are computed using the well-known recurrence formula.

In this case the method has the following form:

(33)

\begin{array}[]{c}x_{s+2}=x_{s}-[y_{s},y_{s};f^{-1}]y_{s}+[y_{s},y_{s},y_{s+1}% ;f^{-1}]y_{s}^{2}-\\ -[y_{s},y_{s},y_{s+1},y_{s+1};f^{-1}]y_{s}^{2}y_{s+1},\quad s=1,2,...,\quad x_% {1},x_{2}\in I.\quad\end{array}

The following theorem holds:

Theorem 4.3.6

Among the methods given by relation $\left(3.2.5\right)$ for $n\geq 1$ and $q\geq n+1,$ the method with the highest efficiency index is given by $\left(4.3.5\right)$ , and corresponds to the case $n=1$ and $q=2$ .

We shall analyze the case $q<n+1.$ In this case the efficiency index verifies $\left(4.3.3\right)$ . We also consider, besides the function $l$ already defined, the functions $p_{n}:\left(0,\infty\right)\rightarrow{\mathbf{R}},\,p_{n}\left(t\right)=\left% [\frac{n+1}{n+2}\left(t+1\right)\right]^{\frac{1}{2t}}$ , which satisfy the following properties $\lim\limits_{t\searrow 0}p_{n}\left(t\right)=0,\,\lim\limits_{t\rightarrow% \infty}p_{n}\left(t\right)=1$ and

p_{n}^{\prime}\left(t\right)=\frac{1}{2}\left[\frac{n+1}{n+2}\left(t+1\right)% \right]^{\frac{1}{2t}}\frac{\frac{t}{t+1}-\ln\frac{n+1}{n+2}\left(t+1\right)}{% t^{2}}.

It can be easily shown that the equation $p_{n}^{\prime}\left(t\right)=0$ has a unique positive solution, denoted by $\tau_{n}.$ We also have $p_{n}^{\prime}\left(t\right)>0$ for $t<\tau_{n}$ and $p_{n}^{\prime}\left(t\right)<$ $0$ for $t>\tau_{n},$ i.e. $p_{n}$ attains its maximum value at $t=\tau_{n}.$

We also have that $p_{n+1}\left(\tau_{n}\right)<0$ , showing that $\tau_{n+1}<\tau_{n}$ for all $n\geq 2.$ But since $1<q<n+1$ it follows that we must examine only the cases when $n\geq 2$ . Taking into account that $\tau_{n}$ is the solution of the equation $p_{n}^{\prime}\left(t\right)=0$ we get that the maximum value of the function $p_{n}$ is equal to $e^{\frac{1}{2\left(\tau_{n}+1\right)}}.$

Let $v_{n}:\left(0,+\infty\right)\rightarrow{\mathbf{R}}$ , $v_{n}\left(t\right)=\left(t+1\right)^{\frac{1}{2t}}-e^{\frac{1}{2\left(\tau_{n% }+1\right)}}.$ An elementary reasoning leads us to the following conclusions: $v_{n}$ is decreasing on $\left(0,+\infty\right);$ the equation $v_{n}\left(x\right)=0$ has a unique solution $\mu_{n}$ on the interval $\left(0,+\infty\right)$ and $\mu_{n+1}<\mu_{n}.$

Since for $t>\mu_{n},$ we have $p_{n}\left(\tau_{n}\right)>p_{n}\left(t\right)$ , it follows that the values of $n$ and $q$ for which $E$ attains its maximum must be searched in the set

(34)

\left\{q\in{\mathbf{N}}\mid 2\leq q<\min\left\{n+1,\mu_{n}\right\}\right\}.

Table 4.3.3. below contains the approximate values of the solutions $\tau_{n}$ and $\mu_{n},\;$ the error being smaller than $10^{-2}.$

$n$	$\tau_{n}$	$\mu_{n}$
$2$	$1.3816$	$3.6711$
$3$	$1.1201$	$2.8679$
$4$	$0.9566$	$2.3871$
$5$	$0.8436$	$2.0649$
$6$	$0.7601$	$1.8327$

Table 4.3.3

Since $q\in{\mathbf{N},}$ we shall be interested only in the integer parts of the solutions $\mu_{n}$ .

From the above Table and by $\left(4.3.6\right)$ we can see that $E\left(\gamma_{n+1}\left(q\right),q\right)$ attains its maximum at $q=2$ . Taking into account that $E\left(\gamma_{n}\left(2\right),2\right)<E\left(\gamma_{n+1}\left(2\right),2\right)$ for $n\geq 2$ then we observe that $E$ is increasing with respect to $n$ .

Hence the following theorem holds:

Theorem 4.3.7

Taking $q<n+1$ in $\left(3.2.5\right)$ , the greatest values of the efficiency indexes $E\left(\gamma_{n+1}\left(q\right),q\right)$ , $n\geq 2$ , are obtained for $q=2$ . In this case the efficiency index is increasing with respect to $n$ , and we have

\lim E\left(\gamma_{n}\left(2\right),2\right)=\sqrt[4]{3}.

4.4 Bounds for the efficiency index of the general Hermite-type methods

As it was shown in [6], the method $\left(3.2.2\right)$ have the highest convergence order when the natural numbers $a_{1},a_{2},...,a_{n+1}$ verify the inequalities $a_{1}\leq a_{2}\leq...\leq a_{n+1}$ . More exactly consider the equations:

(35)

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

(36)

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

(37)

t^{n+1}-a_{i_{1}}t^{n}-a_{i_{2}}t^{n-1}-...-a_{i_{n}}t-a_{i_{n+1}}=0,

where $a_{i}\geq 0,\quad i=\overline{1,n+1},\quad\sum\limits_{i=1}^{n+1}a_{i}>1$ and $\left(i_{1},i_{2},...,i_{n+1}\right)$ is an arbitrary permutation of the numbers $1,2,...,n+1$ .

If $a, b, c$ are the corresponding positive solutions for equations $\left(4.4.1\right)-\left(4.4.3\right)$ then the following Lemma holds:

Lemma 4.4.0

If $a_{1}\leq a_{2}\leq...\leq a_{n+1}$ then $1<b\leq c\leq a$ , i.e., among all equations of the form $\left(4.4.3\right),\,$ equation $\left(4.4.1\right)$ has the greatest positive root.

In the following we shall assume that the multiplicity orders of the interpolation nodes of the Hermite polynomial which leads to the method $\left(3.2.2\right)$ satisfy

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

From the above assumptions, at each iteration step there must be performed $2a_{n+1}$ function evaluations. Denoting by $E\left(\delta_{n+1}\right)$ the efficiency index of $\left(3.2.2\right)$ and taking into account Lemma 3.2.1 we get:

Theorem 4.4.9

If $a_{1}\leq a_{2}\leq...\leq a_{n+1}$ and $\delta_{n+1}$ is the positive solution of $\left(3.2.4\right)$ then the efficiency index of the method $\left(3.2.2\right)$ satisfies

(38)

\left(m+1\right)^{\frac{m+1}{2\left[m\left(n+1\right)+P_{n+1}^{\prime}\left(1% \right)\right]a_{n+1}}}\leq E\left(\delta_{n+1}\right)\leq\left(1+a_{n+1}% \right)^{\frac{1}{2a_{n+1}}}.

Taking into account the properties of the function $l$ given in 4.3. and that $a_{n+1}>1$ , it follows that the expression $\left(1+a_{n+1}\right)^{\frac{1}{2a_{n+1}}}$ attains its maximum value for $a_{n+1}=2$ . Taking into account the inequalities from $\left(4.4.4\right)$ the fact that $\left(1+a_{n+1}\right)^{\frac{1}{2a_{n+1}}}$ attains its maximum value at $a_{n+1}=2$ do not imply the maximality of $E\left(\delta_{n+1}\right)$ .

4.5 Optimal Steffensen-type methods

In the following we shall determine the optimal efficiency index for the class of iterative methods given by $\left(3.3.3\right)$ . First, we observe that at each iteration step $s$ in $\left(3.3.3\right)$ , we must compute $n$ values of the function $\varphi$ , $u_{s+i}=\varphi\left(u_{s+i-1}\right)$ , $i=\overline{1,n}$ , $u_{s}=x_{s}$ being an already computed approximation of the solution $\bar{x}$ .

We then compute $\bar{y}_{s+i}=f\left(u_{s+i}\right),\,i=\overline{0,n},$ i.e. $n+1$ function evaluations. In order to compute the successive values of $f$ and $f^{-1}$ at the nodes $u_{s+i},\,i=\overline{0,n}$ we need $2\left(m-n\right)$ function evaluations. Finally, there is another function evaluation in computing the right hand side of $\left(3.3.3\right)$ . Totally there are $2\left(m+1\right)$ function evaluations.

If we denote by $E\left(m\right)$ the efficiency index of $\left(3.3.3\right)$ then

E\left(m\right)=\left(m+1\right)^{\frac{1}{2\left(m+1\right)}},

which, taking into account the results from 4.1., attains its maximum at $m=2$ .

Remark 4.5.5

If we take $a_{i}\geq 1$ in $\left(3.3.3\right)$ , then method $\left(3.3.2\right)$ is a particular case of $\left(3.3.3\right)$ , since for $a_{1}=a_{2}=...=a_{n+1}=1$ in $\left(3.3.3\right)$ we get $\left(3.3.2\right)$ .

By the above remark, if $m=2$ then from $a_{1}+a_{2}+...+a_{n+1}=3$ , it follows $n\leq 2$ . Hence we have to analyze the following cases:

i): $a_{1}+a_{2}+a_{3}=3$ , i.e. $a_{1}=a_{2}=a_{3}=1;$
ii): $a_{1}+a_{2}=3,\,$ i.e. $a_{1}=1,\,a_{2}=2\,$ or $a_{1}=2,\,a_{2}=1;$
iii): $a_{1}=3.$

i) For $a_{1}=a_{2}=a_{3}=1$ , by $\left(3.3.2\right)$ we get the following method:

(39)

\begin{array}[]{c}x_{k+1}=x_{k}-\dfrac{f\left(x_{k}\right)}{\left[x_{k},% \varphi\left(x_{k}\right);f\right]}-\\ \dfrac{\left[x_{k},\varphi\left(x_{k}\right),\varphi\left(\varphi\left(x_{k}% \right)\right);f\right]f\left(x_{k}\right)f\left(\varphi\left(x_{k}\right)% \right)}{\left[x_{k},\varphi\left(x_{k}\right);f\right]\left[x_{k},\varphi% \left(\varphi\left(x_{k}\right)\right);f\right]\left[\varphi\left(x_{k}\right)% ,\varphi\left(\varphi\left(x_{k}\right)\right);f\right]},\;k=0,1,...,\quad x_{% 0}\in I.\end{array}

ii) For $a_{1}=2,\,a_{2}=1$ we get the method

(40)

x_{k+1}=x_{k}-\frac{f\left(x_{k}\right)}{f^{\prime}\left(x_{k}\right)}-\frac{% \left[x_{k},x_{k},\varphi\left(x_{k}\right);f\right]f^{2}\left(x_{k}\right)}{f% ^{\prime}\left(x_{k}\right)\left[x_{k},\varphi\left(x_{k}\right);f\right]^{2}}% ,\,\,k=0,1,...,\;x_{0}\in I

and for $a_{1}=1,\,a_{2}=2$ we get

(41)

\begin{array}[]{c}x_{k+1}=x_{k}-\dfrac{f\left(x_{k}\right)}{\left[x_{k},% \varphi\left(x_{k}\right);f\right]}-\dfrac{\left[x_{k},\varphi\left(x_{k}% \right),\varphi\left(x_{k}\right);f\right]f\left(x_{k}\right)f\left(\varphi% \left(x_{k}\right)\right)}{\left[x_{k},\varphi\left(x_{k}\right);f\right]^{2}f% ^{\prime}\left(\varphi\left(x_{k}\right)\right)},\\ \,k=0,1,...,\;x_{0}\in I.\end{array}

iii) For $a_{1}=3$ we get the method $\left(4.1.1\right)$ , i.e. the Chebyshev’s method of third order.

We have proved the following theorem:

Theorem 4.5.10

Among Steffensen-type iterative methods given by $\left(3.3.3\right)$ , the methods $\left(4.5.1\right)-\left(4.5.3\right)$ have the optimal efficiency index.

Remark 4.5.6

In the particular case when $a_{1}=a_{2}=...=a_{n+1}=q$ the condition imposed to obtain an optimal method leads us to two possibilities, namely: $q=3$ and $n=0$ , i.e. method $\left(4.1.1\right)$ or $q=1$ and $n=2$ , i.e. method $\left(4.5.1\right)$ .

References

[1] R. Brent, S. Winograd, F. Wolfe, Optimal Iterative Processes for Root-Finding, Numer. Math. 20 (1973), 327-341.
[2] Gh. Coman, Some Practical Approximation Methods for Nonlinear Equations, Mathematica - Revue d’Analyse Numérique et de Théorie de l’Approximation, Tome 11, N ${}^{\text{o}}$ 1-2, (1982), 41-48.
[3] H.T. Kung, J.F. Traub, Optimal Order and Efficiency for Iterations with Two Evaluations, SIAM J. Numer. Anal., Vol. 13, N ${}^{\text{o}}$ 1, (1976), 84-99.
[4] A.M. Ostrowski, Solution of Equations and Systems of Equations, Academic Press, New York and London, (1966).
[5] I. Pǎvǎloiu, Bilateral Approximations for the Solutions of Scalar Equations, Revue d’Analyse Numérique et de Théorie de l’Approximation, (23), 1, (1994), 95-100.
[6] I. Pǎvǎloiu, Optimal Problems Concerning Interpolation Methods of Solution of Equations, Publ. Inst. Math., 52 (66) (1992), 113-126.
[7] Traub J.F., Iterative methods for solution of equations, Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1964.
[8] Turowicz B.A., Sur les derivées d’ordre superieur d’une fonction inverse, Ann. Polon. Math. 8 (1960), 265-269.

Optimal efficiency indexes for iterative methods of interpolatory type

Abstract

Authors

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

OPTIMAL EFFICIENCY INDEXES FOR ITERATIVE METHODS OF INTERPOLATORY TYPE ††thanks: AMS Subject Classification (1991): Primary 65Y20, 68Q25, 65H05.††thanks: This work has been supported by the Romanian Academy of Sciences.

Abstract

1 Introduction

2 The convergence order and the efficiency index

Definition 2.0.1

Remark 2.0.1

Lemma 2.0.0

Lemma 2.0.0

Definition 2.0.2

Remark 2.0.2

3 Iterative methods of interpolatory type

3.1 Lagrange-type inverse interpolation

3.2 Hermite-type inverse interpolation

Lemma 3.2.0

Remark 3.2.3

3.3 Steffensen-type iterative methods

Remark 3.3.4

4 Optimal efficiency

4.1 Optimal Chebyshev-type methods

Theorem 4.1.4

4.2 The efficiency of Lagrange-type methods

Theorem 4.2.5

4.3 Optimal Hermite-type particular methods

Theorem 4.3.6

Theorem 4.3.7

4.4 Bounds for the efficiency index of the general Hermite-type methods

Lemma 4.4.0

Theorem 4.4.9

4.5 Optimal Steffensen-type methods

Remark 4.5.5

Theorem 4.5.10

Remark 4.5.6

References

Related Posts

OPTIMAL EFFICIENCY INDEXES FOR ITERATIVE METHODS OF INTERPOLATORY TYPE ^†^†thanks: AMS Subject Classification (1991): Primary 65Y20, 68Q25, 65H05.^†^†thanks: This work has been supported by the Romanian Academy of Sciences.