The inverse interpolation problem, connected with equation solution was essentially approached in [5], [6], [7], [4]. In  [4] it was shown that the most known iteration methods, are: Newton’s method, Chebyshev’s method, chord method, as well as various generalizations of them, which are all obtained by means of Lagrange-Hermite-type inverse interpolations. A classification of these methods according to their order of convergence is not beyond interest. In this paper we propose to solve two extremum problems concerning the order of convergence of the iteration methods obtained by the Lagrange-Hermite-type inverse interpolation and that of the Steffensen-type method which follows from the preceding ones.

The Lagrange-Hermite-type inverse interpolation polynomial with $n+1$ nodes $\left(n\in \mathbb{N}\right),$ each node having a given multiplication order, leads to a class of $\left(n+1\right)!$  iteration methods. Out of this class of methods, we propose to determine the method having the highest order of convergence. In the last part of the paper we solve the same problem for a class of Steffensen-type iteration methods.

Let $f:I\to ℝ$ be a function, where $I$ is an interval of the real axis. Denote by $E$ a set of $n+1$ distinct points from the interval $I$, namely $E=\{x_1,x_2,\mathrm{\dots },x_{n+1}\},$ where $x_i\ne x_j$ for $i\ne j,$ $i,j=1,2,\mathrm{\dots }n+1$.

Consider the natural numbers ${\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_{n+1}$ and suppose that they satisfy

It is a well-known fact that the numbers $y_i^j,j=0,1,\mathrm{\dots },$ ${\alpha }_i=1,i=1,2\mathrm{\dots },n+1$ being given, there exists a unique polynomial $P$, of degree at most $m$, which satisfies the relations

The polynomial $P$ satisfying the conditions (1.2) has the form:

where:

If we suppose that the function $f$ admits derivatives up to the $\left(m+1\right)-th$ order on the interval $I$, and if we put $y_i^j=f^{\left(j\right)}\left(x_i\right),$ $j=0,1,\mathrm{\dots }{\alpha }_i-1,i=1,2\mathrm{\dots },n+1,$ in (1.3), then $P$ is the Hermite interpolating polynomial on the nodes $x_i,i=1,2,\mathrm{\dots },n+1$, associated with the function $f$, and the following equality holds:

with $\xi \in I$.

We shall suppose, in what follows, that $f^{\prime }\left(x\right)\ne 0$ for every $x\in I$ and denote $F=f\left(I\right)$. It follows that $f:I\to F$ is bijective, hence there exists $f^{-1}:F\to I$ and the function $f^{-1}$ admits derivatives up to the $\left(m+1\right)-th$ order, for every $x\in F$.The $k-th$ order derivative, where $k\le m+1,$ can be determined by means of the following formula [7]:

where the above sum is extended over all integral and nonnegative solutions of the system

If we suppose that the equation:

From $f\left(\overline{x}\right)=0$ it follows that $\overline{x}=f^{-1}\left(0\right)$ and the problem of the approximate solution of the equation (1.8) reduces to the determination of an approximation for $f^{-1}\left(0\right)$. Let $\phi$ be a function which approximates the function $f^{-1}$, at least in a neighbourhood $V_0$ of the point $y=0$; thus an approximation formula of the form:

holds on the set $V_0$.

Neglecting  the function $R[f^{-1},y]$ and putting $y=0$ into (1.9), we obtain the following approximation for $\overline{x}$:

with an approximation error given by the inequality

There are two natural conditions to be imposed on the function $\phi$:

• a)

  to approximate the function $f^{-1}\left(y\right)$ as well as possible, i.e. the number $R[f^{-1},0]$ must be as small as possible;

• b)

  to have some simplicity properties for the computation of its values.

The functions which agree with the second condition are (or rather seem so) polynomials, since the computation of their values reduces to elementary arithmetic operations.

Obviously, if we succeed in constructing the best approximating polynomial for $f^{-1}$ on the set $V_0$, then the first condition will be satisfied too.

In what follows we shall not approach the problem from this point of view; therefore the function will be replaced by the Hermite interpolating polynomial associated to the function $f^{-1}$, on the set $F$, called Hermite inverse interpolating polynomial. For this purpose, in the interpolating polynomial (1.3) we consider, as interpolating nodes, the values $y_i=f\left(x_i\right),i=1,2,\mathrm{\dots },n+1$, while for $y_i^j,j=0,1,\mathrm{\dots },{\alpha }_i-1,i=1,2,\mathrm{\dots },n+1$, we consider $y_i^{\left(0\right)}=x_i,i=1,2,\mathrm{\dots },n+1,$ respectively $y_i^{\left(j\right)}={\left(f^{-1}\right)}^{\left(j\right)}\left(y_i\right),i=1,2,\mathrm{\dots },n+1,j=1,2,\mathrm{\dots },{\alpha }_i-1$. In this way the polynomial (1.3) acquires the form:

