MATHEMATICA - REVUE D'ANALYSE
NUMERIQUE ET DE THÉORIE
DE LAPPRROXIMATION

LA THÉORIE DE L'APPROXIMATION

TOME 9
${\mathbf{N}}^{\mathbf{0}}$${\mathbf{N}}^{\mathbf{0}}$N^(0)\mathbf{N}^{\mathbf{0}}${\mathbf{N}}^{\mathbf{0}}$ 1
1980

MATHEMATICA - REVUE D'ANALYSE
NUMÉRIQUE ET DE THÉORIE
DE L'APPROXIMATION

L'ANALYSE NUMÉRIQUE
ET

Tome 9, ${\mathrm{N}}^{0}1$${\mathrm{N}}^{0}1$N^(0)1\mathrm{N}^{0} 1${\mathrm{N}}^{0}1$
1980

OlegArąmă (sécretaire de rédaction), Gheorghe Coman, Sever Groze, Adolf Haimovici, Acad. Caius Iacob (rédacteur en chef), Dumitru V. Ionescu, Carol Kalik, Arpád Pál, Elena Popoviciu (rédacteur en chef adjoint), Ioan A. Rus, Dimitrie Stancu, Acad. Nicolae Teodorescu.

G. Avdelas, A. Hadjidimos and A. Yeyios, Some Theoretical and Computational Results Concerning the Accelerated Overrelaxation (AOR) Method

Wolfgang W. Breckner, Eine Verallgemeinerung des Prinzips der Gleichmässigen Beschränktheit
S. Cobzaş, Non Convex Optimization Problems on Weakly Compact Subsets of Banach Spaces . . .

Adrian Dadu, Une méthode d'accélération de la convergence des séries trigonométriques
F. J. Delvos and H. Posdorf, A Boolean Method in Bivariate Interpolation
C. Kalik, Un théorème d'existence pour une inéquation variationnelle

Mircea Ivan, Différences divisées généralisées et fonctionnelles de forme simple
I. Kolumbán. Das Prinzip der Kondensation der Singularitäten präkonvexer Funktionen

Walter Kölnnen, Einige Saturationssätze für n-parametrige Halbgruppen von Operatoren

Octavian Lipovan, Sur l'intégrabilité des fonctions multivoques 75
Alexandru Lupaş, Numerical Integration by means of Gauss-Legendre Formula
C. Mustăta, The Extension of Starshaped Bounded Lipschitz Functions 93
Andrei Ney, La $\mathrm{\Delta }$$\mathrm{\Delta }$Delta\Delta$\mathrm{\Delta }$-métrique, instrument d'approximation dans un clan (I)
Elena Popoviciu, Sur un théorème de la moyenne ..... 107
Radu Precup, Le théorème des contractions dans des espaces syntopogènes ..... 113
I. Ras a, On Some Results of C. A. Micchelli ..... 125
Stefan Tigan, Remarques sur certains problèmes de programmation psendo-linéaire par morceaux ..... 129
Ch. Ullrich, Intervallrechnung über vollständig schwachgeordneten Vektoiden133

