Observaţii asupra rezolvării sistemelor de ecuaţii cu ajutorul procedeelor iterative

(English translation)
Remarks on solving the systems of equations
by iterative methods¹⁾

by
Ion Păvăloiu
(Cluj)

Abstract.

In this paper we give a condition for the convergence of an iterative method of Gauss-Seidel type for solving the system of equations:

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

We then provide some error evaluations in case of exact and approximate computations. We also provide a sufficient condition when the system contains $k$ equations with $k$ unknowns.

¹⁾Communication presented at the second Scientific Session of the Youth, May 20-22, 1966, Bucharest, Romania.

ST. CERC. MAT., TOM. 19, NR. 9, PP. 1289–1298, BUCUREŞTI, 1967.

Introduction

Given the systems of equations:

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

where the functions $\varphi$ and $\psi$ are assumed to satisfy:

a)

The functions $\varphi$ and $\psi$ are defined on the closed domain $\bar{D},$ and transform this domain in itself.
b)

The functions $\varphi$ and $\psi$ are Lipschitz on $\bar{D},$ i.e., there exist $\alpha,$ $\beta,$ $a$ and $b\geq 0$ such that:

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

$\displaystyle\left|\psi\left(x_{1},y_{1}\right)-\psi\left(x_{2},y_{2}\right)\right|$ $\displaystyle\leq a\left|x_{1}-x_{2}\right|+b\left|y_{1}-y_{2}\right|,\qquad% \forall\left(x_{i},y_{i}\right)\in\bar{D},i=1,2.$

We propose the following iterations for solving the system (1). Let $\left(x_{0},y_{0}\right)\in\bar{D}$ be an initial approximation; let:

(2)		$\displaystyle x_{i}$	$\displaystyle=\varphi\left(x_{i-1},y_{i-1}\right)$
	$\displaystyle y_{i}$	$\displaystyle=\psi\left(x_{i},y_{i-1}\right),\qquad i=1,2,3,\ldots,$

Regarding the sequences (2), the following result is well known [1]:

Theorem 1.

If the functions $\varphi$ and $\psi$ satisfy the hypotheses a) and b) with the following restrictions: either $\alpha+\beta<1,$ $a+b<1$ or $a+\alpha<1,$ $b+\beta<1,$ then the sequences (2) converge to the limits $\bar{x}$ and $\bar{y}$ such that the point $M\left(\bar{x},\bar{y}\right)$ is a solution of the system (1), and this solution is unique.

Since Theorem 1 offers sufficient (but not also necessary) conditions for the convergence of the sequences (2), there are cases when the constants $\alpha,$ $\beta,$ $a$ and $b$ do not satisfy the hypotheses of Theorem 1 but still, the sequences (2) converge. In this note we give certain conditions on the constants $\alpha,$ $\beta,$ $a$ and $b$ which strictly include those in Theorem 1; our conditions will contain supplementary cases for which the system (1) admits an unique solution, which can be computed with the aid of the sequences (2).

1. Auxiliary results

Being given two sequences of nonnegative numbers:

(1)		$\displaystyle g$	$\displaystyle=\left\{g_{0},g_{1},\ldots,g_{n},\ldots\right\}$
	$\displaystyle f$	$\displaystyle=\left\{f_{0},f_{1},\ldots,f_{n},\ldots\right\}.$

we assume that the elements obey the conditions:

(2)		$\displaystyle f_{n}$	$\displaystyle\leq\alpha^{\prime}f_{n-1}+\beta^{\prime}g_{n-1}$
	$\displaystyle g_{n}$	$\displaystyle\leq a^{\prime}f_{n}+b^{\prime}g_{n-1},\qquad n=1,2,\ldots,$

with $\alpha^{\prime},$ $\beta^{\prime},$ and $a^{\prime},b^{\prime}$ nonnegative. We attach to the system of recurrent inequalities (2) the following algebraic system in the unknowns $k$ and $h$ :

(3)		$\displaystyle\alpha^{\prime}+\beta^{\prime}h$	$\displaystyle=kh,$
	$\displaystyle a^{\prime}k+b^{\prime}$	$\displaystyle=kh.$

Lemma 2.

The necessary and sufficient condition for the system (3) to admit a solution $\left(h_{1},k_{1}\right),\ h_{1}\geq 0\ k_{1}\geq 0,$ such that

(4)

0\leq h_{1}k_{1}\leq q<1

is that the constants $\alpha^{\prime},$ $\beta^{\prime},$ $a^{\prime}$ and $b^{\prime}$ satisfy the following inequalities:

