On computational complexity in Solving Equations
by Interpolation Methods

Ion Păvăloiu
(Cluj-Napoca)

1. Introduction

Let $I\subseteq{\mathbb{R}}$ be an interval of the real axis and $f:I\rightarrow{\mathbb{R}}$ a function. Consider the equation:

(1)

f\left(x\right)=0,

supposed to have a solution $\bar{x}\in I$ . Also get $g:I\rightarrow I$ be a function whose fixed points from $I$ coincide with the root of (1).

For solving (1) one can usually use an iterative method of the form:

(2)

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

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

(3)

g\left(x\right)=G\left(x,x,\ldots,x\right),\qquad\text{for\ all\ }x\in I

then one can consider the following iterative method for solving equation (1):

(4)

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

The convergence of the sequences $\left(x_{n}\right)_{n\geq 0}$ generated by (2) or (4) to a solution of equation (1) depends obviously on the properties of the functions $f, g$ respectively $G,$ and the amount of time necessary to obtain a suitable approximation for the solution $\bar{x}$ is influenced both by the convergence order of the methods (2), resp. (4) and by the amount of elementary operations that must be performed at each iteration step. This last aspect belongs to a chapter of the calculus theory and practice, chapter concerning the computational complexity.

Many authors ([1], [2], [3], [5], [6], [9], [10], [11]), who studied the computational complexity of the iteration processes, have defined different notions, as: the efficiency of a method, the efficiency index of a method or the cost of a method, which they have quantitatively expressed by different scalar magnitudes.

Throughout this paper we shall adopt the following definition for the convergence order of an iteration method:

Definition 1.1.

The real number $p\geq 1$ is called the convergence order of the sequence $\left(x_{n}\right)_{n\geq 0}$ generated by an iterative method if the following limit exists and is not zero:

(5)

\lim_{n\rightarrow\infty}\tfrac{\left|x_{n+1}-\bar{x}\right|}{\left|x_{n}-\bar% {x}\right|^{p}}=a\neq 0.

where $\bar{x}$ is the solution of equation (1).

Concerning the calculus complexity, using the convergence order we can define now the following notion:

Definition 1.2.

[6]. The number $I$ is called the efficiency index of the method (2) or (4), if the following limit exists and is finite:

(6)

\lim_{n\rightarrow\infty}\left(\tfrac{\ln\left|x_{n+1}-\bar{x}\right|}{\ln% \left|x_{n}-\bar{x}\right|^{p}}\right)^{1/m_{n}}=I,

where $m_{n}$ represents the number of function evaluations that must be performed when passing from the step $n$ to the step $n+1$ .

If we suppose that $m_{n}$ is the same for all $n$ , and take into account that (6) has an asymptotical character, then there results for $I$ the following expression:

(7)

I=I\left(p,m\right)=p^{\frac{1}{m}}.

In the following we shall study certain classes of iteration methods,namely the methods obtained by interpolation, among which we shall select those for which the efficiency index given by (7) is optimal, i.e. the greatest. For this purpose in the next section we shall briefly recall the classes of methods that we want to study.

2. Interpolation Iterative Methods

2.1. Lagrange’s inverse interpolation polynomial

Let $I\subseteq{\mathbb{R}}$ be an interval and $f:I\rightarrow{\mathbb{R}}$ a function. Denote by $F=f\left(I\right)$ the set of all values of $f$ for $x\in I$ . Suppose that $f$ is one-to-one, i.e. there exists the inverse function $f^{-1};F\rightarrow I$ . Consider in $I,n+1$ interpolation nodes:

(8)

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

Suppose that equation (1) has the unique solution $\bar{x}\in I$ .

Obviously,

(9)

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

and so the problem of approximation the solution $\bar{x}$ reduces to the approximation of $f^{-1}\left(0\right)$ .

A simple and efficient approximation method for the functions is given by the interpolating approximation.

Denote by:

(10)

y_{1},y_{2},\ldots,y_{n+1},\ y_{i}=f\left(x_{i}\right),\qquad i=\overline{1,n+% 1,}

the values of the $f$ on the nodes $x_{i}$ from (8).

The Lagrange interpolation polynomial corresponding to the function $f^{-1}$ on the nodes from (10) (taking into account that $y_{i}\neq y_{j},i\neq j;i,j=\overline{1,n+1}$ ) has the form:

(11)