Very recently HADJIDIMOS (1978) has introduced a new iterative method for the numerical solution of a linear system $Ax=b$$Ax=b$Ax=bA x=b$Ax=b$, where $A$$A$AA$A$ is an $n\times n$$n\times n$n xx nn \times n$n\times n$ known matrix, $x$$x$xx$x$ an unknown $n$$n$nn$n$-dimensional vector and $b$$b$bb$b$ a known vector of the same dimension. By splitting $A$$A$AA$A$ into the sum $D-A_L-$$D-A_L-$D-A_(L)-D-A_{L}-$D-A_L-$ - $A_U$$A_U$A_(U)A_{U}$A_U$, where $D$$D$DD$D$ is the diagonal part of $A$$A$AA$A$ and $A_L$$A_L$A_(L)A_{L}$A_L$ and $A_U$$A_U$A_(U)A_{U}$A_U$ the strictly lower and upper triangular parts of $A$$A$AA$A$ multiplied by -1 and assuming that det $(D)\ne 0$$(D)\ne 0$(D)!=0(D) \neq 0$(D)\ne 0$, the corresponding AOR scheme has the following form:
(1.1) $(I-vL)x^{(n+1)}=[(1-\omega )I+(\omega -r)L+\omega U]x^{(n)}+\omega c\mid n=0,1,2,\dots$$(I-vL)x^{(n+1)}=[(1-\omega )I+(\omega -r)L+\omega U]x^{(n)}+\omega c\mid n=0,1,2,\dots$(I-vL)x^((n+1))=[(1-omega)I+(omega-r)L+omega U]x^((n))+omega c∣n=0,1,2,dots(I-v L) x^{(n+1)}=[(1-\omega) I+(\omega-r) L+\omega U] x^{(n)}+\omega c \mid n=0,1,2, \ldots$(I-vL)x^{(n+1)}=[(1-\omega )I+(\omega -r)L+\omega U]x^{(n)}+\omega c\mid n=0,1,2,\dots$
where $L=D^{-1}{A}_L,U=D^{-1}{A}_U,c=D^{-1}b,I$$L=D^{-1}{A}_L,U=D^{-1}{A}_U,c=D^{-1}b,I$L=D^(-1)A_(L),U=D^(-1)A_(U),c=D^(-1)b,IL=D^{-1} A_{L}, U=D^{-1} A_{U}, c=D^{-1} b, I$L=D^{-1}{A}_L,U=D^{-1}{A}_U,c=D^{-1}b,I$ is the unit matrix of order $n,r$$n,r$n,rn, r$n,r$ is the acceleration parameter, $\omega \ne 0$$\omega \ne 0$omega!=0\omega \neq 0$\omega \ne 0$ is the overrelaxation parameter and $x^{(0)}$$x^{(0)}$x^((0))x^{(0)}$x^{(0)}$ arbitrary. The iterative matrix of scheme (1.1) is given by

This new two-parameter method is obviously a generalization of the sor method (since for $r=\omega$$r=\omega$r=omegar=\omega$r=\omega$ AOR coincides with SOR) and it should be noted that for $r\ne 0$$r\ne 0$r!=0r \neq 0$r\ne 0$ the AOR method is the Extrapolated SOR (ESOR) method with overrelaxation parameter $r$$r$rr$r$ and extrapolation one $s=\omega /r$$s=\omega /r$s=omega//rs=\omega / r$s=\omega /r$. Without loss of generality we shall assume throughout this paper that $A\equiv I-L-U$$A\equiv I-L-U$A-=I-L-UA \equiv I-L-U$A\equiv I-L-U$ since by premultiplication by $D^{-1}$$D^{-1}$D^(-1)D^{-1}$D^{-1}$ the new coefficient matrix $A$$A$AA$A$ of the original system will have this form.

The purpose of this paper is to present some further basic results concerning the AOR method when the matrix $A$$A$AA$A$ is
i) An irreducible with weak diagonal dominance matrix
ii) A positive definite matrix
iii) An $L$$L$LL$L$-matrix and
iv) An $M$$M$MM$M$-matrix
and also to show by mumerical examples its superiority compared with the SOR method.

Here we state and prove a basic theorem which helps us to extend and improwe the results of hadjidimos (1978).
theorem 1. Let $A$$A$AA$A$ be a nonsingular matrix. If the sor method with overrelaxation parameter $r$$r$rr$r$ converges for $0<\alpha \leqq r\leqq \beta <2$$0<\alpha \leqq r\leqq \beta <2$0 < alpha <= r <= beta < 20<\alpha \leqq r \leqq \beta<2$0<\alpha \leqq r\leqq \beta <2$, then the aor method converges for all $r$$r$rr$r$ and $s$$s$ss$s$ such that $\alpha \leqq r\leqq \beta$$\alpha \leqq r\leqq \beta$alpha <= r <= beta\alpha \leqq r \leqq \beta$\alpha \leqq r\leqq \beta$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$ where $s=\omega /t$$s=\omega /t$s=omega//ts=\omega / t$s=\omega /t$.

