"Babeş-Bolyai" University

Faculty of Mathematics and Physics

Research Seminars

Seminar on Functional Analysis and Numerical Methods

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

Sur l’approximation des racines des équations dans un espace métrique

Ion Păvăloiu

Dans cette note nous étudions l’évaluation des erreurs qui surgissent pendant la résolution numérique des équations en espaces métriques à l’aide de certaines méthodes d’itération à plusieurs pas.

Considerons un espace métrique $\left(X,\rho\right)$ complet et l’équation suivante:

(1)

x=f\left(x\right),

où $f:X\rightarrow X$ est un opérateur quelconque.

Déssignons par $X^{k+1}=X\times X\times\ldots\times X,$ c’est-à-dire le produit cartèsien de l’ensemble $X$ avec lui même $k+1$ fois.

Pour la résolution de l’équation (1) nous consiérons l’application $G:X^{k+1}\rightarrow X$ dont nous supposons que sa restriction à la diagonale de l’espace $X^{k+1}$ coincide avec l’opérateur $f$ , c’est-à-dire:

(2)

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

pour chaque $x\in X$ .

Considérons la suite $\left(x_{n}\right)_{n=0}^{\infty}$ fournie par le procédé d’iteration suivant:

(3)

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

où $x_{0},x_{1},\ldots,x_{k}\in X$ sont des éléments donnés.

Désignons par $D\subset X$ un ensemble borné en cet espace. Nous supposons que sur l’ensemble $D^{k+1}$ l’opérateur $G$ vérifie la condition de Lipschitz c’est-à-dire:

(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),

où $a_{i}\in\mathbb{R},\ a_{i}\geq 0,\ i=1,2,\ldots,k+1,$ pour chaque $\left(u_{1},u_{2},\ldots,u_{k+1}\right)$ , $\left(v_{1},v_{2},\ldots,v_{k+1}\right)\in D^{k+1}$ .

Considérons l’équation:

(5)

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

On sait que dans lec cas où $a_{i}\geq 0$ pour chaque $i=1,2,\ldots,k+1$ et où il existe au moins un nombre $i_{1},1\leq i_{1}\leq k+1$ pour lequel $a_{i_{1}}>0$ , cette équation a une seul racine $t_{1}$ réelle et positive.

Si de plus:

(6)

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

alors cette racine vérifie l’inégalité

(7)

0<t_{1}<1.

En ce qui concerne la convergence de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ fournie par la méthode (3) on a le théorème suivant:

Théorème 1.

Si l’application $G$ et les éléments initiaux $x_{0},x_{1},\ldots,x_{k}$ remplissent les conditions suivantes:

i)

L’application $G$ remplit la condition (4) où $a_{i},\ i=1,2,\ldots,k+1$ , satisfont à la relation (6);
ii)

L’ensemble $S=\{x\in X:\rho\left(x,x_{0}\right)\leq\frac{\alpha}{1-t_{1}}\}\subseteq D,$ où $t_{1}$ est la racine positive de l’équation (5) et

$\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{\}};$

alors on a les propriétés suivantes:

j)

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

la suite $\left(x_{n}\right)_{n=0}^{\infty}$ est convergente et si nous désignons par $x^{\ast}$ la limite de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ , alors $x^{\ast}\in S$ et $x^{\ast}$ est la solution unique de l’equation (1) de la sphère $S$ ;
jjj)

on a les inégalités suivantes:

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

Démonstration.

De la conclusion ii) il résulte que $\rho\left(x_{i},x_{i+1}\right)\leq\alpha t_{1}^{i}$ pour chaque $i=0,1,\ldots,k-1$ . Pour $i=1,2,\ldots,k$ on a les inégalités suivantes:

(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}}$

d’où nous déduisons que $x_{i}\in S,$ pour $i=1,2,\ldots,k$ .

Par la suite nous supposons que $x_{i}\in S$ et $\rho\left(x_{i-1},x_{i}\right)\leq\alpha t^{i-1},$ pour chaque $i=1,2,\ldots,n+k+1$ . De cette inégalité nous déduisons que:

		$\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},$

où nous avons utilisé le fait que $t_{1}$ vérifie l’équation (5).

Des inégalités ci-dessus, et d’une manière similaire à celle utilisée à la démonstration de la relation (8), nous déduisons que $x_{n+k+2}\in S$ . Du principe de l’induction mathématique il résulte donc que tous les éléments de la suite $\left(x_{n}\right)_{n=0}^{\infty}$ appartiennent à la sphère $S$ .

De la complétitude de l’espace $X$ et des inégalites

(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}}$

pour chaque $s=1,2,\ldots,$ il résulte que la suite $\left(x_{n}\right)_{n=0}^{\infty}$ est convergente.

Désignons par $x^{\ast}=\lim\limits_{n\rightarrow\infty}x_{n}$ . Alors en passant à limite dans les inégalités (9) avec $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

Démontrons maintenant que $G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right)=x^{\ast}$ .

En effet on a:

		$\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}}.$

Cette inégalité est vérifiée pour chaque $n\in\mathbb{N}$ , d’où il resulte qu’on a l’égalité $x^{\ast}=G\left(x^{\ast},x^{\ast},\ldots,x^{\ast}\right)$ , mais cette relation et la relation (2) impliquent que l’élement $x^{\ast}\subset S$ est la solution de l’équation (1). ∎

