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

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

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

Алгоритм

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

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

${\ displaystyle b_ {я + 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} }}.}$

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

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

пример

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

{\ 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 .

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

Languages

In other projects