Über die Autorin bzw. den Autor

Magnus Egerstedt is associate professor of electrical and computer engineering at Georgia Institute of Technology. Clyde Martin is the P. W. Horn Professor of Mathematics and Statistics at Texas Tech University.

Von der hinteren Coverseite

"This is the only book I know of that combines control theory with splines. Its multidisciplinary approach will appeal to a wide range of readers, including researchers in control theory and splines, numerical analysis, engineering, and biology. The book is well organized and nicely written. Reading it was quite enjoyable."--Zhimin Zhang, Wayne State University

Aus dem Klappentext

"This is the only book I know of that combines control theory with splines. Its multidisciplinary approach will appeal to a wide range of readers, including researchers in control theory and splines, numerical analysis, engineering, and biology. The book is well organized and nicely written. Reading it was quite enjoyable."--Zhimin Zhang, Wayne State University

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Control Theoretic Splines

PRINCETON UNIVERSITY PRESS

Contents

Preface..................................................................ixChapter 1. INTRODUCTION..................................................1Chapter 2. CONTROL SYSTEMS AND MINIMUM NORM PROBLEMS.....................11Chapter 3. EIGHT FUNDAMENTAL PROBLEMS....................................25Chapter 4. SMOOTHING SPLINES AND GENERALIZATIONS.........................53Chapter 5. APPROXIMATIONS AND LIMITING CONCEPTS..........................73Chapter 6. SMOOTHING SPLINES WITH CONTINUOUS DATA........................87Chapter 7. MONOTONE SMOOTHING SPLINES....................................113Chapter 8. SMOOTHING SPLINES AS INTEGRAL FILTERS.........................133Chapter 9. OPTIMAL TRANSFER BETWEEN AFFINE VARIETIES.....................155Chapter 10. PATH PLANNING AND TELEMETRY..................................169Chapter 11. NODE SELECTION...............................................193Bibliography.............................................................205Index....................................................................215

Chapter One

Splines are ubiquitous in science and engineering. Sometimes they play a leading role as generators of paths or curves, but often they are hidden inside, for example, software packages for solving dynamic equations, in graphics, and in numerous other applications.

The standard, classic spline is an interpolating curve. In contrast to this, smoothing splines are only required to pass "close" to the data points. Such smoothing splines are well know by name in statistics, but not so well known outside of this area. The goal of this book is to show that smoothing splines arise as a natural part of control theory, and that, by using control theoretic concepts, we can construct and interpret smoothing splines in an efficient, algorithmic manner.

Throughout the book, this connection between control theory and smoothing splines will be made explicit, and we will find numerous applications for smoothing splines in path planning for mobile robots, in numerical analysis, graphics, and other basic applications. This introductory chapter presents a brief background to interpolating and smoothing splines, as well as sets up their connection to linear systems theory.

1.1 FROM INTERPOLATION TO SMOOTHING

The basic problem that the classical spline was constructed to solve was as follows: Given a finite set of data points, find a smooth curve that interpolates through these points. Of course, there are infinitely many such curves, and the real task is to devise an algorithm that selects a unique (hopefully exhibiting certain desirable properties) curve. In fact, classical splines solve this problem by requiring that the curve be piecewise polynomial, that is, that it be polynomial between the data points, and that the pieces be connected as smoothly as possible. Often additional conditions must be applied as well at the endpoints to ensure uniqueness.

This idea of producing interpolating polynomials, stitched together at the data points, works wonderfully if the data are exact, or nearly so. Unfortunately, data often have significant error associated with them, and classical splines tend to accent these errors. Smoothing splines were developed to remedy this very problem, that is, to handle cases when there is error associated with the data points. Naturally enough, these smoothing splines were developed in statistics, where noise is a fact of life, and where error is assumed in almost all data. As such, the restriction of exact interpolation was dropped, while the restriction remained that the curves should be piecewise polynomial and as smooth as possible.

Statistics aside, this notion of producing smoothing rather than interpolating curves is rather natural as well in engineering in general, and control theory in particular. In fact, various notions of controllability have always played fundamental roles in engineering through the canonical problem of moving an object at a known position with known dynamics to a new position. For example, in air traffic control, ground control typically will dictate to the pilot of an airplane where it should be at a fixed set of times, and what its corresponding directions should be, for example, the command could be to be at 10,000 feet in 2 minutes with a given heading. The pilot will in fact receive a string of such commands as the plane approaches an airport. Typically, some deviations from the exact locations are allowed, and the size of the deviation depends on many factors. For example, passenger comfort requires that accelerations are minimized, and that transitions are smooth. As a consequence, exact interpolation is not desirable in this case. In fact, the pilot is constructing a type of smoothing spline.

Based on this rather informal observation, it seems natural to give a more explicit description of the general controllability problem in the context of smoothing splines. It was from this rather straightforward idea that the concept under investigation in this book arose, that is, the concept of control theoretic splines.

1.2 BACKGROUND

The problem of approximation is almost as old as modern mathematics. In fact, polynomial interpolation dates back to the mid 1700s, with the work of Edward Waring (Lagrange interpolation). The ideas of polynomial approximation were central during the 1800s, with the development of various families of orthogonal polynomials, and what later became known as the related Hilbert space theories. The polynomial interpolation problems were of such importance that a significant part of modern mathematics can trace its history back to these developments in one form or another. But, if polynomial interpolation is such a well-studied and powerful tool, then why were polynomial splines invented?

1.2.1 Polynomial Interpolating Splines

Traditional (pre-spline) polynomial interpolation has at least two very serious drawbacks, which limit its use in many applications. The first is that a polynomial of degree n + 1 may have as many as n local extrema. This causes the curve to be very complex. If, for example, we have n + 2 data points that are connected by curves that are approximately linear, then the interpolating polynomial will have degree n + 1, and hence will not at all be approximately (piecewise) linear. As such, while we may have a locally good fit, we cannot have a good fit over an arbitrarily large interval.

The second major drawback is an algorithmic problem. To find a polynomial that interpolates a given set of data is equivalent to inverting a van der Monde matrix. The condition number of a van der Monde matrix can grow as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with N being the size of the matrix, making the inversion rather intractable in that numerically, the problem of polynomial interpolation may become highly unstable (see e.g., [42]). So, as beautiful as the theory of polynomial interpolation is, it is not particularly useful for large problems.

To remedy this, during the early 1940s, splines as we know them were invented by Isaac Schoenberg at the U.S. Army Ballistic Research Laboratory in Aberdeen, Maryland (the Aberdeen Proving Ground). The splines' early uses are somewhat shrouded in...