"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

Preprint Nr.1, 1983, pp. 175-182

On Optimal Iterative Methods

by
Ion Pavaloiu and Ioan Serb

In this work we study iterative methods for solving the equation:

(1)

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

Or $\varphi:I\rightarrow X$ is a given application and $\left(X,\rho\right)$ is a complete metric space.

A l’application $\varphi$ we will attach an application $F:X^{k}\rightarrow X$ , which has the following property:

(2)

F\left(x,x,\ldots,x\right)=\varphi\left(x\right),\ \ \ \ x\in X.

To solve equation ( 1 ) we consider the multi-step iterative method, of the form:

(3)

x_{n+1}=F\left(x_{n},x_{n-1},\ldots,x_{n-k+1}\right),\ n=k-1,k,k+1,\ldots

And $i_{0},i_{1},\ldots,i_{k-1}$ is a permutation of numbers $0,1,\ldots,\ k-1$ , SO $i_{0}+n-k+1,\ i_{1}+n-k+1,\ldots,i_{k-1}+n-k+1$ will be a permutation that matches the numbers $n-k+1,\ n-k+2,\ldots,n$ .

For such a permutation we obtain a new multi-step iterative method:

(4)

x_{n+1}=F\left(x_{i_{0}+n-k+1},x_{i_{1}+n-k+1},\ldots,x_{i_{k-1}+n-k+1}\right),

Or $n=k-1,\ k,\ldots$

In this way, from the given application $F$ , we obtain $k!$ iterative methods, which are generally distinct.

If under certain conditions imposed on the application $F$ , all these $k!$ iterative methods converge to a solution of equation ( 1 ), the problem arises of choosing the method for which the best error bound is obtained.

In the following we will assume that $F$ verifies the following relationship:

(5)

\displaystyle\rho\left(F\left(u_{1},u_{2},\ldots,u_{k}\right),F\left(v_{1},v_{% 2},\ldots,v_{k}\right)\right)\leq\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{% i}\right)^{\beta}\Big{)}^{\frac{1}{\beta}},

whatever the elements $u_{1},u_{2},\ldots,u_{k},\ v_{1},v_{2},\ldots,v_{k}\in X$ , Or $a_{i}\geq 0$ And $\beta>0$ are given and $0<\sum_{i=1}^{k}a_{i}<1.$

We note that if $F$ verifies conditions ( 2 ) and ( 5 ) then $\varphi$ checks the condition:

	$\displaystyle\rho\big{(}\varphi\left(x\right),\varphi\left(y\right)\big{)}$	$\displaystyle=\rho\big{(}F\left(x,x,\ldots,x\right),F\left(y,y,\ldots,y\right)% \big{)}$
		$\displaystyle\leq\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(x,y\right)^{\beta}\Big{)}% ^{\frac{1}{\beta}}=\Big{(}\sum_{i=1}^{k}a_{i}\Big{)}^{\frac{1}{\beta}}\rho% \left(x,y\right),$

and the fact that $0<\sum_{i=1}^{k}a_{i}<1$ , it follows that $\varphi$ is a contraction, that is, equation ( 1 ) has only one solution.

On the other hand, if we designate by $\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)$ all functions $F$ verifying conditions ( 2 ) and ( 5 ), then if $\beta<\beta^{\prime}$ it results $\mathcal{F}_{\beta}\left(a_{1},a_{2},\mathcal{\ldots},a_{k}\right)\subset% \mathcal{F}_{\beta^{\prime}}\left(a_{1},a_{2},\ldots a_{k}\right)$ .

