Алгоритм разделяй и властвуй на собственные значения - Divide-and-conquer eigenvalue algorithm

Алгоритмы разделения и властвования на собственные значения являются классом алгоритмы собственных значений за Эрмитский или же настоящий симметричные матрицы которые недавно (около 1990-х) стали конкурентоспособными с точки зрения стабильность и эффективность с более традиционными алгоритмами, такими как QR-алгоритм. Основная концепция этих алгоритмов - это разделяй и властвуй подход от Информатика. An собственное значение проблема разделена на две задачи примерно вдвое меньшего размера, каждая из которых решена рекурсивно, а собственные значения исходной задачи вычисляются по результатам этих меньших задач.

Здесь мы представляем простейшую версию алгоритма «разделяй и властвуй», подобного тому, который был первоначально предложен Куппеном в 1981 году. Многие детали, выходящие за рамки этой статьи, будут опущены; однако без учета этих деталей алгоритм не является полностью стабильным.

Фон

Как и большинство алгоритмов собственных значений для эрмитовых матриц, разделяй и властвуй начинается с сокращения до трехдиагональный форма. Для ${\displaystyle m\times m}$ матрица, стандартный метод для этого, через Размышления домохозяина, берет ${\displaystyle {\frac {4}{3}}m^{3}}$ шлепки, или же ${\displaystyle {\frac {8}{3}}m^{3}}$ если собственные векторы также необходимы. Есть и другие алгоритмы, такие как Итерация Арнольди, что может быть лучше для определенных классов матриц; мы не будем здесь рассматривать это дальше.

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

${\displaystyle T={\begin{bmatrix}T_{1}&0\\0&T_{2}\end{bmatrix}}.}$

Собственные значения и собственные векторы ${\displaystyle T}$ просто те из ${\displaystyle T_{1}}$ и ${\displaystyle T_{2}}$, и почти всегда будет быстрее решить эти две более мелкие проблемы, чем решить исходную проблему сразу. Этот метод можно использовать для повышения эффективности многих алгоритмов собственных значений, но он имеет особое значение для разделения и властвования.

В оставшейся части этой статьи мы будем предполагать, что входом в алгоритм «разделяй и властвуй» является ${\displaystyle m\times m}$ вещественная симметричная трехдиагональная матрица ${\displaystyle T}$. Хотя алгоритм может быть модифицирован для эрмитовых матриц, мы не приводим здесь подробностей.

Разделять

В разделять Часть алгоритма «разделяй и властвуй» исходит из понимания того, что трехдиагональная матрица является «почти» блочной диагональю.

Размер подматрицы ${\displaystyle T_{1}}$ мы позвоним ${\displaystyle n\times n}$, а потом ${\displaystyle T_{2}}$ является ${\displaystyle (m-n)\times (m-n)}$. Обратите внимание, что замечание о ${\displaystyle T}$ почти блочная диагональ верна независимо от того, как ${\displaystyle n}$ выбрано (т.е. есть много способов так разложить матрицу). Однако с точки зрения эффективности имеет смысл выбрать ${\displaystyle n\approx m/2}$.

Мы пишем ${\displaystyle T}$ как блочно-диагональная матрица, плюс ранг-1 исправление:

Единственная разница между ${\displaystyle T_{1}}$ и ${\displaystyle {\hat {T}}_{1}}$ это нижняя правая запись ${\displaystyle t_{nn}}$ в ${\displaystyle {\hat {T}}_{1}}$ был заменен на ${\displaystyle t_{nn}-\beta }$ и аналогично в ${\displaystyle {\hat {T}}_{2}}$ верхняя левая запись ${\displaystyle t_{n+1,n+1}}$ был заменен на ${\displaystyle t_{n+1,n+1}-\beta }$.

Оставшаяся часть шага деления заключается в поиске собственных значений (и, при желании, собственных векторов) ${\displaystyle {\hat {T}}_{1}}$ и ${\displaystyle {\hat {T}}_{2}}$, то есть найти диагонализации ${\displaystyle {\hat {T}}_{1}=Q_{1}D_{1}Q_{1}^{T}}$ и ${\displaystyle {\hat {T}}_{2}=Q_{2}D_{2}Q_{2}^{T}}$. Это может быть выполнено с помощью рекурсивных вызовов алгоритма «разделяй и властвуй», хотя практические реализации часто переключаются на алгоритм QR для достаточно малых подматриц.

Завоевывать

В завоевывать часть алгоритма - неинтуитивная часть. Учитывая диагонализацию подматриц, вычисленную выше, как нам найти диагонализацию исходной матрицы?

Сначала определим ${\displaystyle z^{T}=(q_{1}^{T},q_{2}^{T})}$, куда ${\displaystyle q_{1}^{T}}$ это последняя строка ${\displaystyle Q_{1}}$ и ${\displaystyle q_{2}^{T}}$ это первая строка ${\displaystyle Q_{2}}$. Теперь элементарно показать, что

${\displaystyle T={\begin{bmatrix}Q_{1}&\\&Q_{2}\end{bmatrix}}\left({\begin{bmatrix}D_{1}&\\&D_{2}\end{bmatrix}}+\beta zz^{T}\right){\begin{bmatrix}Q_{1}^{T}&\\&Q_{2}^{T}\end{bmatrix}}}$

Оставшаяся задача была сведена к нахождению собственных значений диагональной матрицы плюс коррекция первого ранга. Прежде чем показать, как это сделать, упростим обозначения. Ищем собственные значения матрицы ${\displaystyle D+ww^{T}}$, куда ${\displaystyle D}$ диагональна с различными элементами и ${\displaystyle w}$ - любой вектор с ненулевыми элементами.

