Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

1995 | Book

Introduction Read chapter Read first chapter

C++ Toolbox for Verified Computing I

Basic Numerical Problems Theory, Algorithms, and Programs

Authors: Prof. Dr. Ulrich Kulisch, Dr. Rolf Hammer, Dr. Matthias Hocks, Dr. Dietmar Ratz

Publisher: Springer Berlin Heidelberg

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

Our aim in writing this book was to provide an extensive set of C++ programs for solving basic numerical problems with verification of the results. This C++ Toolbox for Verified Computing I is the C++ edition of the Numerical Toolbox for Verified Computing l. The programs of the original edition were written in PASCAL-XSC, a PASCAL eXtension for Scientific Computation. Since we published the first edition we have received many requests from readers and users of our tools for a version in C++. We take the view that C++ is growing in importance in the field of numeri­ cal computing. C++ includes C, but as a typed language and due to its modern concepts, it is superior to C. To obtain the degree of efficiency that PASCAL-XSC provides, we used the C-XSC library. C-XSC is a C++ class library for eXtended Scientific Computing. C++ and the C-XSC library are an adequate alternative to special XSC-Ianguages such as PASCAL-XSC or ACRITH-XSC. A shareware version of the C-XSC library and the sources of the toolbox programs are freely available via anonymous ftp or can be ordered against reimbursement of expenses. The programs of this book do not require a great deal of insight into the features of C++. Particularly, object oriented programming techniques are not required.

Table of Contents

Frontmatter

Introduction

Chapter 1. Introduction
Abstract
This is a reference book for numerical methods with automatic result verification. The methods presented here are practical, reliable, and elegant. We provide theory, algorithmic descriptions, and implementations for methods to solve a number of basic numerical problems in a reliable way. Also, this book can help you to learn how to develop such methods and how to proceed for other problems beyond the scope of the book.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz

Preliminaries

Frontmatter
Chapter 2. The Features of C-XSC
Abstract
In this chapter, we present a brief review of the C-XSC library, a C++ class library for eXtended Scientific Computation. For a complete library reference and examples, refer to [49].
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 3. Mathematical Preliminaries
Abstract
Interval arithmetic is the basic mathematical tool in verified numerical computing. This chapter summarizes the mathematical terms used in this book. After an introduction to real, complex, and extended interval arithmetic, we make some comments on the realization of arithmetics on a digital computer. We also touch on the problem of data conversion. Finally, we point out how to use fixed-point theorems to derive algorithms for verified numerical computing.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz

One-Dimensional Problems

Frontmatter
Chapter 4. Evaluation of Polynomials
Abstract
In this chapter, we consider the evaluation of a polynomial function of a single variable. We usually compute the value of an arithmetic function by replacing each arithmetic operation by its corresponding floating-point machine operation (see Section 3.5). Roundoff errors and cancellations sometimes cause the calculated result to be drastically wrong. For similar reasons, a naive interval evaluation of a polynomial may lead to intervals so large as to be practically useless. Roundoff and cancellation errors are especially dangerous if we are evaluating a function close to a root, as we will see in Chapter 9 when we compute verified enclosures of zeros of polynomials.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 5. Automatic Differentiation
Abstract
In many applications of numerical and scientific computing, it is necessary to compute derivatives of functions. Simple examples are methods for finding the zeros, maxima, or minima of nonlinear functions. There are three different methods to get the values of the derivatives: numerical differentiation, symbolic differentiation, and automatic differentiation.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 6. Nonlinear Equations in One Variable
Abstract
One of the most important tasks in scientific computing is the problem of finding zeros (or roots) of nonlinear functions. In classical numerical analysis, root-finding methods for nonlinear functions begin with an approximation and apply an iterative method (such as Newton’s or Halley’s methods), which hopefully improves the approximation. It is a myth that no numerical algorithm is able to compute all zeros of a nonlinear equation with guaranteed error bounds, or even more, that no method is able to give concrete information about the existence and uniqueness of solutions of such a problem.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 7. Global Optimization
Abstract
We want to find the global minimum in an interval [x] of a function f that may have many local minima. We want to compute the minimum value of f and the point(s) at which the minimum value is attained. This is a very difficult problem for classical methods because narrow, deep valleys may escape detection. In contrast, the interval method presented here evaluates f on a continuum of points, including those points that are not finitely represent able, so valleys, no matter how narrow, are recognized with certainty. Further, interval techniques often can reject large regions in which the optimum can be guaranteed not to lie, so they can be faster overall than classical methods for many problems.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 8. Evaluation of Arithmetic Expressions
Abstract
The evaluation of arithmetic expressions using floating-point arithmetic may lead to unpredictable results due to an accumulation of roundoff errors. As an example, the evaluation of x + 1 − x for x > 1020 using the standard floating-point format on almost every digital computer yields the wrong result 0. Since the evaluation of arithmetic expressions is a basic task in digital computing, we should have a method to evaluate a given expression to an arbitrary accuracy. We will develop such a method for real expressions composed of the operations +, −, ·, and ↑, where ↑ denotes exponentiation by an integer. The method is based on the principle of iterative refinement as discussed in Section 3.8.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 9. Zeros of Complex Polynomials
Abstract
We consider the complex polynomial p: ℂ → ℂ defined by
$$p(z) = \sum\limits_{1 = 0}^n {{p_i}{z^i}} ,{p_i} \in C,i = 0, \ldots ,n,{p_n} \ne 0.$$
(9.1)
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz

