La résolution des systèmes d’équations opérationnelles à l’aide des méthodes itératives

par
Ion Păvăloiu
à Cluj

1. Soient $X$ et $Y$ deux espaces de type Banach et $Z=X\times Y$ le produit cartésien de ces espaces.

Dans l’espace $Z$ on considérera l’équation suivante:

(1)		$\displaystyle x$	$\displaystyle=\varphi\left(x,y\right)$
	$\displaystyle y$	$\displaystyle=\psi\left(x,y\right).$

Dans la présente note on interprétera l’équation antérieure comme un système de deux équations à deux inconnues où $\varphi$ et $\psi$ sont des opérateurs définis sur $Z$ et à valeurs respectivement $X$ et $Y .$ De cette manière on mettra en évidence un critérium de convergence du procédé de Gauss-Seidel appliqué à la résolution de ce systéme. Ensuite on montrera que ce criterium est plus général que ceux qui sont connus.

Enfin on appliquera les résultats obtenus à l’élaboration d’une nouvelle méthode de résolution des systèmes des équations lineaires.

Une partie des résultats de cette note ont été obtenus par nous dans un cas particulier $\left(X=Y=\mathbb{R}\right)$ dans le travail [2].

2. On suppose que les opérateurs $\varphi$ et $\psi$ satisfont les conditions suivantes:

a) Les opérateurs $\varphi$ et $\psi$ transforment le domaine $D\subset Z$ en lui même.

b) Il existe des constantes $\alpha,\beta,$ a et $b$ telles que

	$\displaystyle\left\\|\psi\left(x_{2},y_{2}\right)-\psi\left(x_{1},y_{1}\right)\right\\|$	$\displaystyle\leq a\left\\|x_{2}-x_{1}\right\\|+b\left\\|y_{2}-y_{1}\right\\|$
	$\displaystyle\left\\|\varphi\left(x_{2},y_{2}\right)-\varphi\left(x_{1},y_{1}% \right)\right\\|$	$\displaystyle\leq\alpha\left\\|x_{2}-x_{1}\right\\|+\beta\left\\|y_{2}-y_{1}\right\\|$

pour tout $\left(x_{i},y_{i}\right)\in D,\ i=1,2.$

Théorème 1.

Si les opérateurs $\varphi$ et $\psi$ satisfont les conditions a) et b), où les constantes $\alpha,\ \beta$ , $a$ et $b$ satisfont aux inégalités:

(2)		$\displaystyle\alpha+b+a\beta$	$\displaystyle<2,$
	$\displaystyle\left(1-\alpha\right)\left(1-b\right)$	$\displaystyle>a\beta,$

alors on a les propriétés suivantes:

a’) Le systéme (1) a une seule solution $\left(\bar{x},\bar{y}\right)\in\bar{D}$

b’) Le procédé itératif

(3)		$\displaystyle x_{n}$	$\displaystyle=\varphi\left(x_{n-1},y_{n-1}\right),$
	$\displaystyle y_{n}$	$\displaystyle=\psi\left(x_{n},y_{n-1}\right),\ \;\;n=1,2,\ldots,\ \left(x_{0},% y_{0}\right)\in D$

est convergent et on a:

\displaystyle\bar{x}

\displaystyle=\lim_{n\rightarrow\infty}x_{n},\qquad\bar{y}=\lim_{n\rightarrow% \infty}y_{n}.

Démonstration.

On montrera d’abord qu’on a la propriété b’). Pour cela on observera que les sommes partielles des deux séries suivantes

(4)		$\displaystyle x_{0}+\sum_{i=1}^{\infty}\left(x_{i}-x_{i-1}\right)$
	$\displaystyle y_{0}+\sum_{i=1}^{\infty}\left(y_{i}-y_{i-1}\right)$

coïncident avec les termes des suite (3). En notant

	$\displaystyle f_{n-1}$	$\displaystyle=\left\\|x_{n}-x_{n-1}\right\\|,$
	$\displaystyle g_{n-1}$	$\displaystyle=\left\\|y_{n}-y_{n-1}\right\\|,\qquad n=1,2,\ldots,$

et tenant compte des conditions b) on obtient les inégalités suivantes

	$\displaystyle f_{n}$	$\displaystyle\leq\alpha f_{n-1}+\beta g_{n-1}$
	$\displaystyle g_{n}$	$\displaystyle\leq af_{n}+bg_{n-1},\ \;\;n=1,2,\ldots\ .$

En employant maintenant le lemme 2 [2] il en résulte que si les conditions (2) ont lieu alors il existe un constante $C$ indépendente de $n$ telleque l’on ait

	$\displaystyle f_{n}$	$\displaystyle\leq Ch_{1}^{n-1}k_{1}^{n-1},\ \;\;$
	$\displaystyle g_{n}$	$\displaystyle\leq Ch_{1}^{n}k_{1}^{n-1}$

et que les séries $\sum_{i=0}^{\infty}f_{i},\sum_{i=0}^{\infty}g_{i}$ sont convergentes, où $0\leq h_{1}k_{1}<1,\ \left(h_{1},k_{1}\right)$ etant une solution positive du système algébrique suivant:

	$\displaystyle\alpha+\beta h$	$\displaystyle=kh$
	$\displaystyle ak+b$	$\displaystyle=kh.$

Il en résulte la convergence absolue des séries (4) et donc la convergence du procédé (3). Si $\bar{x}$ et $\bar{y}$ sont les limites des suites (3) alors en tenant compte de b) il en résulte que $\left(\bar{x},\bar{y}\right)\$ est une solution pour le système (1).

Pour l’unicité on supposera que le système (1) a deux solutions $\left(\bar{x},\bar{y}\right)\in\bar{D}$ et $\left(\bar{x}_{1},\bar{y}_{1}\right)\in\bar{D}$ alors on a

	$\displaystyle\left\\|\bar{x}-\bar{x}_{1}\right\\|$	$\displaystyle\leq\alpha\left\\|\bar{x}-\bar{x}_{1}\right\\|+\beta\left\\|\bar{y}-% \bar{y}_{1}\right\\|$
	$\displaystyle\left\\|\bar{y}-\bar{y}_{1}\right\\|$	$\displaystyle\leq a\left\\|\bar{x}-\bar{x}_{1}\right\\|+b\left\\|\bar{y}-\bar{y}_% {1}\right\\|$

d’où on déduit

	$\displaystyle\left\\|\bar{x}-\bar{x}_{1}\right\\|$	$\displaystyle\leq\tfrac{\beta a}{\left(1-b\right)\left(1-\alpha\right)}\cdot% \left\|\left\|\bar{x}-\bar{x}_{1}\right\|\right\|$
	$\displaystyle\left\\|\bar{y}-\bar{y}_{1}\right\\|$	$\displaystyle\leq\tfrac{\beta a}{\left(1-b\right)\left(1-\alpha\right)}\cdot% \left\\|\bar{y}-\bar{y}_{1}\right\\|$

ce qui contredit le fait que $\left(1-b\right)\left(1-\alpha\right)>a\beta.$ ∎

Remarque.

Si $\alpha,\ \beta,\ a$ et $b$ satisfont les conditions $\alpha+\beta<1,\ a+b<1$ ou $\alpha+a<1,\ \beta+b<1$ alors les conditions (2) sont vérifiées.

L’évaluation des erreurs est donnée par les inégalités suivantes:

	$\displaystyle\left\\|\bar{x}-x_{n}\right\\|$	$\displaystyle\leq C\tfrac{h_{1}^{n-1}k_{1}^{n-1}}{1-h_{1}k_{1}}$
	$\displaystyle\left\\|\bar{y}-y_{n}\right\\|$	$\displaystyle\leq C\tfrac{h_{1}^{n}k_{1}^{n-1}}{1-h_{1}k_{1}},\ \;\;n=1,2,% \ldots\ .\alignqed$

3. On appliquera les résultats exposés antérieurement à la résolution des systémes d’équations linéaires de la forme

(5)

X=AX+b

où $X\in\mathbb{R}^{n}$ est l’inconnue, $A=\left(a_{i,j}\right);\ i,\ j=\overline{1,n}$ est la matrice du système et $b\in\mathbb{R}^{n}$ est le terme libre.

Pour la résolution du système (5) on décomposera la matrice $A$ en les matrices $M_{1},\ M_{2},\ M_{3},\ M_{4}$ des types suivants. $M_{1}$ est une matrice du type $\left(s,\ s\right),\ M_{2}$ est du type $\left(s,\ n-s\right),\ M_{4}$ est du type $\left(n-s,s\right)$ et $M_{4}\$ est du type $\left(n-s,\ n-s\right),$ $1\leq s<n,$ c’est-à-dire que $A$ a la forme suivante