Proof. By relationship (2.7) (hadjidimos, 1978) the eigenvalues ${\lambda }_i$${\lambda }_i$lambda_(i)\lambda_{i}${\lambda }_i$ of the AOR method ( $r\ne 0$$r\ne 0$r!=0r \neq 0$r\ne 0$ ) are given in terms of the eigenvalues $v_i$$v_i$v_(i)v_{i}$v_i$ of the sor metod by the expressions ${\lambda }_i=s{\nu }_i+1-s$${\lambda }_i=s{\nu }_i+1-s$lambda_(i)=snu_(i)+1-s\lambda_{i}=s \nu_{i}+1-s${\lambda }_i=s{\nu }_i+1-s$ where $s=\omega /r$$s=\omega /r$s=omega//rs=\omega / r$s=\omega /r$. If ${\nu }_i==\rho e^{i\theta }$${\nu }_i==\rho e^{i\theta }$nu_(i)==rhoe^(i theta)\nu_{i}= =\rho e^{i \theta}${\nu }_i==\rho e^{i\theta }$ with $0\leqq \rho <1$$0\leqq \rho <1$0 <= rho < 10 \leqq \rho<1$0\leqq \rho <1$, then for $\alpha \leqq r\leqq \beta$$\alpha \leqq r\leqq \beta$alpha <= r <= beta\alpha \leqq r \leqq \beta$\alpha \leqq r\leqq \beta$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$ we have that

and the AOR method converges for all $\alpha \leqq r\leqq \beta$$\alpha \leqq r\leqq \beta$alpha <= r <= beta\alpha \leqq r \leqq \beta$\alpha \leqq r\leqq \beta$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$. In what follows we examine the extensions concerning the theory of aor method as was given by HADJIDIMOS (1978) in view of the theorem which has just been proved.

theorem 1. Let $A$$A$AA$A$ be an irreducible matrix with weak diagonal dominance. Then the AOR method ( $r\ne 0$$r\ne 0$r!=0r \neq 0$r\ne 0$ ) converges for all $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$ and $0<<s\leqq 1$$0<<s\leqq 1$0<<s <= 10< <s \leqq 1$0<<s\leqq 1$.

Proof. In all basic books (see varga, 1962; wachspress, 1966 ; voung, 1971) a classical theorem concerning the sor method is presented stating that the SOR method converges for $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$. Thus by Theorem 2.1 above we conclude that the AOR method converges for all $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$. (i.e. $0<\omega \leqq r\leqq 1$$0<\omega \leqq r\leqq 1$0 < omega <= r <= 10<\omega \leqq r \leqq 1$0<\omega \leqq r\leqq 1$ ). This is a corollary to the theorem of section 3 (hadjidimos, 1978) according to which the aor method converges for all $0\leqq r\leqq 1$$0\leqq r\leqq 1$0 <= r <= 10 \leqq r \leqq 1$0\leqq r\leqq 1$ and $0<\omega \leqq 1$$0<\omega \leqq 1$0 < omega <= 10<\omega \leqq 1$0<\omega \leqq 1$.

theorem 1. Let $A$$A$AA$A$ be a positive definite (real) matrix. Then the aor method converges for $0<\omega \leqq \gamma \leqq 2(\omega \ne 2)$$0<\omega \leqq \gamma \leqq 2(\omega \ne 2)$0 < omega <= gamma <= 2(omega!=2)0<\omega \leqq \gamma \leqq 2(\omega \neq 2)$0<\omega \leqq \gamma \leqq 2(\omega \ne 2)$.

