Abstract
We give an overview of various Lanczos/Krylov space methods and the way in which they are being used for solving certain problems in Control Systems Theory based on state-space models. The matrix methods used are based on Krylov sequences and are closely related to modern iterative methods for standard matrix problems such as sets of linear equations and eigenvalue calculations. We show how these methods can be applied to problems in Control Theory such as controllability, observability, and model reduction. All the methods are based on the use of state-space models, which may be very sparse and of high dimensionality. For example, we show how one may compute an approximate solution to a Lyapunov equation arising from a discrete-time linear dynamic system with a large sparse system matrix by the use of the Arnoldi algorithm, and so obtain an approximate Gramian matrix. This has applications in model reduction. The close relation between the matrix Lanczos algorithm and the algebraic structure of linear control systems is also explored.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. Adamjan, D. Arov, and M. Krein, Analytic properties of Schmidt pairs for a Hankel operator and the generalized Schur-Takagi problem,Math. USSR Sbornik 15 (1971), pp. 31–73.
U. M. Al-Saggaf and G. F. Franklin, An error bound for a discrete reduced order model of a linear multivariable system,IEEE Trans. Auto. Contr. AC-32 (1987), pp. 815–819.
A. Antoulas, New results on the algebraic theory of linear systems: The solution of the cover problems,Linear Algebra Appl. 50 (1983), pp. 1–45.
W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem,Quart. Appl. Math. 9 (1951), pp. 17–29.
A. W. Bojanczyk, L. W. Ewerbring, F. T. Luk, and P. Van Dooren, An accurate product SVD algorithm,Signal Processing 25 (1991), pp. 189–201.
D. L. Boley, Computing the Kalman decomposition, an optimal method,IEEE Trans. Auto. Contr. AC-29 (1984), pp. 51–53. (Correction in AC-36 (1991), p. 1341).
D. L. Boley, R. P. Brent, G. H. Golub, and F. T. Luk, Error correction via the Lanczos process,SIAM J. Matrix Anal. (1992), pp. 312–332.
D. L. Boley, S. Elhay, G. H. Golub, and M. H. Gutknecht, Nonsymmetric Lanczos and finding orthogonal polynomials associated with indefinite weights,Numerical Algorithms 1 (1991), pp. 21–44.
D. L. Boley and G. H. Golub, The Lanczos algorithm and controllability,Systems Control Lett. 4 (1984), pp. 317–324.
D. L. Boley and G. H. Golub, The nonsymmetric Lanczos algorithm and controllability,Systems Control Lett. 16 (1991), pp. 97–105.
D. L. Boley, T. J. Lee, and F. T. Luk, The Lanczos algorithm and Hankel matrix factorization,Linear Algebra Appl. 172 (1992), pp. 109–133.
S. P. Boyd and C. H. Barratt,Linear Controller Design, Prentice-Hall, Englewood Cliffs, NJ, 1991.
C. Brezinski,Padé-Type Approximation and General Orthogonal Polynomials, Birkhäuser, Basel and Boston, 1980.
A. Bultheel, Recursive algorithms for the matrix Padé problem,Math. Comp. 35 (1980), pp. 875–892.
R. R. Craig, Jr. and A. L. Hale, Block-Krylov component synthesis method for structural model reduction,J. Guid., Contr. Dyn. 11 (1988), pp. 562–570.
J. Cullum, W. Kerner, and R. Willoughby, A generalized nonsymmetric Lanczos procedure,Computer Physics Communications 53 (1989), pp. 19–48.
J. Cullum and R. Willoughby,Lanczos Algorithms for Large Symmetric Eigenvalue Computations, vol.I, Theory, Birkhäuser, Basel and Boston, 1985.
L. S. de Jong, Numerical aspects of recursive realization algorithms,SIAM J. Control Optim. 16 (1978), pp. 646–659.
C. A. Desoer,A Second Course in Linear Systems, Van Nostrand Reinhold, New York, 1970.
P. V. Dooren, Numerical linear algebra techniques for large scale matrix problems in systems and control, in Proc. 31 st Conf. on Dec. and Contr., Tucson, AZ, Dec. 1992, Session TM6, to appear.
P. V. Dooren,Upcoming numerical linear algebra issues in systems and control theory, TR 1007, Univ. of Minn. IMA, August 1992.
D. F. Enns, Model reduction with balanced realizations: An error bound and a frequency weighted generalization, in Proc. 23rd IEEE Conf. Dec. Contr., 1984, pp. 127–132.
R. W. Freund, M. H. Gutknecht, and N. M. Nachtigal, An implementation of the look-ahead Lanczos algorithm for non-hermitian matrices,SIAM J. Scientific Comp., 14 (1993), pp. 137–158.
F. R. Gantmacher,Theory of Matrices, vol. 2, Chelsea, New York, 1959.
E. G. Gilbert, Controllability and observability in multivariable control systems,SIAM J. Control 1 (1963), pp. 128–151.
K. Glover, All optimal Hankel norm approximations of linear multivariable systems, and theirL ∞ error bounds,Intl. J. Contr. 39 (1984), pp. 1115–1193.
G. H. Golub and M. H. Gutknecht, Modified moments for indefinite weight functions,Numer. Math. 57 (1990), pp. 607–624.
G. H. Golub and R. Underwood, The block Lanczos method for computing eigenvalues, inMathematical Software III, J. Rice, ed., pp. 364–377, Academic Press, New York and San Diego, 1977.
G. H. Golub and C. F. Van Loan,Matrix Computations, 2d ed., Johns Hopkins Univ. Press, Baltimore, MD, 1989.
W. B. Gragg, The Padé table and its relation to certain algorithms in numerical analysis,SIAM Rev. 14 (1972), pp. 1–62.
W. B. Gragg and A. Lindquist, On the partial realization problem,Linear Algebra Appl. 50 (1985), pp. 277–319.
G. Gu, P. P. Khargonekar, and E. B. Lee, Approximation of infinite-dimensional systems,IEEE Trans. Auto. Contr. AC-34 (1989), pp. 610–618.
M. H. Gutknecht, The unsymmetric Lanczos algorithms and their relations to Padé approximation, continued fractions, and gd algorithm, biconjugate gradient squared algorithms, and fast Hankel solvers, preprint, 1990.
M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms, part I,SIAM J. Math. Anal. 13 (1992), pp. 594–639.
M. H. Gutknecht and L. N. Trefethen, Real polynomial Chebyshev approximation by the Carathéodory-Féjer method,SIAM J. Numer. Anal. 19 (1982), pp. 358–371.
S. J. Hammarling, Numerical solution of stable, non-negative definite Lyapunov equations,IMA J. Numer. Anal. 2 (1982), pp. 303–323.
S. J. Hammarling, Numerical solutions of the discrete-time convergent, non-negative definite Lyapunov equations,Systems Control Lett. 17 (1991), pp. 137–139.
M. T. Heath, A. J. Laub, C. C. Paige, and R. C. Ward, Computing the SVD of a product of two matrices,SIAM J. Sci. Statist. Comput. 7 (1986), pp. 1147–1159.
J. Hickin and N. K. Sinha, Model reduction for linear multivariable systems,IEEE Trans. Auto. Contr. AC-25 (1980), p. 1121–1127.
R. E. Kalman, Mathematical description of linear systems,SIAM J. Contr. 1 (1963), pp. 152–192.
R. E. Kalman, On partial realizations transfer functions and canonical forms,Acta Polytech. Scand. MA31 (1979), pp. 9–32.
S. Kaniel, Estimates for some computational techniques in linear algebra,Math. Comp. 20 (1966), pp. 369–378.
H. M. Kim and R. R. Craig, Jr., Structural dynamics analysis using an unsymmetric block Lanczos algorithm,Internat. J. Numer. Methods Engrg. 26 (1988), pp. 2305–2318.
H. M. Kim and R. R. Craig, Jr., Computational enhancement of an unsymmetric block Lanczos algorithm,Internat. J. Numer. Methods Engrg. 30 (1990), pp. 1083–1089.
S. Y. Kung, A new identification and model reduction algorithm via singular value decompositions, in Proc. 12th Asilomar Conf. Circ. Syst. Comp., November 1984, pp. 705–714.
C. Lanczos, An iteration method for the solution of the eigenvalue problem linear differential and integral operators,J. Res. Natl. Bur. Stand. 45 (1950), pp. 255–282.
A. J. Laub, On computing “balancing” transformations, in Proc. 1980 JACC, San Francisco, 1980, pp. FA8-E.
A. J. Laub, Numerical linear algebra aspects of control design computations,IEEE Trans. Auto. Contr. AC-30 (1985), pp. 97–108.
A. J. Laub, M. T. Heath, C. C. Paige, and R. C. Ward, Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms,IEEE Trans. Auto. Contr. AC-32 (1987), pp. 115–122.
B. C. Moore, Principal component analysis in linear systems: Controllability, observability, and model reduction,IEEE Trans. Auto. Contr. AC-26 (1981), pp. 17–31.
C. C. Paige, The computation of eigenvalues and eigenvectors of very large sparse matrices, Ph.D. thesis, Univ. of London, 1971.
B. N. Parlett,The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ, 1980.
B. N. Parlett, Reduction to tridiagonal form and minimal realizations,SIAM J. Matr. Anal. 13 (1992), pp. 567–593.
B. N. Parlett, D. R. Taylor, and Z. A. Liu, A look-ahead Lanczos algorithm for unsymmetric matrices,Math. Comp. 44 (1985), pp. 105–124.
L. Reichel and D. Y. Hu, Krylov subspace methods for the Sylvester equation,Linear Algebra Appl. 172 (1992), pp. 283–314.
Y. Saad, On the rates of convergence of the Lanczos and the block Lanczos methods,SIAM J. Num. Anal. 17 (1980), pp. 687–706.
Y. Saad, Krylov subspace methods for solving large unsymmetric linear systems,Math. Comp. 37 (1981), pp. 105–126.
Y. Saad, Numerical solution for large Lyapunov equations, inSignal Processing, Scattering and Operator Theory, and Numerical Methods, Proc. Intl Symp. MTNS-89, vol. 3, pp. 503–511, Birkhäuser, Basel and Boston, 1990.
Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving unsymmetric linear systems,SIAM J. Sci. Stat. Comput. 7 (1986), pp. 856–869.
D. Scott, Analysis of the symmetric Lanczos process, Electronic Res. Lab. Report UCB/ERL M78/40, Univ. of Calif. Berkeley, 1978.
L. S. Shieh and Y. J. Wei, A mixed method for multivariable system reduction,IEEE Trans. Auto. Contr. AC-20 (1975), pp. 429–432.
G. W. Stewart and J. G. Sun,Matrix Perturbation Theory, Academic Press, New York and San Diego, 1990.
T. J. Su, A decentralized linear quadratic control design method for flexible structures, Ph.D. thesis, Univ. of Texas, Austin, 1989.
T. J. Su and R. R. Craig, Jr., Model reduction and control of flexible structures using Krylov vectors,J. Guid., Contr., Dyn. 14 (1991), pp. 260–267.
L. N. Trefethen, Rational Chebyshev approximation on the unit disk,Numer. Math. 37 (1981), pp. 297–320.
P. Van Dooren, Numerical aspects of system and control problems,Journal A 30 (1987), pp. 25–32.
C. D. Villemagne and R. E. Skelton, Model reduction using a projection formulation,Intl. J. Contr. 46 (1987), pp. 2141–2169.
J. H. Wilkinson,The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965.
H. P. Zeiger and A. J. McEwen, Approximate linear realizations of given dimensions via Ho's algorithm,IEEE Trans. Auto. Contr. AC-19 (1974), p. 153.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Boley, D.L. Krylov space methods on state-space control models. Circuits Systems and Signal Process 13, 733–758 (1994). https://doi.org/10.1007/BF02523124
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02523124