Multi-Dimensional Problems

Frontmatter
Chapter 10. Linear Systems of Equations
Abstract
Finding the solution of a linear system of equations is one of the basic problems in numerical algebra. We will develop a verification algorithm for square systems with full matrix based on a Newton-like method for an equivalent fixed-point problem.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 11. Linear Optimization
Abstract
A linear programming problem consists of a linear function to be maximized (or minimized) subject to linear equality and inequality constraints. Any linear program (LP) can be put by well-known transformations into standard form
$$\begin{array}{l} (LP)\begin{array}{*{20}{c}} z&{{c^T}x}&{ = \max }\\ {}&{{A_x}}&{ = b}\\ {}&x&{ \ge 0} \end{array}\\ \mathop \Leftrightarrow \limits_{\max \{ {c^T}x|x \in X\} ,X: = \{ x \in {R^n}|Ax = b,x \ge 0\} ,} \end{array}$$
(11.1)
where A is a real m x n matrix, \( b \in {\mathbb{R}^m},\,c\, \in \,{\mathbb{R}^n}\). The input data of (11.1) are given by the triple \(P = (A,b,c)\, \in \,{\mathbb{R}^{m \cdot n + m + n}}\).
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 12. Automatic Differentiation for Gradients, Jacobians, and Hessians
Abstract
In Chapter 5, we considered automatic differentiation in one variable, but there are also many applications of numerical and scientific computing where it is necessary to compute derivatives of multi-dimensional functions. In this chapter, we extend the concept of automatic differentiation to the multi-dimensional case as given by Rail [72] and many others. We apply well-known differentiation rules for gradients, Jacobians, or Hessians with the computation of numerical values, combining the advantages of symbolic and numerical differentiation. Only the algorithm or formula for the function is required. No explicit formulas for the gradient, Jacobian, or Hessian have to be derived and coded.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 13. Nonlinear Systems of Equations
Abstract
In Chapter 6, we considered the problem of finding zeros (or roots) of nonlinear functions of a single variable. Now, we consider its generalization, the problem of finding the solution vectors of a system of nonlinear equations. We give a method for finding all solutions of a nonlinear system of equations f(x) = 0 for a continuously differentiable function f: ℝn→ ℝn in a given interval vector (box). Our method computes close bounds on the solution vectors, and it delivers information about existence and uniqueness of the computed solutions. The method we present is a variant of the interval Gauss-Seidel method based on the method of Hansen and Sengupta [3], [32], and a modification of Ratz [79]. Our method makes use of the extended interval operations defined in Section 3.3.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Chapter 14. Global Optimization
Abstract
In Chapter 7, we considered the problem of finding the global minimizers of one- dimensional nonlinear functions. Now, we consider its generalization, the problem of finding the global minimizers of multi-dimensional nonlinear functions. Our algorithm is based on the method of Hansen [29]. The algorithm computes enclosures for all global minimizers and for the global minimum value of a twice continuously differentiable function in the interior of a given interval vector.
Ulrich Kulisch, Rolf Hammer, Matthias Hocks, Dietmar Ratz
Backmatter
Metadata
Title
C++ Toolbox for Verified Computing I
Authors
Prof. Dr. Ulrich Kulisch
Dr. Rolf Hammer
Dr. Matthias Hocks
Dr. Dietmar Ratz
Copyright Year
1995
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-79651-7
Print ISBN
978-3-642-79653-1
DOI
https://doi.org/10.1007/978-3-642-79651-7