L\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1}|y\right)=\sum_{i=1}^{n+1}\tfrac{x_{i}% \omega_{1}\left(y\right)}{\left(y-y_{i}\right)\omega_{1}\left(y_{i}\right)},

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

If we suppose that the function $f$ has derivatives up to the order $k,k\in\mathbb{N}$ and $f^{\prime}\left(x\right)\neq 0$ for all $x\in I,$ then we have the following formula for the computation of the $k$ -th derivative of $f^{-1}$ at the point $y=f\left(x\right),x\in I$ ([7], [12]):

(12)

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

where the above sum extends to all nonnegative integer numbers, solutions of the system:

(13)		$\displaystyle i_{2}+2i_{3}+\ldots+\left(k-1\right)i_{k}$	$\displaystyle=k-1;$
	$\displaystyle i_{1}+i_{2}+\ldots+i_{k}$	$\displaystyle=k-1.$

If we suppose that $f$ admits derivatives up to the order $n+1$ on the interval $I$ and the $n+1$ -th derivative is bounded on $I$ , then by (12) we obtain,

(14)

\bar{x}=f^{-1}\left(0\right)=L\left(y_{1},y_{2},\ldots,y_{n+1};f^{-1}|0\right)% +\tfrac{\left[f^{-1}\left(c\right)\right]^{\left(n+1\right)}}{\left(n+1\right)% !}\omega_{1}\left(0\right),

where $c$ is a point belonging to the smallest interval containing $0,y_{1},y_{2},\ldots,y_{n+1}$ and $\omega_{1}\left(0\right)=\left(-1\right)^{n+1}f\left(x_{1}\right)f\left(x_{2}% \right)\ldots f\left(x_{n+1}\right).$

Denote by $x_{n+2}$ the number:

(15)

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

and by (14) we get:

(16)

\left|\bar{x}-x_{n+2}\right|\leq\tfrac{M_{n+1}}{\left(n+1\right)!}\left|f\left% (x_{1}\right)\right|\left|f\left(x_{2}\right)\right|\ldots\left|f\left(x_{n+1}% \right)\right|,

from which we see that if $x_{1},x_{2},\ldots,x_{n+1}$ are chosen in a neighbourhood of $\bar{x}$ such that $\left|f\left(x_{i}\right)\right|<1,i=\overline{1,n+1},$ then $x_{n+1}$ can be considered as a new approximation for $\bar{x}$ . We have denoted in inequality (16), $M_{n+1}=\sup\limits_{y\in F}\left|\left[f^{-1}\left(y\right)\right]^{\left(n+1% \right)}\right|$ .

Let now $x_{k},x_{k+1},\ldots,x_{k+n}\in I$ be $n+1$ approximations for $\bar{x}$ . Then the Lagrange polynomial corresponding to the function $f^{-1}$ on the nodes $y_{i}=f\left(x_{i}\right),\ i=\overline{k,n+k}$ has the form:

(17)

L\left(y_{k},y_{k+1},\ldots,y_{k+n};f^{-1}|y\right)=\sum_{i=k}^{k+n}\tfrac{x_{% i}\omega_{k}\left(y\right)}{\left(y-y_{i}\right)\omega_{k}\left(y_{i}\right)}

where $\omega_{k}\left(y\right)=\prod\limits_{i=k}^{n+k}\left(y-y_{i}\right)$ . From this relation, for $y=0$ , we obtain a new approximation for $\bar{x}$ , namely

(18)

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

which satisfies the delimitation

(19)

\left|\bar{x}-x_{n+k+1}\right|\leq\tfrac{M_{n+1}}{\left(n+1\right)!}\left|f% \left(x_{k}\right)\right|\left|f\left(x_{k+1}\right)\right|\ldots\left|f\left(% x_{k+n}\right)\right|.

It is well known that the iterative method given by (18) has the convergence order $\theta_{n+1}$ , which is the unique positive root of the equation, [6]:

(20)

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

It is also known (see [6]) that $\theta_{n+1}$ verifies:

(21)

\tfrac{2\left(n+1\right)}{n+2}<\theta_{n+1}<2

and

(22)

\theta_{n}<\theta_{n+1};\lim_{n\rightarrow\infty}\theta_{n}=2,\qquad\text{for % all }n\geq 1.

Remark 2.1.

In the successive computation of the elements of the sequence $\left(x_{n}\right)_{n\geq 0}$ generated by (18) it is necessary to compute at each step $k$ the values $\omega_{k}\left(0\right)$ and $\omega_{k}^{\prime}\left(y_{i}\right),\ i=k,k+1,\ldots,k+n$ .