Если w_я равен нулю, (${\displaystyle e_{i}}$, d_я) является собственной парой ${\displaystyle D+ww^{T}}$ поскольку${\displaystyle (D+ww^{T})e_{i}=De_{i}=d_{i}e_{i}}$.

Если ${\displaystyle \lambda }$ - собственное значение, имеем:

${\displaystyle (D+ww^{T})q=\lambda q}$

куда ${\displaystyle q}$ - соответствующий собственный вектор. Сейчас же

${\displaystyle (D-\lambda I)q+w(w^{T}q)=0}$

${\displaystyle q+(D-\lambda I)^{-1}w(w^{T}q)=0}$

${\displaystyle w^{T}q+w^{T}(D-\lambda I)^{-1}w(w^{T}q)=0}$

Имейте в виду, что ${\displaystyle w^{T}q}$ ненулевой скаляр. Ни один ${\displaystyle w}$ ни ${\displaystyle q}$ равны нулю. Если ${\displaystyle w^{T}q}$ должен был быть нулевым, ${\displaystyle q}$ будет собственным вектором ${\displaystyle D}$ к ${\displaystyle (D+ww^{T})q=\lambda q}$. Если бы это было так, ${\displaystyle q}$ будет содержать только одну ненулевую позицию, так как ${\displaystyle D}$ имеет отличную диагональ, поэтому внутренний продукт ${\displaystyle w^{T}q}$ в конце концов, не может быть нулю. Таким образом, мы имеем:

${\displaystyle 1+w^{T}(D-\lambda I)^{-1}w=0}$

или записать в виде скалярного уравнения,

${\displaystyle 1+\sum _{j=1}^{m}{\frac {w_{j}^{2}}{d_{j}-\lambda }}=0.}$

Это уравнение известно как светское уравнение. Таким образом, проблема свелась к поиску корней рациональная функция определяется левой частью этого уравнения.

Все общие алгоритмы собственных значений должны быть итеративными, и алгоритм «разделяй и властвуй» ничем не отличается. Решение нелинейный секулярное уравнение требует итеративного метода, такого как Метод Ньютона – Рафсона. Однако каждый корень можно найти в О (1) итерации, каждая из которых требует ${\displaystyle \Theta (m)}$ шлепки (для ${\displaystyle m}$-степень рациональной функции), что делает стоимость итерационной части этого алгоритма ${\displaystyle \Theta (m^{2})}$.

Анализ

Как обычно для алгоритмов «разделяй и властвуй», мы будем использовать основная теорема для повторений "разделяй и властвуй" для анализа времени работы. Помните, что выше мы заявили, что выбираем ${\displaystyle n\approx m/2}$. Мы можем написать отношение повторения:

${\displaystyle T(m)=2\times T\left({\frac {m}{2}}\right)+\Theta (m^{2})}$

В обозначениях Главной теоремы ${\displaystyle a=b=2}$ и поэтому ${\displaystyle \log _{b}a=1}$. Четко, ${\displaystyle \Theta (m^{2})=\Omega (m^{1})}$, так что у нас есть

${\displaystyle T(m)=\Theta (m^{2})}$

Помните, что выше мы указывали, что приведение эрмитовой матрицы к трехдиагональной форме принимает ${\displaystyle {\frac {4}{3}}m^{3}}$ шлепки. Это затмевает время работы части «разделяй и властвуй», и на данный момент не ясно, какое преимущество алгоритм «разделяй и властвуй» предлагает по сравнению с алгоритмом QR (который также требует ${\displaystyle \Theta (m^{2})}$ флопы для трехдиагональных матриц).

Преимущество принципа «разделяй и властвуй» возникает тогда, когда нужны собственные векторы. В этом случае приведение к трехдиагональной форме принимает ${\displaystyle {\frac {8}{3}}m^{3}}$, но вторая часть алгоритма принимает ${\displaystyle \Theta (m^{3})}$ также. Для алгоритма QR с разумной целевой точностью это ${\displaystyle \approx 6m^{3}}$, в то время как для разделяй и властвуй это ${\displaystyle \approx {\frac {4}{3}}m^{3}}$. Причина этого улучшения в том, что в «разделяй и властвуй» ${\displaystyle \Theta (m^{3})}$ часть алгоритма (умножение ${\displaystyle Q}$ матрицы) отделен от итерации, тогда как в QR это должно происходить на каждом итерационном шаге. Добавление ${\displaystyle {\frac {8}{3}}m^{3}}$ флоп для снижения, общее улучшение от ${\displaystyle \approx 9m^{3}}$ к ${\displaystyle \approx 4m^{3}}$ шлепки.

Практическое использование алгоритма «разделяй и властвуй» показало, что в большинстве реалистичных задач на собственные значения этот алгоритм работает лучше этого. Причина в том, что очень часто матрицы ${\displaystyle Q}$ и векторы ${\displaystyle z}$ как правило численно редкий, что означает, что у них много записей со значениями меньше, чем плавающая точка точность, позволяющая численное дефляция, т.е. разбиение проблемы на несвязанные подзадачи.

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

Представленный здесь алгоритм является самой простой версией. Во многих практических реализациях используются более сложные поправки ранга 1, чтобы гарантировать стабильность; некоторые варианты даже используют исправления ранга 2.^{[нужна цитата ]}

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

Алгоритм разделяй и властвуй легко распараллеленный, и линейная алгебра вычислительные пакеты, такие как ЛАПАК содержат качественные параллельные реализации.

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

• Деммель, Джеймс У. (1997), Прикладная числовая линейная алгебра, Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, ISBN  0-89871-389-7, МИСТЕР  1463942.
• Куппен, J.J.M. (1981). "Разделяй и властвуй метод для симметричной трехдиагональной собственной задачи". Numerische Mathematik. 36: 177–195.