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

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

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

Алгоритм

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

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

${ displaystyle b_ {i + 1} = { frac {(A- mu _ {i} I) ^ {- 1} b_ {i}} { | (A- mu _ {i} I) ^ {-1} b_ {i} |}},}$
куда ${ displaystyle I}$ является единичной матрицей, и устанавливает следующее приближение собственного значения к коэффициенту Рэлея текущей итерации, равному
${ Displaystyle му _ {я + 1} = { гидроразрыва {b_ {я + 1} ^ {*} Ab_ {я + 1}} {b_ {я + 1} ^ {*} b_ {я + 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} приблизительно 5,2361}$ и соответствует любому собственному вектору, пропорциональному ${ displaystyle v_ {1} приблизительно 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} приблизительно left [{ begin {matrix} -0,57927 - 0,57348 - 0,57927 end {matrix}} right], ~ mu _ {1} приблизительно 5,3355 }$

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

${ displaystyle b_ {2} примерно left [{ begin {matrix} 0,64676 0,40422 0,64676 end {matrix}} right], ~ mu _ {2} примерно 5,2418}$

и третий,

${ displaystyle b_ {3} приблизительно left [{ begin {matrix} -0.64793 - 0.40045 - 0.64793 end {matrix}} right], ~ mu _ {3} приблизительно 5.2361 }$

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

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

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

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

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

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

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

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