Теорема Гершгорина об окружности

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

Заявление и доказательство

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

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 с наибольшим абсолютным значением равен $x_{i}$ . С $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$ исходя из того, как мы выбрали меня ,

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

Доказательство. Применить теорему к 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$ в то время как диск третьего ряда покрывает $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 , и пусть

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

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

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

Замечания: Необходимо считать собственные значения относительно их алгебраических кратностей. Вот противоположный пример:

Рассмотрим матрицу, ${\begin{bmatrix}5&1&0&0&0\\0&5&1&0&0\\0&0&5&0&0\\0&0&0&1&1\\0&0&0&0&1\end{bmatrix}}$

Объединение первых трех дисков не пересекает последние два, но матрица имеет только два собственных вектора e1,e4 и, следовательно, только два собственных значения, что свидетельствует о неверности теоремы в ее формулировке. Демонстрация показаний показывает лишь то, что собственные значения различны, однако любое утверждение о их количестве не подходит, и это контрпример.

Непрерывность $\lambda (t)$ следует понимать в смысле топологии . Достаточно показать, что корни (как точка пространства $\mathbb {C} ^{n}$ ) является непрерывной функцией своих коэффициентов. Обратите внимание, что обратное отображение, которое отображает корни в коэффициенты, описывается формулами Виеты (обратите внимание на характеристические многочлены, которые $a_{n}\equiv 1$ ), что можно доказать как открытое отображение . Это доказывает, что корни в целом являются непрерывной функцией своих коэффициентов. Поскольку композиция непрерывных функций снова непрерывна, $\lambda (t)$ как композиция решателя корней и $B(t)$ также является непрерывным.
Индивидуальное собственное значение $\lambda (t)$ могло сливаться с другими собственными значениями или возникать в результате разделения предыдущего собственного значения. Это может сбить людей с толку и поставить под сомнение концепцию непрерывности. Однако при рассмотрении из пространства множества собственных значений $\mathbb {C} ^{n}$ траектория по-прежнему представляет собой непрерывную кривую, хотя и не обязательно всюду гладкую.

Добавлено примечание:

Приведенное выше доказательство, возможно, (не)корректно... Существует два типа непрерывности собственных значений: (1) каждое отдельное собственное значение является обычной непрерывной функцией (такое представление существует на вещественном интервале, но может и не существовать). на комплексной области), (2) собственные значения в целом непрерывны в топологическом смысле (отображение матричного пространства с метрикой, индуцированной нормой, в неупорядоченные наборы, т. е. фактор-пространство C ^n при перестановочной эквивалентности с индуцированной метрика). Какая бы непрерывность ни использовалась при доказательстве теоремы Гершгорина о диске, следует обосновать, что сумма алгебраических кратностей собственных значений остается неизменной на каждой связной области. Доказательство с использованием принципа аргументации комплексного анализа не требует какой-либо непрерывности собственных значений. ^[1] Краткое обсуждение и пояснение см. ^[2]

Приложение

Теорема Гершгорина о окружности полезна при решении матричных уравнений вида Ax = b для x , где b — вектор, а A — матрица с большим числом обусловленности .

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

Было бы хорошо уменьшить число обусловленности A . Это можно сделать, предварительно обуславливая : Матрицу P такую, что P ≈ A ⁻¹ строится, а затем уравнение PAx = Pb решается относительно x . Было бы неплохо использовать точную обратную матрицу , но мы хотим избежать нахождения обратной матрицы из-за вычислительных затрат.

Теперь, поскольку PA ≈ 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{and}}\;D(-11,3).

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

Собственные значения: -10,870, 1,906, 10,046, 7,918. Обратите внимание, что это (столбец) диагонально-доминантная матрица : ${\textstyle |a_{ii}|>\sum _{j\neq i}|a_{ji}|}$ . Это означает, что большая часть матрицы находится по диагонали, что объясняет, почему собственные значения так близки к центрам окружностей, а оценки очень хорошие. Для случайной матрицы мы ожидаем, что собственные значения будут существенно дальше от центров кругов.

См. также

О матрицах с неотрицательными элементами см. теорему Перрона–Фробениуса .
Двойная стохастическая матрица
Матрица Гурвица
Джоэл Ли Бреннер
Матрица Метцлера
Неравенство Мюрхеда
Неравенство Бендиксона
Теорема Шура – Хорна

Ссылки

^ Роджер А. Хорн и Чарльз Р. Джонсон (2013), Матричный анализ , второе издание, Cambridge University Press ISBN 9780521548236 [ https://www.cambridge.org/ca/academic/subjects/mathematics/algebra/matrix-anaанализ-2nd-edition
^ Чи-Квонг Ли и Фучжэнь Чжан (2019), Непрерывность собственных значений и теорема Герсгорина , Электронный журнал линейной алгебры (ELA) {Том 35, стр. 619-625 | 2019} [DOI: https://doi.org/ 10.13001/ela.2019.5179 ]

Гершгорин С. (1931), "О разграничении собственных значений матрицы" , Изв. Академик Наук. СССР Странно. Физ.-Мат. Наук (на немецком языке), 6 : 749–754 .
Варга, Ричард С. (2004), Гершгорин и его круги , Берлин: Springer-Verlag, ISBN 3-540-21100-4 . ( Ошибки ).
Варга, Ричард С. (2002), Матричный итеративный анализ (2-е изд.), Springer-Verlag . 1-е изд., Прентис-Холл, 1962.
Голуб, GH ; Ван Лоан, К.Ф. (1996), Матричные вычисления , Балтимор: Издательство Университета Джонса Хопкинса, стр. 320, ИСБН 0-8018-5413-Х .

Внешние ссылки

«Теорема Гершгорина об окружности» . ПланетаМатематика .
Эрик В. Вайсштейн. « Теорема Гершгорина о круге ». Из MathWorld — веб-ресурса Wolfram.
Биография Семена Арановича Гершгорина на MacTutor

[1] Роджер А. Хорн и Чарльз Р. Джонсон (2013), Матричный анализ , второе издание, Cambridge University Press ISBN 9780521548236 [ https://www.cambridge.org/ca/academic/subjects/mathematics/algebra/matrix-anaанализ-2nd-edition

[2] Чи-Квонг Ли и Фучжэнь Чжан (2019), Непрерывность собственных значений и теорема Герсгорина , Электронный журнал линейной алгебры (ELA) {Том 35, стр. 619-625 | 2019} [DOI: https://doi.org/ 10.13001/ela.2019.5179 ]

[1]

[2]