COMPUTATIONAL ASPECTS OF LINEAR CONTROL Numerical Methods and Algorithms VOLUME 1 Series Editor: Claude Brezinski Universite des Sciences et Technologies de Lille, France Computational Aspects of Linear Control by Claude Brezinski Universite des Sciences et Technologies de Lille, France KLUWER ACADEMIC PUBLISHERS DORDRECHTI BOSTON I LONDON A C.I.P. Catalogue record for this book is available from the Library of Congress. ISBN·13: 978-1·4613·7966·9 e·ISBN·13: 978·1-4613·0261·2 DOl: 10.10071978·1-4613·0261·2 Published by Kluwer Academic Publisher.;, P.O. Box 17, 3300 AA Dordrecht, The Netherlands. Sold and distributed in North, Central and South America by Kluwer Academic Publishers, 101 Philip Drive, Norwell. MA 02{)61, U.S.A. In all other countries, sold and distributed by Kluwer Academic Publishers, P.O. Box 322, 3300 AH Dorrlrecht, The Netherlands. Print~d on acidjre~ paper All Rights Reserved C 2002 Kluwer Academic Publishers Sof tcoYer reprint of \he hardcover 1s\ edilion 2002 No part of this work may be reproduc~, stored in a retrieval system, Of transmitted in any fonn or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without wrinen pennission from the Publisher. with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of hte work. Contents INTRODUCTION 1 1. CONTROL OF LINEAR SYSTEMS 3 1 The control problem 3 2 Examples 11 2.1 Hard disk read/write head 11 2.2 Predator-prey 12 2.3 Harmonic oscillator 13 2.4 Toilet control 14 2.5 Control of pH 14 2.6 Nuclear reactor 14 3 Basic notions and results 15 3.1 State-space approach 15 3.2 Frequency-domain approach 16 4 Controllability 23 5 Observability 25 6 The canonical representation 28 7 Realization 30 7.1 Complete realization 31 7.2 Partial realization 36 8 Model reduction 38 8.1 Truncation 39 8.2 Diagonalization 39 8.3 Aggregation 40 8.4 Singular perturbations 41 8.5 Schur decomposition 41 v vi COMPUTATIONAL ASPECTSOF liNEAR CONTROL 8.6 Balanced reduction 42 8.7 Pade and Lanczos techniques 43 9 Stability analysis 44 10 Poles and zeros 48 10.1 Poles 49 10.2 Zeros 50 10.3 Pole placement 52 lOA Pole-zero cancellation 54 11 Decoupling 56 12 State estimation 58 12.1 Full-order observers 58 12.2 Reduced-order observers 60 12.3 The separation principle 61 13 Geometric theory 62 14 Solving the control problem 63 15 Effects of finite precision 64 Bibliography 67 2. FORMAL ORTHOGONAL POLYNOMIALS 73 1 Definition and properties 73 2 Matrix interpretation 78 3 Adjacent families 79 4 Biorthogonal polynomials 82 5 Vector orthogonal polynomials 84 Bibliography 85 3. PADE APPROXIMATIONS 87 1 Preliminaries 87 2 Pade-type approximants 92 3 Pade approximants 95 3.1 The direct approach 96 3.2 The second approach 97 3.3 Algebraic properties 98 304 Connection to FOPs 101 3.5 Continued fractions 103 3.6 The c:-algorithm 109 4 Error estimation 110 Contents vii 5 Generalizations 117 5.1 Partial Pade approximants 117 5.2 Vector Pade approximants 125 5.3 Matrix Pade approximants 129 6 Approximations to the exponential 131 Bibliography 133 4. TRANSFORM INVERSION 135 1 Laplace transform 135 1.1 Collocation 136 1.2 Rational approximation 136 2 z-transform 140 Bibliography 142 5. LINEAR ALGEBRA ISSUES 145 1 Singular value decomposition 145 1.1 Square matrices 145 1.2 Rectangular matrices 146 1.3 Least squares 147 1.4 Pseudo-inverses 149 2 Schur complement 150 3 The bordering method 151 4 Determinantal identities 151 5 Hankel matrices and related topics 152 6 Stable matrices 154 7 Recursive projection 155 Bibliography 159 6. LANCZOS TRIDIAGONALIZATION PROCESS 161 1 The tridiagonalization process 161 2 The non-Hermitian Lanczos process 166 Bibliography 168 7. SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS 171 1 The method of Arnoldi 171 2 Lanczos method 173 2.1 Matrix approach 174 2.2 Polynomial approach 174 2.3 Recapitulation 176 viii COMPUTATIONAL ASPECTSOF LINEAR CONTROL 3 Implementation of Lanczos method 176 3.1 The recurrences 177 3.2 Computation of the coefficients 180 3.3 The algorithms 180 4 Preconditioning 183 5 Transpose-free algorithms 185 5.1 CGS 187 5.2 BiCGSTAB 188 6 Breakdowns 190 6.1 Avoiding true breakdowns 190 6.2 Avoiding ghost breakdowns 193 6.3 Near-breakdowns 194 6.4 Other Lanczos-based algorithms 195 7 Krylov subspace methods 197 7.1 The methods 198 7.2 The polynomial and rational approaches 199 7.3 Particular cases 203 7.4 Recursive algorithms 204 8 Hankel and Toeplitz systems 207 8.1 Hankel systems 208 8.2 Toeplitz systems 212 9 Error estimates for systems of linear equations 215 9.1 The estimates 216 9.2 Discussion 217 9.3 A numerical example 218 Bibliography 219 8. REGULARIZATION OF ILL-CONDITIONED SYSTEMS 225 1 Introduction 225 2 Analysis of the regularized solutions 226 3 The symmetric positive definite case 229 4 Rational extrapolation procedures 230 4.1 Restricted case 230 4.2 Full case 238 Bibliography 245 9. SYLVESTER AND RICCATI EQUATIONS 249 1 Sylvester equation 249 Contents ix 2 Riccati equation 250 Bibliography 253 10. TOPICS ON NONLINEAR DIFFERENTIAL EQUATIONS 255 1 Integrable systems 255 2 Connection to convergence acceleration 262 2.1 Construction of sequence transformations 262 2.2 The mechanism of extrapolation 268 2.3 Associated partial differential equations 270 2.4 Confluent algorithms 272 Bibliography 272 11. APPENDIX: THE MATHEMATICS OF MODEL REDUCTION 277 1 Model reduction by projection 277 2 Matrix interpretation 279 3 Increasing the dimension 281 4 Construction of the projection 282 5 Transfer function matrices 283 5.1 The modeling error 283 5.2 Moment matching 284 Bibliography 286 INDEX 289