Введение

В численном анализе обратная итерация (также известная как метод обратной степени) — это итеративный алгоритм для вычисления собственных значений. Он позволяет найти приближенный собственный вектор, если известно приближение соответствующего собственного значения. Метод концептуально схож с методом степеней. По-видимому, он был первоначально разработан для вычисления резонансных частот в области строительной механики. Алгоритм обратной итерации начинается с приближения собственного значения, соответствующего желаемому собственному вектору, и вектора – либо случайно выбранного вектора, либо приближения к собственному вектору. Метод описывается следующей итерацией:

где – некоторые константы, обычно выбираемые как . Поскольку собственные векторы определены с точностью до умножения на константу, выбор в теории может быть произвольным; практические аспекты выбора обсуждаются ниже. На каждой итерации вектор умножается на матрицу и нормализуется. Это точно такая же формула, как в методе степеней, за исключением замены матрицы на. Чем точнее приближение к собственному значению, тем быстрее сходится алгоритм; однако неправильный выбор может привести к медленной сходимости или сходимости к другому, нежелательному собственному вектору. На практике метод используется, когда известно хорошее приближение для собственного значения, и, следовательно, требуется лишь несколько (зачастую всего одна) итераций.

Сложность

Алгоритм обратной итерации требует решения линейной системы или вычисления обратной матрицы. Для неструктурированных матриц (не разреженных, не Toeplitz) это требует операций.

Выбор постоянной нормализации

На процессорах общего назначения (например, производимых Intel) время выполнения операций сложения, умножения и деления примерно одинаково. Однако на встраиваемых и/или малопотребляющих устройствах (цифровые сигнальные процессоры, FPGA, ASIC) аппаратная поддержка деления может отсутствовать, поэтому его следует избегать. Выбор позволяет быстро выполнять деление без специальной аппаратной поддержки, так как деление на степень двойки может быть реализовано как битовый сдвиг (для арифметики с фиксированной точкой) или вычитание из экспоненты (для арифметики с плавающей точкой). При реализации алгоритма с использованием арифметики с фиксированной точкой выбор константы особенно важен. Небольшие значения приведут к быстрому росту нормы и переполнению, а большие значения приведут к тому, что вектор будет стремиться к нулю.

Использование

Основным применением метода является случай, когда известно приближенное собственное значение и требуется найти соответствующий приближенный собственный вектор. В такой ситуации обратная итерация является основным и, вероятно, единственным методом, который следует использовать.

Методы определения приблизительных собственных значений

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

Норма матрицы как приближение к доминирующей собственной стоимости

Доминирующее собственное значение можно легко оценить для любой матрицы. Для любой индуцированной нормы справедливо, что для любого собственного значения |λ| ≤ ||A||. Таким образом, используя норму матрицы в качестве приближения доминирующего собственного значения, можно увидеть, что метод будет сходиться к доминирующему собственному вектору.

Оценки, основанные на статистике

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