where:

From (1.5) it follows that

Taking into account the fact that $\overline{x}=f^{-1}\left(0\right),$ from (1.14) one obtains:

where ${\eta }_1$ is a point lying in the shortest interval which contains $0,f\left(x_1\right),f\left(x_2\right),\mathrm{\dots },$ $f\left(x_{n+1}\right).$ Denoting this interval by $F_1$ and putting:

it results, from (1.15),

and since $y_i=f\left(x_i\right),i=1,2,\mathrm{\dots },n+1$,

From (1.17) it follows that if $x_1,x_2,\mathrm{\dots },x_{n+1}$ are chosen sufficiently close to $\overline{x}$, then the values $f\left(x_1\right),f\left(x_2\right),\mathrm{\dots },f\left(x_{n+1}\right)$ are real numbers close to zero; so much more the product ${\prod }_{i=1}^{m+1}{\left|f\left(x_i\right)\right|}^{{\alpha }_i}$ will be close to zero. This remark allows us to consider the value $P\left(0\right)$ as an approximation for $\overline{x}$ the root of the equation (1.8).

If $P\left(0\right)$ is not a good enough approximation for $\overline{x}$, then we can construct, by iterations, a sequence of approximations ${\left(x_k\right)}_{k\ge 1}$, which, under certain conditions, will be convergent, and $lim{x}_k=\overline{x}$.

More precisely, let $x_1,x_2,\mathrm{\dots },x_{n+1}$ be $n+1$ approximations of the root $\overline{x}$ of the given equation (1.8). We denote $x_{n+2}=P\left(0\right)$ and replace one of the $n+1$ nodes $x_1,x_2,\mathrm{\dots },x_{n+1}$, then continue the iteration process by the above described procedure.

The problem which arises is to determine the interpolating node which should be replaced at each iteration step in order to obtain a sequence of approximations ${\left(x_k\right)}_{k>1}$ with a maximum order of convergence. To solve the problem, let us consider the following equations:

where a${}_1{}^{},a_2,\mathrm{\dots },a_{n+1}$ are real numbers satisfying the conditions:

while $i_1,i_2,\mathrm{\dots },i_{n+1}$ is an arbitrary permutation of the numbers $1,2,\mathrm{\dots },n+1$.

The following lemma holds:

