Recursive-Based PCG Methods for Toeplitz Systems with Nonnegative Generating Functions
Michael K. Ng, Hai‐Wei Sun, Xiaoqing Jin · SIAM Journal on Scientific Computing · 2003
In this paper, we consider the solutions of symmetric positive definite, but ill-conditioned, Toeplitz systems A n x = b. Here we propose to solve the system by the recursive-based preconditioned conjugate gradient method. The idea is to use the inverse of A m (the principal submatrix of A n with the Gohberg--Semencul formula as a preconditioner for A n . The inverse of A m can be generated recursively by using the formula until m is small enough. The construction of the preconditioners requires only the entries of A n and does not require the explicit knowledge of the generating function f of A n . We show that if f is a nonnegative, bounded, and piecewise continuous even function with a finite number of zeros of even order, the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers. Hence the conjugate gradient method, when applied to solving the preconditioned system, converges very quickly. Numerical results are included to illustrate the effectiveness of our approach.