(5)		$\displaystyle\alpha^{\prime}+b^{\prime}+a^{\prime}\beta^{\prime}$	$\displaystyle<2$
	$\displaystyle\left(1-\alpha^{\prime}\right)\left(1-b^{\prime}\right)$	$\displaystyle>a^{\prime}\beta^{\prime}.$

Proof.

Necessity. From (3) we deduce the following equation in $h$ :

(6)

\beta^{\prime}h^{2}-\left(b^{\prime}+\beta^{\prime}a^{\prime}-\alpha^{\prime}% \right)h-\alpha^{\prime}a^{\prime}=0.

If we add the relation

(7)

p=k\cdot h

to the system (3) and we eliminate $h$ and $k$ from the three obtained equalities and we take into account (6), we obtain the following equation in $p$ :

(8)

F\left(p\right)=p^{2}-\left(b^{\prime}+\beta^{\prime}a^{\prime}+\alpha^{\prime% }\right)p+b^{\prime}\alpha^{\prime}=0.

Again, from the system (3) we deduce the following equation in $k$ :

(9)

a^{\prime}k^{2}-\left(\alpha^{\prime}+\beta^{\prime}a^{\prime}-b^{\prime}% \right)k-\beta^{\prime}b^{\prime}=0.

We notice that the equations (6) and (9) admit real roots, and since the right-hand site terms from both equations are negative, it follows that these equations admit roots of different signs.

Denote by $\left(h_{1},h_{2}\right)$ the roots of (6) and by $\left(k_{1},k_{2}\right)$ the roots of equations (9); then the roots of (8) will be $p_{1}=k_{1}h_{1}$ and $p_{2}=k_{2}h_{2}$ and these roots are always real. If $\left(k_{1},h_{1}\right)$ is the pair of positive solutions of equations (6) and (9), then it is obvious that $p_{1}>p_{2}$ and $p_{2}\geq 0.$ Assume that $p_{1}<1.$ For this inequality to hold, it is necessary that $F\left(1\right)>0$ and $\frac{p_{1}+p_{2}}{2}<1$ which leads to inequalities (5).

Sufficiency. If inequalities (5) are true, it follows that:

	$\displaystyle F\left(0\right)$	$\displaystyle=b^{\prime}\alpha^{\prime}\geq 0$
	$\displaystyle F\left(1\right)$	$\displaystyle=\left(1-\alpha^{\prime}\right)\left(1-b^{\prime}\right)-a^{% \prime}\beta^{\prime}>0$

and

\tfrac{p_{1}+p_{2}}{2}=\tfrac{\left(\alpha^{\prime}+b^{\prime}+a^{\prime}\beta% ^{\prime}\right)}{2}<1

whence $p_{1}<1,$ which finishes the proof. ∎

Lemma 3.

If $\alpha^{\prime},$ $\beta^{\prime},$ $a^{\prime}$ and $b^{\prime}$ satisfy inequalities (5) and the elements of the sequences (1) satisfy inequalities (2), then there exists a nonnegative constant $c_{1}$ for which

(10)		$\displaystyle f_{n}$	$\displaystyle\leq c_{1}h_{1}^{n-1}k_{1}^{n-1}$
	$\displaystyle g_{n}$	$\displaystyle\leq c_{1}h_{1}^{n}k_{1}^{n-1}$

and, moreover, the series $\sum\limits_{i=0}^{\infty}f_{i}$ and $\sum\limits_{i=1}^{\infty}g_{i}$ are convergent.

Proof.

Let $\left(h_{1},k_{1}\right)$ be a solution of the system (3) such that the hypotheses of the lemma are satisfied. Assume that for $n=1$ we have:

(11)		$\displaystyle f_{1}$	$\displaystyle\leq c_{1}$
	$\displaystyle g_{1}$	$\displaystyle\leq c_{1}h_{1}$

One notes without difficulty that for these inequalities to hold it suffices to choose $c_{1}$ such that:

(12)

c_{1}\geq\max\left\{\alpha^{\prime}f_{0}+\beta^{\prime}g_{0},\tfrac{a^{\prime}% f_{1}+b^{\prime}g_{0}}{h_{1}}\right\}.

If the inequalities (11) are satisfied by the chosen $c_{1}$ we assume by induction that:

	$\displaystyle f_{n-1}$	$\displaystyle\leq c_{1}h_{1}^{n-2}k_{1}^{n-2}$
	$\displaystyle g_{n-1}$	$\displaystyle\leq c_{1}h_{1}^{n-1}k_{1}^{n-2}.$

Based on the fact that the system (3) is verified by the solutions $h_{1}$ and $k_{1}$ from (2) we have:

f_{n}\leq c_{1}h_{1}^{n-2}k_{1}^{n-2}\left(\alpha^{\prime}+\beta^{\prime}h_{1}% \right)=c_{1}h_{1}^{n-1}k_{1}^{n-1}

and

g_{n}\leq c_{1}h_{1}^{n-1}k_{1}^{n-2}\left(a^{\prime}k_{1}+b^{\prime}\right)=c% _{1}h_{1}^{n}k_{1}^{n-1}.

According to the induction principle, the first part of the lemma is proved. The second part is obvious, since the terms of the two series are majorized by the terms of two geometrical series with subunitary ratio. ∎

Corollary 4.

If $\alpha^{\prime}+\beta^{\prime}<1$ and $a^{\prime}+b^{\prime}<1$ or $\alpha^{\prime}+a^{\prime}<1$ and $\beta^{\prime}+b^{\prime}<1,$ the inequalities (5) are satisfied.

Lemma 5.

If the elements of the sequence (1) satisfy the following inequalities:

(13)		$\displaystyle f_{n}$	$\displaystyle\leq\alpha^{\prime}f_{n-1}+\beta^{\prime}g_{n-1}+\delta$
	$\displaystyle g_{n}$	$\displaystyle\leq a^{\prime}f_{n}+b^{\prime}g_{n-1}+\delta,$

where $\delta$ is a positive constant and if $\ \alpha^{\prime},\beta^{\prime},a^{\prime}$ and $b^{\prime}\$ satisfy inequalities (5), then there exists a positive constant $c_{1}$ such that

(14)		$\displaystyle f_{n}$	$\displaystyle\leq c_{1}h_{1}^{n-1}k_{1}^{n-1}+\tfrac{\delta}{1-h_{1}k_{1}}$
	$\displaystyle g_{n}$	$\displaystyle\leq c_{1}h_{1}^{n}k_{1}^{n-1}+\tfrac{\delta h_{1}}{1-h_{1}k_{1}}.$

The proof of this lemma is analogous to the proof of Lemma 2.

2. Theorem of existence and uniqueness of solution

Theorem 6.

If the functions $\varphi\$ and $\ \psi\$ satisfy conditions a) and b), and, moreover, the constants $\alpha,\beta,a\$ and $\ b$ are such that the following inequalities are satisfied:

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

then system (1) has a unique solution in $\bar{D},\$ given by the limits of the sequences (2).

Proof.

We shall show first that the sequences (2) are convergent. One notices that the partial sums of the following series

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

coincide with the terms of the sequences (2). If we denote $f_{n-1}=\left|x_{n}-x_{n-1}\right|$ and $\ g_{n-1}=\left|y_{n}-y_{n-1}\right|,\$ then taking into account condition b) and the terms of the sequences (2) then we are lead to 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}.$

By using Lemma 3, it follows that the series (16) are absolutely convergent, and therefore convergent. Therefore there exist two numbers $\bar{x},\bar{y},$ such that

\lim_{n\rightarrow\infty}x_{n}=\bar{x}\ \;\;\text{and}\ \ \ \lim_{n\rightarrow% \infty}y_{n}=\bar{y}.

Taking now into account that functions $\varphi\$ and $\ \psi$ satisfy condition b), it follows that they are continuous on $\bar{D},$ and passing to the limit in the equalities

	$\displaystyle x_{n+1}$	$\displaystyle=\varphi\left(x_{n},y_{n}\right)$
	$\displaystyle y_{n+1}$	$\displaystyle=\psi\left(x_{n+1},y_{n}\right)$

we get

\bar{x}=\varphi\left(\bar{x},\bar{y}\right)

and

\bar{y}=\psi\left(\bar{x},\bar{y}\right)

whence it follows that $\bar{x}\$ and $\ \bar{y}$ satisfy system (1). Let us now show that the obtained solution is the unique solution of the system (1) in the domain $\bar{D}$ . Assume that, besides the solution $\left(\bar{x},\bar{y}\right)\$ the system admits another solution, $\ \left(\bar{x}_{1},\bar{y}_{1}\right)$ which does not coincide with the previous one. We shall show first that if $\left(\bar{x},\bar{y}\right)$ is a solution of (1) and $\left(\bar{x}_{0},\bar{y}_{0}\right)\$ is an arbitrary element of $\bar{D}$ , then there exist two sequences

	$\displaystyle x_{1}$	$\displaystyle=\varphi\left(x_{0},y_{0}\right),\ldots,x_{n}=\varphi\left(x_{n-1% },y_{n-1}\right),\ldots$
	$\displaystyle y_{1}$	$\displaystyle=\varphi\left(x_{1},y_{0}\right),\ldots,y_{n}=\varphi\left(x_{n},% y_{n-1}\right),\ldots$

such that

(17)		$\displaystyle\lim_{n\rightarrow\infty}\left\|\bar{x}-x_{n}\right\|$	$\displaystyle=0$
	$\displaystyle\lim_{n\rightarrow\infty}\left\|y-\bar{y}_{n}\right\|$	$\displaystyle=0.$

Indeed, from the fact that $\left(\bar{x},\bar{y}\right)$ satisfy (1) and if we take into account condition b) we get the following inequalities

	$\displaystyle\left\|\bar{x}-x_{n}\right\|$	$\displaystyle\leq\alpha\left\|\bar{x}-x_{n-1}\right\|+\beta\left\|\bar{y}-y_{n-1}\right\|$
	$\displaystyle\left\|\bar{y}-y_{n}\right\|$	$\displaystyle\leq a\left(\bar{x}-x_{n}\right)+b\left\|\bar{y}-y_{n-1}\right\|,$

whence, taking into account Lemma 2 it follows that the inequalities (17) are true. If $\left(x_{0},y_{0}\right)\$ and $\ \left(x_{0}^{\prime},y_{0}^{\prime}\right)\$ are distinct points from $\ \bar{D}$ and

	$\displaystyle x_{n}$	$\displaystyle=\varphi\left(x_{n-1},y_{n-1}\right)\ \ \ \ \ \ \ \ \ \ \ \ \ \ % \ \ \ \ \ \ \ \ \ \ x_{n}^{\prime}=\varphi\left(x_{n-1}^{\prime},\ y_{n-1}^{% \prime}\right)$
	$\displaystyle y_{n}$	$\displaystyle=\psi\left(x_{n},y_{n-1}\right),\ n=1,2,\ldots,\ \ \ \ y_{n}^{% \prime}=\psi\left(x_{n}^{\prime},y_{n-1}^{\prime}\right),\ \ n=1,2,\ldots$

are the sequences generated by them, we shall show that

(18)		$\displaystyle\lim_{n\rightarrow\infty}\left\|x_{n}-x_{n}^{\prime}\right\|$	$\displaystyle=0$
	$\displaystyle\lim_{n\rightarrow\infty}\left\|y_{n}-y_{n}^{\prime}\right\|$	$\displaystyle=0.$

Indeed, we have

	$\displaystyle\left\|x_{n}-y_{n}^{\prime}\right\|$	$\displaystyle\leq\alpha\left\|x_{n-1}-x_{n-1}^{\prime}\right\|+\beta\left\|y_{n-1% }-y_{n-1}^{\prime}\right\|$
	$\displaystyle\left\|y_{n}-y_{n}^{\prime}\right\|$	$\displaystyle\leq a\left\|x_{n}-x_{n}^{\prime}\right\|+b\left\|y_{n-1}-y_{n-1}^{% \prime}\right\|.$

Then Lemma 2 imply the inequalities (18). The above relations imply that if $\{x_{n}\}$ and $\ \{y_{n}\}$ are two sequences such that

	$\displaystyle\lim_{n\rightarrow\infty}x_{n}$	$\displaystyle=\bar{x}$
	$\displaystyle\lim_{n\rightarrow\infty}y_{n}$	$\displaystyle=\bar{y}$

and $\{x_{n}^{\prime}\}$ and $\{y_{n}^{\prime}\}$ are two sequences such that

	$\displaystyle\lim x_{n}^{\prime}$	$\displaystyle=\bar{x}_{1},$
	$\displaystyle\lim y_{1}^{\prime}$	$\displaystyle=\bar{y}_{1},$

then we have

	$\displaystyle\left\|\bar{x}-\bar{x}_{1}\right\|$	$\displaystyle\leq\left\|\bar{x}-x_{n}\right\|+\left\|x_{n}-x_{n}^{\prime}\right\|+% \left\|x_{n}^{\prime}-\bar{x}_{1}\right\|$
	$\displaystyle\left\|\bar{y}-\bar{y}_{1}\right\|$	$\displaystyle\leq\left\|\bar{y}-y_{n}\right\|+\left\|y_{n}-y_{n}^{\prime}\right\|+% \left\|y_{n}^{\prime}-\bar{y}_{1}\right\|.$

These inequalities are true for all $n .$ Passing to limit as $n\rightarrow\infty$ and taking into account the above remarks, we have

\bar{x}=\bar{x}_{1}\ \text{and }\ \ \bar{y}=\bar{y}_{1}

