Solving the systems of operator equations by iterative methods

by
Ion Păvăloiu
in Cluj

1. Let $X$ And $AND$ two Banach-type spaces and $Z=X\times Y$ the Cartesian product of these spaces.

In space $WITH$ we will consider the following equation:

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

In this note we will interpret the previous equation as a system of two equations with two unknowns where $\varphi$ And $\psi$ are operators defined on $WITH$ and values respectively $X$ And $AND .$ In this way, we will highlight a convergence criterion of the Gauss-Seidel process applied to the resolution of this system. Then we will show that this criterion is more general than those that are known.

Finally, the results obtained will be applied to the development of a new method for solving systems of linear equations.

Part of the results of this note were obtained by us in a particular case $\left(X=Y=\mathbb{R}\right)$ in work [ 2 ] .

2. We assume that the operators $\varphi$ And $\psi$ satisfy the following conditions:

a) Operators $\varphi$ And $\psi$ transform the field $D\subset Z$ in himself.

b) There are constants $\alpha,\beta,$ has and $b$ such as

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

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

Theorem 1 .

If the operators $\varphi$ And $\psi$ satisfy conditions a) and b), where the constants $\alpha,\ \beta$ , $a$ And $b$ satisfy the inequalities:

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

then we have the following properties:

a') The system ( 1 ) has only one solution $\left(\bar{x},\bar{y}\right)\in\bar{D}$

b') The iterative process

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

is convergent and we have:

\displaystyle\bar{x}

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

Demonstration.

We will first show that we have property b'). To do this we will observe that the partial sums of the following two series

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

coincide with the terms of the sequence ( 3 ). Noting

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

and taking into account conditions b) we obtain the following inequalities

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

Now using Lemma 2 [ 2 ] it follows that if conditions ( 2 ) hold then there exists a constant $C$ independent of $n$ such that we have

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

and that the series $\sum_{i=0}^{\infty}f_{i},\sum_{i=0}^{\infty}g_{i}$ are convergent, where $0\leq h_{1}k_{1}<1,\ \left(h_{1},k_{1}\right)$ being a positive solution of the following algebraic system:

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

This results in the absolute convergence of the series ( 4 ) and therefore the convergence of the process ( 3 ). If $\bar{x}$ And $\bar{y}$ are the limits of the sequences ( 3 ) then taking into account b) it results that $\left(\bar{x},\bar{y}\right)\$ is a solution for the system ( 1 ).

For uniqueness we will assume that the system ( 1 ) has two solutions $\left(\bar{x},\bar{y}\right)\in\bar{D}$ And $\left(\bar{x}_{1},\bar{y}_{1}\right)\in\bar{D}$ so we have

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

from which we deduce

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

which contradicts the fact that $\left(1-b\right)\left(1-\alpha\right)>a\beta.$ ∎

Noticed .

And $\alpha,\ \beta,\ a$ And $b$ meet the conditions $\alpha+\beta<1,\ a+b<1$ or $\alpha+a<1,\ \beta+b<1$ then conditions ( 2 ) are verified.

The error evaluation is given by the following inequalities:

	$\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. The results presented previously will be applied to the resolution of systems of linear equations of the form

(5)

X=AX+b

Or $X\in\mathbb{R}^{n}$ is the unknown, $A=\left(a_{i,j}\right);\ i,\ j=\overline{1,n}$ is the system matrix and $b\in\mathbb{R}^{n}$ is the free term.

To resolve the system ( 5 ) we will decompose the matrix $A$ in the matrices $M_{1},\ M_{2},\ M_{3},\ M_{4}$ of the following types. $M_{1}$ is a matrix of the type $\left(s,\ s\right),\ M_{2}$ is of the type $\left(s,\ n-s\right),\ M_{4}$ is of the type $\left(n-s,s\right)$ And $M_{4}\$ is of the type $\left(n-s,\ n-s\right),$ $1\leq s<n,$ that is to say that $A$ has the following form

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

It should also be noted

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

Or $u,\ b_{1}\in\mathbb{R}^{s}$ And $v,\ b_{2}\in\mathbb{R}^{n-s}.$ Thus the system ( 5 ) can be written in the form:

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

Or $in$ And $in$ are the vectors of the unknowns, $\left(u,v\right)\in\mathbb{R}^{s}\times\mathbb{R}^{n-s}.$

To resolve the system ( 6 ) we will apply the following iterative process:

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

This iterative process results as an application of the process ( 3 ) exposed in the first part of this note.

Applying Theorem 1 we will obtain the

Theorem 2 .

If the matrices $M_{1},M_{2},M_{3}$ And $M_{4}\$ satisfy the following inequalities:

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

then the system ( 6 ) has only one solution $\left(\bar{u},\ \bar{v}\right)\in\mathbb{R}^{s}\times\mathbb{R}^{n-s}$ and the method ( 7 ) converges to this solution.

We have thus obtained a new iterative method for solving systems of equations. This method converges under much more general conditions than the simple iteration method or the Gauss-Seidel method. This fact will be illustrated by the following numerical example.

4. Given the system:

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

It should be noted

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

If we consider the uniform norm for these matrices we have

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

We will check whether with these values the conditions ( 8 ) are fulfilled,

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

It follows that conditions ( 8 ) are verified. From Theorem 2 and ( 10 ) it follows that the following iterative process

	$\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}$ arbitrary, converges to the solution of the system ( 5 ).

By performing the calculations we verify all previous theoretical conclusions and after about 40 iterations we obtain the following approximate solution

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

Bibliography

[1]
[2] ^†^†margin: clickable $\rightarrow$ I. Păvăloiu, Observations on solving the systems of equations by iterative methods , Studii şi Cercetări Matematica, 19 (1967) no. 9, 1289–1298 (in Romanian) [English translation of the title: Remarks on solving the systems of equations by iterative methods]

Received on 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

Solving the systems of operator equations by iterative methods

Theorem 1 .

Demonstration.

Noticed .

Theorem 2 .

Bibliography

References

Related Posts