Proof. Since $A=I-L-U$$A=I-L-U$A=I-L-UA=I-L-U$A=I-L-U$ we have $L=U^T$$L=U^T$L=U^(T)L=U^{T}$L=U^T$ and also that $y^{H}Ay>>0$$y^{H}Ay>>0$y^(H)Ay>>0y^{H} A y> >0$y^{H}Ay>>0$ for every complex $n$$n$nn$n$-dimensional vector $y$$y$yy$y$ with $y^H$$y^H$y^(H)y^{H}$y^H$ denoting the conjugate transpose of $y$$y$yy$y$. If $\lambda$$\lambda$lambda\lambda$\lambda$ is an eigenvalue of $L_{r,\omega }$$L_{r,\omega }$L_(r,omega)L_{r, \omega}$L_{r,\omega }$, then for some $\nu \ne 0$$\nu \ne 0$nu!=0\nu \neq 0$\nu \ne 0$ we shall have $L_{y,\omega }\nu =\lambda \nu$$L_{y,\omega }\nu =\lambda \nu$L_(y,omega)nu=lambda nuL_{y, \omega} \nu=\lambda \nu$L_{y,\omega }\nu =\lambda \nu$ and hence

Multiplying both sides on the left by ${\nu }^H$${\nu }^H$nu^(H)\nu^{H}${\nu }^H$ and solving for $\lambda$$\lambda$lambda\lambda$\lambda$, assuming for the moment that $v^H(I-rL)v\ne 0$$v^H(I-rL)v\ne 0$v^(H)(I-rL)v!=0v^{H}(I-r L) v \neq 0$v^H(I-rL)v\ne 0$, we obtain

Since $L=U^T$$L=U^T$L=U^(T)L=U^{T}$L=U^T$ we have

where ${\nu }^{\ast }$${\nu }^{\ast }$nu^(**)\nu^{*}${\nu }^{\ast }$ is the complex conjugate matrix of $\nu$$\nu$nu\nu$\nu$.
Thus if we let

If we put $z=\alpha +\beta i$$z=\alpha +\beta i$z=alpha+beta iz=\alpha+\beta i$z=\alpha +\beta i$ where $\alpha$$\alpha$alpha\alpha$\alpha$ and $\beta$$\beta$beta\beta$\beta$ are real we have

To prove the validity of the theorem it is sufficient to show that $|\lambda |<1$$|\lambda |<1$|lambda| < 1|\lambda|<1$|\lambda |<1$ for $0<\omega \leqq r\leqq 2(\omega \ne 2)$$0<\omega \leqq r\leqq 2(\omega \ne 2)$0 < omega <= r <= 2(omega!=2)0<\omega \leqq r \leqq 2(\omega \neq 2)$0<\omega \leqq r\leqq 2(\omega \ne 2)$ or equivalently that

Since $\omega >0$$\omega >0$omega > 0\omega>0$\omega >0$ we must show that

Using (4.1) and (4.2) we have that

since $A$$A$AA$A$ is positive definite. This gives that $\alpha <1/2$$\alpha <1/2$alpha < 1//2\alpha<1 / 2$\alpha <1/2$. Relationship (4.3) is now equivalent to

which, we observe, is satisfied for $r=\omega$$r=\omega$r=omegar=\omega$r=\omega$, since $2-\omega >0$$2-\omega >0$2-omega > 02-\omega>0$2-\omega >0$. For $r=2$$r=2$r=2r=2$r=2$ (4.4) gives $(1-2\alpha )(2-\omega )>0$$(1-2\alpha )(2-\omega )>0$(1-2alpha)(2-omega) > 0(1-2 \alpha)(2-\omega)>0$(1-2\alpha )(2-\omega )>0$ which is also valid. For $\gamma \ne \omega ,2$$\gamma \ne \omega ,2$gamma!=omega,2\gamma \neq \omega, 2$\gamma \ne \omega ,2$ we have to distinguish cases. Thus if $\alpha \leqq 0(4.4)$$\alpha \leqq 0(4.4)$alpha <= 0(4.4)\alpha \leqq 0(4.4)$\alpha \leqq 0(4.4)$ becomes $-2\alpha (r-\omega )+2-\omega >0$$-2\alpha (r-\omega )+2-\omega >0$-2alpha(r-omega)+2-omega > 0-2 \alpha(r-\omega)+2-\omega>0$-2\alpha (r-\omega )+2-\omega >0$ which is readily seen to hold. If $\alpha >0$$\alpha >0$alpha > 0\alpha>0$\alpha >0$ then we have

