Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Korovkin tests, approximation, and ergodic theory

Author: Stefano Serra Capizzano
Journal: Math. Comp. 69 (2000), 1533-1558
MSC (1991): Primary 65F10, 65D15, 15A60, 47B65, 28Dxx
Published electronically: March 6, 2000
MathSciNet review: 1697646
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


We consider sequences of $s\cdot k(n)\times t\cdot k(n)$ matrices $\{A_n(f)\}$ with a block structure spectrally distributed as an $L_1$ $p$-variate $s\times t$ matrix-valued function $f$, and, for any $n$, we suppose that $A_n(\cdot)$ is a linear and positive operator. For every fixed $n$ we approximate the matrix $A_n(f)$ in a suitable linear space $\mathcal{M}_n$ of $s\cdot k(n)\times t\cdot k(n)$ matrices by minimizing the Frobenius norm of $A_n(f)-X_n$ when $X_n$ ranges over $\mathcal{M}_n$. The minimizer $\hat{X}_n$ is denoted by $\mathcal{P}_{k(n)}(A_n(f))$. We show that only a simple Korovkin test over a finite number of polynomial test functions has to be performed in order to prove the following general facts:

the sequence $\{\mathcal{P}_{k(n)}(A_n(f))\}$ is distributed as $f$,
the sequence $\{A_n(f)-\mathcal{P}_{k(n)}(A_n(f))\}$ is distributed as the constant function $0$ (i.e. is spectrally clustered at zero).
The first result is an ergodic one which can be used for solving numerical approximation theory problems. The second has a natural interpretation in the theory of the preconditioning associated to cg-like algorithms.

