On some interpolation iterative methods with optimal convergence speed

by
I. Păvăloiu and Ioan Şerb
(Cluj-Napoca)

In this paper we study a class of iterative methods for solving equations of the form:

(1)

f\left(x\right)=0,

Or $f:I\rightarrow\mathbb{R}$ is a real function of a real variable and $I$ is an interval of the real axis.

Let us designate by $x_{1},x_{2},\ldots,x_{n+1},\ n+1$ distinct points of the interval $I$ and by $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1},\ n+1$ natural numbers such as:

(2)

\alpha_{1}+\alpha_{2}+\ldots+\alpha_{n+1}=m+1,

Or $m\in\mathbb{N}$ .

It is well known that whatever the numbers $y_{i}^{j},\ j=0,\ 1,\ldots,\alpha_{i}-1,$ $i=1,2,\ldots,n+1,$ there is only one polynomial $H_{1}$ of degree at most $m$ which verifies the conditions:

(3)

H_{1}^{\left(j\right)}\left(x_{i}\right)=y_{i}^{j},\ j=0,1,\ldots,\alpha_{i}-1% ,\ i=1,2,\ldots,n+1.

The polynomial $H_{1}\$ determined by conditions ( 3 ) has the form:

(4)

H_{1}\left(x\right)=\sum_{i=1}^{n+1}\sum_{j=0}^{\alpha_{i}-1}\sum_{k=0}^{% \alpha_{i}-j-1}y_{i}^{j}\tfrac{1}{k!j!}\left[\tfrac{\left(x-x_{i}\right)^{% \alpha_{i}}}{\omega\left(x\right)}\right]_{x=x_{i}}^{\left(k\right)}\tfrac{% \omega\left(x\right)}{\left(x-x_{i}\right)^{\alpha_{i}-j-k}},

(5)

\omega\left(x\right)={\textstyle\prod\limits_{i=1}^{n+1}}\left(x-x_{i}\right)^% {\alpha_{i}}.

If we assume that the function $f$ admits a derivative of order $m+1$ on the interval $I$ and if $y_{i}^{j}=f^{\left(j\right)}\left(x_{i}\right),\ j=0,1,\ldots,\alpha_{i}-1,\ i% =1,2,\ldots,n+1,$ SO $H_{1}$ , the Hermite polynomial of the function $f$ , relative to the nodes $x_{i},$ to the orders of multiplicity $\alpha_{i}$ , checks the equality:

(6)

f\left(x\right)-H_{1}\left(x\right)=\tfrac{f^{\left(m+1\right)}\left(\xi\right% )}{\left(m+1\right)!}\omega\left(x\right),

Or $\xi\in I$ .

In the following it is assumed that $f^{\prime}\left(x\right)\neq 0$ regardless of $x\in I$ and we designate by $F=f\left(I\right)$ . It follows that $f:I\rightarrow F$ is a bijective function and there exists $f^{-1}:F\rightarrow I$ . The inverse function $f^{-1}$ admits a derivative of order $m+1,$ for everything $x\in F.$

The order derivative $k,k\leq m+1$ on one point $y_{0}=f\left(x_{0}\right),\ y_{0}\in F$ can be calculated by the formula:

(7)

\left(f^{-1}\right)^{\left(k\right)}\left(y_{0}\right)=\sum\tfrac{\left(2k-i_{% 1}-2\right)!\left(1-\right)^{k+i_{1}-1}}{i_{2}!\ldots i_{k}!\left(f^{\prime}% \left(x_{0}\right)\right)^{2k-1}}\big{(}\tfrac{f^{\prime}\left(x_{0}\right)}{1% !}\big{)}^{i_{1}}\big{(}\tfrac{f^{\prime\prime}\left(x_{0}\right)}{2!}\big{)}^% {i_{2}}\ldots\big{(}\tfrac{f^{\left(k\right)}\left(x_{0}\right)}{k!}\big{)}^{i% _{k}},

where the above sum is extended to all integer and nonnegative solutions of the system:

