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

ISBN-13: 9783642784255 / Angielski / Miękka / 2011 / 339 str.

Rolf Hammer; Matthias Hocks; Ulrich Kulisch

Opis

As suggested by the title of this book Numerical Toolbox for Verified Computing, we present an extensive set of sophisticated tools to solve basic numerical problems with a verification of the results. We use the features of the scientific computer language PASCAL-XSC to offer modules that can be combined by the reader to his/her individual needs. Our overriding concern is reliability - the automatic verification of the result a computer returns for a given problem. All algorithms we present are influenced by this central concern. We must point out that there is no relationship between our methods of numerical result verification and the methods of program verification to prove the correctness of an imple entation for a given algorithm. This book is the first to offer a general discussion on - arithmetic and computational reliability, - analytical mathematics and verification techniques, - algorithms, and - (most importantly) actual implementations in the form of working computer routines. Our task has been to find the right balance among these ingredients for each topic. For some topics, we have placed a little more emphasis on the algorithms. For other topics, where the mathematical prerequisites are universally held, we have tended towards more in-depth discussion of the nature of the computational algorithms, or towards practical questions of implementation. For all topics, we present exam- ples, exercises, and numerical results demonstrating the application of the routines presented.

Spis treści

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.

O autorze

Prof. Dr. Ulrich Kulisch (Karlsruhe) ist auf dem Gebiet der Numerischen Mathematik tätig. Prof. Dr. Dietmar Ratz ist Studiengangsleiter Wirtschaftsinformatik an der Dualen Hochschule Baden-Württemberg (DHBW) Karlsruhe und lehrt als apl. Professor auch am Karlsruher Institut für Technologie (KIT).