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

!!!!] —.5 — з —.5+ зев —.5 — е —.5 — е —.5 — пз е —.5+ ~е —.5 — пе пг —.5 — пе —.5 — е —.5+ ~~е 266 Глава 5. Симметричная проблема собственных значений о 1 1 о'3 Ог 1 1 ~/з,Гг 1 ч'3 ч'2 чз ъб 1 -1 ~З /б 1 -1 оз 7б 1 2 Гз Гб 1 Д, Π—;2 0 чг 1 0 -1 3 ~6 и — 1 3 ч'б 3 чб и Е = йа8(Я0,31, ~/3,0). (Метод Якоби сам по себе не упорядочивает сингулярные числа по величине; такое упорядочение может быть пристроено к нему в качестве заключительного этапа.) О Приведем другие примеры ситуаций, где может быть показано: метод Якоби или его варианты гарантируют высокую относительную точность вычисленного 3ЧР (или спектрального разложения симметричной матрицы), тогда как методы, использующие приведение к двухдиагональной (или трекдиагональной) форме, могут терять все значащие разряды наименьших сингулярных чисел (или собственных значений). Еще ряд примеров можно найти в [75].

1. Пусть А = ЬЬг — разложение Холесского симметричной положительно определенной матрицы А. Тогда ЯЧР матрицы Ь, т. е. Ь = УХ'Чт, дает спектральное разложение для А: А = УЕЗУг. Если Р = РХ, где Х хорошо обусловлена, а Р— диагональная матрица, то, согласно теореме 5.15, сингулярные числа об матрицы Ь могут быть вычислены методом Якоби с высокой относительной точностью, причем относительные погрешности ограничены величинами 0(е) к(Х). Нужно еще учесть округления, произведенные при вычислении множителя Холесского Ь.

Используя оценку (2.16) и теорему 5.6, можно дать оценку 0(е) кг (Х) для относительных погрешностей в сингулярных числах, появившихся вследствие округлений в алгоритме Холесского. Таким образом, если Х хорошо обусловлена, то все собственные значения матрицы А будут вычислены с высокой относительной точностью (см. вопрос 5.23, а также [82, 92, 183]). Пример 5.10.

Этот пример, подобно примеру 5.9, иллюстрирует экстремальную ситуацию, где всякий алгоритм, опирающийся на предварительное приведение матрицы А к трехдиагональной форме, полностью теряет относительную точность в наименьшем собственном значении; в то же время, применяя алгоритм Холесского, а затем метод односторонних вращений к полученному множителю Холесского, можно вычислить все собственные значения с почти полной машинной точностью. Как и в предыдущем примере, положим 31 = 10 20 (в действительности, годится любое 31 ( е/120) и пусть А =,/б 1 10п ,Уб 10п 100п 1 10-10 10 — 10 10-10 1 10-19 Метод односторонних вращенизз не испытывает никаких трудностей с этой матрицей. За три цикла вычисляется разложение С = РЕЮ'т, где, с точностью до машинного эпсилон, 5.5.

Дифференциальные уравнения и задачи на собственные значения 267 Если приведение А к трехдиагональной форме выполняется точно, то будет получена матрица Т= 1 ~/2ц ~/2ц .5+ 60п .5 — 500 .5 — 50п .5+ 40п Однако, вследствие малости числа и, округления приводят к матрице Т = ~/20 .5 .5 которая не будет даже положительно определенной, так как 2 х 2- подматрица в ее правом нижнем углу (точно) вырожденна. Таким образом, наименьшее собственное значение матрицы Т неположительно, т.е. при приведении к трехдиагональной форме относительная точность в наименьшем собственном значении была полностью утеряна. Напротив, метод односторонних вращений не встречает затруднений при вычислении квадратных корней из собственных значений матрицы А, а именно, чисел 1+ /0 = 1+ 10 1а 1 — /0 = 1 — 10 ш и 0.99п = 0.99 10 ~~ Найденные приближения имеют почти полную машинную точность.

О 2. Опишем наиболее общую ситуацию, в которой мы понимаем, как следует вычислять 8ЧР матрицы А с высокой относительной точностью: требуется, чтобы мы могли с хорошей точностью найти произвольное разложение вида А = УРХ, где матрицы Х и У хорошо обусловлены, но в остальном произвольны, а Р— диагональная матрица. В предыдущем примере мы имели Ь = РХ, т. е.

У была единичной матрицей. Другим источником подходящих разложений является гауссово исключение с полным выбором главного элемента (где У вЂ” нижняя, а Х вЂ” верхняя треугольные матрицы). Подробнее об этом см. в (74]. Приложения этой техники к симметричным незнакоопределенным задачам на собственные значения можно найти в [228, 250], а к обобщенной симметричной проблеме собственных значений — в ]66, 92]. 5.5. ДиФференциальные уравнения и задачи на собственные значения Пусть х — горизонтальное смещение от положения равновесия. Тогда закон Ньютона Г = гпа может быть записал уравнением тй($) + Мотивацией для данного раздела являются физические законы сохранения. Снова обратимся к связанной системе материальных точек, введенной в при- мере 4.1 и затем рассмотренной в примере 5.1.

