Skip to main content
main-content

Über dieses Buch

The articles in this book give a comprehensive overview on the whole field of validated numerics. The problems covered include simultaneous systems of linear and nonlinear equations, differential and integral equations and certain applications from technical sciences. Furthermore some papers which improve the tools are included. The book is a must for scientists working in numerical analysis, computer science and in technical fields.

Inhaltsverzeichnis

Frontmatter

On a Unified Concept of Mathematics

Abstract
On a Unified Concept of Mathematics. Mathematics is not simply a branch of science, but the unique and conclusive means of expressing and solving any problem in any field whatever. In this paper I wish to submit some thoughts justifing my belief in the unification of Mathematics. Besides that, I make a proposal for replacement of the structureblock for questions (with two or more answers) in structuregrams, which not only makes the structuregrams more representative and comprehensive but also corrects certain shortcomings and makes them more adapted to the structure of programming languages.
N. Apostolatos

A General Approach to a Class of Single-Step Methods for the Simultaneous Inclusion of Polynomial Zeros

Abstract
A General Approach to a Class of Single-Step Methods for the Simultaneous Inclusion of Polynomial Zeros. A general model for the construction of certain classes of simultaneous single-step inclusion methods for polynomial roots is presented. This approach makes use of interval Operations in order to guarantee the inclusion of the zeros. It is shown how the order of convergence of these methods can be determined. Some methods of the literature are special cases of this model and new methods can be constructed.
L. Atanassova, J. Herzberger

On Some Properties of an Interval Newton Type Method and its Modification

Abstract
On some Properties of an Interval Newton Type Method and its Modification. Considered is an interval iterative Newton type method for enclosing a real simple root of the nonlinear equation f(x) = 0 in a given interval X. The method has a simple formulation in terms of extended interval arithmetic. Cubic convergence of the method is proved assuming that f possesses a Lipschitzian second derivative which vanishes at the root of the equation. A modification of the method with higher order of convergence is proposed. An algorithm with result verification is formulated and some numerical experiments are reported.
N. S. Dimitrova

Verified Solution of the Integral Equations for the Two-Dimensional Dirichlet and Neumann Problem

Abstract
Verified Solution of the Integral Equations for the Two-Dimensional Dirichlet and Neumann Problem. In this article selfvalidating numerical methods for including the Solution of the Dirichlet and Neumann problem in the plane are constructed. Here an additional error analysis to estimate roughly the quality of the computed Solution is obsolete. The so-called verification or E-methods compute a mathematically guaranteed enclosure for the true Solution of these problems.
Hans-Jürgen Dobner

Two-Stage Interval Iterative Methods

Abstract
Two-Stage Interval Iterative Methods. We present an interval version of the well-known two-stage iterative methods to approximate solutions of linear systems of equations. By using interval arithmetical tools we are able to verify such solutions within interval bounds. The method can also guarantee the non-singularity of the underlying coefficient matrices of the systems. We prove criteria of convergence for the method and we report on an optimality result for the enclosure.
A. Frommer, G. Mayer

Convergence Acceleration for Some Rootfinding Methods

Abstract
Convergence Acceleration for Some Rootfinding Methods. We present simple, efficient extrapolation formulas to accelerate the convergence of super-linearly convergent sequences. Applications are given for some rootfinding methods such as Newton’s method and the secant method. Numerical examples are given showing the effectiveness of the extrapolation formulas.
Weimin Han, F. A. Potra

A Program for Enclosing Cumulative Binomial Probabilities

Abstract
A Program for Enclosing Cumulative Binomial Probabilities. Based on a simple theoretical algorithm for Computing cumulative binomial probabilities, a PASCAL-SC program for enclosing such probabilities is derived. In several real life problems the high quality of the computed enclosures is demonstrated.
G. Heindl

Effective Evaluation of Hausdorff Distances for Finite Unions of Hyperrectangles

Abstract
Effective Evaluation of Hausdorff Distances for Finite Unions of Hyperrectangles. Based on the usual Operations, relations and evaluations of function values for axis-parallel hyperrectangles, the corresponding objects for finite sets of hyperrectangles resp. their unions can be defined and implemented in a natural way. Algebraic properties remain valid. The aim of this paper is to give also methods for an effective evaluation of lower and upper distances as well as of Hausdorff distances for such sets. On this basis the distances and similarity and congruency grades for each pair of nonempty bounded subsets of ℝ n are approximately computable, and the convergence behaviour of general set-valued iteration processes can be investigated.
K.-U Jahn

