\documentstyle[IEEEtran]{article}
\begin{document}
\tolerance 10000
\title{Inner Estimation of the United Solution Set
              of Interval Linear Algebraic System}
\author{L. Kupriyanova}

\pagestyle{myheadings}

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

\maketitle

\auffil{The authors are with the Department of Mechanics and Mathematics,
 Saratov State University,
 Astrakhanskaya 83,
 Saratov, 410071, Russia,
 e-mail zyuzin@scnit.saratov.su (for Kupriyanova).}

\section{Formulation of the Problem}
Suppose that an interval matrix ${\bf A}=\{{\bf A}_{ij}\}$ 
and an interval vector ${\bf b}=\{{\bf b}_i\}$ 
are given. The set of all solutions $x=\{x_j\}$ of the
systems $Ax=b$ for $A\in {\bf A}$ and $b\in{\bf b}$ 
is called the {\it united solution set}. It is known that the united
solution set is (in general) not an interval
vector. This set 
may  have  a  complicated
structure. 
\begin{itemize}
\item
There are many papers devoted  to  computing {\it outer
estimations} for this set (see, e.g. \cite{2,3}).

     \item We present a method of finding an interval vector that is an
{\it inner estimation} for the united  solution set.
\end{itemize}

\section{Kaucher's Extended Interval Arithmetic}
For computing the desired inner estimation, we use 
the {\it extended  interval  arithmetic} proposed by 
Kaucher in \cite{1}. 

In this formalism, basic objects are 
{\it extended intervals}, i.e., arbitrary pairs of real numbers. These pairs
are denoted by $[a,b]$. 
\begin{itemize}
\item
We interpret extended intervals
with  $a<b$  (called {\it proper intervals}) as standard intervals
(i.e., as sets of real numbers $[a,b]$). 

\item Extended intervals with $a>b$ 
({\it improper} intervals) are used in our method as auxiliary objects in 
intermediate  computations.
\end{itemize}

\section{Main Result}
We propose an algorithm that:\begin{itemize}
\item  starts with  an extended interval matrix
$\bf A$ and an extended interval vector $\bf b$, and 
\item returns an extended interval vector $${\bf x}=({\bf x}_1,
...,{\bf x}_n).$$
\end{itemize}

This algorithm has the following property:
If we start with proper intervals ${\bf A}_{ij}$ and ${\bf b}_i$, and
all components of the resulting vector ${\bf x}_j$ are proper
intervals, then this interval vector is an inner estimation for the
united solution set of the system ${\bf A}x={\bf b}$. 

\section{Basic Idea}
This algorithm is based on the following idea:
It turns out that the solution of an interval algebraic system with
proper intervals is 
related to the solution of the {\it dual} system ${\bf A}'x={\bf b}'$, 
whose matrix ${\bf A}_{ij}$ is
composed of the elements that are {\it dual} to ${\bf A}_{ij}$ (a
dual to an extended interval $[a,b]$ is the interval $[b,a]$). 

We show that 
an algebraic  interval   solution  to this dual system 
is an inner estimation 
for  the  united  solution  set  of the original system. 
So, to find the desired inner estimation, 
it is sufficient to find a normal
solution to the algebraic system with improper interval coefficients. 

For that purpose, we use an algorithm that has been originally
proposed by  Zyuzin  \cite{4,5}  for 
systems with proper interval coefficients. 
We show  that  the properties of this algorithm described in
\cite{4,5} remain true if we use this algorithms for extended
intervals. 

\section{Other Applications of This Idea}
Other applications of this idea are described.

\begin{thebibliography}{99}

\bibitem{1} C. W. Kaucher, ``Interval analysis in the extended interval
   space $IR$'', {\it Computing}, Supplement 2, 1980, pp. 33--49.

\bibitem{2} S. P. Shary, ``A new class of algorithms for optimal  solution
   of interval linear systems'', {\it Interval Computations}, 1992,
No.  4, pp. 18--29.

\bibitem{3} A. V. Zakharov, {\bf The solution of interval linear systems $Ax=b$
   and their properties}, VIMI Dep. 16.02.1989, No. D007755
   (in Russian).

\bibitem{4} V. S. Zyuzin, ``On  a  method of  finding  two-sided  interval
   approximations for the solution of linear  interval  system
   of equations'', In:  {\bf Diff. equations and functions theory},
Vol. 7, 
Saratov University Press, Saratov, 1987, pp. 28--32 (in Russian).

\bibitem{5}V. S. Zyuzin, ``An iterative method for solving  a  system  of
   segment algebraic equations'', In:  {\bf Diff. equations and functions
   theory}, Vol. 8, 
Saratov University Press, Saratov, 1989, pp. 72-82 (in Russian).


\end{thebibliography}
\end{document}