В численной линейной алгебре , то итерация Чебышева является итерационным методом для определения решений системы линейных уравнений . Метод назван в честь русского математика Пафнутия Чебышева .
Итерация Чебышева позволяет избежать вычисления скалярных произведений, как это необходимо для других нестационарных методов. Для некоторых архитектур с распределенной памятью эти внутренние продукты являются узким местом с точки зрения эффективности. Цена, которую платят за отказ от внутренних продуктов, заключается в том, что метод требует достаточных знаний о спектре матрицы коэффициентов A , то есть верхней оценке для верхнего собственного значения и нижней оценке для нижнего собственного значения. Существует модификация методы для несимметричных матриц A .
Пример кода в MatLab [ править ]
функция [x] = SolChebyshev002 ( A, b, x0, iterNum, lMax, lMin ) d = ( lMax + lMin ) / 2 ; c = ( lMax - lMin ) / 2 ; preCond = глаз ( размер ( A )); % Прекондиционер х = х0 ; г = Ь - А * х ; для i = 1 : iterNum % size (A, 1) z = линзольв ( preCond , r ); если ( я == 1 ) p = z ; альфа = 1 / д ; иначе если ( я == 2 ) бета = ( 1 / 2 ) * ( с * альфа ) ^ 2 альфа = 1 / ( d - бета / альфа ); р = г + бета * р ; еще 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[edit]
- 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[edit]
- "Chebyshev iteration method", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- ^ Barrett, Richard; Michael, Berry; Tony, Chan; Demmel, James; Donato, June; Dongarra, Jack; Eijkhout, Victor; Pozo, Roldan; Romine, Charles; Van der Vorst, Henk (1993). "Templates for the solution of linear systems: building blocks for iterative methods". 43. SIAM. Cite journal requires
|journal=
(help) - ^ Gutknecht, Martin; Röllin, Stefan (2002). "The Chebyshev iteration revisited". Parallel Computing. 28 (2): 263–283. doi:10.1016/S0167-8191(01)00139-9.
- ^ On the Convergence of Chebyshev’s Method for Multiple Polynomial Zeros