Теорема Гершгорина о круге - Gershgorin circle theorem

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

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

Позволять ${ displaystyle A}$ быть сложный ${ Displaystyle п раз п}$ матрица с записями ${ displaystyle a_ {ij}}$ . За ${ Displaystyle я в {1, точки, п }}$ позволять ${ displaystyle R_ {i} = sum _ {j neq {i}} left | a_ {ij} right |}$ быть суммой абсолютные значения недиагональных элементов в ${ displaystyle i}$ -бросать. Позволять ${ Displaystyle D (а_ {II}, R_ {я}) substeq mathbb {C}}$ быть закрытым диск сосредоточен на ${ displaystyle a_ {ii}}$ с радиусом ${ displaystyle R_ {i}}$ . Такой диск называется Диск Гершгорина.

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

Доказательство: Позволять ${ displaystyle lambda}$ быть собственным значением ${ displaystyle A}$ . Выберите соответствующий собственный вектор ${ displaystyle x = (x_ {j})}$ так что один компонент ${ displaystyle x_ {i}}$ равно ${ displaystyle 1}$ а остальные имеют абсолютное значение меньше или равны ${ displaystyle 1}$ : ${ displaystyle x_ {i} = 1}$ и ${ displaystyle | x_ {j} | leq 1}$ за ${ displaystyle j neq i}$ . Всегда есть такой ${ displaystyle x}$ , который может быть получен простым делением любого собственного вектора на его компонент с наибольшим модулем. С ${ displaystyle Ax = lambda x}$ , особенно

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

Итак, разделив сумму и еще раз учитывая, что ${ displaystyle x_ {i} = 1}$ , мы получили

{ displaystyle sum _ {j neq i} a_ {ij} x_ {j} + a_ {ii} = lambda.}

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

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

Следствие: Собственные значения А также должен лежать внутри дисков Гершгорина C_j соответствующие столбцам А.

Доказательство: Примените теорему к А^Т.

Пример Для диагональная матрица, диски Гершгорина совпадают со спектром. Наоборот, если диски Гершгорина совпадают со спектром, матрица диагональна.

Обсуждение

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

Теорема делает нет утверждают, что для каждого собственного значения существует один диск; во всяком случае, диски скорее соответствуют топоры в ${ 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 + (ab) & 2 (ab) c-a & 2 (ac) & a + (ac) 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 (радиус которого может быть вдвое больше сумма двух других радиусов) покрывает все три собственных значения.

Усиление теоремы

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

Теорема: Если объединение k диски не пересекаются с объединением других п − k дисков, то первое объединение содержит ровно k и последний п − k собственные значения А.

Доказательство: Позволять D - диагональная матрица, элементы которой равны диагональным элементам матрицы А и разреши

{ Displaystyle B (t) = (1-t) D + tA.}

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

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

Примечания:

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

Индивидуальное собственное значение ${ displaystyle lambda (t)}$ может сливаться с другими собственными значениями или возникать в результате разделения предыдущего собственного значения. Это может сбить с толку людей и поставить под сомнение концепцию непрерывности. Однако при просмотре из пространства множества собственных значений ${ displaystyle mathbb {C} ^ {n}}$ , траектория по-прежнему является непрерывной кривой, хотя и не обязательно везде гладкой.

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

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

Заявление

Теорема Гершгорина о круге полезна при решении матричных уравнений вида Топор = б за Икс куда б вектор и А матрица с большим номер условия.

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

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

Теперь, поскольку PA ≈ я куда я - единичная матрица, собственные значения из PA все должны быть близки к 1. По теореме Гершгорина о круге каждое собственное значение PA находится в пределах известной области, поэтому мы можем приблизительно оценить, насколько хорошо мы выбрали п был.

Пример

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

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

{ 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}}.}

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

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

чтобы получить следующие четыре диска:

{ Displaystyle D (10,2), ; D (8,0.6), ; D (2,3), ; { text {and}} ; D (-11,3).}

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

Собственные значения: 9,8218, 8,1478, 1,8995, -10,86. Обратите внимание, что это (столбец) диагонально доминирующая матрица: ${ displaystyle | a_ {ii} |> sum _ {j neq i} | a_ {ji} |}$ . Это означает, что большая часть матрицы расположена по диагонали, что объясняет, почему собственные значения так близки к центрам кругов, а оценки очень хорошие. Для случайной матрицы мы ожидаем, что собственные значения будут значительно дальше от центров окружностей.

Смотрите также

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

внешняя ссылка

"Теорема Гершгорина о круге". PlanetMath.
Эрик В. Вайсштейн. "Теорема Гершгорина о круге. »Из MathWorld - веб-ресурса Wolfram.
Семен Аранович Гершгорин биография на MacTutor

[1] Роджер А. Хорн и Чарльз Р. Джонсон (2013), Матричный анализ, второе издание, Издательство Кембриджского университета ISBN 9780521548236 [https://www.cambridge.org/ca/academic/subjects/mat Mathematics/algebra/matrix-analysis-2nd-edition

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

[1]

[2]