and therefore the system has a unique solution. ∎

Corollary 7.

From the consequence of Lemma 3 it follows that the conditions from Theorem 1 are contained also in Theorem 6, but Theorem 6 contains other cases, which are not contained in Theorem 1. We shall illustrate this in the following example.

Example 1.

Given the linear system

	$\displaystyle x$	$\displaystyle=0.1x+8y-0,6$
	$\displaystyle y$	$\displaystyle=0.05x+0.45y-0.5.$

Theorem 1 can say nothing about this, while if we apply Theorem 6 we obtain the system

	$\displaystyle 0.1+8h$	$\displaystyle=hk$
	$\displaystyle 0.05\ k+0.45$	$\displaystyle=hk$

which can be seen to satisfy (5). From here we can draw the conclusion that the procedure (2) applied to the above system converges to the solution of this system. Starting from $x_{0}=0$ and $y_{0}=0$ in approximately 150 iterations we obtain the approximate solutions $\ x=-45.578936,\ y=-5.052631.$

3. The evaluation of errors in the exact case

In order to evaluate the errors we assume that one can exactly compute the values of $\varphi$ and $\psi\$ at any point in $\ \bar{D}$ . Consider

	$\displaystyle\left\|x_{n+p}-x_{n}\right\|$	$\displaystyle\leq\left\|x_{n+p}-x_{n+p-1}\right\|+\cdots+\left\|x_{n+1}-x_{n}\right\|$
		$\displaystyle\leq c_{1}\left(h_{1}^{n+p-2}k_{1}^{n+p-2}+\cdots+h_{1}^{n-1}k_{1% }^{n-1}\right),$

whence, passing to limit as $p\rightarrow\infty,$ one obtains

(19)

\left|\bar{x}-x_{n}\right|\leq c_{1}\tfrac{h_{1}^{n-1}k_{1}^{n-1}}{1-h_{1}k_{1% }}.

Analogously, we obtain for the second solution the following evaluation:

(20)

\left|\bar{y}-y_{n}\right|\leq\tfrac{c_{1}h_{1}^{n}k_{1}^{n-1}}{1-h_{1}k_{1}}.

4. The evaluation of errors in the approximate case

We consider here that the values of the functions $\varphi\$ and $\ \psi\$ cannot be computed at the points in $\ \bar{D}$ , but we have the possibility to compute the exact values of two functions $\ \varphi_{1}\$ and $\ \psi_{1}\$ which are defined on the domain $\bar{D},\$ and the functions $\varphi_{1}\$ and $\ \psi_{1}$ transform this domain in itself. We also assume that there exists a positive number $\delta$ such that

(21)		$\displaystyle\left\|\varphi\left(x,y\right)-\varphi_{1}\left(x,y\right)\right\|$	$\displaystyle\leq\delta$
	$\displaystyle\left\|\psi\left(x,y\right)-\psi_{1}\left(x,y\right)\right\|$	$\displaystyle\leq\delta,\qquad\text{for all }\left(x,y\right)\in D.$

Instead of the system (1) we consider now an approximate one

(22)		$\displaystyle x^{\ast}$	$\displaystyle=\varphi_{1}\left(x^{\ast},y^{\ast}\right)$
	$\displaystyle y^{\ast}$	$\displaystyle=\psi_{1}\left(x^{\ast},y^{\ast}\right).$

Regarding the functions $\varphi_{1}\$ and $\ \psi_{1}$ we have assumed just that they obey (21), and we do not know whether the Gauss-Seidel method applied to it converges. Also, if we intend to stop the iterations when

(23)		$\displaystyle\left\|x_{n+1}^{\ast}-x_{n}^{\ast}\right\|$	$\displaystyle\leq\varepsilon$
	$\displaystyle\left\|y_{n+1}^{\ast}-y_{n}^{\ast}\right\|$	$\displaystyle\leq\varepsilon$

we have no guarantee that for arbitrary $\varepsilon\$ the inequalities (23) can be satisfied. Indeed, considering the iterations

	$\displaystyle x_{n+1}^{\ast}$	$\displaystyle=\varphi_{1}\left(x_{n}^{\ast},y_{n}^{\ast}\right)$
	$\displaystyle y_{n+1}^{\ast}$	$\displaystyle=\psi_{1}\left(x_{n+1}^{\ast},y_{n}^{\ast}\right).$

We have

\left|x_{n+1}^{\ast}-x_{n}^{\ast}\right|\leq\alpha\left|x_{n}^{\ast}-x_{n-1}^{% \ast}\right|+\beta\left|y_{n}^{\ast}-y_{n-1}^{\ast}\right|+2\delta

