# Chebyshev iteration method

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An iterative algorithm for finding a solution to a linear equation (1)

that takes account of information about the inclusion of — the spectrum of the operator — in a certain set , and uses the properties and parameters of those polynomials that deviate least from zero on and are equal to 1 at 0.

The most well-developed Chebyshev iteration method is obtained when in (1), is a linear self-adjoint operator and , where are the boundary points of the spectrum; then the Chebyshev iteration method uses the properties of the Chebyshev polynomials of the first kind, . For this case one considers two types of Chebyshev iteration methods: (2) (3) in which for a given one obtains a sequence as . In (2) and (3) and are the numerical parameters of the method. If , then the initial error and the error at the -th iteration are related by the formula where (4)

The polynomials are calculated using the parameters of each of the methods (2), (3): for method (2) (5)

where are the elements of the permutation , while for method (3) they are calculated from the recurrence relations (6) Here The methods (2) and (3) can be optimized on the class of problems for which by choosing the parameters such that in (4) is the polynomial least deviating from zero on . It was proved in 1881 by P.L. Chebyshev that this is the polynomial (7)

where . Then (8)

where Substituting (7) for in (6), the parameters of the method (3) are determined: (9)

where (10) Thus, computing and by the formulas (9) and (10), one obtains the Chebyshev iteration method (3) for which is optimally small for each .

To optimize (2) for a given , the parameters are chosen corresponding to the permutation in formula (5) in such a way that (7) holds, that is, (11) Then after iterations, inequality (8) holds for .

An important problem for small is the question of the stability of the method (2), (5), (11). An imprudent choice of may lead to a catastrophic increase in for some , to the loss of significant figures, or to an increase in the rounding-off errors allowed on intermediate iteration. There exist algorithms that mix the parameters in (11) and guarantee the stability of the calculations: for see Iteration algorithm; and for one of the algorithms for constructing is as follows. Let , and suppose that has been constructed, then (12) There exists a class of methods (2) — the stable infinitely repeated optimal Chebyshev iteration methods — that allows one to repeat the method (2), (5), (11) after iterations in such a way that it is stable and such that it becomes optimal again for some sequence . For the case , it is clear from the formula (13)

that agrees with (11). If after iterations one repeats the iteration (2), (5), (11) further, taking for in (11) the values (14)

then once again one obtains a Chebyshev iteration method after iterations. To ensure stability, the set (14) is decomposed into two sets: in the -th set, , one puts the for which is a root of the -th bracket in (13); within each of the subsets the are permuted according to the permutation . For one substitutes elements of the first set in (5), (11), and for one uses the second subset; the permutation is defined in the same way. Continuing in an analogous way the process of forming parameters, one obtains an infinite sequence , uniformly distributed on , called a -sequence, for which the method (2) becomes optimal with and (15) The theory of the Chebyshev iteration methods (2), (3) can be extended to partial eigen value problems. Generalizations also exist to a certain class of non-self-adjoint operators, when lies in a certain interval or within a certain domain of special shape (in particular, an ellipse); when information is known about the distribution of the initial error; or when the Chebyshev iteration method is combined with the method of conjugate gradients.

One of the effective methods of speeding up to the convergence of the iterations (2), (3) is a preliminary transformation of equation (1) to an equivalent equation of the form and the application of the Chebyshev iteration method to this equation. The operator is defined by taking account of two facts: 1) the algorithm for computing a quantity of the form should not be laborious; and 2) should lie in a set that ensures the fast convergence of the Chebyshev iteration method.