Top

Numerical Algorithms

Published in:

12-01-2021 | Original Paper

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

Authors: Stefano Pozza, Miroslav Pranić

Published in: Numerical Algorithms | Issue 2/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Projected explicit and implicit Taylor series methods for DAEs

next article Filtered interpolation for solving Prandtl’s integro-differential equations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

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)CrossRef

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/2153404MathSciNetCrossRefMATH

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/S0895479897317806MathSciNetCrossRefMATH

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

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

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)MathSciNetMATHCrossRef

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

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

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/BF02142326MathSciNetCrossRefMATH

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/BF01385846MathSciNetCrossRefMATH

11.

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

12.

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

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)

14.

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

15.

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

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–87MathSciNet

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-XMathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

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/S0895479895292503MathSciNetCrossRefMATH

22.

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

23.

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

24.

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

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.1197922MathSciNetCrossRefMATH

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/120886261MathSciNetCrossRefMATH

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)MathSciNetMATHCrossRef

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/BF01388691MathSciNetCrossRefMATH

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]

32.

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

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)CrossRef

35.

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

36.

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

37.

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

38.

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

39.

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

40.

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

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)MathSciNetMATH

42.

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

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)MathSciNetMATHCrossRef

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)MathSciNetMATHCrossRef

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-PMathSciNetCrossRefMATH

47.

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

48.

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

49.

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

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)MATHCrossRef

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)MathSciNetMATHCrossRef

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. GohbergMATH

54.

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

55.

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

56.

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

57.

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

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/BF02416454MathSciNetCrossRefMATH

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)MathSciNetMATH

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)MathSciNetCrossRef

63.

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

64.

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

65.

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

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=aWDxBQAAQBAJMATH

67.

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

68.

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

69.

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

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.009MathSciNetMATHCrossRef

72.

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

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/2007796MathSciNetCrossRefMATH

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-XMathSciNetMATHCrossRef

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/drw032MathSciNetCrossRefMATH

76.

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

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.026MathSciNetCrossRefMATH

78.

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

79.

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

80.

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

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–745MathSciNetMATH

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-0MathSciNetCrossRefMATH

83.

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

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-0MathSciNetMATHCrossRef

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)

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

Title: The Gauss quadrature for general linear functionals, Lanczos algorithm, and minimal partial realization
Authors: Stefano Pozza
Miroslav Pranić
Publication date: 12-01-2021
Publisher: Springer US
Published in: Numerical Algorithms / Issue 2/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-020-01052-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2021

Filtered interpolation for solving Prandtl’s integro-differential equations

Relationship between time-instant number and precision of ZeaD formulas with proofs

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation

Gradient and diagonal Hessian approximations using quadratic interpolation models and aligned regular bases

A numerical study on the N-periodic wave solutions of two coupled bilinear equations

A class of blending functions with smoothness

Premium Partner