Numerical Toolbox for Verified Computing I : Basic Numerical Problems Theory, Algorithms, and Pascal-XSC Programs

This book presents an extensive set of tools for solving basic numerical problems with verification of the results using the scientific computer language PASCAL-XSC. It contains implementations of algorithms and many examples and exercises. Some topics covered are usually not found in standard numerical analysis texts. It is written for engineers, mathematicians and scientists working in scientific computing.

1 Introduction.- 1 Introduction.- 1.1 Advice for Quick Readers.- 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 PASCAL―XSC.- 2.1 Predefined Data Types, Operators, and Functions.- 2.2 The Universal Operator Concept.- 2.3 Overloading of Procedures, Functions, and Operators.- 2.4 Module Concept.- 2.5 Dynamic Arrays and Subarrays.- 2.6 Data Conversion.- 2.7 Accurate Expressions (#-Expressions).- 2.8 The String Concept.- 2.9 Predefined Arithmetic Modules.- 2.10 Why PASCAL-XSC?.- 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 PASCAL―XSC 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 PASCAL―XSC 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 PASCAL―XSC 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 PASCAL―XSC Program Code.- 7.3.1.1 Module 1st1_ari.- 7.3.1.2 Module gopl.- 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 PASCAL―XSC 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 PASCAL―XSC 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 PASCAL―XSC 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 PASCAL―XSC Program Code.- 11.3.1.1 Module lop_ari.- 11.3.1.2 Module rev_simp.- 11.3.1.3 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 PASCAL―XSC Program Code.- 12.3.1.1 Module hess_axi.- 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 PASCAL―XSC Program Code.- 13.3.1.1 Module nlss.- 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 PASCAL―XSC Program Code.- 14.3.1.1 Module 1st_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.l Module b_util.- A.2 Module r_util.- A.3 Module i_util.- A.4 Module mvi_util.- Index of Special Symbols.