Chebyshev iteration

The Chebyshev iteration (after Pafnuti Lwowitsch Chebyshev ) is a numerical method for solving systems of linear equations with and is also referred to as a semi-iterative method, since it can be interpreted as a simple iteration step of a splitting method with subsequent extrapolation. The basis is the recursion formula for Chebyshev polynomials . The method reaches the speed of the CG method for symmetric positive definite matrices , but can also be adapted for asymmetric matrices if information about the position of the eigenvalues ​​is available. ${\displaystyle Ax=b}$ ${\displaystyle A\in \mathbb {R} ^{n\times n}}$

The semi-iterative method

The basis is the idea that a better sequence can be obtained from the vector sequence obtained with a splitting process through general linear combinations ${\displaystyle (x_{k})_{k\geq 0}}$

${\displaystyle y_{k}=\sum _{j=0}^{k}\alpha _{kj}x_{j}}$

constructed. In order not to leave an exact solution again is necessary. Since the following applies to the errors in the splitting process , one obtains for the new error ${\displaystyle {\hat {x}}}$ ${\displaystyle \sum _{j=0}^{k}\alpha _{kj}=1}$ ${\displaystyle x_{k}-{\hat {x}}=M^{k}(x_{0}-{\hat {x}}),\ M=I-B^{-1}A}$

${\displaystyle y_{k}-{\hat {x}}=\sum _{j=0}^{k}\alpha _{kj}(x_{j}-{\hat {x}})=\sum _{j=0}^{k}\alpha _{kj}M^{j}(x_{0}-{\hat {x}})=p_{k}(M)(x_{0}-{\hat {x}}).}$

So the starting error is multiplied by the matrix polynomial with the aim of reducing it. If the matrix only has real eigenvalues ​​in an interval , the polynomial with the smallest bound for the spectral radius is a shifted Chebyshev polynomial . Since a two-stage recursion formula applies to the latter, the Chebyshev iteration can also be carried out as a two-stage procedure: ${\displaystyle x_{0}-{\hat {x}}}$ ${\displaystyle p_{k}(M)}$ ${\displaystyle A}$ ${\displaystyle [a,b],\,a>0,}$ ${\displaystyle \rho (p_{k}(A))}$ ${\displaystyle T_{k}}$

${\displaystyle \,\!y_{1}=y_{0}+\gamma (b-Ay_{0})}$

${\displaystyle y_{k+1}=\omega _{k}(y_{k}+\gamma (b-Ay_{k}))+(1-\omega _{k})y_{k-1},\ k=1,2,\ldots }$

with the parameters

${\displaystyle \gamma ={\frac {2}{a+b}},\quad \omega _{k}=2\mu {\frac {T_{k}(\mu )}{T_{k+1}(\mu )}},\quad \mu ={\frac {b+a}{b-a}}.}$

In the instruction for it can be seen that there is an optimal step of the Richardson procedure in the brackets . ${\displaystyle y_{k+1}}$

For a symmetric-definite matrix , this iteration is closely related to the CG method, which, however, determines the parameters differently and has the same speed of convergence . The Chebyshev iteration can also be applied to asymmetrical matrices with complex eigenvalues if these can be included in an ellipse that does not contain the zero point. ${\displaystyle A}$ ${\displaystyle \gamma ,\omega _{k}}$

Convergence of the procedure

In the Euclidean norm, the error bound applies to a symmetrical, positively definite matrix ${\displaystyle A}$

${\displaystyle \|y_{k}-{\hat {x}}\|\leq 2\left({\frac {{\sqrt {\kappa }}-1}{{\sqrt {\kappa }}+1}}\right)^{m}\|y_{0}-{\hat {x}}\|,\ m\geq 0,\quad \kappa =b/a,}$

similar to the CG method , wherein a barrier for the condition number of the matrix is . For the error is apparently towards zero. ${\displaystyle \kappa }$ ${\displaystyle A}$ ${\displaystyle \kappa \geq \kappa _{2}(A)=\lambda _{\rm {max}}(A)/\lambda _{\rm {min}}(A)}$ ${\displaystyle m\to \infty }$

The convergence advantage over the simple splitting method or Richardson method is that the convergence only depends on the root of the condition. In the case of complex eigenvalues, this advantage is lost the more the rounder the ellipse required for the enclosure becomes. Finally, when enclosing in a circle , the simple method is also optimal. ${\displaystyle \omega _{k}\equiv 1}$

literature

• Gene H. Golub, Charles van Loan: Matrix Computations , Johns Hopkins University Press.