C++ Toolbox for Verified Computing I: Basic Numerical Problems Theory, Algorithms, and Programs

ISBN-13: 9783642796531 / Angielski / Miękka / 2011 / 382 str.

Rolf Hammer; Matthias Hocks; Ulrich Kulisch

Opis

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."

Spis treści

1 Introduction.- 1.1 Advice for Quick Reading.- 1.2 Structure of the Book.- 1.3 Typography.- 1.4 Algorithmic Notation.- 1.5 Implementation.- 1.6 Computational Environment.- 1.7 Why Numerical Result Verification?.- 1.7.1 A Brief History of Computing.- 1.7.2 Arithmetic on Computers.- 1.7.3 Extensions of Ordinary Floating-Point Arithmetic.- 1.7.4 Scientific Computation with Automatic Result Verification.- 1.7.5 Program Verification versus Numerical Verification.- I Preliminaries.- 2 The Features of C-XSC.- 2.1 Data Types, Predefined Operators, and Functions.- 2.2 Vector and Matrix Handling..- 2.3 Dot Product Expressions.- 2.4 Input and Output.- 2.5 Data Conversion.- 2.6 Predefined Modules.- 2.7 C-XSC or Other Libraries?.- 3 Mathematical Preliminaries.- 3.1 Real Interval Arithmetic.- 3.2 Complex Interval Arithmetic.- 3.3 Extended Interval Arithmetic.- 3.4 Interval Vectors and Matrices.- 3.5 Floating-Point Arithmetic.- 3.6 Floating-Point Interval Arithmetic.- 3.7 The Problem of Data Conversion.- 3.8 Principles of Numerical Verification.- II One-Dimensional Problems.- 4 Evaluation of Polynomials.- 4.1 Theoretical Background.- 4.1.1 Description of the Problem.- 4.1.2 Iterative Solution.- 4.2 Algorithmic Description.- 4.3 Implementation and Examples.- 4.3.1 C++ Program Code.- 4.3.1.1 Module rpoly.- 4.3.1.2 Module rpeval.- 4.3.2 Examples.- 4.3.3 Restrictions and Hints.- 4.4 Exercises.- 4.5 References and Further Reading.- 5 Automatic Differentiation.- 5.1 Theoretical Background.- 5.2 Algorithmic Description.- 5.3 Implementation and Examples.- 5.3.1 C++ Program Code.- 5.3.1.1 Module ddf_ari.- 5.3.2 Examples.- 5.3.3 Restrictions and Hints.- 5.4 Exercises.- 5.5 References and Further Reading.- 6 Nonlinear Equations in One Variable.- 6.1 Theoretical Background.- 6.2 Algorithmic Description.- 6.3 Implementation and Examples.- 6.3.1 C++ Program Code.- 6.3.1.1 Module xi_ari.- 6.3.1.2 Module nlfzero.- 6.3.2 Example.- 6.3.3 Restrictions and Hints.- 6.4 Exercises.- 6.5 References and Further Reading.- 7 Global Optimization.- 7.1 Theoretical Background.- 7.1.1 Midpoint Test.- 7.1.2 Monotonicity Test.- 7.1.3 Concavity Test.- 7.1.4 Interval Newton Step.- 7.1.5 Verification.- 7.2 Algorithmic Description.- 7.3 Implementation and Examples.- 7.3.1 C++ Program Code.- 7.3.1.1 Module lst1_ari.- 7.3.1.2 Module gop1.- 7.3.2 Examples.- 7.3.3 Restrictions and Hints.- 7.4 Exercises.- 7.5 References and Further Reading.- 8 Evaluation of Arithmetic Expressions.- 8.1 Theoretical Background.- 8.1.1 A Nonlinear Approach.- 8.2 Algorithmic Description.- 8.3 Implementation and Examples.- 8.3.1 C++ Program Code.- 8.3.1.1 Module expreval.- 8.3.2 Examples.- 8.3.3 Restrictions, Hints, and Improvements.- 8.4 Exercises.- 8.5 References and Further Reading.- 9 Zeros of Complex Polynomials.- 9.1 Theoretical Background.- 9.1.1 Description of the Problem.- 9.1.2 Iterative Approach.- 9.2 Algorithmic Description.- 9.3 Implementation and Examples.- 9.3.1 C++ Program Code.- 9.3.1.1 Module cpoly.- 9.3.1.2 Module cipoly.- 9.3.1.3 Module cpzero.- 9.3.2 Example.- 9.3.3 Restrictions and Hints.- 9.4 Exercises.- 9.5 References and Further Reading.- III Multi-Dimensional Problems.- 10 Linear Systems of Equations.- 10.1 Theoretical Background.- 10.1.1 A Newton-like Method.- 10.1.2 The Residual Iteration Scheme.- 10.1.3 How to Compute the Approximate Inverse.- 10.2 Algorithmic Description.- 10.3 Implementation and Examples.- 10.3.1 C++ Program Code.- 10.3.1.1 Module matinv.- 10.3.1.2 Module linsys.- 10.3.2 Example.- 10.3.3 Restrictions and Improvements.- 10.4 Exercises.- 10.5 References and Further Reading.- 11 Linear Optimization.- 11.1 Theoretical Background.- 11.1.1 Description of the Problem.- 11.1.2 Verification.- 11.2 Algorithmic Description.- 11.3 Implementation and Examples.- 11.3.1 C++ Program Code.- 11.3.1.1 Module set_ari.- 11.3.1.2 Module lop_ari.- 11.3.1.3 Module rev_simp.- 11.3.1.4 Module lop.- 11.3.2 Examples.- 11.3.3 Restrictions and Hints.- 11.4 Exercises.- 11.5 References and Further Reading.- 12 Automatic Differentiation for Gradients, Jacobians, and Hessians.- 12.1 Theoretical Background.- 12.2 Algorithmic Description.- 12.3 Implementation and Examples.- 12.3.1 C++ Program Code.- 12.3.1.1 Module hess_ari.- 12.3.1.2 Module grad_ari.- 12.3.2 Examples.- 12.3.3 Restrictions and Hints.- 12.4 Exercises.- 12.5 References and Further Reading.- 13 Nonlinear Systems of Equations.- 13.1 Theoretical Background.- 13.1.1 Gauss-Seidel Iteration.- 13.2 Algorithmic Description.- 13.3 Implementation and Examples.- 13.3.1 C++ Program Code.- 13.3.1.1 Module nlinsys.- 13.3.2 Example.- 13.3.3 Restrictions, Hints, and Improvements.- 13.4 Exercises.- 13.5 References and Further Reading.- 14 Global Optimization.- 14.1 Theoretical Background.- 14.1.1 Midpoint Test.- 14.1.2 Monotonicity Test.- 14.1.3 Concavity Test.- 14.1.4 Interval Newton Step.- 14.1.5 Verification.- 14.2 Algorithmic Description.- 14.3 Implementation and Examples.- 14.3.1 C++ Program Code.- 14.3.1.1 Module lst_ari.- 14.3.1.2 Module gop.- 14.3.2 Examples.- 14.3.3 Restrictions and Hints.- 14.4 Exercises.- 14.5 References and Further Reading.- A Utility Modules.- A.1 Module r_util.- A.2 Module i_util.- A.3 Module ci_util.- A.4 Module mv_util.- A.5 Module mvi_util.- B Alphabetical List of Modules.- C List of Special Symbols.

Blurb

This C++ Toolbox for Verified Computing presents an extensive set of sophisticated tools for solving basic numerical problems with verification of the results. It is the C++ edition of the Numerical Toolbox for Verified Computing which was based on the computer language PASCAL-XSC. The sources of the programs in this book are freely available via anonymous ftp. This book offers a general discussion on arithmetic and computational reliablility, analytical mathematics and verification techniques, algoriths, and (most importantly) actual C++ implementations. In each chapter, examples, exercises, and numerical results demonstrate the application of the routines presented. The book introduces many computational verification techniques. It is not assumed that the reader has any prior formal knowledge of numerical verification or any familiarity with interval analysis. The necessary concepts are introduced. Some of the subjects that the book covers in detail are not usually found in standard numerical analysis texts.