This note is a continuation of the paper [5]. We shall establish here the optimal methods for the efficiency index of the class of Steffensen-type methods.

We adopt the efficiency index of an iterative process as being the number $I(\omega ,p)$ given in [2] by:

where $\omega$ is the convergence order of the iterative method and $p$ represents the number of function evaluations that must be performed at each step. As it results from [2] and [5], the efficiency index can be defined as in (1) if we admit that the number of function evaluations is constant beginning from a certain step.

Let $I\subset R$ denote an interval of the real axis, and consider equation

where $f:I\to R$. Suppose that equation (2) possesses a unique root $\overline{x}\in I$. Also suppose that $f$ admits derivatives up to the order $m+1,m\in \mathbb{N}$, the $\left(m+1\right)$-th derivative of $f$ is bounded on $I$, and $f^{\prime }\left(x\right)\ne 0$ for all $x\in I$. If $F=f\left(I\right)$, then there exists the function $f^{-1}:F\to I$ and $\overline{x}=f^{-1}\left(0\right)$.

It is obvious that for approximating the solution of (2) it is sufficient to approximate $f^{-1}$ at $y=0$.

From the derivability hypotheses concerning $f$ it follows that $f^{-1}$ also possesses derivatives up to the order $m+1$, which are given by [3]:

In order to establish the optimal efficiency index of the class of Steffensen methods we shall adopt, as in [5], the following assumptions:

We consider as a function evaluation:

a) the evaluation of the function or of any of its derivatives at a certain point;

b) the evaluation by (3) of any of the derivatives of $f^{-1}$ at a certain point;

c) the evaluation of $g$ from (5) at a certain point.

Let

be $n+1$ interpolation nodes from $I$ and

the values of $f$ at $x_i,y_i=f\left(x_i\right),i=\overline{1,n+1}$.

Consider $n+1$ natural numbers $a_1,a_2,\mathrm{\dots },a_{n+1}$ such that $a_i\ge 1i=\overline{1,n+1}$, and $a_1+a_2+\mathrm{\dots }+a_n+a_{n+1}=m+1$. Supposing that at each $x_i,i=\overline{1,n+1}$, we know that values of $f$ and of its derivatives up to the order $a_i-1,$ i.e. we know $f\left(x_i\right),f^{\prime }\left(x_i\right),\mathrm{\dots },f^{\left(a_i-1\right)}\left(x_i\right)$, by (3) we can get the values of $f^{-1}$ and of its derivatives up to the order $a_i-1$.

We can now construct the Hermite inverse interpolation polynomial corresponding to $f^{-1}$, nodes (7), i.e. the following polynomial exists and is unique:

where

If $x_{n+2}$ denotes the value of $H$ at $y=0$ we have

where

If $x_k,x_{k+1},\mathrm{\dots },x_{k+n}\in I$ are $n+1$ approximations of $\overline{x}$, then a new approximation $x_{k+n+1}$ can be obtained by (8):

with the error evaluation

Method (11) is called Hermite-like iterative method.

Consider a function $\phi :I\to I$ whose fixed point from $I$ is $\overline{x}$ i.e. $\phi \left(\overline{x}\right)=\overline{x}$, and suppose there exists a real number $\alpha >0$ such that

Let ${\phi }_1\left(x\right)=\phi \left(x\right),{\phi }_2\left(x\right)=\phi \left({\phi }_1\left(x\right)\right),{\phi }_3\left(x\right)=\phi \left({\phi }_2\left(x\right)\right),\mathrm{\dots },{\phi }_n\left(x\right)=\phi \left({\phi }_{n-1}\left(x\right)\right),$ be the iterations up to the order $n$ of the function $\phi$.

To increase the convergence order of method (11) we can do as if follows.

Let $x_k\in I$ be a certain approximation of the solution $\overline{x}$ of equation (2) and $u_k=x_k,u_{k+1}={\phi }_1\left(x_k\right),\mathrm{\dots },u_{n+k}={\phi }_n\left(x_k\right)$. Consider the values ${\overline{y}}_i=f\left(u_i\right)i=\overline{k,n+k}$ as interpolation nodes in (8). Then $x_{k+1}$, the next approximation of $\overline{x}$, is given by:

Repeating this process, called Steffensen type iterative method, we obtain a sequence ${\left(x_n\right)}_{n\ge 0}$ of approximations of $\overline{x}$.

Using (13) and (12) it can be easily seen that the convergence order of (14) is $m+1$.

As it can be seen above, at each iteration step in (14) we have the following function evaluations:

1) $n$ values of $\phi$ to obtain the interpolation nodes $u_{k+i},i=\overline{1,n}$;

2) $n+1$ values of $f$ at the nodes $u_{k+i},i=\overline{0,n}$;

3) at each interpolation node $u_{k+i},i=\overline{0,n}$ we compute the values of successive derivatives of $f$ up to the order $a_{i+1}-1$, altogether $m-n$ function evaluations:

4) by (3) we evaluate the successive derivatives of $f^{-1}$ at ${\overline{y}}_{k+1}=f\left(u_{k+i}\right),i=\overline{0,n}$ up to the order $a_{i+1}-1,$ altogether $m-n$ function evaluations;

5) finally, consider (14) as a single function evaluation.

Summing up, we obtain altogether $2\left(m+1\right)$ function evaluations.

Using (1) we obtain the following expression for the efficiency index of the class of Steffensen-type methods:

Elementary considerations on the behaviour of the function $h:(0,\mathrm{\infty })\to ℝ,h\left(t\right)=t^{\frac{1}{2t}}$ lead us to the conclusion that the function $I(m+1,2\left(m+1\right))$ attains its maximum at $m=2$.

Note that the efficiency index (15) does not depend on the number of interpolation nodes.

From $m=2$ and $a_1+a_2+\mathrm{\dots }+a_{n+1}=m+1,a_i\ge 1i=\overline{1,n+1}$ it follows that $n\le 2$.

We shall successively analyse all the cases that lead us to the optimal methods form (14).

A. $a_1+a_2+a_3=3,$ i.e. $a_1=a_2=a_3=1$. Then (8) becomes the Lagrange’s inverse interpolation polynomial, and (14) is written:

$x_0\in I,k=0,1,\mathrm{\dots },$ where $[u,v;f]$ respectively $[u,v,w;f]$ denote the first, respectively the second order divided differences of $f$.

B. $a_1+a_2=3,$ i.e. $a_1=2,$ $a_2=1$ or $a_1=1$ and $a_2=2$. When $a_1=2,$ $a_2=1$ we obtain the following method:

$x_0,\in I,k=0,1,\mathrm{\dots },$ and when $a_1=1,a_2=2$ it follows:

$x_0\in I,k=0,1,\mathrm{\dots }$

C. $a_1=3$. In this case we get from (14) the third order Chebyshev iterative method, studied in [5].

In conclusion, the following theorem holds: