Skip to main content
Top

1988 | Book

Scientific Computation with Automatic Result Verification

Editors: Prof. Dr. Ulrich Kulisch, Prof. Dr. Hans J. Stetter

Publisher: Springer Vienna

Book Series : Computing Supplementum

insite
SEARCH

About this book

Scientific Computation with Result Verification has been a persevering research topic at the Institute for Applied Mathematics of Karlsruhe University for many years. A good number of meetings have been devoted to this area. The latest of these meetings was held from 30 September to 2 October, 1987, in Karlsruhe; it was co-sponsored by the GAMM Committee on "Computer Arithmetic and Scientific Computation". - - This volume combines edited versions of selected papers presented at this confer­ ence, including a few which were presented at a similar meeting one year earlier. The selection was made on the basis of relevance to the topic chosen for this volume. All papers are original contributions. In an appendix, we have supplied a short account of the Fortran-SC language which permits the programming of algorithms with result verification in a natural manner. The editors hope that the publication of this material as a Supplementum of Computing will further stimulate the interest of the scientific community in this important tool for Scientific Computation. In particular, we would like to make application scientists aware of its potential. The papers in the second chapter of this volume should convince them that automatic result verification may help them to design more reliable software for their particular tasks. We wish to thank all contributors for adapting their manuscripts to the goals of this volume. We are also grateful to the Publisher, Springer-Verlag of Vienna, for an efficient and quick production.

Table of Contents

Frontmatter

Automatic Result Verification

Automatic Result Verification
Abstract
Automatic Result Verification. As an introduction to the following articles, we explain the meaning of automatic result verification as a tool in Scientific Computation; then we shortly sketch its principal methods and put the papers of the volume into a common perspective.
U. Kulisch, H. J. Stetter

Numerical Methods with Result Verification

Frontmatter
A Method for Producing Verified Results for Two-Point Boundary Value Problems
Summary
A Method for Producing Verified Results for Two-Point Boundary Value Problems. This paper presents algorithms for solving second order two-point boundary value problems which yield existence proofs and two-sided bounds (EB-algorithms) The algorithms are composed of two numerical procedures as sub-algorithms, an approximation procedure A for calculating approximate solutions of certain boundary value problems, and an estimation procedure E for calculating bounds of certain continuous functions. Conditions (on the given boundary value problems) are formulated such that the EB-algorithms can be carried out, if these conditions are satisfied and procedures A and E of sufficient accuracy are available.
Johann Schröder
A Kind of Difference Methods for Enclosing Solutions of Ordinary Linear Boundary Value Problems
Summary
A Kind of Difference Methods for Enclosing Solutions of Ordinary Linear Boundary Value Problems. In [5] a method is described, how to build algorithms for enclosing the solution u(x) of ordinary linear differential problems by an interval polynomial Y(x). In this paper the method is used for enclosing the values u(x i) of boundary value problems at equidistant points x i by intervals Y i. The Y i are determined by a system of linear equations which, for simple problems, is tridiagonal and can be solved easily.
Johannes Weissinger
A Self-Validating Method for Solving Linear Programming Problems with Interval Input Data
Abstract
A Self-Validating Method for Solving Linear Programming Problems with Interval input Data. Linear programming problems are very important in many practical applications. They are usually solved by the simplex method. The computational results are, in general, good approximations to the solution of the problem. However, in some cases the computed approximation may be wrong due to round-off and cancellation errors. In practice it occurs frequently that the input data of a linear programming problem are not known exactly but are afflicted with tolerances. In this case it has to be precisely defined what a “solution” to such a problem is. A sensitivity or postoptimality analysis is necessary.
In the following a method for linear programming problems with interval input data is described which computes guaranteed lower and upper bounds for all optimal vertices and the optimal value. The method controls rigorously all round-off errors and gives an automatic sensitivity analysis. As an example a diet problem is treated to demonstrate how the method in principle works.
Christian Jansson
Enclosing the Solutions of Systems of Linear Equations by Interval Iterative Processes
Summary
Enclosing the Solutions of Systems of Linear Equations by Interval Iterative Processes. We present a class of iterative processes to enclose the solutions of systems of linear equations Ax=b,where the coefficients of A and b are allowed to vary within given intervals. The methods are based on so-called M-splittings and contain many standard iterative processes. We derive results concerning the feasibility, the global convergence, the quality of enclosure and the speed of convergence.
Günter Mayer
Errorbounds for Quadratic Systems of Nonlinear Equations Using the Precise Scalar Product
Abstract
Errorbounds for Quadratic Systems of Nonlinear Equations Using the Precise Scalar Product. For nonlinear systems of quadratic equations we show how the precise scalar product can be used in order to compute and to improve inclusions for a solution. Our main interest is the special case which comes from the generalized eigenvalue problem.
G. Alefeld
Inclusion of Eigenvalues of General Eigenvalue Problems for Matrices
Abstract
Inclusion of Eigenvalues of General Eigenvalue Problems for Matrices. In this paper, a procedure for calculating bounds to eigenvalues of general matrix eigenvalue problems is proposed. The procedure is based on Temple quotients and their generalization by Lehmann, in connection with interval arithmetic. Numerical examples illustrate the fact that bounds for multiple or clustered eigenvalues can be calculated as well.
Henning Behnke
Verified Inclusion for Eigenvalues of Certain Difference and Differential Equations
Abstract
Verified Inclusion for Eigenvalues of Certain Difference and Differential Equations. The paper presents a method for obtaining accurate verified inclusions of eigenvalues. Second order difference and differential equations with a boundary condition at infinity can be treated. Using interval arithmetic and the exact scalar product very accurate inclusions can be obtained even for ill conditioned problems where classical methods fail.
Martin Ohsmann

