Дж. Деммель - Вычислительная линейная алгебра, страница 48

В результате, правое выражение для сг2 также упрощается и принимает вид а2 — — шах,аа р(з, А). Аналогичным образом можно показать, что для наименьшего собственного значения теорема упрощается до формулы сг„= ш!п„ао р(т, А). О Доказательство минимаксной теоремы Куранта — Фишера. Возьмем произ- вольные надпространства Кз и Я" 1+2 указанных в формулировке теоремы размерностей.

Поскольку сумма их размерностей у + (и — у+ 1) = п+ 1 больше, чем и, найдется ненулевой вектор хнз Е Вд Г! Я" дт'. Таким образом, ппп р(Г,А) < р(хнв,А) < тах р(з,А). Ои~ ЕН2 Офгев" г и Таким образом, р(и, А) есть взвешенное среднее собственных значений матрицы А.

Наибольшее значение шах„,-го р(и, А) достигается для и = о2 (С = ег) и равно р(дм А) = оы Наименьшее значение ш!п„ао р(и, А) реализуется вектором и = !!„(с = е„) и равно р(да, А) = сг„. Вместе эти результаты означают, что 211 5.2. Теория возмущений Выберем теперь Йу так, чтобы выражение слева принимало наибольшее значение, и В»» 1+1 так, чтобы выражение справа было минимальным. Тогда 1пах ппп р(т, А) = ппп р(т, А) (5.3) К»' ОФ»ЕК' ОВ«»ЕК» < р(х--,А) < 1пах р(е, А) От«ЕБ" 1»» ппп 1пах р(е, А). Б — »е»» ОЯвЕБ»+» Убедимся теперь, что неравенства в этих выкладках в действительности являются равенствами. С этой целью укажем конкретные подпространства Вв и В" '+1, для которых нижняя граница совпадает с верхней.

Вначале положим ВУ = Крап(»11,..., ц). Тогда имеем 1пах ппп р(т, А) > ппп р(т, А) К»' О~»ЕК» О~»ЕК» ппп р(т, А) От»=Я,Е. Кдв Едй, 4Ъ ппп 2 1' не все б равны 0 2 „1<1 С1 — я — » -~-1 Теперь возьмем Я = Врал(дд,...,О„). Имеем ппп 1пах р(е, А) Б" »+» ОФ«ЕБ" »е»» < шах р(е, А) О~»ЕБ 1пах р(е, А) От«=Т:,», бд, ь«2 „ шах 2 1 не все 6 равны 0 2 с»уьд Итак, «2 одновременно и меньше, и больше обеих границ, которые поэтому совпадают друг с другом и с сд,. П Пример 5.3.

Рис. 5.1 иллюстрирует теорему для случая 3 х 3-матриц. Поскольку р(иДиЙ2, А) = р(и, А), то можно интерпретировать р(и, А) как функцию, заданную на единичной сфере 5иЙ2 = 1. На рис. 5.1 показаны линии уровня этой функции для матрицы А = »11аб(1,.25, 0). Для этой простой матрицы имеем О1 = е;, где ед есть 2-й столбец единичной матрицы. Картина линий уровня симметрична относительно начала координат в силу свойства р(и, А) = р( — и, А).

Малые пунктирные окружности вблизи ~»11 опоясывают точки глобального максимума (р(~»11, А) = 1), а малые сплошные окружности вблизи ~»12 — точки глобального минимума (р(хдз, А) = 0). Две большие окружности составляют линию уровня р(и, А) = .25, соответствующую среднему собственному значению. Внутри двух узких «ломтей», определяемых большими кругами, имеем р(и,А) < .25, а внутри широких ломтей выполняется неравенство р(и, А) > .25. 212 Глава 5.

Симметричная проблема собственных значений Непрозрачная сфера Прозрачная сфера 0.5 0.5 ш е 0 з н -0.5 ш о 0 -0.5 — 1 — 1 -1 -1 у=е 2 х=е 1 у=е 2 х=е 1 Рис. 5.1. Линии уровня отношения Рзлея на единичной сфере. Дадим интерпретацию минимаксной теоремы с помощью этого рисунка. Выбор подпространства В.з равносилен выбору болыпой окружности С: каждая точка С принадлежит соответствующему подпространству Рсз и все Вз состоит из векторов, пропорциональных векторам из С. Таким образом, ш1пом -еи р(т, А) = ппп„ес р(т, А). При вычислении ппп,ес р(т, А) нужно рассматривать четыре случая: 1.

С не проходит через точки пересечения ~уз двух больших окружностей на рис. 5.1. Ясно, что в этом случае С должна пересекать и узкий ломоть, и широкий; следовательно, ппп„ес р(т, А) <,25. 2. С проходит через точки пересечения шдз, а в остальном находится внутри узких ломтей. Тогда ппп„ес р(т, А) < .25. 3. С проходит через точки пересечения шдз, а в остальном находится внутри широких ломтей.

