In this paper we study the local convergence of some general methods of Aitken-Steffensen type, which are based on inverse interpolation of Lagrange type.

Let $f:[a,b]\to ℝ$, $a,b\in ℝ$, be a function and $x_i$, $i=\overline{0,n}$, $n+1$ distinct points in $[a,b]$, which we call interpolation nodes. Denote $y_i=f\left(x_i\right)$, $i=\overline{0,n}$, and suppose that $y_i\ne y_j$ for $i\ne j$. Assume in the beginning that $f:I\to f\left(I\right)$, $I=[a,b]$ is one-to-one, i.e., there exists $f^{-1}:f\left(I\right)\to I$. Consider the Lagrange polynomial with the interpolation nodes $y_i$, $i=\overline{0,n}$ and the values of $f^{-1}$ on these nodes $x_i=f^{-1}\left(y_i\right)$, $i=\overline{0,n}$. This is the inverse interpolation polynomial, which we denote by $L(y_0,y_1,\mathrm{\dots },y_n;f^{-1}|y)$, and it can be represented in the Lagrange form

and in the Newton form:

where $[y_0,\mathrm{\dots },y_i;f^{-1}],i=\overline{1,n}$ denotes the $i$-th order divided difference of the function $f^{-1}$ on the nodes $y_0,\mathrm{\dots },y_i$.

Assuming that $f$ admits derivatives up to the order $n+1$ on the interval $[a,b]$, then

where $\xi$ is a point belonging to the smallest interval containing $y,y_0,\mathrm{\dots },y_n$. Denote

Consider now the equation

If it has a solution $\overline{x}\in [a,b]$, then obviously

An approximation of the solution $\overline{x}$ can be obtained from (3) for $y=0$, i.e.,

whence, by neglecting the remainder $R_n[f^{-1},0]$ we get

and the error

Denoting $M=\underset{y\in f\left(I\right)}{sup}\left|{\left[f^{-1}\left(y\right)\right]}^{\left(n+1\right)}\right|$, then

Assuming that $x_{n+1}\in [a,b]$ and denoting $y_{n+1}=f\left(x_{n+1}\right)$, then we can obtain a new approximation $x_{n+2}$ given by relation

where, as it can be seen, the node $x_0$ has been neglected and instead we consider $y_{n+1}$. The above procedure may continue indefinitely: assuming that we have obtained the approximations $x_k,x_{k+1},\mathrm{\dots },x_{k+n}\in [a,b]$ then the next approximation is given by

where $y_{k+i}=f\left(x_{k+i}\right)$, $i=\overline{0,n}$. If all the iterates are contained in $[a,b]$, then the procedure may continue indefinitely.

In the same way as for (9), we get the following error bound:

Assume that $f^{\prime }\left(x\right)\ne 0,\forall x\in [a,b]$, and denote

Obviously

By (12) and (13)

Multiplying relations (14) by ${\left(\frac{mM}{(n+1)!}\right)}^{\frac{1}{n}}$ and denoting

leads to

Suppose now that ${\rho }_i\le d^{{\alpha }_i}$, with and ${\alpha }_i\in ℝ$, ${\alpha }_i>0,$ $i=\overline{0,n}$. Then

where

In general, from (15) it follows

where

Let now $t_0>0$ be the unique positive solution of equation

Assume that the values of $f$ obey

for a certain constant $\alpha >0$, i.e., ${\alpha }_i=\alpha t_0^i$. Then one can show by induction using (19) that

In [8] it is shown that $t_0$ verifies . It is clear that the convergence order of the sequence given in (11) is less than 2.

In order to increase the convergence order of the sequence we proceed as follows. Consider the following equation, equivalent to (4):

We shall choose the interpolation nodes in (11) using $g$, generalizing in this way the Steffensen method.

Assume in the beginning that for all $x\in [a,b]$, it follows that $g\left(x\right)\in [a,b]$.

Let $u_0\in [a,b]$ be an initial approximation of the solution $\overline{x}$ of equation (14). We shall use the following notations:

which, by (7) lead to a new approximation for $\overline{x}$

where $y_i=f\left(x_i\right),i=\overline{0,n}$, $x_i$ being given by (24).

From (9) we get:

whence, by (13) we get

Assume that $g$ obeys the Lipschitz condition on $[a,b]$, i.e. there exists $l>0$ such that

Under this hypothesis, taking into account (24), we are lead to

Let now $u_1$ be the next approximation for $\overline{x}$; then, analogously to (24), we consider in (7) the following values to $f^{-1}$ at the interpolation nodes:

