Perspectives on Enclosure Methods

Frontmatter

Proving Conjectures by Use of Interval Arithmetic

Abstract

Machine interval arithmetic has become an important tool in computer assisted proofs in analysis. Usually, an interval arithmetic computation is just one of many ingredients in such a proof. The purpose of this contribution is to highlight and to summarize the role of interval arithmetic in some outstanding results obtained in computer assisted analysis. ‘Outstanding’ is defined through the observation that the importance of a mathematical result is at least to some extent indicated by the fact that it has been formulated as a ‘conjecture’ prior to its proof.

Andreas Frommer

Advanced Arithmetic for the Digital Computer — Interval Arithmetic Revisited

Abstract

This paper deals with interval arithmetic and interval mathematics. Interval mathematics has been developed to a high standard during the last few decades. It provides methods which deliver results with guarantees. However, the arithmetic available on existing processors makes these methods extremely slow. The paper reviews a number of basic methods and techniques of interval mathematics in order to derive and focus on those properties which by today’s knowledge could effectively be supported by the computer’s hardware, by basic software, and by the programming languages. The paper is not aiming for completeness. Unnecessary mathematical details, formalisms and derivations are left aside whenever possible. Particular emphasis is put on an efficient implementation of interval arithmetic on computers.

Ulrich W. Kulisch

Highly Accurate Verified Error Bounds for Krylov Type Linear System Solvers

Abstract

Preconditioned Krylov subspace solvers are an important and frequently used technique for solving large sparse linear systems. There are many advantageous properties concerning convergence rates and error estimates. However, implementing such a solver on a computer, we often observe an unexpected and even contrary behavior.

Axel Facius

Elements of Scientific Computing

Abstract

In the past decades, computer performance has increased dramatically and is still doing so, putting tremendous power at the fingertips of every computer user. Many of these capabilities are used for new and complex functions and for a (hopefully) better user interface, but also sometimes wasted for questionable gadgets. Unfortunately, in the same time frame little has been done to increase the confidence in the answers computers produce in the scientific field, because, so far, computer designers are much more motivated by mass market needs than by scientific requirements. With the circuit densities achievable on computer chips today and with ‘clean’ architectures already in place, only very little additional effort would have to be spent to provide the means to allow computers to deliver results with guamntees, i.e. with verified accuracy.

J. Hartmut Bleher

The Mainstreaming of Interval Arithmetic

Abstract

Interval arithmetic and validated arithmetic methods are almost unknown in the United States, and are absent in the federally funded High Performance Computing efforts of the last twenty years. The focus has been on ßoatingpoint operations per second (FLOPS) to the exclusion of any concern for the correctness of the result. However, the treaty-mandated need to validate nuclear weapons without physical experiments (the ASCI program) may prove to be the key to changing this. Radiation transport provides an example where bounded intervals can provide much more useful answers than existing point methods, whether they are used for modeling nuclear reactions or for computer-generated graphics. This example, and others, can be used to illustrate a general strategy that will allow us to move interval arithmetic into the mainstream of high-speed computing.

John L. Gustafson

Bounds for Eigenvalues with the Use of Finite Elements

Abstract

Verified upper and lower bounds for the smallest eigenvalues of eigenvalue problems with self-adjoint partial differential equations are computed. Upper bounds are obtained by the Rayleigh-Ritz method, a suitable Goerisch method provides lower bounds. The trial functions are constructed with the use of finite elements. All computations are carried out with intervaI arithmetic thus the results are protected against rounding errors. Numerical results are given for the L-shaped membrane.

Henning Behnke, Ulrich Mertins

Algorithmic Differencing

Abstract

An algorithmic representation of a function is a step-by-step specification of its evaluation in terms of known operations and functions, such as a computer program. In addition to function values, the algorithmic representation can be used to compute related quantities such as derivatives of the function. A process similar to automatie (or algorithmic) differentiation will be applied to obtain differences and divided differences of functions. Advantages of this approach are that it often reduces the sometimes catastrophic cancellation errors in computation of differences and divided differences and provides numerical convergence of divided differences to derivatives.

Louis B. Rall, Thomas W. Reps

A Comparison of Techniques for Evaluating Centered Forms

Abstract

