Круги Гершгорина

Круги Гершгорина — набор кругов на комплексной плоскости, определяемых по квадратной матрице, таких, что все собственные значения данной матрицы заведомо лежат внутри каких-то из этих кругов. Таким образом, они позволяют получить априорное ограничение на расположение собственных значений (локализовать спектр) квадратной матрицы. Впервые их описание было опубликовано советским математиком Семёном Ароновичем Гершгориным в 1931 году.

Теорема Гершгорина

Пусть $A$ — комплексная матрица $n\times n$ с элементами $a_{ij}$. Обозначим через $R_{i}$ сумму абсолютных значений внедиагональных элементов $i$-й строки (при $i\in \{1,\dots ,n\}$):

$R_{i}=\sum _{j\neq {i}}\left|a_{ij}\right|.$

Рассмотрим $D(a_{ii},R_{i})\subseteq \mathbb {C}$ — круг с центром в $a_{ii}$ и радиусом $R_{i}$. Такой круг называется кругом Гершгорина.

Теорема. Каждое собственное значение матрицы $A$ лежит хотя бы в одном из кругов Гершгорина $D(a_{ii},R_{i})$.

Доказательство. Пусть $\lambda$ — собственное значение матрицы $A$ с соответствующим ему собственным вектором $x=(x_{j})$. Выберем такое $i$, что $x_{i}$ — координата с наибольшим по модулю значением среди всех координат вектора $x$. Так как $Ax=\lambda x$, для $i$-ой координаты этого равенства:

$\sum _{j}a_{ij}x_{j}=\lambda x_{i}.$

Переносим $a_{ii}$ в другую сторону:

$\sum _{j\neq i}a_{ij}x_{j}=(\lambda -a_{ii})x_{i}.$

Тогда, применяя неравенство треугольника и, вспоминая, что ${\frac {\left|x_{j}\right|}{\left|x_{i}\right|}}\leq 1$ из выбора $i$, получаем:

$\left|\lambda -a_{ii}\right|=\left|\sum _{j\neq i}{\frac {a_{ij}x_{j}}{x_{i}}}\right|\leq \sum _{j\neq i}\left|a_{ij}\right|=R_{i}.$

Следствие. Собственные значения матрицы $A$ также должны лежать в кругах Гершгорина $C_{j}$, соответствующих столбцам матрицы $A$.

Пример. Для диагональной матрицы, круги Гершгорина имеют нулевой радиус и совпадают со спектром. Обратное утверждение верно: если круги Гершгорина совпадают со спектром, то матрица диагональная.

Свойства

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

Теорема не утверждает, что каждому собственному значению соответствует один круг Гершгорина; каждый круг, скорее, соответствует оси в $\mathbb {C} ^{n}$, к которой ближе всего расположено собственное пространство каждого собственного значения. В матрице

${\begin{pmatrix}3&2&2\\1&1&0\\1&0&1\end{pmatrix}}{\begin{pmatrix}a&0&0\\0&b&0\\0&0&c\end{pmatrix}}{\begin{pmatrix}3&2&2\\1&1&0\\1&0&1\end{pmatrix}}^{-1}={\begin{pmatrix}-3a+2b+2c&6a-2b-4c&6a-4b-2c\\b-a&a+(a-b)&2(a-b)\\c-a&2(a-c)&a+(a-c)\end{pmatrix}}$

— которая по построению имеет собственные значения $a$, $b$, и $c$ с собственными векторами $\left({\begin{smallmatrix}3\\1\\1\end{smallmatrix}}\right)$, $\left({\begin{smallmatrix}2\\1\\0\end{smallmatrix}}\right)$, и $\left({\begin{smallmatrix}2\\0\\1\end{smallmatrix}}\right)$ — легко видеть, что круг для строки 2 покрывает $a$ и $b$, в то время как круг для строки 3 покрывает $a$ и $c$. Однако, это просто счастливое совпадение; при выполнении шагов доказательства обнаружится, что в каждом собственном векторе первая координата будет наибольшей (каждое собственное пространство ближе к первой оси, чем к любой другой оси), поэтому теорема только обещает, что круг для строки 1 (чей радиус может быть вдвое больше «суммы» двух других радиусов) покрывает все три собственных значения.

Вторая теорема Гершгорина

Если один из кругов не пересекается с другими, то он содержит только одно собственное значение. Однако, если он пересекается с другим кругом, возможно, он не содержит собственного значения (например, $A=\left({\begin{smallmatrix}0&1\\4&0\end{smallmatrix}}\right)$ или $A=\left({\begin{smallmatrix}1&-2\\1&-1\end{smallmatrix}}\right)$). В общем случае теорему можно усилить следующим образом:

Теорема: Если $k$ кругов образуют связную область, изолированную от остальных $n-k$ кругов, то первая область содержит ровно $k$, а вторая — $n-k$ собственных значений матрицы $A$.

Доказательство: Пусть $D$ — диагональная матрица с элементами, равными диагональным элементам матрицы $A$, и определим функцию переменной $t$ на отрезке $[0,1]$

$B(t)=(1-t)D+tA.$

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

