On the iterative methods with high convergence orders

by
I. Pavaloiu
in Cluj

Either $X$ a Banach space and

(1)

P\left(x\right)=\theta

an operational equation where the operator $P$ is defined on space $X$ and with values in the normed linear space $AND$ .

For the resolution of equation ( 1 ) we generally consider another operator $Q$ defined on space $X$ and with values in the same space.

Definition 1 .

We say that the operator $Q$ is an iterative operator attached to equation ( 1 ) if any element $\bar{x}\in X$ for which $P\left(\bar{x}\right)=\theta$ , is a fixed point for the operator $Q .$

Using the iterative operator $Q$ we will attach to equation ( 1 ) the following iterative process.

(2)

x_{n+1}=Q\left(x_{n}\right),\ n=0,1,\ldots,\ x_{0}\in X

Definition 2 .

And $x_{0}\in X$ , the iterative operator $Q$ and the real and positive number $\rho$ meet the conditions:

a) $\left\|P\left(x_{n+1}\right)\right\|\leq\rho\left\|P\left(x_{n}\right)\right\|% ^{k},\$ For $n=0,1,\ldots,$ Or $k\geq 2$ is a natural number.

b) $\rho^{\frac{1}{k-1}}\left\|P\left(x_{0}\right)\right\|<1.$

Then we will say that the iterative process ( 2 ) has the order of convergence $k .$

Regarding the notion of order of convergence introduced previously, the following lemma takes place.

Lemme 1.

If the iterative process ( 2 ) has the order of convergence $k$ SO $\lim\limits_{n\rightarrow\infty}\left\|P\left(x_{n}\right)\right\|=0,$ moreover, if the following $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent and the operator P is continuous, then $\bar{x}=\lim\limits_{n\rightarrow\infty}x_{n}$ is a solution to equation ( 1 ) .

Demonstration.

Since the process ( 2 ) has the order of convergence $k$ it follows that there is an element $x_{0}\in X$ for which

(3)

\varepsilon_{0}=\rho^{\frac{1}{k-1}}\left\|P\left(x_{0}\right)\right\|<1

Or $\rho$ is a real and positive constant for which condition a) of definition 2 is also fulfilled.

Using condition a) of Definition 2, for $n=0,1,\ldots,$ we get

\rho^{\frac{1}{k-1}}\left\|P\left(x_{n+1}\right)\right\|\leq\left[\rho^{\frac{% 1}{k-1}}\left\|P\left(x_{n}\right)\right\|\right]^{k}

from where, while writing $\varepsilon_{n}=\rho^{\frac{1}{k-1}}\left\|P\left(x_{n}\right)\right\|$ we deduce

\varepsilon_{n+1}\leq\varepsilon_{n}^{k}.

If we apply this inequality successively for $n=0,1,\ldots,$ we get

\varepsilon_{n}\leq\varepsilon_{0}^{k^{n}}

or, if we take into account ( 3 ) we have

\lim_{n\rightarrow 0}\varepsilon_{n}=0.

Since $\rho>0$ it follows that

\lim_{n\rightarrow\infty}\left\|P\left(x_{n}\right)\right\|=0.

And $\bar{x}=\lim\limits_{n\rightarrow\infty}x_{n}$ and the operator $P$ is continuous, it follows that we have the equality:

\lim_{n\rightarrow\infty}\left\|P\left(x_{n}\right)\right\|=\left\|P\left(\bar% {x}\right)\right\|=0.

That's to say

P\left(\bar{x}\right)=\theta

what needed to be demonstrated. ∎

In definition 2 where we specified the notion of order of convergence of an iterative operator we did not include the condition that the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ given by the process ( 2 ) is convergent.

In this sense, we started from the idea that in practice we are quite rarely led by certain procedures to the exact solution of equations of form ( 1 ). Usually, for the needs of practice, we can limit ourselves to a single approximate solution. One of the simple criteria for assessing the fact that $x$ is an approximate solution for equation ( 1 ) is to check to what extent the real and positive number $\left\|P\left(x\right)\right\|$ is close to zero. Obviously, the closer it is to zero, the more we will consider that the approximate solution found can more exactly satisfy the requirements of the practical problem.

In the following, in all the convergence problems that we will study, concerning equation ( 1 ) and procedure ( 2 ) we will examine both the way in which the sequence $\left(\left\|P\left(x_{n}\right)\right\|\right)_{0}^{\infty}$ converges to zero than the way the approximate solution approaches the exact solution.

We will now present a general convergence criterion for the following $\left(x_{n}\right)_{n=0}^{\infty}$ provided by the method ( 2 ). This result can also be considered as a criterion for the existence of the solution for equation ( 1 ). For this we will assume that the iterative operator $Q$ has the form:

(3^′)

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

Theorem 2 .

[ 6 ] . Let $x_{0}\in X$ And $S=\{x\in X;\ \left\|x-x_{0}\right\|\leq\delta\}.$ If the element $x_{0}$ and the real number $\delta$ can be chosen so that in the sphere $S$ the following conditions are met:

a) the operator $P$ admits derivatives (in the Fréchet sense) up to order $k$ inclusively and $\left\|P^{\left(k\right)}\left(x\right)\right\|\leq M<+\infty$ for everything $x\in S.$

b) There exists a real and non-negative constant $\alpha,$ for which the inequality takes place

