Итерация фактора Рэлея

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

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

Алгоритм

Алгоритм очень похож на обратную итерацию, но в конце каждой итерации расчетное собственное значение заменяется коэффициентом Рэлея. Начните с выбора некоторого значения $\mu _{0}$ как начальное предположение о собственном значении для эрмитовой матрицы $A$. Начальный вектор $b_{0}$ также должно быть предоставлено в качестве начального предположения о собственном векторе.

Вычислить следующее приближение собственного вектора $b_{i+1}$ к $$b_{i+1}={\frac {(A-\mu _{i}I)^{-1}b_{i}}{\|(A-\mu _{i}I)^{-1}b_{i}\|}},$$ где $I$ - единичная матрица, и присвоим очередное приближение собственного значения к коэффициенту Рэлея текущей итерации, равное
$$\mu _{i+1}={\frac {b_{i+1}^{*}Ab_{i+1}}{b_{i+1}^{*}b_{i+1}}}.$$

Чтобы вычислить более одного собственного значения, алгоритм можно комбинировать с методом дефлятирования.

Обратите внимание, что для очень маленьких задач полезно заменить обратную матрицу на адъюгату , которая даст ту же итерацию, поскольку она равна обратной матрице до нерелевантного масштаба (в частности, обратной определителю). Сопряженное легче вычислить явно, чем обратное (хотя обратное легче применить к вектору для немалых задач), и оно более корректно с численной точки зрения, поскольку оно остается четко определенным при сходимости собственного значения.

Пример

Рассмотрим матрицу

$A=\left[{\begin{matrix}1&2&3\\1&2&1\\3&2&1\\\end{matrix}}\right]$

для которого точные собственные значения равны $\lambda _{1}=3+{\sqrt {5}}$, $\lambda _{2}=3-{\sqrt {5}}$ и $\lambda _{3}=-2$, с соответствующими собственными векторами

$v_{1}=\left[{\begin{matrix}1\\\varphi -1\\1\\\end{matrix}}\right]$, $v_{2}=\left[{\begin{matrix}1\\-\varphi \\1\\\end{matrix}}\right]$ и $v_{3}=\left[{\begin{matrix}1\\0\\1\\\end{matrix}}\right]$.

(где $\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}$ это золотое сечение).

Наибольшее собственное значение $\lambda _{1}\approx 5.2361$ и соответствует любому собственному вектору, пропорциональному $v_{1}\approx \left[{\begin{matrix}1\\0.6180\\1\\\end{matrix}}\right].$

Начнем с первоначального предположения о собственном значении

$b_{0}=\left[{\begin{matrix}1\\1\\1\\\end{matrix}}\right],~\mu _{0}=200$.

Тогда первая итерация дает

$b_{1}\approx \left[{\begin{matrix}-0.57927\\-0.57348\\-0.57927\\\end{matrix}}\right],~\mu _{1}\approx 5.3355$

вторая итерация,

$b_{2}\approx \left[{\begin{matrix}0.64676\\0.40422\\0.64676\\\end{matrix}}\right],~\mu _{2}\approx 5.2418$

и третий,

$b_{3}\approx \left[{\begin{matrix}-0.64793\\-0.40045\\-0.64793\\\end{matrix}}\right],~\mu _{3}\approx 5.2361$

откуда очевидна кубическая сходимость.

Октавная реализация

Ниже представлена ​​простая реализация алгоритма в 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

См. также

• Итерация мощности
• Обратная итерация

Ссылки

• Ллойд Н. Трефетен и Дэвид Бау, III, Численная линейная алгебра , Общество промышленной и прикладной математики, 1997. ISBN   0-89871-361-7 .
• Райнер Кресс, «Численный анализ», Springer, 1991. ISBN   0-387-98408-9