After studying this chapter you will be able to

• apply basic operations to vectors and matrices;

• define a vector space;

• define a subspace of a vector space;

• compute the rank of a matrix;

• list the four fundamental subspaces defined by a linear transformation;

• compute the inverse, determinant, eigenvalues, and eigenvectors of a square matrix.

• describe what positive-definite matrices are;

• compute some important matrix decompositions, such as the eigenvalue decomposition, the singular-value decomposition and the QR factorization;

• solve linear equations using techniques from linear algebra;

• describe the deterministic least-squares problem; and

• solve the deterministic least-squares problem in numerically sound ways.

Introduction

In this chapter we review some basic topics from linear algebra. The material presented is frequently used in the subsequent chapters.

Since the 1960s linear algebra has gained a prominent role in engineering as a contributing factor to the success of technological breakthroughs.

Linear algebra provides tools for numerically solving system-theoretic problems, such as filtering and control problems. The widespread use of linear algebra tools in engineering has in its turn stimulated the development of the field of linear algebra, especially the numerical analysis of algorithms. A boost to the prominent role of linear algebra in engineering has certainly been provided by the introduction and widespread use of computer-aided-design packages such as Matlab (MathWorks, 2000b) and SciLab (Gomez, 1999). The user-friendliness of these packages allow us to program solutions for complex system-theoretic problems in just a few lines of code.

After studying this chapter you will be able to

• describe the prediction-error model-estimation problem;

• parameterize the system matrices of a Kalman filter of fixed and known order such that all stable MIMO Kalman filters of that order are presented;

• formulate the estimation of the parameters of a given Kalman-filter parameterization via the solution of a nonlinear optimization problem;

• evaluate qualitatively the bias in parameter estimation for specific SISO parametric models, such as ARX, ARMAX, output error, and Box–Jenkins models, under the assumption that the signal-generating system does not belong to the class of parameterized Kalman filters; and

• describe the problems that may occur in parameter estimation when using data generated in closed-loop operation of the signal-generating system.

Introduction

This chapter continues the discussion started in Chapter 7, on estimating the parameters in an LTI state-space model. It addresses the determination of a model of both the deterministic and the stochastic part of an LTI model.

The objective is to determine, from a finite number of measurements of the input and output sequences, a one-step-ahead predictor given by the stationary Kalman filter without using knowledge of the system and covariance matrices of the stochastic disturbances. In fact, these system and covariance matrices (or alternatively the Kalman gain) need to be estimated from the input and output measurements. Note the difference from the approach followed in Chapter 5, where knowledge of these matrix quantities was used. The restriction imposed on the derivation of a Kalman filter from the data is the assumption of a stationary one-step-ahead predictor of a known order.

After studying this chapter you will be able to

• derive the data equation that relates block Hankel matrices constructed from input–output data;

• exploit the special structure of the data equation for impulse input signals to identify a state-space model via subspace methods;

• use subspace identification for general input signals;

• use instrumental variables in subspace identification to deal with process and measurement noise;

• derive subspace identification schemes for various noise models;

• use the RQ factorization for a computationally efficient implementation of subspace identification schemes; and

• relate different subspace identification schemes via the solution of a least-squares problem.

Introduction

The problem of identifying an LTI state-space model from input and output measurements of a dynamic system, which we analyzed in the previous two chapters, is re-addressed in this chapter via a completely different approach. The approach we take is indicated in the literature (Verhaegen, 1994; Viberg, 1995; Van Overschee and De Moor, 1996b; Katayama, 2005) as the class of subspace identification methods. These methods are based on the fact that, by storing the input and output data in structured block Hankel matrices, it is possible to retrieve certain subspaces that are related to the system matrices of the signal-generating state-space model. Examples of such subspaces are the column space of the observability matrix, Equation (3.25) on page 67, and the row space of the state sequence of a Kalman filter.