In the same way as above, we obtain the next approximation $u_2$ for $\overline{x}$, which satisfies

In general, if $u_k$ is an approximation of $\overline{x}$ and we set

then by (7) we obtain the next approximation $u_{k+1}$, which satisfies

Denoting ${\delta }_k=m{l}^{\frac{n+1}{2}}{\left(\frac{Mm}{\left(n+1\right)!}\right)}^{\frac{1}{n}}\left|\overline{x}-u_k\right|$, then from the above relation we deduce

which leads to the conclusion that for $n\ge 1$, method (11) converges superlinearly. Moreover, if $x_0$ is chosen such that then ${lim}_{k\to \mathrm{\infty }}{\delta }_k=0$ and therefore ${lim}_{k\to \mathrm{\infty }}{u}_k=\overline{x}.$

The error at each step is bounded by:

In the following we analyze two particular cases.

1. (1)

   Case $n=1$. In this case (11) leads to the well known Steffensen method.

   Indeed, by (2) we get

   (32)

   $$L[y_0,y_1{f}^{-1}|y]=x_0+[y_0,y_1;f^{-1}]\left(y-y_0\right),$$

   hence, taking into account the equality

   $$[y_0,y_1;f^{-1}]=\frac{1}{[x_0,x_1;f]},$$

   for $y=0$ we obtain the approximation

   (33)

   $$x_2=x_0-\frac{f\left(x_0\right)}{[x_0,x_1;f]},$$

   i.e., the first step in the chord method.

   Obviously, (9) may continue by

   (34)

   $$x_k=x_{k-2}-\frac{f\left(x_{k-2}\right)}{[x_{k-2},x_{k-1};f]},k=2,3,\mathrm{\dots }.$$

   Denoting in (33) $x_0=u_0$ and $x_1=g\left(u_0\right)$, we get

   $$u_1=u_0-\frac{f\left(u_0\right)}{[u_0,g\left(u_0\right);f]}$$

   and in general

   (35)

   $$u_k=u_{k-1}-\frac{f\left(u_{k-1}\right)}{[u_{k-1},g\left(u_{k-1}\right);f]},$$

   which is precisely the Steffensen method.

   In this case, the elements of the sequence ${\left({\delta }_k\right)}_{k\ge 0}$ have the form

   $${\delta }_k=\frac{l{m}^{2}M}{2}\left|\overline{x}-u_k\right|,k=0,1,\mathrm{\dots },M=\underset{y\in f\left(I\right)}{sup}\left|{\left(f^{-1}\left(y\right)\right)}^{\prime \prime }\right|$$

   and obey

   $${\delta }_{k+1}\le {\delta }_k^2,k=0,1,\mathrm{\dots }.$$

   If , then obviously

   $$\underset{k\to \mathrm{\infty }}{lim}{\delta }_k=0$$

   and hence $lim{x}_k=\overline{x}$, with the error

   $$\left|x_k-\overline{x}\right|\le \frac{2}{l{m}^{2}M}{\delta }_0^{2^k},k=1,2,\mathrm{\dots },$$

   whence (35) converges quadratically.