For $\beta<\beta^{\prime}$ we deduce from Hölder's inequality:

	$\displaystyle\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta}% \Big{)}^{\frac{1}{\beta}}$	$\displaystyle=\Big{[}\sum_{i=1}^{k}\left(a_{i}^{\frac{\beta}{\beta^{\prime}}}% \rho\left(u_{i},v_{i}\right)^{\beta}\right)a_{i}^{1-\frac{\beta}{\beta^{\prime% }}}\Big{]}^{\frac{1}{\beta}}$
		$\displaystyle\leq\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta% ^{\prime}}\Big{)}^{\frac{1}{\beta^{\prime}}}\Big{[}\sum_{i=1}^{k}\Big{(}a_{i}^% {1-\frac{\beta}{\beta^{\prime}}}\Big{)}^{\frac{\beta^{\prime}}{\beta^{\prime}-% \beta}}\Big{]}^{\frac{\beta^{\prime}-\beta}{\beta\beta^{\prime}}}$
		$\displaystyle=\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta^{% \prime}}\Big{)}^{\frac{1}{\beta^{\prime}}}\Big{(}\sum_{i=1}^{k}a_{i}\Big{)}^{% \frac{\beta^{\prime}-\beta}{\beta\beta^{\prime}}}$
		$\displaystyle<\Big{(}\sum_{i=1}^{k}a_{i}\rho\left(u_{i},v_{i}\right)^{\beta^{% \prime}}\Big{)}^{\frac{1}{\beta^{\prime}}}$

SO $\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)\subset\mathcal{F}_{% \beta^{\prime}}\left(a_{1},a_{2},\ldots,a_{k}\right)$ .

Let's consider the numbers $\alpha_{i}\in\mathbb{R}$ , $i=1,2,\ldots,k$ , which verify the relations:

(6)

\alpha_{1}\geq\alpha_{2}\geq\ldots\geq\alpha_{k-1}\geq\alpha_{k}\geq 0,

And

(6^′)

0<\sum_{i=1}^{k}\alpha_{i}<1.

We now consider the equations

(7)

P\left(u\right)=u^{k}-\alpha_{1}u^{k-1}-\ldots-\alpha_{k-1}u-\alpha_{k}=0,

(8)

Q\left(u\right)=u^{k}-\alpha_{k}u^{k-1}-\ldots-\alpha_{2}u-\alpha_{1}=0,

And

(9)

R\left(u\right)=u^{k}-\alpha_{i_{1}}u^{k-1}-\ldots-\alpha_{i_{k-1}}u-\alpha_{i% _{k}}=0,

Or $i_{1},i_{2},\ldots,i_{k}$ is any permutation of the numbers $1,2,\ldots,k$ .

LEMME.

And $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ verify the conditions ( 6 ) and ( 6 ^′ ) then each equation of the form ( 9 ) has a single positive root. If we denote by a the positive root of equation ( 7 ) and by $b$ the positive root of equation ( 8 ), then the positive root $c$ of equation ( 9 ) verifies the following inequalities:

(10)

0<a\leq c\leq b<1.

Demonstration.

Either $i_{1},i_{2},\ldots,i_{k}$ a permutation of numbers $1,2,\ldots,k$ and either $s$ the biggest clue for which $\alpha_{i_{s}}\neq 0$ .

We obviously have $\alpha_{i_{s+1}}=\alpha_{i_{s+2}}=\cdots=\alpha_{i_{k}}=0$ And $\alpha_{i_{s}}\neq 0$ .

Consider the function $\psi\left(u\right)=R\left(u\right)/u^{k-s}$ . SO $\psi\left(0\right)=-\alpha_{i_{s}}<0$ And $\psi\left(1\right)=R\left(1\right)=1-\alpha_{i_{1}}-\ldots-\alpha_{i_{k-1}}-% \alpha_{i_{k}}=1-\alpha_{1}-\ldots-\alpha_{k}>0$ .

SO $\psi\left(u\right)$ has a positive root in the interval $\left(0,1\right)$ . It follows that $R\left(u\right)=u^{k-s}\psi\left(u\right)$ has a root in the interval $\left(0,1\right)$ .

The uniqueness of this root follows immediately by considering the equation $f\left(v\right)=-v^{k}R\left(1/v\right)=0$ , for which $f^{\prime}\left(v\right)>0$ and $v>0$ And $f\left(0\right)=-1$ .

