Обратная итерация

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

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

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

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

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

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

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

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

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

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

В частности, взяв $\mu =0$ мы видим это $(A)^{-1}b_{k}$сходится к собственному вектору, соответствующему собственному значению $A^{-1}$ с наибольшей величиной ${\frac {1}{\lambda _{N}}}$ и, таким образом, может использоваться для определения наименьшего собственного значения величины $A$ поскольку они обратно пропорциональны.

Скорость сходимости

Проанализируем скорость сходимости метода.

степенной метод Известно, что сходится к пределу линейно , точнее:

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

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

$$\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).$$

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

Сложность

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

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

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

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

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

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

Мы можем переписать формулу следующим образом: $$(A-\mu I)b_{k+1}={\frac {b_{k}}{C_{k}}},$$

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

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

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

Трехдиагонализация, форма Хессенберга

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

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

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

Выбор константы нормировки C _k

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

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

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

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

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

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

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

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

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

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

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

См. также

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