Обратная итерация - Inverse iteration

В численный анализ, обратная итерация (также известный как метод обратной мощности) является итеративный алгоритм собственных значений. Это позволяет найти примернуюсобственный вектор когда приближение к соответствующему собственное значение уже известен. Метод концептуально аналогичен силовой метод Похоже, что изначально он был разработан для вычисления резонансных частот в области строительной механики.^[1]

Алгоритм обратной степенной итерации начинается с приближения ${\displaystyle \mu }$ для собственное значение соответствующий желаемому собственный вектор и вектор ${\displaystyle b_{0}}$, либо случайно выбранный вектор, либо приближение к собственному вектору. Метод описывается итерацией

${\displaystyle b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},}$

где ${\displaystyle C_{k}}$ - некоторые константы, обычно выбираемые как ${\displaystyle C_{k}=\|(A-\mu I)^{-1}b_{k}\|.}$ Поскольку собственные векторы определены с точностью до умножения на константу, выбор ${\displaystyle C_{k}}$ теоретически может быть произвольным; практические аспекты выбора ${\displaystyle C_{k}}$ обсуждаются ниже.

На каждой итерации вектор ${\displaystyle b_{k}}$ умножается на матрицу ${\displaystyle (A-\mu I)^{-1}}$ и нормализованный. Это точно такая же формула, что и в силовой метод, кроме замены матрицы ${\displaystyle A}$ от ${\displaystyle (A-\mu I)^{-1}.}$Чем ближе приближение ${\displaystyle \mu }$ к собственному значению выбирается, тем быстрее алгоритм сходится; однако неправильный выбор ${\displaystyle \mu }$ может привести к медленной сходимости или к сходимости к собственному вектору, отличному от желаемого. На практике этот метод используется, когда известно хорошее приближение для собственного значения, и, следовательно, требуется всего несколько (довольно часто всего одна) итерация.

Теория и конвергенция

Основная идея итерация мощности выбирает начальный вектор ${\displaystyle b}$ (либо собственный вектор приближение или случайный вектор) и итеративно вычисляя ${\displaystyle Ab,A^{2}b,A^{3}b,...}$. За исключением набора нуля мера, для любого начального вектора результат будет сходиться к собственный вектор соответствующий доминирующему собственное значение.

Обратная итерация делает то же самое для матрицы ${\displaystyle (A-\mu I)^{-1}}$, поэтому он сходится к собственному вектору, соответствующему доминирующему собственному значению матрицы ${\displaystyle (A-\mu I)^{-1}}$. Собственные значения этой матрицы: ${\displaystyle (\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},}$ где ${\displaystyle \lambda _{i}}$ собственные значения ${\displaystyle A}$.Наибольшее из этих чисел соответствует наименьшему из ${\displaystyle (\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).}$ Собственные векторы ${\displaystyle A}$ и из ${\displaystyle (A-\mu I)^{-1}}$ такие же, поскольку

${\displaystyle Av=\lambda v\Leftrightarrow (A-\mu I)v=\lambda v-\mu v\Leftrightarrow (\lambda -\mu )^{-1}v=(A-\mu I)^{-1}v}$

Заключение: Метод сходится к собственному вектору матрицы ${\displaystyle A}$ соответствующему ближайшему собственному значению к ${\displaystyle \mu .}$

В частности, принимая ${\displaystyle \mu =0}$ Мы видим, что ${\displaystyle (A)^{-1}b_{k}}$сходится к собственному вектору, соответствующему собственному значению ${\displaystyle A}$ с наименьшим абсолютным значением^{[требуется разъяснение ]}.

Скорость схождения

Разберем скорость сходимости метода.

В силовой метод известно сходятся линейно до предела, точнее:

${\displaystyle \mathrm {Distance} (b^{\mathrm {ideal} },b_{\mathrm {Power~Method} }^{k})=O\left(\left|{\frac {\lambda _{\mathrm {subdominant} }}{\lambda _{\mathrm {dominant} }}}\right|^{k}\right),}$

следовательно, для метода обратной итерации аналогичный результат звучит так:

${\displaystyle \mathrm {Distance} (b^{\mathrm {ideal} },b_{\mathrm {Inverse~iteration} }^{k})=O\left(\left|{\frac {\mu -\lambda _{\mathrm {closest~to~} \mu }}{\mu -\lambda _{\mathrm {second~closest~to~} \mu }}}\right|^{k}\right).}$

Это ключевая формула для понимания сходимости метода. Это показывает, что если ${\displaystyle \mu }$ выбирается достаточно близко к некоторому собственному значению ${\displaystyle \lambda }$, Например ${\displaystyle \mu -\lambda =\epsilon }$ каждая итерация будет повышать точность ${\displaystyle |\epsilon |/|\lambda +\epsilon -\lambda _{\mathrm {closest~to~} \lambda }|}$ раз. (Мы используем это для достаточно малых ${\displaystyle \epsilon }$ "ближайший к ${\displaystyle \mu }$"и" ближайший к ${\displaystyle \lambda }$"то же самое.) Для достаточно маленьких ${\displaystyle |\epsilon |}$ это примерно так же, как ${\displaystyle |\epsilon |/|\lambda -\lambda _{\mathrm {closest~to~} \lambda }|}$. Следовательно, если можно найти ${\displaystyle \mu }$, так что ${\displaystyle \epsilon }$ будет достаточно маленьким, тогда может быть достаточно нескольких итераций.

