Метод итераций Рэлея

Метод итераций Рэлея — итеративный алгоритм вычисления собственных значений и векторов, который дополняет идею обратного степенного метода итеративным вычислением текущего приближения к собственному значению с помощью отношения Рэлея.

Метод Рэлея имеет очень большую скорость сходимости, и часто для получения решения требуется всего лишь несколько итераций. Для симметричных и эрмитовых матриц при достаточно хорошо выбранных начальных значениях сходимость кубическая. Однако время выполнения каждой итерации обычно пропорционально кубу размера матрицы, в то время как для обратного степенного и степенного метода оно квадратично.

АлгоритмПравить

Как и в обратном степенном методе, мы задаём некоторое начальное приближение ${\mathrm{\mu <!--\; \mu \; -->}}_0$$\mu _{0}$  к собственному значению матрицы $A$$A$  и начальный вектор $b_0$$b_{0}$ , который может быть либо случайным, либо известным приближением к собственному вектору. Далее итеративно вычисляем новые приближения к собственному вектору $b_{i+1}$$b_{i+1}$  по формуле

$b_{i+1}=\frac{(A-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}_{i}I{)}^{-<!--\; -\; -->1}{b}_i}{||(A-<!--\; -\; -->{\mathrm{\mu <!--\; \mu \; -->}}_{i}I{)}^{-<!--\; -\; -->1}{b}_i||},$$b_{i+1}={\frac {(A-\mu _{i}I)^{-1}b_{i}}{||(A-\mu _{i}I)^{-1}b_{i}||}},$ , где $I$$I$  единичная матрица.

В завершение итерации вычисляем следующее приближение к собственному значению с помощью отношения Рэлея:

${\mathrm{\mu <!--\; \mu \; -->}}_{i+1}=\frac{b_{i+1}^{\ast <!--\; \ast \; -->}A{b}_{i+1}}{b_{i+1}^{\ast <!--\; \ast \; -->}{b}_{i+1}}.$$\mu _{i+1}={\frac {b_{i+1}^{*}Ab_{i+1}}{b_{i+1}^{*}b_{i+1}}}.$ 

Пример программной реализацииПравить

Ниже приведен пример реализации на языке 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 0-89871-361-7.
• Rainer Kress, «Numerical Analysis», Springer, 1991. ISBN 0-387-98408-9