Chebyshev iteration - AbsoluteAstronomy.com

Numerical linear algebra

Numerical linear algebra is the study of algorithms for performing linear algebra computations, most notably matrix operations, on computers. It is often a fundamental part of engineering and computational science problems, such as image and signal processing, Telecommunication, computational...

, the Chebyshev iteration is an
iterative method for determining the solutions of a system of linear equations. The method is named after Russia

Russia

Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...

n mathematician Pafnuty Chebyshev

Pafnuty Chebyshev

Pafnuty Lvovich Chebyshev was a Russian mathematician. His name can be alternatively transliterated as Chebychev, Chebysheff, Chebyshov, Tschebyshev, Tchebycheff, or Tschebyscheff .-Early years:One of nine children, Chebyshev was born in the village of Okatovo in the district of Borovsk,...

.

Chebyshev iteration avoids the computation of inner products as is necessary for the other nonstationary methods. For some distributed-memory architectures these inner products are a bottleneck with respect to efficiency. The price one pays for avoiding inner products is that the method requires enough knowledge about spectrum of the coefficient matrix A, that is an upper estimate for the upper eigenvalue and lower estimate for the lower eigenvalue. There are modifications of the method for nonsymmetric matrices A.

Example code in MatLab
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...

function [x] = SolChebyshev002(A,b,x0,iterNum,lMax,lMin)

d=(lMax+lMin)/2;
c=(lMax-lMin)/2;
preCond=eye(size(A)); %preconditioner
x=x0;
r=b-A*x;

for i = 1:iterNum % size(A,1)
z = linsolve(preCond,r);
if (i

1)
p=z;
alpha=2/d;
else
beta=(calpha/2)^2;
alpha=1/(d-beta);
p=z+betap;
end;

x=x+alphap;
r=b-Ax; %(=r-alphaAp)
if (norm(r)<1e-15), break; end; %stop if necessary
end;
end

External links

1) p=z; alpha=2/d; else beta=(c*alpha/2)^2; alpha=1/(d-beta); p=z+beta*p; end; x=x+alpha*p; r=b-A*x; %(=r-alpha*A*p) if (norm(r)<1e-15), break; end; %stop if necessary end; end

Templates for the Solution of Linear Systems Chebyshev Iteration. From MathWorld

1)
p=z;
alpha=2/d;
else
beta=(calpha/2)^2;
alpha=1/(d-beta);
p=z+betap;
end;

x=x+alphap;
r=b-Ax; %(=r-alphaAp)
if (norm(r)<1e-15), break; end; %stop if necessary
end;
end

Templates for the Solution of Linear Systems

Chebyshev Iteration. From MathWorld