A Verified Computation of Fourier-Representations of Solutions for Functional Equations

Abstract
A Verified Computation of Fourier-Representations of Solutions for Functional Equations. A generalisation of the functoid concept for the representation of functions in L 2(—π, π), in particular for periodic functions, is introduced. In such so-called hyper functoids the spectrum of a function can be included with arbitrary accuracy. This calculus can be used for example to solve periodical differential and integral equations. An example shows the computed inclusion of the spectrum of a solution.
E. Kaucher, Ch. Baumhof

The Cluster Problem in Global Optimization: the Univariate Case

Abstract
The Cluster Problem in Global Optimization the Univariate Case. We consider a branch and bound method for enclosing all global minimizers of a nonlinearC 2 or C 1 objective function. In particular, we consider bounds obtained with interval arithmetic, along with the “midpoint test,” but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable Cluster of intervals around each minimizer. In this article, we analyze this problem in the one dimensional case. Theoretical results are given which show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.
B. Kearfott, K. Du

Developing Expert Systems for Validating Numerics

Abstract
Developing Expert Systems for Validating Numerics. The selection of an appropriate method out of a software library and its application to a given problem require a lot of expert knowledge. Usually there are more than one mathematically equivalent self-validating methods with completely different behavior on a Computer. Therefore only a quantitative valuation of the available software modules rather than qualitative can lead to a satisfactory result. First the design of a shell suitable for the derivation of expert systems dealing with different domains of numerics is discussed. The main idea is the decoupling of the logic and the domain-specific part allowing an easy adaptation to a new field or extension with additional methods and selection criteria. Then a functional model for knowledge acquisition and representation under quantitative aspects is elaborated and enhanced by considering execution time problems arising from portations. The procedure is demonstrated by a comprehensive example dealing with two methods for systems of linear equations.
S. König, C. P. Ullrich

Computation of Interval Bounds for Weierstrass’ Elliptic Function ℘(z)

