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

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. O. Axelsson and G. Lindskög, ``The rate of convergence of the preconditioned conjugate gradient method'', Numer. Math., 52 (1986), pp. 499-523. MR 88a:65037b
  • 2. R. Bhatia, Matrix Analysis. Springer, New York, 1997. MR 98i:15003
  • 3. D. Bini and V. Pan, Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms. Birkäuser, Boston, 1994. MR 95k:65003
  • 4. N. Bonanni, Proprietà spettrali e computazionali di algebre di matrici. Graduate Thesis in Computer Science, University of Pisa, 1993.
  • 5. R.H. Chan and M. Ng, ``Conjugate gradient methods for Toeplitz systems'', SIAM Rev., 38 (1996), pp. 427-482. MR 97i:65048
  • 6. T.F. Chan, ``An optimal circulant preconditioner for Toeplitz systems'', SIAM J. Sci. Stat. Comp., 9 (1988), pp. 766-771. MR 89e:65046
  • 7. P. Davis, Circulant Matrices. John Wiley and Sons, New York, 1979. MR 81a:15003
  • 8. R. De Vore and G. Lorentz, Constructive Approximation. Springer-Verlag, Berlin, 1993. MR 95f:41001
  • 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), pp 61-68. MR 97g:65216
  • 12. W. Gautschi, ``The condition of Vandermonde-like matrices involving orthogonal polynomials'', Linear Algebra Appl., 52/53 (1983), pp. 293-300. MR 84i:65043
  • 13. U. Grenander and G. Szegö, Toeplitz Forms and Their Applications. Second Edition, Chelsea, New York, 1984. MR 88b:42031
  • 14. E. Isaacson and H. Keller, Analysis of Numerical Methods. John Wiley and Sons, New York, 1966. MR 34:924
  • 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 (English translation). Hindustan Publishing Co., Delhi, 1960. MR 27:561
  • 18. W. Rudin, Real and Complex Analysis. McGraw-Hill, Singapore, 1986. MR 88k:00002
  • 19. S. Serra, ``Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems'', Math. Comp., 66 (1997), pp. 651-665. MR 97h:65056
  • 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. S. Serra Capizzano, ``An ergodic theorem for classes of preconditioned matrices'', Linear Algebra Appl., 282 (1998), pp. 161-183. MR 99k:65040
  • 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. S. Serra Capizzano, ``Korovkin Theorems and linear positive Gram matrix algebras approximation of Toeplitz matrices'', Linear Algebra Appl., 284 (1998), pp. 307-334. MR 99h:65088
  • 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. S. Serra, ``On the extreme eigenvalues of Hermitian (block) Toeplitz matrices'', Linear Algebra Appl., 270 (1998), pp. 109-129. MR 98k:15034
  • 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. P. Tilli, ``A note on the spectral distribution of Toeplitz matrices'', Linear Multilin. Algebra, 45 (1998), pp. 147-159. MR 99j:65063
  • 30. P. Tilli, ``Locally Toeplitz sequences: spectral properties and applications'', Linear Algebra Appl., 278 (1998), pp. 91-120. MR 99g:47057
  • 31. E. Tyrtyshnikov, ``A unifying approach to some old and new theorems on distribution and clustering'', Linear Algebra Appl., 232 (1996), pp. 1-43. MR 96m:15018
  • 32. E. Tyrtyshnikov and N. Zamarashkin, ``Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships'', Linear Algebra Appl., 270 (1998), pp. 15-27. MR 98i:65030
  • 33. H. Widom, Toeplitz matrices. In Studies in real and complex analysis, I. Hirschman Jr. Ed., Math. Ass. Amer., 1965. MR 32:1080

Similar Articles

Retrieve articles in Mathematics of Computation 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

American Mathematical Society