"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

Preprint Nr.1, 1989, pp.95-104

On approximating the solutions of equations in metric spaces

Ion Pavaloiu

In this note we study the evaluation of errors that arise during the numerical resolution of equations in metric spaces using certain multi-step iteration methods.

Consider a metric space $\left(X,\rho\right)$ complete and the following equation:

(1)

x=f\left(x\right),

Or $f:X\rightarrow X$ is any operator.

Let us designate by $X^{k+1}=X\times X\times\ldots\times X,$ that is to say the Cartesian product of the set $X$ with himself $k+1$ times.

For the resolution of equation ( 1 ) we consider the application $G:X^{k+1}\rightarrow X$ which we assume is restricted to the diagonal of space $X^{k+1}$ coincides with the operator $f$ , that's to say:

(2)

G\left(x,x,\ldots,x\right)=f\left(x\right),

for each $x\in X$ .

Consider the following $\left(x_{n}\right)_{n=0}^{\infty}$ provided by the following iteration process:

(3)

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

Or $x_{0},x_{1},\ldots,x_{k}\in X$ are given elements.

Let us designate by $D\subset X$ a bounded set in this space. We assume that on the set $D^{k+1}$ the operator $G$ verifies the Lipschitz condition, that is:

(4)

\rho\big{(}G\left(u_{1},u_{2},\ldots,u_{k+1}\right),G\left(v_{1},v_{2},\ldots,% v_{k+1}\right)\big{)}\leq\sum_{i=1}^{k+1}a_{i}\rho\left(u_{i},v_{i}\right),

Or $a_{i}\in\mathbb{R},\ a_{i}\geq 0,\ i=1,2,\ldots,k+1,$ for each $\left(u_{1},u_{2},\ldots,u_{k+1}\right)$ , $\left(v_{1},v_{2},\ldots,v_{k+1}\right)\in D^{k+1}$ .

Consider the equation:

(5)

a_{1}+a_{2}t+\ldots+a_{k+1}t^{k}=t^{k+1}.

We know that in the case where $a_{i}\geq 0$ for each $i=1,2,\ldots,k+1$ and where there exists at least one number $i_{1},1\leq i_{1}\leq k+1$ for which $a_{i_{1}}>0$ , this equation has only one root $t_{1}$ real and positive.

If in addition:

(6)

\beta=\sum_{i=1}^{k+1}a_{i}<1

then this root verifies the inequality

(7)

0<t_{1}<1.

Regarding the convergence of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ provided by method ( 3 ) we have the following theorem:

Theorem 1 .

If the application $G$ and the initial elements $x_{0},x_{1},\ldots,x_{k}$ meet the following conditions:

i)

L’application $G$ fulfills condition ( 4 ) where $a_{i},\ i=1,2,\ldots,k+1$ , satisfy the relation ( 6 );
ii)

The whole $S=\{x\in X:\rho\left(x,x_{0}\right)\leq\frac{\alpha}{1-t_{1}}\}\subseteq D,$ Or $t_{1}$ is the positive root of equation ( 5 ) and

$\alpha\geq\max\Big{\{}\rho\left(x_{0},x_{1}\right),\tfrac{1}{t_{1}}\rho\left(x% _{1},x_{2}\right),\ldots,\tfrac{1}{t_{1}^{k-1}}\rho\left(x_{k-1},x_{k}\right)% \Big{\}};$

then we have the following properties:

j)

$x_{n}\in S$ for each $n=0,1,\ldots$ ;
jj)

the sequel $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent and if we denote by $x^{\ast}$ the limit of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ , SO $x^{\ast}\in S$ And $x^{\ast}$ is the unique solution of equation ( 1 ) of the sphere $S$ ;
jjj)

we have the following inequalities:

$\rho\left(x^{\ast},x_{n}\right)\leq\tfrac{\alpha t_{1}^{n}}{1-t_{1}},\qquad% \text{pour chaque }n=0,1,\ldots$

Demonstration.

From conclusion ii) it follows that $\rho\left(x_{i},x_{i+1}\right)\leq\alpha t_{1}^{i}$ for each $i=0,1,\ldots,k-1$ . For $i=1,2,\ldots,k$ we have the following inequalities:

(8)	$\displaystyle\rho\left(x_{i},x_{0}\right)$	$\displaystyle\leq\rho\left(x_{0},x_{1}\right)+\rho\left(x_{1},x_{2}\right)+% \ldots+\rho\left(x_{i-1},x_{i}\right)$
	$\displaystyle\leq\alpha+\alpha t_{1}+\ldots+\alpha t_{1}^{i-1}$
	$\displaystyle<\tfrac{\alpha}{1-t_{1}}$

