Recursive Techniques in State-Space and Matrix Fraction Realizations for Linear Systems

Antonio Barreiro    Dept. de Ingeniería de Sistemas L. y S. Informáticos Universidad de Vigo, E.T.S. Ing. Industriales Vigo Spain

I INTRODUCTION

Given a finite sequence of data, formed with N samples of the time response of a dynamical system, an important problem is to find the internal mechanism that explains the given external time behavior.

Under the assumption that the system admits a linear time-invariant model, the more significative time response is the impulse response, which characterizes the linear input–output behavior. Then, it is an important problem to obtain the state space equations or the transfer function that generates the given piece of impulse response.

Such question is known as the partial realization problem, and plays a crucial role in linear system theory. It appears not only in identification problems, but also in many other topics, such as system parametrization, canonical forms, or model reduction in controller synthesis.

For obvious reasons, realization algorithms are preferable to work in a recursive way. Recursiveness not only implies a computational simplification, but mainly reveals new useful properties of the internal structure of linear systems.

The SISO sytems partial realization has a long history. It has been widely treated, and there are many recursive algorithms, like those developed by Massey-Berlekamp [12], and Rissanen [13]. The link with topics like Padé approximants, continued fractions, and the Euclidean algorithm is well established by Gragg and Lindquist [9], and Kalman [11].

The MIMO partial realization, in the state space form, has also been studied by Ho and Kalman [10]. Some recursive algorithms have been developed. The solution presented by Bosgra and Van der Weiden [6,7] gives a satisfactory characterization of all the minimal partial realizations in a canonical form. However this solution is not obtained in a recursive way.

The MIMO partial realization, in the matrix fraction form, has been treated by Dickinson, Morf and Kailath [8], and Anderson, Brasch and Lopestri [1]. The link with continued fractions, Euclidean algorithm, and linear fractional transformations was established in the theoretical approach of Antoulas [2], and in the work of Van Barel and Bultheel [1], closer to the solutions in [1,8]. Both [2,15] provide partial realizations in matrix fraction form and in continued fraction form, but do not consider explicitly the relation with state space models.

State space realization algorithms like [6,7,10] are based on factorizations of the Hankel matrix, while matrix fraction realizations algorithms like [2,15], are based on polynomials, rational fractions, and power series. These different matricial and polynomial formulations imply that that state-space and matrix fraction algorithms work in an apparently different way, as if they had nothing in common.

In [3], a unified treatment was proposed, based on certain factorization of the Hankel matrix, recursively updated. From this factorization, one can simultaneously extract the parameters of the state-space and the matrix fraction models. Each model is independent, i.e., it is obtained not from the other but directly from the data.

The main features of [3] are that it reformules the nonrecursive algorithm in [6,7] providing recursive state-space realizations, and, simultaneously, shows the link with [2,15], providing independent matrix fraction realizations. Then, the Hankel factorization in [3] defines broader context to deal with realization questions.

In this chapter, a detailed exposition of the partial realization algorithm in [3] is presented. Some of the results are based on the work of Bosgra and Van der Weiden [6,7], or are related to the approach in Van Barel and Bultheel [15] or Antoulas [2]. In this case, and because of space limitation, these results are briefly cited, and the details can be found in the reference.

The content of the chapter is as follows. In Section II we establish a Hankel factorization, enjoying some nice properties, from which state-space realizations can be directly obtained. In Section III we show how to obtain, from this Hankel factorization, the realizations in the matrix fraction form. In Section IV we describe the recursive factorization algorithm, and apply it to one example. Finally, the discussion and the conclusions are presented in Section V.

II STATE-SPACE PARTIAL REALIZATION

The results in this section are based on the algorithm in Bosgra [6], which employs the input-ouput canonical form of Bosgra and Van der Weiden [7]. This nonrecursive algorithm is reformuled following [3] to achieve the recursive solution in section IV.

Assume that the sequence of data

k1N=H1H2…HN

is given, where the p × m matrices Hk are the samples of the impulse response of a linear, time-invariant, discrete-time system. An important problem is to obtain the system that generates these data. If we look for a state-space model then we must determine the n × n state matrix A, the n × m input matrix B, and the p × n output matrix C. The relation between the model and the samples is:

Ak−1B=Hk,1≤k≤N.

Then, the partial realization problem can be precisely formuled as: given the sequence {Hk}1N, find a triple Σ = (A, B, C), so that Eq.(2) holds. Such triple is called a partial realization of the sequence. When the infinite sequence k1∞=H1H2… is involved, the corresponding realization is called complete. The size n of the state matrix is called the dimension of the realization. A (partial or complete) realization is called minimal when there is no other realization of lower dimension. Minimal realizations must be controllable and observable.

The relevance of the impulse response and its choice among other possible time responses is due to its easy derivation, from identification techniques, and, mainly, to its more direct relation to the model via the series expansion in z− 1 of the transfer function G(z) = C(zI – A)− 1B.

For this reason, the continuous-time realization problem can be given exactly the same formulation, with the Hk, also called Markov parameters, related to the model via series expansion in s− 1 of the continuous transfer function G(s) = C(sI – A)− 1B. In this way, the results of this chapter, presented for discrete-time systems, are also directly applicable to continuous-time systems.

For questions of unicity, let us recall the notion of equivalence. Two realizations, Σi = (Ai, Bi, Ci), with i = 1, 2, are equivalent, when one can be obtained from the other by means of a state-space coordinate change T, det T ≠ 0:

2=T−1A1T,B2=T−1B1,C2=C1T.

Two minimal realizations generate the same (complete) impulse response if and only if they are in the same equivalence-class. Then, it is important to look for partial realizations in a certain canonical form. A canonical form is defined by a particular set of conditions on the triples (A, B, C), so that in each equivalence-class there is one and only one triple satisfying these conditions We will consider partial realizations in the input-output (I/O) canonical form of Bosgra and Van der Weiden [7].

Since the original work of Ho and Kalman [10], it was clear that the realizations of the sequence {Hk}1N can be obtained arranging the data in the pN × mN (partial) Hankel or behavior matrix:

N=H1H2……HNH2H3…HN*⋮⋮⋮⋮HN*…**,

where the ‘*’ in the formula, means that the corresponding p × m block-entry is unknown at the current stage. When the whole sequence k1∞ is available, from Eq.(4) one can formally build the complete Hankel matrix H∞. The relevance of Hankel matrices in state-space realization is due to its relation to the controllability and observability matrices of the pairs (A, B) and (A, C), respectively.

We...