and

\left|y_{n+1}^{\ast}-y_{n}^{\ast}\right|\leq a\left|x_{n+1}^{\ast}-x_{n}^{\ast% }\right|+b\left|y_{n}^{\ast}-y_{n-1}^{\ast}\right|+2\delta.

If we take into account Lemma 5 we get

(24)		$\displaystyle\left\|x_{n+1}^{\ast}-x_{n}^{\ast}\right\|$	$\displaystyle\leq c_{1}h_{1}^{n-1}k_{1}^{n-1}+\tfrac{2\delta}{1-h_{1}k_{1}}$
	$\displaystyle\left\|y_{n+1}^{\ast}-y_{n}^{\ast}\right\|$	$\displaystyle\leq c_{1}h_{1}^{n}k_{1}^{n-1}+\tfrac{2\delta h_{1}}{1-h_{1}k_{1}},$

whence it follows that if we choose $\varepsilon$ such that

(25)

\varepsilon>\max\left\{\tfrac{2\delta}{1-h_{1}k_{1}},\tfrac{2\delta h_{1}}{1-h% _{1}k_{1}}\right\},

at a certain step $n^{\prime}\$ the inequalities (23) will be satisfied. Let now $\varepsilon$ be chosen as in (25); then there exists $n^{\prime}$ such that

(26)		$\displaystyle\left\|x_{n^{\prime}+1}^{\ast}-x_{n^{\prime}}^{\ast}\right\|$	$\displaystyle\leq\varepsilon$
	$\displaystyle\left\|y_{n^{\prime}+1}^{\ast}-y_{n^{\prime}}^{\ast}\right\|$	$\displaystyle\leq\varepsilon;$

we have

\left|\bar{x}-x_{n^{\prime}+1}^{\ast}\right|\leq\alpha\left|\bar{x}-x_{n^{% \prime}}^{\ast}\right|+\beta\left|\bar{y}-y_{n^{\prime}}^{\ast}\right|+\delta.

If we take into account that for the system (3) to admit a solution $\left(h_{1},k_{1}\right)$ for which

0\leq h_{1}k_{1}\leq q<1,

it is necessary that $\ \alpha<1$ and $b<1$ . Then we have

(27)

\left|\bar{x}-x_{n^{\prime}+1}^{\ast}\right|\leq\tfrac{\alpha\varepsilon+% \delta+\beta(\bar{y}-y_{n^{\prime}}^{\ast})}{1-\alpha}.

Analogously, we find for $\left|\bar{y}-y_{n^{\prime}+1}^{\ast}\right|$ the following evaluation

(28)

\left|\bar{y}-y_{n^{\prime}+1}^{\ast}\right|\leq\tfrac{b\varepsilon+\delta+a% \left|\bar{x}-x_{n+1}^{\ast}\right|}{1-b}.

From (27) and (28) we obtain

(29)		$\displaystyle\left\|\bar{x}-x_{n^{\prime}+1}^{\ast}\right\|$	$\displaystyle\leq\tfrac{\left(\alpha+\beta\right)\varepsilon+\delta}{1-\alpha}% +\tfrac{\beta}{1-\alpha}\left\|\bar{y}-y_{n^{\prime}+1}^{\ast}\right\|$
	$\displaystyle\left\|\bar{y}-y_{n^{\prime}+1}^{\ast}\right\|$	$\displaystyle\leq\tfrac{b\varepsilon+\delta}{1-b}+\tfrac{a}{1-b}\left\|\bar{x}-% x_{n^{\prime}+1}^{\ast}\right\|.$

From the above inequalities, taking into account (5) we deduce

(30)		$\displaystyle\left\|\bar{x}-x_{n^{\prime}+1}^{\ast}\right\|$	$\displaystyle\leq\tfrac{\left(1-b\right)\left[\left(\alpha+\beta\right)% \varepsilon+\delta\right]+\beta\left(b\varepsilon+\delta\right)}{\left(1-% \alpha\right)\left(1-b\right)-\beta a}$
	$\displaystyle\left\|\bar{y}-y_{n^{\prime}+1}^{\ast}\right\|$	$\displaystyle\leq\tfrac{\left(1-\alpha\right)\left[b\varepsilon+\delta\right]+% a\left[\left(\alpha+\beta\right)\varepsilon+\delta\right]}{\left(1-\alpha% \right)\left(1-b\right)-\beta a}.$

5. A generalization

Consider now a system of $k\$ equations in $k$ unknowns of the form

(31)