(8)

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

If we assume that equation ( 1 ) has a root in the interval $I$ , this root is unique because $f^{\prime}\left(x\right)\neq 0$ regardless of $x\in I$ and we will designate it by $\bar{x}$ . So from $f\left(\bar{x}\right)=0$ it follows that $\bar{x}=f^{-1}\left(0\right).$

In the following, in the expression of the interpolation polynomial given by ( 4 ) we will take as interpolation nodes the values $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ and as values $y_{i}^{j}$ the values of the derivatives $\left(f^{-1}\right)^{\left(j\right)}\left(y_{i}\right),\ i=1,2,\ldots,n=1,\ j=% 0,1,\ldots,$ $\alpha_{i}-1$ . Therefore we obtain the Hermite interpolation polynomial for the inverse function $f^{-1}$ . This polynomial then has the following form:

(9)

H\left(y\right)=\sum_{i=1}^{n+1}\sum_{j=0}^{\alpha_{i}-1}\sum_{k=0}^{\alpha_{i% }-j-1}\left(f^{-1}\right)^{\left(j\right)}\left(y_{i}\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)}\tfrac{\omega\left(y\right)}{\left(y-y_{i}\right)^{% \alpha_{i}-j-k}},

(10)

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

From ( 6 ) the equality results

f^{-1}\left(y\right)-H\left(y\right)=\tfrac{\left(f^{-1}\right)^{\left(m+1% \right)}\left(\eta\right)}{\left(m+1\right)!}\omega\left(y\right),

Or $\eta\in F$ .

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

(11)

\bar{x}-H\left(0\right)=\tfrac{\left(f^{-1}\right)^{\left(m+1\right)}\left(% \eta_{1}\right)}{\left(m+1\right)!}\omega\left(0\right),

Or $\eta_{1}est$ a point of the smallest interval containing the points:

0,f\left(x_{1}\right),\ldots,f\left(x_{n+1}\right).

If we designate by $F_{1}$ this interval and by

M_{m+1}=\sup_{y\in F_{1}}\left|\left(f^{-1}\right)^{\left(m+1\right)}\left(y% \right)\right|,

\left|\bar{x}-H\left(0\right)\right|\leq\tfrac{M_{m+1}}{\left(m+1\right)!}% \left|\omega\left(0\right)\right|.

From ( 10 ) and the fact that $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ we deduce

(12)

\left|\bar{x}-H\left(0\right)\right|\leq\tfrac{M_{m+1}}{\left(m+1\right)!}% \left|f\left(x_{1}\right)\right|^{\alpha_{1}}\cdot\left|f\left(x_{2}\right)% \right|^{\alpha_{2}}\ldots\left|f\left(x_{n+1}\right)\right|^{\alpha_{n+1}}.

From inequality ( 12 ) it follows that if $x_{1},x_{2},\ldots,x_{n+1}$ are in a sufficiently small neighborhood of $\bar{x}$ , SO $\prod\nolimits_{i=1}^{n+1}\left|f\left(x_{i}\right)\right|^{\alpha_{i}}$ will be in a pre-given neighborhood of $0 .$ Therefore, we can assume that $H\left(0\right)$ is an approximant of the root $\bar{x}$ of equation ( 1 ).

And $\left|\bar{x}-H\left(0\right)\right|$ is not small enough, then, by successive iterations we can obtain better approximations. Let us denote by $x_{1},x_{2},\ldots,x_{n+1},$ $n+1$ initial approximations of the root $\bar{x}$ of ( 1 ). Let $x_{n+2}=H\left(0\right)=H\left(y_{1},\alpha_{1};\ldots;y_{n+1},\alpha_{n+1};0% \right),$ Or $H(y_{1},\alpha_{1};y_{2},\alpha_{2};\ldots;$ $y_{n+1},\alpha_{n+1};y)$ is the Hermite interpolation polynomial ( 9 ) of the function $f^{-1}$ relative to nodes $y_{1},y_{2},\ldots,y_{n+1}$ to the respective orders of multiplicity $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ And $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots,n+1$ . If we now consider the new node system $x_{2},x_{3},\ldots,x_{n+1},x_{n+2}$ an obtains a new approximation $x_{n+3}=H\left(y_{2},\alpha_{1};y_{3},\alpha_{2};\ldots;y_{n+2},\alpha_{n+1};0\right)$ and so on.