Thus $|\lambda |<1$$|\lambda |<1$|lambda| < 1|\lambda|<1$|\lambda |<1$ and the convergence follows. It remains to be proved that $v^H(I-\gamma L)v\ne 0$$v^H(I-\gamma L)v\ne 0$v^(H)(I-gamma L)v!=0v^{H}(I-\gamma L) v \neq 0$v^H(I-\gamma L)v\ne 0$. For this we assume that $v^H(I-\gamma L)v=0$$v^H(I-\gamma L)v=0$v^(H)(I-gamma L)v=0v^{H}(I-\gamma L) v=0$v^H(I-\gamma L)v=0$. Then it will be

which implies that $1-r\alpha =0$$1-r\alpha =0$1-r alpha=01-r \alpha=0$1-r\alpha =0$ and $r\beta =0$$r\beta =0$r beta=0r \beta=0$r\beta =0$. Since $r\ne 0$$r\ne 0$r!=0r \neq 0$r\ne 0$ we have that $\beta =0$$\beta =0$beta=0\beta=0$\beta =0$ and $\alpha =1/\gamma$$\alpha =1/\gamma$alpha=1//gamma\alpha=1 / \gamma$\alpha =1/\gamma$. But $1/\gamma \geqq 1/2$$1/\gamma \geqq 1/2$1//gamma >= 1//21 / \gamma \geqq 1 / 2$1/\gamma \geqq 1/2$ or equivalently $2\alpha \geqq 1$$2\alpha \geqq 1$2alpha >= 12 \alpha \geqq 1$2\alpha \geqq 1$ which is not possible because $2\alpha <1$$2\alpha <1$2alpha < 12 \alpha<1$2\alpha <1$.

Remark. By theorems 3.6 (young, 1971, p. 113) and 2.1 of this paper we can show the convergence of the AOR method for $0<v<2$$0<v<2$0 < v < 20<v<2$0<v<2$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$, where $s=\omega /r$$s=\omega /r$s=omega//rs=\omega / r$s=\omega /r$. This, however does not include the case $r=2$$r=2$r=2r=2$r=2$. So the theorem 4.1 of the present section is more general.

THEOREM 1. Let $A$$A$AA$A$ be an $L$$L$LL$L$-matrix. Then the aor method converges for all $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$, where $s=\omega /r$$s=\omega /r$s=omega//rs=\omega / r$s=\omega /r$ if and only if the Jacobi method converges $(\rho (B)<1,B\equiv L+U)$$(\rho (B)<1,B\equiv L+U)$(rho(B) < 1,B-=L+U)(\rho(B)<1, B \equiv L+U)$(\rho (B)<1,B\equiv L+U)$.

Proof. If $\rho (B)<1$$\rho (B)<1$rho(B) < 1\rho(B)<1$\rho (B)<1$ then by theorem 5.1 (a) (young, 1971, p. 120) we have that the sor method converges for $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$ and therefore by theorem 2.1 of this paper the AOR method converges for $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$. Conversely, if the AOR method converges for $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$, then for $s=1$$s=1$s=1s=1$s=1$ we have that the sor method converges for $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$. Therefore theorem 5.1 (a) (young, 1971, p. 120) implies that $\rho (B)<1$$\rho (B)<1$rho(B) < 1\rho(B)<1$\rho (B)<1$.

If we combine the theorem above with the theorem of section 4 (hadjidimos, 1978) we conclude the following more general theorem for $L$$L$LL$L$-matrices.

