C++ Toolbox for Verified Computing I

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.