But, if we put the knots away $x_{1},x_{2},\ldots,x_{n+1}$ in order $x_{i_{1}},x_{i_{2}},\ldots,$ $x_{i_{n+1}}$ we obtain a new sequence of approximations of $\bar{x}$ , given by the formulas

(13)

\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}};0\right)=H\left(0% \right)\\ \!\!x_{n+s+2}\!=\!H\left(y_{i_{s+1}},\alpha_{i_{1}};\ldots;y_{i_{n+1}},\alpha_% {{}_{n+1-s}};y_{n+2},\alpha_{i_{n+2-s}};\ldots;y_{n+s+1},\alpha_{i_{n+1}};0% \right),\\ \qquad\qquad s=1,2,\ldots,n,\\ \!\!x_{n+s+2}\!=\!H\left(y_{s+1},\alpha_{i_{1}};y_{s+2},\alpha_{i_{2}};\ldots;% y_{n+s+1},\alpha_{i_{n+1}};0\right),\ s=n+1,n+2,\ldots\end{array}\right.

Or $y_{i}=f\left(x_{i}\right),\ i=1,2,\ldots$

For each permutation of the numbers $1,2,\ldots,n+1$ we obtain a sequence of approximations of $\bar{x}$ given by ( 13 ). In all, it $and$ a $\left(n+1\right)!$ sequences of approximations of $\bar{x}$ .

The question is asked to choose among these $\left(n+1\right)!$ suites, the one that ensures the maximum convergence speed.

To solve this problem, we consider the following equations

(14)	$\displaystyle P\left(t\right)=$	$\displaystyle t^{n+1}-a_{n+1}t^{n}-a_{n}t^{n-1}-\ldots-a_{2}t-a_{1}=0,$
(15)	$\displaystyle Q\left(t\right)=$	$\displaystyle t^{n+1}-a_{1}t^{n}-a_{2}t^{n-1}-\ldots-a_{n}t-a_{n+1}=0,$
(16)	$\displaystyle R\left(t\right)=$	$\displaystyle t^{n+1}-a_{i_{1}}t^{n}-\ldots-a_{i_{n}}t-a_{i_{n+1}}=0,$

Or $a_{1},a_{2},\ldots,a_{n+1}\in R$ check the relationships

(17)		$\displaystyle a_{1}+a_{2}+\ldots+a_{n+1}>$	$\displaystyle 1,\ a_{i}\geq 0,\qquad i=1,2,\ldots,n+1,$
(18)		$\displaystyle a_{n+1}\geq$	$\displaystyle a_{n}\geq\ldots\geq a_{2}\geq a_{1},$

And $i_{1},i_{2},\ldots,i_{n+1}$ is any permutation of $1,2,\ldots,n+1.$

Lemme 1.

And $a_{1},a_{2},\ldots,a_{n+1}$ verify the relation ( 17 ), then every equation of the form ( 16 ) has a single root greater than unity. If, moreover, $a_{1},a_{2},\ldots,a_{n+1}$ verify condition ( 18 ) and if $a, b, c$ are respectively the positive roots of equations ( 14 ), ( 15 ) or ( 16 ), then we have the inequalities

(19)

1<b\leq c\leq a

Demonstration..