Applications in the Technical Sciences

Frontmatter
VIB — Verified Inclusions of Critical Bending Vibrations
Summary
VIB — Verified Inclusions of Critical Bending Vibrations. In a joint project of the Institutes of Applied Mathematics and Technical Mechanics of the University of Karlsruhe a program system was developed for the calculation and animation of the bending vibrations of rotating shafts. The mechanical model of the rotor is based on the Bernoulli-Euler beam and evaluated by means of transfer matrices. By means of verified inclusions the eigenvalues can be determined with high accuracy up to high speeds of rotation.
A. Ams, W. Klein
Stability Test for Periodic Differential Equations on Digital Computers with Applications
Abstract
Stability Test for Periodic Differential Equations on Digital Computers with Applications. For linear and nonlinear ordinary initial value problems with periodic coefficient functions, a sufficient enclosure test is derived. The successful execution on digital computers guarantees the stability of all solutions in the linear case or the boundedness of all perturbed solutions starting in an admitted finite neighborhood of the initial data in the nonlinear case. Presented applications are concerned with vibrations of gear drives. An implementation of the test using FORTRAN and ACRITH is discussed.
Dietrich Cordes
The Periodic Solutions of the Oregonator and Verification of Results
Abstract
The Periodic Solutions of the Oregonator and Verification of Results. The Oregonator is a numerically ill-conditional mathematical model in chemical kinetics involving nonlinear highly stiff ODEs. For the (stiffly coupled) “simplified Oregonator”, periodic solutions in the phase plane can be confined to an annular closed strip S whose lateral extension can be made negligibly small within graphical accuracy. This result of the “Karlsruhe enclosure methods” has been obtained with a simultaneous verification of the existence of periodic solutions in S, making use of index theory and th Poincaré-Bendixson theory.
E. Adams, A. Holzmüller, D. Straub
On Arithmetical Problems of Geometric Algorithms in the Plane
Abstract
On Arithmetical Problems of Geometric Algorithms in the Plane. In the last years computational geometry has achieved a mature status within the framework of algorithms and data structures. Hundreds of new solutions for geometric problems are avaiable now. Corresponding algorithms are distinguished by clever data structures, rigorous proofs and nontrivial complexity analysis.
The application of the new algorithms in real systems is less successful. One of the reasons for this phenomenon is given by the numerical problems occurring during execution of nearly all geometric algorithms.
This paper gives an introduction to the latter class of problems in geometric algorithms The scan-line algorithm for computing all pairs of intersecting line segments in the plane serves as model example for the isolation of basic operations which have to be handled numerically correct. It can be shown that the optimal evaluation of arithmetic expressions provides a solid tool for the solution of the problems.
Th. Ottmann, G. Thiemt, Ch. Ullrich

Improving the Tools