A=\underset{s}{\left(\begin{array}[c]{ccc}M_{1}&\vdots&M_{2}\\ \cdots&&\cdots\\ M_{3}&\vdots&M_{4}\end{array}\right)}s.

On notera aussi

X=\binom{u}{v}\ \;\text{et\ \ }b=\binom{b_{1}}{b_{2}}

où $u,\ b_{1}\in\mathbb{R}^{s}$ et $v,\ b_{2}\in\mathbb{R}^{n-s}.$ Ainsi le systéme (5) peut être écrit sous la forme:

(6)		$\displaystyle u$	$\displaystyle=M_{1}u+M_{2}v+b_{1}$
	$\displaystyle v$	$\displaystyle=M_{3}u+M_{4}v+b_{2}$

où $u$ et $v$ sont les vecteurs des inconnues, $\left(u,v\right)\in\mathbb{R}^{s}\times\mathbb{R}^{n-s}.$

Pour la résolution du système (6) on appliquera le procédé itératif suivant:

(7)		$\displaystyle u_{i}$	$\displaystyle=M_{1}u_{i-1}+M_{2}v_{i-1}+b_{1}$
	$\displaystyle v_{i}$	$\displaystyle=M_{3}u_{i}+M_{4}v_{i-1}+b_{2},\;\;i=1,2,\ldots,\;\left(u_{0},v_{% 0}\right)\in\mathbb{R}^{s}\times\mathbb{R}^{n-s}.$

Ce procédé itératif résulte comme une application du procédé (3) exposé dans la première partie de cette note.

En appliquant la théorème 1 on obtiendra le

Théorème 2.

Si les matrices $M_{1},M_{2},M_{3}$ et $M_{4}\$ satisfont aux inégalités suivantes:

(8)		$\displaystyle\left\\|M_{1}\right\\|+\left\\|M_{4}\right\\|+\left\\|M_{2}\right\\|\ % \left\\|M_{3}\right\\|$	$\displaystyle<2$
	$\displaystyle\left(1-\left\\|M_{1}\right\\|\right)\left(1-\left\\|M_{4}\right\\|\right)$	$\displaystyle>\left\\|M_{3}\right\\|\left\\|M_{2}\right\\|$

alors le système (6) a une seule solution $\left(\bar{u},\ \bar{v}\right)\in\mathbb{R}^{s}\times\mathbb{R}^{n-s}$ et le procédé (7) converge vers cette solution.

On a ainsi obtenu une nouvelle méthode itérative de résolution des systèmes d’équations. Cette méthode converge dans des conditions beacoup plus générales que la méthode de l’itération simple ou la méthode de Gauss-Seidel. On ilustrera ce fait par l’example numérique suivant.

4. Soit donné le système:

(9)		$\displaystyle x_{1}$	$\displaystyle=0.02x_{1}+0.045x_{2}+8x_{3}+0.4$
	$\displaystyle x_{2}$	$\displaystyle=0.05x_{1}+0.042x_{2}+3x_{3}-0.6$
	$\displaystyle x_{3}$	$\displaystyle=0.003x_{1}+0.013x_{2}+0.45x_{3}-0.8.$

On notera

	$\displaystyle u$	$\displaystyle=\binom{x_{1}}{x_{2}},\ v=\left(x_{3}\right),\$
	$\displaystyle M_{1}$	$\displaystyle=\binom{0.02\ \ 0.045}{0.05\ \ 0.042},\ \;\;M_{2}=\binom{8}{3}$
	$\displaystyle M_{3}$	$\displaystyle=\left(0.003,\ 0.013\right),\;\;M_{4}=\left(0.45\right),\ \;\;$
	$\displaystyle b_{1}$	$\displaystyle=\binom{\ \ 0.4}{-0.6},\ \;\;b_{2}=\left(-0.8\right).$

Si on considère pour ces matrices la norme uniforme on a

	$\displaystyle\left\\|M_{1}\right\\|$	$\displaystyle=0.092,\ \;$
	$\displaystyle\left\\|M_{2}\right\\|$	$\displaystyle=8,\ \;$
	$\displaystyle\left\\|M_{3}\right\\|$	$\displaystyle=0.016\ \;\text{et\ \ }$
	$\displaystyle\left\\|M_{4}\right\\|$	$\displaystyle=0.45.$

