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

Тогда матрица Т(Ь) = Ят(й)Т(0)Ц(й) является решением уравнения (Б.йЦ. Мы докажем эту теорему несколько позже. Оказывается, что при подходящем выборе функции Е получается решение дифференциального уравнения, 5.5. Дифференциальные уравнения и задачи на собственные значения 271 (П=Т Т(2) = Т2 Доказательство следств л.

При ( = 1 имеем е'1'гт' = То —— Я(1)В(1), т.е. ((Я-разложение матрицы То. Отсюда Т(1) = Я~(1)То(г(1) = В(1)сг(1) = Ты как и требуется. Поскольку решение задачи Коши единственно, зто рассуждение модно распространить на ббльшие значения (, что дает Т(() = Ть П На рисунке следствие проиллюстрировано графически. Кривая представляет решение дифференциального уравнения, а точки — значения решения Т(() в целочисленные моменты времени ( = 0,1,2.... Указано, что Т(() равны ((тьитерациям Т;.

Доказательство гпеоремы 8.18. Дифференцируя равенство егге = (зВ, полу- чаем (~В+()В В граВ-1 дВВ-1 (зтВ греВ-1 (1 го((1В) — ЯВ потому что е ' = (дВ (зтг (Т(0))(ьЗ вЂ” ЯВ 1 потому что Ро = Е(Т(0)) Е ( ( с т Т ( 0 ) ь г ) В В 1 Р(Т) — ВВ-'. В гро или или г Отметим, что поскольку (2и-разложение ие вполне единственно ((2 можно заменить матрицей ОЯ, а й — матрицей Яй, где Я вЂ” диагоивльнал матрица с диагональными элементами ж1), то T, и ТОО могут в действительности различаться подобием вида Тг = ЯТООЯ Длл простоты, мы предположим, что и здесгч и в следствии бя, Я выбрана так, чтобы T; = Т((). значения которого совпадают с матрицами, вычисляемыми ((гь-итерацией (ал- горитм 4.4).

Определение 5.6. Выбор Г(х) = 1оях в (8.88) даегп дифференциальное урав- нение, называемое ОВ;потоком. Следствие 5.3. Пусть Р(х) = 1оях. Предполож м, что матрица Т(0) по- лоэкительно определепц тогда матрица 1ояТ(0) вещественна.

Пусть То = Т(0) = (гВ, Т1 = В(в, и т. д. есть последовательносгпь матриц, генерируе- мая (гВ-итерацией без сдвигов. Тогда Т(() = Т;. Таким образом, (гВ-олгоригпм дает значения решен л (ЗВ-потока в целочисленные моменты времени (1. 272 Глава 5. Симметричная проблема собственных значений Из соотношения 1 = Ят«Л выводим, что 0 = з««г Я = Я «г + Я «е' ят«г)т + ят«г). Это означает что матрица чтя кососимметрична, поэтому ко% г) = гт г = ко(Р(Т) — г»11 ~). Присутствие в аргументе верхней треугольной матрицы ВВ ' не изменяет значения функции ко, поэтому окончательно находим ЯтЯ = ко(Е(Т)). Теперь имеем — Т($) = — ьг [Ф) Т [0) 9(1) = Я~Т(ОЯ+ Я~Т(0)Я = бЛ~ЯС3~)Т(0)Я+СЗ~Т[0)ЩГЛ Я = Я~ЯТЯ+ Т(г)Ц~Я вЂ” чтит[1) + Тяптя = — о[Р'[Т[~)))Т[~) + Т[4) о[Р'[Т[~))), что и требовалось.

Следующее следствие объясняет наблюдение, сделанное в вопросе 4.15, где ЯГ«-итерацию удалось «обратить вспять» и вернуться к исходной матрице. См. по этому поводу также вопрос 5.25. Следствие 5.4. Предположим, что матрица Т«получена из положительно определенной матрицы То посредством следующих операций: 1. СТо выполняются т шагов»гЯ-алгоритма без сдвигов, что дает матрицу Т,. 2. Полагаем Тг = «отраженная матрица Т1 ~ — — ЛТ1Л, где,1 получается из единичной матрицы обращением порядка столбцов. 3. С Тг выполняются т шагов ЯЯ-алгоритма без сдвигов, что дает матрицу Т,. 4. Полагаел«Т« = ЛТ»Л. Тогда Т« = Та.

Доказательство. Легко проверить, что если Х = Хт, то ко[,1ХЛ) — Лко(Х)Л. Отсюда следует, что матрица Тз(г) = ЛТЯЛ удовлетворяет уравнению Н Н вЂ” Тз(1) = Л вЂ” Т[г)Л а» дг = Л[ — ко(Р(Т))Т+ Тко[Р(Т)))Л = — Лко[г'(Т))Л[ЛТЛ) + [ЛТЛ)Лко(г" (Т))Л, так как Л~ = 1, = хо (ЛР (Т).Г) Тз — Тгко [ЛР(Т) Л) = ко(Р(ЛТЛ))Т, — Твко[У(ЛТЛ)) = ко(Р(Тз))Тз — Тзко[Е[Тз)). Это почти такое же уравнение, как для Т(4). В действительности, это в точности то уравнение, которому удовлетворяет функция Т[ — г): Н Н вЂ” Т(-1) = — — Т[, = -[-,(Р'(Т))т+ Т о(Г[Т))]-,. ах «М Поэтому при одном и том же начальном условии Тг матрицы ТзЯ и Т[ — 4) должны совпадать всюду.

При интегрировании по промежутку длины т реше- 273 5.6. Литература и смежные вопросы к главе 5 ние Т( — 1) возвращается из состояния Тэ —— УТ1 У в начальное состояние 3Те1. Следовательно, Тэ —— ,УТе,У и Т4 = ЛТэЛ = Те, что и требовалось. П 5.5.2. Связь с дифференциальными уравнениями в частных производных Этот раздел можно опустить при первом чтении книги.

Пуст~ Т(1) = — йэт+д(х,1) и ВЯ = — 43эт+3(д(х,1)Д+ ~э 9(х,1)). И Т(1), и В(1) суть линейные операторы (т.е. обобщения матриц), действующие в функциональных пространствах. Подставляя Т(1) в уравнение» = ВТ вЂ” ТВ, получаем д» вЂ” — 699, — д„, (5.29) при условии, что для д выбраны подходящие граничные условия, (В должен быть кососимметричным оператором, а Т вЂ” симметричным.) Уравнение (5.29) называется уравнением Корглееега — де Фриза и описывает течение воды в мелком канале.

Можно строго показать, что это уравнение сохраняет при всех 1 собственные значения оператора ТЯ, т. е. обыкновенное дифференциальное уравнение с акэ — — + д(х,1) Й(х) = ЛЬ(х) дх2 имеет при всех 1 одно и то же бесконечное множество собственных значений Лм Лш.... Иначе говоря, существует бесконечная последовательность величин, родственных энергии, которые сохраняются уравнением Кортевега — де Фриза. Это важно и с теоретической точки зрения, и с вычислительной.

Более подробно о потоке Тода можно прочитать в [144, 170, 67, 68, 239], а также в статьях Крускала [166], Флашки [106] и Мозера [187] в сборнике [188]. 5.6. Литература и смежные вопросы к главе 5 Прекрасным справочником по симметричной проблеме собственных значений является книга [197]. Изложение теории относительных возмущений можно найти в [75, 82, 101]; раздел 5.2.1 был основан на последней из этих публикаций. Родственный материал содержится в [66, 92, 228, 250].

Книга [161] — это классический учебник теории возмущений для линейных операторов общего вида. Обзор параллельных алгоритмов для симметричной проблемы собственных значений дан в [76]. б)Б.-алгоритм в приложении к вычислению БУР двух- диагональных матриц обсуждается в [80, 67, 120], а алгоритм 6«16э — в [104, 200, 209]. Анализ ошибок метода бисекции проведен в [73, 74, 156]; отметим, что в последнее время метод пытаются ускорить (см. [105, 203, 201, 176, 173, 175, 269]). Современные исследования по усовершенствованию обратной итерации представлены работами [105, 83, 201, 203]. Алгоритм «разделяй-и-властвуй» для задач на собственные значения был впервые предложен в [59], а затем развивался в работах [13, 90, 127, 131, 153, 172, 210, 234]. Возможность вычисления собственных значений с высокой точностью с помощью метода Якоби разрабатывается в [66, 75, 82, 92, 183, 228]. Поток Тода и сходные феномены обсуждаются в [67, 68, 106, 144, 166, 170, 187, 188, 239].

274 Глава 5. Симметричная проблема собственных значений 5.7. Вопросы к главе о Вопрос 5.1 (легкий, Х Ва1). Показать, что матрица А = В+1С тогда и только тогда является эрмитовой, когда матрица С В симметрична. Выразить собственные значения и собственные векторы матри- цы М через собственные значения и собственные векторы матрицы А. Вопрос 5.2 (средней трудности), Доказать следствие 5.1, используя теорему Вейля (т. е. теорему 5.1) и утверждение 4 теоремы 3.3. Вопрос 5.3 (средней трудности). Исследовать картину линий уровня для произвольной 3 х 3-матрицы А с собственными значениями аз < аз < а1, аналогичную рис. 5.1. Пусть С1 и Сз — две большие окружности, вдоль которых р(и, А) = аю Под каким углом они пересекаются? Вопрос 5.4 (трудный). Опираясь на минимаксную теорему Куранта— Фишера (теорему 5.2), доказать теорему Коши о перемежаемостьи ~Н Ь1 ° Пусть А = т ~ — симметричная и х и-матрица и Н вЂ” подматрица =(ь порядка п — 1.

Пусть а„« .. а1 — собственные значения матрицы А, а 0„1 « 01 — собственные значения матрицы Н. Доказать, что два этих набора чисел перемежаются, т. е. а <В„1«.. ° 01<а;<В1 1<а1 1«. ° В1<а1. Н В ° Пусть А = т по-прежнему порядка н, а т х т-подматрица Н имеет собственные значения В « 01. Доказать, что собственные значения матриц А и Н перемежаются в смысле справедливости неравенств але1„о,1 < 01 < а (или, что эквивалентно, ад < 0. 1 „,1 < ад ~„„,~). Вопрос 5.5 (средней трудности). Пусть а1 » а„— собственные значения матрицы А = Ат, а 01 » 0„— собственные значения матрицы Н = Нз. Обозначим через Л1 » .

Л„собственные значения матрицы А+ Н. Используя минимаксную теорему Куранта — Фишера (теорему 5.2), доказать неравенства а. + 0„< Л, < ад + 01. Для положительно определенной матрицы Н вывести отсюда неравенство Л. > а,. Другими словами, добавление симметричной положительно определенной матрицы Н к симметричной матрице А может лишь увеличить собственные значения последней.

Этот результат будет использован в доказательстве теоремы 7.1. Вопрос 5.6 (средней тарудности). Пусть А = [А1, Аз) — матрица порядка и, причем А1 и Аз имеют соответственно размеры и х т и п х (и — т). Пусть о1 » и„— сингулярны числа матрицы А, а т1 » т, — сингулярные числа матрицы А1.

Используя теорему Коши о перемежаемости (вопрос 5.4) и утверждение 4 теоремы 3.3, доказать неравенства и > т; > очи 5.7. Вопросы к главе б 275 Вопрос 5.7 (средней трудности). Пусть а — нормированный вектор, а «(— произвольный вектор, ортогональный к а. Показать, что ~[(д + а)ч — 1[[а —— ~[у+ «(~[г (Этот результат используется в доказательстве теоремы 5.4.) Вопрос 5.8 (трудный).