Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 2
Текст из файла (страница 2)
й 1,1. Метод Холесского и проблема упорядочения Все методы, обсуждаемые в книге, основаны на единственном численном алгоритме, известном как метод Холесского,— симметричном варианте гауссова исключения, скроенном для симметричных положительно определенных матриц. Мы определим этот класс матриц и детально опишем метод в 5 2.1.
Предположим, что система уравнений, которую нужно решить, есть Ах =Ь, (1.!.1) где А — й(Хо( симметричная положительно определенная матрица коэффициентов, Ь вЂ” вектор длины Ж, называемый правой частью, а х — вектор-решение длины Ф, компоненты которого должно вычислить. Применение к А метода Холесского приводит к треугольному разложению А=к,Ь~, (1.1.2) Где Š— нижняя треугольная матрица с положительнымн диагональными элементами.
Матрица М называется нижней (верх- У Л1 Метод Холесского и ироблема уоорядочеиил 11 ней) треугольной, если.ттгц = О для 1~! (1 !). Верхний индекс Т указывает иа операцию травспонмровпмия. В $2.1 мы покажем, что разложение (!.1.2) всегда существует, если А симметрична и положительно определена. Подставляя (1.1.2) в (1.1.1), имеем Ы х=Ь. Замена у = Етх показывает, что х можно получить, решая треугольные системы 2,у=Ь (1.1.4) и Е х=у. (1.1.6) В качестве примера рассмотрим задачу 4 1 2 —,' 2 1 0 0 0 2 0 3 0 0 Хг Х2 (1,!.6) Хз ΠΠ—,' 0 2 0 0 0 16 Х5 Множитель Холесского для матрицы коэффициентов системы (!.1.6) выглядит так: О. 50 (1.1.7) — 1 1 -0.25 -0.50 -1 -2 О. 50 — 3 1 Решая систему (у = Ь, получаем О.
50 1 О. 25 3.5 2. 5 6 -2.5 -О. 50 12 Гл 1 ВведеНие Затем, решая систему Егх = ГГ, находим 2 2 1 -8 -О. 50 Этот пример иллюстрирует наиболее важный факт, относящийся к применению метода Холесского для разреженной матрицы А: матрица обычно претерпевает заполнение Это значит, что ь имеет ненулевые злементы в позициях, где в нижней треугольной части А стояли нули. Предположим теперь, что мы перенумеровали переменные в соответствии с правилом х,-+-ха,+ь Г = 1, 2, ..., б, и переупорядочилн уравнения так, чтобы последнее стало первым, второе снизу — вторым сверху и так далее, пока, наконец, бывшее первое уравнение не станет последним.
Мы получим тогда эквивалентную систему рпавнений Г!.1.8) 16 О 0 0 2 0 в 0 О 0 0 3 0 2 Г!.1.8) 0 0 0 — ' 1 2 — ' 2 1 4 хт Должно быть ясно, что эта перенумерация переменных и пере- упорядочение уравнений равносильны симметричной перестановке строк и столбцов А, причем та же перестановка применяется к Ь. Эту новую систему обозначим через Ах = Ь. Применяя к ией, как и прежде, метод Холесского, мы разложим А в произведение И.г, где Гс точностью до трех значащих цифр) 4 0 0 О. 791 0 0 ).73 0 0 0 0.707 0.500 О.б32 1.15 1.41 0.129 р" 1.1 Метод Холесского и проблема упорядочения 13 ° ° 1 ° ° ° ° Э 1 * 1 ° ° ° ° ° 1 1 ° ° $ ° ° ° 11 1 ° ° ° 1 1 ° 1 1 ° ° ° ° 1 ° ° 1 ° 1 ° 1 ° ° ° 1 ° ° ° ° ° ° ° 1 1 ° 1 ° 1 ° 1 ° ° ° 1 ° ° 111 ° ° ° ° ° 1 1 ° ° ° ° ° ° ° ° $ 1 * 1 Рис.
1.1.1. Структура ненулевых элементов матрицы А порядка ЗЗ. ° ° ЭЭ ° ° ° ° ° ° ° ° ° ° 1 1 ° ° 1 ° 1 ° ° ° ° ° $1 ° 1 ° ° ° 1 ° ° ° ° ° ° ° 111 ° 1 1 1 1 ° ° ° ° ° 1 ° ° ° ° ° ° 1 ° ° ° ° ° ° ° ° 1 ° ° 111 ° ° ° ° 1 ° 1 ° ° 1 ° ° ° ° ° ° ° 1 ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° * ° ° ° ° ° 1 ° 11 ° 1 ° 1 ° ° 1 1 ° ° ° ° ° 1 ° ° ° ° 1 ° ° $ ° ° ° 11 1 1 ° 1 ° ° ° ° ° ° 1 1 ° ° ° ° ° ° ° 1 ° 1* ° ° ° ° 1 ° ° ° 1 ° 1 1 ° ° Э ° 1 ° ° ° ° ° ° ° ° ° ° ° ° ° ° 1$ ° 11 ° ° ° ° ° ° 1 ° ° 1 ° ° ° ° ° ° ° ° 1 1 ° ° ° 1 ° ° ° ° ° ° 1 ° ° ° ° ° 1 1 ° ° ° 1 ° 1 ° 1 ° ° 1 1 ° 1 1 1 ° ° 1 ° ° 1 ° 1 1 ° ° ° ° ° ° ° ° ° ° ° * 1 1 ° ° ° ° ° ° 1 1 1 1 ° ° ° ° ° 1 ° ° ° 1 Рис.
1.1.2. Структура ненулевых элементов множителя Холесского 1. цля мат. рицы, устройство которой показано на рнс. 1.1.1. й 1 Д Метод Холееекого и проблеме рооредочение 1б Решая Еу = Ь и Етк = у, получим решение л, которое есть всего лишь переупорядоченная форма к. Важнейший момент состоит в том, что переупорядочение уравнений и переменных привело к треугольному множителю Е, который разрежен в точности в той мере, что и нижний треугольник А.
Хотя на практике редко удается достигнуть столь полного успеха, для ° ° ° е ° ° ° е е ° ° ° ° ° ° ° ° ° ° ° ° ° е ° е ° ° ° е ° ° ° е ° ° е ° е ° е ° е ° ° *е ° е ° ° ° ° Ркс. 1.1.5. Структура матрицы А", свмметркчкой перестановки матрицы А, устройство которой показано ка ркс 1.1,1. большинства задач с разреженными матрицами разумное упорядочение строк и столбцов матрицы коэффициентов может дать огромное сокращение заполнения и, следовательно, экономию машинного времени и памяти (при условии, конечно, что разреженность используется). Исследование алгоритмов, которые автоматически выполняют этот процесс переупорядочения,— один из главных предметов этой книги наряду с исследованием эффективных численных методов и схем хранения разреженных множителей Е, предоставляемых этими переупорядочениями.
Приведенный выше матричный пример 5)т',5 иллюстрирует основные характеристики разреженного исключения и эффект переупорядочения. Чтобы лучше прочувствовать эти вопросы, рассмотрим пример несколько большего порядка; соответствующая !З Гл ! Вяадавва ему структура нулей-неиулей приведена иа рнс. 1ЛЛ. Раскла. дывая эту матрицу в произведение ЬЬг, получим структуру, указанную иа рис. 1.1.2. Очевидно, что матрица прв ее теперешнем упорядочении нехороша для разреженного исключеяия, поскольку онз претерпевает значительное заполнение. Рисунка 1.1.3 и 1.1.5 демонстрируют структуру двух сим.- метричных перестановок А' н А" матрицы А, устройство которой $ ° ° $ $ 1 $ $ $ ° ° ° ° ° ° $ ° 1 ° 1 ° ° ° $ ° * ° ° ° ° ° $ ° ° ° ° ° ФФФ ° $ ° ° ° ° ° $$$1 ° $ ° ° $$ ° $ 1 ° $1 ° ° ° ° ° ° ° ° ° ° ° ° 1 ° ° ° ° ° ° ° ° ° ° ° $ Э ° 1 Ф 1 Э $$$ ° ° ° $ 1 ° 1 1 ° $1 Э 1 ° ° ° ° ° ° ° 1 111 ФЭ Э ° ° 1 ° ° ° ° ° 1 ° ° ° $ ° ° ФФФ ° Э ° ° ° ° 1 ° ° $$ Рвс.
!.!.З. Структура а,", ввожвтсля Кола«ского матрацы 4", час устройства воватаво ва рве. !.!тк было показано иа рис. 1.1.1. Матрица А' приведена к так пазы ваемой ленточной форме, обсуждаемой в главе 4. Матрица А» упорядочена так, чтобы уменьшить заполнение; метод получения этого типа упорядочения является предметом главы 5. Число ненулевых элементов в у, а' и а.» равно соответственно 369, 189 и 177.
Как показывает наш пример, некоторые упорядочения могут вести к весьма существенным сокращениям заполнения илв ограничить его определенными областями Ь, которые допускают удобное хранение. Эта задача отыскания «хорошего» упорядоченна, называемая в дальнейшем «проблемой упорядочения», занимает центральное место при решении разреженных положительно определенных систем. э 1.2. Пологнительно онределенные гнданн !7 й 1.2, Положительно определенные и неопределенные матричные задачи В этой книге мы будем иметь дело исключительно со случаем, когда А симметрична и положительно определена.
Как уже было отмечено, существенная часть линейных систем, возникающих в научных и инженерных расчетах, обладает этим свойством, и проблема упорядочения для них решается иначе и проще, чем для разреженной матрицы А общего вида. В последнем случае необходима для обеспечения численной устойчивости та или иная форма выбора главного элемента, т, е. перестановки строк и/или столбцов (Рогзу1)зе 1967). Таким образом,.
при заданной А обычно получают разложение для РА или РАЯ, где Р и Я вЂ” матрицы перестановок соответствующих размеров. (Заметим, что умножение на Р слева переставляет строки 4, а умножение на 9 справа переставляет столбцы А.) Эти перестановки определяются и процессе разложения путем компромисса между (обычно конкурирующими) требованиями численной устойчивости и разреженности (Оп!! 1974). Различные матрицы, хотя бы они и имели одинаковую структуру нулей-ненулей, обычно приводят к различным Р и (;! и, следовательно, имеют множители с различной структурой раз.реженности.
Другими словами, для разреженных матриц общего вида, как правило, нельзя предсказать, ~де произойдет заполнение, пока не начались собственно вычисления. Тем самым мы вынуждены пользоваться какой-либо схемой динамического хранения, в которой память для заполнения выделяется в ходе вычислений, С другой стороны, симметричное гауссово исключение (т. е, метод Холесского илн один из его вариантов, описываемых в главе 2), в применении к симметричной положительно определенной матрице, не требует перестановок (выбора главных элементов) для поддержания численной устойчивости. Г(оскольку РАР' также симметрична и положительно определена ири любой матрице перестановки Р, это значит, что можно симметрично переупорядочить А, во-первых не заботясь о численной устойчивости и, во-вторых, до начала реального численного разложения.
Эти возможности, обычно отсутствующие в случае матрицы А общего вида, имеют важнейшие практические последствия, Раз упорядочение можно определить до начала разложения, то можно определить также и местоположение заполнения, которое произойдет при разложении. Поэтому способ хранения Е можно выбрать до реального численного разложения, так же как и зарезервировать место для элементов заполнения. Вычисления затем проводят при структуре хранения, остающейся статичной (неизменной).
Таким образом, три задачи 1) выбор 18 ГА. 1 Введение надлежащего упорядочения; 2) формирование подходящей схемы хранения; 3) реальные вычисления — могут быть разделены как самостоятельные объекты исследования и как разные модули программного обеспечения. Ситуация изображена на рисунке, Эта независимость задач имеет ряд отчетливых преимуществ. Она поощряет модульность при составлении математн ческого обеспечения и, в частности, позволяет кроить метод хранения по мерке данного этапа. Например, применение списков для хранения матричных индексов может быть вполне приемлемо при реализации алгоритма упорядочения, но решительно неудобно для реального хранения матрицы или се множителей.
Точно так же уверенность в возможности использовать при факторизации статичную схему хранения позволяет выбрать метод, очень эффективный в смысле требований к памяти, который, однако, потребовал бы катастрофических накладных расходов, если бы схему хранения пришлось менять в процессе разложения. Наконец, во многих инженерно-конструкторских приложениях приходится решать большое количество различных задач с положительно определенными матрицами, имеющих одинаковую структуру. Ясно, что упорядочение и формирование схемы хранения нужно выполнить лишь однажды; поэтому желательно, чтобы эти этапы были изолированы от реальных вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
