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

Программа выдаст график 6.12. Вопросы к главе 6 З?б скорости сходимости (т. е. отношения последовательных невязок). Зависит ли эта скорость от величины Ь? от частоты осцилляций в Ь? значений параметров )ас1 и 1ас2? Для каких значений 1ас1 и )ас2 задача решается наиболее эффективно? Вопрос 6.1Т (средней трудности; програм.мироеание). Используя быстрый решатель модельной задачи из вопроса 6.8 или вопроса 6.16, применить метод декомпозиции области к построению быстрого решателя для уравнения Пуассона на Ь-образной области, как это описано в разд.

6.10. Большой квадрат должен иметь размер 1 х 1, а малый — размер 0.5 х 0.5; при этом малый квадрат примыкает к нижней половине правой стороны большого квадрата. Вычислить невязку, чтобы убедиться в правильности ответа. Вопрос 6.18 (трудньгй). Составить таблицу типа табл. 6.1, но не для двумерного, а для трехмерного уравнения Пуассона. Считать, что сетка неизвестных имеет размер )У х Х х М и п = Жв. Заполнить как можно больше позиций во втором и третьем столбцах таблицы.

Глава 7 Итерационные методы для задач на собственные значения 7.1. Введение В этой главе обсуждаются итерационные методы вычисления собственных значений для матриц столь больших, что к ним нельзя применить прямые методы из гл. 4 и 5. Иными словами, нужны алгоритмы, которые требуют памяти, меньшей чем 0(иэ) машинных слов, и работы, меньшей чем 0(из) флопов. Так как для хранения всех собственных векторов почти любой и х и-матрицы необходимо иметь иэ машинньгх слов, то наши требования к алгоритму означают, что он будет вычислять лишь несколько собственных значений, каким-либо образом выделенных пользователем, и соответствующих собственных векторов. Нам понадобятся сведения о крыловских подпространствах (см. рэзд. 6.6), симметричной проблеме собственных значений (равд.

5.2), а также о степенном методе и обратной итерации (равд. 5.3). Рекомендуем читателю вначале просмотреть названные разделы. Простейшая спектральная задача состоит в вычислении собственного значения с наибольшим модулем и соответствующего ему собственного вектора. Среди методов, решающих эту задачу, простейшим является степенной метод (элгоритм 4.1). Напомним, что внутренний цикл метода имеет вид у;~.~ = Ах;, х,+1 — — у;~.дДу;+д1~э. Последовательность (х ) сходится к собственному вектору, отвечающему искомому собственному значению (при условии, что имеется только одно собственное значение с наибольшим модулем и хг не лежит в инвариантном подпространстве, где требуемый собственный вектор не представлен).

Заметим, что матрица А используется в алгоритме только для выполнения матричновекторных умножений. Поэтому все, что нужно для алгоритма, — это «черный ящикь, на вход которого подается х;, а на выходе появляется Ах; (см. пример 6.13). С рассмотренной задачей тесно связана задача вычисления собственного значения, ближайшего к задаваемому пользователем числу и, и соответствующего собственного вектора. Именно для такой ситуации предназначена обрат- 377 7.2.