We designate by $s$ the largest number for which $a_{i_{s}}\neq 0$ . SO $a_{i_{s+1}}=a_{i_{s+2}}=\ldots=a_{i_{n}}=a_{i_{n+1}}=0,\ a_{i_{s}}\neq 0$ . Let us designate by $\psi$ the function defined by $\psi\left(t\right)=R\left(t\right)/t^{n-s+1}$ . On a $\psi\left(1\right)=1-a_{i_{1}}-\ldots-a_{i_{s}}<0$ And $\lim\limits_{t\rightarrow\infty}\psi\left(t\right)=\infty,$ so the equation $\psi\left(t\right)=0$ admits a root greater than unity. Then, the equation $R\left(t\right)=0$ has a root greater than 1. The uniqueness of this root follows immediately by considering the function $f\left(t\right)=-t^{n+1}R\left(1\backslash t\right)$ which verifies the condition $f^{\prime}\left(t\right)>0$ For $t>0$ .

To prove the inequalities ( 19 ) it is enough 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)$
	$\displaystyle=$	$\displaystyle\left(a_{1}-a_{i_{1}}\right)b^{n}+\left(a_{2}-a_{i_{2}}\right)b^{% n-1}+\ldots+\left(a_{n}-a_{i_{n}}\right)b+a_{n+1}-a_{i_{n+1}}$
	$\displaystyle=$	$\displaystyle\left(b-1\right)\big{[}\left(a_{1}-a_{i_{1}}\right)b^{n-1}+\left(% a_{1}+a_{2}-a_{i_{1}}-a_{i_{2}}\right)b^{n-2}+\ldots$
		$\displaystyle+(a_{1}+a_{2}+\ldots+a_{n-1}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{n-1% }})b$
		$\displaystyle+a_{1}+\ldots+a_{n}-a_{i_{1}}-a_{i_{2}}-\ldots-a_{i_{n}}\big{]}\leq 0$

because $b>1$ and from ( 18 ) it results

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

Similarly, we show that $R\left(a\right)\geq 0.$

Be it now $i_{1},i_{2},\ldots,i_{n+1}$ a permutation of numbers $1,2,\ldots,n+1,$ for which the natural numbers $\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1}$ which verify the relation ( 2 ) can be arranged in ascending order

(20)

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

The corresponding sequence of nodes is $x_{i_{1}},x_{i_{2}},\ldots,x_{i_{n+1}}$ and the corresponding sequence of successive approximations of $\bar{x}$ is given by ( 13 ). If we denote by

(21)

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

and by

(22)

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

then the sequence of approximations ( 13 ) becomes $\left(u_{n}\right)_{n=1}^{\infty}$ Or

(23)

x_{n+s+2}=H\left(y_{s+1},a_{1};y_{s+2},a_{2};\ldots;y_{s+n+1},a_{n+1};0\right),

$s=0,1,\ldots,$ Or $y_{i}=f\left(u_{i}\right),\ i=1,2,\ldots\ .$

Inequality ( 12 ) becomes

(24)

\left|\bar{x}-H\left(0\right)\right|=\left|\bar{x}-u_{n+2}\right|\leq\tfrac{M}% {\left(m+1\right)!}\left|f\left(u_{1}\right)\right|^{a_{1}}\ldots\left|f\left(% u_{n+1}\right)\right|^{a_{n+1}},

Or $M=\sup\limits_{y\in F}\left|\left(f^{-1}\right)^{\left(m+1\right)}\left(y% \right)\right|$ . If we designate by $\beta=\sup\limits_{x\in I}\left|f^{\prime}\left(x\right)\right|$ then from ( 23 ) and ( 24 ) we obtain

(25)

\left|\bar{x}-u_{n+2}\right|\leq\tfrac{M\beta^{m+1}}{\left(m+1\right)!}\left|% \bar{x}-u_{1}\right|^{a_{1}}\ldots\left|\bar{x}-u_{n+1}\right|^{a_{n+1}}.

In general, is the elements of the sequence $\left(u_{n}\right)_{n=1}^{\infty}$ are in the interval $I$ , SO

(26)

\left|\bar{x}-u_{n+s+1}\right|\leq\tfrac{M\beta^{m+1}}{\left(m+1\right)!}\left% |\bar{x}-u_{s}\right|^{a_{1}}\ldots\left|\bar{x}-u_{s+n}\right|^{a_{n+1}}

