As we have shown in [7], the problem of determining the Hermite interpolatory iterative methods having the optimal efficiency index cannot be solved in the general case. We have determined however in [7] some upper and lower bounds for the efficiency indexes; these bounds depend on the coefficients of the characteristical equation whose positive root provide the convergence order of the considered equation.

In this note we shall consider a subclass of Hermite interpolatory methods, based on two interpolatory nodes which have the same multiplicity order $q\in \mathbb{N}.$ We shall use the efficiency index defined in [4] for determining the method with the optimal efficiency index.

Let $I=[a,b],$ $a,b\in ℝ,$ $f:I\to ℝ$  and consider the equation

We assume that this equation has a unique solution $\overline{x}\in ]a,b[.$ For solving the above equation we consider a function $g:I\to I$ and we also assume that $\overline{x}$ is the unique fixed point of $g$ in $I.$

For approximating $\overline{x}$ there is usually taken an element from the sequence ${\left(x_s\right)}_{s\ge 0}$ generated by the iterative method:

More generally, if $h:I^k\to I$ is a function of $k$ variables whose restriction to the diagonal of the set $I^k$ coincides with $g,$ then the following sequence may be considered for approximating $\overline{x}:$

The convergence of the sequence ${\left(x_s\right)}_{s\ge 0}$ generated by (2) or (3) depends on certain properties of the functions $f,g$ and resp. $h$. The time needed by a computer to obtain a convenient approximation of $\overline{x}$ depends on the convergence order of the sequence ${\left(x_s\right)}_{s\ge 0}$ and also on the number of elementary operations performed at each iteration step.

While the convergence order may be determined exactly in most of the situations, the number of elementary operations may be hard to evaluate.

For this reason Ostrowski has proposed in [4] a simplification of this problem, by considering the number of function evaluations needed at each iteration step. This leads to the definition of the efficiency index, which may be naturally applied to the comparison of different methods.

Consider a sequence ${\left(x_s\right)}_{s\ge 0},$ which together with $f$ and $g$ satisfies:

a) $x_s\in I;$ for all $s=0,1,\mathrm{\dots }$

b) ${\left(x_s\right)}_{s\ge 0}$ converges to $\overline{x};$

c) the sequence ${\left(g\left(x_s\right)\right)}_{s\ge 0}$ converges also to $\overline{x};$

d) $f\left(\overline{x}\right)=0;$

e) $f$ is derivable at $\overline{x};$

f) for all $x,y\in I$ there exists $m\in {ℝ}_{+}$ such that where $[x,y;f]$ denotes the divided differences of $f$ on the nodes $x$ and $y.$

Concerning the convergence order of ${\left(x_s\right)}_{s\ge 0},$ we shall consider the following definition:

then $\omega$ is the positive root of the equation

We shall denote in the following by $m_s$ the number of function evaluations that must be performed at the step $s$ for the iteration (2) or (3).

Taking into account Lemmas 1 and 2, the following definition becomes natural:

Remark.  If there exist $s_0\in \mathbb{N}$ such that for $s>s_0$ the values $m_s$ are constant, $m_s=r,$ then the efficiency index is given by relation

Let $q\in \mathbb{N},$ $q\ge 1$ be a natural number and consider the Hermite inverse interpolatory polynomial on two nodes with the same multiplicity order $q.$

We shall make the following assumptions concerning the function $f:$