В таком случае ппп„ес р/т, А) = .25, и этот минимум достигается для т = х:чз. 4. С совпадает с одной из двух больших окружностей. Тогда р(г, А) = .25 для всех т 5 С. Согласно минимаксиой теореме, аз —— .25 есть максимум функции пзш„ес р(т, А) относительно всех выборов большой окружности С. Этот максимум достигается в случаях 3 и 4.

Если, в частности, С делит широкий ломоть пополам (случай 3), то получаем Кз = Врап(дз, дз). Программы для вычерчивания линий уровня типа линий на рис. 5.1, но для случая произвольной симметричной 3 х 3 матрицы, можно найти на НОМЕРАОЕ/Ма11аЬ/Нау1е15ЬСопсопг.ш. 0 5.2. Теория воэмуосвний 213 Мы можем теперь приступить к доказательству теоремы Вейля: и~(А+ Е)и ссэ ш'сс шах . т по минимаксной теореме е"-с+' обвея"-~+с и~и итАи итЕи ппп шах (,„+ в" '+'акоев" сл' 'с, и и и и сси~ Аи < ппп шах ~~, + ОЕОг согласно (5.2) я"-с+'оФьев-- "' и сс = ос + ОЕОг снова использУЯ минимакснУю теоРемУ. Меняя А и А + Е ролями, получим неравенство ад < ссс + ЙЕОг.

Вместе эти два неравенства доказывают теорему Вейля. С минимаксной теоремой Куранта — Фишера тесно связана теорема Сильвестра об инерции. Она понадобится нам в равд. 5.3А для обоснования алгоритма бисекции. Определение 5.2. Инерцией симметричной матрицьс А называется тройка целых чисел 1пегйаА = (о,с„к), где о, с", и к суть соответственно число отрицательных, нулевых и положительных собственных значений этой матрицьь Если Х вЂ” ортогональная матрица, то матрицы ХгАХ и А подобны, а потому имеют одни и те же собственные значения.

Если относительно Х предполагается только невырожденность, то матрицы ХТАХ и А называют конгруэнтнъми. В этом случае собственные значения матриц Хс АХ и А, вообще говоря, различны. Однако, как показывает следующая теорема, оба множества собственных значений имеют, по крайней мере, одни и те же знаки. Теорема 5.3 (теорема Сильвестра об инерции). Пусть А симметричная, а Х невырожденная матрицы. Тогда матрицы А и ХгАХ имеют одну и ту же инерцию. Доказательство.

Пусть п — порядок матрицы А. Предположим, что А имеет и отрицательных собственных значений, а аналогичное число о',:~ся ХТАХ меньше, чем и. Мы покажем, что это невозможно, приведя данное предположениек противоречию. Пусть 1ч1 обозначает о-мерное отрицательное собственное подпространство матрицы А, т. е. надпространство, натянутое на собственные векторы для о отрицательных собственных значений.

Это значит, что хгАх < О для всякого ненулевого вектора х Е 1Ч1. Пусть Р— неотрицательное собственное подпространство размерности и — о' матрицы ХгАХ; имеем хгХТАХх > О для всякого ненулевого вектора х Е Р. Поскольку Х вЂ” невы- рожденная матрица, подпространство ХР также имеет размерность п — и'. Из соотношений с)1ш1с1ч1) + с1нп1ХР) = и + и — ос > п следует, что в пересечении надпространств 1ь1и ХР должен содержаться ненулевой вектор х. Но тогда О > хс Ах, поскольку х Е 1ч1, и О < хтАх, поскольку х Е ХР.

Это противоречие доказывает, что и < и'. Меняя матрицы А и ХТАХ ролями, получим неравенство и' < о. Таким образом, А и ХТАХ имеют одинаковое число отрицательных собственных значений. Аналогичное рассуждение показывает, что обе матрицы имеют одно и то же число положительных собственных значений. 214 Глава 5.

Симметричиан проблема собственных значений Теперь мы исследуем, насколько могут измениться собственные векторы при переходе от матрицы А к возмущенной матрице А+ Е. Чтобы сформулировать оценку, нам потребуется понятие отделенности собственного значения. Определение 5.3. Пусть ат » тт„— собственные значения матарицы А. Отделенностью собственного значения ен назътвается число бар[7', А) = ппп чы ~стд — ст,[. Если матрица А известана из контекста, будем писать просто бар [т).

Наш основной результат состоит в том, что чувствительность собственного вектора зависит от отделенности соответствующего собственного значения: если отделенность мала, то собственный вектор чувствителен. Пример5.4.ПустьА= ~ ~ иА+Е=[ ],гдеО<е< [1+д 1 1+у е 1 д. Тогда кар[7,А) = д кар[т,А+ Е) для 1 = 1,2. Собственные векторы матрицы А — это дт — — ет и дг — — ег. Несложное вычисление показывает, что собственные векторы матрицы А + Е имеют вид 1 -,/1+ (ф)' дт=д. дг=д' -Ь гт У где д — 1/2 — нормирующий множитель. Мы видим, что, в первом приближении по е, угол между исходными векторами д; и возмущенными векторами дг равен е/д. Итак, угол обратно пропорционален отделенности д.