Chebyshev iteration

In numerical linear algebra, the Chebyshev iteration is an iterative method for determining the solutions of a system of linear equations. The method is named after Russian mathematician Pafnuty Chebyshev.

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.

## Contents

* 1 Example code in MATLAB
* 2 See also
* 3 References
* 4 External links

## Example code in MATLAB

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 = 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 [1] and.[2]

## See also

* Iterative method. Linear systems
* List of numerical analysis topics. Solving systems of linear equations
* Jacobi iteration
* Gauss–Seidel method
* Modified Richardson iteration
* Successive over-relaxation
* Conjugate gradient method
* Generalized minimal residual method
* Biconjugate gradient method
* Iterative Template Library
* IML++

## References

* Hazewinkel, Michiel, ed. (2001), "Chebyshev iteration method", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=p/c021900

1. ↑ Barrett, Richard; Michael, Berry; Tony, Chan; Demmel, James; Donato, June; Dongarra, Jack; Eijkhout, Victor; Pozo, Roldan et al. (1994). Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (2nd ed.). SIAM. http://www.netlib.org/linalg/html_templates/Templates.html.
2. ↑ Gutknecht, Martin; Röllin, Stefan (2002). "The Chebyshev iteration revisited". Parallel Computing 28 (2): 263–283. doi:10.1016/S0167-8191(01)00139-9.

## External links

* Chebyshev Iteration. From MathWorld
* Chebyshev Iteration. Implementation on Go language

* v
* t
* e

Numerical linear algebra

Key concepts|

* Floating point
* Numerical stability

Problems|

* System of linear equations
* Matrix decompositions
* Matrix multiplication (algorithms)
* Matrix splitting
* Sparse problems

Hardware|

* CPU cache
* TLB
* Cache-oblivious algorithm
* SIMD
* Multiprocessing

Software|

* MATLAB
* Basic Linear Algebra Subprograms (BLAS)
* LAPACK
* Specialized libraries
* General purpose software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Chebyshev iteration. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Chebyshev_iteration&oldid=4153079"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template