PRECONDITIONERS FOR ILL-CONDITIONED TOEPLITZ SYSTEMS CONSTRUCTED FROM POSITIVE KERNELS

In this paper, we are interested in the iterative solution of ill-conditioned Toeplitz systems generated by continuous nonnegative real-valued functions f with a finite number of zeros. We construct new w-circulant preconditioners without explicit knowledge of the generating function f by approximating f by its convolution f * K-N with a suitable positive reproducing kernel K-N. By the restriction to positive kernels we obtain positive definite preconditioners. Moreover, if f has only zeros of even order <= 2s, then we can prove that the property integral(pi)(-pi) t(2k) K-N(t) dt <= CN-2k (k = 0, ... , s) of the kernel is necessary and sufficient to ensure the convergence of the PCG method in a number of iteration steps independent of the dimension N of the system. Our theoretical results were confirmed by numerical tests.