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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}.}$

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle B(t)=(1-t)D+tA.}$

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

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

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

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

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

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

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

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

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

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

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

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

Собственные значения: ${\displaystyle 9.8218}$, ${\displaystyle 8.1478}$, ${\displaystyle 1.8995}$, ${\displaystyle -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.