from which we deduce that $x_{i}\in S,$ For $i=1,2,\ldots,k$ .

Subsequently we assume that $x_{i}\in S$ And $\rho\left(x_{i-1},x_{i}\right)\leq\alpha t^{i-1},$ for each $i=1,2,\ldots,n+k+1$ . From this inequality we deduce that:

		$\displaystyle\rho\left(x_{n+k+2},x_{n+k+1}\right)\leq\rho\big{(}G\left(x_{n},x% _{n+1},\ldots,x_{n+k}\right),G\left(x_{n+1},\ldots,x_{n+k+1}\right)\big{)}$
		$\displaystyle\sum_{i=1}^{-k+1}a_{i}\rho\left(x_{n+i-1},x_{n+i}\right)\leq% \alpha\left(a_{1}t_{1}^{n}+\ldots+a_{k+1}t_{1}^{k+n}\right)=\alpha t_{1}^{n+k+% 1},$

where we used the fact that $t_{1}$ verifies equation ( 5 ).

From the above inequalities, and in a manner similar to that used in the demonstration of relation ( 8 ), we deduce that $x_{n+k+2}\in S$ . From the principle of mathematical induction it therefore follows that all the elements of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ belong to the sphere $S$ .

On the completeness of space $X$ and inequalities

(9)		$\displaystyle\rho\left(x_{n+s},x_{n}\right)$	$\displaystyle\leq\rho\left(x_{n},x_{n+1}\right)+\ldots+\rho\left(x_{n+s-1},x_{% n+s}\right)$
		$\displaystyle\leq\alpha\left(t_{1}^{n}+t_{1}^{n+1}+\ldots+t_{1}^{n+s-1}\right)% \leq\tfrac{\alpha t_{1}^{n}}{1-t_{1}}$

for each $s=1,2,\ldots,$ it follows that the following $\left(x_{n}\right)_{n=0}^{\infty}$ is convergent.

Let us designate by $x^{\ast}=\lim\limits_{n\rightarrow\infty}x_{n}$ . So by passing to limit in the inequalities ( 9 ) with $s\rightarrow\infty,$ on a:

(10)

\rho\left(x_{n},x^{\ast}\right)\leq\tfrac{\alpha t_{1}^{n}}{1-t_{1}},\qquad n=% 0,1,\ldots

Let us now demonstrate that $G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right)=x^{\ast}$ .

In fact we have:

		$\displaystyle\rho\left(x^{\ast},G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right% )\right)\leq$
		$\displaystyle\leq\rho\left(x_{n+k+1},x^{\ast}\right)+\rho\left(x_{n+k+1},G% \left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right)\right)$
		$\displaystyle\leq\rho\left(x_{n+k+1},x^{\ast}\right)+\rho\left(G\left(x_{n},x_% {n+1},\ldots,x_{n+k}\right),G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right)\right)$
		$\displaystyle\leq\rho\left(x_{n+k+1},x^{\ast}\right)+\sum_{i=1}^{k+1}a_{i}\rho% \left(x_{n+i-1},x^{\ast}\right)$
		$\displaystyle\leq\tfrac{\alpha t_{1}^{n+k+1}}{1-t_{1}}+\sum_{i=1}^{k+1}a_{i}% \tfrac{\alpha t_{1}^{n+i-1}}{1-t_{1}}$
		$\displaystyle=\tfrac{\alpha}{1-t_{1}}\left[t_{1}^{n+k+1}+t_{1}^{n}\sum_{i=1}^{% k+1}a_{i}t_{1}^{i-1}\right]$
		$\displaystyle=\tfrac{2\alpha t_{1}^{n+k+1}}{1-t_{1}}.$

This inequality is verified for each $n\in\mathbb{N}$ , from which it follows that we have the equality $x^{\ast}=G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right)$ , but this relation and relation ( 2 ) imply that the element $x^{\ast}\subset S$ is the solution to equation ( 1 ). ∎

Let us now show that $x^{\ast}$ is the unique solution of equation ( 1 ) which belongs to the sphere $S$ . Suppose instead that equation ( 1 ) has at least two solutions $x^{\ast}$ And $y^{\ast}$ in $S$ . So from $x^{\ast}=f\left(x^{\ast}\right)$ And $y^{\ast}=f\left(y^{\ast}\right)$ , and from ( 2 ) it follows that:

	$\displaystyle\rho\left(x^{\ast},y^{\ast}\right)$	$\displaystyle=\rho\big{(}G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right),G% \left(y^{\ast},y^{\ast},\ldots,y^{\ast}\right)\big{)}$
		$\displaystyle\leq\sum_{i=1}^{k+1}a_{i}\cdot\rho\left(x^{\ast},y^{\ast}\right)$