Сложность

Алгоритм обратной итерации требует решения линейная система или вычисление обратной матрицы. Для неструктурированных матриц (не разреженных, не теплицевых, ...) это требует ${\displaystyle O(n^{3})}$ операции.

Варианты реализации

Метод определяется формулой:

${\displaystyle b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},}$

Однако есть несколько вариантов его реализации.

Вычислить обратную матрицу или решить систему линейных уравнений

Мы можем переписать формулу следующим образом:

${\displaystyle (A-\mu I)b_{k+1}={\frac {b_{k}}{C_{k}}},}$

подчеркивая, что найти следующее приближение ${\displaystyle b_{k+1}}$ мы можем решить систему линейных уравнений. Есть два варианта: один может выбрать алгоритм, решающий линейную систему, или один может вычислить обратную ${\displaystyle (A-\mu I)^{-1}}$ а затем примените его к вектору. Оба варианта имеют сложность На³), точное количество зависит от выбранного метода.

Выбор зависит также от количества итераций. Наивно, если на каждой итерации решать линейную систему, сложность будет к * O (п³), где k - количество итераций; аналогично, вычисление обратной матрицы и ее применение на каждой итерации представляет собой сложную задачу. к * O (п³)Отметим, однако, что если оценка собственного значения ${\displaystyle \mu }$ остается постоянным, то мы можем уменьшить сложность до На³) + k * O (n²) с помощью любого метода. Вычисление обратной матрицы один раз и сохранение ее для применения на каждой итерации представляет собой сложную задачу. На³) + k * O (n²).Сохранение LU разложение из ${\displaystyle (A-\mu I)}$ и используя прямая и обратная замена решать систему уравнений на каждой итерации тоже сложно На³) + k * O (n²).

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

Тридиагонализация, Форма Гессенберга

Если необходимо выполнить много итераций (или несколько итераций, но для многих собственных векторов), тогда может быть разумным вывести матрицу на верхний уровень. Форма Гессенберга первый (для симметричной матрицы это будет трехдиагональная форма ). Что стоит ${\displaystyle {\begin{matrix}{\frac {10}{3}}\end{matrix}}n^{3}+O(n^{2})}$ арифметические операции с использованием техники, основанной на Сокращение домовладельцев ), с конечной последовательностью ортогональных преобразований подобия, что-то вроде двустороннего QR-разложения.^[2][3] (Для QR-разложения вращения Хаусхолдера умножаются только слева, но для случая Хессенберга они умножаются как слева, так и справа.) симметричные матрицы эта процедура стоит ${\displaystyle {\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})}$ арифметические операции с использованием техники, основанной на редукции Хаусхолдера.^[2][3]

Решение системы линейных уравнений для трехдиагональная матрица расходы ${\displaystyle O(n)}$ операций, поэтому сложность растет как ${\displaystyle O(n^{3})+kO(n)}$, где ${\displaystyle k}$ - номер итерации, что лучше, чем для прямого обращения. Однако для нескольких итераций такое преобразование может оказаться непрактичным.

Также преобразование в Форма Гессенберга включает извлечение квадратного корня и операцию деления, которые не всегда поддерживаются оборудованием.

Выбор константы нормализации ${\displaystyle C_{k}}$

На процессорах общего назначения (например, производства Intel) время выполнения сложения, умножения и деления примерно одинаково. Но на встроенном и / или оборудовании с низким энергопотреблением (цифровые сигнальные процессоры, FPGA, ASIC ) разделение может не поддерживаться аппаратными средствами, поэтому его следует избегать. Выбор ${\displaystyle C_{k}=2^{n_{k}}}$ позволяет быстрое деление без явной аппаратной поддержки, так как деление на степень 2 может быть реализовано как битовый сдвиг (для арифметика с фиксированной точкой ) или вычитание ${\displaystyle k}$ от экспоненты (для арифметика с плавающей запятой ).

При реализации алгоритма с использованием арифметика с фиксированной точкой, выбор постоянной ${\displaystyle C_{k}}$ особенно важно. Небольшие значения приведут к быстрому росту нормы ${\displaystyle b_{k}}$ и чтобы переполнение; большие значения ${\displaystyle C_{k}}$ вызовет вектор ${\displaystyle b_{k}}$ стремиться к нулю.

Применение

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

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

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

Бывают ситуации, когда метод можно использовать сам по себе, однако они весьма незначительны.

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

Доминирующее собственное значение легко оценить для любой матрицы. Для любого индуцированная норма правда, что${\displaystyle \left\|A\right\|\geq |\lambda |,}$ для любого собственного значения ${\displaystyle \lambda }$. Итак, взяв норму матрицы в качестве приближенного собственного значения, можно увидеть, что метод сходится к доминирующему собственному вектору.

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

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

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

• Итерация мощности
• Итерация фактора Рэлея
• Список алгоритмов собственных значений

использованная литература

1. Эрнст Польхаузен, Berechnung der Eigenschwingungen statisch-bestimmter Fachwerke, ZAMM - Zeitschrift für AngewandteMathematik und Mechanik 1, 28-42 (1921).
2. Деммель, Джеймс У. (1997), Прикладная числовая линейная алгебра, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, ISBN  0-89871-389-7, Г-Н  1463942.
3. Ллойд Н. Трефетен и Дэвид Бау, Числовая линейная алгебра (СИАМ, 1997).