$s=1,2,\ldots$ . If we write $\rho_{i}=\beta\sqrt{\tfrac{\beta M}{\left(m+1\right)!}}\left|\bar{x}-u_{i}% \right|,i=1,2,\ldots,$ then from ( 26 ) we obtain

(27)

\rho_{n+s+1}\leq\rho_{n+s}^{a_{n+1}}\rho_{n+s-1}^{a_{n}}\ldots\rho_{s+1}^{a_{2% }}\rho_{s}^{a_{1}},

$s=1,2,\ldots$ .

We now assume that there exists a number $d,0<d<1$ such as

(28)

\rho_{i}\leq d^{\omega^{i}},\qquad i=1,2,\ldots,n+1,

Or $\omega$ is the only positive root of the equation

(29)

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

If we assume that for a $s$ fixed $s\geq 2$ We have

(30)

\rho_{n+s}\leq d^{x+s},

then from ( 27 ), ( 28 ) and ( 29 ) it immediately follows that

(31)		$\displaystyle\rho_{n+s+1}$	$\displaystyle\leq d^{a_{n+1}\omega^{n+s}}\cdot d^{a_{n}\omega^{n+s-1}}\ldots d% ^{a_{2}\omega^{s+1}}\cdot d^{a_{1}\omega^{s}}$
		$\displaystyle=d^{a_{n+1}\omega^{n+s}+a_{n}\omega^{n+s-1}+\ldots+a_{2}\omega^{s% +1}+a_{1}\omega^{s}}=d^{\omega^{n+s+1}},$

and by induction it follows that

(32)

\rho_{n}\leq d^{\omega^{n}},n=1,2,\ldots

The solution $\omega$ of equation ( 29 ) is called the order of convergence of the iterative method ( 23 ). We have

(33)

\left|\bar{x}-u_{n}\right|\leq\tfrac{1}{\beta\sqrt[m]{\frac{M\beta}{\left(m+1% \right)!}}}d^{\omega^{n}},n=1,2,\ldots,

from which it follows that $\lim\limits_{n\rightarrow\infty}u_{n}=\bar{x}$ . ∎

We note that the order of convergence of the methods ( 13 ) depends on the positive root $\omega$ of equation ( 29 ).

Taking into account the lemma and the above considerations we obtain the following theorem:

Theorem 1 .

Either $i_{1},i_{2},\ldots,i_{n+1}$ a permutation of $1,2,\ldots,n+1$ And $M\left(i_{1},i_{2},\ldots,i_{n+1}\right)$ the corresponding iterative method ( 13 ) . If $\alpha_{i_{1}}\leq\alpha_{i_{2}}\leq\ldots\leq\alpha_{i_{n+1}}$ Or $\alpha_{i_{j}}est$ the order of multiplicity of the knot $y_{i_{j}}=f(x_{i_{j}}),$ $j=1,2,\ldots,n+1,$ then under conditions ( 20 ) method ( 23 ) ensures the order of convergence $\omega$ maximum, among the $\left(n+1\right)!$ iterative methods of the form ( 13 ).

Bibliography

[1]
[2] Ostrowski, M. A., Solution of Equations and Systems of Equations, Academic Press, New-York and London, 1960.
[3] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Solving equations by interpolation , Ed. Dacia, 1981.
[4] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Iancu, C., The solution of equations by inverse interpolation of Hermite type , Seminar of functional analysis and Numerical methods, ”Babeş-Bolyai” University, Research Seminaries, Preprint Nr. 4, (1981), 72–84.
republished in: Mathematica (Cluj), 26(49) (1984), no. 2, pp. 115–123.

Recu le 5.III.1983

Babeş-Bolyai University Computing Institute

37 Republic Street

3400 Cluj-Napoca

On some interpolation iterative methods with optimal convergence speed

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

Paper on the journal website

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form

On some interpolation iterative methods with optimal convergence speed

Lemme 1.

Demonstration..

Theorem 1 .

Bibliography

Related Posts