nach oben

2001 | Buch

Kapitel lesen Erstes Kapitel lesen

Applied Interval Analysis

With Examples in Parameter and State Estimation, Robust Control and Robotics

verfasst von: Luc Jaulin, PhD, Michel Kieffer, PhD, Olivier Didrit, PhD, Éric Walter, PhD

Verlag: Springer London

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

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

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

1. Introduction

Abstract

This book is about guaranteed numerical methods for approximating sets, and their application to engineering. Guaranteed means here that outer (and sometimes inner) approximations of the sets of interest are obtained, which can, at least in principle, be made as precise as desired. It thus becomes possible to achieve tasks often thought to be out of the reach of numerical methods, such as finding all solutions of sets of non-linear equations and inequalities or all global optimizers of possibly multi-modal criteria.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

Tools

Frontmatter

2. Interval Analysis

Abstract

Before using interval analysis as a basic tool in the following chapters, we shall now introduce its main concepts. Section 2.2 recalls fundamental notions on set operators, set functions and set calculus. Section 2.3 then presents basic notions of interval analysis. Section 2.4 is dedicated to the important notion of inclusion function. Finally, Section 2.5 deals with the extension to intervals of logical tests that are almost invariably present in the algorithms of interest to us.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

3. Subpavings

Abstract

As we have seen in the previous chapter, intervals and boxes form an attractive class of wrappers, easily manipulated. These wrappers, however, are not by themselves general enough satisfactorily to describe all types of sets of interest to us, which are of course not restricted to intervals and boxes and include, for instance, unions of disconnected subsets.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

4. Contractors

Abstract

Consider n_x variables x_i ∈ ℝ, i ∈ {1, …, n_x} linked by n_f relations (or constraints) of the form

$${f_j}\left( {{x_1},{x_2}, \ldots ,{x_{{n_x}}}} \right) = 0,j \in \left\{ {1, \ldots ,{n_f}} \right\}.$$

(4.1)

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

5. Solvers

Abstract

Chapter 4 presented contractors that make it possible to contain a compact set ${\Bbb S}$ defined by non-linear equations and inequalities in a box. Although the results are guaranteed, the accuracy with which ${\Bbb S}$ is characterized is not under control. On the other hand, bisection allows accuracy to be controlled, but causes exponential complexity. Bisection should therefore be avoided as much as possible when the number of variables is high, in an attempt to escape the curse of dimensionality. This is why, in our opinion, when many variables are involved bisection should be used as a last resort, only when all available contractors have failed. A decision may then have to be taken as to which variable domains should be bisected.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

Applications

Frontmatter

6. Estimation

Abstract

Consider a set X consisting of real variables x₁,…, x_n, which form a vector x. For the sake of simplicity, n = dim x will be taken as finite.

the time at which a given event occurs (or the value taken by any other independent variable),
the value of some physical parameter, such as the rate constant of a chemical reaction,
the value taken by some quantity of interest at a given instant of time.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

7. Robust Control

Abstract

The aim of this chapter is to illustrate the use of interval techniques presented in Part II to solve some robust control problems. Robustness is understood here with respect to uncertainty in the model of the process to be controlled. The problems considered range from the analysis of the properties of an existing uncertain system to the design of a controller for an uncertain process.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

8. Robotics

Abstract

Robots are mechanical systems that are controlled to achieve specific tasks, deemed too repetitive, too dangerous or too difficult for human beings. As a result, robotics is a vast interdisciplinary field, which draws on mathematics, mechanics, control theory, artificial intelligence, ergonomics… This chapter cannot, of course, pretend to exhaustiveness, and will limit itself to illustrating how interval analysis can contribute to the solution of three difficult problems.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

Implementation

Frontmatter

9. Automatic Differentiation

Abstract

Interval solvers require the repeated interval evaluation of derivatives of functions. For instance, the evaluation of centred inclusion functions (page 33), Newton contractors (page 86), contractors based on parallel linearization (page 87) and the choice of the direction of bisection in SiviaX (see (5.4), page 106) all require the computation of derivatives of functions with interval arguments.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

10. Guaranteed Computation with Floating-point Numbers

Abstract

One of the main features of interval analysis is its ability to provide boxes guaranteed to contain the image of a given box by a function. This containment property has to be preserved by computer implementation. The intervals computed using a finite-precision representation of real numbers should therefore always contain those that would be obtained with an infinite precision. A trade-off should moreover be found between execution time and accuracy of interval evaluation.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

11. Do It Yourself

Abstract

The first purpose of this chapter will be to show how your library, a basic library for interval analysis, can be implemented in C++. As will soon become apparent, such an implementation is a lot of work. One may thus wonder if one would not be better off using a readily available library, and the second purpose of this chapter will be to explain how this can be done. We have chosen the profil/bias library, because it is licensed free of charge, and runs on a large choice of platforms. The time spent building your library will facilitate the understanding of the source code of profil/bias, as they share their basic syntax. The last purpose of this chapter will be to give some details on how the algorithms described in the rest of the book may be implemented, using either your library or profil/bias.

Luc Jaulin, Michel Kieffer, Olivier Didrit, Éric Walter

Backmatter

Titel: Applied Interval Analysis
verfasst von: Luc Jaulin, PhD
Michel Kieffer, PhD
Olivier Didrit, PhD
Éric Walter, PhD
Verlag: Springer London
Electronic ISBN: 978-1-4471-0249-6
Print ISBN: 978-1-4471-1067-5
DOI: https://doi.org/10.1007/978-1-4471-0249-6

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

1. Introduction

Tools

Frontmatter

2. Interval Analysis

3. Subpavings

4. Contractors

5. Solvers

Applications

Frontmatter

6. Estimation

7. Robust Control

8. Robotics

Implementation

Frontmatter

9. Automatic Differentiation

10. Guaranteed Computation with Floating-point Numbers

11. Do It Yourself

Backmatter