Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Maximum likelihood identification of linear discrete-time systems De Glas, Michel 1976

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1976_A7 D44.pdf [ 3.84MB ]
Metadata
JSON: 831-1.0100141.json
JSON-LD: 831-1.0100141-ld.json
RDF/XML (Pretty): 831-1.0100141-rdf.xml
RDF/JSON: 831-1.0100141-rdf.json
Turtle: 831-1.0100141-turtle.txt
N-Triples: 831-1.0100141-rdf-ntriples.txt
Original Record: 831-1.0100141-source.json
Full Text
831-1.0100141-fulltext.txt
Citation
831-1.0100141.ris

Full Text

MAXIMUM LIKELIHOOD IDENTIFICATION OF LINEAR DISCRETE-TIME SYSTEMS  by mchel^De Glas Tngenieur, Ecole Superieure d" Informatique Electronique et Automatique, France 1973  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENT FOR THE DEGREE OF MASTER OF APPLIED SCIENCE  i n the Department of E l e c t r i c a l Engineering  We accept this thesis as conforming to the required standard  THE UNIVERSITY OF BRITISH COLUMBIA July, 1976  0  Michel De Glas, 1976  In  presenting  an  advanced  the I  Library  further  for  degree shall  agree  scholarly  by  his  of  this  written  thesis  in  at  University  the  make  that  it  thesis  permission  purposes  for  partial  freely  may  representatives.  of  It  is  financial  British  available for  by  the  understood  gain  shall  Head  be  of  University  E of  I €. chr  * <L &\  British  TcJv  Z l ^ j  >Q7f>  of  my  I  agree  and  of  copying  this  or  for  that  study. thesis  Department  or  publication  allowed without  £ t*- J? / **- ^~g- v  Columbia  requirements  reference copying  that  not  the  Columbia,  for  extensive  be g r a n t e d  2075 W e s b r o o k P l a c e V a n c o u v e r , Canada V6T 1W5  Date  fulfilment of  permission.  Department The  this  my  ABSTRACT / RESUME  Abstract The t h e o r e t i c a l p r o p e r t i e s o f t h e Maximum L i k e l i h o o d e s t i m a t o r , f o r b o t h s i n g l e i n p u t - s i n g l e o u t p u t and m u l t i v a r i a b l e systems, a r e c o n s i d e r e d .  New r e s u l t s r e l a t i v e t o convergence  p r o p e r t i e s o f some i d e n t i f i c a t i o n methods o f s i n g l e o u t p u t systems a r e o b t a i n e d .  input-single  A u n i f i e d a p p r o a c h t o t h e Maximum  L i k e l i h o o d i d e n t i f i c a t i o n method o f m u l t i v a r i a b l e systems i s proposed.  N u m e r i c a l t e s t s on a computer a r e p e r f o r m e d .  Resumg Nous c o n s i d e r o n s l e s p r o p r i e t e s t h e o r i q u e s de l ' e s t i — mateur du Maximum de V r a i s e m b l a n c e dans l e c a s de systemes monov a r i a b l e s e t de systemes m u l t i v a r i a b l e s .  Nous e'tudions d e s  methodes d ' i d e n t i f i c a t i o n de systemes m o n o v a r i a b l e s , e t de nouveaux r e s u l t a t s r e l a t i f s a l a convergence de c e s methodes s o n t obtenus.  Nous proposons une approche g l o b a l e de 1 ' i d e n t i f i c a t i o n  des systemes m u l t i v a r i a b l e s au sens du Maximum de V r a i s e m b l a n c e . C e t t e p r o c e d u r e e s t i l l u s t r e e p a r des exemples numeriques.  iii TABLE OF CONTENTS INTRODUCTION Chapter 1  Page 1  '  SINGLE INPUT - SINGLE OUTPUT SYSTEMS  ....  6  1  Introduction  6  2  Preliminaries  1  3  Moving Average noise model  12  3.1  Introduction  12  3.2  Global minimum points  14  3.3  L o c a l extremum points  16  Autoregressive noise model  20  4.1  Introduction . . .  20  4.2  Global minimum points  4.3  L o c a l extremum p o i n t s  25  4.4  Comments  30  4  5  ......<  Conclusion  31  Chapter 2 MULTIVARIABLE SYSTEMS 1  Introduction  2  Canonical structures  3  21  . . . . . . .  32 32  .  34  2.1  Introduction  34  2.2  Preliminaries  35  2.3  Canonical forms  36  Canonical input - output equations  42  3.1  Introduction  42  3.2  Noise-free v e r s i o n  43  3.3 Noisy v e r s i o n 3.4  Comments  55 • • • •  $9  Page 4  5  Maximum Likelihood estimator  61  4.1  Introduction .  61  4.2  Equation of error  61  4.3  S t a t i s t i c a l properties of the estimates  Chapter 3  65  Minimizing the loss functions  71  5.1  Introduction  71  5.2  Minimization procedures  5.3  Minimization procedures without derivatives  6  . . .  Conclusion  EXPERIMENTS  using derivatives  . .  72  using 73 75  . . .  78  1  Introduction  78  2  Experiment 1  78  3  Experiment 2  79  CONCLUSIONS  84  REFERENCES  85  V  LIST OF TABLES  Table 3.1  P a  Identification results.  Identification results. (S/N = 10)  3.3  Identification results.  80 T h i r d o r d e r system . .  81  F o u r t h o r d e r system  (S/N = 10)  3.4  Identification results. (S/N =3)  e  T h i r d o r d e r system  (S/N = ») 3.2  g  82  F o u r t h order system •  83  vi  ACKNOWLEDGEMENT  I would l i k e to express my gratitude to Dr. E.V. Bohn, my supervisor, f o r h i s guidance during the research and w r i t i n g of my thesis.  I wish to thank Dr. A.C. Soudack f o r h i s h e l p f u l  suggestions.  I am thankful to the Canada Council f o r the f i n a n c i a l  support  afforded me i n the form of a Graduate Scholarship from 1974 to 1976.  INTRODUCTION  Preliminaries  D u r i n g t h e p a s t decade, i n c r e a s i n g a t t e n t i o n has been devoted t o t h e d i f f e r e n t a s p e c t s o f s y s t e m i d e n t i f i c a t i o n . a l t h o u g h t h e s e t o p i c s have been d i s c u s s e d  i n a multitude  However,  of papers  and a r a t h e r l a r g e number o f s u r v e y p a p e r s [3,8,9,25] have been p u b l i s h e d , t h e f i e l d o f i d e n t i f i c a t i o n does not appear as a subject.  unified  I t i s t h e n o f i m p o r t a n c e t o have i n mind t h e b a s i c c o n -  c e p t s c h a r a c t e r i z i n g an i d e n t i f i c a t i o n p r o b l e m .  One o f t h e b a s i c i n g r e d i e n t s i n t h e f o r m u l a t i o n o f t h e i d e n t i f i c a t i o n p r o b l e m i s t h e c h o i c e o f t h e c l a s s o f models [21] ( p a r a m e t r i c , non p a r a m e t r i c ) and o f t h e model s t r u c t u r e non l i n e a r , c o n t i n u o u s - d i s c r e t e  time,...).  (linear-  Such c h o i c e s c a n n o t be  done s y s t e m a t i c a l l y and depend on t h e a p r i o r i knowledge o f t h e case t r e a t e d and on t h e purpose o f t h e i d e n t i f i c a t i o n .  Due t o t h e f a c t t h a t , i n most r e a l i s t i c s i t u a t i o n s , t h e measurements made on t h e s y s t e m c o n s i d e r e d disturbances,  are corrupted  one may i n v e s t i g a t e t h e i d e n t i f i c a t i o n p r o b l e m t h r o u g h  s t a t i s t i c a l methods, l e a d i n g t o an e s t i m a t i o n p r o b l e m . t i o n p r o b l e m c a n be f o r m u l a t e d  a s t h e c h o i c e o f an  ( L e a s t - S q u a r e s , Markov, Bayes, Maximum L i k e l i h o o d ) . mulation  by random  The  estima-  estimator Such a f o r -  makes i t p o s s i b l e t o d e r i v e m a t h e m a t i c a l p r o p e r t i e s o f t h e  estimates fication.  and p r o v i d e s  a r i g o r o u s framework t o t h e f i e l d o f i d e n t i -  I t must be n o t i c e d t h a t t h e p r o b a b i l i s t i c i n t e r p r e t a t i o n  can be e l u d e d by t a k i n g i n t o account t h e e f f e c t s o f t h e d i s t u r b a n c e s f r o m an e m p i r i c a l p o i n t o f view.  I n any s i t u a t i o n ( p r o b a b i l i s t i c o r d e t e r m i n i s t i c ) , t h e i d e n t i f i c a t i o n p r o b l e m can c o n c e p t u a l l y be s t a t e d as t h e f i n d i n g o f the m o d e l — s u b j e c t e d t o t h e same i n p u t s i g n a l s as t h e s y s t e m — t h a t i s o p t i m a l i n some sense. c r i t e r i o n with respect the parameters values  The o p t i m a l i t y has t o be d e f i n e d u s i n g a  t o t h e output s i g n a l s , which a r e r e l a t e d t o through a f u n c t i o n a l r e l a t i o n s h i p .  The  c r i t e r i o n i s g e n e r a l l y d e f i n e d by means o f a l o s s f u n c t i o n , l e a d i n g t o an o p t i m i z a t i o n problem.  The c h o i c e o f an o p t i m i z a t i o n method  ( d e r i v a t i v e - t y p e methods, s e a r c h methods) i s , once a g a i n ,  strongly  r e l a t e d t o t h e p r o b l e m under s t u d y .  A l l these aspects a r e e q u a l l y important steps of t h e i d e n t i f i c a t i o n problem w h i c h t h e n cannot be c o n s i d e r e d  as a  simple  e s t i m a t i o n o f a s e t o f parameters o r as a s i m p l e o p t i m i z a t i o n problem.  Aim o f T h e s i s The  p r e s e n t work i s concerned w i t h i d e n t i f i c a t i o n o f  linear discrete-time  systems.  As o u t l i n e d above, t h e c h o i c e o f an e s t i m a t o r s t e p o f t h e i d e n t i f i c a t i o n problem. the L e a s t - S q u a r e s (LS) e s t i m a t o r .  i s a crucial  A very popular choice i s that of However, i t i s w e l l known t h a t t h e  LS e s t i m a t o r i s g e n e r a l l y b i a s e d .  I n o r d e r t o overcome t h e p r o b l e m  o f c o r r e l a t e d n o i s e , one may p o s t u l a t e a system w i t h c o r r e l a t e d n o i s e , by i n t r o d u c i n g a n o i s e model.  Depending on t h e a p r i o r i  knowledge o f t h e system and o f t h e n o i s e , t h e f o l l o w i n g e s t i m a t o r s may be chosen: - t h e Markov e s t i m a t o r f o r w h i c h t h e knowledge o f t h e c o v a r i a n c e m a t r i x o f t h e n o i s e i s needed - t h e Bayes' e s t i m a t o r f o r w h i c h t h e knowledge o f t h e p r o b a b i l i t y d e n s i t y f u n c t i o n o f t h e n o i s e and o f t h e p a r a m e t e r s v a l u e s i s needed - t h e Maximum L i k e l i h o o d e s t i m a t o r f o r w h i c h t h e p r o b a b i l i t y d e n s i t y f u n c t i o n o f t h e n o i s e i s needed. The a s s u m p t i o n o f known c o v a r i a n c e m a t r i x o f t h e n o i s e o r o f known p r o b a b i l i t y d e n s i t y f u n c t i o n o f t h e p a r a m e t e r s v a l u e s s e v e r e l y l i m i t s t h e p r a c t i c a l a p p l i c a b i l i t y o f t h e two f i r s t e s t i m a t o r s .  The  aim o f Chapter 1 i s t o a n a l y z e , f o r s i n g l e i n p u t - s i n g l e o u t p u t systems, t h e m a t h e m a t i c a l p r o p e r t i e s o f t h e Maximum L i k e l i h o o d estimator.  Two new r e s u l t s w i l l be o b t a i n e d : - i n case o f a Moving Average n o i s e model (Astrom [ 2 ] ) ,  i t w i l l be shown t h a t t h e Maximum L i k e l i h o o d e s t i m a t e s may conv e r g e t o wrong v a l u e s .  Counterexamples t o g e n e r a l convergence  w i l l be g i v e n ( S e c t i o n 3 ) . - i n c a s e o f an A u t o r e g r e s s i v e n o i s e model, i t w i l l be e s t a b l i s h e d t h a t - under s u i t a b l e a s s u m p t i o n s t h e Maximum L i k e l i h o o d e s t i m a t e s converge t o t h e  t r u e values o f the p a r a n e t e r s  (Section 4 ) .  This  r e s u l t p r o v i d e s a convergence p r o o f o f t h e w e l l know G e n e r a l i z e d - L e a s t - S q u a r e s  (GLS) method, p r o -  posed by C l a r k e  In  Chapter  2, m u l t i v a r i a b l e systems w i l l  d e r e d . The i d e n t i f i c a t i o n viewed a s a simple output  o f m u l t i v a r i a b l e systems cannot be  g e n e r a l i z a t i o n of the s i n g l e  case and, b e f o r e  be c o n s i -  input-single  f o r m u l a t i n g the i d e n t i f i c a t i o n  the f o l l o w i n g c o n s i d e r a t i o n s must be taken i n t o a c c o u n t  problem : the  c h o i c e g e n e r a l l y made f o r t h e c l a s s o f the models ( s t a t e - s p a c e r e p r e s e n t a t i o n ) i m p l i e s the d e t e r m i n a t i o n o f a s u i t a b l e cal  canbni  form and the d e r i v a t i o n o f a c a n o n i c a l s e t o f i n p u t - o u t p u t  relations.  The  problem o f f i n d i n g  s t a t e - s p a c e c a n o n i c a l forms  "have been i n v e s t i g a t e d by L u e n b e r g e r [ l 5 J , G o p i n a t h [ 12 J and Kayne[l6J.  I t c a n be shown t h a t the use o f a s e l e c t o r  matrix  or o f a s e t o f i n d e x e s a l l o w s one t o d e s c r i b e t h e s t r u c t u r e of a c a n o n i c a l model. I n S e c t i o n 2, t h e r e s u l t s r e l a t i v e t o thJS s problem w i l l  Although input-output  be r e p o r t e d .  the problem o f d e r i v i n g a s e t o f c a n o n i c a l  r e l a t i o n s has been s t u d i e d by many a u t h o r s , no  g e n e r a l a p p r o a c h i s y e t a v a i l a b l e i n l i t e r a t u r e . The methods proposed  by G o p i n a t h [ 1 5 ], Ackernan [ 1 ], Z u e r c h e r L28J  or  Guidorzi[l3 ] the  comparison w i t h  the p r e v i o u s  3,  methods i s e s t a b l i s h e d .  b a s i c d i f f e r e n c e s between the approach p r e s e n t e d  S e c t i o n and  the p r e v i o u s  ones l i e i n the  a d i s c r i m i n a t i o n o f the i n p u t - o u t p u t tended t o the n o i s y  fact  that i t allows  d a t a and  t h a t i t i s ex-  u s i n g the r e s u l t s o f C h a p t e r 1, a  ximum L i k e l i h o o d e s t i m a t o r the e s t i m a t e s ,  in this  case.  In S e c t i o n k,  i s d e f i n e d and  the c o n s i s t e n c y  Maof  i n case o f c o r r e l a t e d n o i s e , i s p r o v e d .  In. S e c t i o n 5, The  In S e c t i o n  s o l u t i o n t o t h i s problem i n the most g e n e r a l case i s propo-  sed and The  are subject to strong r e s t r i c t i o n s .  various- t y p e s  the o p t i m i z a t i o n problem i s d i s c u s s e d .  of minimization, a l g o r i t h m s  are d e s c r i b e d  and  r e s u l t s are  pre-  compared.  F i n a l l y , i n Chapter 3, s e n t e d . The  experimental  t h e o r e t i c a l r e s u l t s of C h a p t e r 1 and  t e s t e d on n u m e r i c a l  examples.  C h a p t e r 2 are  6  C h a p t e r 1:  SINGLE INPUT - SINGLE OUTPUT SYSTEMS  1 - INTRODUCTION  As  pointed  out i n the introductory  o f i d e n t i f i c a t i o n problem may be o b t a i n e d a probabilistic  The  by embedding i t i n  framework, l e a d i n g t o an e s t i m a t i o n  Such a p o i n t of view a l l o w s identification  Chapter, a type  problem.  a r i g o r o u s approach to the f i e l d o f  and c o n s t i t u t e s one o f i t s main  aspects.  a i m o f t h i s Chapter i s to i n v e s t i g a t e the mathe-  m a t i c a l p r o p e r t i e s of the Maximum L i k e l i h o o d e s t i m a t i o n for  various  t y p e s o f n o i s e model s t r u c t u r e s .  (i)  I n S e c t i o n 3, be  the Moving Average n o i s e model w i l l  considered,  ( i i ) I n S e c t i o n 4, the A u t o r e g r e s s i v e be  noise  two c l a s s e s o f Maximum L i k e l i h o o d  be i n v e s t i g a t e d and new r e s u l t s r e l a t i v e  convergence p r o p e r t i e s o f some e x i s t i n g methods w i l l blished.  mo-"el w i l l  studied.  I n both c a s e s , mators w i l l  method  esti-  t o the be e s t a -  2^  PRELIMINARIES  The  class  of linear  discrete-time single  s i n g l e o u t p u t systems c o n s i d e r e d ference  i srepresented  input  —  by t h e d i f -  equation  A C z " ) y(k) = B ( z 1  _ 1  ) u(k) +• n(k)  (1.1)  where |y(k), k = l , . . . . , N |  i s the system output  Ju(k), k=l,....,NJ  i s the system input.  |n(k), k = l , . . . , N j  i s an a d d i t i v e zero-mean noise  :  and  n ACz" ) = 1 +  a  1  BU" ) = 1  i=l  Yl i=0  a.z"  b.sT 1  1  1  (1.2) (1.3)  It. i a assumed that, the noise process can be expressed as a process driven by a white noise  e(k)  . n(k) = H(z~ ) e(k) 1  (1.4)  where  HU-lj ~Sl£bi D(z~ ) i  (1.5)  CCz" ) = 1 +  c  1  i=l  DCz" ) = 1 1  1=1  A  <1.6)  z r ±  d-z  (1.7)  _ i  The L i k e l i h o o d , f u n c t i o n L can t h e n be d e f i n e d lity  density  f u n c t i o n of £ ( k ) , where the numbers £(k) are the  s o - c a l l e d r e s i d u a l s defined H(z  _ 1  as the p r o b a b i -  by  ) £(k) = A ( z ~ ) y(k) - B ( z - ) u(k) 1  (1.8)  1  2 Assuming  t h a t e i s (0, G~ ) g a u s s i a n , the r e s i d u a l ;  £(k) is  e  2 a sequence of independent and g a u s s i a n ( 0 , °~ ) v a r i a b l e s the l o g - L i k e l i h o o d f u n c t i o n A takes the form  and  H  2  C (k) - N l o g tr - N l o g <r  d  e  k=l  2 TT  (1.9)  6  The Maximum L i k e l i h o o d e s t i m a t i o n p r o c e d u r e can then be i n terpreted  as the f i n d i n g o f a model  A(z  _ 1  i n such a way  From  (1.9),.  ) y(k) = B U " ) 1  u(k) + H ( z  t h a t the l o g - L i k e l i h o o d  - 1  )  function A  i t i s c l e a r t h a t maximizing A  (1.10)  G(k)  i s maximized.  Is equivalent  to  9  minimizing the loss  function N"  (1.11)  V ( a , b , c , d ) = ^rr !C £ ( k ) 2  N  "  k=l  where £(k) i s o b t a i n e d through t h e e q u a t i o n o f e r r o r C(k) = H-^z" ) A(z 1  - 1  ) y(k) - i T ^ z " )  In t h e f o i l o w i n g ,  £ = where  — I a d,  a  (1.12)  i s an advantage i n p u t t i n g T ,T ". T d  T , T b e  (1.13) c  =  T  1 2  n  n  d »...d 0  n  yd.  The  there  1  a ~ . ..a  n  1 2 and  k z " ) u(k)  1  Maximum L i k e l i h o o d  estimator  c a n thus be d e f i n e d  as f o l l o w s  the Maximum L i k e l i h o o d e s t i m a t e ( s ) o f p_, say p_, i s ( a r e ) t h e a b s o l u t e minimum p o i n t ( s ) o f  s  E ] L  £ £ S  x  VJJ(E)  =• j i J J  : V (pJJ) N  = min V  N  (  £  )  (1.14)  P  However, from e q u a t i o n *  (1,12), i t i s c l e a r t h a t £ i s non l i n e a r  *  *M  i n c and d„ C o n s e a u e n t l y , the f i n d i n g o f p i t e r a t i v e l y using t o know i f redefine  V, (T>) T  has t o be done  a search r o u t i n e . I t i s then of importance has l o c a l extremum p o i n t s  the Maximum L i k e l i h o o d e s t i m a t o r  This  leads us to  i n the f o l l o w i n g way  10  p £ Sp =  'm  dV(£)  (1.15)  = 0  m  The  estimator  E  ±  (resp. E ) w i l l £  S (resp. 1  Clearly S  x  Q S  £  and E  £  be c o n s i s t e n t i f and o n l y i f  (1.16)  S ) =j 2  consistent, implies E  ±  consistent.  From a p r a c t i c a l p o i n t o f view,, i t i s h i g h l y d e s i r a b l e E  2  i s consistent, E  minimum p o i n t  2  i n c o n s i s t e n t means t h a t ,  even i f t h e g l o b a l  o f the l o s s f u n c t i o n c o i n c i d e s w i t h the t r u e  o f t h e parameter v e c t o r £ ( E ^ c o n s i s t e n t ) , t h e Maximum hood e s t i m a t i o n give a wrong  p r o c e d u r e may n o t c o n v e r g e i n t o  Likeli-  and may then  e q u a t i o n (1,-k)  c a n be r e w r i t t e n a s -1,  (1.17)  D U " ) n(k) = C U ) e(k) x  1  which i m p l i e s that, the n o i s e  the  value  estimate.  The  gressive  that  p r o c e s s i s modeled as an  moving average (ARMA) p r o c e s s .  f o l l o w i n g cases w i l l  be i n v e s t i g a t e d  In the next  autore-  Sections,  11  a) MA  n o i s e model ( D = l ) , T h i s case has  by Astrom {_2. ] , Astrom and  been t r e a t e d  Soderstrom [ ^ ] and  Soderstrom b) AR  n o i s e model (0=1).. T h i s c h o i c e  of n o i s e  t u r e i s the b a s i c i n g r e d i e n t i n the the G e n e r a l i z e d by C l a r k e [ 6  In both c a s e s , be  be  The  p r o p e r t i e s of the  estimates  ( S e c t i o n 3) , the  estirelator  used i n the f o l l o w i n g , A s i g n a l u ( k ) n  is  estimators  are c o n s i s t e n t .  2  concept of p e r s i s t e n t l y  e x c i t i n g of o r d e r  will  i s inconsistent.  a A 3 noise, model ( S e c t i o n ^ ) , the E  proposed  shown t h a t  consistent while  E^ and  of  K  — f o r a MA' model  for  formulation  Least-Squares algorithm  the s t a t i s t i c a l  considered. I t w i l l  struc-  [ 2 ]  exciting i s said  signals will  t o be  be  persistently  if N  lim N—• exists  i  (1.18a)  and  A  Is  Yl u(k) u(k+3) = R ( o ) k=l u  00  n  = [a  U-j)  p o s i t i v e definite.. I f u(k)  1 i=l,....,n  i s persistently  (1.18b)  exciting  of  order n  n n  T  XI  1=0  h. u ( k - i ) = 0  (1.19a)  = 0  (1.19b)  implies h  ±  i=0,..».,n  3. MOVING AVERAGE N O I S E MODEL 3«~1»  Introduction If a M o v i n g A v e r a g e  output  data a r e governed by the d i f f e r e n c e  A(z"" ) y ( k ) = B ( z " ) 1  The  1  model s t r u c t u r e  Mz' ) 1  To  (MA) n o i s e m o d e l i s u s e d , t h e  i s then  u(k) + C(z  1  _ 1  )  1  and  zeros inside the unit that  prime [ t h i s  _ 1  ),  C(z~^~)  that  have a l l  c i r c l e £this  t h e system  " A 3 . The p o l y n o m i a l s A ( z relatively  (1.21)  €(k)  are ergodic  - A2> The p o l y n o m i a l s A ( z ~ )  tion implies  (1.20)  e(k)  (ML) method, i t i s assumed  - A l . A l l the processes  their  )  g i v e n by  y(k) = B(z ) u ( k ) + C ( z  a p p l y Maximum L i k e l i h o o d  _ 1  equation  condi-  (1*20) i s s t a b l e ]  B(z  - 1  condition  )  and  C(z~^~)  implies  are  that the  (1.20) i s c o n t r o l l a b l e  system  e i t h e r , from u or  from e ] .  [  a  say p =|^a  b  c J , i s obtained  by m i n i m i z a t i o n  T  T  T"lT  _b  c l ,  o f the l o s s  function  V (£) = ^  YZ £ ( k )  where t h e r e s i d u a l  (1.22)  2  N  k=l  £(k) depends on p v i a (1.21)  * -1 -1 £ ( k ) = ^ - r y(k> - ? > u(k) C(z  As a first result, tion w i l l  Section  1  ( 2  )  C(z  - ±  (1.23)  )  the g l o b a l minimum p o i n t s o f the l o s s  be c o n s i d e r e d  estimator  _ ±  and c o n d i t i o n s w i l l  t o be c o n s i s t e n t . . T h i s w i l l  be g i v e n  func-  f o r the  be the o b j e c t o f  3.2.  A s mentioned above, i t i s o f i m p o r t a n c e t o know i f t h e r e i s a unique l o c a l minimum p o i n t o f V^(£).. I n p r a c t i c e , t h e r e a r e c a s e s f o r which the l o s s f u n c t i o n can have more than one l o c a l minimum. The r e a s o n s f o r such d i f f i c u l t i e s  are the  following — the model s t r u c t u r e may n o t be  appropriate  — the number o f d a t a , N, may be too s m a l l — the model s t r u c t u r e may have the i n h e r e n t p r o perty  t h a t V^(_I>) bas s e v e r a l l o c a l  minima.  In order to avoid the f i r s t two p i t f a l l s , the f o l l o w i n g a d d i t i o n a l assumptions w i l l be made - M , I t i s assumed that ( 1 . 2 0 ) r e a l l y -  holds  A5.The asymptotic l o s s f u n c t i o n (1.24)  V(£).= l i m V„(£) = E [ £ ] 2  w i l l be considered  The  instead of V^(£).  case covered by the t h i r d explanation  w i l l be the main  object of Section 3.3., where i t w i l l be shown that the model structure considered  implies that,- i n general, a unique l o c a l  minimum cannot be obtained and consequently that  i s inconsis-  tent.  3-2.  Global minimum points Let us define - £  K  the g l o b a l minimum p o i n t ( s ) of V^(p) :  V%>  =  m  ^ V£)  <l-5) 2  P  — £  the g l o b a l minimum p o i n t ( s ) of V ( ) £  V(p ) = min V(jg) M  (1.26)  Astrora has shown [ 2 ] t h a t  £  M  =£  (1-27)  lim jpjj = 2 N-* oo provided  u i s p e r s i s t e n t l y e x c i t i n g o f order *  r e l a t i o n s establish, that function  V (j3.) N  the  true value  n  a  + n,.  D  the g l o b a l minimum p o i n t ( s )  converged) as. N —  p o i n t o f the a s y m p t o t i c  (1.28)  with p r o b a b i l i t y 1  n  t  o  These two of the l o s s  t h e u n i q u e g l o b a l minimum  loss function  V(]D),,  which c o i n c i d e s  with  of the parameters, ja.  T h i s means t h a t , under t h e assumptions A l - A5, =  | £j  Theorem  and t h a t  1,1 The  ML e s t i m a t o r  E.^ i s a s y m p t o t i c a l l y  The  r e s u l t s of t h i s Section  consistent.  do n o t g i v e any i n f o r m a -  t i o n about l o c a l extremum p o i n t s and thus  do n o t prove t h a t JD  converges t o j). The convergence p r o p e r t i e s o f t h e ML method, c r u c i a l l y depends on the e x i s t e n c e the l o s s  l o c a l extrema o f  function.  I t must be n o t i c e d been e x t e n s i v e l y a p p l i e d  (1.20),  of multiple  no g e n e r a l  t h a t , a l t h o u g h the ML method has  to systems whose model i s given- by  result relative  to l o c a l  extremum p o i n t s i s  a v a i l a b l e i n l i t e r a t u r e - e x c e p t i n the case o f a pure ARMA  pro-  c e s s ( B = 0) [ if j . I n the next S e c t i o n ' a c l a s s o f c o u n t e r examp l e s t o a unique l o c a l minimum i s g i v e n  : this implies  the i n -  \  16  consistency  o f E ^ and the non-convergence o f t h e method  bed above, which i s one the most commonly  descri-  used i n system i d e n -  tification.  3-3.  L o c a l extremum Combining  points (1.20) and (1.21) and d r o p p i n g the argu-  ments z "*" and k, f o r c o n v e n i e n c e , y i e l d s -  £  =  AB - A 3  u  +  AC.  AC  Cl.29)  e  AC  S i n c e u and e a r e assumed t o be u n c o r r e l a t e d ,  the a s y m p t o t i c  l o s s f u n c t i o n t a k e s then the form 2 E  2V  AB - AB AC  u  which c a n be r e w r i t t e n , u s i n g P a r s e v a l  2V =  2 °e 2 7Ti  AC  + E  (1-30)  AC — e AC  s theorem, a s  AC  ^ ' ' 7  1  AC  AC  where t h e i n t e g r a t i o n path i s t h e u n i t c i r c l e  and 3* (z) I u  s  the  d i s c r e t e power spectrum o f u .  We can now c o n s i d e r  t h e s t a t i o n a r y p o i n t s o f V, i . e .  the points which are solutions of ^ = 0  Let us f i r s t j = l .. n l  |  Dc .  . After  2irt  (1.32)  simple  / ACC  .  calculations,  i t c a n be w r i t t e n  AC  1A&45  2iri J  t h e s o l u t i o n s o f dV/dc . = 0 ,  consider  (i)  ACC  A B ^ C . - I , 4> (z) z ^ u  1  3=1,...,  d »  AC  (1.33a) or  aS.  J A*C*  J-l,...,n  U  c  (  1  .  3  3  b  )  where  <>  f  z  i  = -  2 AC  °t  -  "* * A  ACC  C  ~  A3-; A'B (  ACC  tic)  B  -A B  ) *  (1.3'+a) a  * n * A (z) = z A(z~ )  (1.3*»b)  B*(z)  a  Since  ****** A  L  = z  b  B(z~ )  (1.3^+c)  C (z) = z  C  C(z  (1.3ifd)  the integrand , the equation  1  _ 1  )  o f 3 V / 3 c . h a s n +n p o l e s ( f ( z ) i s a n a l y 3 a c d V / c £ = 0 h a s s e v e r a l s o l u t i o n s ' i n £_.  18  (1.30),  L e t u s now c o n s i d e r d V / d a a n d DV/Db. U s i n g one  may w r i t e  B  J  AC  3V  AB-AB-  z" u  z  J  u  AC  E  AC  j = l , . . . , n.  A  AC  -j  1 —  E  +  AC  j=0,...,n.  u  AC  (1.35)  or  av  .1!  a.  i=l  '3 - i -— z u AC  E  1  AC n  +  "C E \ z - e " —T AC AC J  z  - i " e  T  1 - i — z u  B - j — z °u AC  E  1=0  (1.36a)  n  v4 E  i  B - i — z u  z- u j  i=l  2>b  AC  i  z^u  i=0  The  (1.36b) c)b .  equation SV  -21 = 0 *a  can  1 - i — z u  then  = 0  (1.37a)  3b  be r e w r i t t e n a s M  - N '  (1.37b) -If  T  19  where M,- IT,. F,. £ and r are d e f i n e d by  M. .  =  E  TB  - i  —  z  [AC N.  1J  .  P. . =  AC  E  1 - i z u .C  - i  —  A  AC  i  E  1 3  u  C  5- z - J u  z  e  (1.39a)  A  AC  A  AC  (1.39b)  z~ u J  (1.39c)  —  C (1.40a)  da  r = -M  (  0  (1.40b)  )  ob  For any C, the m a t r i c e s M and P are p o s i t i v e d e f i n i t e . tion  (1.38)  £. Since  has then, a t l e a s t ,  The e q u a -  one solution i n a and b, f o r any  ( 1 . 3 3 ) ' has s e v e r a l s o l u t i o n s i n £ , the g r a d i e n t s o f V  may v a n i s h f o r s e v e r a l v a l u e s o f  The p o i n t s JD s a t i s f y i n g S . T h i s means t h a t 2  (1.33)  and ( 1 . 3 8 )  belong  to  i s inconsistent..  Remark The above a n a l y s i s i s v a l i d  f o r any (A,B,C). The  non-uniqueness of the e s t i m a t e s i s thus an i n h e r e n t o f the model c o n s i d e r e d .  property  20  We ples  to  a  have  unique  vergence  of  the  drawback  i s  an  thus  local ML  shown  the  minimum  method  inherent  i n  existence  and  property  counter-exam-  consequently  case  the  of  of  of  the  a  MA  model  to  general  con-  model.  This  noise  structure  consi-  dered..  In  the  Autoregresslve  4. 4.1.  noise  section,, model  AUT05EGRSSSIVE, NOISE  a  case  similar i s  analysis  the  equations  case  (1.8)  A(z.~ ) 1  the  proposed.  MODEL  of  and  y(k)  a  Autoregresslve  (1.10)  take  = B ( z -)  the  u(k)  1  +  (AR)  1  Similarly  with  the  ,. i s o b t a i n e d  1  previous by  case,  minimizing  noise  1  — e(k)  1\ _x  lo  ( 1 . 4 D  cC^ ) 1  e<k)  the  the  model,  form  Mz" ) y(k) = rkz" ) u(k) + -  £  for  Introduction In  the  next  function  (1.42)  V ( P ) = 2 I 51  where  2  the r e s i d u a l £(k) i s given  C(k)  =  hold, (Section  C ( z  -  1  )  (1.43)  £ (k)  N  by  ACz" ) y(k) 1  C ( z  _  )  1  1  Assuming  the conditions  A1-A5  we  analyze  the global  shall  4-2)  and  first,  second,  the l o c a l  (1.44)  BCz" ) u(k)  3  of Section  extremum  s t i l l  minimum points  points (Section  A  4-3)  of the asymptotic  sistency  4.2-  -  of  minii'iUUii  points  The  purpose  of this  follows  estimator  First,  shall  we  loss  of the parameters  V, (p), T  11  Second,  p„  ii  we  will  be  do  con-  proved.  i s to prove  E ^ . To  (I.44)  function  shall  s o , we  the shall  asymptotic proceed  bo  obtain A  c  and  ~  AB  that  the global  V(p_) c o i n c i d e s  minimum with  the  point true  p_  show  to v  (1.41)  and  prove  vector,  converge(s)  Combining equation  E^  asymptotic  :  of  V ( p ) . The  section  o f t h e ML  o f the asymptotic  value  and  Global  — j2  function  the estimators  consistency as  loss  that  the global  a s N—»  co .  (1.42)  allows  the equation A  - A S  ' A  \  us  of  minimum  to rewrite  point(  the  error  A  AC  , ,  .  C  K  22  It  then  follows A  2V  E  =  A  AM  1  AB - AB  (1.46)  ,JAC  L  j  and 2V.>  E  AC AC  2 111 T A C  A C  v Z j  U  >z  "  where the i n t e g r a t i o n path i s t h e u n i t c i r c l e  (1.47)  V  | z | = 1.  We c a n now p o s t u l a t e the Lemma  1.1 2V  The e q u a l i t y h o l d s  Proof  (1.48)  o-:  >  i f and o n l y i f p_ = p_  (A=A, B-B and C=C),  r Let us consider  the i n t e g r a l  2 AC (z) - 1 AC  I = 2iri  AC  U  )  dz z  >  0  (1.49)  Then  I = V - 2  Clearly,  2 TTi  since A ( z  _ 1  AC  Z  l Z ;  27Ti  dz z  (1.50)  ) and C ( z ) have a l l .their zeros i n s i d e the  unit circle,(assumption A 2 )  1  and A ( 0 ) = C ( 0 ) = 1 , i t follows that  23  AC,  27Ti  AC  (  Z  )  vdz T  A(0)  0 ( 0 )  A ( 0 )  C ( 0 )  =• 1  (1.51)  0  (1.52)  1 I dz = 1 2lTif z and > I = V - Cr" e  Hence 2Y  The  >  (.1.53)  0-:  e q u a l i t y holds i f and only i f (i)  1=0  which i m p l i e s (1.5if)  AC = AC  (ii)  = 0, w h i c h i s e q u i v a l e n t ,  E provided  u i s persistently  exciting  o f order  n +n , to b  c  AB = AB  Combining  (1.55)  (1,5*4-) a n d (1,55) a n d u s i n g A s s u m p t i o n A3 y i e l d s A- = A, B = B , C = C  (1.%)  Q,E,.D„  For assertion  a l l N, V" (_£) a n d V(jo) a r e p o l y n o m i a l s . N  o f convergence  o f V" t o V as N-»<*> I m p l i e s N  Then,t h e that  V" (p) N  converges uniformly dering  t o V(r>) o n e v e r y  the estimates  i n a compact  compact s e t . Hence, c o n s i -  s e tG allows us t o e s t a b l i s h  the Lemma  1.2 lim  (1.57)  1  TL! = v' w i t h p r o b a b i l i t y 1  TIT  Proof Let«be  an a r b i t r a r y  small positive  r e a l number a n d  be t h e s e t M  (1.58)  £ -£ Since V i scontinuous, min G-G  there  e x i s t s fi >  V(J) >  that (1.59)  V ( £ ) + /? M  S i n c e V" c o n v e r g e s t o V u n i f o r m l y , t h e r e If s u c h t h a t i f IT>M  0 such  exists  an i n t e g e r M  then  (1.60)  for  a l l p 6 G,  Thus  Bin V (£)>  min v(£) - /3> V ( P ) + 2 / 3 M  M  G-G T h i s means t h a t £  N  Finally,  i s i n G^.  Q,E..D.  t h e lemmas 1 . 1  and 1.2  yields the  (1.61)  1.2  Theorem  r  The  4-3  —  Local  so, V  i s we  goal  of  only  In  prove at  a  i s  asymptotically  this  that  _p_ =•  Section  for to  "small" the  recent  the  gradients  that -  of  V(jo)  v/ith  the  estima-  j  T°  respect  ^°  to  paper  signal-to-noise  this  show  i.e.. that  gradients  counter-examples  introduction  overcome  to  T)-  implementation  that, the to  of  i s  consistent,  [23], existence  consistent.  points  asymptotically  shall  vanish  estimator  extremum  The tor  ML  Soderstrom to  a  ratios  of  this  of  one  has  unique  local  :  i s  this  a  method.. H o w e v e r , additional  shov/n  the  minimum major  of  V,  drawback  i t will  be  assumption  allows  conditions  for  shown us  problem*  V/e  shall  of  V  to  thus vanish  investigate  the  the  •  i.e..  ^7=2  Defining  the  (1.62)  polynomials n  E = IS = 1  +  z~  £ f k=l  k  (1.63)  tn ^ = ^ = | ^ k  z  ~  k  (1-64)  where n = n  (1.65a)  a + n,b  (1.65b)  m = n, + n D  C  c o n f e r s to V" the form 2V"  =  E  r  -, 2  A F  +  AG  E  F B  6  -  HA  (1.66)  A  and allows us to rev/rite (1.62) as n I  .  ^ ~  da. k=l "~ df  = o  j=l,-..,n  (1.67a)  0=0,....n,  (1.67b)  k - JJ  m 3V  c  Sb.  0  k=0  ^ —r~= 0  i  m  n 5V  = ^ > a, . ~ ~ = / \ b Be. k=l ° df. k=0  5V  0  5=1,...,n  (1.67c)  k - ; 5  In the f o l l o w i n g , i t w i l l be assumed that A6  The polynomials A and C, and B and C are r e l a t i v e l y prime.  With t h i s assumption, (1.67) i m p l i e s j=l,...,n  Df. av  _= 0  j=0,... ,m  (1.68a)  (1.68b)  27  Using  i c  E  (1.66),  (1.68)  FB-HA A  + E  e  FB-HA, -u  (1.69a)  0  (1.69b)  = 0  z~^u  A  can be r e w r i t t e n as  o r n  YL i=l  h  i  E  -1  n  , - 3  B - i A  E  AC  AC  2  i=l  f  U  z^u  ro - l  E z  i=0  u  i=l  (1.70a)  = 0  ^ ( 0 )  m  n  YL  +  E  K - i A  Z  U  r^ul  Z  -  —  h  E  z  -X  u  z  3  U  +  dv  dh.  i=0  (1.70b)  L e t us d e f i n e the m a t r i c e s  M  H  E z  l =  2  -X  AC  1  \z~i AC  6  _  B - i  jz  =  u  £  6  i=l, 3=1,  z- u  E  r -i z  E^z  - 1  u  u  7  A  z'^uj  . ,n  J  1=1, 3 = 1,  A  N =-  (1.7D  . ,n .. ,n  i=l,....,n  (1.72)  (1.73)  3=1,...,m  i=1,  • . . , EI  , i = l , . . , , ra  (1.7'+)  and  the v e c t o r s  f = |VV" n] ?  „  U  -  = 4-(o>  T  ? 5 )  ( 1  -  7 7 )  (1.78)  The  e q u a t i o n (1.70) t a k e s then the form 0^ N  or  + M ) f_ - N h + £ = 0  (1.79a)  f - P h + r = 0  (1.79b)  2  T  equivalently ^ l M  +  M  2 ~  h = P"  1  N  N  T  P  _  1  n T  ) £ =  f + P  - 1  N  p  _  1  H ~ £  (1.80a) (1.80b)  r  Defining (1.81)  v = | u  yields H 2 N N  T  P  [R (i-j) =|R  u v  (i-j)j  (1.82b)  =[R  v u  (i-j)]  (1.82c)  the m a t r i x M  Is positive  definite,  (1.82d)  =|^R (i-j) ] u  -1 Clearly,  (1.82a)  ]  y  N P  T N  i spositive  the matrix  + M  2  definite.  - N  Since  N^, as  a  sum  of  two  symmetric p o s i t i v e  definite  and  then  The  equation 1  matrices,  thus  a unique s o l u t i o n ,  1  1  T  1  T  This  £>2  =  j JE]  one  (1.83a)  Theorem  *  of V vanish  o f _p_. F r o m T h e o r e m 1.2,  M.L.  the  estimator  It  E^  AR  noise  must be  are  above s t u d y  verified  algorithm,  thing  e l s e than  method f o r w h i c h the  a ML  proposed  v i a a g r a d i e n t a l g o r i t h m . The  establish  the  Before  made-  A1-A6,  -  i s that  the  -  iiL method,  n o t i c e d that the Generalized.  identification  comments  coincides  model, i s convergent.  (GLS)  thus  value  one  i s asymptotically consistent.  consequence of the  a s s u m p t i o n s A1-A6  c a s e o f an  minimized  this  for  1.3  A direct  in  gradients  +  that  The  provided  a  (1.83b)  p-lj.  1  N  proves t h a t the  value  T  2  have thus established t h a t under assumption  a n c  by  1  1  1  w i t h J D . We  given  2  1  only  positive  (M +M -IfP~ N )~ (NP~ r-q)  h = P~ N- (M +H -NP" N )- ( p-lp_ )  and  is  non-singular.  (1.80) h a s =  definite  convergence proof  concluding  we  shall  of  by  Least-Squares  Clarke [ 6 ] i s  no-  loss function i s  t h e o r e m s 1.2 the  proceed  GLS  and  method.  t o make some  about the v a r i o u s a s s u m p t i o n s w h i c h have  been  1.3  /{..Iv, Comments The that  reason  the values  why a f i n i t e N c a n c a u s e d i f f i c u l t i e s i s f o r f i x e d JD, a r e s t o c h a s t i c v a r i a b l e s  o f V (_p_)» N  w h i l e V(_p_), f o r f i x e d £ , i s a d e t e r m i n i s t i c f u n c t i o n .  The  a s s u m p t i o n A6 i s a r e s t r i c t i v e a s s u m p t i o n s i n c e  no m i n i m i z a t i o n ' a l g o r i t h m c a n g u a r a n t e e fulfilled  a t each stage  when a s t a t i o n a r y  that this  of the procedure.  point i s reached,  condition i s  I t i s however  easy,  t o t e s t i f i t i s so or  not.  In process  t h e v/hole  may be m o d e l l e d  s e c t i o n , i t was a s s u m e d t h a t t h e n o i s e as an  process  CCz" ) n ( k ) = e ( k )  (1.8*0,  1  T h i s means t h a t t h e r e be  represented  exists  a noise whitening  by I t s t r u n c a t e d i m p u l s e  response  T h i s assumption has the drawback t h a t there rules  f o r choosing  the order  n  c  reasonably  O  argue the f o l l o w i n g points;.  which can  |,i=0,...,n  a r e no  systematic  of the autoregression  • t h a t t h e c . s , f o r i > n , c a n be n e g l e c t e d . JL  filter  such  H o w e v e r , v/e c a n  c  - an a n a l y s i s o f t h e n o i s e c a n f a c i l i t a t e  the choice of  the o r d e r o f t h e a u t o r e g r e s s i o n - n  c  can be d e t e r m i n e d i t e r a t i v e l y by i n c r e a s i n g i t  u n t i l t h e r e d u c t i o n o f t h e l o s s f u n c t i o n i s no l o n g e r significant.  5 - CONCLUSION In  t h i s C h a p t e r , t h e ML e s t i m a t o r , f o r l i n e a r  i n p u t - s i n g l e o u t p u t systems, has been i n v e s t i g a t e d .  single  The  p r o p e r t i e s o f t h e ML e s t i m a t o r have been e s t a b l i s h e d :  statistical  i t has been  shown t o depend on t h e n o i s e model s t r u c t u r e c o n s i d e r e d .  For  t h i s p u r p o s e , two new r e s u l t s have been o b t a i n e d - f o r a MA n o i s e model, t h e ML method may n o t c o n v e r g e . Counterexamples  t o g e n e r a l convergence c a n be f o u n d .  - f o r an AR n o i s e m o d e l , t h e ML method i s c o n v e r g e n t .  I n t h e next C h a p t e r , t h e above s t u d y w i l l be extended t o the m u l t i v a r i a b l e case where i t w i l l be shown t h a t , once a canonical s t r u c t u r e i s defined, the extension i s s t r a i g h t f o r w a r d .  C h a p t e r 2: MULTIVARIABLE i  SYSTEMS  - INTRODUCTION  As  outlined i n the previous  d e f i n i t i o n ' of systems  identification  freedom  i n the formulation  leading  to take -  into  allows  the  many  the following  The choice  of a  class  response  transfer  function -  :  of  problem,  points  o f models  general  degrees  of the i d e n t i f i c a t i o n  account  -  chapter,  :  impulse  state-space  representation.. -  The determination  -  The choice  of the  -  The c h o i c e  of the optimization  When is  important  treated in  a in  t o have  This  cannot  of view.  unified  an a b s t r a c t  (i) multivariable  then  be  The choice  done  systems Such  highly  obtain  choice  the determination a  from  suitable  a  problems, i t  of the system  purely  desirable  procedure mathematical to  achieve  a n d , by e m b e d d i n g  general  that  them  results.  f o r the class  i s generally a  such  type  problems  made  signals  algorithm.  of the i d e n t i f i c a t i o n  of these  framework,  representation^ -  goal  of input  estimator  and s o l v i n g  I t i s , however,  approach  class  the particular  and t h e f i n a l  mind.  point  formulating  of a  of  o f the models state-spsce  implies of the system  canonical  form  order  and o f  of  - the d e r i v a t i o n of a set of input-output  The use o f a s e l e c t o r m a t r i x S,  relations.  as suggested  by  G o p i n a t h [ 1 2 ] , o r o f a s e t N of i n d e x e s , as shown by Mayne  [16]  a l l o w s one  These  t o d e s c r i b e the s t r u c t u r e o f a c a n o n i c a l model.  approaches have t h e drawback t h a t t h e r e i s no method f o r the c h o i c e of S o r N. to input-output  However, s i n c e such a method s h o u l d be a p p l i e d  sequences, t h i s p r o b l e m cannot be p e r f o r m e d i n  r e a l i s t i c c a s e s - i . e . when no p r e c i s e a p r i o r i knowledge of noise c h a r a c t e r i s t i c s i s a v a i l a b l e .  The v a r i o u s a s p e c t s o f  the the  d e t e r m i n a t i o n o f a c a n o n i c a l s t r u c t u r e w i l l be t r e a t e d i n S e c t i o n 2.  Although  the problem o f d e r i v i n g a s e t o f  r e l a t i o n s f r o m the c a n o n i c a l s t a t e - s p a c e  input-output  r e p r e s e n t a t i o n has  i n v e s t i g a t e d by many a u t h o r s , no u n i f i e d a p p r o a c h can be The methods p r o p o s e d by G o p i n a t h [12],  in literature.  Z u e r c h e r [28] o r G u i d o r z i [13] I n S e c t i o n 3,  i t i s shown how  are subject to s t r o n g  found  Ackerman  o f the system  Moreover t h i s approach i s extended t o the n o i s y  c a s e i n w h i c h a s u i t a b l e n o i s e model i s i n t r o d u c e d i n such a f a s h i o n as t o p r e s e r v e the advantages o f t h e d e c o m p o s i t i o n even i n t h e case of c o r r e l a t e d n o i s e .  [1],  restrictions.  t o work out t h i s p r o b l e m i n the  most g e n e r a l c a s e , p e r m i t t i n g t h e d e c o m p o s i t i o n i n t o subsystems.  been  -  (ii) described  In Section k,  a Maximun L i k e l i h o o d estimator i s  and the s t a t i s t i c a l p r o p e r t i e s of the Maximum L i k e -  l i h o o d estimates are investigated..  ( i i i ) F i n a l l y , i n Section 5, the computational aspects are discussed. Two  c l a s s e s of o p t i m i z a t i o n algorithms  are des-  c r i b e d and compared.  2 - CANONICAL 2,1.-  STRUCTURES  Introduction The c l a s s of l i n e a r d i s c r e t e - t i m e r a u l t i v a r i a b l e systems  considered  i s represented by the s t a t e equations  ' z ( k + l ) = Fz(k) + Gu(k) £(k) where z ( k ) f R  n  = Hz(k)  X-R  (2.1b)  ( s t a t e v e c t o r ) , u_(k)CR  put v e c t o r ) , F £ R and H £ R  (2.1a)  n  x. R  In  (input v e c t o r ) , ^ ( k ) £ R  (state matrix), G £ R  n  (observation  n  x R  m  (out-  r  (control matrix)  matrix).  I t i s w e l l known (see e,g, [ 15 ] ) that. (F^, G-^,  H^)  and  (F^, G-,,, H-,) are s i m i l a r - i . e , they l e a d to the sane t r a n s f e r f u n c t i o n K(z) =. H ( z l - H ) " ^ — i f there e x i s t s a p n matrix TER" x R such that -  F  " " l ' "  2  ° "2  2  =  T  1  G  - V  1  1  non-singular  <2.2a> (2.2b) (2.2c)  The  non-uniqueness o f ( F , G, H) r e s u l t s i n a degree o f  a r b i t r a r i n e s s i n the r e a l i z a t i o n a l g o r i t h m which cannot be removed by simple  The (F  r  K  —  representation  G, II) i s c h a r a c t e r i z e d by a s e t o f i n t e g e r s t h a t , i f (n, ,n,,,  (F,.  G  2..2..  , H),  normalization.  next s e c t i o n s show t h a t each  and  G  ( n ^ , n .-..,n ) 2>  s  ,.n ) i s knov/n, the r e p r e s e n t a t i o n  H ) o f ( 2 - 1 ) i s unique..  T  Preliminaries Let  r  =  [ H  T  (HF) ....T  ( H F  N  -  1  )  T  ]  T  A =.[G  FG...- F  n _ 1  c-]  (2.3)  be,  r e s p e c t i v e l y , the o b s e r v a b i l i t y and c o n t r o l l a b i l i t y  matrices.  (F,  G ) and ( F , H ) a r e assumed t o be, r e s p e c t i v e l y , c o n t r o l l a b l e  and  observable,  which i s e q u i v a l e n t t o  (2.4)  rank(T) = rank ( A ) = n  ;  T L e t h^  denote the i - t h rpw o f H and l e t I and J  denote the s e t s I = { J  1,2  = { J  where l ^ j ^ ^ r  2  rj  , - . - . J  for a l l k =  s  -  (2.5)  )  (2,6)  1,2,... . s ,  s^Tr. J i s a permutation  o f any subspace o f I .  L e t T be the n o n - s i n g u l a r  (n x n) m a t r i x  defined  by h. —1 —h l. F  T.  T  T. T =  T  ^2  T.  X  h-> —x  0.  Since  the pair  (F,H) i s observable, (n +l) ±  i € J  F  i € J  (2.7)  1  T non-singular  implies  = s  (2.8)  T = P where P i s a p e r m u t a t i o n  (2.9)  matrix  From ( 2 . 7 ) and ( 2 . 9 ) i t i s . c l e a r m a t r•iixx T i s c o m p l e t e l y  d e f i n e d by e i t h e r  that the transformation  the s e t j n . ,n. ,...,n. \ ' 1 2 °s 3  or t h e matrix. P, T h i s m a t r i x i s n o t h i n g  else than  J  J  the s e l e c t o r  matrix, which i s the basic concept of the approach suggested  by  G o p i n a t h [ l 2 ] , A l t h o u g h t h e s e two d e f i n i t i o n s o f T a r e e q u i v a l e n t , t h e s e t o f i n d e x e s f n . , n . , . . . , n . 1 , r a t h e r t h a n P, w i l l be ' l 2 s> used i n the f o l l o w i n g . J  2.3-  Canonical  forms  Defining state-space  J  J  t h e new  state vector x(k) - Tz(k) y i e l d s the  equations x(k+l)  = Ax(k) + Bu(k)  (2a0a)  y_(k) = C x ( k )  w h e r e ( A , B, C) i s o b t a i n e d  f r o m ( F , G, H ) t h r o u g h  (2.10b)  (2.2).  37  We can now e s t a b l i s h  the  Lemma 2 . 1 : Let -  a.  — l  T be the i th rov/ of  -  b. —i  -  c.  — l  — e.  A.  T  be the i - t h row  of B  T  be the i - th row  of C  T  — l  be the i - th u n i t i  i'  = 1,2,.  s,  vector  the  indexes  i-1 ^  = 1  v. =  1  1  k=l  n. + i J ' k  Then (i>  %  T  a. —x  r  = <L l  i£{l,2,."..,nJ-j%  ±+  = a.. —x  T T -ci. . = " -ev. .. i i T T c . = c.  (ii)  jW"-'  i £  T  i  9  1  1  ,v ,...^ J 2  (2.11a)  s  s!  (2.11b)  = 1,2,...,s  (2.12a)  J  —X  i €  —X  Jl,2,...,rJ  Before i n v e s t i g a t i n g these necessary  to prove  Le mraa 2 . 2  is  ±  s  results  further,  it  is  the  : The  triplet  ( A , B,  Let  us assume t h e r e  C ) , defined  by ( 2 . 1 1 )  -  (2.12)  unique.  Proof  and  (2.12b)  - jj ., . . . J )  :  (A  2 >  B , 2  C ) of 2  (2.10)  exist  two r e p r e s e ' n t a t i o n s  ( A ^ , B^, C  38  Let  and r* be the corresponding o b s e r v a b i l i t y m a t r i c e s . 2  Since the representations  are  r and  there e x i s t s a non  similar,  -FT  (2.13)  2 s i n g u l a r permutation matrix P such  1  1  that r  P  r  I. n  i =  P T  "2  -  (2.-14)  M,  •where I n i s the n x n u n i t m a t r i x , Combining ( 2 , 1 3 ) and PF  ±  = Pr T = £  (2.14) y i e l d s T  (2.15)  MT 2  and  T  I  . *  n  The  QED  ^  lemma 2;.l and 2.2  e s t a b l i s h that the knowledge  of a set .Cvf indexes j n^,n ,.. .n } i m p l i e s the uniqueness of 2  the t r i p l e t (A, B, C) c h a r a c t e r i z i n g the state  representation  of a m u l t i v a r i a b l e system.  In the f o l l o w i n g , we can assume, w i t h o u t . l o s s generality,  of  that 0\ = i  i = 1  s  (2.16)  i.e.  J = |1,2,...sj  l<s<r  (2.17)  39  Hence, the c a n o n i c a l (2.11) bit  and ( 2 . 1 2 )  form of the t r i p l e t  (A, 3, C) , g i v e n i n  can be r e w r i t t e n . . The m a t r i c e s A, B and C exhi-  the f o l l o w i n g  structure  ( i ) A matrix n^+1 n^+l XL 1  A =  (2.18)  (n.+l) = n  +1  n s •n where  A^,i=l,2,  £(n^+l) x n J  . s , i s the r  matrix  n  0  0  0  0  . . . .  0  1  0  0  0  0  1  0 n  a. —x (ii)  ± +  l  (2.19)  T  B matrix B  n  n^+1 n^+l  B =  n  B s «-m,-  +1  n s  4-  (2.20)  v/here  , i =1 , 2 ,  ,s, i s the  (n +l) x m matrix i  T x T B_. =  ^.+1  ( 2 . 2 1 )  x  n.^+1  T b — -o. +n. x  l  l  ( i i i ) C matrix T  ( 2 , 2 2 )  T  r-s c —r-s T  n  The  s t a t e .equations take t h e n the form  41  x  (k+1)  (k)  v  —  1  v  x  x  v  ( 1  +  2  n  k  +  1  x.  )  1  (k+1)  x , V +n  l  n  *v  ~V i n  (k)  (k+1)  A  2  —  +  ( ) k  2  2  1  (k)  v  i  ^„  2  2  ^ T  u(k)  ~b V  n  2  •  •x  s  *S>  (k+1)  b  Ck)  s  T  —  s  A  x  v +n S  (  k  +  1  )  X  V  +  <  n  s s  8  k )  b  T  — V  +n  s s (2.23a)  Za  0 0  T •v.. l  Z  where  2  (k)  Ji =  1  s  x (k)  (2.23b)  i ^ k ) = [y (k) ±  ^2  < k )  =  t y s  +i  ( k )  y (k)...y (k)] 2  y  (2.24a)  T  s  s + 2  (k)...y (k)]  (2.24b)  T  r  Having obtained a c a n o n i c a l s t r u c t u r e f o r the matrices A, B and C, a s e t o f i n p u t - o u t p u t from (A, B, C ) . Remarkable  e q u a t i o n s c a n now be deduced  features of t h i s formulation are  t h a t i t e x h i b i t s t h e s t r u c t u r e o f t h e system and t h a t i t shows t h e l i n k between t h e i n t e r n a l  (state-space)  the e x t e r n a l (input-output) equations.  r e p r e s e n t a t i o n and  T h i s extends t h e r e s u l t s  of G o p i n a t h [ 1 2 ] , Zuercher [28] and G u i d o r z i [ 1 3 ] .  3 - CANONICAL INPUT-OUTPUT EQUATIONS 3.1 I n t r o d u c t i o n  A d i r e c t consequence  of the s t r u c t u r e of the matrices  A and C, d e r i v e d i n t h e above S e c t i o n , i s t h a t t h e o r i g i n a l system has been decomposed i n t o s i n t e r c o n n e c t e d  subsystems.  The main g o a l o f t h i s S e c t i o n i s t o d e r i v e an i n p u t - o u t p u t r e p r e s e n t a t i o n o f t h e system such t h a t t h e subsystems can be separately  identified.  S e c t i o n 3.2 w i l l be concerned w i t h t h e n o i s e - f r e e  case  while  the noisy  3.2..  Noise-free  divided  into  y_p(k)] b e i n g meters i s  an  (2.23) t h e  to  related  t o x(k)  [resp.  the derivation  3-3.  i n Section  input-output  output  vector  £(k) can  ^ ( k ) and ^ ( k ) , £ ^ 0 0 £resp.  through  a relation  whose  unknown] . The aim o f t h i s  o f an i n p u t - o u t p u t  the parameters  parameters  be t r e a t e d  two c o m p o n e n t s  a r e known  involving  will  version  According be  case  equation  of the matrices  equation  u_  »-2L2  COn  A  a  n  section  u  and B  ^ ^ ^- S  ^  n  para-  n  e  and  then  unknown  o f C.  3.2.1. p a r a m e t e r s (2.19)  From subsystem,  i  =  (2.21),  and  1,2,...  ,s,  Ck)  =  x v  o f A and 3  i s described  x  v  i  *v  +  (  1  k  )  i  k  +  v  +  i  Combining  x  y  +  1  1 +  ( k )  (  2  k  i  V n.-l< > X X x  =  (k)  n  i t follows  )  +  equation.  b / u ( k ) i  u (  +  )  k  i  =  X  v .  = a .  +  n  (  k  +  )  X X T  x(k)  +  i  (2.22)  thei - t h  by t h e s e t o f  b /  +  that  *  V  b „  n , - l X X T +  i  and (2.25)  leads  to  n  *  (  u ( k ) i  k  )  (2  1  x: (k) i  = y (k)  x  = zy (k)  v  (k)  i  x _ (k) v  x  = z  + 2  v n i i  ( k )  +  =  ^ V  2 y ; L  (k)  ~  0  u(k)  T  -D^  b  1  bi  -  7  T + 1  u.(k).  + n i-1  u  (  k  - b zu(k) T  v  J ^  )  i  1  1  1  "  i  1  H.( ) k  (2.26)  Remark  I t must be emphasized operator, defined by z~  J  that  i s the time delay  f(k) = f(k-j)  Then, since x(k) =  V  ^ • + 1 n1  (  1  k  )  '  ' x.. (k)  I  x , . (k) v +n s s A  (2.27)  the whole s t a t e vector can be expressed as x ( k ) =. H(z)  Z l  ( k ) - N(z) u(k)  (2.28)  45  where  1 1 1 1  z  Z  M(z) =  |  1  1  0  |  °  1 1 1  i  1 1 . . .  1  1  z  •  •  •  i  l  1| i  | 0  (n x s )  |  L_  |  1  [  1 i  o  1  1  i 0  j  l z  j  *-  1  l  1  and  1  !  n 2  =  (2.29)  0 1  b  V  T 1 +  n -l  Z  +  b V  1  n  i  - 2  —•  +  +  n-i-1 V  Z  b  m x  0 b "*2 T  n -l  T  2  Z  N(z)  ^  n -2  +  2  2 +  *  +  2  T  V  2  = • *  0 b  T  •  * v n -1 s s +  +  Z  ^V  +-n  s  -2 s  +  ''  -• • ."'"V s  (2.30) The s u b s t i t u t i o n of (2.28) i n t o (2.10a) leads t o the i n p u t output r e l a t i o n  [ ( z l - A) H-J^Oc) = [ ( z l -A) IT + B ] u(k.)  (2.3D  In ( 2 . 3 D , howovjr, only the ( v - l ) t h , (N), - l ) t h , .... 2  (\^ - l ) t h , n-th equations are s i g n i f i c a n t , the remaining ones s  47  being i d e n t i t i e s . the  By r e m o v i n g  these  identities,  ( 2 . 3 D takes  form P(z) v ( k ) = Q(Z) x  (2.32)  U(k)  where P and Q a r e p o l y n o m i a l m a t r i c e s i n z  P(z) = ^ljCz)j i  1, . • >  Q(z)  1, ..,s  ij  (z)  of  (2.3D+1  = </, , z  n  1, .  (2.33b)  . ,10  a n d 0, . ( z ) a r e o b t a i n e d  by s i m p l e i n s -  I t follows a.  j  n.  ,  - a. r ,  z.  i = 1,.. . , s  Q* . ( z ) =/3  1, .. , s  =  The p o l y n o m i a l s P . . ( z ) pection  (2.33a)  s  V  l  _ z - a. x,».  j =  1,. .. , s  (2.34a)  j =  1,...,m  (2.3*+b)  .z " + 1  1  i  = l,...,s.  where t h e / ^ ' s a r e r e l a t e d  t o t h e a*s and b's t h r o u g h t h e  equation 1  fii. p  l l  '21  21  nl  b  =  ftim  b  12  J  lm  2m  J  L  nl  nm  (2.35)  48  with  i,v. l  a  +  -  a  h i )  =  L  " ^,^+2  '  \  '  :  \  '  -  a  (2.36)  -  i , V  n  i  i,V +2 ±  L  (2.37a)  i i  o  x,V.+n. ' x x  a  i,-*.+l  ~ i,S» +2 a  J  J  - a  i'Y  0  2  (2.37b) -  a  0 0  the  matrices  being  [(n  i  + 1) x (n^. + 1) J .  Remark The  m a t r i x L i s always non s i n g u l a r  s i n c e d e t ( L . . ) = cf. .. xj  x j  : d e t ( L ) = 1,  49  We then o b t a i n s subsystems whose i n p u t - o u t p u t d e s c r i p t i o n i s  p  i i  (  z  )  y  i  (  k  )  +  +  p  i s  (  z  )  y  (  k  )  =  s  Q^ (z) 1  U ; L  ( k ) + ... + Q* m (z)• u (k)  i=l,..,s  ffl  (2.38) D e f i n i n g the i n t e g e r s n\ = max ( n , n , ... ,. n _ , 1  £  i  1  n ,+l, n , j  .  ±+1  , n ) Q  i=l,...,s  (2.39)  ,and the parameters Pjk  q  Jk  = " i,-> .+n.-k+l a  s s  A ir -k I,J1  1 +  +  3=1,...s  k=l,..,n l  3=1,..,  k=l,..,n.+l  J+  S  i=l,..,s  (2.40)  a l l o w s us t o d e f i n e the r e c i p r o c a l p o l y n o m i a l s  , "  • n.-n.+l  if  . +  = cf.13", z i-l,_,,S  j l  Z  +  n..+l 3 V  n.-n.+l 1 J  P  n.-n.  +  j=l,..,s  Z_ '  7  P  l. 3k  . +  P  j , n +1  -n. Z  n .-n. -k+1 0 l Z  (2.41)  n.-n.  X  X  „ X  =• j l q  Z  .  ,  j2  q  +  n.-n.+l  X  X  X  Z  .  — •  +  -n.  x  , +  q  o,n. l  l  Z  +  n .+1  a  n.-ru-k+l q  kk=l =l  ik  J  x  z  i  k  (2.42)  j=l,...,m  i=l,...,s  (2.38) i n t h e f o r m  and t o r e v / r i t e  P  1  ( z ~ ) y ( k ) + ... + P ^ U " ) y ( k ) = 1  i l  1  x  Q  s  (z~ )  u ( k ) + ... + Q  1  i l  x  In  (z~ ) u ( k ) 1  i f f i  m  (2.43)  i=l , . . , s  summary, a s e t o f s i n p u t - o u t p u t  equations  of t h e form s  m  Yl  1  j=l  =  y M  P^A^ ) 0  X^0..(z ) _ 1  0=1  J  J  (2.44a)  u (k) J  n.+l J n . - n +1  , P  i0  ( z  ~  }  ^ i j  =  2  +  \ ^  . p  jk  Z  n.-n.-k+l i=l,..,s  (2.44b)  n. +1 x  1 Q  i0  ( Z  "  1 = 1,  / )  •  has been  ^1  =  j  • " q  ^  s obtained..  k Z  ^-m-k+l  J=r,-.-,s (2.44c)  (2.40),  Recalling parameters  of A  (2.44)  and  3.2.2, In system is  derive vided  a by  be  used  set of  to  estimate  the  C  equations-(2.44), only  order  i n order  B.  Parameters of  dynamics,  used.. I n  can  the  which, a l l o w  information  to i d e n t i f y  equations  the  making  contained  matrix use  us  of  C, the  we  to identify  the  i n u_ a n d shall  now  information  pro-  y_ . 2  According  to  (2.23),  i (k) 2  i t follows  '(2.45)  = Cx(k)  where T  ^2  T  C =  (2.46)  c —r-s T  Then,  combining  (2.46)  2 (k) 2  or,  and  = CM(z)  (2.28)  yields  v ^ k )  -  CN(z)  u(k)  (2.47)  - £ (k>  =  Q.«(z)  u(k)  (2.48)  equivalently  P*(z)  v (k) x  2  52  where P ' ( z ) a n d Q'(z) a r e t h e m a t r i c e s  P ( z ) •= C M ( z ) =  F  ple  P_  z  )  (z)  i=l,. j=l,.  . ,r-s  (2.49a)  i = l,. J=l,.  ,r-s  (2.49b)  and  a r e o b t a i n e d from  sim-  calculations  •* P..(-z)=c.  x  element  (  Ci  Q ( z ) = CN(z) =  whose c o n s t i t u t i v e  i J  ,  x ,  0  z V  n. + c. J  n .  n - l - , z  i.VV "  J  1  + . . . + C .  .  n  X , \> . + 1  z + c .  X,  J  J  i  t *  0- .(z) =  10  . zn - l jn,x  v  j = l,...,s  n - 2 .+ .  jn-l,i  i in  = l,...,c-s  + t .^  (2,50a)  . Z• + ^. . ^ , A/ , .  (j-l)n,x  = l,...,r-s  V .  'j = l , . . . , m  (j-l)n+l,x (2.50b)  which  n = max(n.) s  *  7 (3-l)n+k,i  =  ^  n  (2.5D  x  u  -k+1  7  £ a  V/e t h e n o b t a i n r - s s u b s y s t e m s  ° .-V i  + v + k  -  1  b  v  u  +  v  ~ ^ 1  (2.52)  whose i n p u t - o u t p u t d e s c r i p t i o n i s  53  p  ii  ( a )  .y'i  ;Q  i l  ( k )  —  +  + p  ±sy  ( k ) s  - W  k  )  =  ( z ) u ( k ) + ... + ^ ( z ) u ( k ) :  Recalling  P  ( 2 . 5 D and i n t r o d u c i n g  jk  =  C  qj:, k 3  s  +  3  = #\ jn-, k + l , i.  j = l ,». . . ,>m o  k=l,..,n.. + l k = l, , , .5, n  (2.34)  i=l,...,r-s allows us t o define P. ( z ) = z L  J  n  the r e c i p r o c a l  polynomials  (z)  p  3  . n .—n . n .-n+1 = p.,z + p ^ z + ... + p . . J  J  -jl y =  t  _1  Q. . ( z xj v  32 n .-n-k+1 p * z  _«  ) = z  «v  ,,z"  J  n  -j.n^+l  ±  J  k=l  v  (2.53)  t h e parameters  J=l>-->  i,v. n.-k+l 3  H  i=l,...,r-s  m  i=l,..,r-s  j=l,..,s  (2.55)  k  »*  Q. . ( z ) ^13  i -1 i -2 , i -n q .,z +q._z +.... + q . z j l " ^32" "* \ j , n J  n  •k=l and  t o rev/ri-.e  q^z""^ J K  (2,53)  i=l,..,r-s  i n t h e form  3=1,..,in  (2.56)  P^C*-' )  (k)  1  Q  il  (  z  y i  "  1  }  u  ...  +  l  (  k  )  F^Cz" ) y ( k ) - y 1  +  s  +  +  in  Q  ( z  "  1 )  u  m  e + j L  (k) =  i=l,..r» -s  ( k )  r  (2.57)  Remark (2.54)  Using in  and ( 2 . 5 2 ) ,  the q , 1  's car. be  expressed  t e r m o f t h e p :. 's ~ n -n+k s u 3  J  q* J  =  k  k  (2.58)  p « , . b, •. ^u,n -v-n+k+l ^.+v-.l,j 1  u=l  v=l  u  s o t h a t t h e number o f u n k n o w n p a r a m e t e r s i n ( 2 . 5 3 )  I n summary, a s e t . o f r - s i n p u t - o u t p u t the s  form . 1  k  +  n  r P  a i  i j  of  z  ?  i =  ^  C^Cz" ) = 1  QT (z" ) u.(k) 1  (2.59a)  *  +  .1 (  equations  m  P . ' ^ - ) y ( k ) - ^ - ; ( ) = YL  ^  i s n.  p  jk  n.-n-k+1 J=l,^-,s  z  q^z  k  j=l,,....,m  (2.59b)  (2,59c)  i=l, ,,. ,r-s ;  "has  been  Recalling  obtained. (2.54), (2,59) a l l o w s u s t o e s t i m a t e  o f t h e m a t r i x CT,  the parameters  (2.44)  Equations input-output class  (2.10).  description of  of canonical state-space  input-output  extended  The  c o n s t i t u t e the canonical equivalence  representations  (2,44)-(2..59)  description  In the next  (2.59)  and  to the case of data  corrupted  (2.10)  has t h u s been  Section, the r e s u l t s by  between the  obtained  and t h e obtained.  above a r e  noise.  3.3.- N o i s y . v e r s i o n If corrupted  we assume t h a t t h e i n p u t a n d o u t p u t s e q u e n c e s a r e  by an a d d i t i v e y (k)  =3^00 +  u (k)  = u ( k ) + w (k)  ±  ±  the  noise  p  p  Ii  ±  ±  (2.44)  equations  v (k) ±  (2,59)  and  = Q ».  +  'zi ~ Z  2  p  I  take  i=l,...,r  (2.60)  i=l,...,m  (2.61)  the form  QI  + x  = Q'ii +  (2,62) - v - + q'w  (2.63)  2  where v (k)  = [v^k)  v (k)  =  1  2  [ s l v  ( k  +  (2.64)  v (k) 2  v  >  s 2  ( k  +  v(k)  = [v^(k)'  v£(k)"  w(k)  = [w-^k)  w (k) 2  T  >  J  T  (2.65) (2.66)  ... \W]  T  (2.67)  The i - t h c o m p o n e n t n ^ ( k ) n(k)  = P v  o  f  t  n  e  noise vector (2.63)  + Q w  d e f i n e d by s n  (k) =  m P.^z  0=1  has  - 1  )  O.Az' )  v. ( k ) +  a power-density  spectrum  (2.69)  w, ( k )  1  j = l  J  J  g i v e n by  s  m 0 . .(r )  Q, (S) ^  0=1  where  v^  Since $  n  n  i  a n d <|>  ±  a  j  are the power-density  (%) c a n be e x p r e s s e d  <*  1  S  W  i  s p e c t r a o f v . a n d w. , 1  1  1  n  H.(r) = ,-1  1  as the product  4>n. i%) " = *" n. V%) rn. (r ) i i l then  (2.70)  (<?)  X  T  n  ^  i  —  r  <r )  -  (2.71)  (2.73)  constant  is  the t r a n s f e r  function  Since, i n addition,  ofa realizable  filter.  (2.73) i s e q u i v a l e n tt o  *  ,-1,  ( ? ) H . ( ^ ) \(%~ ) X  N  = cl  (2.74)  57  H.(^ ^) i s the t r a n s f e r f u n c t i o n of a 'whitening -  filter.  I t f o l l o w s immediately that n (k) = ±  H ( z- 1 )  e,(k)  (2.75)  x  ±  where  e^(k) i s a sequence of independant E [ej  =  random v a r i a b l e s  0  (2.76a)  E [ e . ( j ) e . ( k ) ] = <r\ cf If  (2.76b)  the whitening f i l t e r i s represented by i t s impulse  response,  the process (2.?5) takes the form of an a u t o - r e g r e s s i v e process n (k) =  e (k)  D.U" )  (2.77)  1  V  where  i  D. ( z " ) = 1 +  d^z"'  1  j=l  (2.78)  3  The equation ( 2 . 6 2 ) can, then, be r e w r i t t e n i n the form Py  1  = Qu  +  De  (2.79)  where e(k) = [e-^k) e ( k ) ... e ( k ) J 2  DizT ) 1  = diag  ^(z- ) 1  s  V '^ 2  T  (2.80) (2,81)  58  The  (2.63),'  equation  i n the  sane manner,  becomes  u + D  (2.82)  e  where  r • (k)  i  D ' ( Z  _  1  =  )  e (k)  .  2  '  e  r - s  (  k  )  ]  T  (  1  diag D  V/e t h e n o b t a i n  1  (  Z  the  _  1  D  )  noisy  r-s  (z  version  X  of  2  *  8  3  )  (2.84)  )  the  equations  (2.44) and (2.59)  Yl  5=1  m  P,  no  y  Az- ) 1  10  Yl  =  Q... . ( z  0=1  )  _ 1  u.(k)  1 J  3  +  ^ D,(z- )  e  X  (k)  1  (2.85a) m  Yl 5=1  P.'.CZ" ) 1  3  (k)  - y  s  i  ( k )  = Yl  oj  - - -  -  1  J  1—  (2.85b)  s  These r e s u l t s g e n e r a l i z e equivalence  between the  input-output  It  those obtained state-space  i n S e c t i o n 3.2-  representation  and  d e s c r i p t i o n o f a m u l t i v a r i a b l e s y s t e m has  been e s t a b l i s h e d i n the  m u s t be  advantages of the has  +  been p r e s e r v e d  case of data  pointed  out  t h a t , as  d e c o m p o s i t i o n of — In  the  corrupted  the  sense t h a t  by  revealed  system i n t o  The the thus  noise.  by  (2.85),  the  subsystems  these subsystems can  be  s e p a r a t e l y i d e n t i f i e d - a l t h o u g h , no r e s t r i c t i v e  a s s u m p t i o n on  n o i s e c h a r a c t e r i s t i c s h a s b e e n made..  I t i s now a s i m p l e m a t t e r cation  p r o b l e m . However, b e f o r e  blem,, we s h a l l  3.4-  proceed  to formulate  stating  the i d e n t i f i -  and s o l v i n g  this  pro-  t o some c o m m e n t s .  Comments The s t r u c t u r e o f t h e m a t r i c e s A, 3 a n d C, g i v e n i n  S e c t i o n 2,  and, c o n s e q u e n t l y ,  equations,  derived i n Section 3,  of the indexes ficient  n^.  the s t r u c t u r e of the input-output  method f o r the f i n d i n g  H o w e v e r , v/hatever  o f t h e s e t j n^,  account  criterion  problem  t h e n o i s e whose s t a t i s t i c s  the minimal  r e p r e s e n t a t i o n case  data matrices  t o p r o p o s e an e f n ^ , .... ,  we c h o o s e , s u c h  in  ?"). I t t h e n  realistic  n 0  j »  a method  sequences and  : how c a n one t a k e  into  a r e unknown ? F o r e x a m p l e ,  l e a d s us t o c o n s i d e r i n p u t -  : how c a n we a s s e r t t h a t t h e s e  a r e s i n g u l a r o r n o t ? ( I s a m a t r i x whose d e t e r m i n a n t singular  choice  criterion.  be b a s e d o n t h e m e a s u r e d i n p u t - o u t p u t  would l e a d to the f o l l o w i n g  output  f r o m an a r b i t r a r y  I t w o u l d be o f i m p o r t a n c e  optimal with respect to a given  should  result  seems t h a t t h i s  matrices i s  10~  10  p r o b l e m c a n n o t be s o l v e d  cases.  Nevertheless,  the choice  f o r t h e n . ' s c a n be  guided  by  some  physical considerations —  The  structure  meaning —  may  be  from  zation  assigned  by  the p h y s i c a l  of the state v a r i a b l e s .  I f the j - t houtput free  :  noise  of  than  the  system  i s markedly  the remaining  of the corresponding  ones,  n . could  be  a  more maximi-  advanta-  geous. —  The  number  o f unknown  paraneters  in  (2.85a)  : n+m(n +l)+n^  in  (2.85b)  :  If  n  i s a  order  +  n  multiple  to minimize  choose  i=l,...,s  i  n  n^=  i s  d  i=l,...,r-s  of  s,  i t c a n be  the computing  n/s, since  judicious, i n  requirenents,  the subsystems  are  to  separately  identified.  Another model  : introducing  unknown dure,  parameters  since  creases noise  problem a  noise  which  model  t h e number allows  —  to  ting to  of any  the effect  related  noise  t h e number  the I d e n t i f i c a t i o n  optimization  of proce-  algorithm  increases.  of  the choice  results  However,  dethe  of  the n^  this  effect  of noise  s  on  i s  corrup-  outputs.  the e f f i c i e n c y  algorithms,  since  t o t h e amount  the d i f f e r e n t  improve  tion  to the  increases  of parameters  identification  directly  -  f i l t e r  regard  us  reduce  the  with  affects  the efficiency  when  arises  which  of  some  simple  are sensitive  to  minimizanoise.  M o r e o v e r • s u c h an approach p r o v i d e s which permits the  a probabilistic  framework  us t o e s t a b l i s h the mathematical p r o p e r t i e s o f  estimates.  4 - MAXIMUM L I K E L I H O O D ESTIMATOR i+.l.  Introduction The  Likelihood function  object  of t h i s Section i s to present  e s t i m a t o r . The e q u a t i o n  will  t h e Maximum L i k e l i h o o d e s t i m a t e s  4.2,  Equation  o f e r r o r and t h e l i k e l i h o o d  (Section 4.2)  be d e r i v e d  a Maximum  will  and the c o n s i s t e n c y be p r o v e d  (Section  of  4.3).  of error  Recalling  (2.85)  s  leads us t o choose  t h e model  m  1=1  , , ••,  (2,86a)  s  m  s  i i — •  » > 3?" —  S  (2,86b)  62  where n ,  .+1  n,-n,+l  n,-n,-k+l  (2.87)  n.+l  YL  Q^OT ) =1  n.-n.-k+l q^z" ^ 1  (2.88)  n .+1 P 1  ,. , n .-n-k+1 p^z  Z_ k=l  (z—) ^ 3  J  (2,89)  J  n  i  n  D.Cz"' ) 1  YL d^z" ' i=i *  =1+  n  X  )  (0,  i d  = 1 +: Z L , (T- z j=l  r e s i d u a l s £^(t) [ ^ ( t ) ] ;  r) ±  (2.92)  J  3  1  The  (2.9D  3  1  D.(z  d  [ ( 0 ,  ^  )  ]  3  X  6  independant. and Gaussian  .  Rewriting  (2,86) i n t h e f o r m  63  S  \—'  ^  e(t) = D. ±  P^, y , ( t )  0=1  0. . u . ( t ) "13 3  3=1  1—1 y »#-»•) S 1 —1 yields  (2.93a)  L  ^—• Q_. • u  3=1  3=1  (2.93b)  , , , » j T - S  the so-called  equations  of  error  n.,+1  £  Z_  (t) =  al  - i  y  f~*  3=1  <^— K=l  p.,  1  h=0  y (t+n _n i  i  j L  -h+l)  -  q  0=1  i—1  €,(t)  j » « • j  3k  u  o(t n.-n.-k-h l) +  +  k=l  (2.94a)  n  s  n  h=0  3=1  k=l  E m  '  .-n. - k - h + 1 ) 0  s  = E?:  -s +1 1 8  3  n. +1 x  m +  y .(t+n  3  0=1  3.—1 j » « • i X * ~ " S  .+1  P,, - y , ( t + n - n - k - h + 1 ) 3 - ^ 3 3  n C  1  "I  q, u.(t-k-h) ^ ^ i k " i k=l v  J  k  J  (2.94b)  64  T h e G a u s s i a n ess the  log-Likelihood  of c  ±  a n d €^ a l l o w s , u s t o  define  functions N  L  i * 2 i  2  L. l  2  S  (2.95a)  i=l,..,s  t=l  1  = -  cri ^  2  ~  x  x  » i (t) G  2  +  Nlog<r!  w h e r e N i s t h e number o f a v a i l a b l e  T h e Maximum obtained  + NTLo 2Tr  £ (t) + Nlogcr  + Nlog27r  i=l,...,r-s (2.95b)  data.  L i k e l i h o o d e s t i m a t e s o f Pj_-pQjLji  a  n  d  by m a x i m i z a t i o n o f L ^ a n d L ^ o r e q u i v a l e n t l y  nimization  of the l o s s  Qj_j  a  r  e  by m i -  functions  ~^ t=l ^Zcf(t) N  W.1  =  i=l,....,s  (2.96a)  l=l,...,r-s  (2.96b)  N  w| = 1  ~~ ^  H £-(t) 2  t=l  Having  defined  t h e Maximum  Likelihood  estimation  i  p r o b l e m a s t h e f i n d i n g o f t h e g l o b a l m i n i m a - o f V/. a n d V/., x x we c a n d e t e r m i n e t h e s t a t i s t i c a l by  examining these  minima..  properties  of the estimates  4-3.- S t a t i s t i c a l p r o p e r t i e s o f t h e e s t i m a t e s  In made :  .  t h e whole -  Section, the following  a n  - -  - A l . To e n s u r e it  assumptions  t h a t t h e model s t r u c t u r e i s a p p r o p r i a t e ,  i s assumed t h a t ( 2 . 8 5 )  really  holds.  —1 ' —1 v F o r a l l ( i , j ) , t h e p o l y n o m i a l s P. . ( z ) ?. . ( z ), — i •— i D .x ( z ) a n d D. x ( z ) a r e assumed t o have a l l t h e i r  _A2  zeros inside equations  t h e u n i t c i r c l e . T h i s i m p l i e s that, t h e  (2.85) a r e s t a b l e .  _ A 3 . F o r a l l i = l , . . . . ,s a n d j = l , . . . , m i n (m, s ) £i=l,.. . , r j = l , . . . . ,min(m,r-s) 1 t h e p o l y n o m i a l s  and  Q j(z""' ') 1  i  ^ ^ ( z "  1  )  and  Q ^.(z~" ")J 1  i  These c o n d i t i o n s a r e f u l f i l l e d controllable _M  P. .(z~^~) a n d  are r e l a t i v e l y  provided  prime.  t h e system i s  from u .  .- A l l s t o c h a s t i c  processes  are ergodic.  Moreover — S i n c e , f o r a f i n i t e number o f d a t a , N, t h e p r o p e r t i e s of to  and  t  another,  will  may c h a n g e d r a s t i c a l l y  theasymptotic  loss  from  one  experiment  functions  V.  = lim  W  i=l,....,s  (2.97a)  v!  = lim  W\  i=l,...,r-s  (2.97b)  be c o n s i d e r e d i n t h e f o l l o w i n g .  - F o r convenience, E N lim  77  _ » o o  N  provided  ^  "  v/ill  denote  J  (2.98)  f(t)  » t=l  the l i m i t  stochastic  f(t)  exists.  process,  I f f ( t ) i s an e r g o d i c  E^f(t)j  i s the e x p e c t e d  value  of f ( t ) .  The  output  d a t a a r e governed by  P i  i  P ii - 1 '  =  2  while  (2.99a)  = Q u + D e  Q H.  +  D  (2.99b)  1  t h e model i s d e f i n e d by  P  z  x  = Q u + D  (2,100a)  e  (2.100b)  Let u s , • f i r s t , two  equations £ =  D•  consider  (2.99a) and (2.100a). Combining  these  yields P P  -1 e + D P P  D  *-l ~ Q - D Q  Then, assuming t h a t u and £ are u n c o r r e l a t e d ~-l F = D  " -1 P P D  A Ki = D  A  allows us to w r i t e  -J  P P  1  (2.101)  and s e t t i n g (2.102)  A  Q — B  "I  A  Q  (2.103)  E  [ i £ ] = E [F. e e  which  T  clearly  implies  Applying  F J + E [G u u T  T  T  E  [  F  £ £  T  p  T  ^  M f  =  theorem,  definite.  V becomes  TO)  R  p  T  (2.105)  ] = V  means t h a t A-B i s p o s i t i v e  Parseval's  (2.104)  G J  T  that  ['£ £ ] >  E  where A > B  T  ^ "  (Assumption  1  )  A4)  (2.106)  i f '  ' 1*1=1 where eTJ  R = E  Let us consider  (2.107)  the i n t e g r a l  [?{%) - i j R [ F ( r ) - i ] - # > 0  J = ~2 l fri i  T  1  d  (2.108)  Then  J where  = V f J  x  - 2 J  2  (2.109)  7  J,  =<fc»  J-  =cb  latter  F(^) F  =1  *  e q u a l i t y i s due t o the  fact that  = D~ (0) P(0) P~ (0) D(0) = I s i n c e 1  P  1  (0) = P  (0)  (2.111)  = R  have t h e i r z e r o s o u t s i d e t h e u n i t c i r c l e  (0)  and  5  F(S) R ~  J |%|  2  The  m=i  (2.110)  R -Tr = R  the  elements o f  (Assumption A2)  and  D (0)  = 1  ±  = D (0) ±  that  = J  Hence  and,  recalling  (2.105) a n d (2.107)  [i £ ]  E  Applying  (2.112)  = V - R > 0  J  - [e  T  £ ]>  E  T  (2.113)  0  S y l v e s t e r ' s theorem i m p l i e s  that  the  diagonal  elements  m u s t be p o s i t i v e  V  The  i  =  E  [  €  i ] ^  [ i ]  E  e  °i  =  '1=1,....8  (2.114)  e q u a l i t y , i n (2.114) o c c u r s i f a n d o n l y i f (1)  - R = 0  J  = V  F  = D"  1  P P  - 1  i . e .  D = I  (2.115)  69  (ii)  t h e second  term  of the right-hand side of  (2.104) vanishes tently ter  1)  exciting  of order  2n + n ^ + 1  (see chap-  - i f  G .= D" Combining  i . e . - provided u i s persis-  P P"  1  1  Q - D"  1  Q  = 0  (2.116)  (2.115) a n d (2.116) y i e l d s ' D P = D P  (2.117)  D Q = D Q  (2.118)  -  which i m p l i e s (Assumption  A3) A  P = P  (2.119)  Q = Q  (2.120)  A  D = D  We h a v e t h e n  (2.121)  establishedthe  Lemma 2 . 3 .  V ^> crjr ±  A  The  equalities  are obtained  (2.122)  i=l,...,8 A  i f a n d o n l y i f P = P, Q = Q a n d  D = D. Tha  lemma 2 . 3 s t a t e s t h a t t h e e s t i m a t e s  meters o f t h e m a t r i c e s A and B converge N  »-=»:> .  of the para-  t o the true values as  70  L e t us now c o n s i d e r from ( 2 . 1 0 0 a ) ,  X  equations  (2.100b).Remarking,  = P" Q u + P 1  (2.99b)  and ( 2 . 1 0 0 b )  -  1  D e  (2.123)  can be r e w r i t t e n a s  = ( ' P " Q - Q ) u +• P* P " D e - D* e' p  2  and  v., i s d e f i n e d by  that  ^  the  (2.99b)  £  1  f  = (F* P " Q - Q ) u + P 1  2  (2.114a)  1  f  (2.114b)  P " D e - D' 1  fr-am which we can deduce  €  = [D  1  (P  - P ) P" Q - D 1  1  (Q" -  Q )j r  4W.,P )P- D]e [; - D ]e r  1  r  1  ,  u  r  (2.115)  +  Proceeding  as above l e a d u s t o the  Lemma 2 . 4 . '2 V  i > * l  The e q u a l i t i e s a r e o b t a i n e d a n d D" = D .  i=l,...,r-s  i f and o n l y i f p  - p  (2.116)  Q  =  Q  The  lemma 2 . V p r o v e s t h a t t h e e s t i m a t e s  parameters of the matrix C converge t o the true  of the values  as N—>~ < > = > .  We  Theorem  then obtain the  2.1 The  Maximum L i k e l i h o o d e s t i m a t e  of the t r i p l e t  ( A , B, C ) i s a s y m p t o t i c a l l y c o n s i s t e n t .  The  remaining problem i s the m i n i m i z a t i o n  functions.. Inspecting i W^  and  (2.96) a n d (2.94) s h o w s t h a t  i s a non-linear  the various  classes of non-linear  algorithms.  5 - M I N I M I Z I N G - T H E LOSS 5.1.  minimizing  o p t i m i z a t i o n p r o b l e m . The o b j e c t o f  t h e n e x t s e c t i o n i s co p r e s e n t optimization  of the l o s s  FUNCTIONS  Introduc tion The  nonlinear  minimization  p r o b l e m c a n be f o r m a l l y '  s t a t e d as M i n i m i z e V(p_)  p € E  n  (2.12?)  72  A large  number of methods have been proposed to  solve the general nonlinear minimization  problem  [20,1^].  These methods can be divided i n two c l a s s e s : — The methods that use d e r i v a t i v e s - The methods that do not use d e r i v a t i v e s  In the following, the most commonly used methods are b r i e f l y described  5.2... Minimization procedures usinr; d e r i v a t i v e s We f i r s t consider how to solve problem ( 2 . 1 2 7 ) by algorithms that make use of f i r s t and, p o s s i b l y , second d e r i v a t i v e s of V(p_). 5.2.1. Gradient methods ilk ] At the k-th stage, the t r a n s i t i o n from a point - (k) .  JD  .  "  . .  (k+1) .  to another point, ^(k+D  i s given by s £  (k)  _  x  v  ( p  (k  ) }  (  2  a  2  8  )  The negative of the gradient gives the d i r e c t i o n f o r optimizat i o n but not the magnitude of the step, so that various steepest doscent algorithms are p o s s i b l e , depending on the choice of A . Many methods of s e l e c t i n g A  are a v a i l a b l e . I t can be shown  that, under s u i t a b l e conditions, the method converges as k  •0 0  . However this, t h e o r e t i c a l . r e s u l t i s of l i t t l e i n -  t e r e s t i n p r a c t i c e because the r a t e of convergence can be i n t o l e r a b l y slow.  5-2.2- Newton s methods  [19] 1  The method  s e c o n d - d e r i v a t e methods,  i s the  ximation  of  best  known,  V(p_).. T h e  originate  transition  convergence  matrix this  of V  i s guaranteed  i s positive  method  since  for  from  definite.  ( k  f u n c t i o n s v/hich  ^  k + 1  s  appro-  i s  (2.129)  >)  inverse  This  Newton  quadratic  t o _p_^  (p nn •  i f the  which  the  from  V  The  among  i s a  are  of  the  major  not  Hessian  drawback  strictly  to  convex,  t Newton  s  method  can  diverge.  5.2.3- Quasi-Newton methods [l4 Quasi-Newton or  i t s inverse  vatives.  but  Atstage  -use  =  (  A  problem  i s an of  1  k  °  +  -  methods  Section  (search  1  ^  - *  the  A ( p  k  of  the  Hessian -  a  )  )  has  Hessian  J3^ ^  from  K  deri-  through  (2.130)  V (p< >) k  £  of  been  using  with  matrix  first-order  the  Hessian.  investigated  Powell["14 ] and  without  As  k  inverse  i s concerned  method).  (  the  only  i s computed  Fletcher  Minimization procedures  This of  (  approximating r  5.3«-  £  p^  approximation  Pearsonfl? ] , Davidon  approximate  i n f o r m a t i o n from  (k+1),  £ k+l)  where  methods  j  The by  F l e t c h e r [ 10]  derivatives  derivative-free  general rule,  type  first-derivative  -  and  second-derivative  methods.  However,  have  main  be  laborious  the a  two  drawbacks  to  Second,  of  the  their  or impossible  amount  converge  i n practice,  derivatives.  large  methods  problem  than  search  derivative-type  implementation.  to provide  the  faster  methods  First,  analytical  functions for  d e r i v a t i v e - t y p e methods  preparation  as  i t can  compared  require  with  search  methods.  Two briefly i s  of  t h e many  described,  given  A  existing  complete  search  description  of  these  are  two  methods  i n [14].  5.3.I.  Rosenbrock  s  method  [22 ]  1 Rosenbrock  (k+1)  s  method  unidimensional  searches  of  directions  orthonormal  Schmidt  algorithms  from v  l o c a t e s _t> an  i n i t i a l  T . ^ ^'**' »  V  ' by  successive  point  n ^ ^  along  generated  by  a set  Gram  -  procedure.  5,3.2.  Powell  s  method  1 Powell sive of  s  unidimensional  conjugate  The of  one  method  choice  locates  searches  from  t h e minimum an  i n i t i a l  of V point  by  succes-  along  a set  directions.  Choosing no  method  an  appears  algorithm t o be  cf a p a r t i c u l a r  the problem  and  the  i s not  a  far superior  algorithm  experience  rests of  the  simple  matter  to  a l lthe  on  the  since  others.  formulation  practitioners.  For t h e i d e n t i f i c a t i o n o f m u l t i v a r i a b l e s y s t e m s , s e a r c h methods seem more a p p r o p r i a t e t h a n d e r i v a t i v e - t y p e methods because of the g e n e r a l l y l a r g e number o f parameters.  However, i f t h e com-  p u t a t i o n a l (storage) requirements  a r e c o n s i d e r e d , a quasi-Newton  method c a n be chosen.  3, t h e v a r i o u s a s p e c t s o f t h e s e  I n Chapter  problems w i l l be t r e a t e d on some examples.  6 - CONCLUSION In t h i s chapter a u n i f i e d approach t o the i d e n t i f i c a t i o n o f m u l t i v a r i a b l e systems has been p r e s e n t e d .  Although  t h e problem o f d e r i v i n g t h e i n p u t - o u t p u t de-  s c r i p t i o n o f a m u l t i v a r i a b l e system from i t s s t a t e - s p a c e  represen-  t a t i o n has been d e e p l y i n v e s t i g a t e d by many a u t h o r s , no g e n e r a l result i s available i n literature.  The r e s u l t s o f S e c t i o n 3 b r i d g e  t h i s gap. Compared w i t h t h e p r e v i o u s methods, t h e p r e s e n t one has t h e f o l l o w i n g advantages. - T h i s i s t h e most g e n e r a l a p p r o a c h , s i n c e a l l t h e p r e v i o u s methods a r e s p e c i a l c a s e s o f t h e above method. a) I f t h e number o f subsystems i s e q u a l t o t h e number o f outputs  (s = r ) , one o b t a i n s t h e i n p u t - o u t p u t r e p r e s e n t a t i o n de-  r i v e d by G o p i n a t h  [12] and Zuercher [ 2 8 ] .  b) I f t h e n^'s a r e chosen as l a r g e as p o s s i b l e , one o b t a i n s t h e s o - c a l l e d m i n i m i z a t i o n r e a l i z a t i o n d e r i v e d by A c k e r man  [ 1 ]. c) I f t h e two above c o n d i t i o n s c a n be s a t i s f i e d  s i m u l t a n e o u s l y , t h e i n p u t - o u t p u t r e p r e s e n t a t i o n , suggested by Guidorzi [13], i s obtained. - The i d e n t i f i c a t i o n o f t h e system dynamics ( m a t r i c e s A and B) i s based on t h e i n f o r m a t i o n p r o v i d e d by u. and y_  This  allows a d i s c r i m i n a t i o n of the input-output data which i s of i n t e r e s t i f some o u t p u t s o f t h e system a r e markedly more f r e e from . n o i s e than t h e o t h e r ones. - Equations estimator. equation  (2.28) and (2.25) p r o v i d e a v e r y s i m p l e s t a t e  Having e s t i m a t e d t h e parameters o f P and Q ( i . e . A and B ) ,  (2.99a) g i v e s an e s t i m a t e o f t h e o u t p u t v e c t o r y_^, say y_,  from w h i c h t h e n o i s e has been removed Py^ = Qu  (2.131)  Then, p r o v i d e d ii i s n o i s e - f r e e , t h e s t a t e e s t i m a t o r x ( k ) = Mx (k) - Nu(k) 1  g i v e s an u n b i a s e d  estimate of x ( k ) .  (2.132) T h i s f o r m u l a t i o n l e a d s t o an  a l t e r n a t i v e approach t o t h e i d e n t i f i c a t i o n o f t h e p a r a m e t e r s o f the o b s e r v a t i o n matrix: through equation  t h e parameters o f C c a n be e s t i m a t e d  (2.45).  The Maximum L i k e l i h o o d e s t i m a t o r , i n t r o d u c e d i n S e c t i o n 4, a l l o w s us t o e s t a b l i s h t h e c o n s i s t e n c y o f t h e e s t i m a t e s i n case o f correlated noise.  A l l t h e s e r e s u l t s c o n s t i t u t e a g l o b a l approach t o t h e  i d e n t i f i c a t i o n o f l i n e a r m u l t i v a r i a b l e systems.  The whole p r o c e d u r e d e s c r i b e d  i n the previous Sections  can be e x t e n d e d , i n an e n t i r e l y o b v i o u s way, t o systems whose input-output  s t r u c t u r e i s known a p r i o r i  (transfer functions,  impulse response).  Due t o t h e r e c u r s i v e s t r u c t u r e o f t h e c o m p u t a t i o n scheme, the p r o c e d u r e c a n be extended, w i t h o n l y minor t o an o n - l i n e i d e n t i f i c a t i o n p r o c e d u r e .  modifications,  7 8  C h a p t e r 3 : EXPERIMENTS  1 - INTRODUCTION The  aim o f t h i s Chapter i s t o present  o f Maximum L i k e l i h o o d i n d e n t i f i c a t i o n  For  examples  of m u l t i v a r i a b l e systems.  t h i s purpose, t e s t s w i l l  be made o n s i m u l a t e d  — f o r different minimizations - f o r different noise  some  data  algorithms  powers  2 - EXPERIMENT 1 We c o n s i d e r 0 x(k+l)  =•  i(k)  b  0  1 l l  a  l2  a  l3  21  a  22  a  23  a  a  t h e f o l l o w i n g t h i r d - oorrddeer - s y s c e m  1  0  0  0  0  1  x(k) +  11  '°21 b  3i  b b  12  22  u(k)  b,,  (3.2)  x(k)  =  w i t h 2 i n p u t s and 2  (3.1)  outputs.  T h i s system has been s i m u l a t e d  o n an IBM 370 computer.  The i n p u t s and t h e  o u t p u t s vere s e q u e n c e s o f l e n g t h N = 2 5 0 . The gorithm  £lo]  l o s s f u n c t i o n was m i n i m i z e d .....  Tables  3-1-  and 3-2.  v i a the F l e t c h e r a l give  the r e s u l t s f o r  79  different values  of the s i g n a l - t o - n o i s e  ratio,  N  N " s  i = l  If k=l  3. EXPERIMENT  2  The f o l l o w i n g  system has been s i m u l a t e d  on an IBM 370  computer: 0  x(k+l)  =  1 l l  a  0 a  zoo =  a  12  0  21  22  a  0  a  0  13  a  14  23  0  0  0  0  0  1  0  l l  C  12  The i d e n t i f i c a t i o n  C  +  13  of this  c  l l  b  21  b  3l  b  12  b b  Al  24  a  1  c  x(k)  1  0  a  b  2 2  u(k)  32  V  x(k)  (3.4)  14  s y s t e m has been a c h i e v e d  R o s e n b r o c k m i n i m i z a t i o n a l g o r i t h m f o r a s e t N = 250 data.. The r e s u l t s a r e r e p o r t e d i n T a b l e s  The r e s u l t s ,  (3.3)  given i n Tables  3.3  3.1  and  — 3.4  by u s i n g t h e input-output  3.4.  show t h e u s e -  f u l n e s s , , i n c a s e o f s m a l l s i g n a l - t o - n o i s e - r a t i o s , o f t h e n o i s e model w h i c h a l l o w s one t o e l i m i n a t e t h e b i a s on t h e p a r a m e t e r s . confirms  the t h e o r e t i c a l r e s u l t s of the previous  This  chapters.  parameters  l l  a  a  12  a  13  a  true  values  estimated  - 0.5  -  0.5000  - 0.25  -  0.2499  0.25  0.2500  21  1.375  1.3749  a  22  i-5  1.5000  a  23  b  l l  b  12  b  21  b  22  b  3l  b  32  -  - 0.75  0.7500  0.2  0.1999  0.3  0.2999  0.1  0.0999  - 0.275  -  0.2750  0.85  0.8499  0.95  0.9500  T a b l e 3.1  : T; = e o  values  81  parameters  estimated values  true va3.ues n  d  = 0  0.083  n  = 3  a  - 0.489  -  0.5  -  0.25  - 0.236  0.25  0.018  0.249  a ~  1.375  1.005  1.328  a ~  1.5  1.435  1-506 .  a —  - 0.75  i l  a  a  12  a  13  d  21  22  23  b D  l l  b  12  b D  21  b  22  -  0.595  -  0.252  -  0.751  0.2  0.181  0.210  0.3  0.329  0.296  0.1  0.084  0.097  - 0.275  - 0.237  -  0.259  b ,  0.85  0.426  0.879  b  0.95  0.874  0.898  D  3l  32  Table 3-2 ': | = 10 ( n , : noise model order)  estimated v a l u e s parameters l l  a  •  true v a l u e s  n ,  d  - 1.  =  0  n  d =  -1.274  - 1.061  0.5  0.067  0.506  2  2.186  2.003  1.5  1.324  1.491  a  l2  a  13  a  U  a  21  1.  0.645  0.979  a  22  2.5  2.484  2.485  a  23  a  24  b  0.23  - 0.016  0.261  1  0.715  1.083  ll  0.5  0.674  0.501  b  12  0.5  0.323  0.518  b  21  2  2.711  2.215  b  22  1.617  • - 1.184  -  1  -  V  4  3.P77  3.899  32  3.2  1.006  2.994  V  2.7  - 0.199  2.645  - 0.2  —1.157  1 -  0.874  b  Vc  l l  C  12  C  13  c  14  3  -  - 0.247 1.012  -  1  -  1.015  -  1.024  -  1  -  1.637  -  1.127  1  T a b l e 3.3  0.421  : 77  = 1 0  (rt, : n o i s e model order)  0.919  estimated parameters  t r u e value s  '  l2  a  0.5  1.064  - 0.126  0 . 512  2  2.114  2.004  a  14  1.5  1.677  1.494  a  21  •1  0.429  0.875  a  22  2.5  2.734  2.515  0.126  0.299  1  0.834  1.077  0.5  0.722  0.494  0.5  0.299  0.577  2  2.612  2.129  - 1  -1.739  4  2.984  3.725  3.2  1.008  2.999  2.7  - 0.237  2.825  0.2  -  -  0.25  23 24  b  l l  b  12  b  21  b  22  b  .  32  -  c  l l  • 12 C  C  !  -  13  a  i  n, = 3  a  a  1  1.429  - 1  l l  a  n . = 0 d  values  13  c.. 14  0.975  -  -  0.251 1.108  0.827  1  1.227  - 1  -  1.115  - 1.009  - 1  -  1.725  -  0.622  1 Table (n,  3.4.  * N  : n o i s e model  order)  1.118 0.905  CONCLUSIONS  The purpose o f t h i s t h e s i s i s t o i n v e s t i g a t e t h e Maximum L i k e l i h o o d i d e n t i f i c a t i o n o f l i n e a r d i s c r e t e - t i m e  systems.  The s t a t i s t i c a l p r o p e r t i e s o f t h e Maximum L i k e l i h o o d e s t i m a t o r , f o r s i n g l e i n p u t - s i n g l e output systems, a r e analyzed. Two d i f f e r e n t t y p e s o f n o i s e model s t r u c t u r e a r e c o n s i d e r e d  and  two new r e s u l t s r e l a t i v e t o t h e c o n v e r g e n c e p r o p e r t i e s o f i d e n t i f i c a t i o n methods a r e o b t a i n e d .  A g e n e r a l method f o r d e r i v i n g t h e i n p u t - o u t p u t o f a m u l t i v a r i a b l e system f r o m i t s s t a t e - s p a c e proposed.  description  representation i s  I t i s shown t h a t t h i s a p p r o a c h i s s u p e r i o r , f r o m d i f -  f e r e n t p o i n t s o f view, t o those proposed i n l i t e r a t u r e .  Based on t h e r e s u l t s o b t a i n e d  i n the single input-single  o u t p u t c a s e , a Maximum L i k e l i h o o d e s t i m a t i o n p r o c e d u r e f o r m u l t i v a r i a b l e systems i s d e s c r i b e d and c o n v e r g e n c e p r o p e r t i e s a r e d e r i v e d .  I t i s shown t h a t t h e r e s u l t s c a n b e g e n e r a l i z e d i n v a r i o u s directions.  F i n a l l y , numerical t i f i c a t i o n a r e obtained.  r e s u l t s o f Maximum L i k e l i h o o d i d e n -  85  REFERENCES [1]  Ackermann, J . E . and Bucy, R.S., " C a n o n i c a l m i n i m a l r e a l i z a t i o n of a m a t r i x o f i m p u l s e r e s p o n s e sequences", I n f o r m . C o n t r . 19, pp. 224-231, 1971.  [2]  Astrom, K . J , and B o h l i n , T., " N u m e r i c a l i d e n t i f i c a t i o n o f l i n e a r dynamic systems from normal o p e r a t i n g r e c o r d s " , IFAC Symp. on t h e o r y o f s e l f - a d a p t i v e systems, T e d d i n g t o n , E n g l a n d , 1965. I n t h e o r y o f s e l f - a d a p t i v e c o n t r o l systems (ed. by P.H. Hammond), Plenum P r e s s , New Y o r k , 1966.  [3]  A s t r o m , K . J . , and E y k h o f f , P., "System i d e n t i f i c a t i o n - A s u r v e y " , A u t o m a t i c a 7, pp. 123-162, 1971.  [4]  Astrom, K . J . , and Soderstrom, T. , "Uniqueness o f t h e maximum l i k e l i h o o d e s t i m a t e s o f t h e p a r a m e t e r s o f an ARMA model", IEEE Trans. A u t . C o n t r o l , S p e c i a l i s s u e on i d e n t i f i c a t i o n and time s e r i e s a n a l y s i s , AC-19, pp. 769-773, 1974.  [5]  B o h l i n , T., "On t h e problem o f a m b i g u i t i e s i n maximum i d e n t i f i c a t i o n " , A u t o m a t i c a 7, pp. 199-210, 1971.  O  O  o  [6]  It  II  It  It  tl  likelihood  C l a r k e , D.W., " G e n e r a l i z e d L e a s t - S q u a r e s e s t i m a t i o n o f t h e p a r a meters o f a dynamic model", IFAC Symp. on i d e n t i f i c a t i o n i n autom. . c o n t r o l systems, Prague, paper 3.17, 1967.  [7]  Cramer, H., " M a t h e m a t i c a l methods o f s t a t i s t i c s " , U n i v e r s i t y P r e s s , 1946.  Princeton  [8]  Cuenod, M. and Sage, A., "Comparison o f some methods used f o r p r o c e s s i d e n t i f i c a t i o n " , A u t o m a t i c a 4, pp. 235-269, 1968.  [9]  E y k h o f f , P., "System i d e n t i f i c a t i o n , parameter and s t a t e e s t i m a t i o n " , W i l e y , 1974.  [10]  F l e t c h e r , R., "A new approach t o v a r i a b l e m e t r i c methods", Computer J . 13, pp. 317-322, 1970.  [11]  F l e t c h e r , R. and P o w e l l , M.J.P., "A r a p i d l y c o n v e r g e n t d e s c e n t method f o r m i n i m i z a t i o n " , Computer J . 6, pp. 163-168, 1963.  [12]  G o p i n a t h , B., "On t h e i d e n t i f i c a t i o n o f l i n e a r t i m e i n v a r i a n t systems f r o m i n p u t - o u t p u t d a t a " , B e l l . S y s t . Tech. J . 4 8 , pp. 1101-1113, 1969.  [13]  G u i d o r z i , R., " C a n o n i c a l s t r u c t u r e s i n t h e i d e n t i f i c a t i o n o f m u l t i v a r i a b l e systems", A u t o m a t i c a 1 1 , pp. 361-374, 1975.  [14]  Himmelblau, P.M., " A p p l i e d n o n l i n e a r programming", 1972.  McGraw H i l l  86  [15]  L u e n b e r g e r , D.G., " C a n o n i c a l forms f o r l i n e a r m u l t i v a r i a b l e s y s t e m s " , IEEE Trans. A u t . C o n t r o l , AC-12, pp. 290-293, 1967.  [16]  Mayne, D.Q., " P a r a m e t r i z a t i o n and i d e n t i f i c a t i o n o f l i n e a r m u l t i v a r i a b l e systems", L e c t u r e n o t e s i n m a t h e m a t i c s , S p r i n g e r V e r l a g , 1972.  [17]  P e a r s o n , J.D., " U n c o n s t r a i n e d m i n i m i z a t i o n o f a f u n c t i o n o f s e v e r a l v a r i a b l e s " , Computer J . 13, pp. 171-178, 1969.  [18]  P o w e l l , M.J.D., "An e f f i c i e n t method o f f i n d i n g t h e minimum o f a f u n c t i o n of s e v e r a l v a r i a b l e s without c a l c u l a t i n g d e r i v a t i v e s " , Computer J . 7, pp. 155-162, 1965.  [19]  P o w e l l , M.J.D., A s u r v e y o f n u m e r i c a l methods f o r u n c o n s t r a i n e d o p t i m i z a t i o n , SIAM Rev. 12, pp. 79-97, 1970.  [20]  R i c h a l e t , J . , R a u l t , A. and P o u l i q u e n , R. , " P r o c e s s i d e n t i f i c a t i o n by t h e model method" ( i n F r e n c h ) , Gordon and B r e a c h , 1971.  [21]  R o s e n b l u e t h , A. and Wiener, N., "The r o l e of models i n s c i e n c e " , P h i l o s o p h y of S c i e n c e 12, pp. 316-321, 1945.  [22]  Rosenbrock, H.H., "An a u t o m a t i c method f o r f i n d i n g t h e g r e a t e s t o r l e a s t v a l u e of a f u n c t i o n " , Computer J . 3, pp. 175-184, 1970.  [23]  SciderstrHm, T., "Convergence p r o p e r t i e s o f the G e n e r a l i z e d L e a s t - S q u a r e s i d e n t i f i c a t i o n method", A u t o m a t i c a 10, 1974.  [24]  SBderstrcltn, T., "On t h e u n i q u e n e s s o f Maximum L i k e l i h o o d i d e n t i f i c a t i o n " , A u t o m a t i c a 11, pp. 193-197, 1975.  [25]  Soudack, A . C , Suryanarayanan, K.L. and Rao, S.G. , "A u n i f i e d approach t o d i s c r e t e - t i m e systems i d e n t i f i c a t i o n " , I n t . J . C o n t r o l , V o l . 14, No. 6, pp. 1009-1029, 1971.  [26]  W i l d e , D.J.,  [27]  Woo, K.T., "Maximum L i k e l i h o o d i d e n t i f i c a t i o n of n o i s y s y s t e m s . " Second IFAC Symp. i d e n t i f i c a t i o n and p r o c e s s parameter e s t i m a t i o n , P r a g u e , paper 3.1, 1970.  [28]  Z u e r c h e r , H., " L i n e a r systems i d e n t i f i c a t i o n a l g o r i t h m s f o r a m i n i c o m p u t e r " , M.A.Sc. T h e s i s , Dept. o f E l e c t . E n g g . , ^ U n i v e r s i t y o f B r i t i s h Columbia, 1974.  "Optimum s e e k i n g methods", P r e n t i c e H a l l ,  1964.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0100141/manifest

Comment

Related Items