x_{i}=\varphi_{i}\left(x_{1},x_{2},\ldots,x_{k}\right),\qquad i=1,2,\ldots,k.

Regarding the functions $\varphi_{i},\ i=1,2,\ldots,k$ , we consider assumptions similar to those considered for the system (1):

a^′)

The functions $\varphi_{i},\ i=1,2,\ldots,k$ , transform the domain $\bar{D},\$ of the space $E_{k}$ , in itself;
b^′)

There exists a matrix with nonnegative constants, $\beta=\left(\beta_{i}^{j}\right),\ \ i,j=1,2,\ldots,k,$ such that

$\left|\varphi_{i}\left(x_{1},x_{2},\ldots,x_{k}\right)-\varphi_{i}\left(x_{1}^% {\prime},x_{2}^{\prime},\ldots,x_{k}^{\prime}\right)\right|\leq\sum_{j=1}^{k}% \beta_{i}^{j}\left|x_{j}-x_{j}^{\prime}\right|,\qquad i=1,2,\ldots,k$

for all $\left(x_{1},x_{2},\ldots,x_{k}\right)\$ and $x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{k}^{\prime}$ are two points from $\bar{D}$ .

We obtain the following result.

Theorem 8.

If the functions $\varphi_{i},$ $i=1,2,\ldots,k,\$ satisfy conditions a’), b’) and the elements of the matrix $\beta$ are such that the system

	$\displaystyle\beta_{1}^{1}+\beta_{2}^{1}h_{1}+\ldots+\beta_{k}^{1}h_{1}h_{2}% \ldots h_{k-1}=h_{1}h_{2}\ldots h_{k}$
	$\displaystyle..............................................$
	$\displaystyle\beta_{1}^{i}h_{i}h_{i+1}\ldots h_{k}+\beta_{2}^{i}h_{1}h_{i}% \ldots h_{k}+\ldots+\beta_{i}^{i}+\beta_{i+1}^{i}h_{i}+\ldots+\beta_{k}^{i}h_{% i}h_{i+1}\ldots h_{k-1}=h_{1}h_{2}\ldots h_{k}$
	$\displaystyle..............................................$
	$\displaystyle\beta_{1}^{k}h_{k}+\beta_{2}^{k}h_{1}h_{k}+\ldots+\beta_{k-1}^{k}% h_{1}h_{2}\ldots h_{k-2}h_{k}+\beta_{k}^{k}=h_{1}h_{2}\ldots h_{k}$

is compatible and has a solution $\left(h_{1}^{0},h_{2}^{0},\ldots,h_{k}^{0}\right),$ $h_{i}\geq 0$ $i=1,2,\ldots,k$ for which

0\leq h_{1}^{0}h_{2}^{0}\ldots h_{k}^{0}\leq q<1,

then the system (31) has a unique solution in the domain $\bar{D},$ which can be obtained from the iterations

x_{i}^{\left(n\right)}=\varphi_{i}\left(x_{1}^{\left(n\right)},x_{2}^{\left(n% \right)},\ldots,x_{i-1}^{\left(n\right)},x_{i}^{(n-1)},\ldots,-x_{k}^{(n-1)}% \right),\ i=1,2,\ldots,k;\ n=1,2,3,\ldots,

for any initial approximation $\left(x_{1}^{0},x_{2}^{0},\ldots,x_{k}^{0}\right)\in D$ .

The proof of this result is obtained analogously to the proof of Theorem 6.

Received by the editors on March 23, 1967.

Institutul de Calcul al Academiei Republicii Socialiste Romania - Filiala Cluj

References

