On the convergence of a class of iteration methods of JF Traub

by
I. Păvăloiu
(Cluj)

1. Consider the operational equation

(1)

P\left(x\right)=\theta,

Or $P$ is an operator defined on the Banach space $X$ with values in the normed linear space $Y .$

In case $P\left(x\right)$ is a real function of the real variable $x$ , JF Traub [ 5 ] studies the order of the following iterative function attached to equation ( 1 ):

(2)

\psi\left(x\right)=\Phi\left(x\right)-\tfrac{P\left(\Phi\left(x\right)\right)}% {P^{\prime}\left(x\right)}.

In work [ 4 ] , we extended the iterative function ( 2 ) for more general equations of form ( 1 ) and we easily studied its order by employing a notion of order of an iterative operator, a more general notion than that employed [ 5 ] .

In this note we will study the convergence of the iterative process which results from the following iterative operator studied by us in [ 4 ]

(3)

R\left(x\right)=Q\left(x\right)-\left[P^{\prime}\left(x\right)\right]^{-1}P% \left(Q\left(x\right)\right),

Or $P^{\prime}\left(x\right)est$ the Fréchet derivative of the operator $P$ And $Q$ is an arbitrary iterative operator attached to equation ( 1 ). We will then consider a special case of operator ( 3 ) by the particularization of the operator $Q .$

2. The iterative operator ( 3 ) obviously leads us to the following iterative method:

(4)

x_{n+1}=Q\left(x_{n}\right)-\left[P^{\prime}\left(x_{n}\right)\right]^{-1}P% \left(Q\left(x_{n}\right)\right),\ \ \ \ n=0,1,\ldots,x_{0}\in X,

where for the clarity of the statements and demonstrations which follow we will assume that the operator $Q$ has the shape

(5)

Q\left(x\right)=x+\varphi\left(x\right).

Let x ${}_{0}\in X$ And $\delta$ a real and positive number. We denote by $S\left(x_{0},\delta\right)$ the whole $\{x\in X:\left\|x-x_{0}\right\|\leq\delta\}.$

It is assumed that in the sphere $S\left(x_{0},\delta\right)$ previously defined the following conditions are met.

1.i)

The operator $P\left(x\right)$ admits derivatives in the Fréchet sense up to order $k$ inclusively and $\sup\limits_{x\in S\left(x_{0},\delta\right)}\left\|P(x)^{\left(k\right)}\left% (x\right)\right\|\leq M_{k}<\infty,\$ Or $k\geqq 2$ is a natural number. We denote by $M_{2}=\sup\limits_{x\in S\left(x_{0},\delta\right)}\left\|P^{\prime\prime}% \left(x\right)\right\|.$
2.i)

$\Big{\|}\sum\limits_{s=0}^{k-1}\frac{P^{\left(s\right)}\left(x\right)}{s!}% \varphi^{s}\left(x\right)\Big{\|}\leq\alpha\left\|P\left(x\right)\right\|^{k}$ for everything $x\in S\left(x_{0},\delta\right)$ Or $\alpha$ is a non-negative real number.
3.i)

$\left\|\varphi\left(x\right)\right\|\leq\beta\left\|P\left(x\right)\right\|$ for everything $x\in S\left(x_{0},\delta\right),$ Or $\beta$ is a positive real number.
4.i)

The operator $P^{\prime}\left(x\right)$ admits a bounded inverse for all $x\in S\left(x_{0},\delta\right)$ that is to say he $y$ has a real and positive constant $B$ for which $\|\left[P^{\prime}\left(x\right)\right]^{-1}\|\leq B.$
5.i)

The generalized divided difference [ 2 ] , $\left[x,y;Q\right]$ of the operator $Q$ is bounded in norm for all $x,y\in S\left(x_{0},\delta\right)$ that is to say he $y$ has a real and non-negative constant $\lambda$ for which $\left\|\left[x,y;Q\right]\right\|\leq\lambda.$
6.i)

$\varepsilon_{0}=\rho_{0}^{\frac{1}{k}}\left\|P\left(x_{0}\right)\right\|<1$ Or

$\rho_{0}=M_{2}B\left(\tfrac{M_{k}\beta^{k}}{k!}+\alpha\right)\left[\tfrac{1}{2% }B\left(\tfrac{M_{k}\beta^{k}}{k!}+\alpha\right)h_{0}^{k-1}+\beta\right]\ \;\;% \text{et\ }h_{0}=\left\|P\left(x_{0}\right)\right\|$
7.i)

Either

