Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics

ISBN-13: 9781852332198 / Angielski / Twarda / 2001 / 379 str.

Luc Jaulin;Michel Kieffer;Olivier Didrit

Opis

At the core of many engineering problems is the solution of sets of equa- tions and inequalities, and the optimization of cost functions. Unfortunately, except in special cases, such as when a set of equations is linear in its un- knowns or when a convex cost function has to be minimized under convex constraints, the results obtained by conventional numerical methods are only local and cannot be guaranteed. This means, for example, that the actual global minimum of a cost function may not be reached, or that some global minimizers of this cost function may escape detection. By contrast, interval analysis makes it possible to obtain guaranteed approximations of the set of all the actual solutions of the problem being considered. This, together with the lack of books presenting interval techniques in such a way that they could become part of any engineering numerical tool kit, motivated the writing of this book. The adventure started in 1991 with the preparation by Luc Jaulin of his PhD thesis, under Eric Walter's supervision. It continued with their joint supervision of Olivier Didrit's and Michel Kieffer's PhD theses. More than two years ago, when we presented our book project to Springer, we naively thought that redaction would be a simple matter, given what had already been achieved . . .

Recenzje

From the reviews:
"Applied Interval Analysis is the right book at the right time to move computing with intervals into the mainstream of engineering, financial, and scientific computing."
G. William Walster, Interval Technology Engineering Manager, Sun Microsystems and Member of the Editorial Board of Reliable Computing

Spis treści

