Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 61

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 61)

8.12. Матричное препставпеиие лпя рис. 6.11 1 2 3 4 5 б 7 Я 9 Ю 11 12 13 14 1 Х Х 2 Х Х Х Х Х 3 Х Х Х Х Х 4 Х Х Х Х 3 Х 5 Х Х Х Х 3 4 Х б Х 3 3 Х 4 5 Х Х 7 Х 4 4 Х Б 6 6 Х 5 5 Х 6 6 Х 6 6 Х Х Х Х 6 6 Х Х 9 Х Х 9 Х Ю Х Х Ю Х 11 Х Х 11 Х 12 14 Х 12 Х Рис. 8. !3. Матричиое представлеиие лпя рис.

6.11 после исключения меним к модели динамического манекена, является так называемый алюритм минимальной степени. Если вернуться к исходной нумерации узлов, показанной на рис. 8.8 и 8.9, то алгоритм минимальной степени начинает работу с выбора строки с минимальным числом ненулевых элементов (илн узла с минимальным числом непосредственных соседей) и меняет местами первые строку и столбец с этой строкой и столбцом с тем же но- мером*).

Затем выполняется первый шаг алгоритма исключения. После этого весь процесс повторяется, но уже с преобразованной подматрицей. Число ненулевых элементов встроке дает оценку сверху дпя числа заполняющих элементов, которые могут возникнуть на данном этапе гауссова исключения. Таким образом, алгоритм минимальной степени пытается осуществить локальную минимизацию заполнения. На рис.8.14и8.15 показано применение алгоритма минимальной степени к модели динамического манекена.

Хотя это и не является характерным, упорядочивание по алгоритму минимальной степени для данной конкретной матрицы приводит к полному отсутствию заполнения. В табл. 8.1 приведены требования к памяти при различных алгоритмах упорядочивания. Рис. 8.14. упорядочивание узлов динамического манекена по алгоритму минимальной степени Давайте теперь сравним различные упорядочивания по числу мультипликативных операций при реализации алгоритма гауссова исключения. В табл. 8.2 указано число умножений, необходимое дпя выполнения гауссова исключения при различных упорядочиваниях.

Число сложений приблизительно такое же, как и число умножений. Из этой таблицы видно, что, как и память, количество арифметических операций сильно зависит от способа упорядочивания. Приведенные данные показывают, что на рассматриваемой задаче алгоритм минимальной степени значительно превосходит другие алгоритмы упорядочивания. Отсюда, однако, отнюдь не следует, что этот алгоритм целесообразно использовать во всех случаях. Сравнительная эффективность различных алгоритмов упорядочивания зависит от конкретной задачи.

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

неизвестных) . Поэтому выбор строки, с помощью которой производится исключение, еще не стесняет выбор столбца для дополнительной опти мизацин. — Примеч, ред. 17ч Таблица 8.1 Требования к памяти ппи различном упорядочивании узлов в модели динамическо- го манекена 1я = 14) „число ненулевых элементов в исходной матрице равно 48 Всего ненулевых элементов Количество заполнителей Гауссово исключение без учета разреженности Гауссово исключение с учетом разреженности: первоначальное упорядочивание ленто кое упорядочивание алгоритм минимальной степени 196 46 28 48 1 2 3 4 5 б 7 8 9 Ю 11 12 !3 И 1 Х 2 Х Х 3 Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х Х 10 Х Х Х Х Х Х Х Х Х Х Х Х Х 13 Х Х Х Х рис.

8,14 Рис. 8.15. Матричное представление для чивость. Простейшим и наиболее изученным является случай симметричной матрицы, не требующей перестановки стуок для устойчивости гауссова исключения. Примеры таких матриц дают симметричные положительно определенные нли диагонально доминирующие матрицы, которые возникают при применении метода конечных элементов и конечно-разностных аппроксимаций. В этом случае можно использовать метод Холецкого или симметричные варианты гауссова исключения, представляющие собой модификации рассмотренных в гл. 3 алгоритмов для заполненных матриц.

Для таких задач имеется несколько простых алгоритмов упорядочивания, Таблица 82 Число мультипликативиых операций прн разлячном упорядочивании узлов в моде- ли динамического манекена (л = 14); число ненулевых элементов в исходной мат- рице равно 48 Решение Факторизация Гауссово исключение без учета разреженности Гауссово исклю инне с учетом разреженности; первоначальное упорядочивание ленточное упорядочивание алгоритм минимальной степени 546 210 138 117 39 108 84 62 которые стремятся получить Малую ширину лентЫ. Часто используется и алгоритм минимальной степени.

