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

Мы можем теперь проверить равенство (6.18): (г З г) (1 З Л+ Л З 1) (г З г) т = (Я З Я) (1 З Л+ Л З 1) (у,т З у,т) согласно утверждению 3 леммы 6,3 (У. 1. Ут) З (У. Л. Ут) + (У. Л . Ет) З (~. 1. ~т) согласно утверждению 1 леммы 6.3 =(1)з(т )+(т )з(1) =т Кроме того, легко видеть, что матрица 1 З Л + Л З 1 диагональная, а ее диагональный элемент с номером г1ч'+ г равен Л, + Л, Таким образом, равенство (6.18) действительно есть спектральное разложение матрицы Тн хгг. Наконец, из определения кронекерова произведения следует, что столбцом с номером г11' + г в матрице Я З Я является гг З г,. П Читатель может проверить, что г; Зг. = пес(гугт), что находится в согласии с выражением для собственного вектора в уравнении (6.12). По поводу обобщения предложения 6.1 на случай матрицы А З 1+ Вт З 1, возникающей при решении уравнения Сильвестра АХ+ХВ = О, см.

вопрос 6.5 (а также вопрос 4.6). Сходным образом, трехмерное уравнение Пуассона приводит к матрице т „к„~ азт З1 З1гг+1м Зт З1м+1м З1 Зт . Ее собственными значениями являются всевозможные тройные суммы собственных значений матрицы тгг, а Я З л З Я есть матрица собственных векторов. Уравнения Пуассона для еще более высокой размерности могут быть представлены в аналогичной форме.

6.4. Краткая сводка методов для решения уравнения Пуассона В таблице 6.1 указаны затраты при решении модельной задачи на сетке )ч' х Ф различными прямыми и итерационными методами. Число неизвестных п в за- 290 Глава 6. Итераниоиные методы для линейных систем даче равно /2/~. При сравнении затрат нужно проявлять известную осмотрительность, поскольку (в отсутствие ошибок округления) прямые методы дают точный ответ, тогда как итерационные методы находят лишь приближенное решение; в то же время приближение невысокой точности может быть вычислено посредством итерационного метода дешевле, чем очень хорошее приближение.

Поэтому мы сравниваем затраты в предположении, что число операций итерационного метода достаточно велико для того, чтобы снизить погрешность до некоторой фиксированной малой величины1 (скажем, 10 е). П 2.7.1 п2 Э/2 П П 2.7.3 и' П И 6.5 И 6.5 п/ и 1оби П 2.7.4 Якоби Гаусса — Зейаеля Холесского для разреженных матриц 3/2 2/2 Сопряженных градиентов Последовательной верхней релаксации Чебышевское ускорение с ББОВ. И И 6.6 6.5 2/4 И 6.5 п 1обп п 1обп Быстрое преобразование Фурье Блочная циклическая редукция Многосеточный 6.7 П 6.8 И Нижняя оценка Таблица 6.1.

Сравнительная сложность решения уравнения Пуассона на сетке )1/ х /2/(и — )2/2) Второй и третий столбцы табл. 6.1 показывают число арифметических операций (или время) и память, необходимые для метода на последовательной машине. В столбце 4 отмечено, является ли метод прямым (П) или итерационным (И). Для всех элементов таблицы указан лишь их порядок; константы, входящие в символ О, зависят от деталей реализации и критерия останова, принятого для итерационных методов (например, погрешность не превосходит 10 е). Поэтому, скажем, данные для метода Холесского верны и для гауссова исключения, так как (вдвое) меняются лишь константы в оценках. Последний столбец указывает раздел книги, в котором обсуждается данный алгоритм.

1 Другая возможность состоит в том, чтобы продолжать итерации до тех лор, пока оогрешлость не станет величиной порядка О(52) = О((14/+ 1) 2), т. е. того же порядка, что в погрешность элвроксвмацяв. Можно показать, что в этом случае стоимости ятерационлых методов, увезенные в табл. 6.1, приобрели бы множитель О(1окп). Холесского для плотных матриц Явного обращения Холесского лля ленточных матриц Время Память Прямой нлн Раздел итерационный 6.4. Краткая сводка методов для решения уравнения Пуассона 291 Методы перечислены в порядке возрастания их скорости от самого медленного (алгоритма Холесского для плотных матриц) до самого быстрого (многосеточный метод); таблица заканчивается нижней оценкой, справедливой для любого метода. Нижняя оценка п объясняется тем, что по крайней мере одна операция нужна для вычисления каждой компоненты решения; в противном случае, не все компоненты различны, что возможно лишь при специальных входных данных.