Making observations through the senses of the environment around us is a natural activity of living species. The information acquired is diverse, consisting for example of sound signals and images. The information is processed and used to make a particular model of the environment that is applicable to the situation at hand. This act of model building based on observations is embedded in our human nature and plays an important role in daily decision making.

Model building through observations also plays a very important role in many branches of science. Despite the importance of making observations through our senses, scientific observations are often made via measurement instruments or sensors. The measurement data that these sensors acquire often need to be processed to judge or validate the experiment, or to obtain more information on conducting the experiment. Data are often used to build a mathematical model that describes the dynamical properties of the experiment. System-identification methods are systematic methods that can be used to build mathematical models from measured data. One important use of such mathematical models is in predicting model quantities by filtering acquired measurements.

A milestone in the history of filtering and system identification is the method of least squares developed just before 1800 by Johann Carl Friedrich Gauss (1777–1855). The use of least squares in filtering and identification is a recurring theme in this book. What follows is a brief sketch of the historical context that characterized the early development of the least-squares method.

After studying this chapter you will be able to

• define discrete-time and continuous-time signals;

• measure the “size” of a discrete-time signal using norms;

• use the z-transform to convert discrete-time signals to the complex z-plane;

• use the discrete-time Fourier transform to convert discrete-time signals to the frequency domain;

• describe the properties of the z-transform and the discrete-time Fourier transform;

• define a discrete-time state-space system;

• determine properties of discrete-time systems such as stability, controllability, observability, time invariance, and linearity;

• approximate a nonlinear system in the neighborhood of a certain operating point by a linear time-invariant system;

• check stability, controllability, and observability for linear time-invariant systems;

• represent linear time-invariant systems in different ways; and

• deal with interactions between linear time-invariant systems.

Introduction

This chapter deals with two important topics: signals and systems. A signal is basically a value that changes over time. For example, the outside temperature as a function of the time of the day is a signal. More specifically, this is a continuous-time signal; the signal value is defined at every time instant. If we are interested in measuring the outside temperature, we will seldom do this continuously. A more practical approach is to measure the temperature only at certain time instants, for example every minute. The signal that is obtained in that way is a sequence of numbers; its values correspond to certain time instants. Such an ordered sequence is called a discrete-time signal.

After studying this chapter you will be able to

• use the discrete Fourier transform to transform finite-length time signals to the frequency domain;

• describe the properties of the discrete Fourier transform;

• relate the discrete Fourier transform to the discrete-time Fourier transform;

• efficiently compute the discrete Fourier transform using fast-Fourier-transform algorithms;

• estimate spectra from finite-length data sequences;

• reduce the variance of spectral estimates using blocked data processing and windowing techniques;

• estimate the frequency-response function (FRF) and the disturbance spectrum from finite-length data sequences for an LTI system contaminated by output noise; and

• reduce the variance of FRF estimates using windowing techniques.

Introduction

In this chapter the problem of determining a model from input and output measurements is treated using frequency-domain methods. In the previous chapter we studied the estimation of the state given the system and measurements of its inputs and outputs. In this chapter we do not bother about estimating the state. The models that will be estimated are input–output models, in which the state does not occur. More specifically, we investigate how to obtain in a simple and fast manner an estimate of the dynamic transfer function of an LTI system from recorded input and output data sequences taken from that system. We are interested in estimating the frequency-response function (FRF) that relates the measurable input to the measurable output sequence. The FRF has already been discussed briefly in Section 3.4.4 and its estimation is based on Lemma 4.3 via the estimation of the signal spectra of the recorded input and output data. Special attention is paid to the case of practical interest in which the data records have finite data length.

After studying this chapter you will be able to

• describe the output-error model-estimation problem;

• parameterize the system matrices of a MIMO LTI state-space model of fixed and known order such that all stable models of that order are presented;

• formulate the estimation of the parameters of a given system parameterization as a nonlinear optimization problem;

• numerically solve a nonlinear optimization problem using gradient-type algorithms;

• evaluate the accuracy of the obtained parameter estimates via their asymptotic variance under the assumption that the signal-generating system belongs to the class of parameterized state-space models; and

