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

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

27.01.2021


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

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

Алгоритм

Как и в обратном степенном методе мы задаём некоторое начальное приближение μ 0 {displaystyle mu _{0}} к собственному значению матрицы A {displaystyle A} и начальный вектор b 0 {displaystyle b_{0}} , который может быть либо случайным, либо известным приближением к собственному вектору. Далее итеративно вычисляем новые приближения к собственному вектору b i + 1 {displaystyle b_{i+1}} по формуле

b i + 1 = ( A − μ i I ) − 1 b i | | ( A − μ i I ) − 1 b i | | , {displaystyle b_{i+1}={frac {(A-mu _{i}I)^{-1}b_{i}}{||(A-mu _{i}I)^{-1}b_{i}||}},} , где I {displaystyle I} единичная матрица.

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

μ i + 1 = b i + 1 ∗ A b i + 1 b i + 1 ∗ b i + 1 . {displaystyle 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