from which, if we take into account ( 6 ) we obtain

0<\rho\left(x^{\ast},y^{\ast}\right)<\rho\left(x^{\ast},y^{\ast}\right).

This last inequality being impossible, it follows that the assumption is false, therefore that equation ( 1 ) has a unique solution.

Let us then consider the application $G^{\ast}:X^{k+1}\rightarrow X$ which fills with the application $G$ the following condition:

(11)

\rho\big{(}G\left(u_{1},u_{2},\ldots,u_{k+1}\right),G^{\ast}\left(u_{1},u_{2},% \ldots,u_{k+1}\right)\big{)}\leq\varepsilon,\qquad\varepsilon>0

for each $\left(u_{1},u_{2},\ldots,u_{k+1}\right)\in D^{k+1}$ .

To solve equation ( 1 ) we will replace the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ provided by the relation ( 3 ), subsequently $\left(x_{n}^{\ast}\right)_{n=0}^{\infty}$ provided by the following iterative process:

(12)

x_{n+k+1}^{\ast}=G^{\ast}\left(x_{n}^{\ast},x_{n+1}^{\ast},\ldots,x_{n+k}^{% \ast}\right),\qquad n=0,1,\ldots,

where we assume that the initial elements have been chosen $x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}$ such that the following conditions are met:

(13)		$\displaystyle\rho\left(x_{0}^{\ast},x_{1}^{\ast}\right)$	$\displaystyle\leq\alpha+\tfrac{2\varepsilon}{1-\beta}$
	$\displaystyle\rho\left(x_{1}^{\ast},x_{2}^{\ast}\right)$	$\displaystyle\leq\alpha t_{1}+\tfrac{2\varepsilon}{1-\beta}$
		$\displaystyle....................$
	$\displaystyle\rho\left(x_{k-1}^{\ast},x_{k}^{\ast}\right)$	$\displaystyle\leq\alpha t_{1}^{k-1}+\tfrac{2\varepsilon}{1-\beta}.$

Regarding the relationship $x_{k+1}^{\ast}=G^{\ast}\left(x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}\right)$ we assume that we have the following condition

\rho\left(x_{k}^{\ast},x_{k+1}^{\ast}\right)\leq\alpha t_{1}^{k}+\tfrac{2% \varepsilon}{1-\beta}.

Let us also assume that the set:

(14)

S^{\ast}=\left\{x\in X:\rho\left(x,x_{0}\right)\leq\tfrac{\alpha\left(2-t_{1}% \right)}{1-t_{1}}+\tfrac{\varepsilon}{1-\beta}\right\}

is contained in $D$ .

Furthermore we assume that the initial elements $x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}$ of method ( 12 ) fill with the elements $x_{0},x_{1},\ldots,x_{k}$ of ( 3 ) the following conditions:

(15)		$\displaystyle\rho\left(x_{0},x_{0}^{\ast}\right)$	$\displaystyle\leq\alpha+\tfrac{\varepsilon}{1-\beta}$
	$\displaystyle\rho\left(x_{1},x_{1}^{\ast}\right)$	$\displaystyle\leq\alpha t_{1}+\tfrac{\varepsilon}{1-\beta}$
		$\displaystyle.....................$
	$\displaystyle\rho\left(x_{k},x_{k}^{\ast}\right)$	$\displaystyle\leq\alpha t_{1}^{k}+\tfrac{\varepsilon}{1-\beta}$

Using these assumptions and further using the fact that $G$ verifies the hypotheses of Theorem 1 , we will demonstrate that for each $n\in\mathbb{N}$ we have the following inequalities:

(16)

\rho\left(x_{n+k+1},x_{n+k+1}^{\ast}\right)\leq\alpha t_{1}^{n+k+1}+\tfrac{% \varepsilon}{1-\beta}

(17)

\rho\left(x_{n+k+1}^{\ast},x_{n+k+2}^{\ast}\right)\leq\alpha t_{1}^{n+k+1}+% \tfrac{2\varepsilon}{1-\beta}

And

(18)

\rho\left(x^{\ast},x_{n+k+1}^{\ast}\right)\leq\tfrac{\alpha\left(2-t_{1}\right% )}{1-t_{1}}t_{1}^{n+k+1}+\tfrac{\varepsilon}{1-\beta}.