References [Enhancements On Off] (What's this?)

  • 1. Owe Axelsson and Gunhild Lindskog, On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math. 48 (1986), no. 5, 499–523. MR 839614, 10.1007/BF01389448
  • 2. Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662
  • 3. Dario Bini and Victor Y. Pan, Polynomial and matrix computations. Vol. 1, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1994. Fundamental algorithms. MR 1289412
  • 4. N. Bonanni, Proprietà spettrali e computazionali di algebre di matrici. Graduate Thesis in Computer Science, University of Pisa, 1993.
  • 5. Raymond H. Chan and Michael K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38 (1996), no. 3, 427–482. MR 1409592, 10.1137/S0036144594276474
  • 6. Tony F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988), no. 4, 766–771. MR 945937, 10.1137/0909051
  • 7. Philip J. Davis, Circulant matrices, John Wiley & Sons, New York-Chichester-Brisbane, 1979. A Wiley-Interscience Publication; Pure and Applied Mathematics. MR 543191
  • 8. Ronald A. DeVore and George G. Lorentz, Constructive approximation, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 303, Springer-Verlag, Berlin, 1993. MR 1261635
  • 9. F. Di Benedetto and S. Serra Capizzano, ``A unifying approach to abstract matrix algebra preconditioning'', Numer. Math., 82-1 (1999), pp. 57-90. CMP 99:10
  • 10. F. Di Benedetto and S. Serra Capizzano, ``Optimal and superoptimal matrix algebra operators'', TR nr. 360, Dept. of Mathematics - Univ. of Genova (1997).
  • 11. G. Fiorentino and S. Serra, Fast parallel solvers for elliptic problems, Comput. Math. Appl. 32 (1996), no. 2, 61–68. MR 1398257, 10.1016/0898-1221(96)00103-4
  • 12. Walter Gautschi, The condition of Vandermonde-like matrices involving orthogonal polynomials, Linear Algebra Appl. 52/53 (1983), 293–300. MR 709357, 10.1016/0024-3795(83)80020-2
  • 13. Ulf Grenander and Gábor Szegő, Toeplitz forms and their applications, 2nd ed., Chelsea Publishing Co., New York, 1984. MR 890515
  • 14. Eugene Isaacson and Herbert Bishop Keller, Analysis of numerical methods, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR 0201039
  • 15. C. Jordan, Cours d'Analyse de l'Ecole Polytecnique: Vol. I. Gauthier-Villars, Paris, France, 1909. Reprint, CMP 93:03
  • 16. T. Kailath and V. Olshevsky, ``Displacement structure approach to discrete-trigonometric-transform based preconditioners of G. Strang type and T. Chan type'', Proc. ``Workshop on Toeplitz matrices'' Cortona (Italy), September 1996. Calcolo, 33 (1996), pp. 191-208. CMP 98:15
  • 17. P. P. Korovkin, Linear operators and approximation theory, Translated from the Russian ed. (1959). Russian Monographs and Texts on Advanced Mathematics and Physics, Vol. III, Gordon and Breach Publishers, Inc., New York; Hindustan Publishing Corp. (India), Delhi, 1960. MR 0150565
  • 18. Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill Book Co., New York, 1987. MR 924157
  • 19. Stefano Serra, Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems, Math. Comp. 66 (1997), no. 218, 651–665. MR 1401945, 10.1090/S0025-5718-97-00833-8
  • 20. S. Serra, ``A Korovkin-type Theory for finite Toeplitz operators via matrix algebras'', Numer. Math., 82-1 (1999), pp. 117-142. CMP 99:10
  • 21. Stefano Serra Capizzano, An ergodic theorem for classes of preconditioned matrices, Linear Algebra Appl. 282 (1998), no. 1-3, 161–183. MR 1648324, 10.1016/S0024-3795(98)80002-5
  • 22. S. Serra Capizzano, ``A Korovkin based approximation of multilevel Toeplitz matrices (with rectangular unstructured blocks) via multilevel Trigonometric matrix spaces'', SIAM J. Numer. Anal., 36-6 (1999), pp. 1831-1857. CMP 2000:03
  • 23. S. Serra Capizzano, ``Approximation of multilevel Toeplitz matrices via multilevel Trigonometric matrix spaces and application to the preconditioning'', Calcolo, 36 (1999), pp. 187-213.
  • 24. Stefano Serra Capizzano, Korovkin theorems and linear positive Gram matrix algebra approximations of Toeplitz matrices, Linear Algebra Appl. 284 (1998), no. 1-3, 307–334. ILAS Symposium on Fast Algorithms for Control, Signals and Image Processing (Winnipeg, MB, 1997). MR 1655142, 10.1016/S0024-3795(98)10072-1
  • 25. S. Serra Capizzano and C. Tablino Possio, ``Spectral and structural analysis of high order finite difference matrices for Elliptic Operators'', Linear Algebra Appl. 293 (1999), 85-131. CMP 99:15
  • 26. Stefano Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl. 270 (1998), 109–129. MR 1484077
  • 27. S. Serra Capizzano, ``Some theorems on linear positive operators and functionals and their applications'', TR nr. 26, LAN, Dept. of Mathematics - Univ. of Calabria (1997). Comput. Math. Appl., in press.
  • 28. S. Serra Capizzano and P. Tilli, ``Extreme singular values and eigenvalues of non-Hermitian block Toeplitz matrices'', J. Comput. and Appl. Math. 108 (1999), 113-130. CMP 99:17
  • 29. Paolo Tilli, A note on the spectral distribution of Toeplitz matrices, Linear and Multilinear Algebra 45 (1998), no. 2-3, 147–159. MR 1671591, 10.1080/03081089808818584
  • 30. P. Tilli, Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl. 278 (1998), no. 1-3, 91–120. MR 1637331, 10.1016/S0024-3795(97)10079-9
  • 31. Evgenij E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. 232 (1996), 1–43. MR 1366576, 10.1016/0024-3795(94)00025-5
  • 32. E. E. Tyrtyshnikov and N. L. Zamarashkin, Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl. 270 (1998), 15–27. MR 1484073
  • 33. Studies in real and complex analysis, I. I. Hirschman, Jr., editor. Studies in Mathematics, Vol. 3, The Mathematical Association of America, Buffalo, N.Y.; Prentice-Hall, Inc ., Englewood Cliffs, N.J., 1965. MR 0183600

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65F10, 65D15, 15A60, 47B65, 28Dxx

Retrieve articles in all journals with MSC (1991): 65F10, 65D15, 15A60, 47B65, 28Dxx

Additional Information

Stefano Serra Capizzano
Affiliation: Dipartimento di Energetica, Via Lombroso 6/17, 50134 Firenze, Italy; Dipartimento di Informatica, Corso Italia 40, 56100 Pisa, Italy

Keywords: Distributions and ergodic theory, Toeplitz matrices, Korovkin theorem, circulants and $\tau$ matrices, discrete transforms
Received by editor(s): February 2, 1998
Received by editor(s) in revised form: November 20, 1998
Published electronically: March 6, 2000
Article copyright: © Copyright 2000 American Mathematical Society