New band Toeplitz preconditioners for ill-conditioned symmetric positive definite Toeplitz systems (Q2784377)

This authors study the use of band Toeplitz matrices as preconditioners for solving the \(n \times n\) ill-conditioned symmetric and positive definite Toeplitz system \(T_n(f)x=b\), where the matrix \(T_n(f) \in \mathbb{R}^{n \times n}\) is produced by a real-valued, even, \(2\pi\)-periodic function defined in the fundamental interval \([-\pi, \pi]\), using the preconditioned conjugate gradient (PCG) method. In addition it is assumed that \(f\) is continuous, nonnegative and has zeros of even order. NEWLINENEWLINENEWLINEThe authors define \(z_k\) as the trigonometric polynomial of minimum degree \(k\) containing all the zeros of \(f\) with their multiplicities, and then \(r_{lm} = p_l/q_m\) as the best rational approximation of \(\hat f = \sqrt{f/z_k}\) in the uniform norm, i.e., NEWLINE\[NEWLINE \|\hat f - r_{lm} \|_\infty = \min_{r \in {\mathcal R}(l,m)} \|\hat f - r \|_\infty, NEWLINE\]NEWLINE where \({\mathcal R}(l,m)\) denotes the set of irreducible rational functions \(r\), with \(p \in {\mathcal P}_l\), and \(q \in {\mathcal P}_m\) (that is \(p\) and \(q\) have not common zeros). NEWLINENEWLINENEWLINEThe preconditioner is constructed in the following way. Let \(x_1\), \(x_2\), \(\dots\), \(x_s\) the zeros of \(f\) with respective multiplicities \(2 \mu_1\), \(2 \mu_2\), \(\dots\), \(2 \mu_s\), and let \(\rho = 2 \mu_1 + 2 \mu_2 + \cdots + 2 \mu_s\). First \(z_\rho = \prod_{i=1}^s (1 - \cos(x-x_i))^{\mu_i}\) is defined, \(z_\rho\) is the trigonometric polynomial of minimum degree \(\rho\) with all the zeros of \(f\), then \(f/z_\rho\) is a real positive function. NEWLINENEWLINENEWLINEThen the authors approximate the function \(\hat{f} = \sqrt{f/z_\rho}\) by the rational trigonometric function \(r_{lm}=p_l/q_m\), since this function is the best rational approximation of \(\sqrt{f/z_\rho}\), the authors conclude that \(p_l^2/q_m^2\) should be a good approximation of \(f/z_\rho\), that is there exists a small \(\epsilon >0\) such that NEWLINE\[NEWLINE \left \|{f \over z_\rho} - {p_l^2 \over q_m^2} \right \|_\infty < \epsilon NEWLINE\]NEWLINE or, equivalently, there exists a small \(\delta >0\) such that NEWLINE\[NEWLINE \left \|{q_m^2 \over z_\rho p_l^2}f - 1 \right \|_\infty < \delta, NEWLINE\]NEWLINE which means that the values of \({q_m^2 \over z_\rho p_l^2}f\) are clustered in a small region around the number \(1\). Then, taking \(T_n ({z_\rho p_l^2 \over q_m^2})\) as a preconditioner the eigenvalues of \(T_n^{-1} ({z_\rho p_l^2 \over q_m^2} T_n(f))\) are clustered in a small region near \(1\), and the PCG method will converge very fast. But this matrix is full, hard to construct and costly to invert. Instead the authors propose to separate the numerator and the denominator of the ratio \(z_\rho p_l^2/q_m^2\) and use as preconditioner the product \(M_n=B_{nm}^{-1}(q) B_{n \hat{l}}(p^2 z_\rho) B_{nm}^{-1}(q)\), where \(\hat{l} = 2l+\rho\) and the second index in the matrices stands for its half bandwidth. It is proved that the preconditioned matrix is symmetric and positive definite, and that if \(h={fq^2\over p^2z_\rho}\) and \(m\) is the degree of \(q_m\), then at most \(2m\) eigenvalues of the preconditioned matrix are in \((0, h_{min})\), and at most \(2m\) are bigger than \(h_{max}\), the rest lies in the interval \((h_{min}, h_{max})\). Other results state that there exists upper and lower bounds of the spectra of the preconditioned matrix which are independent of \(n\). NEWLINENEWLINENEWLINEIn the lasts sections the computational cost is analyzed and several numerical experiments are presented using functions of different behaviors.