Русская Википедия:Метод итераций Рэлея
Метод итераций Рэлея — итеративный алгоритм вычисления собственных значений и векторов, который дополняет идею обратного степенного метода итеративным вычислением текущего приближения к собственному значению с помощью отношения Рэлея.
Метод Рэлея имеет очень большую скорость сходимости, и часто для получения решения требуется всего лишь несколько итераций. Для симметричных и эрмитовых матриц при достаточно хорошо выбранных начальных значениях сходимость кубическая. Однако время выполнения каждой итерации обычно пропорционально кубу размера матрицы, в то время как для обратного степенного и степенного метода оно квадратично.
Алгоритм
Как и в обратном степенном методе, мы задаём некоторое начальное приближение <math>\mu_0</math> к собственному значению матрицы <math>A</math> и начальный вектор <math>b_0</math>, который может быть либо случайным, либо известным приближением к собственному вектору. Далее итеративно вычисляем новые приближения к собственному вектору <math>b_{i+1}</math> по формуле
<math> b_{i+1} = \frac{(A-\mu_i I)^{-1}b_i}{||(A-\mu_i I)^{-1}b_i||}, </math>, где <math>I</math> единичная матрица.
В завершение итерации вычисляем следующее приближение к собственному значению с помощью отношения Рэлея:
- <math>
\mu_{i+1} = \frac{b^*_{i+1} A b_{i+1}}{b^*_{i+1} b_{i+1}}. </math>
Пример программной реализации
Ниже приведен пример реализации на языке GNU Octave.
function x = rayleigh(A, epsilon, mu, x)
x = x / norm(x);
% the backslash operator in Octave solves a linear system
y = (A - mu * eye(rows(A))) \ x;
lambda = y' * x;
mu = mu + 1 / lambda
err = norm(y - lambda * x) / norm(y)
while err > epsilon
x = y / norm(y);
y = (A - mu * eye(rows(A))) \ x;
lambda = y' * x;
mu = mu + 1 / lambda
err = norm(y - lambda * x) / norm(y)
end
end
Ссылки
- Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. Шаблон:Isbn.
- Rainer Kress, «Numerical Analysis», Springer, 1991. Шаблон:Isbn