Consider now the permutation $i_1,i_2,\mathrm{\dots },i_{n+1}$ of the numbers $1,2,\mathrm{\dots },n+1$ for which the natural numbers ${\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_{n+1}$ satisfying the equality (1.1), can be increasingly ordered, namely:

We renumber, accordingly, the elements of the set $E,$ i.e. we consider:

For the sake of clearness we shall set:

and

and denote by $H(y_1;a_1,y_2;a_2,\mathrm{\dots },y_{n+1};a_{n+1};f^{-1}|x)$ the Hermite interpolating polynomial, corresponding to the nodes $y_i=f\left(u_i\right),i=1,2,\mathrm{\dots },n+1$  having the multiplicities $a_1,a_2,\mathrm{\dots },a_{n+1}$ respectively.

From (1.17) we obtain

where $M_{m+1}$ has the same meaning as in (1.15).

Let $u_1,u_2,\mathrm{\dots },u_{n+1}$ be the $n+1$ initial approximations of the root $\overline{x}$ of the equation (1.8). We construct the sequence ${\left(u_p\right)}_{p\ge 1}$ by means of the following iterative procedure:

Denoting $M={sup}_{y\in F}\left|{\left[f^{-1}\left(y\right)\right]}^{\left(m+1\right)}\right|$ and $\beta ={sup}_{x\in I}\left|f^{\prime }\left(x\right)\right|,$ we obtain from (1.27) and (1.28):

Denoting ${\rho }_i=\beta \sqrt[m]{\beta M/\left(\left(m+1\right)!\right)}\left|\overline{x}-u_i\right|,i=1,2,\mathrm{\dots },$ we obtain from (1.29):

Suppose that there exists a $d\in ℝ$, , such that:

where $\omega$ is the positive root of the equation (1.18). That number is called the convergence order of the method (1.28).

If we suppose that:

then, taking into account (1.30) and the fact that $\epsilon$ is a root of the equation (1.18), we derive the inequality:

which is valid for every $s=1,2,\mathrm{\dots }.$

Taking into account the expression for ${\rho }_{n+s+1}$, we obtain the following inequality for the error evaluation:

from which it follows that ${lim}_{n\to \mathrm{\infty }}{u}_p=\overline{x}$.

Observe that both the error evaluation and the convergence speed of the method (1.28) depend on the root $\omega$ of the equation (1.18). The greatest $\omega$ is, the better the upper limit obtained for the error is.

Consider all $\left(n+1\right)!$ permutations of the set $\{1,2,\mathrm{\dots },n+1\}.$ To each permutation $i_1,i_2,\mathrm{\dots },i_{n+1}$ it corresponds an iterative method of the form:

All together we have $\left(n+1\right)!$ iterative methods.

Taking into account Lemma 1 and the results proved so far, we can state the following theorem:

In what follows we shall discuss some particular cases.

Case $n=0.$ From (1.12) one obtains the Taylor inverse interpolating polynomial:

while, from (1.6), we obtain the following expressions for the successive derivatives ${\left[f^{-1}\left(y\right)\right]}^{\left(k\right)},$ $k=1,2,3,4:$

From (2.2) and (2.1) for ${\alpha }_1=2$ we obtain:

From (2.2), (2.3)  and (2.1) for ${\alpha }_1=3$ we obtain Chebyshev’s method, i.e.:

Lastly, from (2.2), (2.3), (2.4) and (2.1) for ${\alpha }_1=4$ we obtain:

From the above methods one obtains by iterations the corresponding sequence of approximations, which has the order of convergence 2, 3 and 4 respectively.

As one may notice from (2.5) and (1.6), for ${\alpha }_1\ge 5$ the expressions for the derivatives ${\left[f^{-1}\left(y\right)\right]}^{\left(k\right)},k\ge 4,$ have a more complex form. That is why the methods following from (2.1) in these cases are also complex.

Case $n=1.$ In this case, from (1.12) it follows:

where:

From (2.9) one obtains two iterative methods; namely denoting as above by $H(y_1;{\alpha }_1,y_2;{\alpha }_2;f^{-1}|y)$ the Hermite inverse interpolating polynomial (2.9), we find:

or

The characteristic equations which provide the convergence orders for the two methods are

Now, we shall briefly discuss some particular cases.

From (2.9), for ${\alpha }_1={\alpha }_2=1,$ we obtain

wherefrom, taking into account the fact that $f^{-1}\left(y_1\right)=x_1$and $f^{-1}\left(y_2\right)=x_2$, we find for $y=0$

where $[x_1,x_2;f]$ stands for the first order divided difference of the function $f$ on the nodes $x_1$ and $x_2$, and

which is the chord method. In this case, since ${\alpha }_1={\alpha }_2,$ the above method has the same convergence order as the other one, which follows from (2.12), i.e.:

The order of convergence of the method (2.17) is ${\omega }_1=\frac{1}{2}\left(1+\sqrt{5}\right).$

Now we shall discuss the case ${\alpha }_1=1,$ ${\alpha }_2=2$. In this particular case, we obtain from (2.9) the following iterative methods:

and

Solving the corresponding characteristic equations, we find the convergence orders ${\omega }_1=1+\sqrt{2}$ for the method (2.19) and ${\omega }_2=2$ for the method (2.20).

As we showed above, the Hermite inverse interpolating polynomial leads to a large class of iterative methods. The convergence order of each method depends on the number of interpolating nodes, the order of multiplicity of these ones, and, essentially, on the interpolating node replaced at each iteration step by that calculated at the precedent one.

As Steffensen notices, in the case of the method (2.17), the convergence order of this method can be increased if at each iteration step the element $x_n$ depends in a certain manner on $x_{n-1}$. More exactly, if we consider a function $\phi :I\to ℝ$, having the property $\phi \left(\overline{x}\right)=\overline{x}$, where $\overline{x}$ is the root of the equation (1.8), and if we put $x_n=\phi \left(x_{n-1}\right)$ into (2.17), then we obtain the sequence ${\left(x_n\right)}_{n\ge 1}$ generated by Steffensen’s method:

which has, as it is well known, the convergence order 2.

Now let ${\phi }_i:I\to ℝ$, $i=1,2,\mathrm{\dots },n+1,$ be $n+1$ functions satisfying the following conditions:

• a)

  ${\phi }_i\left(\overline{x}\right)=\overline{x},i=1,2,\mathrm{\dots },n+1$, where $f\left(\overline{x}\right)=0;$

• b)

  there exist real numbers ${\rho }_i\ge 0$ and $p_i>1,i=1,2,\mathrm{\dots },n+1$ such that the functions ${\phi }_i$ and $f$ satisfy the relations:

  (3.1)

  $$\left|f\left({\phi }_i\left(x\right)\right)\right|\le {\rho }_i{\left|f\left(x\right)\right|}^{p_i},i=1,2,\mathrm{\dots },n+1.$$

Denote by $u_0\in I$ an initial approximation of the root $\overline{x}$ of the equation (1.8).

We construct $n+1$ interpolating nodes $x_i^1,i=1,2,\mathrm{\dots },n+1,$ as follows: