SÉMINAIRE DE LA THÉORIE DE LA MEILLEURE APPROXIMATION,

CONVEXITÉ ET PROGRAMMATION MATHÉMATIQUE

CLUJ - NAPOCA, 1999, pp. 222–248

Optimal Algorithms Concerning the Solving of Equations by Interpolation

Ion Păvăloiu
(Cluj - Napoca)

1. Introduction

It is well known that the most usual methods for approximating a solution of a nonlinear equation in $\mathbb{R}$ (Newton’s method, Chebyshev’s method, chord method and different generalizations of these) are obtained in an unitary manner by Lagrange-Hermite-type inverse interpolation.

The inverse interpolatory polynomials, by a proper choice of the nodes, also lead to Aitken-Steffensen-type methods.

In this paper we approach two aspects concerning the optimality problems arising from the consideration of the iterative methods for approximating the solutions of equations by inverse interpolation. The first aspect concerns the construction of some algorithms having optimal convergence orders, while the second addresses the optimal complexity of calculus concerning the inverse interpolation iterative methods.

We adopt the efficiency index (see [6]) as a measure of the complexity of the iterative methods.

This paper represents a synthesis of the results obtained by us in the papers [3], [4], [7], [10], [11].

We shall begin by presenting some definitions and results (some of them are known) concerning the convergence order and the efficiency index of an iterative method. We briefly present then the inverse interpolatory methods and the iterative methods generated by them. We consider different classes of interpolatory methods determining for each class the methods having the optimal convergence order. Finally, we determine the methods having the optimal efficiency indexes.

2. Convergence orders and efficiency indexes

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

(1)

f\left(x\right)=0

where $f:I\rightarrow\mathbb{R}$ is given. We shall assume for simplicity in the following that the above equation has a unique solution $\bar{x}\in I.$ Let $g:I\rightarrow I$ be a function having a unique fixed point and let that point be $\bar{x}.$

For approximating the solution $\bar{x}$ we shall consider the elements of the sequence $\left(x_{p}\right)_{p\geq 0}$ generated by the iterations

(2)

x_{s+1}=g\left(x_{s}\right),\qquad s=0,1,\ldots,\;\;x_{0}\in I,

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

G\left(x,x,\ldots,x\right)=g\left(x\right),\qquad\forall x\in I

then we may consider the iterations

(3)

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

The convergence orders of the sequences $\left(x_{p}\right)_{p\geq 1}$ generated by (2) and (3) depend on some properties of the function $f,$ $g,$ resp. $G .$

The amount of time needed by a computer to obtain a convenient approximation depends both on the convergence order of $\left(x_{p}\right)_{p\geq 0}$ and on the number of elementary operations that must be performed at each iteration step in (2) or (3). The convergence order of the methods of the form (2) and (3) may be determined exactly under some circumstances, but the number of elementary operations needed at each iteration step may be hard or even impossible to evaluate. A simplification of this problem may be obtained (see [6]) by taking into account the number of function evaluations needed at each iteration step.

It is obvious that this criterion may be, at the first sight, contested, since some functions may be simpler and others may be more complicated from the calculus viewpoint.

This inconvenient does not affect our viewpoint on optimal efficiency, because it refers on classes of iterative methods which are applied for solving an equation in which the functions are well determined by the form of equation (1), and by $g,$ resp. $G .$

Let $\left(x_{p}\right)_{p\geq 0}$ be an arbitrary sequence which together with $f$ and $g$ satisfies

i.

$x_{s}\in I$ and $g\left(x_{s}\right)\in I$ for $s=0,1,\ldots;$
ii.

the sequence $\left(x_{p}\right)_{p\geq 0}$ converges and $\lim x_{p}=\lim g\left(x_{p}\right)=\bar{x};$
iii.

$f$ is derivable at $\bar{x};$
iv.

for any $x,y\in I$ it follows $0<\left|\left[x,y;f\right]\right|\leq m,$ for some $m\in\mathbb{R}$ , $m>0,$ where $\left[x,y;f\right]$ denotes the first order divided difference of $f$ on the nodes $x$ and $y .$

Definition 2.1.

The sequence $\left(x_{p}\right)_{p\geq 0}$ has the convergence order $\omega,$ $\omega\geq 1,$ with respect

to $g$ if there exists the limit

(4)

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

and $\alpha=\omega.$

For a unitary treatment of the convergence orders of the studied methods we shall prove the following lemmas.

Lemma 2.1.

If the sequence $\left(x_{p}\right)_{p\geq 0}$ and the functions $f$ and $g$ satisfy properties i–iv then the necessary and sufficient condition for this sequence to have the convergence order $\omega,$ $\omega\geq 1,$ is that there exists

(5)

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

and $\beta=\omega.$

Proof.

Assuming true one of the relations (4) and (5) and taking into account hypotheses i–iv, we get

	$\displaystyle\lim\frac{\ln\left\|g\left(x_{p}\right)-\bar{x}\right\|}{\ln\left\|x% _{p}-\bar{x}\right\|}$	$\displaystyle=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|-\ln% \left\|\left[g\left(x_{p}\right),\bar{x};f\right]\right\|}{\ln\left\|f\left(x_{p}% \right)\right\|-\ln\left\|\left[x_{p},\bar{x};f\right]\right\|}$
		$\displaystyle=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|}{\ln% \left\|f\left(x_{p}\right)\right\|}\cdot\frac{1-\frac{\ln\left\|\left[g\left(x_{p% }\right),\bar{x};f\right]\right\|}{\ln\left\|\left[f\left(g\left(x_{p}\right)% \right)\right]\right\|}}{1-\frac{\ln\left\|\left[x_{p},\bar{x};f\right]\right\|}{% \ln\left\|f\left(x_{p}\right)\right\|}}$
		$\displaystyle=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|}{\ln% \left\|f\left(x_{p}\right)\right\|}.$

∎

Lemma 2.2.

Assume that $\left(u_{p}\right)_{p\geq 0}$ is a sequence of real positive numbers satisfying the following properties:

i.

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

there exist the real nonnegative numbers $\alpha_{1},$ $\alpha_{2},\ldots,\alpha_{n+1}$ and a sequence $\left(c_{p}\right)_{p\geq 0}$ with $c_{s}>0,$ $s=0,1,\ldots$ and $0<\inf\{c_{p}\}\leq\sup\{c_{p}\}\leq m,$ which together with the elements of the sequence $\left(u_{p}\right)_{p\geq 0}$ satisfy

(6) $u_{s+n+1}=c_{s}u_{s}^{\alpha_{1}}u_{s+1}^{\alpha_{2}}\ldots u_{s+n}^{\alpha_{n% }+1},\qquad s=0,1,\ldots,$
iii.

there exists $\lim\frac{\ln u_{p+1}}{\ln u_{p}}=\omega>0.$

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

(7) $t^{n+1}-\alpha_{n+1}t^{n}-\alpha_{n}t^{n-1}-\ldots-\alpha_{2}t-\alpha_{1}=0.$

Proof.

By (6) we obtain

(8)

\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+1}}+\sum_{i=0}^{n}\alpha_{i+1}\lim_{s% \rightarrow\infty}\frac{\ln u_{s+i}}{\ln u_{s+n}}

The hypotheses imply

\lim_{s\rightarrow\infty}\frac{\ln c_{s}}{\ln u_{n+s}}=0

and

\lim\frac{\ln u_{s+i}}{\ln u_{s+n}}=\frac{1}{\omega^{n-i}},\qquad i=\overline{% 0,n,}

whence, by (8) we get

\omega=\sum_{i=0}^{n}\alpha_{i+1}\frac{1}{\omega^{n-i}},

i.e.,

(9)

\omega^{n+1}-\sum_{i=0}^{n}\alpha_{i+1}\omega^{i}=0.

∎

We turn now our attention to equation of the form (9).

Let $a_{1},$ $a_{2},\ldots,a_{n+1}\in\mathbb{R}$ , $a_{i}\geq 0=\overline{1,n+1}.$

We shall assume that the numbers $a_{i},$ $i=1,\ldots,n+1$ are ordered:

(10)

a_{n+1}\geq a_{n}\geq\ldots\geq a_{2}>a_{1}

and satisfy

(11)

a_{1}+a_{2}+\ldots+a_{n+1}>1.

Consider the equations

(12)

P\left(t\right)=t^{n+1}-a_{n+1}t^{n}-a_{n}t^{n-1}-\ldots-a_{2}t-a_{1}=0

(13)

Q\left(t\right)=t^{n+1}-a_{1}t^{n}-a_{2}t^{n-1}-\ldots-a_{n}t-a_{n+1}=0

(14)

R\left(t\right)=t^{n+1}-a_{i_{1}}t^{n}-a_{i_{2}}t^{n-1}-\ldots-a_{i_{n}}t-a_{i% _{n+1}}=0

where $\left(i_{1},i_{2},\ldots,i_{n+1}\right)$ is an arbitrary permutation of $\left(1,2,\ldots,n+1\right).$

Lemma 2.3.

If $a_{i},i=\overline{1,n+1}\$ satisfy condition (11) then any equation of form (14) has a unique root larger than 1. Moreover, if relations (10) are satisfied and if we denote by $a, b, c$ the positive roots of (12), (13) resp. (14), then

(15)

1<b\leq c\leq a,

i.e., equation (12) has the largest root.

Proof.

Consider the $\left(n+1\right)!$ equations of the form (14) and denote by $s$ the largest natural number for which $a_{i_{s}}\neq 0.$

We have $a_{i_{s+1}}=a_{i_{s+2}}=\ldots=a_{i_{n+1}}=0.$ Consider the function $\Psi\left(t\right)=R\left(t\right)/t^{n-s+1}.$ It can be seen by (11) that $\Psi\left(1\right)=1-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{s}}<0,$ and $\lim_{t\rightarrow\infty}\Psi\left(t\right)=+\infty.$ It follows that equation (14) has a unique positive root. The first part of the lemma is proved. In order to prove inequality (15) it suffices to show that $R\left(b\right)\leq 0$ and $R\left(a\right)\geq 0.$ Indeed,

	$\displaystyle R\left(b\right)$	$\displaystyle=R\left(b\right)-Q\left(b\right)=\left(a_{1}-a_{i_{1}}\right)b^{n% }+\left(a_{2}-a_{i_{2}}\right)b^{n-1}+\ldots$
		$\displaystyle\quad\ldots+\left(a_{n}-a_{i_{n}}\right)b+a_{n+1}-a_{i_{n+1}}$
		$\displaystyle=\left(b-1\right)\left(a_{1}-a_{i_{1}}\right)b^{n-1}+\left[\left(% a_{1}+a_{2}-a_{i_{1}}-a_{i_{2}}\right)b^{n-2}+\ldots\right.$
		$\displaystyle\quad\ldots+\left(a_{1}+a_{2}+\ldots+a_{n-1}-a_{i_{1}}-a_{i_{2}}-% \ldots-a_{i_{n-1}}\right)b$
		$\displaystyle\quad+\left.a_{1}+a_{2}+\ldots+a_{n}-a_{i_{1}}-a_{i_{2}}-\ldots-a% _{i_{n}}\right]\leq 0,$

since from (15) follow the inequalities

a_{1}+a_{2}+\ldots+a_{s}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{s}}\leq 0,\qquad s=1% ,2,\ldots,n,

and $b>1.$ The fact that $R\left(a\right)\geq 0$ is shown in an analogous manner. ∎

Lemma 2.4.

Let $p_{1},p_{2},\ldots p_{n+1}$ and $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1},$ where $p_{i}\geq 1$ , $\alpha_{i}\geq 1,$ $i=\overline{1,n+1}$ , be two sets of real numbers satisfying

(16)

p_{1}\geq p_{2}\geq\ldots\geq p_{n+1},\qquad\alpha_{1}\leq\alpha_{2}\leq\ldots% \leq\alpha_{n+1}.

Then, among all the numbers of the form

(17)

\alpha=\alpha_{j_{1}}p_{k_{1}}+\alpha_{j_{2}}p_{k_{1}}p_{k_{2}}+\ldots+\alpha_% {j_{n+1}}p_{k_{1}}p_{k_{2}}\ldots p_{k_{n+1}}

where $\left(j_{1},j_{2},\ldots,j_{n+1}\right)$ and $\left(k_{1},k_{2},\ldots,k_{n+1}\right)$ are arbitrary permutations of $\left(1,2,\ldots,n+1\right),$ the largest such number is given by

(18)

\alpha_{\max}=\alpha_{1}p_{1}+\alpha_{2}p_{1}p_{2}+\ldots+\alpha_{n+1}p_{1}p_{% 2}\ldots p_{n+1}.

Proof.

From the first set of inequalities (16) it follows that the inequality:

(19)			$\displaystyle\alpha_{j_{1}}p_{k_{1}}+\alpha_{j_{2}}p_{k_{1}}p_{k_{2}}+\ldots+% \alpha_{j_{n+1}}p_{k_{1}}p_{k_{2}}\cdot\ldots\cdot p_{k_{n+1}}\leq$
		$\displaystyle\leq\alpha_{j_{1}}p_{1}+\alpha_{j_{2}}p_{1}p_{2}+\ldots+\alpha_{j% _{n+1}}p_{1}p_{2}\cdot\ldots\cdot p_{n+1}$

holds for any two permutations $\left(j_{1},j_{2},\ldots,j_{n+1}\right)$ and $\left(k_{1},k_{2},\ldots,k_{n+1}\right)$ of $\left(1,2,\ldots,n+1\right).$

Let us denote

(20)

b_{i}=p_{1}p_{2}\ldots p_{i},\qquad i=1,2,\ldots,n+1.

In order to prove the inequality

(21)

\alpha_{j_{1}}b_{1}+\alpha_{j_{2}}b_{2}+\ldots+\alpha_{j_{n+1}}b_{n+1}\leq% \alpha_{1}b_{1}+\alpha_{2}b_{2}+\ldots+\alpha_{n+1}b_{n+1}

for every permutation $\left(j_{1},j_{2},\ldots,j_{n+1}\right),$ we shall proceed by induction. For $n=0$ the inequality (21) is obvious, since $n+1$ $=1$ and hence $\alpha_{j_{1}}=\alpha_{1}.$ Suppose now that the inequality is true for $n$ pairs of numbers $\left(\alpha_{1},b_{1}\right),\ldots,\left(\alpha_{n},b_{n}\right),$ namely

(22)

\alpha_{j_{1}}b_{1}+\alpha_{j_{2}}b_{2}+\ldots+\alpha_{j_{n}}b_{n}\leq\alpha_{% 1}b_{1}+\ldots+\alpha_{n}b_{n},

where $\alpha_{1}\leq\alpha_{2}\leq\ldots\leq\alpha_{n}$ and $b_{1}\leq b_{2}\leq\ldots\leq b_{n}.$ Using the inequalities $b_{1}\leq b_{2}\leq\ldots\leq b_{n}\leq b_{n+1}$ and $\alpha_{1}\leq\alpha_{2}\leq\ldots\leq\alpha_{n}\leq\alpha_{n+1},$ as well as the induction hypothesis (22) and assuming that $j_{1}=i,$ $1\leq i\leq n$ , we have

		$\displaystyle\alpha_{j_{1}}b_{1}+\alpha_{j_{2}}b_{2}+\ldots+\alpha_{j_{n+1}}b_% {n+1}=$
		$\displaystyle=b_{1}\left(\alpha_{j_{1}}+\alpha_{j_{2}}+\ldots+\alpha_{j_{n+1}}% \right)+\left(b_{2}-b_{1}\right)\alpha_{j_{2}}+\left(b_{3-b_{1}}\right)\alpha_% {j_{3}}+\ldots+\left(b_{n+1}-b_{1}\right)\alpha_{j_{n+1}}$
		$\displaystyle\leq b_{1}\left(\alpha_{1}+\alpha_{2}+\ldots+\alpha_{n+1}\right)+% \left(b_{2}-b_{1}\right)\alpha_{1}+\left(b_{3}-b_{1}\right)\alpha_{2}+\ldots$
		$\displaystyle\quad\ldots+\left(b_{i}-b_{1}\right)\alpha_{i-1}+\left(b_{i+1}-b_% {1}\right)\alpha_{i+1}+\ldots+\left(b_{n+1}-b_{1}\right)\alpha_{n+1}$
		$\displaystyle\leq b_{1}\left(\alpha_{1}+\alpha_{2}+\ldots+\alpha_{n+1}\right)+% \left(b_{2}-b_{1}\right)\alpha_{3}+\ldots$
		$\displaystyle\quad\ldots+\left(b_{i}-b_{1}\right)\alpha_{i}+\left(b_{i+1}-b_{1% }\right)\alpha_{i+1}+\ldots+\left(b_{n+1}-b_{1}\right)\alpha_{n+1}$
		$\displaystyle=b_{1}\alpha_{1}+b_{2}\alpha_{2}+\ldots+b_{n+1}\alpha_{n+1}.$

∎

We turn back our attention to the equation

(23)

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

and we assume that $a_{i}\geq 1,$ $a_{i}\in\mathbb{N}$ , $i=\overline{1,n+1}$ and $\sum_{i=1}^{n+1}a_{i}=m+1,$ $m\in\mathbb{N}$ . Denote by $\delta_{n+1}$ the positive root of the above equation. The following result holds.

Lemma 2.5.

[7] The positive solution $\delta_{n+1}$ of equation (23) verifies the relation:

(24)

\displaystyle\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)\alpha_{i}}}

\displaystyle\leq\delta_{n+1}\leq 1+\max_{1\leq i\leq n+1}\{\alpha_{i}\},% \qquad n=1,2,\ldots

Proof.

Let

(25)

\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)\alpha_{i}}}

It is sufficient to prove that $P_{n+1}\left(\alpha\right)\leq 0,$ where $P_{n+1}(t)$ $=t^{n+1}-a_{n+1}t^{n}-\mathbb{\cdots-}a_{2}t-a_{1}.$

We shall use for this the inequality between the arithmetic mean and the geometric mean, i.e.

\displaystyle\frac{\sum\limits_{i=1}^{n+1}\alpha_{i}p_{i}}{\sum\limits_{i=1}^{% n+1}p_{i}}

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

Using this inequality we obtain

	$\displaystyle P_{n+1}\left(\alpha\right)$	$\displaystyle=\alpha^{n+1}-\sum_{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}\alpha_% {i}}\cdot\sum_{i=1}^{n+1}a_{i}$
		$\displaystyle\leq\alpha^{n+1}-\left(\sum_{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}}}$
		$\displaystyle=\alpha^{n+1}-\left(m+1\right)\left(\prod\limits_{i=1}^{n+1}% \alpha^{\left(i-1\right)\alpha_{i}}\right)^{\frac{1}{m+1}}$
		$\displaystyle=\alpha^{n+1}-\left(m+1\right)\alpha^{\sum\limits_{i=1}^{n+1}% \left(i-1\right)\alpha_{i}}$
		$\displaystyle=\frac{\sum\limits_{i=1}^{n+1}\left(i-1\right)a_{i}}{m+1}\left[% \alpha^{\left(n+1\right)\frac{\sum\limits_{i=1}^{n+1}\left(i-1\right)a_{i}}{m+% 1}}-\left(m+1\right)\right]=0,$

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

Remark 2.1.

It can be easily seen that the number $\alpha$ given by (25) can be expressed 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 (24) follows easily from the inequality $P_{n+1}\left(a\right)>0,$ where $a=1+\max_{1\leq i\leq n+1}\{\alpha_{i}\}.$

Some more specific results concerning the bounds for the root $\delta_{n+1}$ of equation (23) can be obtained in the case

(26)

a_{1}=a_{2}=\mathbb{\cdots=}a_{n+1}=q,\qquad q\geq 1.

More precisely, denoting by $\gamma_{n}\left(q\right)$ the positive root of equation

(27)

t^{n+1}-qt^{n}-qt^{n-1}-\mathbb{\cdots-}qt-q=0,

then the following relations hold (see [15]):

a)

$\gamma_{n}\left(q\right)<\gamma_{n+1}\left(q\right),\ n=1,2,\mathbb{\ldots};$
b)

$\max\{q,\frac{n+1}{n+2}\left(q+1\right)\}<\gamma_{n+1}\left(q\right)\leq q+1,$ $n=1,2,\mathbb{\ldots};$
c)

$\lim\limits_{n\rightarrow\infty}\gamma_{n}\left(q\right)=q+1.$

For $q=1,$ from relations a)–c) we get (see [6]):
a’)

$\gamma_{n}\left(1\right)\leq\gamma_{n+1}\left(1\right),$ $n=1,2,\mathbb{\ldots}$
b’)

$\frac{2\left(n+1\right)}{n+2}<\gamma_{n+1}\left(1\right)<2,$ $n=1,2,\mathbb{\ldots};$
c’)

$\lim\gamma_{n}\left(1\right)=2.$

In the following we shall denote by $m_{p}$ the number of function evaluations that must be performed when passing from step $p$ to step $p+1$ in the iterative methods (2), resp. (3), for $p=1,2,\mathbb{\ldots}$

Concerning the efficiency index of methods (2) and (3), taking into account Lemma 2.1 and the definition given in [6], we get

Definition 2.2.

The real number $E$ is called the efficiency index of the iterative method (2) and (3) if there exists

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

and $L=E.$

Remark 2.2.

If for methods (2) and (3) 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:

(28)

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 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 :$

(29)

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

In the above hypotheses it follows that the solution $\bar{x}$ of equation (1) is given by

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

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

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

L\left(y_{1},y_{2},\mathbb{\ldots},y_{n+1};f^{-1}|y\right)=\sum_{i=1}^{n}% \tfrac{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

(30)

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

where

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

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

It is also known that under 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 [12], [16]:

(31)

\displaystyle\left[f^{-1}\left(y\right)\right]^{\left(k\right)}

\displaystyle=\sum\tfrac{\left(2k-i_{1}-2\right)!\left(-1\right)^{k+i_{1}-1}}{% i_{2}!i_{3}!{\ldots}i_{k}!\left[f^{\prime}\left(x\right)\right]^{2k-1}}\big{(}% \tfrac{f^{\prime}\left(x\right)}{1!}\big{)}^{i_{1}}\big{(}\tfrac{f^{\prime% \prime}\left(x\right)}{2!}\big{)}^{i_{2}}{\ldots}\big{(}\tfrac{f^{(k)}\left(x% \right)}{k!}\big{)}^{i_{k}},\qquad k=\overline{1,n+1}

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

\left\{\begin{array}[c]{rl}i_{2}+2i_{3}+\mathbb{\ldots+}\left(k-1\right)i_{k}&% =k-1\\ i_{1}+i_{2}+\mathbb{\ldots+}i_{k}&=k-1.\end{array}\right.

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

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

Denoting

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

we obtain

\left|x_{n+2}-\bar{x}\right|=\tfrac{\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\{0,f\left(x_{1}\right),\mathbb{\ldots},f\left(x_{n+1}\right)\}<\theta_{1}% <\max\{0,f\left(x_{1}\right),\mathbb{\ldots},f\left(x_{n+1}\right)\}.$

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

(32)

x_{s+n+1}=L\left(y_{s},y_{s+1},\mathbb{\ldots},y_{s+n};f^{-1}|0\right),\qquad s% =1,2,\mathbb{\ldots}

with the error estimate given by

(33)

\left|x_{s+n+1}-\bar{x}\right|=\tfrac{\left|\left[f^{-1}\left(\theta_{s}^{% \prime}\right)\right]^{\left(n+1\right)}\right|}{\left(n+1\right)!}\prod% \limits_{i=0}^{n}\left|f\left(x_{s+1}\right)\right|,\ \;\;s=1,2,\mathbb{\ldots}

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

If we replace in (33) $\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:

(34)

\left|f\left(x_{s+n+1}\right)\right|=\left|f^{\prime}\left(\alpha_{s}\right)% \right|\tfrac{\left|\left[f^{-1}\left(\theta_{s}^{\prime}\right)\right]^{\left% (n+1\right)}\right|}{\left(n+1\right)!}\prod\limits_{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\mathbb{N}$ , satisfies the hypotheses of Lemma 2.2 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 (32). Then the converges order of this sequence is equal to the positive solution of the equation:

t^{n+1}-t^{n}-t^{n-1}-\mathbb{\ldots-}t-1=0.

3.2. Hermite-type inverse interpolation

Consider in the following, besides the interpolation nodes (29), $n+1$ natural numbers $a_{1},a_{2},\mathbb{\ldots},a_{n+1},$ where $a_{i}\geq 1,$ $i=\overline{1,n+1}$ and

a_{1}+a_{2}+\mathbb{\ldots+}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 (31), that $f^{-1}$ is also $m+1$ times differentiable on $F .$ Denoting $y_{i}=f\left(x_{i}\right),\ i=\overline{1,n+1},$ then the Hermite polynomial for the nodes $y_{i},i=\overline{1,n+1},$ has the following form:

(35)			$\displaystyle H\left(y_{1},a_{1};y_{2},a_{2};\mathbb{\ldots};y_{n+1},a_{n+1};f% ^{-1}\|y\right)=$
		$\displaystyle=\sum_{i=1}^{n+1}\sum_{j=0}^{a_{i}-1}\sum_{k=0}^{a_{i-j-1}}\left(% f^{-1}\left(y_{i}\right)\right)^{\left(j\right)}\tfrac{1}{k!j!}\left(\tfrac{% \left(y-y_{i}\right)^{a_{i}}}{\omega_{1}\left(y\right)}\right)_{y=y_{i}}^{% \left(k\right)}\tfrac{\omega_{1}\left(y\right)}{\left(y-y_{i}\right)^{a_{i}-j-% k}}$

where

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

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

(36)

x_{s+n+1}=H\left(y_{s},a_{1};\mathbb{\ldots};y_{s+n},a_{n+1};f^{-1}|0\right),% \qquad s=1,2,\mathbb{\ldots}

where, as in (35),

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

It can be easily seen that the following equality holds:

(37)

\displaystyle\left|f\left(x_{s+n+1}\right)\right|

\displaystyle=\left|f^{\prime}\left(\beta_{s}\right)\right|\tfrac{\left|\left[% f^{-1}\left(\theta_{s}^{\prime\prime}\right)\right]^{\left(m+1\right)}\right|}% {\left(m+1\right)!}\prod\limits_{i=0}^{n}\left|f\left(x_{s+i}\right)\right|^{a% _{i+1}},\;\;\;s=1,2,\mathbb{\ldots}

where $\theta_{s}^{\prime\prime}$ belongs to the smallest open interval containing $0,y_{s},y_{s+1},\ldots,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)!},\qquad s\in\mathbb{N},

verify the hypotheses of Lemma 2.2 and, moreover, $\lim\limits_{s\rightarrow\infty}f\left(x_{s}\right)=0,$ then it is clear that the convergence order of the method (36) is given by the positive solution of the equation

(38)

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

In the following we shall consider a particular case of (36).

For $a_{1}=a_{2}=\ldots=a_{n+1}=q,$ from (36) we obtain

(39)

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

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

(40)

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

3.3. Aitken-Steffensen type iterative methods

Let $\varphi_{i}:I\rightarrow\mathbb{R},$ $i=1,\mathbb{\ldots},n+1$ be $n+1$ functions having the following properties

$\alpha)$

$\varphi_{i}\left(\bar{x}\right)=\bar{x},$ $i=\overline{1,n+1},$ where $\bar{x}$ is the solution of (1);
$\beta)$

there exist $n+1$ continuous functions $g_{i}:I\rightarrow\mathbb{R},$ $g_{i}\left(x\right)\geq 0\ \forall x\in I,$ and the real numbers $p_{i}>1,$ $i=\overline{1,n+1}$ such that the following equalities hold:

(41) $\left|f\left(\varphi_{i}\left(x\right)\right)\right|=g_{i}\left(x\right)\left|% f\left(x\right)\right|^{p_{i}},\qquad i=\overline{1,n+1.}$

Denote $u_{0}\in I$ an initial approximation of the root $\bar{x}$ of (1). We construct the $n+1$ interpolation nodes $x_{i}^{1},$ $i=\overline{1,n+1}$ in the following way:

(42)

x_{1}^{1}=\varphi_{1}\left(u_{0}\right),\ \;x_{i+1}^{1}=\varphi_{i+1}\left(x_{% i}^{1}\right),\qquad i=\overline{1,n}.

Next, we compute $y_{i}^{1}=f\left(x_{i}^{1}\right),\ i=\overline{1,n+1}$ and we consider the natural numbers $\alpha_{i},$ $i=\overline{1,n+1}$ such that

\alpha_{1}+\alpha_{2}+\mathbb{\cdots+\alpha}_{n+1}=m+1.

Taking as interpolation nodes the numbers $y_{i}^{1},\ i=\overline{1,n+1}$ and the Hermite interpolatory polynomial determined by these nodes with the corresponding multiplicities $\alpha_{i},$ $i=\overline{1,n+1},$ we obtain for $\bar{x}$ the following approximation:

(43)

u_{1}=H\left(y_{i}^{1},\alpha_{1};y_{2}^{1},\alpha_{2};\mathbb{\ldots};y_{n+1}% ^{1},\alpha_{n+1};f^{-1}|0\right).

The error is given by

(44)

\left|\bar{x}-u_{1}\right|=\tfrac{\left|\left[f^{-1}\left(\xi_{1}\right)\right% ]^{\left(m+1\right)}\right|}{\left(m+1\right)!}\left|\omega_{1}\left(0\right)\right|

where $\xi_{1}$ is a point belonging to the smallest interval determined by the points $0,$ and $y_{i},\ i=\overline{1,n+1},$ while $\omega_{1}$ has the following form:

(45)

\left|\omega_{1}\left(0\right)\right|=\left|f\left(x_{1}^{1}\right)\right|^{% \alpha_{i}}\cdot\left|f\left(x_{2}^{1}\right)\right|^{\alpha_{2}}\cdot\mathbb{% \ldots\cdot}\left|f\left(x_{n+1}^{1}\right)\right|^{\alpha_{n+1}}.

Taking into account hypothesis $\beta)$ for the functions $\varphi_{i},$ we get

	$\displaystyle\left\|f\left(x_{1}^{1}\right)\right\|$	$\displaystyle=\left\|f\left(\varphi_{1}\left(x_{0}\right)\right)\right\|=g_{1}% \left(u_{0}\right)\left\|f\left(u_{0}\right)\right\|^{p_{1}}$
	$\displaystyle\left\|f\left(x_{2}^{1}\right)\right\|$	$\displaystyle=g_{2}\left(x_{1}^{1}\right)\left\|f\left(x_{1}^{1}\right)\right\|^% {p_{2}}\leq g_{2}\left(x_{1}^{1}\right)g_{1}^{p_{2}}\left(u_{0}\right)\left\|f% \left(u_{0}\right)\right\|^{p_{1}p_{2}}$

and in general

(46)

\displaystyle\left|f\left(x_{i+1}^{1}\right)\right|

\displaystyle=g_{i+1}(x_{i+1}^{1})\left(g_{i}(x_{i}^{1})\right)^{p_{i+1}}% \mathbb{\ldots}\left(g_{1}(x_{1}^{1})\right)^{p_{2}p_{3}\mathbb{\ldots}p_{i+1}% }\cdot\left|f\left(x_{0}\right)\right|^{p_{1}p_{2}\mathbb{\ldots}p_{i+1}},% \qquad i=\overline{1,n}.

Denote

\alpha=\sum_{i=1}^{n+1}\alpha_{i}\prod\limits_{j=1}^{i}p_{j}

and

(47)

\rho(u_{0})=\prod_{i=1}^{n+1}\left[g_{i}\left(x_{i}^{1}\right)\right]^{\theta_% {i}}

where

\theta_{i}=\alpha_{i}+\sum_{j=i+1}^{n+1}\alpha_{j}\prod\limits_{k=i+1}^{j}p_{k}.

With these notations, from (44)–(46) we obtain

(48)

\left|\bar{x}-u_{1}\right|=\tfrac{\left[f^{-1}\left(\xi_{1}\right)\right]^{% \left(m+1\right)}\cdot\rho_{0}}{\left(m+1\right)!}\left|\rho\left(u_{0}\right)% \right|^{\alpha}.

Let $u_{k-1}$ be an arbitrary approximation of the solution $\bar{x},$ obtained by the continuation of the process given by (43). Then the next approximation is constructed in the following way.

Consider the interpolation nodes $x_{i}^{k},\ i=\overline{1,n+1}$ given by the relations

x_{1}^{k}=\varphi_{1}\left(u_{k-1}\right),\ x_{i+1}^{k}=\varphi_{i+1}\left(x_{% i}^{k}\right),\qquad i=\overline{1,n},\ k\geq 2.

Then $u_{k}$ is given by

(49)

u_{k}=H\left(y_{1}^{k},\alpha_{1};y_{2}^{k},;\alpha_{2};\cdots;y_{n+1}^{k},% \alpha_{n+1};f^{-1}|0\right),

where $y_{i}^{k}=f\left(x_{i}^{k}\right),\qquad i=\overline{1,n+1},$ with the error estimation

(50)

\left|\bar{x}-u_{k}\right|=\frac{\rho_{k-1}\left[f^{-1}\left(\xi_{k}\right)% \right]^{\left(m+1\right)}}{\left(m+1\right)}\cdot\left|f\left(u_{k-1}\right)% \right|^{\alpha},\qquad k=2,3,\ldots

where $\xi_{k}$ is a point belonging to the smallest interval determined by $0$ and $y_{i}^{k},\ i=\overline{1,n+1},$ and $\rho_{k-1}$ has an analogous form with that given in (47) for $\rho_{0},$

From (50) we get

(51)

\left|f\left(u_{k}\right)\right|=\tfrac{\rho_{k-1}\left[f^{-1}\left(\xi_{k}% \right)\right]^{\left(m+1\right)}\beta}{\left(m+1\right)!}\left|f\left(u_{k-1}% \right)\right|^{\alpha},\qquad k=2,3,\ldots

where $\beta=\max\limits_{x\in I}\left|f^{\prime}\left(x\right)\right|.$

It is obvious now that if $\lim u_{k}=\bar{x},$ then the convergence order of the process (49) is $\alpha,$ where

(52)

\alpha=\sum_{i=1}^{n+1}\alpha_{i}\prod\limits_{j=1}^{i}p_{j}.

We shall consider in the following the particular case when

\varphi_{1}=\varphi_{2}=\ldots=\varphi_{n+1}=\varphi\ \text{and }p_{1}=p_{2}=% \ldots p_{n+1}=1.

We assume that $f$ and $\varphi$ satisfy

(53)

\left|f\left(\varphi\left(x\right)\right)\right|=g\left(x\right)\left|f\left(x% \right)\right|

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

Let $x_{s}\in I$ be an approximation for the solution $\bar{x}.$ Denote $u_{s}=x_{s},\ u_{s+1}=\varphi\left(u_{s}\right),\ldots,$ $u_{s+n}=\varphi\left(u_{s+n-1}\right)$ and $\bar{y}_{s}=f\left(u_{s}\right),\ldots,\bar{y}_{s+n}=f\left(u_{s+n}\right).$ Taking into account the above assumption, by (32) we get the following Steffensen type method:

(54)

x_{s+1}=L\left(\bar{y}_{s};\bar{y}_{s+1},\ldots,\bar{y}_{s+n};f^{-1}|0\right),% \qquad x_{1}\in I,\ s=1,2,\ldots

Similarly, by (36) it follows:

(55)

\displaystyle x_{s+1}

\displaystyle=H\left(\bar{y}_{s},a_{1};\bar{y}_{s+1};a_{2};\ldots;\bar{y}_{s+n% },a_{n+1};f^{-1}|0\right),\qquad s=1,2,\ldots,\ x_{1}\in I.

By (53) we obtain 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),\qquad i=% \overline{1,n,}

where

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

Taking into account the above considerations, by (34) we obtain:

(56)

\displaystyle\left|f\left(x_{s+1}\right)\right|

\displaystyle=|f^{\prime}\left(\alpha_{s}^{\prime}\right)|\tfrac{\left|[f^{-1}% \left(\mu_{s}\right)]^{\left(n+1\right)}\right|}{\left(n+1\right)!}\prod% \limits_{i=1}^{n}p_{s,i-1}\left|f\left(x_{s}\right)\right|^{n+1},\qquad s=1,2,\ldots,

and analogously, by (37) we get

(57)

\displaystyle\left|f\left(x_{s+1}\right)\right|

\displaystyle=\left|f^{\prime}\left(\beta_{s}^{\prime}\right)\right|\tfrac{% \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}p_{s,i-1}^{a_{i}}\left|f% \left(x_{s}\right)\right|^{m+1},\qquad s=1,2,\ldots,

From Lemma 2.1, it follows that methods (56) and (57) have the convergence orders $n+1,$ respectively $m+1.$

3.4. Some particular cases

In what follows we shall discuss some particular cases.

The case $n=0.$ From (35) one obtains the Taylor inverse interpolating polynomial:

(58)

\displaystyle T\left(y\right)

\displaystyle=x_{1}+\tfrac{\left[f^{-1}\left(y_{1}\right)\right]^{\prime}}{1!}% \left(y-y_{1}\right)+\cdots+\tfrac{\left[f^{-1}\left(y_{1}\right)\right]^{% \left(\alpha_{1}-1\right)}}{\left(\alpha_{1}-1\right)!}\left(y-y_{1}\right)^{% \alpha_{1}-1}

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

(59)

\left[f^{-1}\left(y\right)\right]^{\prime}=\frac{1}{f^{\prime}\left(x\right)},

(60)

\left[f^{-1}\left(y\right)\right]^{\prime\prime}=-\frac{f^{\prime\prime}\left(% x\right)}{\left[f^{\prime}\left(x\right)\right]^{3}},

(61)

\left[f^{-1}\left(y\right)\right]^{\prime\prime\prime}=-\frac{f^{\prime\prime% \prime}\left(x\right)f^{\prime}\left(x\right)-3\left[f^{\prime\prime}\left(x% \right)\right]^{2}}{\left[f^{\prime}\left(x\right)\right]^{5}},

(62)

\displaystyle\left[f^{-1}\left(y\right)\right]^{\left(4\right)}

\displaystyle=\frac{\left[f^{\prime}\left(x\right)\right]^{2}f^{\left(4\right)% }\left(x\right)+10f^{\prime}\left(x\right)f^{\prime\prime}\left(x\right)f^{% \prime\prime\prime}\left(x\right)-15\left[f^{\prime\prime}\left(x\right)\right% ]^{3}}{\left[f^{\prime}\left(x\right)\right]^{7}}

From (59) and (58) for $\alpha_{1}=2$ we obtain:

T\left(y\right)=x_{1}+\tfrac{1}{f^{\prime}\left(x_{1}\right)}\left(y-f\left(x_% {1}\right)\right),

which, for $y=0,$ leads to the approximation $x_{2}$ of $\bar{x}$ given by the expression

(63)

x_{2}=x_{1}-\tfrac{f\left(x_{1}\right)}{f^{\prime}\left(x_{1}\right)},

i.e., to the Newton’s method.

From (59), (60) and (58) for $\alpha_{1}=3$ we obtain Chebyshev’s method, i.e.:

(64)

x_{2}=x_{1}-\tfrac{f\left(x_{1}\right)}{f^{\prime}\left(x_{1}\right)}-\tfrac{1% }{2}\tfrac{f^{\prime\prime}\left(x_{1}f^{2}\left(x_{1}\right)\right)}{\left[f^% {\prime}\left(x_{1}\right)\right]^{3}}.

Finally, from (59), (60) (61) and (58) for $\alpha_{1}=4$ we obtain:

(65)

\displaystyle x_{2}

\displaystyle=x_{1}-\tfrac{f\left(x_{1}\right)}{f^{\prime}\left(x_{1}\right)}-% \tfrac{1}{2}\tfrac{f^{\prime\prime}\left(x_{1}\right)f^{2}\left(x_{1}\right)}{% \left[f^{\prime}\left(x_{1}\right)\right]^{3}}+\tfrac{f^{\prime\prime\prime}% \left(x\right)f^{\prime}\left(x_{1}\right)-3\left[f^{\prime\prime}\left(x_{1}% \right)\right]^{2}}{6\left[f^{\prime}\left(x_{1}\right)\right]^{5}}.

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

As one may notice from (62) and (36), for $\alpha_{1}\geq 5$ the expressions for the derivatives $\left[f^{-1}\left(y\right)\right]^{\left(k\right)},\ k\geq 4,$ have a more complex from. That is why the methods following from (58) in these cases are also complex.

The case $n=1.$ In this case, from (35) it follows:

(66)

P\left(y\right)=\sum_{i=1}^{2}\sum_{j=0}^{\alpha_{i}-1}\sum_{k=0}^{\alpha_{i}-% j-1}\left[f^{-1}\left(y_{i}\right)\right]^{\left(j\right)}\tfrac{1}{k!j!}\left% [\tfrac{\left(y-y_{i}\right)^{\alpha_{i}}}{\omega\left(y\right)}\right]_{y=y_{% i}}^{\left(k\right)}\cdot\tfrac{\omega\left(y\right)}{\left(y-y_{i}\right)^{% \alpha_{i}-j-k}}

where:

(67)

\omega\left(y\right)=\left(y-y_{1}\right)^{\alpha_{1}}\cdot\left(y-y_{2}\right% )^{\alpha_{2}}.

From (66) one obtains two iterative methods; namely denoting as above by $H\left(y_{1},\alpha_{1};y_{2},\alpha_{2};f^{-1}|y\right)$ the Hermite inverse interpolating polynomial (66), we find:

(68)

