Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Gauss quadrature for general linear functionals, Lanczos algorithm, and minimal partial realization

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

The concept of Gauss quadrature can be generalized to approximate linear functionals with complex moments. Following the existing literature, this survey will revisit such generalization. It is well known that the (classical) Gauss quadrature for positive definite linear functionals is connected with orthogonal polynomials, and with the (Hermitian) Lanczos algorithm. Analogously, the Gauss quadrature for linear functionals is connected with formal orthogonal polynomials, and with the non-Hermitian Lanczos algorithm with look-ahead strategy; moreover, it is related to the minimal partial realization problem. We will review these connections pointing out the relationships between several results established independently in related contexts. Original proofs of the Mismatch Theorem and of the Matching Moment Property are given by using the properties of formal orthogonal polynomials and the Gauss quadrature for linear functionals.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Antoulas, A. C.: Approximation of Large-Scale Dynamical Systems, Advances in Design and Control, vol. 6. With a foreword by Jan C. Willems, SIAM, Philadelphia, PA (2005)

    Book  Google Scholar 

  2. Bai, Z.: Error analysis of the Lanczos algorithm for the nonsymmetric eigenvalue problem. Math. Comp. 62(205), 209–226 (1994). https://doi.org/10.2307/2153404

    Article  MathSciNet  MATH  Google Scholar 

  3. Bai, Z., Day, D. M., Ye, Q.: ABLE: an adaptive block Lanczos method for non-Hermitian eigenvalue problems. SIAM J. Matrix Anal. Appl. 20(4), 1060–1082 (1999). https://doi.org/10.1137/S0895479897317806

    Article  MathSciNet  MATH  Google Scholar 

  4. Beckermann, B.: Complex Jacobi matrices. J. Comput. Appl. Math. 127, 17–65 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Berlekamp, E. R.: Algebraic Coding Theory. McGraw-Hill Book Co., New York-Toronto Ont.-London (1968)

    MATH  Google Scholar 

  6. Boley, D. L., Lee, T. J., Luk, F. T.: The Lanczos algorithm and Hankel matrix factorization. Linear Algebra Appl. 172, 109–133 (1992). https://doi.org/10.1016/0024-3795(92)90022-3. Second NIU Conference on Linear Algebra, Numerical Linear Algebra and Applications (DeKalb, IL, 1991)

    Article  MathSciNet  MATH  Google Scholar 

  7. Brezinski, C.: Padé-type approximation and general orthogonal polynomials. Internat. Ser. Numer. Math Birkhäuser (1980)

  8. Brezinski, C.: Computational aspects of linear control Numerical Methods and Algorithms, vol. 1. Kluwer Acad. Publ., Dordrecht (2002)

    Book  Google Scholar 

  9. Brezinski, C., Redivo Zaglia, M., Sadok, H.: Avoiding breakdown and near-breakdown in Lanczos type algorithms. Numer. Algorithms 1(3), 261–284 (1991). https://doi.org/10.1007/BF02142326

    Article  MathSciNet  MATH  Google Scholar 

  10. Brezinski, C., Redivo Zaglia, M., Sadok, H.: A breakdown-free Lanczos type algorithm for solving linear systems. Numer. Math. 63(1), 29–38 (1992). https://doi.org/10.1007/BF01385846

    Article  MathSciNet  MATH  Google Scholar 

  11. Bultheel, A., Van Barel, M.: Linear Algebra, Rational Approximation and Orthogonal Polynomials, Stud. Comput Math., vol. 6. North-Holland Publishing Co., Amsterdam (1997)

    Google Scholar 

  12. Chebyshev, P.: Sur les Fractions Continues (1855). Reprinted in Oeuvres I, vol. 11, pp 203–230. Chelsea, New York (1962)

    Google Scholar 

  13. Chebyshev, P.: Le développement des fonctions à une seule variable (1859). Reprinted in Oeuvres I, vol. 19, pp 501–508. Chelsea, New York (1962)

    Google Scholar 

  14. Chihara, T. S.: On quasi-orthogonal polynomials. Proc. Amer. Math. Soc. 8, 765–767 (1957). https://doi.org/10.2307/2033295

    Article  MathSciNet  MATH  Google Scholar 

  15. Chihara, T. S.: An Introduction to Orthogonal Polynomials, Mathematics and its Applications, vol. 13. Gordon and Breach Science Publishers, New York (1978)

    Google Scholar 

  16. Christoffel, E. B.: Über die Gaußische Quadratur und eine Verallgemeinerung derselben. J. Reine Angew. Math. 55, 61–82 (1858). Reprinted in Gesammelte mathematische Abhandlungen I (B. G. Teubner, Leipzig, 1910), pp. 65–87

    MathSciNet  Google Scholar 

  17. Cullum, J., Kerner, W., Willoughby, R.A.: A generalized nonsymmetric Lanczos procedure. Comput. Phys. Commun. 53(1), 19–48 (1989). https://doi.org/10.1016/0010-4655(89)90146-X

    Article  MathSciNet  MATH  Google Scholar 

  18. Cullum, J., Willoughby, R. A.: A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices. In: North-Holland Mathematics Studies, vol. 127, pp 193–240. Elsevier (1986)

  19. Cybenko, G.: An explicit formula for Lanczos polynomials. Linear Algebra Appl. 88, 99–115 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  20. Day, D.M.: Semi-duality in the two-sided Lanczos algorithm. Ph.D. thesis, University of California, Berkeley. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:9430449 (1993)

  21. Day, D. M.: An efficient implementation of the nonsymmetric Lanczos algorithm. SIAM J. Matrix Anal. Appl. 18(3), 566–589 (1997). https://doi.org/10.1137/S0895479895292503

    Article  MathSciNet  MATH  Google Scholar 

  22. Draux, A.: Polynômes Orthogonaux Formels, Lecture Notes in Math., vol. 974. Springer, Berlin (1983)

    Book  Google Scholar 

  23. Draux, A.: On quasi-orthogonal polynomials. J. Approx. Theory 62(1), 1–14 (1990). https://doi.org/10.1016/0021-9045(90)90042-O

    Article  MathSciNet  MATH  Google Scholar 

  24. Draux, A.: Formal orthogonal polynomials revisited. Applications. Numer. Algorithms 11(1), 143–158 (1996). https://doi.org/10.1007/BF02142493

    Article  MathSciNet  MATH  Google Scholar 

  25. Draux, A.: On quasi-orthogonal polynomials of order r. Integral Transforms Spec. Funct. 27(9), 747–765 (2016). https://doi.org/10.1080/10652469.2016.1197922

    Article  MathSciNet  MATH  Google Scholar 

  26. Fenu, C., Martin, D., Reichel, L., Rodriguez, G.: Block Gauss and Anti-Gauss quadrature with application to networks. SIAM J. Matrix Anal. Appl. 34(4), 1655–1684 (2013). https://doi.org/10.1137/120886261

    Article  MathSciNet  MATH  Google Scholar 

  27. Freund, R. W.: The Look-Ahead Lanczos Process for Large Nonsymmetric Matrices and Related Algorithms. In: Moonen, M. S., Golub, G. H., de Moor, B. L. R. (eds.) Linear Algebra for Large Scale and Real-Time Applications, NATO ASI Series, vol. 232, pp 137–163. Kluwer Acad. Publ., Dordrecht (1993)

  28. Freund, R. W., Gutknecht, M. H., Nachtigal, N. M.: An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Comput. 14(1), 137–158 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  29. Freund, R. W., Hochbruck, M.: Gauss Quadratures Associated With the Arnoldi Process and the Lanczos Algorithm. In: Moonen, M. S., Golub, G. H., de Moor, B. L. R. (eds.) Linear Algebra for Large Scale and Real-Time Applications, NATO ASI Series, vol. 232, pp 377–380. Kluwer Acad. Publ., Dordrecht (1993)

  30. Freund, R. W., Zha, H.: A look-ahead algorithm for the solution of general Hankel systems. Numer. Math. 64(1), 295–321 (1993). https://doi.org/10.1007/BF01388691

    Article  MathSciNet  MATH  Google Scholar 

  31. Gantmacher, F.R.: On the algebraic analysis of Krylov’s method of transforming the secular equation. Trans. Second Math. Congress II, 45–48 (1934). In Russian. Title translation as in [32]

    Google Scholar 

  32. Gantmacher, F. R.: The Theory of Matrices, vol. 1, 2. Chelsea Publishing Co., New York (1959)

    MATH  Google Scholar 

  33. Gautschi, W.: A survey of Gauss-Christoffel quadrature formulae. In: E. B. Christoffel (Aachen/Monschau, 1979), pp 72–147. Basel, Birkhäuser (1981)

  34. Gautschi, W.: Orthogonal polynomials: computation and approximation. Numer. Math. Sci. Comput. Oxford University Press, New York (2004)

    Book  Google Scholar 

  35. Gautschi, W.: Numerical Analysis. Birkhäuser, Boston (2011). https://books.google.it/books?id=-fgjJF9yAIwC

    MATH  Google Scholar 

  36. Gilbert, E.: Controllability and observability in multivariable control systems. SIAM J. Control 1, 128–151 (1963)

    MathSciNet  MATH  Google Scholar 

  37. Golub, G. H., Meurant, G.: Matrices, Moments and Quadrature with Applications. Princeton Ser. Appl. Math. Princeton University Press, Princeton (2010)

    Google Scholar 

  38. Golub, G. H., Van Loan, C. F.: Matrix Computations. Johns Hopkins Stud. Math. Sci., 4th edn. Johns Hopkins University Press, Baltimore (2013)

    Book  Google Scholar 

  39. Gragg, W. B.: Matrix interpretations and applications of the continued fraction algorithm. Rocky Mountain J. Math. 4, 213–225 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  40. Gragg, W. B., Lindquist, A.: On the partial realization problem. Linear Algebra Appl. 50, 277–319 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  41. Günnel, A., Herzog, R., Sachs, E.: A note on preconditioners and scalar products in Krylov subspace methods for self-adjoint problems in Hilbert space. Elect. Trans. Numer. Anal. 41, 13–20 (2014)

    MathSciNet  MATH  Google Scholar 

  42. Guo, H., Renaut, R. A.: Estimation of uTf(A)v for large-scale unsymmetric matrices. Numer. Linear Algebra Appl. 11(1), 75–89 (2004). https://doi.org/10.1002/nla.334

    Article  MathSciNet  MATH  Google Scholar 

  43. Gutknecht, M. H.: A completed theory of the unsymmetric Lanczos process and related algorithms. I. SIAM J. Matrix Anal. Appl. 13(2), 594–639 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  44. Gutknecht, M. H.: A completed theory of the unsymmetric Lanczos process and related algorithms. II. SIAM J. Matrix Anal. Appl. 15(1), 15–58 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  45. Gutknecht, M. H.: The Lanczos Process and Padé approximation. In: Proceedings of the Cornelius Lanczos International Centenary Conference (Raleigh, NC, 1993), pp 61–75. SIAM, Philadelphia (1994)

  46. Heinig, G., Jankowski, P.: Kernel structure of block Hankel and Toeplitz matrices and partial realization. Linear Algebra Appl. 175, 1–30 (1992). https://doi.org/10.1016/0024-3795(92)90299-P

    Article  MathSciNet  MATH  Google Scholar 

  47. Heinig, G., Rost, K.: Algebraic methods for Toeplitz-like matrices and operators, Operator Theory: Advances and Applications, vol. 13. Basel, Birkhäuser (1984)

    Book  MATH  Google Scholar 

  48. Hestenes, M. R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards 49, 409–436 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  49. Higham, N. J.: Functions of Matrices. Theory and Computation. SIAM, Philadelphia (2008)

    Book  MATH  Google Scholar 

  50. Ho, B., Kalman, R. E.: Effective construction of linear state-variable models from input/output functions. at-Automatisierungstechnik 14(1-12), 545–548 (1966)

    Article  MATH  Google Scholar 

  51. Hochbruck, M.: The Padé Table and its Relation to Certain Numerical Algorithms. Habilitation thesis, Universität Tübingen (1996)

  52. Householder, A. S., Bauer, F. L.: On certain methods for expanding the characteristic polynomial. Numer. Math. 1, 29–37 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  53. Iohvidov, I. S.: Hankel and Toeplitz Matrices and Forms. Birkhäuser, Boston (1982). Algebraic theory, Translated from the Russian by G. Philip A. Thijsse, with an introduction by I. Gohberg

    MATH  Google Scholar 

  54. Kailath, T.: Linear Systems. Prentice-Hall, Inc., Englewood Cliffs (1980). Prentice-Hall Information and System Sciences Series

    MATH  Google Scholar 

  55. Kalman, R. E.: Canonical structure of linear dynamical systems. Proc. Nat. Acad. Sci. U.S.A. 48, 596–600 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  56. Kalman, R. E.: Mathematical description linear systems. SIAM J. Control 1, 152–192 (1963)

    MathSciNet  MATH  Google Scholar 

  57. Kalman, R. E.: On partial realizations, transfer functions, and canonical forms. Acta Polytech Scand. Math. Comput. Sci. Ser. 31, 9–32 (1979)

    MathSciNet  MATH  Google Scholar 

  58. Kautský, J.: Matrices related to interpolatory quadratures. Numer. Math. 36(3), 309–318 (1980/81). https://doi.org/10.1007/BF01396657

  59. Krall, H. L., Sheffer, I. M.: Differential equations of infinite order for orthogonal polynomials. Annali di Matematica Pura ed Applicata 74(1), 135–172 (1966). https://doi.org/10.1007/BF02416454

    Article  MathSciNet  MATH  Google Scholar 

  60. Kung, S. Y.: Multivariable and multidimensional systems: analysis and design. Ph.D. thesis, Stanford University Stanford (1977)

  61. Kwon, K. H., Littlejohn, L. L.: Classification of classical orthogonal polynomials. J. Korean Math. Soc 34(4), 973–1008 (1997)

    MathSciNet  MATH  Google Scholar 

  62. Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Research Nat. Bur. Standards 45, 255–282 (1950)

    Article  MathSciNet  Google Scholar 

  63. Lanczos, C.: Solution of systems of linear equations by minimized iterations. J. Research Nat. Bur. Standards 49, 33–53 (1952)

    Article  MathSciNet  Google Scholar 

  64. Liesen, J., Strakoš, Z.: Krylov Subspace Methods: Principles and Analysis. Numer. Math. Sci. Comput. Oxford University Press, Oxford (2013)

    MATH  Google Scholar 

  65. Lorentzen, L., Waadeland, H.: Continued Fractions with Applications, Stud. Comput Math., vol. 3. North-Holland Publishing Co., Amsterdam (1992)

    MATH  Google Scholar 

  66. Malék, J., Strakoš, Z.: Preconditioning and the Conjugate Gradient Method in the Context of Solving PDEs: SIAM Spotlights. SIAM, Philadelphia (2015). https://books.google.it/books?id=aWDxBQAAQBAJ

    MATH  Google Scholar 

  67. Massey, J. L.: Shift-register synthesis and BCH decoding. IEEE Trans. Information Theory IT-15, 122–127 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  68. Milovanović, G.V., Cvetković, A.S.: Complex Jacobi Matrices and quadrature rules. Filomat 17, 117–134 (2003). http://www.jstor.org/stable/43998655

    Article  MathSciNet  MATH  Google Scholar 

  69. Moore, B. C.: Principal component analysis in linear systems: controllability, observability, and model reduction. IEEE Trans. Automat. Control 26 (1), 17–32 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  70. Nachtigal, N. M.: A look-ahead variant of the Lanczos algorithm and its application to the quasi-minimal residual method for non-Hermitian linear systems. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge (1991)

  71. Paige, C. C., Panayotov, I., Zemke, J. P. M.: An augmented analysis of the perturbed two-sided Lanczos tridiagonalization process. Linear Algebra Appl. 447, 119–132 (2014). https://doi.org/10.1016/j.laa.2013.05.009https://doi.org/10.1016/j.laa.2013.05.009

    Article  MathSciNet  MATH  Google Scholar 

  72. Parlett, B. N.: Reduction to tridiagonal form and minimal realizations. SIAM J. Matrix Anal. Appl. 13(2), 567–593 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  73. Parlett, B. N., Taylor, D. R., Liu, Z. A.: A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp. 44(169), 105–124 (1985). https://doi.org/10.2307/2007796

    Article  MathSciNet  MATH  Google Scholar 

  74. Piñar, M., Ramírez, V.: Matrix interpretation of formal orthogonal polynomials for nondefinite functionals. J. Comput. Appl. Math. 18(3), 265–277 (1987). https://doi.org/10.1016/0377-0427(87)90001-X

    Article  MathSciNet  MATH  Google Scholar 

  75. Pozza, S., Pranić, M. S., Strakoš, Z.: Gauss quadrature for quasi-definite linear functionals. IMA J. Numer. Anal. 37(3), 1468–1495 (2017). https://doi.org/10.1093/imanum/drw032

    Article  MathSciNet  MATH  Google Scholar 

  76. Pozza, S., Pranić, M. S., Strakoš, Z.: The Lanczos algorithm and complex Gauss quadrature. Electron. Trans. Numer. Anal. 50, 1–19 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  77. Pozza, S., Strakoš, Z.: Algebraic description of the finite Stieltjes moment problem. Linear Algebra Appl. 561, 207–227 (2019). https://doi.org/10.1016/j.laa.2018.09.026

    Article  MathSciNet  MATH  Google Scholar 

  78. Riesz, M.: Sur le problème des moments. Troisième Note. Ark. Mat. Fys 17(16), 1–52 (1923)

    Google Scholar 

  79. Rutishauser, H.: Beiträge zur Kenntnis des Biorthogonalisierungs-Algorithmus von Lanczos. Z. Angew. Math. Physik 4, 35–56 (1953)

    Article  MathSciNet  MATH  Google Scholar 

  80. Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia (2003)

    Book  MATH  Google Scholar 

  81. Stieltjes, T. J.: Recherches sur les fractions continues. Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys. 8(4), J. 1–122 (1894). Reprinted in Oeuvres II (P. Noordhoff, Groningen, 1918), pp. 402–566. Investigations on continued fractions in Thomas Jan Stieltjes, Collected Papers, Vol. II (Springer-Verlag, Berlin, 1993), pp. 609–745

    MathSciNet  MATH  Google Scholar 

  82. Strakoš, Z.: Model reduction using the Vorobyev moment problem. Numer. Algorithms 51(3), 363–379 (2009). https://doi.org/10.1007/s11075-008-9237-0

    Article  MathSciNet  MATH  Google Scholar 

  83. Szegö, G.: Orthogonal Polynomials, Amer. Math. Soc. Colloq Publ., vol. XXIII. American Mathematical Society, New York (1939)

    Google Scholar 

  84. Taylor, D. R.: Analysis of the look ahead Lanczos algorithm. Ph.D. thesis, University of California, Berkeley (1982)

  85. Tong, C. H., Ye, Q.: Analysis of the finite precision bi-conjugate gradient algorithm for nonsymmetric linear systems. Math. Comp. 69(232), 1559–1575 (2000). https://doi.org/10.1090/S0025-5718-99-01171-0https://doi.org/10.1090/S0025-5718-99-01171-0

    Article  MathSciNet  MATH  Google Scholar 

  86. Vorobyev, Y. V.: Methods of Moments in Applied Mathematics. Translated from the Russian by Bernard Seckler. Gordon and Breach Science Publishers, New York (1965)

    Google Scholar 

  87. Wilkinson, J. H.: The Algebraic Eigenvalue Problem. Monographs on Numerical Analysis. The Clarendon Press Oxford University Press, New York (1988). 1st edn published 1963

    Google Scholar 

Download references

Acknowledgments

We would like to thank Zdeněk Strakoš for the helpful comments and improvements suggested.

Funding

This work has been supported by Charles University Research program No. UNCE/SCI/023 and by the Ministry for Scientific and Technological Development, Higher Education and Information Society of R. Srpska.

Author information

Authors and Affiliations

  1. Faculty of Mathematics and Physics, Charles University, Sokolovská 83, 186 75, Praha 8, Czech Republic

    Stefano Pozza

  2. ISTI-CNR, Pisa, Italy

    Stefano Pozza

  3. INdAM-GNCS, Rome, Italy

    Stefano Pozza

  4. Faculty of Science, Department of Mathematics and Informatics, University of Banja Luka, M. Stojanovića 2, 51000, Banja Luka, Bosnia and Herzegovina

    Miroslav Pranić

Authors
  1. Stefano Pozza
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Miroslav Pranić
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stefano Pozza.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pozza, S., Pranić, M. The Gauss quadrature for general linear functionals, Lanczos algorithm, and minimal partial realization. Numer Algor 88, 647–678 (2021). https://doi.org/10.1007/s11075-020-01052-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-020-01052-y

Keywords

Search

Navigation