Second-order enc10sures for a function’s range can be computed with centered forms, which involve a so-called slope vector. In this paper we discuss several techniques for determining such vectors and compare them with respect to tightness of the resulting enc1osure. We advocate that a two-stage slope vector computation with symbolic preprocessing is optimal.

Bruno Lang

On the Limit of the Total Step Method in Interval Analysis

Abstract

We derive a linear system for the midpoint and the radius of the limit [xl^* of the interval total step method [x]^k+1 = [A][x]^k +[b] provided that p(|[A]|) < 1. The coefficients of this system are formed by lower and upper bounds of the input intervals, their choice depends on the position of the components of [x](vn*) with respect to zero. For particular input data this choice can be made without knowing [x](vn*). For nonnegative [A] the coefficients are determined by solving at most n + 1 real linear systems.

Günter Mayer, Ingo Warnke

How Fast can Moore’s Interval Integration Method Really be?

Abstract

Moore’s interval integration method which uses only function evaluations of the integrant is interpreted as an approximation of the fundamental integration by Riemann-sums. In this way we can estimate the speed of convergence of this method and it is shown that its convergence factor of its linear convergence rate is bounded to below. This lower bound is shown to be sharp in the sense that there is a wide dass of functions for which it cannot be improved. In particular this is true for all rational functions only considered by Moore.

Jürgen Herzberger

Numerical Verification and Validation of Kinematics and Dynamical Models for Flexible Robots in Complex Environments

Abstract

We give a survey on well-known and new interval methods and algorithms with result verification in the field of robotics. In particular we present optimal linear controller design, reliable geometric computations for distances between a point and a non-convex polyhedron or a NURBS curve, path planning, and failure detection with fault tree logic for flexible robots in complex environments. We also present an extension of a multi body modelling and simulating tool, which provides error propagation control and reliable numerical algorithms.

Wolfram Luther, Eva Dyllong, Daniela Fausten, Werner Otten, Holger Traczinski

On the Ubiquity of the Wrapping Effect in the Computation of Error Bounds

Abstract

Historically, the wrapping effect was discovered and named in the context of solving ordinary initial value problems in interval arithmetic. Its explanation was obviously geometric: rotations of interval vectors enclosing the set of solutions catch excessive points into the enclosure which may eventually ‘explode’ exponentially. Also discrete dynamical systems share this undesirable behaviour. In the literature the wrapping effect has been discussed primarily in this context.

Rudolf J. Lohner

A New Perspective on the Wrapping Effect in Interval Methods for Initial Value Problems for Ordinary Differential Equations

Abstract

The problem of reducing the wrapping effeet in interval methods for initial value problems for ordinary differential equations has usually been studied from a geometrie point of view. We develop a new perspeetive on this problem by linking the wrapping effeet to the stability of the interval method. Thus, redueing the wrapping effect is related to finding a more stable seheme for advaneing the solution. This allows us to exploit eigenvalue teehniques and to avoid the eomplieated geometrie arguments used previously.

Nedialko S. Nedialkov, Kenneth R. Jackson

A Guaranteed Bound of the Optimal Constant in the Error Estimates for Linear Triangular Elements

Abstract

In the previous paper([6]), we formulated a numerical method to get a guaranteed bound of the optimal constant in the error estimates with linear triangular elements in R². We describe, in this paper, detailed computational procedures for obtaining a rigorous upper bound of that constant with sufficient sharpness. The numerical verification method for solutions of nonlinear elliptic problems is successfully applied to the present purpose. A constructive error estimate for the triangular element with Neumann boundary condition plays an important role to implement the actual verified computations. Particularly, some special kind of techniques are utilized to improve the computational cost for the algorithm. As a result, we obtained a sufficiently sharp upper bound from the practical viewpoint.

Mitsuhiro T. Nakao, Nobito Yamamoto

Nonsmooth Global Optimization

Abstract

What can interval analysis do for Nonsmooth Global Optimization?

We will answer this quest ion by presenting an overview on pruning techniques based on interval slopes in the context of interval branch-and-bound methods for global optimization. So, this paper is intended to guide interested researchers to future research and improvements or to ways of using the techniques in different contexts.

Dietmar Ratz

Backmatter