\left\|P\left(x\right)+P^{\prime}\left(x\right)\varphi\left(x\right)+\tfrac{P^% {\prime\prime}\left(x\right)}{2!}\varphi^{2}\left(x\right)+\cdots+\tfrac{P^{% \left(k-1\right)}\left(x\right)}{\left(k-1\right)!}\varphi^{k-1}\left(x\right)% \right\|\leq\alpha\left\|P\left(x\right)\right\|^{k},

for everything $x\in S.$

c) There exists a real and positive constant $\beta$ for which the inequality takes place

\left\|\varphi\left(x\right)\right\|\leq\beta\left\|P\left(x\right)\right\|,\ % \text{pour tout\ }x\in S.

d) $\rho_{0}=v\left\|P\left(x_{0}\right)\right\|<1\$ Or $v=\left(\alpha+\frac{M\beta^{k}}{k!}\right)^{\frac{1}{k-1}}.$

and) $\frac{\beta\rho_{0}}{v\left(1-\rho_{0}\right)}\leq\delta.$

Then we have the following properties for equation ( 1 ) and process ( 2 ) :

a') Equation ( 1 ) has at least one solution $\bar{x}\in S.$

b') The sequel $\left(x_{n}\right)_{n=1}^{\infty}$ is convergent and $\lim\limits_{n\rightarrow\infty}x_{n}=\bar{x}.$

c’) $\left\|x_{n+1}-x_{n}\right\|\leq\frac{\beta\rho_{0}^{k^{n}}}{v}.$
d’) $\left|\left|\bar{x}-x_{n}\right|\right|\leq\frac{\beta\rho_{0}^{k^{n}}}{v\left% (1-\rho_{0}^{k^{n}}\right)}.$
and') $\left\|P\left(x_{n+1}\right)\right\|\leq\frac{\rho_{0}^{k^{n+1}}}{v}.$

f') The iterative process ( 2 ) has the order of convergence $k,$ where the sequel $\left(x_{n}\right)_{0}^{\infty}$ is provided by ( 2 ) where $Q\left(x\right)$ has the form ( 3 ^′ ) .

Demonstration.

From condition c) the following inequality results

(4)

\left\|\varphi\left(x_{0}\right)\right\|\leq\beta\left\|P\left(x_{0}\right)% \right\|\leq\tfrac{\beta v\left\|P\left(x_{0}\right)\right\|}{v}\leq\tfrac{% \beta\rho_{0}}{v}\leq\tfrac{\beta\rho_{0}}{v\left(1-\rho_{0}\right)}\leq\delta

from which we deduce the following inequality:

\left\|x_{1}-x_{0}\right\|=\left\|\varphi\left(x_{0}\right)\right\|\leq\delta

that's to say $x_{1}\in S.$ Using hypotheses a), b) and c) and the generalized Taylor formula we deduce

	$\displaystyle\left\\|P\left(x_{1}\right)\right\\|\leq$	$\displaystyle\left\\|P\left(x_{1}\right)-\left(P\left(x_{0}\right)+\tfrac{P^{% \prime}\left(x_{0}\right)}{1!}\varphi\left(x_{0}\right)+\cdots+\tfrac{P^{\left% (k-1\right)}\left(x_{0}\right)}{\left(k-1\right)!}\varphi^{k-1}\left(x_{0}% \right)\right)\right\\|$
		$\displaystyle+\left\\|P\left(x_{0}\right)+\tfrac{P^{\prime}\left(x_{0}\right)}{% 1!}\varphi\left(x_{0}\right)+\cdots+\tfrac{P^{\left(k-1\right)}\left(x_{0}% \right)}{\left(k-1\right)!}\varphi^{k-1}\left(x_{0}\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle\tfrac{M}{k!}\left\\|x_{1}-x_{0}\right\\|^{k}+\alpha\left\\|P\left(x% _{0}\right)\right\\|^{k}\leq\left(\alpha+\tfrac{\beta^{k}M}{k!}\right)\left\\|P% \left(x_{0}\right)\right\\|^{k}$

that is to say that the inequality takes place

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

Since $\left\|x_{1}-x_{0}\right\|\leq\frac{\beta\rho_{0}}{v}$ it follows that for $n=0$ inequality c' occurs).

It is now assumed that $x_{i}\in S$ for everything $i=0,1,\ldots,n$ and we still assume that for the same values of $i$ inequalities take place

$\left\|x_{i}-x_{i-1}\right\|\leq\frac{\beta}{v}\rho_{0}^{k^{i-1}}.$ In these hypotheses we will show that $x_{n+1}\in S$ and that the inequality c') also holds for $i=n+1.$

If we proceed in the same way as previously, starting from the hypotheses made we will obtain the following inequalities.

(5)

\left\|P\left(x_{i}\right)\right\|\leq\big{(}\alpha+\tfrac{M\beta^{k}}{k!}\big% {)}\left\|P\left(x_{i-1}\right)\right\|^{k},\qquad i=1,2,\ldots,n.

By multiplying these inequalities by $in$ we deduce

v\left\|P\left(x\right)\right\|\leq\left[v\left\|P\left(x_{i-1}\right)\right\|% \right]^{k},\qquad\text{pour }i=1,2,\ldots,n

and writing $\rho_{i}=v\left\|P\left(x_{i}\right)\right\|$ there is a plow

(5^′)

\rho_{i}\leq\rho_{i-1}^{k},\ \;\;\text{pour\ }i=1,2,\ldots,n

which, by successive application, gives

(6)

\rho_{i}\leq\rho_{0}^{k^{i}},\ \;\;i=1,2,\ldots,n.

From inequalities ( 6 ) and hypothesis c) we deduce

