\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{On the Interval Multisplitting AOR (IMAOR) Method}
\author{Da-Wei Chang}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\begin{abstract}
Frommer and Mayer have developed 
an interval multi-splitting method 
for solving the systems of linear interval equations 
$${\bf A}x={\bf b},$$ where ${\bf A}\in I(R^{n\times n})$ is 
a regular interval matrix, and ${\bf b}$ is an interval vector. 
Based on this method, we develop a new method called 
{\it multispilitting AOR (IMAOR)}.
The convergence of this method is discussed. For the case when the
matrix $\bf A$ is an $H-$matrix, we formulate conditions that
guarantee convergence. These conditions are easy to check.
\end{abstract} 
  
\auffil{The author is with the Department of Mathematics, Shaanxi
Normal University, Xi'an, 710062, P. R. China.}

\noindent{\bf Definition 1.} An interval matrix ${\bf A}\in
I(R^{n\times n})$ is called {\it regular} if each real matrix $A\in
{\bf A}$ is nonsingular.
\smallskip
 
\noindent{\bf Definition 2.} Let ${\bf A}\in I(R^{n\times n})$ be a
regular interval matrix, and let ${\bf b}\in I(R^n)$ be an interval
vector. Then, by {\it solving linear interval equations}
$${\bf A}x={\bf b},\eqno{(1)}$$ 
we mean the problem of finding an interval enclosure of the solution
set
$$S=\{x\,|\,x=A^{-1}b, A\in {\bf A}, b\in {\bf b}.\},\eqno{(2)}$$

\noindent{\it Comment.} The goal is to find a {\it good} enclosure.
\smallskip

In order to compute the solution (1) iteratively, Frommer and Mayer
\cite {Frommer et al} proposed a class of methods called 
{\it interval multisplitting methods}
to enclose the solution set $S$ given by (2).  Let us explain this
class of methods:
\smallskip

\noindent{\bf Denotation 1.} By 
$IGA({\bf M})({\bf r})$, we will denote the result of applying
interval Gaussian algorithm ({\it IGA}) to the
equation ${\bf M}x={\bf r}$.
\smallskip

\noindent{\bf Definition 3.} \cite{Frommer et al} An {\it 
interval multisplitting} of an interval matrix ${\bf A}$ 
is defined as a finite collection of triples 
$({\bf M}_k,{\bf N}_k,{\bf E}_k), k = 1,2,...,K$ of interval matrices
${\bf M}_k, {\bf N}_k, {\bf E}_k\in I(R^{n\times n})$, such that the
matrix ${\bf
M}_k$ if regular for all $k$, and the following three conditions are
satisfied:
\begin{itemize}
\item[1.] For every $k$, ${\bf A} = {\bf M}_k - {\bf N}_k.$ 
\item[2.] For every $k$, 
the interval Gaussian algorithm $IGA$ is feasible when applied to 
the equation ${\bf M}_kx={\bf b}$ with an arbitrary right-hand side
$\bf b$. 
\item[3.] For every $k$, ${\bf E}_k$ 
is a diagonal matrix with nonnegative entries. These matrices must satisfy
the following equation:
$$\sum_{k=1}^K {\bf E}_k = I.$$
\end{itemize}

\noindent{\bf INTERVAL MULTISPLITTING METHOD.} \cite{Frommer et al}
{\sl Suppose that we want to solve a problem
(1), and that an interval multisplitting is
given for the matrix $\bf A$. 
The corresponding {\it interval multisplitting method} 
to enclose the set $S$ given by (2) is defined by the following iteration:
$${{\bf x}^{(m+1)} = \sum_{k=1}^K {\bf E}_k{\bf y}^{m,k},\ 
m = 0,1,...},\eqno{(3)}$$
where 
$${\bf y}^{m,k} = IGA({\bf M}_k)({\bf N}_k{\bf x}^{(m)} + 
{\bf b}),\ k = 1,2,...,K.$$}
\smallskip

\noindent{\it Comment.} This 
interval multisplitting method possesses a natural {\it parallelism}: 
the computations of ${\bf y}^{m,k}$ for different $k$ are
independent on each other, and therefore, these computations can be 
computed on $K$ different processors of a multiprocessor system.

The fact that we do not not need to compute 
the $i$-th component of ${\bf y}^{m,k}$ if the 
corresponding diagonal entry $({\bf E}_k)_{ii}$ of the matrix ${\bf
E}_k$ is zero, makes these computations even faster. 
This may result in considerable savings of computational time. 
\smallskip

\noindent{\bf Our idea.} In this paper, we present a class of the
interval multisplitting AOR (IMAOR) methods for solving large linear
interval systems of equations (1). The convergence theorems for this 
new algorithm are established under the condition that the coefficient
matrix $\bf A$ is an $H-$matrix. These convergence conditions are
easy to check.

To formulate our algorithm, we will need to modify the definition of a
multisplitting.
\smallskip

\noindent{\bf Definition 4.} Let ${\bf A}\in I(R^{n\times n})$ be a
regular interval matrix. By a {\it multisplitting} of $\bf A$, we will
understand the 
finite collection of triples
$({\bf D}-{\bf L}_k,{\bf U}_k,{\bf E}_k), k = 1,2,...,K$ of interval
matrices, where:
\begin{itemize}
\item $\bf D$ is a diagonal part of the matrix $\bf A$;
\item each matrix ${\bf L}_k$ is strictly lower triangular;
\item each matrix ${\bf U}_k$ is strictly upper triangular,
\end{itemize}
for which 
the following three conditions are satisfied:
\begin{itemize}
\item[1.] For every $k$, ${\bf A} = {\bf D}-{\bf L}_k - {\bf U}_k.$ 
\item[2.] There exists a real number $\gamma$ such that for every $k$, 
the interval Gaussian algorithm $IGA$ is feasible when applied to 
the equation $({\bf D}-\gamma{\bf L}_k)x={\bf b}$ 
with an arbitrary right-hand side $\bf b$. 
\item[3.] For every $k$, ${\bf E}_k$ 
is a diagonal matrix with nonnegative entries. These matrices must satisfy
the following equation:
$$\sum_{k=1}^K {\bf E}_k = I.$$
\end{itemize}

\noindent{\bf Denotation 2.} Suppose that we are given:
\begin{itemize}
\item a system (1), 
\item a
multisplitting for the corresponding matrix $\bf A$, and 
\item a real number $\omega$. 
\end{itemize}
Then, we
will define $f_k(\gamma,\omega,{\bf x})$ as
$$f_k(\gamma,\omega,{\bf x})=$$ 
$$IGA({\bf D}-\gamma{\bf L}_k)$$ $$\{[(1-\omega){\bf
D}+(\omega-\gamma){\bf L}_k+\omega{\bf U}_k]{\bf x}+\omega{\bf b}\}.$$ 
\smallskip

\noindent{\bf IMAOR METHOD.} {\it Start with an arbitrary vector ${\bf
x}^{(0)}\in I(R^n)$. Then, for $m=0,1,2,...,$ compute 
$${\bf x}^{(m+1)}=\sum_{k=1}^K {\bf E}_kf_k(\gamma, \omega,{\bf
x}^{(m)}),$$ until this procedure converges.}
\smallskip

\noindent{\it Comments.} This method can be reformulated as 
$$ {\bf x}^{(m+1)}=T_{IMAOR}(\omega,\gamma){\bf
x}^{(m)}+g_{IMAOR}(\omega,\gamma),$$
where we denoted
\newpage
$$T_{IMAOR}(\gamma,\omega)=$$ $$\sum_{k=1}^K {\bf E}_k \cdot
IGA({\bf D}-\gamma{\bf L}_k)$$ $$[(1-\omega){\bf
D}+(\omega-\gamma){\bf L}_k+\omega{\bf U}_k],$$ and 
$$g_{IMAOR}(\gamma,\omega)=\sum_{k=1}^K {\bf E}_k \cdot
IGA({\bf D}-\gamma{\bf L}_k)(\omega {\bf b}).$$

If $K=1$, and ${\bf A}$, ${\bf L}_1$, and ${\bf U}_1$ are point
matrices, then the above IMAOR methods reduces to the AOR method
proposed in \cite{4}. 
\smallskip

Our main results are as follows:
\smallskip

\noindent{\bf THEOREM 1.} {\sl If $\bf A$ is an $H-$matrix, 
$0\le\gamma\le 1$, $0<\omega<1$, and a multisplitting of $\bf A$
is given, 
then for an arbitrary starting vector ${\bf x}^{(0)}$, the following results
are true:
\begin{itemize}
\item[1)] IMAOR method is {\it feasible}, i.e., the sequence ${\bf
x}^{(m)}$ converges to an interval vector ${\bf x}^*$. 
\item[2)] IMAOR method is {\it monotonic with respect to inclusion},
i.e., if ${\bf x}^{(0)}\subseteq {\bf y}^{(0)}$, then ${\bf
x}^{(m)}\subseteq {\bf y}^{(m)}$ for all $m$. 
\item [3)]If $S\subseteq {\bf x}^{(0)}$, then $S\subseteq {\bf x}^{(m)}$.
\item [4)]$S\subseteq {\bf x}^*$.
\end{itemize}}