We observe that practically there exists a connection both between $\omega_{k}\left(0\right)$ and $\omega_{k+1}\left(0\right)$ and between $\omega_{k}^{\prime}\left(y_{i}\right)$ and $\omega_{k+1}^{\prime}\left(y_{i}\right)$ .

Indeed:

\omega_{k}\left(y\right)={\textstyle\prod\limits_{i=k}^{n+k}}\left(y-y_{i}\right)

and

\omega_{k+1}\left(y\right)={\textstyle\prod\limits_{i=k+1}^{n+k+1}}\left(y-y_{% i}\right)

hence we get

(23)

\omega_{k+1}\left(y\right)=\tfrac{\omega_{k}\left(y\right)\left(y-y_{n+k+1}% \right)}{y-y_{k}},

which for $y=0$ yields

(24)

\omega_{k+1}\left(0\right)=\tfrac{\omega_{k}\left(0\right)y_{n+k+1}}{y_{k}}

From (23) we obtain:

(25)

\omega_{k+1}^{\prime}\left(y\right)=\tfrac{\left[\omega_{k}^{\prime}\left(y% \right)\left(y-y_{n+k+1}\right)+\omega_{k}\left(y\right)\right]\left(y-y_{k}% \right)-\omega_{k}\left(y\right)\left(y-y_{n+k+1}\right)}{\left(y-y_{k}\right)% ^{2}},

which gives us the following recurrence formula:

(26)

\omega_{k+1}^{\prime}\left(y_{i}\right)=\begin{cases}\tfrac{\omega_{k}^{\prime% }\left(y_{i}\right)\left(y_{i}-y_{n+k+1}\right)}{y_{i}-y_{k}},&i=k+1,k+2,% \ldots,k+n\\ \tfrac{\omega_{k}\left(y_{i}\right)}{y_{i}-y_{k}},&i=k+n+1\end{cases}

Recurrence formulae (24) and (26) hold for all $k=1,2,\ldots,$ ∎

2.2. Hermite Inverse Interpolating Polynomial

We consider, besides the interpolatory nodes (8), the natural numbers $a_{1},a_{2},\ldots,a_{n+1}$ with $a_{i}\geq 1\ i=\overline{1,n+1}$ and

(27)

a_{1}+a_{2}+\ldots+a_{n+1}=m+1,\qquad m\in\mathbb{N}.

Suppose that $f$ admits derivatives up to the order $m+1$ on the interval $I$ and $f^{\prime}\neq 0$ . Then, by (12) it follows that the function $f^{-1}$ also admits derivatives up to the order $m+1$ . The Hermite polynomial of degree $m$ associated to the function $f^{-1}$ on the nodes $y_{i}=f\left(x_{i}\right),\ i=\overline{1,n+1}$ , assuming that $f^{\prime}\left(x\right)\neq 0$ for all $x\in I$ , is:

(28)		$\displaystyle H\left(y_{1};a_{1},y_{2};a_{2},\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

(29)

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

This polynomial satisfies:

(30)

H^{\left(j\right)}\left(y_{1};a_{1},y_{2};a_{2},\ldots,y_{n+1};a_{n+1};f^{-1}|% y_{i}\right)=\left[f^{-1}\left(y_{i}\right)\right]^{\left(j\right)}

for all $j=0,1,\ldots,a_{i}-1;i=1,2,\ldots,n+1$ .

As in 2.1 we obtain from (28) the following iterative method for solving equation (8):

(31)

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

where in the polynomial $H,\omega_{k}=\prod\limits_{i=k}^{n+k}\left(y-y_{i}\right)^{a_{i}}$ .

Using the differentiability assumptions for $f$ , we obtain:

(32)

\left|x_{n+k+n}-\bar{x}\right|\leq\tfrac{M_{m+1}}{\left(m+1\right)!}\left|f% \left(y_{k}\right)\right|^{a_{1}}\left|f\left(y_{k+1}\right)\right|^{a_{2}}% \ldots\left|f\left(y_{k+n}\right)\right|^{a_{n+1}}

where $M_{m+1}=\sup\limits_{y\in F}\left|\left[f^{-1}\left(y\right)\right]^{\left(m+1% \right)}\right|$ .

It is well known that the convergence order of (31) is given by the positive root $\omega_{n+1}$ of the equation:

(33)

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

In the particular cases when $a_{1}=a_{2}=\ldots=a_{n+1}$ we have iterative method:

(34)

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

and when $n=0$ we get the Chebyshev iterative method of order $m+1$ :

(35)

x_{k+1}=x_{k}-\tfrac{\left[f^{-1}\left(y\right)\right]^{\prime}}{1!}f\left(x_{% k}\right)+\ldots+\left(-1\right)^{m}\tfrac{\left[f^{-1}\left(y_{k}\right)% \right]}{m!}^{\left(m\right)}f^{m}\left(x_{k}\right),\qquad k=1,2,\ldots

which has the convergence order $p=m+1$ .

For the method (34), by (33) it follows that the convergence order is given by the positive root $\omega_{n+1}$ of the equation:

(36)

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

which satisfies:

(37)

\omega_{n}<\omega_{n+1},\qquad n=1,2,\ldots,

(38)

\max\left\{q,\tfrac{n+1}{n+2}\left(q+1\right)\right\}<\omega_{n+1}<q+1;\qquad n% =1,2,\ldots,

(39)

\lim_{n\rightarrow\infty}\omega_{n+1}=q+1.

3. The Efficiency Index of the Chebyshev Method of Order $m+1$

In the following we shall make the assumptions:

a)