Начнем с простейшего случая одной пружины и одной массы, предполагая, что трение отсутствует. 268 Глава 5. Симметричная проблема собственных значений 5.5.1. Решетка Тода Чтобы упростить обозначения, будем писать х вместо х(«), если аргумент известен из контекста. Реп«етка Тода — это тоже связанная система материальных точек, только воздействие, оказываемое каждой пружиной, вместо того, чтобы линейно зависеть от растяжения, является экспоненциально убывающей функцией от него: -(х«-и««) — (и««« — е«) В качестве граничных условий возьмем е (*' *') = 0 (т.е.

хо = — оо) и е (*"+' *") = 0 (т. е. х„+г = +оо). Проще говоря, эти условия означают, что ни слева, ни справа от системы нет стенок (см. рис. 4,1). Сделаем теперь замену переменных бь = ~1е(*" *»+«)«~ и аь = — йхы Это й приводит к дифференциальным уравнениям бь = -е(*" *»+"' . -(хь — хьы) = Ьь(аь»« — аь), 1., аь = — -хь = 2(б~ь — Ьь,), (5.27) где следует считать бо = 0 и Ь„= О.

Введем две трехдиагональные матрицы а«51 о ь ь, и В= ь„ Ь„1 а„ ь„ — ь„о кх(«) = О. Положим Е(«) = зтх~(«) + зах~(«) = «кинетическая энергия» + «потенциальная энергия». Закон сохранения энергии говорит нам, что производная е«Е(«) должна быть равна нулю. Мы можем проверить, что это действительно так: ее Е(«) = тх(«)х(() + йх(«)х(«) = х(«)(тх(«) + Йх(«)) = О, как и утверждалось. В более общем случае мы имеем уравнение Мх(«) + Кх(Ф) = О, где М— матрица масс, а К вЂ” матрица жесткости. Энергия определяется формулой Е(г) = -'х~(Г)Мх(Г) + 1х~(Г)Кх(Г).

То, что такое определение корректно, подтверждается проверкой сохранения этой величины: — Е(г) = — ~-х (г)Мх(г) + -х («)Кх(г) т 1- т с(с аг '«,2 2 = -(х («)Мх(«) + х~(«)Мх(«) + х~(«)Кх(«) + хт(()Кх(Г)) 1 -т 2 = х (()Мх(г) + х (г)Кх(г) ( К И М х ( ) + К х ( Ф ) ) 0 В этих выкладках была использована симметрия матриц М н К.

Дифференциальное уравнение Мх(г) + Кх(г) = 0 линейно. Замечательно, что и некоторые нелинейные дифференциальные уравнения сохраняют величины, имеющие смысл «энергии». 5.5. Дифференцигльные уравнения и задачи па собственные значения 269 Заметим, что В = — Вт. Легко проверить, что система уравнений (5.27) может быть записана в виде з', = ВТ вЂ” ТВ. Это уравнение называется потоком Тода. Теорема 5.16. Матприца Т(Ь) при всех е имеет те же собственные значения, что и матрица Т(0). Иначе говоря, подобно тзнергииг, собственные значения сохраняются данным ди44еренциальным уравнением.

Доказательство. Рассмотрим задачу ззгУ = ВУ, У(0) = 1. Мы утверзцдаем, что матрица У(г) ортогональна для всех й Поскольку У~У(0) = 1, достаточно показать, что зт(1~У = О. Имеем д — Б~Б = (1~О+ У~О = У~В~У + У~ВО = — У~ВУ + У~ВУ = О. сй Здесь была использована косая симметрия матрицы В.

Теперь мы покажем, что матрица Т(с) = У(г)Т(0) У~(с) удовлетворяет урав- нению Тода зз', = ВТ вЂ” ТВ. Отсюда бУдет следовать, что пРи любом Ь матРи- ца Т(Ь) потока Тода ортогонально подобна матрице Т(0), а потому имеет те же собственные значения. Имеем й — ТЯ = (1(~)Т(0)(1 (с) + 11(~)Т(О)(1'И) = В(с)У(в)Т(О)Ут(Х) + У(в)Т(О)Ут(с)вт(с) = ВИТЯ вЂ” Т(1)В(й), что и требовалось. Единственным свойством матрицы В, использовавшимся в этих выклад- ках, была косая симметрия. Поэтому если з — — ВТ вЂ” ТВ и В = — В, то зт т матрица Т(с) имеет одни и те же собственные значения для всех й Теорема 5.1Т.

При Ь -+ +оо или Ь -+ — оо матрица Т(Ь) сходитпся к диаго- нальной матрице, на диагонали которой находятпся ее собственные значения. Доказательстпво. Мы хотим показать, что Ь; -ь 0 при Ь вЂ” ~ хоо. Для этого вначале покажем, что ) 2 „,,~ Ьг(Ь) гй < оо. Используя индукцию, докажем, что ) (Ьг(Ь) + Ьг .(г)) гй < оо, и затем сложим такие неравенства для всех г. ПРи з = 0 имеем ) (Ьог(Ь) + Ьг (г)) ~й. Эта величина Равна нУлю по пРедполо- жению. Положим теперь у(г) = а. (Ь) — а„+1(с). При всех Ь функция у(г) ограни- чена величиной 29Т(г) Ог —— 29Т(0) Ог.

Ймеем ф(с) = а (Ь) — а„дч.|(й) 2(ЬЬ (г) Ьг г (г)) — 2(ЬЬ 1(г) — Ьг, (Ь)) = 2(Ь,'(Ю) + Ь'„1Я) — 2(Ь,'.,(Ь) + Ь'„1+, (Г)), откуда Гт ~р(т) — ~р( — т) = / ф(с) ~й -т Гт тт = 2 / (Ьг(Ь) + Ьг (Ь)) гй — 2 / (Ьг,(Ь) + Ьг +1(8)) сй. — т — т 270 Глава 5. Симметричнан проблема собственных значений Последний интеграл ограничен при всех ~, согласно предположению индукции. Так как функция ~р(т) — 1р( — т) ограничена при всех т, то интеграл ) (Ьг(Ь)+ Ь~ 1(~)) гй' тоже должен быть ограничен.