• describe two ways for dealing with a nonwhite noise acting on the output of an LTI system when estimating its parameters.

Introduction

After the treatment of the Kalman filter in Chapter 5 and the estimation of the frequency-response function (FRF) in Chapter 6, we move another step forward in our exploration of how to retrieve information about linear time-invariant (LTI) systems from input and output measurements. The step forward is taken by analyzing how we can estimate (part of) the system matrices of the signal-generating model from acquired input and output data. We first tackle this problem as a complicated estimation problem by attempting to estimate both the state vector and the system matrices. Later on, in Chapter 9, we outline the so-called subspace identification methods that solve such problems by means of linear least-squares problems.

Nonparametric models such as the FRF could also be obtained via the simple least-squares method or the computationally more attractive fast Fourier transform.

After studying this chapter you will be able to

• explain that the identification of an LTI model making use of real-life measurements is more then just estimating parameters in a user-defined model structure;

• identify an LTI model in a cyclic manner of iteratively refining data and models and progressively making use of more complex numerical optimization methods;

• explain that the identification cycle requires many choices to be made on the basis of cautious experiments, the user's expertise, and prior knowledge about the system to be identified or about systems bearing a close relationship with, or resemblance to, the target system;

• argue that a critical choice in system identification is the selection of the input sequence, both in terms of acquiring qualitative information for setting or refining experimental conditions and in terms of accurately estimating models;

• describe the role of the notion of persistency of excitation in system identification;

• use subspace identification methods to initialize prediction-error methods in identifying state-space models in the innovation form; and

• understand that the art of system identification is mastered by applying theoretical insights and methods to real-life experiments and working closely with an expert in the field.

Introduction

In the previous chapters, it was assumed that time sequences of input and output quantities of an unknown dynamical system were given. The task was to estimate parameters in a user-specified model structure on the basis of these time sequences.

This book is intended as a first-year graduate course for engineering students. It stresses the role of linear algebra and the least-squares problem in the field of filtering and system identification. The experience gained with this course at the Delft University of Technology and the University of Twente in the Netherlands has shown that the review of undergraduate study material from linear algebra, statistics, and system theory makes this course an ideal start to the graduate course program. More importantly, the geometric concepts from linear algebra and the central role of the least-squares problem stimulate students to understand how filtering and identification algorithms arise and also to start developing new ones. The course gives students the opportunity to see mathematics at work in solving engineering problems of practical relevance.

The course material can be covered in seven lectures:

1. (i) Lecture 1: Introduction and review of linear algebra (Chapters 1 and 2)

2. (ii) Lecture 2: Review of system theory and probability theory (Chapters 3 and 4)

3. (iii) Lecture 3: Kalman filtering (Chapter 5)

4. (iv) Lecture 4: Estimation of frequency-response functions (Chapter 6)

5. (v) Lecture 5: Estimation of the parameters in a state-space model (Chapters 7 and 8)

6. (vi) Lecture 6: Subspace model identification (Chapter 9)

7. (vii) Lecture 7: From theory to practice: the system-identification cycle (Chapter 10).

The authors are of the opinion that the transfer of knowledge is greatly improved when each lecture is followed by working classes in which the students do the exercises of the corresponding classes under the supervision of a tutor.

A telephone network consists of a network of exchanges (or routers, in more modern formulations). Many of these are themselves the centre of a local star network, in that they have direct connections to individual subscribers in the region. However, it is the exchanges that we shall regard as constituting the nodes of a network. The defining feature of a loss network is that a call is accepted only if a clear route to its destination is available, otherwise the call is lost.

Random variation can enter the system in various ways. Even if all the parameters of operation and loading are constant and equilibrium has been reached, there will be statistical variation of the numbers and types of calls in progress. This is the source that receives most attention in at least that part of the literature favoured by mathematicians. One might consider it secondary in comparison with the more radical type of uncertainty which faces the system when there are massive variations in load or major internal failures. It is these that determine system structure, by setting a premium on versatility and robustness.

