THE SPECTRA OF SUPEROPTIMAL CIRCULANT PRECONDITIONED TOEPLITZ-SYSTEMS

The solutions of Hermitian positive-definite Toeplitz systems A(n)x = b by the preconditioned conjugate gradient method are studied. The preconditioner, called the "super-optimal" preconditioner, is the circulant matrix T(n) that minimizes parallel-to I - C(n)-1A(n) parallel-to F over all circulant matrices C(n). The convergence rate is known to be governed by the distribution of the eigenvalues of T(n)-1A(n). For n-by-n Toeplitz matrix A(n) with entries being Fourier coefficients of a positive function in the Wiener class, the asymptotic behaviour of the eigenvalues of the preconditioned matrix T(n)-1A(n) is found as n increases, and it is proved that they are clustered around one.