THEOREM 2. Let $A$$A$AA$A$ be an $L$$L$LL$L$-matrix. Then the aor method converges for al $0\leqq r\leqq 1$$0\leqq r\leqq 1$0 <= r <= 10 \leqq r \leqq 1$0\leqq r\leqq 1$ and $0<\omega \leqq 1$$0<\omega \leqq 1$0 < omega <= 10<\omega \leqq 1$0<\omega \leqq 1$ if and only if the Jacobi method coverges $(\rho (B)<1)$$(\rho (B)<1)$(rho(B) < 1)(\rho(B)<1)$(\rho (B)<1)$.
theorem 3. Let $A$$A$AA$A$ be an $L$$L$LL$L$-matrix. Then each of the following statements is equivalent to the other two.

S1. The Jacobi method converges.
S2. The SOR method converges for $0<r\leqq 1$$0<r\leqq 1$0 < r <= 10<r \leqq 1$0<r\leqq 1$.
S3 The AOR method converges for $0\leqq r\leqq 1$$0\leqq r\leqq 1$0 <= r <= 10 \leqq r \leqq 1$0\leqq r\leqq 1$ and $0<\omega \leqq 1$$0<\omega \leqq 1$0 < omega <= 10<\omega \leqq 1$0<\omega \leqq 1$.
Proof. From S1| we can easily go to S2| and S3| by using theorem 5.2 above. By theorems 5.1 (a) (voung, p. 120) and 5.2 of this paper $\mathrm{\$}2$$\mathrm{\$}2$$2\$ 2$\mathrm{\$}2$ implies $\overline{\mathrm{S}1}$$\overline{\mathrm{S}1}$bar(S1)\overline{\mathrm{S} 1}$\overline{\mathrm{S}1}$ and $\bar{\mathrm{S}}\bar{3}$$\overline{\mathrm{S}}\overline{3}$bar(S) bar(3)\overline{\mathrm{S}} \overline{3}$\bar{\mathrm{S}}\bar{3}$. Finally $\overline{\mathrm{S}3}$$\overline{\mathrm{S}3}$bar(S3)\overline{\mathrm{S} 3}$\overline{\mathrm{S}3}$ implies $\overline{\mathrm{S}1}$$\overline{\mathrm{S}1}$bar(S1)\overline{\mathrm{S} 1}$\overline{\mathrm{S}1}$ for $r=0,\omega =1$$r=0,\omega =1$r=0,omega=1r=0, \omega=1$r=0,\omega =1$ and $|\overline{\mathrm{S}2}|$$|\overline{\mathrm{S}2}|$| bar(S2)||\overline{\mathrm{S} 2}|$|\overline{\mathrm{S}2}|$ for $\omega =r$$\omega =r$omega=r\omega=r$\omega =r$.
theorem 4. Let $A$$A$AA$A$ be an $L$$L$LL$L$-matrix. Then, the aor method converges for $0<r<\frac{2}{1+p(B)}$$0<r<\frac{2}{1+p(B)}$0 < r < (2)/(1+p(B))0<r<\frac{2}{1+p(B)}$0<r<\frac{2}{1+p(B)}$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$ if and only if $A$$A$AA$A$ is an $M$$M$MM$M$-matrix.

