Introduction to Interval Numerical Methods
Ned Nedialkov (McMaster University, Hamilton, Ontario, Canada)Abstract: Interval methods produce bounds that are guaranteed to contain mathematically correct results. Such bounds enclose truncation, rounding, and often modeling errors. Simply replacing reals by intervals in a point numerical method usually leads to a ``naive'' interval method, which computes bounds that are generally too wide to be useful. To compute sufficiently tight bounds, an interval method normally involves specific ``interval'' machinery. This talk presents interval arithmetic and techniques commonly used in interval methods.
We discuss interval arithmetic and some of its properties. Bounding ranges of functions is central to interval computing. We illustrate popular approaches, such as the mean-value form, the slope form, and Taylor series, for bounding ranges of functions.
A contractive mapping theorem is frequently the basis of an efficient interval algorithm. We show how contractive mapping (and other approaches) are employed when enclosing the solution of a nonlinear system of equations, using an interval Newton method, and when enclosing the solution of a linear system of equations.
We also discuss briefly several popular interval-arithmetic packages.
Mapping Expressions to Functions in Cset Interval Arithmetic
John D. Pryce (Cranfield University, RMCS Shrivenham, UK)
Abstract:
Csets (containment-sets) are a way of giving expressions
a value even at arguments that give rise to division by zero or
other ``illegal'' operation. The definition for evaluation over
the reals is that, if 
is a function of 
variables (so
) then its cset at a point 
is the set
of all limits, in the extended reals
![$[-\infty, +\infty]$](T6_files/img5.gif){kind=small}
of
sequences of values 
where the sequence 
converges to 
. Thus, regarding 
as the value of 
at
, and 
one has in the cset sense
,
similarly
![$ \sin(+\infty) = [-1,+1] $](T6_files/img14.gif){kind=small}
,
and so on. This leads to an arithmetic system in which exceptions
do not occur, but where point inputs can produce set outputs.
There are subtle difficulties associated with this programme. How
are set-valued constants to be interpreted? For instance, does it
make sense to define a function by
![$f(x) = \frac{[1,2]}{x +
[1,2]}$](T6_files/img15.gif){kind=small}
? When we see the expression , how do we know to
interpret it as the function 
evaluated at ,
and ?
The talk will address these and related issues.
Multiple Precision Interval Arithmetic and Application to Linear Systems
Nathalie Revol (INRIA, LIP, École Normale Supérieure de Lyon, France)Abstract: Introduction to MPFI. Interval arithmetic provides guaranteed results: it encloses every value or result in an interval, and it computes with these intervals. However, the resulting intervals may grow as the computations proceed. To obviate this swelling, contracting iterative methods are favoured. With such methods, the computing precision becomes a limiting factor. This observation led us to propose a library for arbitrary precision interval arithmetic, Multiple Precision Floating-point Interval (MPFI) arithmetic library, built upon Multiple Precision Floating-point Reliable arithmetic (MPFR, www.mpfr.org). MPFI is developed by N. Revol and F. Rouillier in C and can be freely downloaded from www.ens-lyon.fr/~nrevol/.
Applications. Some algorithms have been developed using MPFI. A first algorithm isolates the real roots of a polynomial using a multiple precision interval arithmetic in the Uspensky (or rather Vincent) algorithm to avoid time-consuming exact computations. A second one is the adaptation of the interval Newton algorithm to this arithmetic. The Interval Newton algorithm encloses the real roots of a function and may also determine the existence and uniqueness of these roots in the returned enclosing intervals. The proposed algorithm additionally allows to enclose the roots with arbitrary accuracy.
Linear systems. Solving a linear system
with a matrix 
and a vector 
,
both with interval components, amounts to determining an
enclosure of
.
Gauss-Seidel iteration, applied to the pre-processed system
with 
a point matrix, is often
used. This method is called the Hansen-Sengupta algorithm. When this
iteration can be made contracting, it is a method of choice for
interval arithmetic and also for arbitrary precision interval
arithmetic. Another linear system comes from signal
processing: determine the dynamics of an IIR filter. This problem
can be written as an iteration similar to Gauss-Seidel. We will
present some preliminary results on this problem.
This type of iteration may be comparable with the technique of elimination of division as presented in Strassen, 1973, which is classical in symbolic computations.
From Intervals to Taylor Models: A Numeric-Symbolic Approach to Validated Computation
Markus Neher (Universität Karlsruhe, Germany)Abstract: Interval arithmetic has been widely used in enclosure methods for almost 40 years. Today, it is a well established tool for the calculation of rigorous error bounds for many problems in numerical analysis.
However, interval arithmetic suffers from two drawbacks: the dependency problem and the so-called wrapping effect. Both can cause an overestimation of the solution set of a given problem, so that the computed error bounds may become over-pessimistic in practical calculations.
To reduce the overestimation of the true error, Taylor models have been developed by Berz and his group since the 1990s. A Taylor model of a function f on an interval X consists of the Taylor polynomial p of order n of f and an interval remainder term I, which encloses the approximation error f-p on X. In computations that involve f, the function is then replaced by p+I. The polynomial part is propagated by symbolic calculations, whereas the interval remainder term encloses all truncation and roundoff errors that appear in the computation. Thus, Taylor models can be regarded as a symbiosis of a computer algebra method and interval arithmetic.
Software implementations of Taylor models have been applied to a variety of problems, such as global optimization problems, validated multidimensional integration, or the solution of ODEs and DAEs.
Our talk will present an introduction to Taylor models and discuss some open problems.
Pictures from Proofs: Sound Graphing Algorithms
Jeff Tupper (University of Toronto, Canada)Abstract: Given just a picture of a relation, what can we deduce about the relation? If the picture was produced by a typical equation graphing program then almost nothing can be deduced as such pictures contain, by themselves, very little useful information. This clearly could be improved upon. I begin by offering some simple semantics for pictures of relations. After discussing some of the limitations of these semantics, I will outline some algorithms. Much of this work is embodied in GrafEq, which is available from www.peda.com/grafeq.
Interval Arithmetic in the Multibody Modeling System MOBILE
Ekaterina Auer (University of Duisburg-Essen)Abstract: We show how a variety of interval algorithms found their use in an important area of applied physics, multibody systems' modeling, and in particular, in the multibody modeling program MOBILE. The talk acquaints the audience with the key features of this open source software (e.g. its object-oriented approach resulting in usage of state objects and transmission elements for modeling of arbitrary mechanical systems), outlines the main advantages of applying interval arithmetic concepts to it (e.g. an opportunity to implement new kinds of transmission elements), and concentrates on interval modeling of dynamics, which is an inherent part of almost all multibody simulations. In the latter case, the strategies to overcome difficulties with integration of an interval initial value problem solver into MOBILE are described and as a result, its interval extension enhanced with such a solver (based on VNODE) is presented. The functionality of the above ways of intervals' application is shown on some examples. We provide insight into techniques used to enhance already existing modeling software with interval arithmetic concepts.
ALIAS: A Library Mixing Interval Analysis and Computer Algebra
Yves Papegay (INRIA Sophia Antipolis, France)Abstract: ALIAS is a C++ library of algorithms that deal with systems of equations and inequalities. Most of these algorithms are based on interval analysis, but some of them are related to constraint programming methods, and a few others perform symbolic computations. The scope of ALIAS includes algebraic expressions and also expressions involving intervals. The library provides tools for a wide range of problems including finding an approximation of the real roots of a 0-dimensional system, giving bounds of the roots of an univariate polynomial, and performing global optimization of a function with interval coefficients.
The Role of Symbolic Computation in the SIAM/Oxford 100-Digit Challenge
Stan Wagon (Macalester College, St. Paul, MN, USA)Abstract: The challenge of the title consisted of ten computing problems (available from www.siam.org/siamnews/01-02/challenge.pdf) posed by L. N. Trefethen, who offered a cash prize for the best solutions. The event attracted 94 teams from 25 countries. The problems were numerical in nature, but symbolic computing was able to play an important, and sometimes surprising, role in about half of them. Interval arithmetic provides both an algorithm and verification for the global optimization problem of problem 4; intervals are also useful for problem 2, as a way to control the exposure to excessive rounding error. For problem 9, computer integration plays a surprising role. Symbolic work yielded interesting results in several of the other problems too, such as 6, 7, and 10. The important moral is that symbolic computation and interval methods can be very important in work on problems that are ostensibly purely numerical.