Утверждение верно для $D=B(0)$. Диагональные элементы $B(t)$ равны таковым элементам в $A$, поэтому центры кругов Гершгорина совпадают, а их радиусы равны $tR_{i}$, где $R_{i}$ — радиус круга, соответствующий $i$-ой строке матрицы $A$. Так как $R_{i}\geq tR_{i}$ при $t\in [0,1]$, радиусы кругов для матрицы $B(t)$ меньше или равны радиусам для матрицы $A$. Таким образом, объединение областей, соответствующих $k$ кругам для $B(t)$, не пересекается с объединением остальных $n-k$ для любого $t\in [0,1]$. Круги замкнуты, поэтому расстояние между двумя связными областями для $A$ будет $d>0$. Такое расстояние для $B(t)$ — убывающая функция от $t$ (чем больше $t$, тем больше радиусы кругов, и, следовательно, меньше расстояние между связными областями), поэтому оно всегда не меньше $d$. Рассмотрим $\lambda (t)$ — непрерывное изменение по $t$ некоторого собственного числа матрицы $B(t)$. Для собственного значения $\lambda (t)$, лежащего в связной области $k$ кругов, его расстояние $d(t)$ до связной области остальных $n-k$ кругов также непрерывно (следует из непрерывности $\lambda (t)$). При $d(0)\geq d$, и предположим $\lambda (1)$ лежит в множестве $n-k$ кругов. Тогда $d(1)=0$, и, в силу непрерывности $d(t)$, существует $0<t_{0}<1$ такое, что $0<d(t_{0})<d$. Но это означает, что $\lambda (t_{0})$ лежит вне кругов Гершгорина, что невозможно. Следовательно, $\lambda (1)$ лежит в множестве $k$ кругов, и теорема доказана.

Применение

Круги Гершгорина применяются для решения матричного уравнения вида $Ax=b$ относительно $x$, где $b$ — вектор, а $A$ — матрица с большим числом обусловленности.

В задачах такого рода ошибка в конечном результате обычно такого же порядка величины, как и ошибка в исходных данных, умноженная на число обусловленности $A$. Например, если $b$ известно с точностью до шести знаков после запятой, а число обусловленности $A$ равно $1000$, то мы можем быть уверены только в том, что $x$ имеет точность до трех знаков после запятой. Чем больше число обусловленности, тем более неустойчив процесс решения системы.

Было бы хорошо уменьшить число обусловленности $A$. Это можно сделать с помощью предобуславливания. Рассматривается матрица $P$ такая, что $P\approx A^{-1}$, и уравнение $PAx=Pb$ решается относительно $x$. Использовать точную обратную к $A$ было бы неплохо, но нахождение обратной матрицы — это то, чего мы хотим избежать из-за вычислительных затрат.

Теперь, поскольку $PA\approx I$, где $I$ — единичная матрица, собственные значения $PA$ будут близки к $1$. По теореме Гершгорина, каждое собственное значение $PA$ находится в пределах известной области, поэтому мы можем приблизительно оценить, насколько хорош был выбор матрицы $P$ при помощи кругов Гершгорина.

Пример

Используем теорему, чтобы оценить собственные значения:

На этой диаграмме желтым цветом показаны круги, полученные для собственных значений. Первые два круга пересекаются, и их объединение содержит два собственных значения. Третий и четвертый круги не пересекаются с остальными и содержат по одному собственному значению.

$A={\begin{bmatrix}10&-1&0&1\\0.2&8&0.2&0.2\\1&1&2&1\\-1&-1&-1&-11\\\end{bmatrix}}.$

Начиная с первой строки, берем элемент по диагонали, $a_{ii}$ как центр круга. Затем мы берем оставшиеся элементы в строке и применяем формулу:

$\sum _{j\neq i}|a_{ij}|=R_{i}$

чтобы получить следующие четыре круга: $D(10,2),\;D(8,0.6),\;D(2,3),\;{\text{и}}\;D(-11,3).$

Заметим, что мы можем повысить точность двух последних кругов, применив формулу к соответствующим столбцам матрицы, получив $D(2,1.2)$ и $D(-11,2.2)$.

Собственные значения: $9.8218$, $8.1478$, $1.8995$, $-10.86$. Данная матрица с диагональным преобладанием: ${\textstyle |a_{ii}|>\sum _{j\neq i}|a_{ji}|}$. Это означает, что большая часть матрицы находится по диагонали, что объясняет, почему собственные значения расположены так близко к центрам кругов, а оценки очень хорошие. Для случайной матрицы ожидается, что собственные значения будут значительно дальше от центров кругов.

Литература

• Semyon Aranovich Gershgorin. Über die Abgrenzung der Eigenwerte einer Matrix. — 1931. — С. 749–754.
• Уилкинсон Дж. X. Алгебраическая проблема собственныx значений. — "Наука", 1970. — С. 565.
• В. В. Воеводин. Вычислительные основы линейной алгебры. — М.: Главная редакция физико-математической литературы изд-ва "Наука", 1977.
• Varga Richard S. Geršgorin and His Circles (англ.). — Berlin: Springer-Verlag, 2004. — ISBN 3-540-21100-4.(Errata)
• Varga Richard S. Matrix Iterative Analysis (1st ed.) (англ.). — Berlin: Springer-Verlag, 2002.
• Golub G. H., Charles F. Van Loan. Matrix Computations (англ.). — Baltimore: Johns Hopkins University Press, 1996. — P. 320. — ISBN 0-8018-5413-X.

Ссылки

• Eric W. Weisstein. «Gershgorin Circle Theorem.» From MathWorld—A Wolfram Web Resource.