\left\|x_{n+1}-x_{n}\right\|=\left\|\varphi\left(x_{n}\right)\right\|\leq% \tfrac{\beta\rho_{n}}{v}\leq\tfrac{\beta\rho_{0}^{k^{n}}}{v}

from which the validity of conclusion c' results). From ( 6 ) also results conclusion e').

We will now demonstrate that $x_{n+1}\in S.$ In fact we have

\left\|x_{n+1}-x_{0}\right\|\leq\tfrac{\beta}{v}\left(\rho_{0}^{k^{n}}+\rho_{0% }^{k^{n+1}}+\cdots+\rho_{0}^{k}+\rho_{0}\right)\leq\tfrac{\beta\rho_{0}}{v% \left(1-\rho_{0}\right)}\leq\delta

from which it follows that $x_{n+1}\in S.$ To demonstrate the convergence of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ we will show that this sequence is fundamental. Indeed for $p=1,2,\ldots,$ on a

(7)

\left\|x_{n+p}-x_{n}\right\|\leq\tfrac{\beta}{v}\left(\rho_{0}^{k^{n}}+\rho_{0% }^{k^{n+1}}+\ldots+\rho_{0}^{k^{n+p-1}}\right)\leq\tfrac{\beta\rho_{0}^{k^{n}}% }{v\left(1-\rho_{0}^{k^{n}}\right)}

from which taking into account hypothesis d) it results that the sequence is convergent since $X$ is a complete space.

Either $\bar{x}=\lim\limits_{n\rightarrow\infty}x_{n},$ then passing to the limit in the inequality ( 7 ) for $p\rightarrow\infty$ on a

\left\|\bar{x}-x_{n}\right\|\leq\tfrac{\beta\rho_{0}^{k^{n}}}{v\left(1-\rho_{0% }^{k^{n}}\right)}

that is, inequality d'). From inequalities ( 5 ^′ ) and hypothesis d) results property f').

Because $P$ is derivable in $S$ it follows that it is a continuous operator and therefore by passing to the limit in the inequalities ( 6 ) we easily deduce that $\left\|P\left(\bar{x}\right)\right\|=0,$ that's to say $P\left(\bar{x}\right)=\theta,$ that is, property a'). ∎

Noticed .

In the proof of Theorem 2 we did not use the fact that conditions b) and c) are fulfilled on the whole sphere $S .$ We obtain the same results if we assume that these conditions are met only for the elements of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ provided by the process ( 2 ). ∎

We will now apply Theorem 2 to present some results in the case of particular iterative processes.

1. The Newton-Kantorovici method [ 1 ] , [ 2 ] , [ 4 ] , [ 10

The Newton-Kantorovici iterative process is obtained by using the iterative operator:

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

In this case, the operator $\varphi,$ which intervenes in the previous theorem has the form

\varphi\left(x\right)=-\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x% \right).

Applying Theorem 2 for $\alpha=0,\ \beta=B_{0}$ And $k=2$ we easily demonstrate the following theorem:

Theorem 3 .

¹¹1 This theorem was demonstrated by Misovski. IP (Trudî Mat. i Steklova 28, 145-147 (1949).

Either $x_{0}\in X$ And $S=\{x\in X;\left\|x-x_{0}\right\|\leq\delta\}.$ And $x_{0}$ And $\delta$ can be chosen such that the following conditions are satisfied:

a) The operator $\left[P^{\prime}\left(x\right)\right]^{-1}$ exists and it is limited for $x\in S$ that's to say $\big{\|}\left[P^{\prime}\left(x\right)\right]^{-1}\big{\|}\leq B_{0}<+\infty.$

b) The operator $P\left(x\right)$ admits a second derivative (in the Fréchet sense) and this derivative is bounded, that is to say, $\left\|P^{\prime\prime}\left(x\right)\right\|\leq M<+\infty,$ for everything $x\in S$

c) $B_{0}^{2}M\left\|P\left(x_{0}\right)\right\|<2.$

d) $\frac{2\rho_{0}}{B_{0}M\left(1-\rho_{0}\right)}\leq\delta\ \$ Or $\rho_{0}=\frac{B_{0}^{2}M\left\|P\left(x_{0}\right)\right\|}{2}$ .

Then the following properties hold for equation ( 1 ) and the Newton-Kantorovici process.

a') Equation ( 1 ) has at least one solution $\bar{x}\in S^{\prime}.$

b') The sequel $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent and $\lim\limits_{n\rightarrow\infty}x_{n}=\bar{x}.$

c’) $\left\|x_{n+1}-x_{n}\right\|\leq\frac{2\rho_{0}^{2^{n}}}{B_{0}M}$

d’) $\left\|\bar{x}-x_{n}\right\|\leq\frac{2\rho_{0}^{2^{n}}}{B_{0}M\left(1-\rho_{0% }^{2^{n}}\right)},\$ or $x_{n}=R\left(x_{n-1}\right).$

e') The Newton-Kantorovici process has order of convergence 2.

2. Tchébycheff's method [ 3 ] , [ 11 ]