Proof. If $A$$A$AA$A$ is an $M$$M$MM$M$-matrix then by theorem 7.2 (young, p.43) we have $\rho (B)<1$$\rho (B)<1$rho(B) < 1\rho(B)<1$\rho (B)<1$ and by theorem 5.9 (young, p. 126) we conclude that the sor method converges for $0<r<\frac{2}{1+p(B)}$$0<r<\frac{2}{1+p(B)}$0 < r < (2)/(1+p(B))0<r<\frac{2}{1+p(B)}$0<r<\frac{2}{1+p(B)}$. Hence by theorem 2.1 of this paper the AOR method converges for $0<r<\frac{2}{1+\rho (B)}$$0<r<\frac{2}{1+\rho (B)}$0 < r < (2)/(1+rho(B))0<r<\frac{2}{1+\rho(B)}$0<r<\frac{2}{1+\rho (B)}$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$. Conversely, if the AOR method converges for $0<r<\frac{2}{1+\rho (B)}$$0<r<\frac{2}{1+\rho (B)}$0 < r < (2)/(1+rho(B))0<r<\frac{2}{1+\rho(B)}$0<r<\frac{2}{1+\rho (B)}$ and $0<s\leqq 1$$0<s\leqq 1$0 < s <= 10<s \leqq 1$0<s\leqq 1$ this implies that the sor method $(s=1)$$(s=1)$(s=1)(s=1)$(s=1)$ converges for $0<\gamma <\frac{2}{1+\rho (B)}$$0<\gamma <\frac{2}{1+\rho (B)}$0 < gamma < (2)/(1+rho(B))0<\gamma<\frac{2}{1+\rho(B)}$0<\gamma <\frac{2}{1+\rho (B)}$. If we assume that $\rho (B)\geqq 1$$\rho (B)\geqq 1$rho(B) >= 1\rho(B) \geqq 1$\rho (B)\geqq 1$ then $\frac{2}{1+\rho (B)}\leqq 1$$\frac{2}{1+\rho (B)}\leqq 1$(2)/(1+rho(B)) <= 1\frac{2}{1+\rho(B)} \leqq 1$\frac{2}{1+\rho (B)}\leqq 1$ and by theorem 5.1 (c) (yOUNG, p. 121) we have that the sor method does not converge for any value of $\gamma$$\gamma$gamma\gamma$\gamma$ such that $0<\gamma \leqq 1$$0<\gamma \leqq 1$0 < gamma <= 10<\gamma \leqq 1$0<\gamma \leqq 1$ which is not true. Thus we have $\rho (B)<1$$\rho (B)<1$rho(B) < 1\rho(B)<1$\rho (B)<1$ and therefore $A$$A$AA$A$ is an $M$$M$MM$M$-matrix according to theorem 7.2. (young, p. 43).

THEOREM 5. Let $A$$A$AA$A$ be an $M$$M$MM$M$-matrix. Then the aor method converges for $0\leqq \nu \leqq 1$$0\leqq \nu \leqq 1$0 <= nu <= 10 \leqq \nu \leqq 1$0\leqq \nu \leqq 1$ and $0<\omega \leqq 1$$0<\omega \leqq 1$0 < omega <= 10<\omega \leqq 1$0<\omega \leqq 1$ and also for $1<\nu <\frac{2}{1+\rho (B)}$$1<\nu <\frac{2}{1+\rho (B)}$1 < nu < (2)/(1+rho(B))1<\nu<\frac{2}{1+\rho(B)}$1<\nu <\frac{2}{1+\rho (B)}$ and $0<\omega \leqq \nu$$0<\omega \leqq \nu$0 < omega <= nu0<\omega \leqq \nu$0<\omega \leqq \nu$.

Proof: The proof follows by Theorems 5.2 and 5.4.

The following examples ensure the validity of all theorems presented previously and in addition show the asymptotical superiority of the aOR method, compared with the sor one. For this, we worked out specific examples and found out the optimum spectral radii of the corresponding iterative matrices in all cases considered. We have, to the parameters $r$$r$rr$r$ and $\omega$$\omega$omega\omega$\omega$ all the values $0(0.01)2$$0(0.01)2$0(0.01)20(0.01) 2$0(0.01)2$ and $0.01(0.01)2$$0.01(0.01)2$0.01(0.01)20.01(0.01) 2$0.01(0.01)2$ respectively and independently of each other. The upper bound 2 was selected because all theorems of this paper give only sufficient conditions for the convergence of the AOR method and not necessary ones as well while in addition to that the theorem of Kahan states that if the sor method converges, then it must be $0<\omega <2$$0<\omega <2$0 < omega < 20<\omega<2$0<\omega <2$.

Using the UNIVAC 1106 Computer of the University of Salonica and with a maximum permissible relative error $E={10}^{-4}$$E={10}^{-4}$E=10^(-4)E=10^{-4}$E={10}^{-4}$, in finding the spectral radii, we have found that:
i) In the case where $A$$A$AA$A$ is the following irreducible with weak diagonal dominance matrix

