\def\talklabel{UTEP94}
\def\runningfoot{NLE Environment}

\documentstyle[12pt,amssymbols]{article}

%  Commands for formatting slides --


\newcommand{\slidetitle}[1]{\begin{center}\Large\bf
                            #1\end{center}}
\newcommand{\subtitle}[1]{\begin{center}\large\it #1
                          \end{center}}
\newcommand\botpage{\footnotetext{\large\runningfoot\scriptsize\rm\hfill
\talklabel--\thepage}
\newpage}

% Commands for formatting mathematical constructions --

\newcommand{\sclvec}[2] {(#1_1,#1_2,\dots,#1_#2)}
\newcommand{\ivl}[1] {{\bf #1}}
\newcommand{\ifpxk} {\ivl F'({\ivl X}_k)}
\newcommand{\iXkb} {{\tilde{\ivl X}_k}}
\newcommand{\iXk}{{\ivl X}_k}
\newcommand{\iXko}{{\ivl X}_{k+1}}
\newcommand{\oix} { {\tilde{\ivl x}} }
\newcommand{\xl}{\underline x}
\newcommand{\xu}{\overline x}
\newcommand{\pl}{ {\underline{\phi}} }
\newcommand{\pu}{ {\overline{\phi}} }
\newcommand{\ia}{{\ivl f}'}
\newcommand{\ix}{{\ivl X}}
\newcommand{\lst}{{\cal L}}
\newcommand{\implies}{{\Rightarrow}}
\newcommand{\ixi}{{\ivl x}_i}

\pagestyle{empty}

\begin{document}
\renewcommand\footnoterule{}
\renewcommand\thefootnote{}
\newpage

\newcommand{\nop}{N_{\makebox{\scriptsize OPS}}}

\slidetitle{What is Interval Arithmetic?}

\noindent Interval arithmetic is based on defining the four
elementary arithmetic operations on intervals.  Let
$ {\bf a} = [a_l,a_u]$
and $ {\bf b} = [b_l,b_u]$ be intervals.
Then, if $\makebox{\it op} \in \{+,-,*,/\}$, we define
$$  {\bf a} \makebox{\ \it op \ }   {\bf b}
= \left\{ x \makebox{\ \it op \ } y \mid x \in  {\bf a} \makebox{\ and\
} y \in  {\bf b} \right\}.$$
For example,
$  {\bf a} +  {\bf b} = [ a_l + b_l, a_u + b_u ]$.
In fact, all four operations can be defined in terms of addition,
subtraction, multiplication, and division of the endpoints of the
intervals, although multiplication and division may require
comparison of several results.  The result of these operations is
an interval except when we compute $ {\bf a} /  {\bf b}
\makebox{\ and \ } 0 \in  {\bf b}$.

\slidetitle{Why Interval Arithmetic?}

\begin{itemize}
\item With {\it directed roundings}, we can bound roundoff error
in
the computations.  We can combine interval arithmetic with tools such as
fixed-point iteration theorems to
\begin{itemize}
\item automatically verify rigorous bounds, from approximate solutions.
\item automatic theorem proving.
\end{itemize}

\item Interval arithmetic provides {\it rigorous\hfill\break
bounds on the ranges\/} of functions.  Po\-session of such bounds can be
powerful, especially in {\it rigorous global optimization}.

\end{itemize}

\slidetitle{An Example of Interval Arithmetic}

\begin{eqnarray*}
[-1,2] \left([3,4] + [-5,6]) \right) &=&
[-1,2] \left([-2,10]\right) \\
&=& [-10,20],
\end{eqnarray*}
whereas
\begin{eqnarray*}
[-1,2] [3,4] + [-1,2] [-5,6] &=& [-4,8] + [-10,12] \\
&=& [-14,20]
\end{eqnarray*}
\smallskip
\noindent Here,
\begin{eqnarray*}
[-14,20] &=& \big\{x\mid x=x_1+x_2, x_1\in[-4,8],\\
& &\qquad x_2\in[-10,12]\big\},
\end{eqnarray*}
and $[-14,20]$ {\em contains} the range of
$xy + xz$ for $x\in[-1,2]$, $y\in[3,4]$, and $z\in[-5,6]$.

\slidetitle{Inclusion Monotonic Interval Extensions of Functions}

\noindent {\bf Definition.} If f is a continuous function of a real
variable, then an inclusion monotonic interval extension $ {\bf f}$ is
a function from the set of intervals to the set of intervals,
such that, if ${\bf x}$ is an interval in the domain of $ {\bf f}$,
$$\left\{ f(x) \mid x \in  {\bf x} \right\} \subset  {\bf f}( {\bf x})$$
and such that
$$  {\bf x} \subset  {\bf y} \implies  {\bf f}( {\bf x}) \subset
 {\bf f}( {\bf y}).$$

\begin{itemize}
\item We may obtain such interval extensions of a polynomial
by replacing real operations by corresponding interval operations.
For example, if
$p(x) = x^2 - 4$, then $ {\bf p}([1,2])$ may be defined by
\begin{eqnarray*}
{\bf p}([1,2]) &=& ([1,2])^2 - 4  =  ([1,4]) - [4,4] \\
&=& [-3,0].
\end{eqnarray*}
\end{itemize}

\slidetitle{Interval Extensions of Transcendental Functions}

\begin{itemize}
\item We may use the mean value theorem or Taylor's theorem
with remainder formula.
For example, suppose ${\bf x}$ is an interval
and $a \in {\bf x}$.  Then, for any $y \in {\bf x}$, we have
$$\sin(y) = \sin(a) + (y - a) \cos(a) - (y - a)^2/2 \sin(c)$$
for some $c$ between $a$ and $y$.  If $a$ and $y$ are both within a
range where the sine function is non-negative, then we obtain
$$\sin(y) \in  \sin(a) + ({\bf x} -a) \cos(a) -
\frac{({\bf x} - a)^2}{2}.$$
Specifically, if ${\bf x} = [.1,.3]$ and we use $a = .2$, we would
obtain
the ``value''
\begin{eqnarray*}
{\bf{sin}}([.1,.3]) &\subseteq& \sin(.2) + [-.1,.1] \cos(.1)\\
& &\phantom{\subseteq sin(.2) }- \frac{({[-.1,.1]}^2)}{2} \\
&\subseteq& [.0998,.0999] \\
& &\phantom{\subseteq} + [-.1,.1] [.995,.996] + [-.005,0]\\
&=&[-.0048,.1995]
\end{eqnarray*}

\item Sharper interval extensions may be obtained
in specific cases by using
e.g.\ monotonicity of the original function.

\end{itemize}

\slidetitle{Pitfalls to Naive Interval Arithmetic}

\begin{itemize}
\item For rigorous bounds on roundoff error, one may be tempted to
translate floating-point computer codes by merely changing the data
types.

\item Due to interval dependencies, such naive development often is
unsuccessful.

\item Interval arithmetic is successful if it is applied to
appropriate tasks and with appropriate algorithms.
\begin{itemize}
\item It provides rigorous results from the computer arithmetic.
\item It can actually result in {\em faster\/} algorithms, even if the
actual arithmetic is in software and 20 to 30 times slower than floating
point arithmetic.
\end{itemize}

\item Researchers continue to make advances to enlargen the domain in
which interval analysis can make computations rigorous and reliable.
\end{itemize}

\slidetitle{Interval Newton Methods}
\subtitle{A Simple Example}

If $n=1$
and  $$f(x) = x^2-4,$$
then the linear interval system becomes
$${2\ixi} (\oix_i - x_i) = -f(x_i).$$
The interval Newton iteration equation becomes
$$\oix_i = \oix = x_i - \frac{f(x_i)}{{2\ixi}} =
x - \frac{f(x)}{2{\ivl x}}.$$

If we
choose initial interval and point
$$\iXk = \ixi = {\ivl x} = [1,2.5],\qquad x_i = x = 1.75,$$
then
\begin{eqnarray}
\oix = 1.75 - \frac{-.9375}{[2,5]} &=& 1.75 - [.1875,.46875] \\
&=& [1.9375,2.21875] \subset {\ivl x},
\end{eqnarray}
so we may conclude that there is a unique root of $f$ in ${\ivl x}$.

\slidetitle{Finding All Roots}

\begin{itemize}
\item In {\em univariate\/} problems, interval Newton methods can be
iterated
with {\em extended interval arithmetic\/} to {\em always\/} find {\em
all\/} roots.

\item In {\em multivariate\/} problems, interval Newton methods can be
combined with {\em generalized bisection\/} and {\em binary search\/} to
{\em always\/} find {\em all\/} roots.


\item In both instances, failure modes are benign:
\begin{itemize}
\item Failure can only occur by exceeding the computer's resources or
because of the limited resolution of the floating-point numbers.
\item When failure occurs, the algorithms still print a list of boxes
within which all roots must lie.
\end{itemize}

\end{itemize}

\subtitle{An Example}

\noindent As before, let $f(x) = x^2-4$, but now let
$\ivl \iXk = \ixi = {\ivl x} = [-2,2]$ and $x_i = x = 0$.
The first iteration of the interval Newton method thus becomes
\begin{eqnarray}
\oix &=& 0 - \frac{-4}{[-4,4]} = 0 -
\left([-\infty,-1]\cup[1,\infty]\right)\\
&=& \left([-\infty,-1]\cup[1,\infty]\right)
\end{eqnarray}

\noindent Thus,
\begin{equation}\label{eq:extended-result}
\oix\cap\iXk = [-2,-1] \cup [1,2].
\end{equation}

\begin{itemize}

\item One of the intervals in Equation~\ref{eq:extended-result} is put
on a list for further processing, and the interval Newton method is
iterated on the other.

\item The interval Newton method will converge to zero-width intervals
for {\em each\/} startin interval from
Equation~\ref{eq:extended-result}.

\item Hansen has proven that this behavior is true in general.
\end{itemize}

\end{document}