Метод Рэлвя — Рятца ная итерация (алгоритм 4.2). Напомним, что ее внутренний цикл имеет внд у«+1 — — (А — о1) ~ х;, х;+г — — у; »1/Ььы[[г, т. е. предусматривает решение системы линейных уравнений с матрицей коэффициентов А — о1. Снова последовательность [х«) сходится к нужному собственному вектору при условии, что имеется лишь одно собственное значение, ближайшее к о (и х1 удовлетворяет сформулированному выше условию). Для вычисления вектора уьы можно использовать любой из методов для разреженных матриц, описанных в гл.

6 или разд. 2.7.4, хотя обычно это стоит много дороже, чем простое умножение матрицы А на вектор. Если А — симметричная матрица, то для ускорения сходимости можно применить И)-итерацию (алгоритм 5.1); правда, не всегда можно гарантировать, что она сойдется именно к собственному значению, ближайшему к числу и. В результате й — 1 шагов степенного метода или обратной итерации, начатых с заданного вектора хм будет получена последовательность векторов хмхг,...,хы На эти векторы натянуто крыловское надпространство, определенное в разд.

6.6.1. Для степенного метода крыловское надпространство имеет внд Кь(А,хг) = врал[хм Ахы Агхы..., А~ 'х1[, а в случае обратной итерации это будет подпространство Кь((А — о.1) 1, х1). Естественно спросить, не правильней ли было бы, вместо того чтобы брать хь в качестве приближенного собственного вектора, поискать «наилучшее» приближение к собственному вектору во всем подпространстве Кы т. е. искать наилучшую линейную комбинацию 2',,, опхь Тот же принцип был применен в разд. 6.6.2 к решению ь системы Ах = 5, при этом в Кь разыскивалось наилучшее приближенное решение системы.

Мы увидим, что наилучшее приближение к собственному вектору, выбранное из Кы имеет значительно лучшую точность, чем вектор хь (и то же самое верно для приближений к собственному значению). Поскольку подпространство Кь в общем случае й-мерно, мы можем с его помощью вычислить 1«наилучших приближений к собственным значениям н собственным векторам. Эти наилучшие приближения называются числами и векторами Ритца.

Мы сосредоточимся на случае симметричной матрицы А. Краткое обсуждение несимметричного случая проводится в последнем разделе. Остальная часть данной главы организована следующим образом. В разд. 7.2 обсуждается метод Рэлея — Ритца, наше основное средство для извлечения информации о собственных значениях и собственных векторах из крыловского подпространства. В разд. 7.3 описан наш главный метод, а именно алгоритм Ланцоша, для случая точной арифметики.

В разд. 7.4 дан анализ существенно иного поведения алгоритма Ланцоша в арифметике с плавающей точкой. В разд. 7.5 и 7.6 описаны практические реализации метода Ланцоша, вычисляющие результаты хорошего качества, несмотря на округления. Наконец, в равд. 7.7 дано краткое обсуждение алгоритмов для несимметричной проблемы собственных значений. Т.2. Метод Рэлея — Ритца Пусть Я = [Щ, Я„] — произвольная ортогональная матрица порядка п, причем Яь и Ц„имеют соответственно размеры и х Й и и х (и — л). На практике 378 Глава 7.

Итерационные методы для задач на собственные значения столбцы матрицы Яь вычисляются алгоритмом Ланцоша (см. алгоритм 6.10 или алгоритм 7.1); на них натянуто крыловское надпространство Кь. Индекс и указывает, что подматрица Я„(большей частью) неизвестна (и — от английского «пп1«помп»). Однако пока нам совершенно не важно происхождение матрицы Ц. Мы будем пользоваться следующими обозначениями (они использовались и в формуле (6.31)): ( дтАд, дтАд = азы гь)~А[Я»,(г ) = ~ фА~) ф ~,) ( т.„с г„~ Т = Я~А«„ (7.1) Иными словами, столбцы матрицы Яь'»' (т. е. векторы Ритца) суть «наилучшие» приближенные собственные векторы, а диагональные элементы матрицы Л (числа Ритца) суть «наилучшие» приближенные собственные значения в том смысле, что они минимизируют норму невязки $8АРь — Р»Цйг.

При й = 1 Ть — зто попросту отношение Рзлея: Тд — — рфы А) (см. определение 5.1). Таким образом, Ть есть естественное обобщение отношения Рзлея на случай й > 1. Определение 7.1. Процедура Рзлея — Ритца заключаетсл в интерпретации собственных значений матрицы Ть = Щ АЯ» как приближений к собствент ным значениям матрицы А. Эти приближения называются числами Ритца. Пусть Ть = Ъ'Л»'т есть спектральное разлоокение матрицы Ть. Столбцы матрицы «ггпу' расс.матриваются как приближения к соответствую«цим собственным векторам и называются векторами Ритца.

Числа и векторы Ритца считаются оптимальными приближениями к собственным значениям и собственным векторам матрицы А по нескольким причинам. Во-первых, когда известны лишь Яь и Ты а Я„не известна, а потому не известны Тьь и Т, то числа и векторы Ритца суть естественные приближения, которые можно извлечь из известной части матрицы. Во-вторых, они удовлетворяют приводимому ниже обобщению теоремы 5.5. (Теорема 5.5 показывала, что отношение Рэлея есть «наилучшее приближение» к одному собственному значению.) Вспомним, что столбцы матрицы Яь тогда и только тогда определяют инвариантное подпространство для А, когда для некоторой матрицы В выполняется соотношение АЯ» = Я»В.