the optimum spectral radius of AOR method has been found for $r=1.26$$r=1.26$r=1.26r=1.26$r=1.26$, $\omega =1.18$$\omega =1.18$omega=1.18\omega=1.18$\omega =1.18$ and is ${\rho }_{\text{opt}}(L_r,\omega )\approx 0.272$${\rho }_{\text{opt }}\left(L_r,\omega \right)\approx 0.272$rho_("opt ")(L_(r),omega)~~0.272\rho_{\text {opt }}\left(L_{r}, \omega\right) \approx 0.272${\rho }_{\text{opt }}(L_r,\omega )\approx 0.272$ while the optimum spectral radius of sor method is given for $\omega =1.24$$\omega =1.24$omega=1.24\omega=1.24$\omega =1.24$ and is ${\rho }_{\text{opt}}\left(L_{\omega ,\omega }\right)\approx 0.327$${\rho }_{\text{opt }}\left(L_{\omega ,\omega }\right)\approx 0.327$rho_("opt ")(L_(omega,omega))~~0.327\rho_{\text {opt }}\left(L_{\omega, \omega}\right) \approx 0.327${\rho }_{\text{opt }}\left(L_{\omega ,\omega }\right)\approx 0.327$.
ii) In the case where $A$$A$AA$A$ is the following positive definite (real) matrix

it has been found that ${\rho }_{\text{opt}}\left(L_{r,\omega }\right)\approx 0.196$${\rho }_{\text{opt }}\left(L_{r,\omega }\right)\approx 0.196$rho_("opt ")(L_(r,omega))~~0.196\rho_{\text {opt }}\left(L_{r, \omega}\right) \approx 0.196${\rho }_{\text{opt }}\left(L_{r,\omega }\right)\approx 0.196$ for $\gamma =1.03$$\gamma =1.03$gamma=1.03\gamma=1.03$\gamma =1.03$ and $\omega =1.23$$\omega =1.23$omega=1.23\omega=1.23$\omega =1.23$ while ${\rho }_{\text{opt}}\left(L_{\omega ,\omega }\right)\approx 0.282$${\rho }_{\text{opt }}\left(L_{\omega ,\omega }\right)\approx 0.282$rho_("opt ")(L_(omega,omega))~~0.282\rho_{\text {opt }}\left(L_{\omega, \omega}\right) \approx 0.282${\rho }_{\text{opt }}\left(L_{\omega ,\omega }\right)\approx 0.282$ for $\omega =1.08$$\omega =1.08$omega=1.08\omega=1.08$\omega =1.08$.
iii) In the case where $A$$A$AA$A$ is the following $L$$L$LL$L$-matrix with $\rho (B)<1$$\rho (B)<1$rho(B) < 1\rho(B)<1$\rho (B)<1$, that is, $A$$A$AA$A$ is an $M$$M$MM$M$-matrix

we have ${\rho }_{\text{opt}}(L_r,\omega )\approx 0.302$${\rho }_{\text{opt }}\left(L_r,\omega \right)\approx 0.302$rho_("opt ")(L_(r),omega)~~0.302\rho_{\text {opt }}\left(L_{r}, \omega\right) \approx 0.302${\rho }_{\text{opt }}(L_r,\omega )\approx 0.302$ for $v=1.18,\omega =0.90$$v=1.18,\omega =0.90$v=1.18,omega=0.90v=1.18, \omega=0.90$v=1.18,\omega =0.90$ and ${\rho }_{\text{opt}}\left(L_{\omega ,\omega }\right)\approx 0.354$${\rho }_{\text{opt }}\left(L_{\omega ,\omega }\right)\approx 0.354$rho_("opt ")(L_(omega,omega))~~0.354\rho_{\text {opt }}\left(L_{\omega, \omega}\right) \approx 0.354${\rho }_{\text{opt }}\left(L_{\omega ,\omega }\right)\approx 0.354$ for $\omega =1.00$$\omega =1.00$omega=1.00\omega=1.00$\omega =1.00$.