Упорядочение методов также примерно соответствует убыванию их общности: плотная версия метода Холесского применима к любой симметричной положительно определенной матрице, а прочие алгоритмы приложимы (или, по крайней мере, имеют гарантированную сходимость) лишь к специальным классам матриц. В последующих разделах область применимости различных методов описана более подробно.

Под алгоритмом «явного обращения» понимается предварительное вычисление матрицы Т в явном виде, после чего вектор е = Т „м~ находится посредством матрично-векторного умножения (операции по вычислению Т '„и не включаются в общую стоимость алгоритма). Подобно методу Холесского для плотных матриц, в данном алгоритме требуется пг слов памяти, что намного больше, чем во всех остальных методах; поэтому алгоритм не удовлетворителен. Метод Холесского для ленточных матриц обсуждался в разд. 2.7.3; это попросту вариант алгоритма Холесского, использующий то обстоятельство, что элементы вне ленты шириной в 2Ю+ 1 диагоналей не требуют хранения и обработки.

Методы Якоби и Гаусса — Зейделя — это классические итерационные методы; они не особенно быстры, но на них основаны другие, более быстрые методы, такие, как последовательная верхняя релаксация, симметричная последовательная верхняя релаксация и многосеточный метод, быстрейший из рассматриваемых нами алгоритмов. Методы Якоби и Гаусса — Зейделя довольно подробно исследуются в разд.

6.5. Метод Холесского для разреженных матриц — это алгоритм, обсуждавшийся в разд. 2.7.4. Он представляет собой реализацию алгоритма Холесского, в которой нулевые элементы матрицы Тг«„м или ее множителя Холесского не хранятся и не обрабатываются. Кроме того, предполагается, что строки и столбцы в Тм „и были «оптимально упорядочены» с тем, чтобы минимизировать работу и память (для чего используется метод вложенных сечений [112, 113]). Хотя разреженный метод Холесского достаточно быстр для двумерного уравнения Пуассона, он значительно хуже работает для трехмерной задачи (требуя времени 0(И ) = 0(п~) и памяти 0(Х ) = 0(п~7г)); причина в том, что происходит большее «заполнение» нулевых элементов.

Алгоритм сопряженных градиентов представляет обширный класс методов, называемых методами крыловского подпространстеа и широко используемых как при решении линейных систем, так и при нахождении собственных значений разреженных матриц. Эти методы более подробно обсуждаются в разд. 6.6. Наиболее быстрые методы — это блочная циклическая редукция, быстрое преобразование Фурье (г г Т) и многосеточный метод. В частности, в многосеточном методе выполняется лишь 0(1) операций на компоненту решения, что асимптотически является оптимальным результатом. В заключение этого обзора предупредим читателя, что таблица не дает полной картины, поскольку в ней отсутствуют константы.

Для задачи конкретного Глава 6. Итерационные методы для линейных систем порядка и конкретной машины из таблицы нельзя усмотреть непосредственно, какой метод работает быстрее всего. Все же ясно, что для достаточно больших и такие итерационные методы, как алгоритмы Якоби, Гаусса — Зейделя, сопряженных градиентов и последовательной верхней релаксации уступают методам РРТ и блочной циклической редукции, а также многосеточному методу. Тем не менее интерес к этим алгоритмам сохраняется, поскольку из них строятся некоторые более быстрые методы„а также потому, что они применимы к большему кругу задач по сравнению с быстрыми методами.

Все указанные алгоритмы могут быть реализованы как параллельные; см. детали в лекциях, помещенных на РАВАЬЬЕ? НОМЕРАСЕ. Интересно, что для некоторых параллельных машин многосеточный метод может оказаться не самым быстрым. Это объясняется тем, что на параллельном компьютере время, требуемое для обмена данными между отдельными процессорами, может быть сравнимо с временем, затрачиваемым на операции с плавающей точкой, и для некоторых алгоритмов объем коммуникаций может быть меньше, чем в многосеточном методе. 6.5. Основные итерационные методы В этом разделе мы обсудим следующие основные итерационные методы: метод Якоби, метод Гаусса — Зейделя, метод последовательной верхней релаксации (ЗОВ(ы)), чебышевское ускорение с симметричной последовательной верхней релаксацией (ВВОВ(ы)).