Consider as a function evaluation, the evaluation of the derivatives $\left[f^{-1}\left(y\right)\right]^{\left(k\right)},$ assuming $f^{\left(k\right)}\left(x\right),k=\overline{1,m}$ as having been computed.
b)

Consider as a function evaluation, the evaluation of the right hand side of expression (35) assuming $f\left(x\right)$ and $\left[f^{\left(-1\right)}\left(y\right)\right]^{\left(k\right)},k=\overline{1,m}$ as having been computed.
c)

Consider as a function evaluation the evaluation of the function $f$ or of any of its derivatives.

In this hypothesis, it is necessary for an iteration step with method (35) to compute firstly the values of the functions: $f,f^{\prime},\ldots,f^{\left(m\right)}$ at the point $x_{k}$ , altogether $m+1$ function for the calculus of the values of the successive derivatives of $f^{-1}$ , by (12). If we take into account that for evaluating the right hand side expression from relation (35) is computed another function value, we have altogether $2\left(m+1\right)$ function evaluations at each iteration step.

Using definition (7) for the efficiency index, method (35) has the following index:

(40)

I\left(m+1,2\left(m+1\right)\right)=\left(m+1\right)^{\frac{1}{2\left(m+1% \right)}}

(We have taken into account that the convergence order is $m+1$ ).

We are searching for the maximum value of the index $I$ from (40), for $m\in\mathbb{N}$ .

For this purpose we consider the auxiliary function $\varphi:\left(0,\infty\right)\rightarrow{\mathbb{R}}_{+}\varphi\left(t\right)=% t^{\frac{1}{2t}}$ and we note that: $\lim\limits_{t\rightarrow 0}\varphi\left(t\right)=0$ , $\lim\limits_{t\rightarrow\infty}\varphi\left(t\right)=1$ , $\varphi$ is increasing for $t\in\left(0,e\right)$ and decreasing for $t\in\left(e,\infty\right);t=e$ is a maximum point for the function $\varphi$ .

For $t\in\mathbb{N}$ , the function $\varphi$ attains its maximum for $t=3,$ so $I\left(m+1,2\left(m+1\right)\right)$ attains its maximum form $m=2$ .

So, the following holds:

Theorem 3.1.

In the above assumptions a)–c) among all the Chebyshev iterative methods of the form (35) the method with the greatest efficiency index is the one of $3^{rd}$ order, namely

(41)

x_{k+1}=x_{k}-\tfrac{f\left(x_{k}\right)}{f^{\prime}\left(x_{k}\right)}-\tfrac% {1}{2}\tfrac{f^{\prime\prime}\left(x_{k}\right)f^{2}\left(x_{k}\right)}{\left[% f^{\prime}\left(x_{k}\right)\right]^{3}},\qquad k=0,1,\ldots,x_{0}\in I.

In the following table are shown the approximations of the efficiency index of Chebyshev methods for some values of $m$ .

$m$	$2$	$3$	$4$	$5$	$6$
$I\left(m+1,2\left(m+1\right)\right)$	$1.1892$	$1.2009$	$1.1892$	$1.1746$	$1.1610$