Indeed, by using relations ( 15 ) we obtain the following relations:

(19)		$\displaystyle\rho\left(x_{k+1},x_{k+1}^{\ast}\right)=$
	$\displaystyle=\rho\big{(}G\left(x_{0},x_{1},\ldots,x_{k}\right),G^{\ast}\left(% x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}\right)\big{)}$
	$\displaystyle\leq\rho\big{(}G\left(x_{0},x_{1},\ldots,x_{k}\right),G\left(x_{0% }^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}\right)\big{)}+$
	$\displaystyle+\rho\big{(}G\left(x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}% \right),G^{\ast}\left(x_{0}^{\ast},\ldots,x_{k}^{\ast}\right)\big{)}$
	$\displaystyle\leq\varepsilon+a_{1}\rho\left(x_{0},x_{0}^{\ast}\right)+a_{2}% \rho\left(x_{1},x_{1}^{\ast}\right)+\ldots a_{k+1}\rho\left(x_{k},x_{k}^{\ast}\right)$
	$\displaystyle\leq\varepsilon+\tfrac{\varepsilon}{1-\beta}\left(a_{1}+\ldots+a_% {k+1}\right)+\alpha\big{(}a_{1}+a_{2}t_{1}+\ldots+a_{k+1}t_{1}^{k}\big{)}$
	$\displaystyle=\tfrac{\varepsilon}{1-\beta}+\alpha t_{1}^{k+1}$

that is to say that inequality ( 16 ) is verified, for $n=0.$ Let us now show that $x_{k+1}^{\ast}\in S^{\ast}$ . Using inequalities ( 19 ) and ( 8 ) we obtain:

(20)	$\displaystyle\rho\left(x_{k+1}^{\ast},x_{0}\right)$	$\displaystyle\leq\rho\left(x_{k+1}^{\ast},x_{k+1}\right)+\rho\left(x_{k+1},x_{% 0}\right)$
	$\displaystyle\leq\tfrac{\alpha}{1-t_{1}}+\tfrac{\varepsilon}{1-\beta}+\alpha t% _{1}^{k+1}\leq\alpha+\tfrac{\alpha}{1-t_{1}}+\tfrac{\varepsilon}{1-\beta}$
	$\displaystyle=\tfrac{\alpha\left(2-t_{1}\right)}{1-t_{1}}+\tfrac{\varepsilon}{% 1-\beta}.$

Generally, if we assume that

x_{n}^{\ast},x_{n+1}^{\ast},\ldots,x_{n+k}^{\ast}\in S^{\ast}

and that we have the following inequalities:

\rho\left(x_{n+i},x_{n+1}^{\ast}\right)\leq\alpha t_{1}^{n+1}+\tfrac{% \varepsilon}{1-\beta}

for each $i=1,2,\ldots,k,$ then in a manner similar to that used to demonstrate inequality ( 19 ) we obtain:

(21)		$\displaystyle\rho\left(x_{n+k+1},x_{n+k+1}^{\ast}\right)$	$\displaystyle\leq\varepsilon+a_{1}\rho\left(x_{n},x_{n}^{\ast}\right)+\ldots+a% _{k+1}\rho\left(x_{n+k},x_{n+k}^{\ast}\right)$
		$\displaystyle\leq\varepsilon+\alpha t_{1}^{n}\left(a_{1}+a_{2}t_{1}+\ldots+a_{% k+1}t_{1}^{k}\right)+\tfrac{\varepsilon\beta}{1-\beta}$

\displaystyle\varepsilon+\alpha t_{1}^{n+k+1}+\tfrac{\varepsilon\beta}{1-\beta% }=\alpha t_{1}^{n+k+1}+\tfrac{\varepsilon}{1-\beta}

from which it follows that we have the inequalities ( 16 ) for each $n\in\mathbb{N}$ . From relations ( 21 ) and ( 8 ), in a manner similar to that used in the deduction of relation ( 20 ), it follows that $x_{n+k+1}^{\ast}\in S^{\ast}$ .

Let us now demonstrate that the inequalities ( 17 ) are verified. If we consider the relations ( 13 ) we have the following inequalities:

