Jackson's theorem and circulant preconditioned Toeplitz systems

AbstractThe preconditioned conjugate gradient method is used to solve n-by-n Hermitian Toeplitz systems Anx = b. The preconditioner Sn is the Strang's circulant preconditioner which is defined to be the circulant matrix that copies the central diagonals of An. The convergence rate of the method depends on the spectrum of Sn−1An. Using Jackson's theorem in approximation theory, we prove that if An has a positive generating fucntion ƒ whose lth derivative ƒ(l), l ⩾ 0, is Lipschitz of order 0 < α ⩽ 1, then the method converges superlinearly. We show moreover that the error after 2q conjugate gradient steps decreases like Πk = 2q (log2kk2(l + α))