Положим р(г) = 2 и, Ь((г). Мы уже знаем, что ) р(г) М < оо. Поскольку р(ь) > О, мы хотели бы вывести отсюда, что 11шг,ь р(ь) = О. Однако нужно сначала исключить возможность для р(Ь) иметь узкие пики при Ь -+ асс, иначе это позволило бы интегралу ) р(Ь) ~й быть конечным даже при том, что р(г) не стремится к нулю. Мы докажем отсутствие пиков, проверив, что производная функции р(г) ограничена: и — 1 и — 1 /р(й)/ = ~~1 2Ь1(г)Ь1(й) = ~~> 2Ь~(й)(а1+1(й) — аг(Ь)) < 4(п — 1)ЦТЦ~~. П Таким образом, чтобы решить проблему собственных значений, в принципе, можно воспользоваться программой, решающей системы обыкновенных дифференциальных уравнений, применяя ее к потоку Тода. Однако этот способ не будет быстрее других существующих методов. Самое интересное в потоке Тода — это его тесная связь с Яй-алгоритмом.

Определение 5.5. Пусть Х обозначает низюнюю строго треугольную часть матрицы Х. Полозкам яо(Х) = Х вЂ” Хз. Заметим, что яо(Х) — кососимметричная матрица и если сама матрица Х кососимметрична, то го(Х) = Х. Таким образом, яо есть проектор на множество кососимметричных матриц. Рассмотрим дифференциальное уравнение — Т = ВТ вЂ” ТВ, 11 Ж (5.28) где В = — яо(г"(Т)) и г" — произвольная гладкая функция вещественного переменного, принимающая вещественные значения. Поскольку В = — В~, из теоремы 5.16 следует, что матрица Т(Ь) имеет одни и те же собственные значения для всех Ф.

Выбор и (х) = х соответствует только что рассмотренному потоку Тода, так как в этом случае о ь, -Ьг -яо(г (Т)) = -яо(Т) = Ьи 1 — Ьи о Оказывается, что Я11-разложение связано с решением дифференциального уравнения (5.28). Теорема 5.18. Пусть г'(Т(0)) = гш и пусть е~ и = Я(~)В(~) есть Ядразлозкение матрицы ег~г.