On vérifiera si avec ces valeurs les conditions (8) sont remplies,

(10)		$\displaystyle 0.092+0.45+8\times 0.016$	$\displaystyle=0.67<2$
	$\displaystyle\left(1-0.092\right)\left(1-0.45\right)$	$\displaystyle=0.4994>0.016\times 8=0.128$

Il en résulte que les conditions (8) sont vérifiées. Du théorème 2 et de (10) il résulte que le procédé itératif suivant

	$\displaystyle x_{1}^{\left(i\right)}$	$\displaystyle=0.02x_{1}^{\left(i-1\right)}+0.045x_{2}^{\left(i-1\right)}+8x_{3% }^{\left(i-1\right)}+0,4$
	$\displaystyle x_{2}^{\left(i\right)}$	$\displaystyle=0.05x_{1}^{\left(i-1\right)}+0.042x_{2}^{\left(i-1\right)}+3x_{3% }^{\left(i-1\right)}-0,6$
	$\displaystyle x_{3}^{\left(i\right)}$	$\displaystyle=0.003x_{1}^{\left(i\right)}+0.013x_{2}^{\left(i\right)}+0,45x_{3% }^{\left(i-1\right)}-0.8,\ \;i=1,2,\ldots$

$x_{1}^{0},\ x_{2}^{0},\ x_{3}^{0}$ arbitraires, converge vers la solution du systême (5).

En exécutant les calculs on vérifie toutes les conclusions théoriques antérieures et après 40 itérations environ on obtient la solution approchée suivante

	$\displaystyle x_{1}$	$\displaystyle\approx-13.6542065,\ \;$
	$\displaystyle x_{2}$	$\displaystyle\approx-6.6168795,\ \;$
	$\displaystyle x_{3}$	$\displaystyle\approx-1.6854203.$

Bibliographie

Reçu le 12.VII.1969.

	$\displaystyle\left\\|\psi\left(x_{2},y_{2}\right)-\psi\left(x_{1},y_{1}\right)\right\\|$	$\displaystyle\leq a\left\\|x_{2}-x_{1}\right\\|+b\left\\|y_{2}-y_{1}\right\\|$
	$\displaystyle\left\\|\varphi\left(x_{2},y_{2}\right)-\varphi\left(x_{1},y_{1}% \right)\right\\|$	$\displaystyle\leq\alpha\left\\|x_{2}-x_{1}\right\\|+\beta\left\\|y_{2}-y_{1}\right\\|$

	$\displaystyle\left\\|\bar{x}-\bar{x}_{1}\right\\|$	$\displaystyle\leq\alpha\left\\|\bar{x}-\bar{x}_{1}\right\\|+\beta\left\\|\bar{y}-% \bar{y}_{1}\right\\|$
	$\displaystyle\left\\|\bar{y}-\bar{y}_{1}\right\\|$	$\displaystyle\leq a\left\\|\bar{x}-\bar{x}_{1}\right\\|+b\left\\|\bar{y}-\bar{y}_% {1}\right\\|$

	$\displaystyle\left\\|\bar{x}-\bar{x}_{1}\right\\|$	$\displaystyle\leq\tfrac{\beta a}{\left(1-b\right)\left(1-\alpha\right)}\cdot% \left\|\left\|\bar{x}-\bar{x}_{1}\right\|\right\|$
	$\displaystyle\left\\|\bar{y}-\bar{y}_{1}\right\\|$	$\displaystyle\leq\tfrac{\beta a}{\left(1-b\right)\left(1-\alpha\right)}\cdot% \left\\|\bar{y}-\bar{y}_{1}\right\\|$

(8)		$\displaystyle\left\\|M_{1}\right\\|+\left\\|M_{4}\right\\|+\left\\|M_{2}\right\\|\ % \left\\|M_{3}\right\\|$	$\displaystyle<2$
	$\displaystyle\left(1-\left\\|M_{1}\right\\|\right)\left(1-\left\\|M_{4}\right\\|\right)$	$\displaystyle>\left\\|M_{3}\right\\|\left\\|M_{2}\right\\|$

Solving the systems of operator equations by iterative methods

Abstract

Authors

Title

Original title (in French)

English translation of the title

Keywords

Cite this paper as:

PDF

About this paper

Journal

Publisher Name

DOI

Print ISBN

Online ISBN

Paper (preprint) in HTML form