[1] Demidovici, B.P., Maron, I.A., Osnovi vacislietel’noi matematiki, Gas. izd. fiz. mat. lit., Moskva, 1960, pp. 148–151.
[2] J.F. Traub, Iterative Methods for the Solution of Equations. Prentice Hall, Inc., Englewwod Cliffs, N.J., 1964, 99.38-39.
[3] Ostrowski, A.N., Resenie uravnenii i sistem uravnenii, Izd. inostr. lit., Moskva, 1963, pp. 83–94.
[4] I. Păvăloiu, On some recurrent inequalities and some of their applications, Communication at the Scientific Session of the Institute for Mining Petroşani, February 7–10, 1966.

	$\displaystyle\left\|\bar{x}-x_{n}\right\|$	$\displaystyle\leq\alpha\left\|\bar{x}-x_{n-1}\right\|+\beta\left\|\bar{y}-y_{n-1}\right\|$
	$\displaystyle\left\|\bar{y}-y_{n}\right\|$	$\displaystyle\leq a\left(\bar{x}-x_{n}\right)+b\left\|\bar{y}-y_{n-1}\right\|,$

	$\displaystyle\left\|x_{n}-y_{n}^{\prime}\right\|$	$\displaystyle\leq\alpha\left\|x_{n-1}-x_{n-1}^{\prime}\right\|+\beta\left\|y_{n-1% }-y_{n-1}^{\prime}\right\|$
	$\displaystyle\left\|y_{n}-y_{n}^{\prime}\right\|$	$\displaystyle\leq a\left\|x_{n}-x_{n}^{\prime}\right\|+b\left\|y_{n-1}-y_{n-1}^{% \prime}\right\|.$

	$\displaystyle\left\|\bar{x}-\bar{x}_{1}\right\|$	$\displaystyle\leq\left\|\bar{x}-x_{n}\right\|+\left\|x_{n}-x_{n}^{\prime}\right\|+% \left\|x_{n}^{\prime}-\bar{x}_{1}\right\|$
	$\displaystyle\left\|\bar{y}-\bar{y}_{1}\right\|$	$\displaystyle\leq\left\|\bar{y}-y_{n}\right\|+\left\|y_{n}-y_{n}^{\prime}\right\|+% \left\|y_{n}^{\prime}-\bar{y}_{1}\right\|.$

(29)		$\displaystyle\left\|\bar{x}-x_{n^{\prime}+1}^{\ast}\right\|$	$\displaystyle\leq\tfrac{\left(\alpha+\beta\right)\varepsilon+\delta}{1-\alpha}% +\tfrac{\beta}{1-\alpha}\left\|\bar{y}-y_{n^{\prime}+1}^{\ast}\right\|$
	$\displaystyle\left\|\bar{y}-y_{n^{\prime}+1}^{\ast}\right\|$	$\displaystyle\leq\tfrac{b\varepsilon+\delta}{1-b}+\tfrac{a}{1-b}\left\|\bar{x}-% x_{n^{\prime}+1}^{\ast}\right\|.$

Remarks on solving the systems of equations by iterative methods

Abstract

Authors

Title

Original Title (in Romanian)

English Translation of the Title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

MSC

MR

ZBL

Paper (preprint) in HTML form

Observaţii asupra rezolvării sistemelor de ecuaţii cu ajutorul procedeelor iterative

(English translation)
Remarks on solving the systems of equations
by iterative methods¹⁾

Abstract.

Introduction

Theorem 1.

1. Auxiliary results

Lemma 2.

Proof.

Lemma 3.

Proof.

Corollary 4.

Lemma 5.

2. Theorem of existence and uniqueness of solution

Theorem 6.

Proof.

Corollary 7.

Example 1.

3. The evaluation of errors in the exact case

4. The evaluation of errors in the approximate case

5. A generalization

Theorem 8.

References

References

Related Posts

	$\displaystyle\left\|\varphi\left(x_{1},y_{1}\right)-\varphi\left(x_{2},y_{2}% \right)\right\|$	$\displaystyle\leq\alpha\left\|x_{1}-x_{2}\right\|+\beta\left\|y_{1}-y_{2}\right\|$
	$\displaystyle\left\|\psi\left(x_{1},y_{1}\right)-\psi\left(x_{2},y_{2}\right)\right\|$	$\displaystyle\leq a\left\|x_{1}-x_{2}\right\|+b\left\|y_{1}-y_{2}\right\|,\qquad% \forall\left(x_{i},y_{i}\right)\in\bar{D},i=1,2.$

Remarks on solving the systems of equations by iterative methods

Abstract

Authors

Title

Original Title (in Romanian)

English Translation of the Title

Keywords

PDF

Cite this paper as:

About this paper

Journal

Publisher Name

DOI

MSC

MR

ZBL

Paper (preprint) in HTML form

Observaţii asupra rezolvării sistemelor de ecuaţii cu ajutorul procedeelor iterative (English translation) Remarks on solving the systems of equations by iterative methods1)

Abstract.

Introduction

Theorem 1.

1. Auxiliary results

Lemma 2.

Proof.

Lemma 3.

Proof.

Corollary 4.

Lemma 5.

2. Theorem of existence and uniqueness of solution

Theorem 6.

Proof.

Corollary 7.

Example 1.

3. The evaluation of errors in the exact case

4. The evaluation of errors in the approximate case

5. A generalization

Theorem 8.

References

References

Related Posts

Observaţii asupra rezolvării sistemelor de ecuaţii cu ajutorul procedeelor iterative

(English translation)
Remarks on solving the systems of equations
by iterative methods¹⁾