Альпин Ю А_Неотрицательные матрицы. Неотрицательные матрицы
 Скачать 0.57 Mb.
|
|
собственный вектор? Задача 5. У положительной матрицы (даже второго порядка) могут быть непропорциональные собственные векторы. Найдите пример такой матрицы. Задача 6. Докажите, что для неразложимой матрицы A ∈ существуют только положительные собственные векторы. Задача 7. Пусть ρ(A) — спектральный радиус, σ(A) — контурная характеристика неразложимой матрицы A ≥ 0. Докажите, что) ≤ ρ(A). Глава Дополнения 1. Модуль комплексной матрицы. Лемма Виландта Модулем комплексной матрицы A называют неотрицательную матрицу |A|, полученную заменой элементов A на их модули. Теорема 1. Пусть A — неразложимая комплексная матрица. Тогда ρ(A) ≤ ρ(|A|). Для того, чтобы имело место равенство) = ρ(|A|), необходимо и достаточно, чтобы матрица A имела представление A = εD|A|D −1 , |ε| = 1, |D| = Доказательство. Пусть Az = λz„ следовательно ≥ Для простоты письма будем считать, что ρ(|A|) = 1. Последствию (с) существует левый неподвижный вектор y T > 0, y T |A| = Умножив неравенство (2) на этот вектор, после очевидных преобразований получим 1 ≥ Второе утверждение теоремы в части достаточности очевидно если для A имеется представление (6), то спектр A отличается от спектра матрицы |A| лишь множителем ε, не изменяющим спектральный радиус. Теперь предположим, что ρ(A) = ρ(|A|) = 1, следовательно, спектр A содержит число ε, |ε| = 1. Пусть Az = εz. Отсюда ≤ Согласно лемме 1 (сна самом деле имеем = |A||z|, |z| > Вектор z можно записать в виде z = D|z|, |D| = E. Тогда = εD|z| = AD|z| =⇒ |z| = ε −1 D −1 AD|z| = Последнее равенство возможно лишь если = |A|, то есть, когда выполняются условия (6). Доказательство вытекает из следующего свойства комплексных чисел+ . . . + z n = |z 1 | + . . . + |z n | ⇒ z 1 = |z 1 |, . . . , z n = |z n |. Соединяя теоремы 1 и 2 (с) получаем утверждение, известное как лемма Виландта: Следствие 1. Пусть для комплексной матрицы A и неразложимой матрицы P ≥ 0 выполнено условие ≤ Тогда ρ(A) ≤ ρ(P ). Равенство ρ(A) = ρ(P ) имеет место тогда и только тогда, когда = εDP D −1 |ε| = 1, |D| = E. (6) § 2. Локализация спектра матрицы Пусть теперь A — комплексная матрица. Положим, что σ(A) = σ(|A|). Комплексную матрицу A будем называть унистрочной, если — унистрочная матрица. Экстремальными в графе A будем считать те вершины, которые экстремальны в графе |A|. Тогда из теоремы на стр. 46 немедленно следует Теорема 1. Для комплексной матрицы A, в графе которой достижимы экстремальные вершины, существуют унистрочная матрица A и положительная диагональная матрица D, такие, что = Действительно, достаточно построить матрицу D для |A| ≥ 0 и применить её к A, чтобы получить равенство (1). Приведём пример использования уравновешивания для локализации собственных значений матрицы. Пусть A = (a ij ) — комплексная матрица порядка n. Известная теорема Гершгорина гласит: Теорема 2. Любое собственное значение λ матрицы A удовлетворяет хотя бы одному из неравенств λ| ≤ n X j=1,j6=i |a ij |, i = 1, . . . , n. (2) § 3. Норма матрицы 53 Таким образом, все собственные значения матрицы A лежат в объединении кругов на комплексной плоскости, центры которых диагональные элементы A, а радиусы — строчные суммы модулей недиагональных элементов. Пусть m i — количество ненулевых недиагональных элементов й строки матрицы A. Обозначим через матрицу, полученную из A заменой диагональных элементов нулями. Из теорем 1 и 2 вытекает Теорема 3. Пусть в графе комплексной матрицы A достижимы экстремальные вершины. Тогда все собственные значения матрицы A лежат в объединении кругов λ| ≤ m i σ(A 0 ), i = 1, . . . , Радиусы кругов, описываемых неравенствами (3), могут быть намного меньше, чем кругов, отвечающих неравенствам (Применим теорему 3 для локализации корней многочлена+ a 1 x n−1 + . . . + a n−1 x + Составим сопровождающую матрицу многочлена (4): −a 1 1 0 . . . 0 −a 2 0 1 . . . 0 · · · · · −a n−1 0 0 . . . 1 −a n 0 0 . . . Спектр этой матрицы совпадает с совокупностью корней многочлена. Следствие 1. Корни многочлена (4) лежат в объединении трёх кругов) |a 1 − λ| ≤ max 2≤i≤n i p |a i |, 2) |λ| ≤ 2 max 2≤i≤n−1 i p |a i |, 3) |λ| ≤ max 2≤i≤n i p |a i |. § 3. Норма матрицы Функция k · k с вещественными значениями, определённая на (необязательно квадратных) комплексных матрицах, называется матричной нормой, если она удовлетворяет следующим аксиомами для любого комплексного числа c; 3) kA + Bk ≤ kAk + kBk; 4) kABk ≤ В последних аксиомах предполагается, что A и B — комплексные матрицы, которые можно сложить (перемножить). Из свойства 4) для квадратных матриц легко выводится неравенство. Лемма 1. Пусть A квадратная комплексная матрица и λ — её собственное значение. При любой матричной норме |λ| ≤ Действительно, для некоторого столбца x 6= 0 имеем Ax = Используя аксиомы 1), 2) и 4), получаем = kAxk ≤ kAkkxk ⇒ |λ| ≤ Мы пользуемся обычно строчной нормой, которая на (m × n)- матрице A = (a ij ) равна Доказательство того, что функция (2) удовлетворяет аксиомам 1) – 4), представляет собой несложное упражнение. Следующее утверждение является частным случаем формулы Гельфанда для спектрального радиуса. Предложение 1. ρ(A) = Доказательство. Из соотношений (ρ(A)) k = ρ(A k ) ≤ вытекает неравенство ρ(A) ≤ для всех k = 1, 2, . . .. При любом спектральный радиус матрицы e A = (ρ(A) + ε) −1 A меньше единицы. Значит, e A k → 0 при k → ∞. Следовательно, существует номер N , такой, что || e A k || ∞ < 1 при всех k ≥ N . Это означает, что ||A k || ∞ < (ρ(A) + при всех k ≥ N или, эквивалентно ρ(A) + ε при всех k ≥ N. Итак, при любом ε > 0 и всех достаточно больших k выполняются неравенства) ≤ ||A k || 1/k ∞ ≤ ρ(A) + что и доказывает наше утверждение. ¤ § 3. Норма матрицы 55 О сходимости матричных рядов Из неравенств (1) с очевидностью следует Лемма 2. Если ||A|| < 1, то A k → 0 при k → Напомним, что спектральный радиус ρ(A) комплексной матрицы равен максимальному из модулей её собственных значений. Теорема 1. lim k→∞ A k = 0 ⇐⇒ ρ(A) < Доказательство. Известно, что любая комплексная матрица подобна верхней треугольной матрице. При переходе к подобной матрице сохраняется спектр и свойство сходимости степеней матрицы к нулевой матрице. Поэтому достаточно доказать утверждение теоремы для случая, когда A — верхняя треугольная матрица. Пусть 0, тогда степени диагональных элементов — собственных значений, сходятся к нулю. Значит, они меньше единицы по модулю и) < Обратно, пусть ρ(A) < 1. Положим D = diag(d, d 2 , ..., d n ), тогда = λ 1 a 12 d . . . a 1n d n−1 0 λ 2 . . . a 2n d n−2 · · · · · · 0 0 . . . a n−1,n d 0 0 . . За счёт выбора d можно сделать модули недиагональных элементов матрицы D −1 AD настолько малыми, чтобы выполнялось неравенство. По лемме 2 тогда D −1 A k D → 0, следовательно 0 при k → ∞. Применим теорему 1 для обобщения леммы Следствие 1. Если ||A m || < 1 для некоторого показателя то A k → 0 при k → Доказательство 1. Осталось применить теорему 1. Лемма 3. Пусть A k → 0 при k → ∞, или, равносильно, ρ(A) < 1. Тогда матрица E − A имеет обратную, причём (E − A) −1 = lim k→∞ (E + A + . . . Доказательство. По теореме 1 единица не является собственным значением матрицы A, следовательно, матрица E − A обратима. Имеет место тождество + A + . . . A k )(E − A) = E − Умножим обе его части на (E − A) −1 : E + A + . . . A k = (E − A k )(E − При k → ∞ в пределе получается равенство (3). Если матрица A ≥ 0, то, разумеется, и (E − A) −1 ≥ Лемма 4. Если Q k → 0 при k → ∞, то блочно треугольные матрицы µ E R 0 Q ¶ k = µ E R k 0 сходятся к матрице R(E − Q) −1 Доказательство следует из равенства R 0 Q ¶ k = µ E R(E + Q + . . . которое доказывается индукцией пои леммы 3. Аналогично, для матрицы вида 0 R из Q k → 0 следует, что µ E 0 R Q ¶ k = µ E 0 R k Q k ¶ → µ E 0 (E − Q) −1 R 0 ¶ . Предметный указатель подграф, порождённый множеством вершин — замкнутый подграф — 7 факторграф — 8 факторграф, соответствующий подграфу — примитивный граф — ациклическая вершина — тупиковая вершина — переставляющая матрица (матрица перестановки) — фокус графа — матрица полупримитивная — 14 полупримитивный граф — совместимые вершины — матрица импримитивная — циклическое разбиение множества вершин графа — темпоральная подматрица — индекс совместимости графа — индекс совместимости матрицы — контурный индекс сильно связного графа — контурный индекс неразложимой матрицы — индекс импримитивности сильно связного графа — индекс импримитивности неразложимой матрицы — перронов корень неотрицательной матрицы — доминирующее собственное значение — возвратная вершина — 39 беступиковый граф — финальная компонента графа — 39 унистрочная матрица — положительная диагональная матрица — модуль комплексной матрицы — 51 Литература 1. Minс H., Nonnegative Matrices. – Wiley, 1988. 2. Seneta E., Non-negative Matrices and Markov Chaines. – Springer, 2006. 3. Гантмахер ФР, Теория матриц. – М Наука, 1967. 4. Хорн Р, Джонсон Ч, Матричный анализ. — М Мир, Сачков В.Н., Тараканов В.Е., Комбинаторика неотрицательных матриц. – М ТВП, Романовский В. И, Дискретные цепи Маркова. – М Гостехиздат, 1949. 7. Артамонов В.А., Латышев В.Н. Линейная алгебра и выпуклая геометрия. – М Факториал Пресс, 2004. 8. Карчевский ЕМ, Карчевский ММ. Лекции по линейной алгебре и аналитической геометрии. – Казань Изд-во Казан. унта, 2014. 9. Альпин Ю.А., Ильин С.Н., Дискретная математика графы и автоматы. – Казань Изд-во Казан. унта, 2007. 10. Альпин Ю. А, Альпина В. С. Теорема Перрона – Фробениуса: доказательство с помощью цепей Маркова. – Зап. научн. семин. ПОМИ – 2008 – 359, С. 5-16. 11. Кривулин Н. К. Методы идемпотентной алгебры в задачах модлирования и анализа сложных систем. — СПб.: Изд-во С.- Петерб. унта, 2009. 12. Butkovich P. Max-linear systems: theory and algorithms – Springer, 2010. |