I. Introduction.- 1. Introduction.- 1.1 What Are the Key Concepts?.- 1.2 How Did the Story Start?.- 1.3 What About Complexity?.- 1.4 How is the Book Organized?.- II. Tools.- 2. Interval Analysis.- 2.1 Introduction.- 2.2 Operations on Sets.- 2.2.1 Purely set-theoretic operations.- 2.2.2 Extended operations.- 2.2.3 Properties of set operators.- 2.2.4 Wrappers.- 2.3 Interval Analysis.- 2.3.1 Intervals.- 2.3.2 Interval computation.- 2.3.3 Closed intervals.- 2.3.4 Interval vectors.- 2.3.5 Interval matrices.- 2.4 Inclusion Functions.- 2.4.1 Definitions.- 2.4.2 Natural inclusion functions.- 2.4.3 Centred inclusion functions.- 2.4.4 Mixed centred inclusion functions.- 2.4.5 Taylor inclusion functions.- 2.4.6 Comparison.- 2.5 Inclusion Tests.- 2.5.1 Interval Booleans.- 2.5.2 Tests.- 2.5.3 Inclusion tests for sets.- 2.6 Conclusions.- 3. Subpavings.- 3.1 Introduction.- 3.2 Set Topology.- 3.2.1 Distances between compact sets.- 3.2.2 Enclosure of compact sets between subpavings.- 3.3 Regular Subpavings.- 3.3.1 Pavings and subpavings.- 3.3.2 Representing a regular subpaving as a binary tree.- 3.3.3 Basic operations on regular subpavings.- 3.4 Implementation of Set Computation.- 3.4.1 Set inversion.- 3.4.2 Image evaluation.- 3.5 Conclusions.- 4. Contractors.- 4.1 Introduction.- 4.2 Basic Contractors.- 4.2.1 Finite subsolvers.- 4.2.2 Intervalization of finite subsolvers.- 4.2.3 Fixed-point methods.- 4.2.4 Forward—backward propagation.- 4.2.5 Linear programming approach.- 4.3 External Approximation.- 4.3.1 Principle.- 4.3.2 Preconditioning.- 4.3.3 Newton contractor.- 4.3.4 Parallel linearization.- 4.3.5 Using formal transformations.- 4.4 Collaboration Between Contractors.- 4.4.1 Principle.- 4.4.2 Contractors and inclusion functions.- 4.5 Contractors for Sets.- 4.5.1 Definitions.- 4.5.2 Sets defined by equality and inequality constraints.- 4.5.3 Improving contractors using local search.- 4.6 Conclusions.- 5. Solvers.- 5.1 Introduction.- 5.2 Solving Square Systems of Non-linear Equations.- 5.3 Characterizing Sets Defined by Inequalities.- 5.4 Interval Hull of a Set Defined by Inequalities.- 5.4.1 First approach.- 5.4.2 Second approach.- 5.5 Global Optimization.- 5.5.1 The Moore—Skelboe algorithm.- 5.5.2 Hansen’s algorithm.- 5.5.3 Using interval constraint propagation.- 5.6 Minimax Optimization.- 5.6.1 Unconstrained case.- 5.6.2 Constrained case.- 5.6.3 Dealing with quantifiers.- 5.7 Cost Contours.- 5.8 Conclusions.- III. Applications.- 6. Estimation.- 6.1 Introduction.- 6.2 Parameter Estimation Via Optimization.- 6.2.1 Least-square parameter estimation in compartmental modelling.- 6.2.2 Minimax parameter estimation.- 6.3 Parameter Bounding.- 6.3.1 Introduction.- 6.3.2 The values of the independent variables are known.- 6.3.3 Robustification against outliers.- 6.3.4 The values of the independent variables are uncertain.- 6.3.5 Computation of the interval hull of the posterior feasible set.- 6.4 State Bounding.- 6.4.1 Introduction.- 6.4.2 Bounding the initial state.- 6.4.3 Bounding all variables.- 6.4.4 Bounding by constraint propagation.- 6.5 Conclusions.- 7. Robust Control.- 7.1 Introduction.- 7.2 Stability of Deterministic Linear Systems.- 7.2.1 Characteristic polynomial.- 7.2.2 Routh criterion.- 7.2.3 Stability degree.- 7.3 Basic Tests for Robust Stability.- 7.3.1 Interval polynomials.- 7.3.2 Polytope polynomials.- 7.3.3 Image-set polynomials.- 7.3.4 Conclusion.- 7.4 Robust Stability Analysis.- 7.4.1 Stability domains.- 7.4.2 Stability degree.- 7.4.3 Value-set approach.- 7.4.4 Robust stability margins.- 7.4.5 Stability radius.- 7.5 Controller Design.- 7.6 Conclusions.- 8. Robotics.- 8.1 Introduction.- 8.2 Forward Kinematics Problem for Stewart—Gough Platforms.- 8.2.1 Stewart—Gough platforms.- 8.2.2 From the frame of the mobile plate to that of the base.- 8.2.3 Equations to be solved.- 8.2.4 Solution.- 8.3 Path Planning.- 8.3.1 Graph discretization of configuration space.- 8.3.2 Algorithms for finding a feasible path.- 8.3.3 Test case.- 8.4 Localization and Tracking of a Mobile Robot.- 8.4.1 Formulation of the static localization problem.- 8.4.2 Model of the measurement process.- 8.4.3 Set inversion.- 8.4.4 Dealing with outliers.- 8.4.5 Static localization example.- 8.4.6 Tracking.- 8.4.7 Example.- 8.5 Conclusions.- IV. Implementation.- 9. Automatic Differentiation.- 9.1 Introduction.- 9.2 Forward and Backward Differentiations.- 9.2.1 Forward differentiation.- 9.2.2 Backward differentiation.- 9.3 Differentiation of Algorithms.- 9.3.1 First assumption.- 9.3.2 Second assumption.- 9.3.3 Third assumption.- 9.4 Examples.- 9.4.1 Example 1.- 9.4.2 Example 2.- 9.5 Conclusions.- 10. Guaranteed Computation with Floating-point Numbers.- 10.1 Introduction.- 10.2 Floating-point Numbers and IEEE 754.- 10.2.1 Representation.- 10.2.2 Rounding.- 10.2.3 Special quantities.- 10.3 Intervals and IEEE 754.- 10.3.1 Machine intervals.- 10.3.2 Closed interval arithmetic.- 10.3.3 Handling elementary functions.- 10.3.4 Improvements.- 10.4 Interval Resources.- 10.5 Conclusions.- 11. Do It Yourself.- 11.1 Introduction.- 11.2 Notions of C++.- 11.2.1 Program structure.- 11.2.2 Standard types.- 11.2.3 Pointers.- 11.2.4 Passing parameters to a function.- 11.3 INTERVAL Class.- 11.3.1 Constructors and destructor.- 11.3.2 Other member functions.- 11.3.3 Mathematical functions.- 11.4 Intervals with PROFIL/BIAS.- 11.4.1 BIAS.- 11.4.2 PROFIL.- 11.4.3 Getting started.- 11.5 Exercises on Intervals.- 11.6 Interval Vectors.- 11.6.1 INTERVAL_VECTOR class.- 11.6.2 Constructors, assignment and function call operators.- 11.6.3 Friend functions.- 11.6.4 Utilities.- 11.7 Vectors with PROFIL/BIAS.- 11.8 Exercises on Interval Vectors.- 11.9 Interval Matrices.- 11.10 Matrices with PROFIL/BIAS.- 11.11 Exercises on Interval Matrices.- 11.12 Regular Subpavings with PROFIL/BIAS.- 11.12.1 NODE class.- 11.12.2 Set inversion with subpavings.- 11.12.3 Image evaluation with subpavings.- 11.12.4 System simulation and state estimation with subpavings.- 11.13 Error Handling.- 11.13.1 Using exit.- 11.13.2 Exception handling.- 11.13.3 Mathematical errors.- References.