To prove inequality ( 10 ) it suffices to show that $R\left(a\right)\leq R\left(c\right)=0$ And $R\left(b\right)\geq R\left(c\right)=0$ . In fact, we have:

	$\displaystyle R\left(a\right)=$	$\displaystyle a^{k}-\alpha_{i_{1}}a^{k-1}-\ldots-\alpha_{i_{k-1}}a-\alpha_{i_{% k}}$
	$\displaystyle=$	$\displaystyle\left(\alpha_{1}-\alpha_{i_{1}}\right)a^{k-1}+\left(\alpha_{2}-% \alpha_{i_{2}}\right)a^{k-2}+\ldots+\alpha_{k}-\alpha_{i_{k}}$
	$\displaystyle=$	$\displaystyle\left(a-1\right)\left(\alpha_{1}-\alpha_{i_{1}}\right)a^{k-2}+% \left(\alpha_{1}+\alpha_{2}-\alpha_{i_{1}}-\alpha_{i_{2}}\right)a^{k-3}+\ldots+$
		$\displaystyle+\left(\alpha_{1}+\alpha_{2}+\ldots+\alpha_{k-2}-\alpha_{i_{1}}-% \alpha_{i_{2}}-\ldots-\alpha_{i_{k-2}}\right)a+$
		$\displaystyle+\left(\alpha_{1}+\alpha_{2}+\ldots+\alpha_{k-1}-\alpha_{i_{1}}-% \alpha_{i_{2}}-\ldots-\alpha_{i_{k-1}}\right)\leq 0,$

because $0<a<1$ and from ( 6 ) it follows that

\alpha_{1}+\alpha_{2}+\ldots+\alpha_{s}-\alpha_{i_{1}}-\alpha_{i_{2}}-\ldots-% \alpha_{i_{s}}\geq 0;

for each $s=1,2,\ldots,k-1$ .

Similarly, we show that $R\left(b\right)\geq 0,\ Q.E.D.$

Now we sort the coefficients $a_{i}$ from ( 5 ) in descending order, that is:

(11)

a_{i_{1}}\geq a_{i_{2}}\geq\ldots\geq a_{i_{k}}\geq 0,

and we write

(11^′)

\alpha_{s}=a_{i_{s}},\ s=1,2,\ldots,k.

We consider the application $G:X^{k}\rightarrow X$ , given by the relation

(12)

G\left(u_{1},u_{2},\ldots,u_{k}\right)=F\left(u_{i_{1}},u_{i_{2}},\ldots,u_{i_% {k}}\right),

Or $i_{1},i_{2},\ldots,i_{k}$ is the permutation of numbers $1,2,\ldots,k$ which corresponds to the relation ( 11 ). We then obtain from ( 5 ), for $G$ , the condition

(13)

\displaystyle\rho\big{(}G\left(u_{1},u_{2},\ldots,u_{k}\right),G\left(v_{1},v_% {2},\ldots,v_{k}\right)\big{)}\leq\left(\sum_{i=1}^{k}\alpha_{i}\rho\left(u_{i% },v_{i}\right)^{\beta}\right)^{\frac{1}{\beta}},

whatever the elements $u_{1},u_{2},\ldots,u_{k},\ v_{1},v_{2},\ldots,v_{k}\in X,$ Or

\alpha_{1}\geq\alpha_{2}\geq\ldots\geq\alpha_{k}\geq 0,\ \beta>0.......0<\sum_% {i=1}^{k}\alpha_{i}<1.

To solve equation ( 1 ) we consider the following iterative method:

(14)

x_{n+1}=G\left(x_{n},x_{n-1},\ldots,x_{n-k+1}\right),\ n=k-1,k\ldots,

Or $x_{0},x_{1},\ldots,x_{k-1}\in X$ .

If we write $q_{i}=\rho\left(x_{i},x_{i+1}\right),\ i=0,1,\ldots$ , then from ( 13 ) and ( 14 ) we obtain

(15)

q_{i}=\left(\sum_{s=1}^{k}\alpha_{s}q_{i-s}^{\beta}\right)^{\frac{1}{\beta}},% \ i=k,k+1,\ldots\ .

If in equation ( 7 ) $\alpha_{1},\alpha_{2},\ldots,\alpha_{k}$ are given by ( 11 ^′ ) and if $a$ is the positive root of equation ( 7 ), then $a^{\frac{1}{\beta}}\in\left(0,1\right)$ .

Either $C$ a positive constant such that:

q_{s}\leq Ca^{s/\beta}\text{ pour}\ s=0,1,\ldots,k-1.

From ( 15 ) we obtain:

	$\displaystyle q_{i}$	$\displaystyle\leq\left(\sum_{s=1}^{k}\alpha_{s}q_{i-s}^{\beta}\right)^{\frac{1% }{\beta}}\leq\left(C\ \sum_{s=1}^{k}\alpha_{s}a^{i-s}\right)^{\frac{i}{\beta}}$
		$\displaystyle=C\ a^{\left(i-k\right)/\beta}\left(\sum_{s=1}^{k}\alpha_{s}a^{k-% s}\right)^{\frac{1}{\beta}}=C\ a^{\left(i-k\right)/\beta}a^{k/\beta}=C\ a^{i/% \beta},$