$r=\lambda\rho_{0}^{-\frac{1}{k}}\mu_{0}\tfrac{\varepsilon_{0}^{k+1}}{1-% \varepsilon_{0}^{k+1}}+\beta h_{0}+\lambda\mu_{0}h_{0}$

And

$r^{\prime}=\mu_{0}\Big{[}\tfrac{\rho_{0}^{-\frac{1}{k}}\varepsilon_{0}^{k+1}}{% 1-\varepsilon_{0}^{k-1}}+h_{0}\Big{]}\ \text{o\`{u}}\ \mu_{0}=\beta+B\big{(}% \tfrac{M_{k}\beta^{k}}{k!}+\alpha\big{)}h_{0}^{k-1}$

we assume that max $\ \{r,r^{\prime}\}\leq\delta.$

Theorem 1 .

If assumptions 1.i)–7.i) are fulfilled then with respect to the class of iterative methods ( 4 ) we have the following properties:

1.c)

equation ( 1 ) has at least one solution $\bar{x}\in S\left(x_{0},\delta\right),$
2.c)

$\lim\limits_{n\rightarrow\infty}x_{n}=\bar{x},$
3.c)

$\left\|P\left(x_{n+1}\right)\right\|\leq\delta_{0}\left\|P\left(x_{n}\right)% \right\|^{k+1}$
4.c)

$\left\|x_{n+1}-\bar{x}\right\|\leq\mu_{0}\rho_{0}^{-\frac{1}{k}}\frac{% \varepsilon_{0}^{\left(k+1\right)^{n+1}}}{1-\varepsilon_{0}^{k+1}},\ \ n=0,1,\ldots$

Demonstration..

To make writing easier we will write $k+1=p.$ First we will show that $Q\left(x_{0}\right)\in S\left(x_{0},\delta\right).$ Indeed from ( 5 ) we deduce

\left\|Q\left(x_{0}\right)-x_{0}\right\|=\left\|\varphi\left(x_{0}\right)% \right\|\leq\beta\left\|P\left(x_{0}\right)\right\|\leq r^{\prime}\leq\delta,

that's to say $Q\left(x_{0}\right)\in S\left(x_{0},\delta\right).$ Taking this into account and assumptions 1.i), 2.i) and 3.i) we deduce the following delimitation:

(6)

\left\|P\left(Q\left(x_{0}\right)\right)\right\|\leq\left(\tfrac{M_{k}\beta^{k% }}{k!}+\alpha\right)\left\|P\left(x_{0}\right)\right\|^{k}

From the previous inequality and from ( 4 ), taking into account hypotheses 3.i) and 4.i) we deduce

\left\|x_{1}-x_{0}\right\|\leq\mu_{0}\left\|P\left(x_{0}\right)\right\|\leq\delta,

that's to say $x_{1}\in S\left(x_{0},\delta\right).$ Based on the fact that $x_{1}$ $\in S\left(x_{0},\delta\right)$ and from the preceding inequalities we will easily deduce the following inequality:

(7)

\left\|P\left(x_{1}\right)\right\|\leq\rho_{0}\left\|P\left(x_{0}\right)\right% \|^{\rho}

Or $\rho_{0}$ is the constant which intervenes in hypothesis 6.i). From inequality ( 7 ) and 6.i) we deduce

\left\|P\left(x_{1}\right)\right\|\leq\rho_{0}\left\|P\left(x_{0}\right)\right% \|^{p-1}\left\|P\left(x_{0}\right)\right\|=\big{(}\rho_{0}^{\frac{1}{p-1}}% \left\|P\left(x_{0}\right)\right\|\big{)}^{p-1}\left\|P\left(x_{0}\right)\right\|

that's to say

(8)

\left\|P\left(x_{1}\right)\right\|\leq\left\|P\left(x_{0}\right)\right\|.

From the preceding inequality it follows that for subsequent considerations the constants $\rho_{0}\$ And $\mu_{0}$ can remain unchanged throughout the demonstration. We will use the principle of induction.

We will assume that the following properties take place: $Q\left(x_{i}\right)\in S\left(x_{0},\delta\right),$

	$\displaystyle x_{i+1}$	$\displaystyle\in S\left(x_{0},\delta\right),\qquad i=1,2,\ldots,n-1;$
	$\displaystyle\left\\|P\left(x_{i}\right)\right\\|$	$\displaystyle\leq\rho_{0}\left\\|P\left(x_{i-1}\right)\right\\|^{p},\quad\left\\|% P\left(x_{i}\right)\right\\|<\left\\|P\left(x_{i-1}\right)\right\\|,\qquad i=1,2,% \ldots,n.$

In these hypotheses we will show that:

	$\displaystyle Q\left(x_{n}\right)$	$\displaystyle\in S\left(x_{0},\delta\right),\qquad x_{n+1}\in S\left(x_{0},% \delta\right),$
	$\displaystyle\left\\|P\left(x_{n+1}\right)\right\\|$	$\displaystyle\leq\rho_{0}\left\\|P\left(x_{n}\right)\right\\|^{p},\quad\left\\|P% \left(x_{n+1}\right)\right\\|<\left\\|P\left(x_{n}\right)\right\\|.$

In fact we have

	$\displaystyle\left\\|Q\left(x_{n}\right)-x_{0}\right\\|$	$\displaystyle\leq\lambda\big{(}\left\\|x_{n}-x_{n-1}\right\\|+\ldots+\left\\|x_{1% }-x_{0}\right\\|\big{)}+\left\\|Q\left(x_{0}\right)-x_{0}\right\\|$
		$\displaystyle\leq\lambda\rho_{0}^{-\frac{1}{k}}\mu_{0}\tfrac{\varepsilon_{0}^{% k+1}}{1-\varepsilon_{0}^{k+1}}+\left(\lambda\mu_{0}+\beta\right)\left\\|P\left(% x_{0}\right)\right\\|\leq\delta.$

That's to say $Q\left(x_{n}\right)\in S.$ By analogy we have

	$\displaystyle\left\\|x_{n+1}-x_{0}\right\\|$	$\displaystyle\leq\left\\|x_{n+1}-x_{n}\right\\|+\ldots+\left\\|x_{1}-x_{0}\right\\|$
		$\displaystyle\leq\mu_{0}\Big{[}\rho_{0}^{-\frac{1}{k}}\tfrac{\varepsilon^{k+1}% }{1-\varepsilon^{k+1}}+\left\\|P\left(x_{0}\right)\right\\|\Big{]}\leq\delta$

which shows us that $x_{n+1}\in S\left(x_{0},\delta\right)$ . Proceeding in the same way as in the case of inequalities ( 7 ) and taking into account the fact that $\left\|P\left(x_{n}\right)\right\|<\left\|P\left(x_{n-1}\right)\right\|$ we deduce the inequality

(9)

\left\|P\left(x_{n+1}\right)\right\|\leq\rho_{0}\left\|P\left(x_{n}\right)% \right\|^{p}.

That is, inequality 3.c). By virtue of the principle of induction and what has just been proven, it follows that the stated properties are true for any natural number $n .$

From these considerations the following inequalities immediately result:

(10)

\left\|x_{i}-x_{i-1}\right\|\leq\rho_{0}^{-\frac{1}{k}}\mu_{0}\varepsilon_{0}^% {p^{i-1}}

To prove the convergence of the sequence we will show that it satisfies the Cauchy condition. Indeed from ( 10 ), we deduce

(11)

\left\|x_{n+s}-x_{n}\right\|\leq\mu_{0}\rho_{0}^{-\frac{1}{k}}\tfrac{% \varepsilon_{0}^{p^{n}}}{1-\varepsilon_{0}^{p}},\ \;\;\text{pour, }n=0,1,\ldots,\ s=0,1,\ldots

If we go to the limit in the inequality ( 11 ) for $s\rightarrow\infty$ we have inequality $\left\|\bar{x}-x_{n}\right\|\leq\mu_{0}\rho_{0}^{-\frac{1}{k}}\frac{% \varepsilon^{p^{n}}}{1-\varepsilon_{0}^{p}},$ which proves inequality (4.c). The fact that the sequence is convergent results from ( 11 ) and from the fact that the space $X$ is complete. Thus the theorem is proven. ∎

Noticed .

In the work [ 3 ] we introduced a notion of characterization of the order of convergence of an iterative process (Definition 2).

In the sense of this definition, from 6.i) and 3.c) it results that the iterative process studied by us has the order of convergence $k+1.$ ∎

3. In the following, we will use Theorem 1 to characterize the convergence of the following iterative process:

(12)		$\displaystyle x_{n+1}$	$\displaystyle=x_{n}-\left[P^{\prime}\left(x_{n}\right)\right]^{-1}P\left(x_{n}% \right)-\left[P^{\prime}\left(x_{n}\right)\right]^{-1}P\big{(}x_{n}-\left[P^{% \prime}\left(x_{n}\right)\right]^{-1}P\left(x_{n}\right)\big{)},$
	$\displaystyle x_{0}$	$\displaystyle\in X,\ n=0,1,\ldots$

This process is obtained from ( 4 ) for $Q\left(x\right)=x-\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x\right).$ In this case, we observe that $\varphi\left(x\right)=-\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x% \right).$

It is shown in the following that some assumptions of Theorem 1 are satisfied by method ( 12 ), and the rest will be modified by us, according to the requirements of the particularities of the iterative method ( 12 ).

Let us designate by $\delta^{\prime}$ the radius of the sphere $S$ which we considered in Theorem 1 .

We immediately observe that hypothesis 2.i) is satisfied in this case for $\alpha=0,$ and hypothesis 3.i) is satisfied for $\beta=B.$

In the sphere defined above, let us assume that the following conditions relating to the iterative method ( 12 ) are met.

1.i')

property 1.i) takes place for $k=2$ And $x\in S\left(x_{0},\delta^{\prime}\right)$
2.i')

property 4.i) holds for all $x\in S\left(x_{0},\delta^{\prime}\right)$
3.i')

property 5.i) holds for all $x\in S\left(x_{0},\delta^{\prime}\right)$
4.i')

$\varepsilon_{0}=\sqrt{\rho_{0}}\left\|P\left(x_{0}\right)\right\|<1,$ Or $\rho_{0}=\frac{M_{2}^{2}B^{3}}{8}\left[M_{2}B^{3}h_{0}+4B\right]$ And $h_{0}=\left\|P\left(x_{0}\right)\right\|$
5.i')

In hypothesis 7.i) of Theorem 1 we assume that

$\displaystyle r^{\prime}$ $\displaystyle=\tfrac{\lambda}{\sqrt{\rho_{0}}}\tfrac{\varepsilon}{1-% \varepsilon_{0}^{3}}+\left(\lambda\mu_{0}+\beta\right)\left\|P\left(x_{0}% \right)\right\|\ \;\text{et \ }r=\mu_{0}\bigg{[}\tfrac{\varepsilon_{0}^{3}}{% \sqrt{\rho_{0}\left(1-\varepsilon_{0}^{3}\right)}}+\left\|P\left(x_{0}\right)% \right\|\bigg{]}$

$\displaystyle\text{o\`{u}}\ \ \mu_{0}$ $\displaystyle=\tfrac{B}{2}\left(2+M_{2}B^{2}h_{0}\right)$

It is assumed that max $\{r,r^{\prime}\}\leq\delta^{\prime}.$

We can then state the following result:

Theorem 2 .

If assumptions 1i')–5i') are fulfilled, then relative to the iterative method ( 12 ) we have the following properties:

1.c')

Equation ( 1 ) has at least one solution $\bar{x}\in S\left(x_{0},\delta^{\prime}\right)$
2.c')

$\lim\limits_{n\rightarrow\infty}x_{n}=\bar{x}$
3.c')

$\left\|P\left(x_{n+1}\right)\right\|\leq\rho_{0}\left\|P\left(x_{n}\right)% \right\|^{3}$ , For $n=0,1,\ldots,$
4.c')

$\left\|x_{n}-\bar{x}\right\|\leq\frac{\mu_{0}\varepsilon_{0}^{3n}}{\sqrt{\rho_% {0}\left(1-\varepsilon_{0}^{3}\right)}}$ , For $n=0,1,\ldots,$

Obviously, from what we have seen, Theorem 1 has a general character since it concerns the convergence of a large class of iterative methods. From 3.i') and 3.c') it follows that method ( 12 ) has the order of convergence $3$ . This method therefore has the same order as the well-known Tchébycheff method but on the other hand method ( 12 ) has a simpler form and in certain cases we can assume that it is easier to use, since it does not require the calculation of the second derivative of the operator $P .$

Bibliography

[1]
[2] Păvăloiu, I., ^†^†margin: clickable $\rightarrow$ Interpolation in normed linear spaces and applications , Mathematica (Cluj), 12 (35) , 1, 149–158 (1970).
[3] Păvăloiu, I., ^†^†margin: clickable $\rightarrow$ On iterative processes with a high order of convergence , Mathematica, Cluj, 12 (35) , 2, 309–324 (1970).
[4] Păvăloiu, I., ^†^†margin: clickable $\rightarrow$ Asupra operatorilor iterativi , Studii şi cercetări matematice, 10, 23 , 1537–1544 (1971).
[5] Traub, JF, Iterative Methods for the Solution of Equations , Prentice-Hall. Inc. Englewood Cliffs NJ, 1964.

Received on 7.IX.1972

Calculation Institute of Cluj

al Academiei Republicii Socialist România

On the convergence of a class of iteration methods of J. F. Traub

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

Print ISSN

Online ISSN

References

Paper (preprint) in HTML form