New Band Toeplitz Preconditioners for Ill-Conditioned Symmetric Positive Definite Toeplitz Systems
New Band Toeplitz Preconditioners for Ill-Conditioned Symmetric Positive Definite Toeplitz Systems
复制标题
DOI：
10.1137/s0895479800376314
复制
发表时间：
2001-03
期刊：
影响因子：
--
通讯作者：
D. Noutsos;P. Vassalos
中科院分区：
文献类型：
--
作者：
D. Noutsos;P. Vassalos
众所周知，预处理的共轭梯度（PCG）方法被广泛用于求解不良条件的Toeplitz线性系统TN（F）X = B。在本文中，我们提出了一种新的预处理技术，用于通过偶数零的非负函数F的对称toeplitz系统解决方案。更具体地说，F除了最小程度的适当三角多项式g，零是F的零以消除其零。使用有理近似，我们近似$ \ sqrt {f/g} $ by $ \ frac {p} {q} $，$ p，q $ trigonometric polyenmials，并考虑$ \ frac {p^2g} {q^2} $ as f的非常令人满意的近似。我们提出矩阵$ m_n = b^{ - 1} _n（q）b_n（p^2g）b^{ - 1} _n（q）$，其中$ b（\ cdot）$表示关联的band toeplitz矩阵，作为预处理，获得了其预处理基质光谱的良好聚类。我们还表明，所提出的技术可能非常灵活，这一事实通过各种数值实验证实，因此在许多情况下，它构成了比现有策略更有效的策略。
It is well known that preconditioned conjugate gradient (PCG) methods are widely used to solve ill-conditioned Toeplitz linear systems Tn(f)x=b. In this paper we present a new preconditioning technique for the solution of symmetric Toeplitz systems generated by nonnegative functions f with zeros of even order. More specifically, f is divided by the appropriate trigonometric polynomial g of the smallest degree, with zeros the zeros of f to eliminate its zeros. Using rational approximation we approximate $\sqrt{f/g}$ by $\frac{p}{q}$, $p,q$ trigonometric polynomials and consider $\frac{p^2g}{q^2}$ as a very satisfactory approximation of f. We propose the matrix $M_n=B^{-1}_n(q)B_n(p^2g)B^{-1}_n(q)$, where $B(\cdot)$ denotes the associated band Toeplitz matrix, as a preconditioner whence a good clustering of the spectrum of its preconditioned matrix is obtained. We also show that the proposed technique can be very flexible, a fact that is confirmed by various numerical experiments so that in many cases it constitutes a much more efficient strategy than the existing ones.