For this method we consider the following iterative process:

Either

(8)

R\left(x\right)=x-\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x\right)-% \tfrac{1}{2}\left[P^{\prime}\left(x\right)\right]^{-1}P^{\prime\prime}\left(x% \right)\Big{\{}\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x\right)\Big{% \}}^{2}

and the corresponding iterative method is

(9)

x_{n+1}=R\left(x_{n}\right),\ n=0,1,\ldots\ \text{et }x_{0}\in X.

If we write

\varphi\left(x\right)=-\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x% \right)-\tfrac{1}{2}\left[P^{\prime}\left(x\right)\right]^{-1}P^{\prime\prime}% \left(x\right)\Big{\{}\left[P^{\prime}\left(x\right)\right]^{-1}P\left(x\right% )\Big{\}}^{2}

then the operator $R\left(x\right)$ has the form ( 3 ^′ ).

We immediately check the equality:

	$\displaystyle P\left(x\right)+P^{\prime}\left(x\right)\varphi\left(x\right)+% \tfrac{1}{2}P^{\prime\prime}\left(x\right)\varphi^{2}\left(x\right)=$
(10)		$\displaystyle=\tfrac{1}{2}P^{\prime\prime}\left(x\right)P^{\prime}\left(x% \right)^{-1}P\left(x\right)P^{\prime}\left(x\right)^{-1}P^{\prime\prime}\left(% x\right)\{P^{\prime}\left(x\right)^{-1}P\left(x\right)\}^{2}+$
	$\displaystyle\quad+\tfrac{1}{8}P^{\prime\prime}\left(x\right)\Big{\{}P^{\prime% }\left(x\right)^{-1}P^{\prime\prime}\left(x\right)\{P^{\prime}\left(x\right)^{% -1}P\left(x\right)\}^{2}\Big{\}}^{2}$

Theorem 4 .

Either $x_{0}\in X$ And $S=\{x\in X:\left\|x-x_{0}\right\|\leq\delta\}$ If the element $x_{0}$ and the real number $\delta$ can be chosen so that the following conditions are met:

a) the operator $P\left(x\right)$ admits derivatives (in the Fréchet sense) up to and including order three for all $x\in S$ And

\sup\limits_{x\in S}\left\|P^{\prime\prime\prime}\left(x\right)\right\|\leq M_% {3}<+\infty.

b) The operator $P^{\prime}\left(x\right)^{-1}$ exists and it is bounded, that is to say $\big{\|}\left[P^{\prime}\left(x\right)\right]^{-1}\big{\|}$ $\leq B_{0}<+\infty,$ for everything $x\in S.$

c) Either

	$\displaystyle M_{2}$	$\displaystyle=\left\\|P^{\prime\prime}\left(x_{0}\right)\right\\|+M_{3}\delta,\;\;$
	$\displaystyle M_{1}$	$\displaystyle=\left\\|P^{\prime}\left(x_{0}\right)\right\\|+M_{2}\delta,\$
	$\displaystyle M_{0}$	$\displaystyle=\left\\|P\left(x_{0}\right)\right\\|+M_{1}\delta$

\nu=B_{0}\left(1+\tfrac{1}{2}M_{2}B_{0}^{2}M_{0}^{2}\right)\ \;\text{et \ }\mu=\tfrac{1}{2}M_{2}^{2}B_{0}^{4}\left(1+\tfrac{1}{4}M_{2}B_{0}^{2}M_{0}% \right).

We assume that we have the inequality:

\rho_{0}=\sqrt{\mu+\tfrac{M_{3}\nu^{3}}{6}}\left\|P\left(x_{0}\right)\right\|<1.

\tfrac{\nu\rho_{0}}{\sqrt{\mu+\frac{M_{3}\nu^{3}}{6}}\left(1-\rho_{0}\right)}% \leq\delta.

Then all the conclusions of Theorem 2 are valid for

k=3,\ \beta=\nu,\ \alpha=\mu\ \text{et }v=\sqrt{\mu+\tfrac{\nu^{3}M_{3}}{6}.}

In the following, we will study the convergence of the Steffensen iterative process. In the work [ 8 ] it was shown that the Steffensen iterative operator provides us with the following two equivalent iterative processes:

(11)

x_{n}=x_{n-1}-\left[x_{n-1},Q\left(x_{n-1}\right);P\right]^{-1}P\left(x_{n-1}\right)

And

(12)

x_{n}=Q\left(x_{n-1}\right)-\left[x_{n-1},Q\left(x_{n-1}\right);P\right]^{-1}P% \left(Q\left(x_{n-1}\right)\right).

Regarding this process, there is the following theorem:

Theorem 5 .

Either $x_{0}\in X$ an item for which the following conditions are met:

a) $\left\|Q\left(x_{0}\right)-x_{0}\right\|\leq\delta_{0}<+\infty.$

b) Real and non-negative numbers $K, B$ And $\rho$ satisfy inequality