\left\{\begin{array}[c]{l}x_{3}=H\left(y_{1},\alpha_{1};y_{2},\alpha_{2};f^{-1% }|0\right),\\ x_{1},x_{2}\in I,\ y_{1}=f\left(x_{1}\right),\ y_{2}=f\left(x_{2}\right),\\ x_{n+1}=H\left(y_{n-1},\alpha_{1};y_{n},\alpha_{2};f^{-1}|0\right),\qquad n=3,% 4,\ldots,\end{array}\right.

(69)

\left\{\begin{array}[c]{l}x_{3}=H\left(y_{1},\alpha_{2};y_{2},\alpha_{1};f^{-1% }|0\right),\\ x_{1},x_{2}\in I,y_{1}=f\left(x_{1},\right)y_{2}=f\left(x_{2}\right),\\ x_{n+1}=H\left(y_{n-1},\alpha_{2};y_{n},\alpha_{1};f^{-1}|0\right),\qquad n=3,% 4,\ldots,\end{array}\right.

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

(70)

t^{2}-\alpha_{2}t-\alpha_{1}=0

for method (68), and:

(71)

t^{2}-\alpha_{1}t-\alpha_{2}=0

for the method (69).

If we denote by $\omega_{1}\$ and respectively $\omega_{2}$ , the positive roots of equations (70) and (71), then it is clear that $\alpha_{2}\geq\alpha_{1}$ implies $\omega_{2}\geq\omega_{1}$ ; so, the method with optimal convergence order is the method (68).

Now, we shall briefly discuss some particular cases.

From (66), for $\alpha_{1}=\alpha_{2}=1,$ we obtain

(72)

P_{1}\left(y\right)=\left(y_{1}-y_{2}\right)^{-1}\left[\left(y-y_{2}\right)f^{% -1}\left(y_{1}\right)-\left(y-y_{1}\right)f^{-1}\left(y_{2}\right)\right]

whence, taking into account the fact $f^{-1}\left(y_{1}\right)=x_{1}$ and $f^{-1}\left(y_{2}\right)=x_{2},$ we find for $y=0$

(73)

x_{3}=x_{1}-\tfrac{x_{2}-x_{1}}{f\left(x_{2}\right)-f\left(x_{1}\right)}f\left% (x_{1}\right)=x_{1}-\tfrac{f\left(x_{1}\right)}{\left[x_{1},x_{2};f\right]},

where $\left[x_{1},x_{2};f\right]$ stands for the first order divided difference of the function $f$ on the nodes $x_{1}$ and $x_{2}$ and in general,

(74)

x_{n+1}=x_{n-1}-\tfrac{f\left(x_{n-1}\right)}{\left[x_{n-1},x_{n};f\right]},% \qquad n=3,4,\ldots,

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 (74), i.e.:

(75)

x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{\left[x_{n-1},x_{n};f\right]},\qquad n% =2,3,\ldots\ .

The convergence order of the method (74) 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 (66) the following iterative methods:

(76)		$\displaystyle x_{n+2}=$	$\displaystyle x_{n}-\tfrac{x_{n+1}-x_{n}}{f\left(x_{n+1}\right)-f\left(x_{n}% \right)}f\left(x_{n}\right)+\tfrac{f\left(x_{n+1}\right)-f\left(x_{n}\right)-% \left(x_{n+1}-x_{n}\right)f^{\prime}\left(x_{n+1}\right)}{\left[f\left(x_{n+1}% \right)-f\left(x_{n}\right)\right]^{2}f^{\prime}\left(x_{n+1}\right)}f\left(x_% {n}\right)\cdot f\left(x_{n+1}\right),$
		$\displaystyle n=1,2,\ldots,\ x_{1},x_{2}\in I$

and

(77)

\displaystyle x_{n+2}

\displaystyle=x_{n+1}-\tfrac{x_{n}-x_{n+1}}{f\left(x_{n}\right)-f\left(x_{n+1}% \right)}f\left(x_{n+1}\right)+\tfrac{f\left(x_{n}\right)-f\left(x_{n+1}\right)% -\left(x_{n}-x_{n+1}\right)f^{\prime}\left(x_{n}\right)}{\left[f\left(x_{n}% \right)-f\left(x_{n+1}\right)\right]^{2}f^{\prime}\left(x_{n}\right)}f\left(x_% {n}\right)\cdot f\left(x_{n+1}\right).

Solving the corresponding characteristic equations, we find the convergence orders $\omega_{1}=1+\sqrt{2}for$ the method (76) and $\omega_{2}=2$ for the method (77).

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 previous one.

As Steffensen noticed, in the case of method (74), 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 $\varphi:I\rightarrow\mathbb{R}$ having the property $\varphi\left(\bar{x}\right)=\bar{x},$ where $\bar{x}$ is the root of the equation (1), and if we put $x_{n}=\varphi\left(x_{n-1}\right)$ into (74), then we obtain the sequence $\left(x_{n}\right)_{n\geq 1}$ generated by Steffensen’s method:

x_{n}=x_{n-1}-\frac{f\left(x_{n-1}\right)}{\left[x_{n-1},\varphi\left(x_{n-1}% \right);f\right]},\qquad n=2,3,\ldots,

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

4. Optimal convergence order

4.1. Optimal convergence order of the iterative methods of Hermite type

As we have seen in the particular cases presented at §3.4, in the case $n=1,$ the Hermite inverse interpolation polynomial for $\alpha_{1}\neq\alpha_{2},$ leads to two different iterative methods (see (68) and (69)). From these two, methods (68) has a convergence order greater than the other one. In the following we shall use Lemma 2.3 in order to generalize the iterative methods (68) and (69). It is clear that the convergence order of method (36) depends on the multiplicity of the interpolation nodes which are replaced at each iteration step such that we are led to different configurations of the coefficients in equation (38). Formula (36) generates $\left(n+1\right)!$ iterative methods, with respect to the algorithm of changing the interpolation nodes at each iteration step. Among those $\left(n+1\right)!$ methods, we shall determine in the following the method with the highest convergence order, i.e. the optimal method. For this purpose we shall do as follows.

Consider the permutation $i_{1},$ $i_{2},\ldots,i_{n+1}$ of the numbers $1,2,\ldots,n+1$ for which the natural numbers $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ satisfying the equality $\alpha_{1}+\alpha_{2}+\cdots+\alpha_{n+1}=m+1,$ can be increasingly ordered, namely:

(78)

\alpha_{i_{1}}\leq\alpha_{i_{2}}\leq\cdots\leq\alpha_{i_{n}}\leq\alpha_{i_{n+1% }}.

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

E=\{x_{i_{1}},x_{i_{2}},\ldots,x_{i_{n+1}}\}.

For the sake of clearness we shall set:

(79)

a_{s}=\alpha_{i_{s}},\qquad s=1,2,\ldots,n+1

and

(80)

u_{s}=x_{i_{s}},\qquad s=1,2,\ldots,n+1,

and denote by $H\left(y_{1},a_{1};y_{2},a_{2};\ldots,y_{n+1},a_{n+1};f^{-1}|x\right)$ the Hermite interpolating polynomial, corresponding to the nodes $y_{i}=f\left(u_{i}\right),\ i=1,2,\ldots,n+1$ , having the multiplicities $a_{1},a_{2},\ldots,a_{n+1}$ respectively.

Let $u_{1},u_{2},\ldots,u_{n+1}$ be the $n+1$ initial approximation of the root $\bar{x}$ of the equation (1). We construct the sequence $\left(u_{p}\right)_{p\geq 1}$ by means of the following iterative procedure:

(81)

\left\{\begin{array}[c]{l}u_{n+2}=H\left(y_{1},a_{1};y_{2},a_{2};\ldots;y_{n+1% },a_{n+1};f^{-1}|0\right),\ldots,\\ u_{n+s+1}=Hy_{s},a_{1};y_{s+1},a_{2};\ldots;y_{s+n},a_{n+1};f^{-1}|0),\qquad s% =2,3,\ldots\end{array}\right.

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

(82)

\left\{\begin{array}[c]{l}x_{n+2}=H\left(y_{i_{1}},\alpha_{i_{1}};y_{i_{2}},% \alpha_{i_{2}};\ldots;y_{i_{n+1}},\alpha_{i_{n+1}};f|0\right);\\ x_{n+s+2}=H\left(y_{i_{1}+s},\alpha_{i_{1}};y_{i_{2}+s},\alpha_{i_{1}};y_{i_{2% }+s},\alpha_{i_{2}};\ldots;y_{i_{n+1}+s},\alpha_{i_{n+1}};f|0\right),\qquad s=% 1,2,\ldots\end{array}\right.

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

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

Theorem 4.1.

Out of the $\left(n+1\right)!$ iterative methods of the form (82), with the greatest convergence order (namely these which provide the best upper limit for the absolute value of the error) is that determined by the permutation $i_{1},i_{2},\ldots,i_{n+1},$ which orders increasingly the numbers $\alpha_{i_{1}},\alpha_{i_{2}},\ldots,\alpha_{i_{n+1}},$ namely $\alpha_{i_{1}}\leq\alpha_{i_{2}}\leq\ldots\leq\alpha_{i_{n+1}}.$

4.2. Aitken-Steffensen-type optimal methods

In the following we shall solve an optimization problem, analogous with the one treated at section 4.1, but now for the case of the Aitken-Steffensen method.

We shall consider the methods of type (49), and for determining the optimal algorithm we shall rely on Lemma 2.4.

Let $\left(k_{1},k_{2},\ldots,k_{n+1}\right)$ and $\left(j_{1},j_{2},\ldots,j_{n+1}\right)$ be two arbitrary permutations of numbers $1,2,\ldots,n+1.$ Also denote

H\left(y\right)=H\left(y_{k_{1}}^{1},\alpha_{j_{1}};y_{k_{2}}^{1},\alpha_{j_{2% }};\ldots;y_{k_{n+1}}^{1},\alpha_{j_{n+1}};f|y\right)

the Hermite inverse interpolating polynomial having the interpolating notes $y_{k_{i}},$ with the orders of multiplicity $\alpha_{j_{i}},\ i=1,2,\ldots,n+1.$

With the above notations, let us consider the following class of iterative methods

(83)

u_{s}=H\left(y_{k_{1}}^{s},\alpha_{j_{1}};y_{k_{2}}^{s},\alpha_{j_{2}};\ldots;% y_{k_{n+1}}^{s},\alpha_{j_{n+1}};f|0\right),\qquad s+1,2,\ldots

where

y_{k_{i}}^{s}=f\left(x_{k_{i}}^{s}\right),\qquad i=1,2,\ldots,n+1;\ s=1,2,\ldots,

and

(84)		$\displaystyle x_{k_{1}}^{s}$	$\displaystyle=\varphi_{k_{1}}\left(u_{s-1}\right),$
	$\displaystyle x_{k_{i}}^{s}$	$\displaystyle=\varphi_{k_{i}}\left(x_{k_{i-1}}^{s}\right),\qquad i=2,3,\ldots,% n+1;\ s=1,2,\ldots,$

$u_{0}$ being the given initial approximation.

To each couple of permutations $\left(k_{1},k_{2},\ldots,k_{n+1}\right)$ and $\left(j_{1},j_{2},\ldots,j_{n+1}\right)$ of the numbers $1,2,\ldots,\left(n+1\right)!$ there corresponds an iterative method of the form (83). All together we have again iterative methods of this form.

We shall attempt to determine, out of the $\left(n+1\right)!$ iterative methods , that one for which the number $\alpha$ given by (52) is maximum.

Theorem 4.2.

Out of all the $\left(n+1\right)!$ iterative methods of the form (83)–(84), the one for which the convergence order $\alpha$ given by (52) attains the maximum value, is the method determined by the order of the numbers $p_{i},\alpha_{i},~{}i=1,2,\ldots,n+1,$ given by the inequalities (16).

The proof of this theorem follows immediately from Lemma 2.4 and (52).

5. Optimal efficiency

We shall analyse 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 (31) 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 relation (28).

5.1. Optimal Chebyshev-type methods

Taking $n=0$ in (36) we obtain again Chebyshev’s method, i.e.

(85)

\displaystyle x_{s+1}

\displaystyle=x_{s}-\tfrac{\left[f^{-1}\left(y_{s}\right)\right]^{\prime}}{1!}% f\left(x_{s}\right)+\tfrac{\left[f^{-1}\left(y_{s}\right)\right]^{\prime\prime% }}{2!}f^{2}\left(x_{s}\right)+\cdots+\left(-1\right)^{m}\tfrac{\left[f^{-1}% \left(y_{s}\right)\right]^{\left(m\right)}}{m!}f^{m}\left(x_{s}\right),

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

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

f\left(x_{s}\right),f^{\prime}\left(x_{s}\right),\ldots,f^{\left(m\right)}% \left(x_{s}\right),

i.e. $m+1$ values.

Then, by (31), 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},\ldots,\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 (85) we perform another function evaluation, so that $2\left(m+1\right)$ function evaluations must be performed.

By (28) the efficiency index of method (85) has the form

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

Considering the function $h:\left(0,\infty\right)\rightarrow\mathbb{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 5.1.

Among the Chebyshev-type iterative methods having the form (85), the method with the highest efficiency index is the third order method, i.e.

(86)

\displaystyle x_{s+1}

\displaystyle=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}},\qquad s=0,1,\ldots,\ x_{0}\in I.

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

$m$	$1$	$2$	$3$	$4$	$5$
$E\left(m\right)$	$1.1892$	$1.2009$	$1.1892$	$1.1746$	$1.1610$

Table 1.

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

5.2. The efficiency of Lagrange-type methods

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

	$\displaystyle E_{n+1}$	$\displaystyle=\left[\gamma_{n+1}\left(1\right)\right]^{\frac{1}{2}},\qquad n=1% ,2,\ldots,$
	$\displaystyle E_{n}$	$\displaystyle<E_{n+1},\qquad n=2,3,\ldots$

and

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

We have proved:

Theorem 5.2.

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

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

5.3. Optimal Hermite-type particular methods

We shall study the class of iterative methods of the form (39) for $q>1.$

Taking into account Remark 2.2 it is clear that we can use again relation (28) for the efficiency index.

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

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

i.e. $q$ function evaluations. Then, by (31) 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 (39). We totally have $2q$ function evaluations, the other values in (39) being already computed.

By a)–c) from Remark 2.2 and denoting by $E\left(\gamma_{n+1}\left(q\right),q\right)$ the efficiency of methods, of the form (39), we get:

