Итерация фактора Рэлея - Rayleigh quotient iteration

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

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

Алгоритм

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

Вычислить следующее приближение собственного вектора ${\displaystyle b_{i+1}}$ к

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

и третий,

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

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

Реализация октавы

Ниже приводится простая реализация алгоритма в Октава.

функцияИкс =Рэйли(А, эпсилон, мю, х)Икс = Икс / норма(Икс);  % оператор обратной косой черты в Octave решает линейную систему  у = (А - му * глаз(ряды(А))) \ Икс;   лямбда = у' * Икс;  му = му + 1 / лямбда  ошибаться = норма(у - лямбда * Икс) / норма(у)  пока эрр> эпсилон    Икс = у / норма(у);    у = (А - му * глаз(ряды(А))) \ Икс;    лямбда = у' * Икс;    му = му + 1 / лямбда    ошибаться = норма(у - лямбда * Икс) / норма(у)  конецконец

Смотрите также

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

Рекомендации

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