\noindent{\bf COROLLARY.} {\sl Suppose that the matrix ${\bf A}$
satisfies the following two conditions:
\begin{itemize}
\item $\bf A$ is an $M-$matrix;
\item $\bf A$ is either strictly or irreducibly diagonally dominant.
\end{itemize}
Suppose also that 
$0\le\gamma\le 1$, $0<\omega<1$, and a multisplitting of $\bf A$
is given.
Then, for an arbitrary starting vector ${\bf x}^{(0)}$, the statements
1)-4) are true.}

\begin{thebibliography}{99}
\bibitem{1}
G. Alefeld and J. Herzberger, {\bf Introduction to Interval
Computations}, Academic Pres, N.Y., 1983.

\bibitem{2} A. Berman and R. J. Plemmous, {\bf Nonnegative matrices in
the mathematical sciences}, Academic Press, N.Y., 1979.

\bibitem{Frommer et al}A. Frommer and G. Mayer, ``Parallel interval
multisplitting'', {\it Numer. Math.}, 1989, Vol. 56, pp. 255--267.

\bibitem{4}A, Hadjidimos, ``Accelerated overrelaxation method'', {\it
Math. Comp.}, 1978, Vol. 32, pp. 149--157.

\bibitem{5} A. Neumaier, ``New techniques for the analysis of linear
interval equations'', {\it Linear Algebra and its Applications}, 1984,
Vol. 58, pp. 273--325.

\end{thebibliography}
\end{document}