Convergence of CG and GMRES on a tridiagonal Toeplitz linear system (Q2458227)

Error bounds, and sometimes exact bounds are constructed for the residual vector when conjugare gradient (CG) or generalized minimal residual (GMRES) iterative methods are applied to the solution of a tridiagonal normal (or Hermitian positive definite) Toeplitz system \(Ax=b\) for some special choices of the vectors \(b\). The method used rests upon the fact that bounds for the residual norm, and hence information about the convergence of the method, can be obtained from \[ \varepsilon_k=\min\{\| \text{diag}(g)V_{k+1,N}^T u\| _2/\| g\| _2\}. \] The minimum is taken over all vectors \(u\) whose first component is 1, \(g\) is a vector depending on the method and \(V_{k+1,N}\) is a \((k+1)\times N\) Vandermonde matrix whose nodes are the eigenvalues of \(A\). In the tridiagonal Toeplitz case, the eigenvalues can be expessed in terms of the zeros of Chebyshev polynomials of the second kind. All the explicit expressions for \(\varepsilon_k\) are given in terms of these Chebyshev nodes and the three Toeplitz parameters. The results for the particular right-hand sides \(b\) can be used to obtain estimates for general \(b\).