Frontmatter
Precise Evaluation of Polynomials in Several Variables
Abstract
Precise Evaluation of Polynomials in Several Variables. In this paper an algorithm is presented which computes the values of polynomials in several variables with high accuracy when the computation is done in a floating-point system using a precise scalar product and directed rounding. Furthermore the value of the polynomial is enclosed in narrow bounds. Numerical examples demonstrate the high precision of the results and show that traditional algorithms (e g nested Homer’s schemes) can fail completely for this problem. The algorithm presented here is a generalization of Böhm’s algorithm for one-dimensional polynomials, [4], [5].
Rudolf Lohner
Evaluation of Arithmetic Expressions with Guaranteed High Accuracy
Abstract
Evaluation of Arithmetic Expressions with Guaranteed High Accuracy. The advantage of having available an exact scalar product in numerical computations has already been mentioned by many authors. In this paper we use this tool to develop an algorithm for the evaluation of rational expressions in several variables with high guaranteed accuracy. An extension for complex expressions, vectormatrix expressions and expressions with standard functions and interval arguments is also given.
Hans Christoph Fischer, Günter Schumacher, Rudolf Haggenmüller
Standard Functions for Real and Complex Point and Interval Arguments with Dynamic Accuracy
Abstract
Standard Functions for Real and Complex Point and Interval Arguments with Dynamic Accuracy. Algorithms for the high-accuracy evaluation of the real and complex standard functions ex, sin x, cos x, tan x, cot x, sinh x, cosh x, tanh x, coth x, \( \sqrt x \) and x2 for point and interval arguments in general floating-point screens are treated. In case of interval functions an inclusion of the exact result is computed. The number of guard digits necessary to obtain this result in general floating-point screens is specified for each function. The error bounds stated in this paper are proved in [3]. The missing inverse standard functions can be found in short in [6] or more detailed in [7].
Klaus D. Braune
Inverse Standard Functions for Real and Complex Point and Interval Arguments with Dynamic Accuracy
Abstract
Inverse standard functions for real and complex point and interval arguments with dynamic accuracy. Algorithms to compute inverse standard functions to arbitrary accuracy with safe error bounds are given. Not only approximation errors but also all possible rounding errors are considered. The desired accuracy of the function as well as the base of the number system used are parameters of the error formula. For implementation it is only assumed that the four elementary arithmetic operations are performed with a certain number of correct digits, which is given by the error formula and little higher than the desired number of correct digits of the function value. The interval routines are constructed out of the point routines considering the monotonicity behaviour of the functions. The ambiguity of the complex functions is briefly discussed (for a detailed discussion see [4] and [5]).
Walter Krämer
Inclusion Algorithms with Functions as Data
Abstract
Inclusion Algorithms with Functions as Data. An algorithm can only use finite information about data, hence a large set of data functions may look alike to a given inclusion algorithm which would then have to include the corresponding result set. It is examined how this dilemma may be overcome by the specification of function data through arithmetic expression strings.
H. J. Stetter

Appendix

Frontmatter
FORTRAN-SC A Study of a FORTRAN Extension for Engineering/Scientific Computation with Access to ACRITH
Abstract
FORTRAN-SC. A Study of a FORTRAN Extension for Engineering/Scientific Computation with Access to ACRITH. A new programming language called FORTRAN-SC is presented which is closely related to FORTRAN 8x. FORTRAN-SC is a FORTRAN extension with emphasis on engineering and scientific computation. It is particularly suitable for the development of numerical algorithms which deliver highly accurate and automatically verified results. The language allows the declaration of functions with arbitrary result type, operator overloading and definition, as well as dynamic arrays. It provides a large number of predefined numerical data types and operators. Programming experiences with the existing compiler have been very encouraging. FORTRAN-SC greatly facilitates programming and in particular the use of the ACRITH subroutine library [14], [15].
J. H. Bleher, S. M. Rump, U. Kulisch, M. Metzger, Ch. Ullrich, W. Walter
Metadata
Title
Scientific Computation with Automatic Result Verification
Editors
Prof. Dr. Ulrich Kulisch
Prof. Dr. Hans J. Stetter
Copyright Year
1988
Publisher
Springer Vienna
Electronic ISBN
978-3-7091-6957-5
Print ISBN
978-3-211-82063-6
DOI
https://doi.org/10.1007/978-3-7091-6957-5