Korovkin tests, approximation, and ergodic theory. (English) Zbl 0956.65021
Let \(A_n(f)\) be a \(k(n)\times k(n)\) matrix whose elements are blocks of size \(s\times t\) and which are spectrally distributed as the the \(s\times t\) matrix valued function \(f\) which means that for any \(F\) bounded and continuous on a probability space \((\Omega,\mu)\) the following ergodic property holds
\[
\lim_{n\to\infty} {1 \over s k(n)} \sum_{i=1}^{sk(n)} F(\sigma_i(A_n(f))) =\int_{\Omega} \sum_{j=1}^s F(\sigma(f(x)))d\mu(x)
\]
where the sigma’s denote singular values. Let \(X_n\) be the best approximant for \(A_n(f)\) in Frobenius norm. It is shown as one of the main results in this paper that the sequence \(X_n\) is distributed as \(f\) and that the elements in the error sequence \(A_n(f)-X_n\) have spectra that cluster around 0.
For the proofs, first some Korovkin theorems are shown, i.e., it is sufficient to perform a simple test for a finite number of polynomial test functions \(F\) in the above ergodic property. Results of the type given here are used in numerical function approximation and in preconditioning for conjugate gradient-like iterative methods.
For the proofs, first some Korovkin theorems are shown, i.e., it is sufficient to perform a simple test for a finite number of polynomial test functions \(F\) in the above ergodic property. Results of the type given here are used in numerical function approximation and in preconditioning for conjugate gradient-like iterative methods.
Reviewer: A.Bultheel (Leuven)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 41A36 | Approximation by positive operators |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65D15 | Algorithms for approximation of functions |
| 60F17 | Functional limit theorems; invariance principles |
| 28D99 | Measure-theoretic ergodic theory |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
Keywords:
spectral distribution; ergodic property; Toeplitz matrices; singular values; Korovkin theorems; discrete transforms; circulants; numerical function approximation; preconditioning; conjugate gradient-like iterative methodsReferences:
| [1] | Owe Axelsson and Gunhild Lindskog, On the eigenvalue distribution of a class of preconditioning methods, Numer. Math. 48 (1986), no. 5, 479 – 498. , https://doi.org/10.1007/BF01389447 Owe Axelsson and Gunhild Lindskog, On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math. 48 (1986), no. 5, 499 – 523. · Zbl 0564.65017 · doi:10.1007/BF01389448 |
| [2] | Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. · Zbl 0863.15001 |
| [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. · Zbl 0809.65012 |
| [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. · Zbl 0863.65013 · doi: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. · Zbl 0646.65042 · doi: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. · Zbl 0418.15017 |
| [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. · Zbl 0797.41016 |
| [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 · Zbl 0930.65050 |
| [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. · Zbl 0857.65107 · doi: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. · Zbl 0522.33005 · doi: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. · Zbl 0611.47018 |
| [14] | Eugene Isaacson and Herbert Bishop Keller, Analysis of numerical methods, John Wiley & Sons, Inc., New York-London-Sydney, 1966. |
| [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 · Zbl 0907.65034 |
| [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. · Zbl 0094.10201 |
| [18] | Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill Book Co., New York, 1987. · Zbl 0925.00005 |
| [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. · Zbl 0864.65019 |
| [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. · Zbl 0935.65026 · doi: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 · Zbl 0958.41016 |
| [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. · Zbl 0947.65052 |
| [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). · Zbl 0936.65059 · doi: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 · Zbl 0940.65113 |
| [26] | Stefano Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl. 270 (1998), 109 – 129. · Zbl 0892.15014 |
| [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 · Zbl 0937.15013 |
| [29] | Paolo Tilli, A note on the spectral distribution of Toeplitz matrices, Linear and Multilinear Algebra 45 (1998), no. 2-3, 147 – 159. · Zbl 0951.65033 · doi:10.1080/03081089808818584 |
| [30] | P. Tilli, Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl. 278 (1998), no. 1-3, 91 – 120. · Zbl 0934.15009 · doi: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. · Zbl 0841.15006 · doi: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. · Zbl 0890.15006 |
| [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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