$i=k,k+1,\ldots,$ . Since $a^{1/\beta}\in\left(0,1\right)$ it follows that the following $\left(x_{n}\right)_{n=0}^{\infty}$ is fundamental. Let us designate by $\bar{x}$ its limit. It is obvious that $\bar{x}$ is the unique solution of equation ( 1 ) and

(16)

\rho\left(\bar{x},x_{n}\right)\leq\tfrac{C\ a^{n/\beta}}{1-a^{1/\beta}}.

∎

So, using the lemma we obtain the following theorem:

THEOREM .

Let's suppose that $F\in\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)$ and that we give the $k!$ iterative methods of the form ( 4 ), attached to $F$ .

The iterative method for which the best error bound is obtained is that given by ( 14 ), with $G$ defined by ( 12 ) and which corresponds to the decreasing order of the sequence of coefficients $a_{i},\ i=1,2,\ldots,k,$ from ( 5 ).

Remarks .

1) Because, from the $F\in\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)$ it follows that $\varphi$ is a contraction, with the Lipschitz constant $\left(\sum_{i=1}^{k}a_{i}\right)^{1/\beta}$ , it is clear that the iterative method

(17)

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

converges to the solution $\bar{x}$ from equation ( 1 ). Furthermore, we have

(18)

\rho\left(\bar{x},x_{n}\right)\leq C_{1}\frac{\left(\sum\limits_{i=1}^{k}a_{i}% \right)^{n/\beta}}{1-\left(\sum\limits_{i=1}^{k}a_{i}\right)^{1/\beta}}.

We will demonstrate that $\sum_{i=1}^{k}a_{i}\leq a$ , where a is the solution to equation ( 7 ), with $\alpha_{s},\ s=1,2,\ldots,k$ given by the formula ( 11 ^′ ).

On a:

		$\displaystyle P\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}=$
		$\displaystyle=\!\!\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}\!\!-% \!\alpha_{1}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}\!\!-\!% \alpha_{2}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-2}\!\!-\ldots-% \!\alpha_{k-1}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}-\alpha_{k}$
		$\displaystyle\leq\!\!\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}\!% \!-\!\alpha_{i}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}\!\!-\!% \alpha_{2}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}\!\!-\!% \ldots\!-\!\alpha_{k-1}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1% }\!\!-\!\alpha_{k}\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k-1}$
		$\displaystyle=\!\Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}\!\!-\!% \Big{(}\textstyle\sum\limits_{i=1}^{k}a_{i}\Big{)}^{k}=0,$

from which it follows that $\sum_{i=1}^{k}a_{i}\leq a$ .

Be it now $F\in\mathcal{F}_{\beta}\left(a_{1},a_{2},\ldots,a_{k}\right)\$ And $\ \varphi\left(x\right)=F\left(x,x,\ldots,x\right)$ . Formulas ( 16 ) and ( 18 ) valid for any metric and for each pair $\left(F,\varphi\right),$ with the above properties, show us that for the iterative method ( 17 ) we obtain a better error delimitation than in the case of other methods of the form ( 4 ). This does not mean that for each choice of the initial points and each application $F,$ method ( 17 ) converges faster than all iterative methods of the form ( 4 ).

For example, $\ X=\mathbb{R}$ , $\rho=\left|\cdot\right|,\ \varphi\left(x\right)=\frac{1}{4}\sin x,$ $F\left(x,y\right)=\frac{1}{2}\sin\frac{x}{2}\cos\frac{y}{2}$ . On a

\big{|}F\left(x_{1},y_{1}\right)-F\left(x_{2},y_{2}\right)\big{|}\leq\tfrac{1}% {4}\left|x_{1}-x_{2}\right|+\tfrac{1}{4}\left|y_{1}-y_{2}\right|,

for each $x_{1},x_{2},y_{1},y_{2}\in\mathbb{R}$ ; $F\in\mathcal{F}_{1}\left(\tfrac{1}{4},\tfrac{1}{4}\right)\$ And $\ F\left(x,x\right)=\varphi\left(x\right)$ .