$\alpha$) $f$ is derivable on $]a,b[$ up to and including the $2q$ - th order;

$\beta$) $f^{\prime }\left(x\right)\ne 0$ for all $x\in ]a,b[$;

$\gamma$) equation (1) has a solution $\overline{x}\in ]a,b[.$

Under this assumptions, it is clear that $f$ admits an inverse $f^{-1}:D\to I,$ where $D=f\left(I\right),$ and also that $\overline{x}$ is given by relation

Moreover, $f^{-1}$ is derivable up to the order $2q$ at all points from $D$ and the $k$ - th derivative, for $k\in \mathbb{N},$ $1\le k\le 2q$ is given by [9].

where we have denoted $y=f\left(x\right),$ and the above sum extends on the nonnegative whole solutions of the system

Denote by $H(y_1,q;y_2,q;f^{-1}|y)$ the Hermite inverse interpolatory polynomial satisfying

where ${\left[f^{-1}\left(y_i\right)\right]}^{\left(0\right)}=f^{-1}\left(y_i\right),$ $i=1,2$ and $y_1,y_2\in D.$

Consider also the polynomial

The residual in the interpolation formula becomes then

where ${\theta }_1$ belongs to the smallest open interval determined by the points $y,y_1$ and $y_2.$

Let $x_s,x_{s+1}\in I$ be two approximations of the solution $\overline{x}.$ Then the next approximation may be determined by

We shall assume that all the elements of the sequence ${\left(x_s\right)}_{s\ge 0}$ generated by (7) belong to the interval $I.$

Taking into account the above assumptions we easily get for $s=0,1,\mathrm{\dots }$ that

where ${\alpha }_s$ belongs to the open interval determined by the points $\overline{x}$ and $x_{s+2},$ and ${\theta }_s$ is contained in the open interval determined by $0,y_s,y_{s+1}.$

Assuming that ${\left[f^{-1}\left(y\right)\right]}^{\left(2q\right)}\ne 0$ for all $y\in intD,$ denoting

and applying Lemma 2, we obtain the following equation for determining the convergence order of method (7):

It follows that the convergence order is

We remark that in order to generate the elements of the sequence ${\left(x_s\right)}_{s\ge 0}$ given by (7), at each iteration step $s,s\ge 2,$ the following function evaluations are needed:

all at $x_s,$ since their values at $x_{s-1}$ are know from the previous step. Hence there are needed $q$ function evaluations.

Remark. Taking into account that the Hermite inverse interpolatory polynomial is computed with the aid of the succession derivatives of $f^{-1},$ which, by (5) have a rather complicated form, then it becomes necessary to take into account $q-1$ more function evaluations. On the other hand, the evaluation of the Hermite polynomial determined by (6) may lead us to the consideration of a one more function evaluation. We can therefore conclude that at each iteration step there is necessary an amount of $2q$ function evaluations. These considerations may affect the value of the efficiency index, but we shall see in the following that the optimal efficiency index is not affected by considering a number of function evaluations proportional with $q.$

Indeed, considering the number of function evaluations as being equal to $\delta q,$ $\delta$ being a positive constant, then by (4), the efficiency index of method (7) is

The value of $q$ for which $E$ attains the upper bound is given by the solution of ${\phi }^{\prime }\left(q\right)=0,$ and we see bellow that this solution does not depend on $\delta .$

By (8) we get

Since $\phi \left(q\right)>0,$ it follows that equation ${\phi }^{\prime }\left(q\right)=0$ is equivalent with the following one

whence we get

For solving this equation denote $t=q+\sqrt{q^2+4q}$ and we notice that $\frac{dt}{dq}>0$ for $q>0.$ By this substitution, equation (9) becomes

and since for $t>0,$ it follows that equation $\eta \left(u\right)=0$ has a unique positive solution $\overline{t}.$ We also notice that $\eta \left(2\right)=\frac{2}{3}>0$ and i.e. which lead us to the conclusion that the positive root $\overline{q}$ of equation ${\phi }^{\prime }\left(q\right)=0$ satisfies

and whence

We also remark that $\eta \left(t\right)>0$ for $1\le t\le \overline{t}$ and for so it follows that ${\phi }^{\prime }\left(q\right)>0$ for and for $q>\overline{q}.$ The function $E=\phi \left(q\right)$ has at $q=\overline{q}$ a maximum value. It remains to compute the maximum value of $E$ in the set of natural numbers from the neighborhood of the real number $\overline{q}.$ By (10), the value of $q$ for which $E$ attains the maximum belong to the set $\{1,2,3\}.$ One can easily check that and $\phi \left(2\right)>\phi \left(3\right),$ which imply that $E$ attains the maximum value for $q=2.$

We have proved the following theorem:

Finally we give for $H$ an expression based on the divided differences on double nodes (see [6]).

where $y_s=f\left(x_s\right),$ $y_{s+1}=f\left(x_{s+1}\right).$

For computing the divided differences from (3) one can use the recurrence formula for divided differences with the aid of the following table:

where $y_s=f\left(x_s\right),y_{s+1}=f\left(x_{s+1}\right),$ $[y_s,y_s;f^{-1}]=\frac{1}{f^{\prime }\left(x_s\right)},[y_s,y_{s+1};f^{-1}]=\frac{1}{[x_s,x_{s+1};f]}$
and $[y_{s+1},y_{s+1};f^{-1}]=\frac{1}{f^{\prime }\left(x_{s+1}\right)}.$