(22)	$\displaystyle\rho\left(x_{k+1}^{\ast},x_{k+2}^{\ast}\right)$	$\displaystyle\leq\rho\big{(}G^{\ast}\left(x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{% k}^{\ast}\right),G^{\ast}\left(x_{1}^{\ast},\ldots,x_{k+1}^{\ast}\right)\big{)}$
	$\displaystyle\leq\rho\big{(}G^{\ast}\left(x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{% k}^{\ast}\right),G\left(x_{0}^{\ast},x_{1}^{\ast},\ldots x_{k}^{\ast}\right)% \big{)}$
	$\displaystyle+\rho\big{(}G\left(x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}% \right),G\left(x_{1}^{\ast},x_{2}^{\ast},\ldots,x_{k+1}^{\ast}\right)\big{)}$
	$\displaystyle+\rho\big{(}G^{\ast}\left(x_{1}^{\ast},x_{2}^{\ast},\ldots,x_{k+1% }^{\ast}\right),G\left(x_{1}^{\ast},x_{2}^{\ast},\ldots,x_{k+1}^{\ast}\right)% \big{)}$
	$\displaystyle\leq 2\varepsilon+\tfrac{2\varepsilon\beta}{1-\beta}+\alpha\big{(% }a_{1}+a_{2}t_{1}+\ldots+a_{k+1}t_{1}^{k}\big{)}$
	$\displaystyle=\tfrac{2\varepsilon}{1-\beta}+\alpha t_{1}^{k+1},$

so we obtained the inequality ( 17 ) for $n=0.$

Now assuming that we have the following inequalities:

\rho\left(x_{n+i}^{\ast},x_{n+i+1}^{\ast}\right)\leq\tfrac{2\varepsilon}{1-% \beta}+\alpha t_{1}^{n+i},

For $i=0,1,\ldots,k,$ in a manner similar to that employed in the deduction of inequality ( 22 ) we obtain inequalities ( 17 ).

For inequalities ( 18 ) we have

	$\displaystyle\rho\left(x^{\ast},x_{n+k+1}^{\ast}\right)$	$\displaystyle\leq\rho\left(x^{\ast},x_{n+k+1}\right)+\rho\left(x_{n+k+1},x_{n+% k+1}^{\ast}\right)$
		$\displaystyle\leq\tfrac{\alpha t_{1}^{n+k+1}}{1-t_{1}}+\alpha t_{1}^{n+k+1}+% \tfrac{\varepsilon}{1-\beta}$
		$\displaystyle=\tfrac{\alpha\left(1-t_{1}\right)}{1-t_{1}}t_{1}^{n+k+1}+\tfrac{% \varepsilon}{1-\beta}$

that is, inequalities ( 18 ).

Inequalities ( 18 ) provide an assessment of the distance between the exact solution of equation ( 1 ) and its approximation, obtained using the iteration method ( 12 ).

Noticed .

If we notice that the whole $D\subset X,$ on which condition ( 4 ) is fulfilled, is itself a metric space, it follows that we can consider theorem 1 as a special case of the main result contained in the work [ 3 ] . From our point of view the importance of this theorem consists in the fact that the set $D$ being limited it allows easy choice of application $G^{\ast}$ , application that fills with the application $G$ the condition ( 11 ). Let us imagine for example the trivial case of the equation $x=ax+b=G\left(x\right),\ x\in\mathbb{R}$ and the approximate equation $x^{\ast}=a^{\ast}x^{\ast}+b^{\ast}=G^{\ast}\left(x^{\ast}\right).$

Because $\left|G\left(x\right)-G^{\ast}\left(x\right)\right|=\left|a-a^{\ast}\right|% \cdot\left|x\right|,$ it follows that the difference $\left|G\left(x\right)-G^{\ast}\left(x\right)\right|$ is not bounded, so even in the case $0<a<1$ condition ( 11 ) cannot be fulfilled in the whole space $\mathbb{R}$ .

Bibliography

[1]
[2] I. Păvăloiu, I., Şerb, Sur des methodes iteratives optimales, Research Seminars, Seminar on Functional Analysis and Numerical Methods, Preprint Nr.1 (1983), 175–182.
[3] I.A. Rus, An iterative method for the solution of the equation $x=f\left(x,x,\ldots,x\right),$ Anal. Numér. Théor. Approx., 10 (1981), 95–100.
[4] Weinischke, JH, On a class of iteration methods , Numerical Mathematics 6 (1964), 395–404.

Institute of Computing

Post Office 1

C.P. 68

3400 Cluj-Napoca

Romania

This paper is in final form and no version of it is or will be submitted for publication elsewhere.

On approximating the solutions of equations in metric spaces

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

On approximating the solutions of equations in metric spaces

Theorem 1 .

Demonstration.

Noticed .

Bibliography

Related Posts