In
numerical linear algebra
Numerical linear algebra, sometimes called applied linear algebra, is the study of how matrix operations can be used to create computer algorithms which efficiently and accurately provide approximate answers to questions in continuous mathemati ...
, the Chebyshev iteration is an
iterative method
In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...
for determining the solutions of a
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variable (math), variables.
For example,
: \begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of th ...
. The method is named after
Russia
Russia, or the Russian Federation, is a country spanning Eastern Europe and North Asia. It is the list of countries and dependencies by area, largest country in the world, and extends across Time in Russia, eleven time zones, sharing Borders ...
n mathematician
Pafnuty Chebyshev
Pafnuty Lvovich Chebyshev ( rus, Пафну́тий Льво́вич Чебышёв, p=pɐfˈnutʲɪj ˈlʲvovʲɪtɕ tɕɪbɨˈʂof) ( – ) was a Russian mathematician and considered to be the founding father of Russian mathematics.
Chebysh ...
.
Chebyshev iteration avoids the computation of
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, ofte ...
s 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
In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
and lower estimate for the lower eigenvalue. There are modifications of the method for nonsymmetric matrices ''A''.
Example code in
MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementat ...
function = 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 = 1/d;
else if (i 2)
beta = (1/2) * (c * alpha)^2
alpha = 1/(d - beta / alpha);
p = z + beta * p;
else
beta = (c * alpha / 2)^2;
alpha = 1/(d - beta / alpha);
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
Code translated from
and.
See also
*
Iterative method. Linear systems
*
List of numerical analysis topics. Solving systems of linear equations
*
Jacobi iteration
*
Gauss–Seidel method
In numerical linear algebra, the Gauss–Seidel method, also known as the Liebmann method or the method of successive displacement, is an iterative method used to solve a system of linear equations. It is named after the German mathematicians Ca ...
*
Modified Richardson iteration
Modified Richardson iteration is an iterative method for solving a system of linear equations. Richardson iteration was proposed by Lewis Fry Richardson in his work dated 1910. It is similar to the Jacobi and Gauss–Seidel method.
We seek the so ...
*
Successive over-relaxation
In numerical linear algebra, the method of successive over-relaxation (SOR) is a variant of the Gauss–Seidel method for solving a linear system of equations, resulting in faster convergence. A similar method can be used for any slowly convergi ...
*
Conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-semidefinite. The conjugate gradient method is often implemented as an it ...
*
Generalized minimal residual method
In mathematics, the generalized minimal residual method (GMRES) is an iterative method for the numerical solution of an indefinite nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace wit ...
*
Biconjugate gradient method
In mathematics, more specifically in numerical linear algebra, the biconjugate gradient method is an algorithm to solve systems of linear equations
:A x= b.\,
Unlike the conjugate gradient method, this algorithm does not require the matrix A to ...
*
Iterative Template Library
*
IML++
References
*
External links
Chebyshev Iteration. From MathWorldChebyshev Iteration. Implementation on Go language{{Numerical linear algebra
Numerical linear algebra
Iterative methods