We see that $I\left(3,6\right)\cong 1.2009.$

4. The Efficiency Index for the Lagrange-Hermite Methods

In the following we shall study the case when $n\geq 1$ , i.e. when number of nodes is greater than one. In the beginning we shall take the method given by (18) for which, if we take into account the assumptions a) - c) and neglect the first step, we get that at each iteration step we have first one function evaluation, namely the value of the function $f$ at $x_{n+k}$ , and then we have another function evaluation, for the right hand side of relation (18), hence altogether two function evaluations. Recalling that the convergence order for (18) is $\theta_{n+1}$ , which satisfies (21) and (22) we get for the efficiency index the relation

(42)

I\left(\theta_{n+1},2\right)=\sqrt{\theta_{n+1}}.

By (22) we have that $I\left(\theta_{n},2\right)<I\left(\theta_{n+1},2\right)$ for all $n\geq 1$ .

So we conclude:

Theorem 4.1.

If the assumptions a)–c) hold, for the Lagrange methods given by (17) the efficiency index is increasing with respect to the number of interpolation nodes and

\lim_{n\rightarrow\infty}I\left(\theta_{n},2\right)=\sqrt{2}.

Now we study the efficiency index for the methods given by (34), for which the convergence order $\omega_{n+1}$ verifies (36)–(39). Obviously, we suppose that $q>1,\ q=1$ in (34) giving (18).

There are two aspects that must be considered: the efficiency with respect to the number of interpolation nodes, when their multiplicity order $q$ is kept fixed and, on the second hand, the efficiency with respect to the multiplicity order $q$ for fixed $n,\ n\geq 1$ .

We again suppose that assumptions a)–c) hold. So from the right hand side of (34), at each iteration step, excepting the first one, we have the following function evaluations: we compute $f\left(x_{n+k}\right),f^{\prime}\left(x_{n+k}\right),\ldots,f^{\left(q-1\right% )}\left(x_{n+k}\right),$ i.e. $q$ function evaluations, and then by (12) we compute $\left[f^{-1}\left(y_{n+k}\right)\right]^{\prime},$ $\left[f^{-1}\left(y_{n+k}\right)\right]^{\prime\prime},\ldots,\left[f^{-1}% \left(y_{n+k}\right)\right]^{\left(q-1\right)}$ i.e., $q-1$ function evaluations, and finally we compute the right hand side of (34). so altogether, $2q$ function evaluations.

Using (37)–(39) we get:

(43)

I\left(\omega_{n+1},2q\right)>I\left(\omega_{n},2q\right),\qquad\text{for all }n\geq 1,q>1,

and

(44)

\left(\max\left\{q,\tfrac{n+1}{n+2}\left(q+1\right)\right\}\right)^{\frac{1}{2% q}}<I\left(\omega_{n+1},2q\right)<\left(q+1\right)^{\frac{1}{2q}}.

for all $n\geq 1,\ q>1$ .

For a fixed $q$ by (43) we get that the efficiency index is increasing as a function of $n$ , and by (44)

\lim_{n\rightarrow\infty}I\left(\omega_{n+1},2q\right)=\left(1+q\right)^{\frac% {1}{2q}}.

From (44) we also obtain:

(45)

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

and

(46)

\left[\tfrac{n+1}{n+2}\left(q+1\right)\right]^{\frac{1}{2q}}<I\left(\omega_{n+% 1},2q\right)<\left(q+1\right)^{\frac{1}{2q}},\qquad\text{,for\ }q<n+1.

A. For the first case, when $q\geq n+1$ we consider the auxiliary functions $\varphi,\psi;\left(0,\infty\right)\rightarrow{\mathbb{R}}_{+}$ given by

\varphi\left(t\right)=t^{\frac{1}{2t}}

and

\psi\left(t\right)=\left(1+t\right)^{\frac{1}{2t}}.

As we have seen before, $\varphi$ satisfies:

\lim\limits_{\begin{subarray}{c}t\rightarrow 0\\ t>0\end{subarray}}\varphi\left(t\right)=0,\quad\lim\limits_{t\rightarrow\infty% }\varphi\left(t\right)=1,

is increasing on $\left(0,e\right)$ and decreasing on $\left(e,+\infty\right),$ so at $t=e$ attains its maximum.

One can establish the following relations for $\psi$ :