Более сложные алгоритмы упоминаются в дополнительных замечаниях к этому разделу. Обычный метод хранения разреженных матриц основывается на том, что слева от диагонали любой заполняющий элемент может возникнуть только правее первого ненулевого элемента строки, в которой этот элемент появляется. Поэтому для хранения можно использовать одномерный массажи, вьщеляя место для элементов строк от первого ненулевого элемента до диагонального элемента. При этом дополнительно требуется и указателей, содержащих информацию о размещении диагональных элементов матрицы А. Схема хранения ясна из рис. 8.16, Другой класс практических задач составляют разреженные матрицы, которые не являются симметричными, но имеют симметричную структуру разреженности, т.е.

такие, что а;; чь и;;, но если а;. = О, то и ад = О.Такие матрицы часто возникают при расчете электрических сетей. На практике такие задачи обычно решают, игнорируя проблему численной устойчи- ао Синнетричнаа аз1 атт аы аяч а„ аы аеч ибе (ач а„ атт азз а„ а„, а„ ам ап а„ ам аы ам абе ам) /,Г,'--- Рис. 8.16. Пример схемы построчного хранения симметричной матрицы 26! вости, даже если при этом не гарантируется точность результатов.

Дпя упорядочивания часто используют алгоритм минимальной степени. Для несимметричных матриц общего вида часто используют алгоритм минимальной степени в комбинации с модификацией стратегии частичного упорядочивания при выборе главного элемента, называемой пороговым упорядочиванием. При частичном упорядочивании в качестве главного используется максимальный по модулю элемент столбца, а при пороговом упорядочивании разрешается проводить исключение с помощью любого элемента, который не слишком мал по сравнению с максимальным, скажем, составляет отнегоне менее 10 — 20%. При такой стратеп1и на роль главного обычно претендуют несколько элементов, и из них можно выбрать лучший с точки зрения разреженности.

Этот алгоритм является компромиссом между сохранением разреженности и контролем за потерей точности, связанной с ошибками округления. Ненулевые элементь1 несимметричной матрицы можно задавать, указывая величину элемента вместе с номерами строки и столбца, т.е. использовать тройки чисел (а», [а, 1'а); где аь — величина элемента в позиции (г„, )а), а я изменяется от 1 до числа ненулевых элементов. Это один из йростейших способов представления данных, но далеко не лучший в смысле эффективности выполнения гауссова исключения. В современных пакетах математического обеспечения используются более сложные структуры хранения данных. Дополнительные замечания и ссылки 8.3 Об использовании прямых методов для решения разреженных линейных систем написаны буквально сотни статей. Это область, в которой в настоящее время ведутся очень активные исследования, так что материал этого раздела отнюдь не является исчерпывающим.

Авторы не рассчитывают, что, прочтя этот раздел, читатель будет в состоянии составлять высококачественные программы решения. разреженных линейных уравнений. Бель этого раздела — дать определенное представление об основных концепциях и приемах, используемых в этой области. Прямым алгоритмам решения разреженных систем посвящены книп~ [22, 81, 108] . Труды конференций по разреженным матрицам представлены в сборниках [2, 15, 63, 69, 85]. Две первые работы по прямым методам для задач с разреженными магри нами — это работы [57,68].

Весьма полный обзор, включающий сравнительно недавние результаты, имеется в статье [13 [. Предназначенная для исследований, связанных с обеспечением безопасности пассажиров, модель динамического манекена широко обсуждается в книге [108], Для симметричных положительно определенных матриц, возникающих при использовании метода конечных элементов, разработано несколько специальных алгоритмов упорядочивания. К ним относятся' профильные методы, методы параллельных и вложенных сечений, а также усовершенствованный алгоритм фактор-дерева. Обширная информация об этих алгоритмах содержится в книге [22]. Для несимметричных матриц также имеются специальные алгоритмы, причем некоторые из них известны по именам их разработчиков — Марковица (Матйоч41а) и Тинни (Т!ппеу).

Несколько таких алгоритмов рассмотрено в книге [108]. Относительно структур данных, используемых при работе с разреженными матрицами, см. работы [13, 22„108]. Описание хорошо документированных и тщательно проверенных пакетов программ, реализующих прямые методы для разреженных матриц, имеется в работах [14, 21, 106]. УПРАЖНЕНИЯ 8.3 8.4. Итерационные методы Альтернативу к рассмотренным в предыдущем разделе методам гауссова исключения составляют итерационные методы.

Характеристики

Список файлов книги