Some algorithms for computing Chebyshev normalized first-kind polynomials by roots

摘要

When numerically implementing the optimal binomial N-cycle Chebyshev iterative methods for solving the linear operator equations Au = f [ 1-13], the iterative sequence of approximations u~k,k= 1,...,N, arises. In this case a transition operator is successively multiplied by operator factors of the form I— α_kA, k ≤ N, where the parameters α_ k are inverse values to the roots of the Chebyshev first-kind polynomial of the degree N reduced to the segment [m,M], 0 < m < M, which comprises the spectrum of the operator A. For small values of ξ = m/M the norms of some of these operators are large. It is advisable to mix these operators with those which reduce the norm of the transition operator. An important problem is the stability of the iterative method u~(k+1) = u~k — α_k(Au~k — f),k = 0,1,..., N — 1. Its stability to round-off errors substantially depends on the sequence of parameters (permutation χN), because the transition operators I — α_kAξ for small values of ξ = m/M and some numbers k have a huge norm. In real computer-aided calculations this can lead to two undesirable effects: (1) a dramatic increase in ||u~k|| for some 1 ≤ k ≤ N, which can result in an emergency halt of the computer or a loss in significant digits in subsequent calculations, and (2) the corresponding increase in the errors at intermediate iterations. The algorithms for ordering parameters for the case N = 2~q3~r have been studied in [ 1-6, 8, 9].