\lim\limits_{t\rightarrow 0}\psi\left(t\right)=\sqrt{e};\quad\lim\limits_{t% \rightarrow\infty}\psi\left(t\right)=1

and $\psi$ is decreasing on $\left(0,+\infty\right)$ .

Recalling that $\varphi$ attains its maximum value at $t=e,$ let $\bar{t}$ be the solution of the equation

(47)

\left(t+1\right)^{\frac{1}{2t}}-e^{\frac{1}{2e}}=0.

then for $t>\bar{t}$ we have $\left(t+1\right)^{\frac{1}{2t}}<e^{\frac{1}{2e}},$ hence, by (45), we obtain that the values of $q$ for which $I\left(\omega_{n+1},2q\right)$ attains its maximum lie in the set $\{q\in\mathbb{N};1<q\leq\bar{t}\}$ . One can easily prove that $\bar{t}\in\left(\ref{f.4.5}\right)$ so we shall study the cases $q=2,\ q=3,$ and $q=4$ . Since $q\geq n$ we study 1) $q=2,\ n=1;\$ 2) $q=3,\ n=1;q=3,\ n=2$ and 3) $q=4,\ n=1;\ n=2,\ n=3$ .

1) The corresponding equation from (36) for $q=2,\ n=1,$ is $t^{2}-2t-2=0$ , with the positive solution $\omega_{2}=1+\sqrt{3}$ . So $I\left(\omega_{2},4\right)=\sqrt[4]{1+\sqrt{3}}\cong 1,2856\ldots$

2) The convergence orders corresponding for this case are the solutions of the equations $t^{2}-3t-3=0$ for $n=1,\ q=3$ respectively $t^{3}-3t^{2}-3t-3=0$ for $n=2$ , $q=3$ .

We obtain $I\left(\omega_{2},6\right)\cong 1.2487\ldots$ , respectively $I\left(\omega_{3},6\right)\cong 1.2573\ldots$

3) The corresponding equations give us:

$I\left(\omega_{2,}8\right)\cong 1,2175\ldots;I\left(\omega_{3},8\right)\cong 1% ,2218\ldots$ and $I\left(\omega_{4},8\right)\cong 1,2226\ldots$

So the greatest efficiency index when $q\geq n+1$ is obtained for $n=1,\ q=2$ i.e $I\left(\omega_{2},4\right)=\sqrt[4]{1+\sqrt{3}}$ .

B. Let $q<n+1$ , so (46) holds. We shall again consider two auxiliary functions

	$\displaystyle\varphi,\psi:$	$\displaystyle\left(0,+\infty\right)\rightarrow{\mathbb{R}}_{+},$
	$\displaystyle\varphi\left(t\right)$	$\displaystyle=\left[\tfrac{n+1}{n+2}\left(t+1\right)\right]^{\frac{1}{2t}},\ % \psi\left(t\right)=\left(t+1\right)^{\frac{1}{2t}}$

which possess the following properties: $\lim\limits_{t\rightarrow 0}\varphi\left(t\right)=0;\ \lim\limits_{t% \rightarrow\infty}\varphi\left(t\right)=1$ ;

\varphi^{\prime}\left(t\right)=\tfrac{1}{2}\left[\tfrac{n+1}{n+2}\left(t+1% \right)\right]^{\frac{1}{2t}}\cdot\tfrac{\frac{t}{t+1}-\ln\frac{n+1}{n+2}\left% (t+1\right)}{t^{2}},

and one can easily prove that: the equation $\varphi^{\prime}\left(t\right)=0$ has a unique positive solution, denoted by $\tau_{n},\varphi^{\prime}\left(t\right)<0$ for $t>\tau_{n}$ and $\varphi^{\prime}\left(t\right)>0$ for $t\in\left(0,\tau_{n}\right),$ i.e. $\varphi$ attains its maximum value at $t=\tau_{n}$ .

Taking into account the properties of $\psi$ one can see that the equations

(48)

\left(t+1\right)^{\frac{1}{2t}}-e^{\frac{1}{2\left(\tau_{n}+1\right)}}=0,% \qquad n=2,3,\ldots

have a unique positive solution $\mu_{n}$ for each $n\geq 2$ .

In the table below we give the approximative values $\mu_{n}$ and $\tau_{n}$ for $n\in[2,10]$ .