2. 2.

   Case $n=2$

   It can be easily seen that the second order divided difference
   $[y_0,y_1,y_2;f^{-1}]$ can be expressed as

   (36)

   $$[y_0,y_1,y_2;f^{-1}]=\frac{-[x_0,x_1,x_2;f]}{[x_0,x_1;f][x_0,x;f][x_1,x_2;f]}.$$

   By (2) we get

   	$L[y_0,y_1,y_2;f^{-1}|y]=$	$x_0+[y_0,y_1;f^{-1}]\left(y-y_0\right)$
   		$+[y_0,y_1,y_2;f^{-1}]\left(y-y_0\right)\left(y-y_1\right).$

   Setting $y=0$ and taking into account (36) and the corresponding formula for the first order divided difference, we are lead to

   (37)

   $$x_3=x_0-\frac{f\left(x_0\right)}{[x_0,x_1;f]}-\frac{[x_0,x_1,x_2;f]f\left(x_0\right)f\left(x_1\right)}{[x_0,x_1;f][x_1,x_2;f][x_1,x_2;f]},$$

   i.e., to a method correcting the chord method.

   In general, a method of type (37) has the form

   (38)

   $x_{n+3}$

   $=x_n-\frac{f\left(x_n\right)}{[x_n,x_{n+1};f]}-\frac{[x_n,x_{n+1},x_{n+2};f]}{[x_n,x_{n+1};f][x_{n+1},x_{n+2};f][x_n,x_{n+2}f]},$

   $n=0,1,\mathrm{\dots }$. If in (37) we control the interpolation nodes as

   $$x_0=u_0,x_1=g\left(x_0\right),x_2=g\left(x_1\right)=g\left(g\left(x_0\right)\right)$$

   we obtain

   $u_1=$

   $u_0-\frac{f\left(u_0\right)}{[u_0,g\left(u_0\right);f]}-\frac{[u_0,g\left(u_0\right);g\left(g\left(u_0\right)\right);f]f\left(u_0\right)f\left(g\left(u_0\right)\right)}{[u_0,g\left(u_0\right);f][u_0,g\left(g\left(u_0\right)\right);f][g\left(u_0\right),g\left(g\left(u_0\right)\right);f]}.$

   In general, if $u_k$ is an approximation to $\overline{x}$, then $u_{k+1}$ is given by

   (39)

   $u_{k+1}$

   $=u_k-\frac{f\left(u_k\right)}{[u_k,g\left(u_k\right);f]}-\frac{[u_k,g\left(u_k\right),g\left(g\left(u_k\right)\right);f]f\left(u_k\right)f\left(g\left(u_k\right)\right)}{[u_k,g\left(u_k\right);f][u_k,g\left(g\left(u_k\right)\right);f][g\left(u_k\right),g\left(g\left(u_k\right)\right);f]}.$

   Denoting $M={sup}_{y\in f\left(I\right)}\left|{[f^{-1}(y)]}^{\prime \prime \prime }\right|,$ then the error satisfies at each iteration step:

   (40)

   $$\left|u_k-\overline{x}\right|\le \frac{\sqrt{6}}{m{l}^{3/2}\sqrt{mM}}{\delta }_0^{3^k},$$

   where

   $${\delta }_0=\frac{m{l}^{3/2}\sqrt{Mm}}{\sqrt{6}}\left|\overline{x}-u_0\right|.$$

   Assuming , then ${lim}_{k\to \mathrm{\infty }}{u}_k=\overline{x}$, with the convergence order at least $3$.

   Suppose in the following that the function $g$ given by (23) has derivatives up to the $p$-th order, $p\in \mathbb{N},$ $p\ge 2$, on $[a,b]$ and its derivatives satisfy

   (41)

   $$g^{\left(i\right)}\left(\overline{x}\right)=0,i=\overline{1,p-1},g^{\left(p\right)}\left(\overline{x}\right)\ne 0.$$

   In this case, if the derivative of $p$-th order in continuous on $[a,b]$ and

   $$L=\underset{x\in [a,b]}{sup}\left|g^{\left(p\right)}\left(x\right)\right|,$$

   then for all $x\in [a,b]$ one has

   (42)

   $$\left|g\left(\overline{x}\right)-g\left(x\right)\right|\le \frac{L}{p!}{\left|\overline{x}-x\right|}^p.$$

   Using the above relation (27) we get

   (43)

   $$\left|\overline{x}-u_1\right|\le \frac{M{m}^{n+1}}{\left(n+1\right)!}{\left(\frac{p!}{L}\right)}^{\frac{n+1}{p-1}}{\theta }_0^{\frac{p^{n+1}-1}{p-1}},$$

   where ${\theta }_0={\left(\frac{L}{p!}\right)}^{\frac{1}{p-1}}\left|\overline{x}-u_0\right|.$

   We make the following notations:

   	$q$	$=\frac{p^{n+1}-1}{p-1};$
   	$K$	$=\frac{M{m}^{n+1}}{\left(n+1\right)!}{\left(\frac{p!}{L}\right)}^{\frac{n+1}{p-1}};$
   	${\epsilon }_0$	$=K^{\frac{1}{q-1}}{\theta }_0;$
   	${\epsilon }_1$	$=K^{\frac{1}{q-1}}\left|\overline{x}-u_1\right|.$

   By (43), we are lead to

   $${\epsilon }_1\le {\epsilon }_0^q.$$

   We obtain the sequence of approximation ${\left(u_s\right)}_{s\ge 0}$ for which, if denoting

   (44)

   $${\epsilon }_s=K^{\frac{1}{q-1}}\left|\overline{x}-u_s\right|,s=1,2,\mathrm{\dots },$$

   we get

   (45)

   $${\epsilon }_s\le {\epsilon }_0^{q^s},s=1,2,\mathrm{\dots }.$$

   Obviously, in this case too, if , then by (44) and (45) it follows $\underset{s\to \mathrm{\infty }}{lim}{u}_s=\overline{x}$ and the convergence order is $q$.