Abstract
Computation of Interval Bounds for Weierstrass’ Elliptic Function ℘(z. A method to enclose the values of Weierstrass’ elliptic function ℘(z) = ℘(z|g 2,g 3) for arbitrary complex invariants g 2,g 3 or arbitrary given zeros of the characteristic polynomial (arbitrary period lattices) is presented. The function is approximated by its truncated Laurent series at zero. An error bound is derived for the remainder term. If necessary, the periodicity of ℘, the homogeneity relations and the addition formulas are used to perform the reduction of the argument and the corresponding adaptation of the result.
Walter Krämer, Bertram Barth

Solving Nonlinear Elliptic Problems with Result Verification Using an H -1 Type Residual Iteration

Abstract
Solving Nonlinear Elliptic Problems with Result Verification Using an H -1 Type Residual Iteration. In this paper, we consider a numerical technique to verify the solutions with guaranteed error bounds for nonlinear elliptic boundary value problems. Using the C° finite element solution and explicit error estimates for the Poisson equation, we construct, in a computer, a set of functions which satisfies the hypothesis of Sadovskii’s fixed point theorem for confdensing map on a certain Sobolev space. Particularly, we propose an H -1 type residual iteration method which improves the ability of verification. A numerical example which confirms the usefulness of the method is presented.
Mitsuhiro T. Nakao

The Wrapping Effect, Ellipsoid Arithmetic, Stability and Confidence Regions

Abstract
>The Wrapping Effect, Ellipsoid Arithmetic, Stability and Confidence Regions. The wrapping effect is one of the main reasons that the application of interval arithmetic to the enclosure of dynamical systems is difficult. In this paper the source of wrapping is analyzed algebraically and geometrically. A new method for reducing the wrapping effect is proposed, based on an interval ellipsoid arithmetic.
Applications are given to the verification of stability regions for nonlinear discrete dynamical systems and to the computation of rigorous confidence regions for nonlinear functions of normally distributed random vectors.
A. Neumaier

Validated Solution of Large Linear Systems

Abstract
Validated Solution of Large Linear Systems. Some new methods will be presented for computing verified inclusions of the solution of large linear systems. The matrix of the linear system is typically of sparse or band structure. There are no prerequisites for the matrix, such as being M-matrix, Symmetric, positive definite or diagonally dominant. For general band matrices of lower, Upper bandwidth p, q of dimension n the Computing time is n · (pq + p 2 + q 2). Examples with up to 1.000.000 unknowns will be presented.
Siegfried M. Rump

The Interval Buneman Algorithm for Arbitrary Block Dimension

Abstract
The Interval Buneman Algorithm for Arbitrary Block Dimension. The interval arithmetic Buneman algorithm is a “fast solver” for a class of block tridiagonal systems with interval coefficients. In the present paper, we consider a modification for arbitrary block dimension and we discuss its inclusion properties.
H. Schwandt

On the Existence and the Verified Determination of Homoclinic and Heteroclinic Orbits of the Origin for the Lorenz Equations

Abstract
On the Existence and the Verified Determination of Homoclinic and Heteroclinic Orbits of the Origin for the Lorenz Equations. For suitable choices of the parameters, the Lorenz ODEs possess (i) stable and unstable manifolds of the stationary point 0 at the origin, (ii) a homoclinic orbit of 0, and (iii) a heteroclinic orbit connecting a periodic orbit with 0. With the exception of only partial results regarding (iii), all addressed orbits are enclosed and verified as follows: (a) enclosures of truncated series expansions and of their remainder terms yield guaranteed starting intervals at some distance from 0, whose width is not more than two units of the last mantissa digit, and (b) a step-size controlled version of Lohner’s enclosure algorithm for IVPs yields the continuations.
H. Spreuer, E. Adams

Verification in Computer Algebra Systems

Abstract
Verification in Computer Algebra Systems. In this paper, we have attempted to demonstrate that the question of condition, i.e. of the sensitivity of results w.r.t. perturbations of data, may play a role in algebraic algorithms, even if they are carried out in rational arithmetic. Poor condition is traced to a near-degeneracy of the situation specified by the data. Thus in a process called verification in this context, the presence of a genuinely degenerate problem near the specified problem should be discovered before or during the execution of the algorithm; the algorithm should switch to a stable modification in this case. Such modified versions are obtained by regarding the specified problem as a perturbation of the nearby degenerate one. Finally, it is indicated how these ideas may also lead to safe implementations of algebraic algorithms in floating-point arithmetic.
These ideas are developed considering the integration of rational functions, the choice of basis in multivariate polynomial interpolation, and the computation of zeros of multivariate polynomial systems.
H. J. Stetter

FORTRAN-XSC A Portable Fortran 90 Module Library for Accurate and Reliable Scientific Computing

Abstract
FORTRAN-XSC: A Portable Fortran 90 Module Library for Accurate and Reliable Scientific Computing. Fortran 90, the new international Fortran Standard released in 1991 [14], offers a multitude of new features and enhancements compared with FORTRAN 77 [2]. However, numerical problems persist since the new standard contains no accuracy requirements for the arithmetic operators and mathematical functions, making reliable computation extremely difficult. Even with IEEE arithmetic [3], results may vary widely depending on code optimization and vectorization [9, 28].
FORTRAN-XSC, a portable Fortran 90 module library, aims at providing a flexible and versatile toolbox for analyzing and improving the accuracy and reliability of numerical application programs. It is particularly suited for the design of algorithms delivering automatically verified results of high accuracy. The library features accurate scalar, vector and matrix arithmetic for real and complex numbers and intervals, conversion routines for numeric constants, fully dynamic multiple precision arithmetic, and much more. The result of every operation is optimal (accurate to 1 ulp) with respect to the rounding selected by the user.
W. V. Walter

Implementation of Accurate Matrix Multiplication on the CM-2

Abstract
Implementation of Accurate Matrix Multiplication on the CM-2 In this paper we report about a parallel implementation of matrix multiplication in the sense of Kulisch’s arithmetic definition. Using the architectural support of the CM-2 the prize for accuracy compared to rounded Software arithmetic is not too high.
J. Wolff v. Gudenberg
Weitere Informationen