(87)

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

(88)

\displaystyle\left(\max\{q,\tfrac{n+1}{n+2}\left(q+1\right)\}\right)^{\frac{1}% {2q}}

\displaystyle<E\left(\gamma_{n+1}\left(q\right),q\right)<\left(q+1\right)^{% \frac{1}{2q}},\qquad n\geq 1,\ q>1.

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

\lim E\left(\gamma_{n+1}\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\mathbb{N}.$

By (88) we have

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

and

(89)

\displaystyle\left[\tfrac{n+1}{n+2}\left(q+1\right)\right]^{\frac{1}{2q}}

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

For $q\geq n+1$ consider the functions $h:\left(0,+\infty\right)\rightarrow\mathbb{R},\ h\left(t\right)=t^{\frac{1}{2t}}$ and $l:\left(0,+\infty\right)\rightarrow\mathbb{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 in $\left(0,+\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$ isdecreasing 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

(90)

\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 (90). 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\mathbb{N}.$ It is easy to prove that $\bar{t}\in(4,5)$ 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 N$ verifying $1<q\leq 4,$ and $n\leq q-1.$

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

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

Table 2.

The highest value for the efficiency index is hence obtained for $q=2$ and $n=1.$ We shall specify explicitly the method (39) 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\left(x\right)$	$x$	$\left[u,v;f^{-1}\right]$	$\left[u,v,\omega;f^{-1}\right]$	$\left[u,v,\omega,z;f^{-1}\right]$
$y_{s}$	$x_{s}$	.	.	.
$y_{s}$	$x_{s}$	$\left[y_{s},y_{s};f^{-1}\right]$	.	.
$y_{s+1}$	$x_{s+1}$	$\left[y_{s},y_{s+1};f^{-1}\right]$	$\left[y_{s},y_{s},y_{s+1};f^{-1}\right]$	.
$y_{s+1}$	$x_{s+1}$	$y_{s+1},y_{s+1};f^{-1}$	$y_{s},y_{s+1},y_{s+1};f^{-1}$	$\left[y_{s},y_{s},y_{s+1},y_{s+1};f^{-1}\right]$

Table 3.

Here < display="inline">[ys,ys;f−1]=1f′(xs),[ys+1,ys+1;f−1]=1f′(xs+1),[ys,ys+1;f−1]=1[xs,xs+1;f], and the other divided differences are computed using the well-known recurrence formula.

In this case the method has the following form:

1999

Smoothness properties of positive summation integral operators

March 3, 2023

On some interpolatory iterative methods for the second degree polynomial operators (II)

December 21, 2017

On the high convergence orders of the Newton-GMBACK methods

February 10, 2018

	$\displaystyle\lim\frac{\ln\left\|g\left(x_{p}\right)-\bar{x}\right\|}{\ln\left\|x% _{p}-\bar{x}\right\|}$	$\displaystyle=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|-\ln% \left\|\left[g\left(x_{p}\right),\bar{x};f\right]\right\|}{\ln\left\|f\left(x_{p}% \right)\right\|-\ln\left\|\left[x_{p},\bar{x};f\right]\right\|}$
		$\displaystyle=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|}{\ln% \left\|f\left(x_{p}\right)\right\|}\cdot\frac{1-\frac{\ln\left\|\left[g\left(x_{p% }\right),\bar{x};f\right]\right\|}{\ln\left\|\left[f\left(g\left(x_{p}\right)% \right)\right]\right\|}}{1-\frac{\ln\left\|\left[x_{p},\bar{x};f\right]\right\|}{% \ln\left\|f\left(x_{p}\right)\right\|}}$
		$\displaystyle=\lim\frac{\ln\left\|f\left(g\left(x_{p}\right)\right)\right\|}{\ln% \left\|f\left(x_{p}\right)\right\|}.$

	$\displaystyle\left\|f\left(x_{1}^{1}\right)\right\|$	$\displaystyle=\left\|f\left(\varphi_{1}\left(x_{0}\right)\right)\right\|=g_{1}% \left(u_{0}\right)\left\|f\left(u_{0}\right)\right\|^{p_{1}}$
	$\displaystyle\left\|f\left(x_{2}^{1}\right)\right\|$	$\displaystyle=g_{2}\left(x_{1}^{1}\right)\left\|f\left(x_{1}^{1}\right)\right\|^% {p_{2}}\leq g_{2}\left(x_{1}^{1}\right)g_{1}^{p_{2}}\left(u_{0}\right)\left\|f% \left(u_{0}\right)\right\|^{p_{1}p_{2}}$

Optimal algorithms concerning the solving of equations by interpolation

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISBN

References

Paper (preprint) in HTML form

Optimal Algorithms Concerning the Solving of Equations by Interpolation

1. Introduction

2. Convergence orders and efficiency indexes

Definition 2.1.

Lemma 2.1.

Proof.

Lemma 2.2.

Proof.

Lemma 2.3.

Proof.

Lemma 2.4.

Proof.

Lemma 2.5.

Proof.

Remark 2.1.

Definition 2.2.

Remark 2.2.

3. Iterative methods of interpolatory type

3.1. Lagrange-type inverse interpolation

3.2. Hermite-type inverse interpolation

3.3. Aitken-Steffensen type iterative methods

3.4. Some particular cases

4. Optimal convergence order

4.1. Optimal convergence order of the iterative methods of Hermite type

Theorem 4.1.

4.2. Aitken-Steffensen-type optimal methods

Theorem 4.2.

5. Optimal efficiency

5.1. Optimal Chebyshev-type methods

Theorem 5.1.

5.2. The efficiency of Lagrange-type methods

Theorem 5.2.

5.3. Optimal Hermite-type particular methods

Related Posts