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

Круги Гершгорина — набір кругів на комплексній площині, які локалізують власні значення матриці. Потребують набагато меньше обчислень, ніж обчислення самих власних значень. Вперше були описані в 1931 році Семеном Аноновичем Гершгориним.

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

Нехай $A$ — комплексна матриця розміру $n\times n$ з елементами $a_{ij}$ , позначимо через $R_{i}$ суму абсолютних значень недіагональных елементів $i$ -го рядка (де $1\leq i\leq 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$ .

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

Властивості

Перетворюючи матрицю, щоб зменшити суму норм недіагональних елементів можна отримати більш точні оцінки власних значень матриці. Діагональні елементи в процесі перетворення можуть змінюватись.
Теорема не стверджує, що кожному власному значенню відповідає один круг Гершгорина. В матриці

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

Посилена теорема Гершгорина

Теорема: Якщо $k$ кругів утворюють зв'язну область, ізольовану від інших $n-k$ кругів, то ця область містить точно $k$ , а друга — $n-k$ власних значень матриці $A$ .