We consider the following iterative methods:

(19)

x_{n+1}=\tfrac{1}{4}\sin x_{n},\ n=0,1,\ldots,\ \ x_{0}=\tfrac{\pi}{2},

(20)

x_{n+2}=\tfrac{1}{2}\sin\tfrac{x_{n+1}}{2}\cos\tfrac{x_{n}}{2},\ n=0,1,\ldots,% \ x_{0}=\tfrac{\pi}{2},\ x_{1}=0,

(21)

x_{n+2}=\tfrac{1}{2}\cos\tfrac{x_{n+1}}{2}\sin\tfrac{x_{n}}{2},\ n=0,1,\ldots,% \ \ x_{0}=\tfrac{\pi}{2},\ x_{1}=0.

In this case the sequence ( 20 ) converges faster than the sequence ( 19 ) or the sequence ( 21 ).

2) There exist iterative methods of the form ( 4 ) respectively ( 17 ), for which the bounds ( 16 ) respectively ( 18 ) cannot improve, i.e.:

\overline{\lim_{n\rightarrow\infty}}\rho\left(\bar{x},x_{n}\right)^{1/n}=a^{1/% \beta},

respectively

\overline{\lim_{n\rightarrow\infty}}\rho\left(\bar{x},x_{n}\right)^{1/n}=\left% (\sum_{i=1}^{k}a_{i}\right)^{1/\beta}.

Example .

Either $X=\mathbb{R},\rho=\left|\cdot\right|,\ \varphi\left(x\right)=\tfrac{5}{6}x,$

	$\displaystyle\ F\left(x,y\right)$	$\displaystyle=\tfrac{1}{2}x+\tfrac{1}{3}y,$
	$\displaystyle F\left(x,x\right)$	$\displaystyle=\varphi\left(x\right),\$
	$\displaystyle\left\|F\left(x_{1},y_{1}\right)-F\left(x_{2},y_{2}\right)\right\|$	$\displaystyle\leq\tfrac{1}{2}\left\|x_{1}-x_{2}\right\|+\tfrac{1}{3}\left\|y_{1}-% y_{2}\right\|,\ \beta=1.$

Either

(22)

x_{n+1}=\tfrac{5}{6}x_{n},\ n=0,1,\ldots\ ,\ x_{0}=1.

(23)

x_{n+2}=\tfrac{1}{2}x_{n+1}+\tfrac{1}{3}x_{n},\ n=0,1,\ldots\ ,\ x_{0}=1,\ x_{% 1}=1.

(24)

x_{n+2}=\tfrac{1}{3}x_{n+1}+\tfrac{1}{2}x_{n},\ n=0,1,\ldots\ \ <x_{0}=1,\ x_{% 1}=1.

In this case we obtain the formulas:

(22^′)

\lim_{n\rightarrow\infty}(x_{n})^{\tfrac{1}{n}}=\tfrac{5}{6}=\tfrac{1}{2}+% \tfrac{1}{3},

(23^′)

\lim_{n\rightarrow\infty}x_{n}^{1/n}=a,

where a is the positive root of the equation $x^{2}-\tfrac{1}{2}x-\tfrac{1}{3}=0$ , that's to say $a=\frac{3+\sqrt{57}}{12}$ . In the same way we obtain

(24^′)

\lim_{n\rightarrow\infty}x_{n}^{1/n}=b,

or $b$ is the positive root of the characteristic equation $x^{2}-\frac{1}{3}x-\tfrac{1}{2}=0\$ that's to say $b=\frac{1+\sqrt{19}}{6}$ . It is clear that $\ \frac{5}{6}<\frac{3+\sqrt{57}}{12}<\frac{1+\sqrt{19}}{6}.$

Bibliography

[1] I. Pavaloiu, ^†^†margin: $\leftarrow$ clickable
$\leftarrow$ clickable Introduction to the theory of approximation of solutions of equations , Ed. Dacia, Cluj-Napoca, 1976.
[2] I. Păvăloiu, Solving equations by interpolation , Dacia Publishing House, Cluj-Napoca, 1981.
[3] Weinischke, JH, On a class of iteration methods , Num. Math., 6 (1964), 395–404.

On optimal iterative methods

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

References

Paper (preprint) in HTML form