$n$	$\tau_{n}$	$\mu_{n}$
$2$	$1.3816\ldots$	$3.6711\ldots$
$3$	$1.1201\ldots$	$2.8679\ldots$
$4$	$0.9566\ldots$	$2.3871\ldots$
$5$	$0.8436\ldots$	$2.0649\ldots$
$6$	$0.7601\ldots$	$1.8327\ldots$
$7$	$0.6955\ldots$	$1.6566\ldots$
$8$	$0.6438\ldots$	$1.5180\ldots$
$9$	$0.6013\ldots$	$1.4056\ldots$
$10$	$0.5656\ldots$	$1.3125\ldots$

An elementary reasoning proves that $\tau_{n}$ and $\mu_{n}$ are decreasing functions of $n$ , $n\geq 2$ , as we can see in the above table.

If $t>\mu_{n}$ then $\varphi\left(\tau_{n}\right)>\varphi\left(t\right)$ so the optimal values for $q$ must lie in the set $\{q\in\mathbb{N};2\leq q<\max\{n+1,\mu_{n}\}\}$ .

It can be shown that for $n\geq 6,\ \mu_{n}<2$ and for $n\in[2,5]$ , $2<\mu_{n}<4$ . It follows that the only suitable value for $q$ is $q=2$ . In this case we get that $I\left(\omega_{n},4\right)<I\left(\omega_{n+1},4\right)$ , $n\geq 2,$ i.e. the efficiency index increases with $n$ , but anyway the best results hold for $q=2$ .

5. Margins for the Efficiency Index in the Case of Lagrange-Hermite Methods

We end this note by indicating, in the above assumptions, left and right margins of the efficiency index of the Lagrange-Hermite methods.

In this respect we shall first establish an inequality that will give left margins for the positive roots of equations (33).

Let

(49)

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

where $a_{1}+a_{2}+\ldots+a_{n+1}=m+1,a_{i}\geq$ for $i=\overline{1,n+1}$ .

The following Lemma holds.

Lemma 5.1.

The positive root $\omega_{n+1}$ of (49) satisfies:

(50)

\omega_{n+1}\geq\left[m+1\right]^{\tfrac{m+1}{\left(n+1\right)\left(m+1\right)% -{\textstyle\sum\limits_{i=1}^{m+1}}\left(i-1\right)a_{i}}}

Proof.

Let

\alpha=\left[m+1\right]^{\tfrac{m+1}{\left(n+1\right)\left(m+1\right)-{% \textstyle\sum\limits_{i=1}^{m+1}}\left(i-1\right)a_{i}}}

It will suffice to show $P\left(\alpha\right)\leq 0$ , using the inequality between the weighted arithmetic and geometric mean, i.e.

(51)

\tfrac{\sum\limits_{i=1}^{n+1}\alpha_{i}p_{i}}{\sum\limits_{i=1}^{n+1}p_{i}}% \geq\left({\textstyle\prod\limits_{i=1}^{n+1}}a_{i}^{p_{i}}\right)^{\tfrac{1}{% \sum\limits_{i=1}^{n+1}p_{i}}}

We get

	$\displaystyle P\left(\alpha\right)$	$\displaystyle=\alpha^{n+1}-{\textstyle\sum\limits_{i=1}^{n+1}}a_{i}\alpha^{i-1% }=\alpha^{n+1}-\tfrac{{\sum\limits_{i=1}^{n+1}}a_{i}\alpha^{i-1}}{{\sum\limits% _{i=1}^{n+1}}a_{i}}{\textstyle\sum\limits_{i=1}^{n+1}}a_{i}$
		$\displaystyle\leq\alpha^{n+1}-\left({\textstyle\sum\limits_{i=1}^{n+1}}a_{i}% \right)\left[{\textstyle\prod\limits_{i=1}^{n+1}}\alpha^{\left(i-1\right)a_{i}% }\right]^{\tfrac{1}{{\sum\limits_{i=1}^{n+1}}a_{i}}}=\alpha^{n+1}-\left(m+1% \right)\alpha^{\tfrac{{\sum\limits_{i=1}^{n+1}}\left(i-1\right)a_{i}}{m+1}}$
		$\displaystyle=\alpha^{\tfrac{{\sum\limits_{i=1}^{n+1}}\left(i-1\right)a_{i}}{m% +1}}\left[\alpha^{n+1}-\tfrac{{\sum\limits_{i=1}^{n+1}}\left(i-1\right)a_{i}}{% m+1}-\left(m+1\right)\right]=0,$

i.e. $P\left(\alpha\right)\leq 0$ .