Nevertheless, there will always be times when a system is working close to capacity, and real-time decisions on acceptance and routing must be made to accommodate normal statistical variation. Such circumstances are associated with the decentralised realisation of policies, and will be considered in the next chapter.

We shall then begin by considering a system operating deterministically with a fixed demand pattern. The variables (e.g. numbers of calls in progress, capacity assigned to a given link) will be regarded as continuous in this treatment.

The size of this appendix may seem excessive, in view of the limited mention of random graphs in the main body of the text. However, given that a review as meticulous and wide-ranging as that by Albert and Barabási (2002) regards certain central questions as open for which a full analysis exists in the literature, it seems appropriate to give a brief and self-contained account of that analysis. It cannot be long concealed that much of the analysis referred to is that developed by the author over some 30 years. Detailed references are given in the literature survey of Section A3.8; the principal advances are treatment of the so-called first-shell model, leading to the integral representions (A3.13), (A3.31) and (A3.35) of various generating functions, in which a raft of conclusions is implicit.

The random graph model can be expressed either in terms of graphs or in terms of polymers if we identify nodes with atoms, arcs with bonds, components (connected subgraphs) with polymer molecules and node ‘colours’ with types of atom. We shall for preference use the term ‘unit’ rather than atom, since the unit does occasionally have a compound (but fixed) form. The situation in which a ‘giant’ component forms (i.e. in which all but an infinitesimal proportion of the nodes form a single component) is identified with the phenomenon of gelation in the polymer context.

We come now to a most remarkable piece of work. This concerns the optimisation of load-bearing structures in engineering, such as frameworks consisting of freely jointed struts and ties – we give examples. The purpose of such structures is to communicate stress, a vector quantity, in an economic fashion from the points where external load is applied to the points where it can be off-loaded: the load-accepting foundation.

The problem of optimising such structures was considered in a paper, remarkable for its brevity and penetration as much as for its prescience, published as early as 1904 by the Australian engineer A. G. M. Michell. He derived the dual form of the problem and exhibited its essential role in determining the optimal design. This was at a time when there was no general understanding of the role or interpretation of the dual variable – Michell uses the concept of a ‘virtual displacement’, a term that we shall see as justified. He then went on to derive the continuous form of the dual, corresponding to the unrestricted optimisation of structures on the continuum. This opened the way to the study of structures made of material with directional properties (e.g. the use of resin-bonded fibre-glass matting in yacht hulls, the laying down of bone in such a way as to meet the particular pressures and tensions to which it is subjected). It also turned out to offer an understanding of materials that behave plastically rather than elastically under load – i.e. that yield catastrophically when load reaches a critical value.

Whither? Why?

The contents list gives a fair impression of the coverage attempted. Networks, both deterministic and stochastic, have emerged as objects of intense interest over recent decades. They occur in communication, traffic, computer, manufacturing and operational research contexts, and as models in almost any of the natural, economic and social sciences. Even engineering frame structures can be seen as networks that communicate stress from load to foundation.

We are concerned in this book with the characterisation of networks that are optimal for their purpose. This is a very natural ambition; so many structures in nature have been optimised by long adaptation, a suggestive mechanism in itself. It is an ambition with an inbuilt hurdle, however: one cannot consider optimisation of design without first considering optimisation of function, of the rules by which the network is to be operated. On the other hand, optimisation of function should find a more natural setting if it is coupled with the optimisation of design.

The mention of communication and computer networks raises examples of areas where theory barely keeps breathless pace with advancing technology. That is a degree of topicality we do not attempt, beyond setting up some basic links in the final chapters. It is well recognised that networks of commodity flow, electrical flow, traffic flow and even mechanical frame structures and biological bone structures have unifying features, and Part I is devoted to this important subclass of cases.

In Chapter 1 we consider a rather general model of commodity distribution for which flow is determined by an extremal principle.