\varepsilon_{0}=\left(KB^{2}\rho\right)^{\frac{1}{k-1}}\left\|P\left(x_{0}% \right)\right\|<1\ \text{o\`{u}\ }k\geq 2\

is a natural number.

c) Either $M$ a real, non-negative number.

We will write $\mu=\max\{\delta_{0}+Mr,r\}$ Or

r=B\Big{(}\left\|P\left(x_{0}\right)\right\|+\left(KB^{2}\rho\right)^{\frac{1}% {k-1}}\tfrac{\varepsilon_{0}^{k}}{1-\varepsilon_{0}^{k}}\Big{)}

And $S=\{x\in X;\ \left\|x-x_{0}\right\|\leq\mu\}.$ It is assumed that for all $x\in S$ the divided difference $\left[x,Q\left(x\right);P\right]$ admits an inverse bounded by the number $B,$ that's to say $\big{\|}\left[x,Q\left(x\right);P\right]^{-1}\big{\|}$ $\leq B<+\infty.$

d) For all $x,y,z\in S$ the divided differences $\left[x,y;Q\right],\ \left[x,y;P\right]$ And $\left[x,y;z;P\right]$ are symmetric with respect to the given nodes and we have the inequalities:

	$\displaystyle\left\\|\left[x,y;Q\right]\right\\|$	$\displaystyle\leq M,\;\;$
	$\displaystyle\left\\|\left[x,y,z;P\right]\right\\|$	$\displaystyle\leq K.$

e) The iterative operator $Q$ has the order $k-1$ in the sphere $S$ that is to say we have the inequality $\left\|P\left(Q\left(x\right)\right)\right\|\leq\rho\left\|P\left(x\right)% \right\|^{k-1}$ and the operator $P$ is continuous in $S .$

If conditions a)–e) are met then we have the following properties:

a') The elements of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ provided by the method ( 11 ) belong to the sphere $S$ .

b') The elements of the sequence $\left(Q\left(x_{n}\right)\right)_{n=0}^{\infty}$ belong to the sphere $S .$

c) Equation ( 1 ) has at least one solution $\bar{x}\in S.$

d) The continuation $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent and $\lim\limits_{n\rightarrow\infty}x_{n}=\bar{x}.$

c') The order of convergence of the process ( 11 ) is $k .$

Demonstration.

If we write $h=KB^{2}\rho$ and we take into account the fact that we assumed that the divided difference $\left[x,y;P\right]$ is symmetrical with respect to the nodes, we have

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

To establish the previous inequality we took into account the fact that $x_{1}\in S,$ what results from inequality

\left\|x_{1}-x_{0}\right\|\leq B\left\|P\left(x_{0}\right)\right\|<r\leq\mu.

In the same way we have

\left\|Q\left(x_{1}\right)-x_{0}\right\|\leq B\left\|P\left(x_{0}\right)\right% \|M+\delta_{0}<Mr+\delta_{0}\leq\mu

that's to say $Q\left(x_{1}\right)\in S.$

We will now assume that we have constructed using the method ( 11 ) the elements $x_{1},x_{2},\ldots,x_{n-1}\in S$ And $Q\left(x_{1}\right),\ldots,Q\left(x_{n-1}\right)\in S.$ We will show that $x_{n}\in S$ And $Q\left(x_{n}\right)\in S.$ In fact, we easily notice that for $i=1,2,\ldots,n-1$ on a

(13)

\left\|P\left(x_{i}\right)\right\|\leq h\left\|P\left(x_{i-1}\right)\right\|^{% k},\ \;\;i=1,2,\ldots,n-1.

Multiplying the last inequality by $h^{\frac{1}{k-1}}$ and writing $\varepsilon_{i}=h^{\frac{1}{k-1}}\left\|P\left(x_{i}\right)\right\|$ we obtain the inequalities:

\varepsilon_{i}\leq\varepsilon_{i-1}^{k},\ \;\;i=1,2,\ldots,n-1

from which it results

\varepsilon_{i}\leq\varepsilon_{0}^{k^{i}},\ \;\;i=1,2,\ldots,n-1.

Taking into account these inequalities and ( 13 ) we deduce:

\left\|x_{n}-x_{n-1}\right\|\leq B\left\|P\left(x_{n-1}\right)\right\|\leq Bh^% {\frac{1}{1-k}}\varepsilon_{0}^{n-1}

from which results the inequality

	$\displaystyle\left\\|x_{n}-x_{0}\right\\|$	$\displaystyle\leq B\left\\|P\left(x_{0}\right)\right\\|+Bh^{\frac{1}{1-k}}\left(% \varepsilon_{0}^{k}+\varepsilon_{0}^{k^{2}}+\cdots+\varepsilon_{0}^{k^{n-1}}\right)$
		$\displaystyle\leq B\left(P\left(x_{0}\right)+h^{\frac{1}{1-k}}\tfrac{% \varepsilon_{0}^{k}}{1-\varepsilon_{0}^{k}}\right)$

that's to say

\left\|x_{n}-x_{0}\right\|\leq\mu

and therefore $x_{n}\in S.$

This immediately results in the inequality:

\left\|Q\left(x_{n}\right)-x_{0}\right\|\leq\delta_{0}+Mr\leq\mu

that's to say $Q\left(x_{n}\right)\in S.$

Hence conclusions a') and b') are demonstrated.

We will now show that the following $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent. To do this we will show that this sequence is a fundamental sequence. We have

(14)

\left\|x_{n+p}-x_{n}\right\|\leq\tfrac{Bh^{\frac{1}{1-k}}\varepsilon_{0}^{k^{n% }}}{1-\varepsilon_{0}^{k^{n}}}

which shows us that the sequel $\left(x_{n}\right)_{n=0}^{\infty}$ is a fundamental sequence and like space $X$ is assumed to be complete, it follows that this sequence is convergent.

Either:

\bar{x}=\lim_{n\rightarrow\infty}x_{n}.

Passing to the limit in inequality ( 14 ) for $p\rightarrow\infty$ on a

(15)

\left\|\bar{x}-x_{n}\right\|\leq\tfrac{Bh^{\frac{1}{1-k}}\varepsilon_{0}^{k^{n% }}}{1-\varepsilon_{0}^{k^{n}}}.

This inequality also gives us an evaluation of the error after $n$ no iteration. Since $k\geq 2$ we notice that the error quickly tends towards zero when $m$ grows.

Passing to the limit in the inequality

\left\|P\left(x_{n}\right)\right\|\leq h^{\frac{1}{1-k}}\varepsilon_{0}^{k^{n}}

and taking into account the continuity of $P$ on a $\lim\left\|P\left(x_{n}\right)\right\|=0$ on $P\left(\bar{x}\right)=\theta$ which demonstrates the conclusion c'). Obviously, the inequality ( 15 ) for $n=0$ shows us that $\bar{x}\in S.$

Conclusion e') follows from the fact that inequality ( 15 ) holds for all $n$ and hypothesis b).

We will now present a numerical application of the results presented in this note. ∎

Application.

We consider the integral equation of the Fredholm type

(1^′)

P\left(\varphi\left(x\right)\right)=\varphi\left(x\right)-0.1\int\nolimits_{0}% ^{1}e^{x}\varphi^{2}\left(y\right)dy=0.

This equation admits, in addition to the solution $\varphi\left(x\right)=0,$ another solution $\varphi\left(x\right)=\frac{2e^{x}}{0.1\left(e^{2}-1\right)}.$

To solve the equation ( 1 ^′ ) we will first apply the simple iteration method. So let $\varphi_{0}=u_{0}e^{x}$ Or $u_{0}$ is a fixed real number, an initial solution, and

(2^′)

\varphi_{n}\left(x\right)=0.1\int\nolimits_{0}^{1}e^{x}\varphi_{n-1}^{2}\left(% y\right)dy.

From the preceding process it results that $\varphi_{n}\left(x\right)$ has the form:

\varphi_{n}\left(x\right)=u_{n}e^{x},\qquad n=1,2,\ldots

(3^′)

u_{n}=\tfrac{0.1\left(e^{2}-1\right)}{2}u_{n-1}^{2},\qquad n=1,2,\ldots

If the iterative process ( 3 ^′ ) converges, then in the limit we obviously obtain one of the solutions of the equation

(4^′)

u=\tfrac{0.1\left(e^{2}-1\right)}{2}u^{2}.

The equation ( 4 ^′ ) admits the solutions

(5^′)

u=0

And

(6^′)

u=\tfrac{2}{0.1\left(e^{2}-1\right)}.

Following the terminology adopted by AM Ostrowski [ 5 ] , we note that $u=0$ is a point of “contraction” for the equation ( 4 ^′ ) since if we choose $\left|u_{0}\right|<\frac{1}{0.1\left(e^{2}-1\right)},$ then the iterative process ( 3 ^′ ) converges and we have $\lim\limits_{n\rightarrow\infty}u_{n}=0.$ On the other hand the point $u=\frac{2}{0.1\left(e^{2}-1\right)}$ is a “repulsive” point for the equation ( 4 ^′ ) since the function

f\left(u\right)=\tfrac{0.1(e^{2}-1)}{2}u^{2}

satisfies the condition:

f^{\prime}\left(u\right)|_{k=\frac{2}{0.1(e^{2}-1)}}=2\gg 1

Applying the results of Lemma 4.2 [ 5 , p. 36] we can deduce the conclusion that the process ( 3 ^′ ) will never converge to the solution ( 6 ^′ ) whatever the choice of the initial value.

Graphically, this fact is presented as follows (Fig. 1).

If we represent graphically in the coordinate system $\left(u,v\right)$ the curves $v=u$ And $v=\frac{0.1\left(e^{2}-1\right)}{2}u^{2}$ then the solutions of the equation ( 4 ^′ ) are nothing other than the abscissas of the points of intersection of the two curves.

In the figure above we notice that by choosing for example $0\leq u_{0}<\frac{2}{0.1\left(e^{2}-1\right)}$ there is a plow $\lim\limits_{n\rightarrow\infty}=0,$ that is to say that using the method ( 3 ^′ ) we obtain $\varphi\left(x\right)=0.$ And $u_{0}>\frac{2}{0.1\left(e^{2}-1\right)}$ SO $\lim u_{n}=\infty,$ that is, the process ( 2 ^′ ) is divergent. Taking for the number $and$ the approximate value $e\approx 2,71288183$ and by using the method ( 3 ^′ ) we obtain the results included in table 1 ²²2 In this table we have introduced only the values which are sufficient to deduce the necessary conclusions on the convergence of the corresponding iteration sequences.

Table 1

$in$	$u_{0}=3$	$u_{0}=4.9$	$u_{0}=3.145$
$1$	$0.28025655\cdot 10$	$0.763485296\cdot 10$	$0.314521122\cdot 10$
$2$	$0.249758376\cdot 10$	$0.185357376\cdot 10^{2}$	$0.314563373\cdot 10$
$3$	$0.198357507\cdot 10$	$0.109251715\cdot 10^{3}$	$0.31464789\cdot 10$
$4$	$0.125113069\cdot 10$	$0.379546552\cdot 10^{4}$	$0.31484816994\cdot 10$
$5$	$0.497760154\cdot 10^{0}$	$0.458077142\cdot 10^{7}$	$0.315155474\cdot 10$
$6$	$0.78785949\cdot 10^{-1}$	$0.667245666\cdot 10^{13}$	$0.315833527\cdot 10$
$7$	$0.1973813\cdot 10^{-2}$	.	$0.317194011\cdot 10$
$8$	$0.1238\cdot 10^{-5}$	.	$0.319932586\cdot 10$
$9$	$0$	.	$0.325480874\cdot 10$
$10$			.
$11$			.
$12$			.
$13$
$14$
$15$
$16$
$17$
$18$			$0.139250090\cdot 10^{9}$
$19$			$0.616594277\cdot 10^{16}$
$20$			$0.120894766\cdot 10^{32}$
$in$	$0$	$+\infty$	$+\infty$

Obviously, the results of the calculations show us that if we take $u_{0}=3$ then the sequence of successive approximations has as limit the value $u=0.$ If we take for example $u_{0}=4.9$ SO $\lim\limits_{n\rightarrow\infty}u_{n}=+\infty.$

To better illustrate the validity of the conclusions, we have taken for $u_{0}$ the value $u_{0}=3.145$ which differs very little from the exact solution, but which is larger than it. In this case, by carrying out the sequence of successive iterations we notice that, even if after the first four iterations the third decimal digit of the result is preserved, which could give us the illusion of a possibility of convergence of the process, we will be convinced however, by continuing the process, that even in this case we have $\lim\limits_{n\rightarrow\infty}u_{n}=+\infty.$

It has been shown here, by several means, that the solution $\varphi\left(x\right)=\frac{2e^{x}}{0.1\left(e^{2}-1\right)}$ of the equation ( 1 ^′ ) can only be obtained by simple iteration. Starting from the same initial approximations, we will now solve the equation ( 1 ^′ ) by applying the Steffensen method. For this, we will note that the equation ( 1 ^′ ) can be put in the form

\varphi\left(x\right)=\psi\left(\varphi\left(x\right)\right)

\psi\left(\varphi\right)=0.1\int\nolimits_{0}^{1}e^{x}\varphi^{2}\left(y\right% )dy

Taking, as in the previous procedure, an initial solution of the form $\varphi_{0}=u_{0}e^{x}$ we find $\psi\left(\varphi_{0}\right)=\frac{0.1\left(e^{2}-1\right)}{2}u_{0}^{2}e^{x}$ and a simple calculation shows us that Steffensen's method gives us for the second approximation $\varphi_{1}\left(x\right)$ the following expression

\varphi_{1}\left(x\right)=\left\{\tfrac{u_{0}-\frac{0.1\left(e^{2}-1\right)}{2% }u_{0}^{2}}{\frac{0.1\left(e^{2}-1\right)}{2}\left[u_{0}+\frac{0.1\left(e^{2}-% 1\right)}{2}u_{0}^{2}\right]-1}+u_{0}\right\}e^{x}.

We deduce that in general, Steffensen's method leads us to the following sequence of approximations

\varphi_{n}\left(x\right)=u_{n}^{\ast}e^{x}

(7^′)

u_{n}^{\ast}=u_{n-1}^{\ast}+\frac{u_{n-1}^{\ast}-\frac{0.1\left(e^{2}-1\right)% }{2}u_{n-1}^{\ast 2}}{\frac{0.1\left(e^{2}-1\right)}{2}\left[u_{n-1}^{\ast}+% \frac{0.1\left(e^{2}-1\right)}{2}u_{n-1}^{\ast 2}\right]-1}.

Taking for $u_{0}$ the values $u_{0}=3$ And $u_{0}=4.9$ we obtain the results included in Table 2.

Table 2

$u_{i}$	$u_{0}=3$	$u_{0}=4.9$
$1$	$0.316020072\cdot 10$	$0.398352495\cdot 10$
$2$	$0.314491069\cdot 10$	$0.341520886\cdot 10$
$3$	$0.314478856\cdot 10$	$0.318278973\cdot 10$
$4$	$0.314478877\cdot 10$	$0.314561525\cdot 10$
$5$	$0.314478877\cdot 10$	$0.314478771\cdot 10$
$6$	$-$	$0.14478877\cdot 10$
$in$	$\approx\frac{2}{0,1\left(e^{2}-1\right)}$	$\approx\frac{2}{0,1\left(e^{2}-1\right)}$

Analyzing this table, it follows that if we choose the initial approximation appropriately $\varphi_{0},$ using the Steffensen method we obtain the solution $\varphi\left(x\right)=\frac{2}{0.1\left(e^{2}-1\right)}e^{x}.$

If in the process ( 7 ^′ ) we start from an initial approximation $u_{0},$ close enough to zero, then we will obtain the second solution $\varphi\left(x\right)=0.$ The example studied previously illustrates the validity of the theoretical results obtained in this note in the following senses:

- The $and$ There are cases where the simple iteration method does not converge to the desired solution, regardless of the choice of the initial approximation. But by applying the Steffensen method and choosing the initial approximation in a suitable way, the desired solution will be obtained. (This fact is valid for any method that has an order of convergence greater than or equal to 2).

-Steffensen's method converges quickly.

Note, for example, that starting from the initial approximation $u_{0}=4.9$ the simple iteration method is divergent, while the Steffensen method leads us to the desired result in 6 steps.

For $\varphi_{0}=3e^{x}$ we will try to numerically illustrate the speed of convergence of the sequence $\left\{\left\|P^{\ast}\left(\varphi_{n}^{\ast}\left(x\right)\right)\right\|\right\}$ towards zero.

Table 3

$N r .$	$\varphi_{i}^{\ast}$	$\left\\|P^{\ast}\left(\varphi_{i}^{\ast}\right)\right\\|$	$\left\\|P^{\ast}\left(\varphi_{i}\right)^{\ast}\right\\|^{2}$
$0$	$3\cdot e^{x}$	$0.37471026334$	$0.14040778007$
$1$	$3.16020072\cdot e^{x}$	$0.04201570293$	$0.0017653192$
$2$	$3.14491069\cdot e^{x}$	$0.0003320011$	$0.000000109416$
$3$	$3.14478856\cdot e^{x}$	$0.0000000697$	$0.0000000000$
$4$	$3.14478877\cdot e^{x}$	$0.0000000000$	$0.0000000000$

In this table $\varphi_{i}^{\ast}$ And $P^{\ast}$ are the approximate (numerical) values of the functions $\varphi_{i}$ and the operator $P .$ We deduce that by taking $\rho=0.4$ so, for everything $i$ the inequalities are satisfied

\left\|P^{\ast}\left(\varphi_{i+1}^{\ast}\right)\right\|\leq\rho\left\|P^{\ast% }\left(\varphi_{i}^{\ast}\right)\right\|^{2},\ \;\;i=0,1,\ldots,

These inequalities characterize the order of convergence of Steffensen's method. More precisely, they show us that it is equal to two.

Bibliography

[1] Kantorovich, LV, Functional analysis $i$ mathematical pricladnaia . UMN, 28, 3 (1948).
[2] Kantorovich, L. V., The Newton Method . Trudy mad. i-ta im. Stacklover. 28 , p. 104–144 (1949).
[3] Jankó, B, and Goldner, G., On the solution of operational equations with the method of Cebişev . (II), Studia Univ. Babeş-Bolyai Cluj 2 , pp. 55–58 (1968).
[4] Ghinea, Monique, On the resolution of operational equations in Banach spaces , French Journal of Information Processing 8 , pp. 3–22 (1965).
[5] Ostrowski, AM, Reşenie uravnenii $i$ sistem uravnenii . Izd. inost. lit., Moscow, (1963).
[6] Păvăloiu, I., On the solution of operational equations by higher-order iteration methods . Proceedings of the colloquium on the theory of function approximation (abstract), Cluj, September 15-20, 1967.
[7] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., On the Steffensen method for solving nonlinear operational equations . Romanian Journal of Pure and Applied Mathematics, XIII, (1968) 6, pp. 857–861.
[8] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., On iterative operators , Mathematical Studies and Research (in print); appeared as: 23 (1971) no. 10, pp. 1567–1574.
[9] ^†^†margin: clickable $\rightarrow$ Păvăloiu, I., Interpolation in normed linear spaces and applications. Mathematica, Cluj, vol. 12 (35), 1, 1970, pp. 149–158.
[10] Stein, M. L., Sufficient conditions for the Banach spaces. Proc. Amer. Math. Soc. 3, pp. 858–863 (1952).
[11] Traub, J, F., Iterative methods for the solution of equations. Prentice-Hall. Inc. Englewood Cliffs N. J. 1964.

Received, 8.VII.1970

	$\displaystyle\left\\|P\left(x_{1}\right)\right\\|\leq$	$\displaystyle\left\\|P\left(x_{1}\right)-\left(P\left(x_{0}\right)+\tfrac{P^{% \prime}\left(x_{0}\right)}{1!}\varphi\left(x_{0}\right)+\cdots+\tfrac{P^{\left% (k-1\right)}\left(x_{0}\right)}{\left(k-1\right)!}\varphi^{k-1}\left(x_{0}% \right)\right)\right\\|$
		$\displaystyle+\left\\|P\left(x_{0}\right)+\tfrac{P^{\prime}\left(x_{0}\right)}{% 1!}\varphi\left(x_{0}\right)+\cdots+\tfrac{P^{\left(k-1\right)}\left(x_{0}% \right)}{\left(k-1\right)!}\varphi^{k-1}\left(x_{0}\right)\right\\|$
	$\displaystyle\leq$	$\displaystyle\tfrac{M}{k!}\left\\|x_{1}-x_{0}\right\\|^{k}+\alpha\left\\|P\left(x% _{0}\right)\right\\|^{k}\leq\left(\alpha+\tfrac{\beta^{k}M}{k!}\right)\left\\|P% \left(x_{0}\right)\right\\|^{k}$

On the iterative methods with high convergence orders

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 ISBN

Online ISBN

References

Paper (preprint) in HTML form

On the iterative methods with high convergence orders

Definition 1 .

Definition 2 .

Lemme 1.

Demonstration.

Theorem 2 .

Demonstration.

Noticed .

Theorem 3 .

Theorem 4 .

Theorem 5 .

Demonstration.

Bibliography

Related Posts