We also get $\omega_{n+1}\leq a+1$ , where $a=\max\limits_{1\leq i\leq n+1}\{a_{i}\}$ .

In the hypotheses of 3., using (31) in generating the sequence $\left(x_{n}\right)_{n\geq 0}$ then the number of function evaluations at each step is $2\left(m+1\right)-n$ .

The efficiency index (31) then satisfies

\alpha^{\frac{1}{2\left(m+1\right)-n}}\leq I\left(\omega_{n+1},2\left(m+1% \right)-n\right)\leq\left(a+1\right)^{\frac{1}{2\left(m+1\right)-n}},

with $\alpha$ and $a$ specified above. ∎

References

[1] Brent, R., Winograd, S. and Wolfe, Ph., Optimal iterative processes for root-finding. Numer Math. 20 (5) (1973), 327–341.
[2] Casulli, V. and Trigiante, D., Sui procedimenti iterativi compositi. Calcolo, XIII, IV (1976), pp. 403–420.
[3] Coman, Gh., ^†^†margin: available soon,
refresh and click here $\rightarrow$ Some practical approximation methods for nonlinear equations. Anal. Numér. Théor. Approx., 11, 1–2 (1982), pp. 41–48.
[4] Kacewitcz, B., An integral-interpolation iterative method for the solution of scalar equations, Numer. Math. 26 (4), (1976), pp. 355–365.
[5] Kung, H. T. and Traub, J. F., Optimal order and efficiency for iterations with two evaluations. SIAM. J. Numer Anal. 13, 1, (1976), pp. 84–99.
[6] Ostrowski, M. A., Solution of Equations and Systems of Equations. Academic Press. New York and London (1960).
[7] Păvăloiu, I., ^†^†margin: available soon,
refresh and click here $\rightarrow$ The Solution of the Equations by Interpolation (Romanian) Ed. Dacia Cluj-Napoca (1981).
[8] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Optimal problems concerning interpolation methods of solution of equa- tions, Publications de L’Institut Mathématique Beograd. 52, (66), (1992), pp. 113–126.
[9] Traub, J. F., Iterative Methods for the Solution of Equations. Prentice-Hall, New York (1964).
[10] Traub, J. F., Theory of Optimal Algorithms, Preprint Department of Computer Science Carnegie-Mellon University (1973) pp. 1–22.
[11] Traub, J, F. and Wozniakowski, H., Optimal radius of convergence of interpolatory iterations for operator equations. Aequationes Mathematicae, 21 (1980), pp. 159–172.
[12] Turowicz, A. B., Sur les dérivées d’ordre supérieur d’une fonction inverse, Ann. Polon Math. 8 (1960), pp. 265–269.
[13]

Received 1 X 1994

Academia Română

Institutul de Calcul

”Tiberiu Popoviciu”

P.O. Box 68

3400 Cluj-Napoca 1

România

On computational complexity in solving equations by interpolation methods

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

paper on journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On computational complexity in Solving Equations
by Interpolation Methods

1. Introduction

Definition 1.1.

Definition 1.2.

2. Interpolation Iterative Methods

2.1. Lagrange’s inverse interpolation polynomial

Remark 2.1.

2.2. Hermite Inverse Interpolating Polynomial

3. The Efficiency Index of the Chebyshev Method of Order $m+1$

Theorem 3.1.

4. The Efficiency Index for the Lagrange-Hermite Methods

Theorem 4.1.

5. Margins for the Efficiency Index in the Case of Lagrange-Hermite Methods

Lemma 5.1.

Proof.

References

Related Posts

On computational complexity in solving equations by interpolation methods

Abstract

Authors

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

paper on journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On computational complexity in Solving Equations by Interpolation Methods

1. Introduction

Definition 1.1.

Definition 1.2.

2. Interpolation Iterative Methods

2.1. Lagrange’s inverse interpolation polynomial

Remark 2.1.

2.2. Hermite Inverse Interpolating Polynomial

3. The Efficiency Index of the Chebyshev Method of Order m+1

Theorem 3.1.

4. The Efficiency Index for the Lagrange-Hermite Methods

Theorem 4.1.

5. Margins for the Efficiency Index in the Case of Lagrange-Hermite Methods

Lemma 5.1.

Proof.

References

Related Posts

On computational complexity in Solving Equations
by Interpolation Methods

3. The Efficiency Index of the Chebyshev Method of Order $m+1$