\section{C++ Toolbox for Verified Computing}

This modules includes several algorithms of the Toolbox into rascal. Please
refer to the book

    R. Hammer, M. Hocks, U. Kulisch, D. Ratz:  C++ Toolbox for
    Verified Computing I - Basic Numerical Problems. Springer-Verlag,
    Heidelberg, New York, 1995.

or the webpage {\tt http://www.xsc.de/} for more information.

In Rascal you may enter {\tt help toolbox} to check what toolbox modules are
included.
 
\subsection{Evaluation of Polynomials}

The function {\tt RPolyeval($p$,$t$)} evaluates the real polynomial $p$ at
$t$ at maximum accuracy, even in the neighborhood of a root where
cancellation dooms an ordinary floating-point evaluation.

The function returns a vector with the entries {\tt [$y$;$iy$;$it$;$err$]}
where $y$ is the result of a Horner scheme evaluation, $iy$ represents a
maximum accuracy enclosure, $it$ the number of iterations needed and $err$
an eventual error message. The function {\tt rpeval($p$,$t$)} just returns
the resulting interval.

\begin{lyxcode}
>X=poly("X");

>p=(X-2)\^{ }4

~X\^{ }4-8*X\^{ }3+24*X\^{ }2-32*X+16

>p(2.0001)
   
~-3.5527136788E-015
  
>RPolyEval(p,2.0001)
   
~[-3.5527136788E-015;[1.0000000000E-016,1.0000000001E-016];2;""]
  
>rpeval(p,2.0001)
   
~[1.0000000000E-016,1.0000000001E-016]

\end{lyxcode}

\subsection{Zeros of Complex Polynomials}

The function {\tt CPolyZero($p$,$t$)} computes verified enclosures of the
roots of a complex polynomial $p$ starting from $t$ by enclosing the zeros
in narrow bounds. The coefficients of the deflated polynomial are also
enclosed.

The function returns a vector with entries {\tt [$y$;$p$;$err$]} where $y$
is a complex enclosure of the root close to $t$, $p$ the complex enclosure
of the reduced polynomial and $err$ represents an eventual error messages.
The functions {\tt cpzero($p$,$t$)} and {\tt cpreduce($p$,$t$)} just return
the enclosure of the root or of the reduced polynomial.

\begin{lyxcode}
>X=poly("X");p=X\^{ }4-(5+3*i)*X\^{ }3+(6+7*i)*X*X-(54-22*i)*X+120+90*i;
   
>CPolyZero(p,1+i)
    
~[([   1.4142135623,   1.4142135624]+[   2.8284271247, 2.8284271248]*i);

~X\^{ }3+([-3.5857864377, -3.5857864376]+[-0.1715728753,-0.1715728752]*i)*X\^{ }2

~+([  1.4142135623,  1.4142135624]+[ -3.3847763109,-3.3847763108]*i)*X

~+([-42.4264068712,-42.4264068711]+[ 21.2132034355,21.2132034356]*i);""]

>cpzero(p,4)

~([4.9999999999,5.0000000001]+[-2.2569491536E-036,2.2569491536E-036]*i)
\end{lyxcode}

\subsection{Linear Systems of Equations}

The function {\tt LinSolve($A$,$b$)} computes a verified solution to the
square linear system $A*x=b$ for a real square matrix $A$ and real vector
$b$ based on a Newton-like method for an equivalent fixed-point problem.

The function returns a vector with entries {\tt [$x$;$cond$;$err$]} where
$x$ represents the verified enclosure or exact solution to the system, $cond$ 
a condition number estimate and $err$ an eventual error message. The
function {\tt linsys($A$,$b$)} just returns the resulting vector enclosure.

\begin{lyxcode}
>A=1.*BoothroydDecker(6);

>b=[1;2;3;4;5;6];

>Precision(-10);
   
>(1/A)*b
    
~[0;1;-2;3.0000000001;-4.0000000002;5.0000000005]
   
>LinSolve(A,b)
    
~[[0;1;-2;3;-4;5];112890625.00085557;""]
   
>A*linsys(A,b)-b
    
~[0;0;0;0;0;0]
\end{lyxcode}

\subsection{Linear Optimization}

The functions {\tt RevSimplex($A$,$b$,$c$)} and {\tt
LinOpt($A$,$b$,$c$,$BStart$)} determine the optimal solution of the linear
optimization problem: Maximize $z=c^T*x$ where $A*x=b$ and $x\geq0$. 
{\tt LinOpt } validates the solution and determines enclosures of the true
optimal solution set.

{\tt RevSimplex} returns a vector with entries {\tt [$x$;$v$;$z$;$err$]}
where $x$ denotes the optimal solution vector, $v$ the optimal basic index
set, which can be used as $bstart$ for {\tt LinOpt}, $z$ the optimal value
and $err$ might contain an error message. {\tt LinOpt} returns a vector {\tt
[$z$;$V$;$X$;$no$;$err$]} where $z$ is the enclose of the optimal value, $V$
is a matrix which no lines represent the different index vectors, $X$ a matrix
which lines represent the different solution vectors and $err$ again is the
eventual error message.

\begin{lyxcode}
>Precision(-10);A=[1 0 1 0 0;0 1 0 1 0;100 18 0 0 1];
   
>b=[50;200;5000];c=[50;9;0;0;0];
   
>S=RevSimplex(A,b,c)

~[[14;200;36;0;0];[1;3;2];2500;""]
   
>LinOpt(A,b,c,S(2))

~[2500;[1 2 3;1 2 4;1 3 4];[14 200 36 0 0;50 0 0 200 0;50 0 0 200 0];3;""] 
\end{lyxcode}