The Spectra of Super-Optimal Circulant Preconditioned Toeplitz Systems
Raymond H. Chan, Xiaoqing Jin, Man-Chung Yeung · SIAM Journal on Numerical Analysis · 1991
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 $\| {I - C_n^{ - 1} A_n } \|_F $ over all circulant matrices $C_n $. The convergence rate is known to be governed by the distribution of the eigenvalues of $T_n^{-1}A_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^{-1}A_n $ is found as n increases, and it is proved that they are clustered around one.