Spectral Properties of Preconditioned Rational Toeplitz Matrices
Ta-Kang Ku, C.‐C. Jay Kuo · SIAM Journal on Matrix Analysis and Applications · 1993
Various Toeplitz preconditioners $P_N $ have recently been proposed so that an $N \times N$ symmetric positive definite Toeplitz system $T_N {\bf x} = {\bf b}$ can be solved effectively by the preconditioned conjugate gradient (PCG) method. It has been proven that if $T_N $ is generated by a positive function in the Wiener class, the eigenvalues of the preconditioned matrices $P_N^{ - 1} T_N $ are clustered between $( 1 - \epsilon ,1 + \epsilon )$ except for a fixed number independent of N. In this research, the spectra of $P_N^{ - 1} T_N $ are characterized more precisely for rational Toeplitz matrices $T_N $ with preconditioners proposed by Strang [Stud. Appl. Math., 74 (1986), pp. 171–176] and Ku and Kuo [IEEE Trans. Signal Process., 40 (1992), pp. 129–141]. The eigenvalues of $P_N^{ - 1} T_N $ are classified into two classes, i.e., the outliers and the clustered eigenvalues, depending on whether they converge to 1 asymptotically. It is proved that the number of outliers depends on the order of the rational generating function, and the clustering radius $\epsilon $ is proportional to the magnitude of the last element in the generating sequence used to construct these preconditioners. For the special case with $T_N $ generated by a pometric sequence, this approach can be used to determine the exact eigenvalue distribution of $P_N^{ - 1} T_N $ analytically.