Montrons maintenant que $x^{\ast}$ est l’unique solution de l’équation (1) qui appartient à la sphere $S$ . Supposons au contraire que l’équation (1) a au moins deux solutions $x^{\ast}$ et $y^{\ast}$ en $S$ . Alors de $x^{\ast}=f\left(x^{\ast}\right)$ et $y^{\ast}=f\left(y^{\ast}\right)$ , et de (2) il résulte que:

	$\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)$

d’où, si nous tenons compte de (6) on obtient

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

Cette derniere inégalité étant impossible, il résulte que la supposition est fausse, donc que l’équation (1) a une solution unique.

Considérons par la suite l’application $G^{\ast}:X^{k+1}\rightarrow X$ qui remplit avec l’application $G$ la condition suivante:

(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

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

Pour la résolution de l’équation (1) nous remplacerons la suite $\left(x_{n}\right)_{n=0}^{\infty}$ fournie par la relation (3), par la suite $\left(x_{n}^{\ast}\right)_{n=0}^{\infty}$ fournie par le procédé itératif suivant:

(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,

où nous supposons qu’on a choisi les éléments intiaux $x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}$ tels que les conditions suivantes sont remplies:

(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}.$

En ce qui concerne la relation $x_{k+1}^{\ast}=G^{\ast}\left(x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}\right)$ nous supposons que l’on a la condition suivante

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

Supposons aussi que l’ensemble:

(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\}

est contenue dans $D$ .

En outre nous supposons que les éléments initiaux $x_{0}^{\ast},x_{1}^{\ast},\ldots,x_{k}^{\ast}$ de la méthode (12) remplissent avec les éléments $x_{0},x_{1},\ldots,x_{k}$ de (3) les conditions suivantes:

(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}$

À l’aide de ces hypothèses et de plus à l’aide du fait que $G$ vérifie les hypothéses du théoréme 1, nous démontrerons que pour chaque $n\in\mathbb{N}$ on a les inégalités suivantes:

(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}

(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}.

En effet, en employant les relations (15) on obtient les relations suivantes:

(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}$

c’est-à-dire que l’inégalité (16) est vérifiée, pour $n=0.$ Montrons maintenant que $x_{k+1}^{\ast}\in S^{\ast}$ . En employant les inégalités (19) et (8) nous obtenons:

(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}.$

Généralement, si nous supposons que

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

et qu’on a les inegalités suivantes:

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

pour chaque $i=1,2,\ldots,k,$ alors d’une manière similaire à celle employée pour demontrer l’inégalité (19) nous obtenons:

(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}

d’où il résulte qu’on a les inégalités (16) pour chaque $n\in\mathbb{N}$ . Des relations (21) et (8), d’une manière similaire à celle utilisée à la déduction de la relation (20), il résulte que $x_{n+k+1}^{\ast}\in S^{\ast}$ .

Démontrons maintenant que les inégalités (17) sont vérifiées. Si nous envisageons les relations (13) on a les inégalités suivantes:

(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},$

donc nous avons obtenu l’inégalité (17) pour $n=0.$

En supposant maintenant qu’on a les inégalités suivantes:

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

pour $i=0,1,\ldots,k,$ d’une manière similaire à celle employée à la déduction de l’inégalité (22) nous obtenons les inégalités (17).

Pour les inégalités (18) on a

	$\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}$

c’est-à-dire les inégalités (18).

Les inégalités (18) fournissent une évaluation de la distance entre la solution exacte de l’équation (1) et son approximation, obtenue à l’aide de la méthode d’itération (12).

Remarque.

Si nous remarquons que l’ensemble $D\subset X,$ sur lequel la condition (4) est remplie, est lui-même un espace métrique, il resulte que nous pouvons considérer le théorème 1 comme un cas particulier du résultat principal contenu dans le travail [3]. De notre point de vue l’importance de ce théorème consiste dans le fait que l’ensemble $D$ étant borné il permet avec facilité le choix de l’application $G^{\ast}$ , application qui remplit avec l’application $G$ la condition (11). Imaginons par exemple le cas banal de l’équation $x=ax+b=G\left(x\right),\ x\in\mathbb{R}$ et l’équation approximante $x^{\ast}=a^{\ast}x^{\ast}+b^{\ast}=G^{\ast}\left(x^{\ast}\right).$

Du fait que $\left|G\left(x\right)-G^{\ast}\left(x\right)\right|=\left|a-a^{\ast}\right|% \cdot\left|x\right|,$ il résulte que la différence $\left|G\left(x\right)-G^{\ast}\left(x\right)\right|$ n’est pas bornée, donc même dans la cas $0<a<1$ la condition (11) ne peut pas être remplie dans tout l’espace $\mathbb{R}$ .

Bibliographie

[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, J.H., Uber eine klasse von Iterationverfahren, Numerische Mathematik 6 (1964), 395–404.

Institutul de Calcul

Oficiul Poştal 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

Sur l’approximation des racines des équations dans un espace métrique

Théorème 1.

Démonstration.

Remarque.

Bibliographie

Related Posts