Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 60
Текст из файла (страница 60)
С этой точки зрения для нас будет раэрекенной такая матрица (или система), которая позволяет с выгодой использовать наличие нулевых элементов — как их количество, так и расположение. В этом и следующем разделах мы будем заниматься методами решения разреженных линейных систем. Существует два основных подхода к решению разреженных систем линейных уравнений. Первый подход состоит в применении метода гауссова исключения, избегая при этом использования и запоминания.
если не всех, то большинства нулевых элементов. Под методом гауссова исключения мы здесь понимаем как треугольную факторизацию, так и алгоритм Холецкого. Важными моментами здесь являются порядок исключения неизвестных и структура данных, используемая для хранения информации об элементах матрицы. Этот метод рассматривается в настоящем разделе. Второй подход к решению разреженных линейных систем заключается в использовании итерационных методов.
Главными здесь являются вопросы сходимости и скорости сходимости. Этот подход обсуждается в разделе 8.4. Как мы показали в гл. 3 и снова напомнили в разделе 8.2, для решения общей линейной системы уравнений размера и Х и требуется О(п ) арифметических операций и О(п~) ячеек памяти. Следовательно, вариант гауссова исключения для разреженных систем должен преследовать две основные цели. 1. Уменьшить необходимое число операций за счет невыполнения операций с нулями. 2. Сократить требования к памяти за счет хранения только отличных от нуля элементов и информации об их расположении.
Именно этим вопросам будет посвящена остальная часть этого раздела. Давайте сначала рассмотрим матрицу системы (8.2.10), которая соответствует лексикографическому упорядочиванию, показанному на рис. 8.4. При Ф = 4 мы получаем ленточную матрицу, представленную на рис. 8.5. Если мы выберем другое упорядочивание, то изменится и вид соответствующей матрицы. Если, например, пронумеровать узлы сетки так, как показано на рис. 8.6, то придем к матрице, представленной на рис. 8.7. Такое упорядочивание называют черно-белым из-за его аналогии с расположением белых и черных полей на шахматной доске.
Эта матрица имеет довольно необычную структуру: если ее рассматривать как блочную, 252 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 4 -1 2 -1 4 -1 3 — 1 1 -1 5 -1 6 -1 4 -1 -1 4 -1 —.1 4 -1 -1 4 4 -1 -1 4 -1 1О -1 4 -1 -1 4 -1 -1 4 -1 16 -1 Рис 8.5. Матричное дредстааленне дли рис. 8.4 прн М состоящую из четырех квадратных блоков, то диагональные блоки являются диагональными матрицами, а все ненулевые элементы внедиагональных блоков равны — 1. Эти две матрицы, которые показаны на рис. 8.5 и 8.7, играют важную роль при анализе итерационных методов, рассматриваемых в разделе 8.4. Вид матрицы, возника.,щей при разностной аппроксимации дифференциального уравнения (8.2.2), зависит от нескольких факторов. Порядок матрицы и определяется значением Ь, задающим размер ячейки сетки. Расположение ненулевых элементов зависит от упорядочивания узлов сетки.
Это видно, если сравнить рис. 8.5 и 8.7; Далее, выбор конкретной разностной аппроксимации (см. формулы (8.2.4)) определяет как величины ненулевых элементов, так и степень разреженности матрицы. Если, например, вместо (8.2.4) воспользоваться разностной аппроксимацией (3.2.36), то изменятся значения ненулевых элементов и их количество (в одной строке матрицы может оказаться до девяти отличных от нуля элементов (упражнение 8.3.4) ) . отрим дружную Р~~реженную матрицу котор обл гораздо меньшей регулярностью, чем маттащы, показанные на рис. 8.5 и 8.7. Эта матрица возникает при изучении проблемы безопасности пассажиров в автомобиле.
Объект, представленный в виде графа на рис. 8.8, является грубой моделью так называемого динамического манекена. Каждому спо. собу нумерации узлов (или вершин) графа соответствует разреженная матрица, структура которой определяется следующим образом: если узел ~ связан ребром с узлом 7', то элемент ап отличен от нуля. Матрица динами- 233 о15 о7 о16 о8 Ч Б Ч Б об о(б о б о14 В Ч Б Ч о 11 ч оз В о12 о4 Ч 'Б о1 об о2 о10 Б Ч Б Ч Рис. 8.б. Сетка при черно-белом упорядочивании дпя Ф = 4 11 12 15 14 15 Ю 8~9 9) 1 1 1 1 ~-1 -1 3 1-] 1 1 -1 1 1 ! ! ! 4~ 1 2 5 4 5 Ь 7 2 4 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 10 -1 11 -1 -1 -1 12 -1 -1 -1 15 14 -1 -1 Рис. 8.
1 Матричное представление для рнс. 8.6 ческого манекена при нумерации узлов, показанной на рис.8.8, представлена на рис. 89. Мы сейчас не будем интересоваться величинами ненулевых элементов, а только их расположением. Основным моментом, осложняющим применение метода гауссова исключения к разреженным матрицам, является то, что элементы, которые первоначально равнялнсь нулю, в ходе алгоритма могут стать отличными от нуля Такие вновь возникающие элементы называют заполняющими элементами или просто заполнителями. То, как появляются заполнители, легко видно из анализа процесса исключения. Рассмотрим основной шаг гауссова исключения (см.
(3.3.11) ): (ач1) (а) (а) (я) (я) а; = (а1 — а,, а, ) /а „ . (8.3.1) На Ус-м шаге исключения элемент а~у по формуле (8.3.1) преобразуется (а) (а+1) (е) (е) (ь) в а~, . Если а(у = О, а элементыау® иаьу отличны отнУлЯ, то на Ус-м шаге в позиции (у, у) появится заполнитель. Давайте посмотрим, как происходит заполнение при применении алгоритма гауссова исключения к матрице на рис. 8.9, которая соответствует первоначальной нумерации узлов динамического манекена.
Первым подлежит исключению элемент в позиции (2,1). Чтобы сделать этот элемент Рис. 8.8. Динамический манекен равным нулю, мы вычитаем иэ второй строки первую, умноженную на подходящий множитель. Это соответствует использованию формулы (8.3.1) при Ус= 1, У= 2 и у'= 2,...,и. Заполнение будет происходить в тех случаях, когда аэ; = О, а а,, ФО. Это имеет место при у =5 и у =8. Следо(э) (з) вательно, на первом шаге гауссова исключения элементы аа, и а,а станут отличными от нуля.
На рис. 8.10 это отмечено единицами в позициях (2,5) н(2,8). То ж. самое произойдет с элементами (5,2) и (8,2) при исключении элементов (5,1) и (8.1). На втором шаге гауссова алгоритма исключение элементов второго столбца приведет к появлению новых ненулевых элементов в третьей строке и третьем столбце. Все заполняющие элементы, которые возникают в процессе исключения, отмечены на рис.8.10.
Число т на рис. 8.10 указывает, что элемент в ссЬтветствуюшей позиции возник на шаге т алгоритма исключения. Отметим, что на шагах 4, 7, 10, 12, 13 и 14 никакого заполнения не происходило. Из рис. 8.10 видно, что исходная матрица имела 48 ненулевых элементов, а в ходе исключения добавилось 46 заполняющих элементов, так что полное число ненулевых элементов стало равным 94, т.е.
почти удвоилось. Соответственно возрастают и требования к памяти. Вопрос о количестве дополнительных арифметических операций будет рассмотрен позднее. Сравните эти числа со 196— числом элементов в заполненной матрице размера 14 Х 14. Обратимся теперь к "разреженным вариантам гауссова исключения". Ключевой вопрос состоит в том, можно ли проводить исключение в другом порядке так, чтобы возникало как можно меньше заполняющих элементов. Так как исключение элементов в другой последовательности эквивалентно перестановке строк и столбцов исходной матрицы, то "разреженные варианты" будут связаны с соответствующим переупорядочива- 2Я 2845В789аиа1316 х х х х ххх х х ххх х х х х х х х х ххх х х х ххх х х 16 ххх х х х х х х х И х х Рис.
В.У. Матричное представление для рнс, 8.8. 1 2 Я 4 5 6 7 8 9 10 11 12 13 14 х х х Х Х Х 1 1 Х Х 2 Х Х 3 3 3 Х Х 3 3 Х Х 5 5 5 Х Х 3 Х 1 2 3 Х 6 6 5 6 Х Х 3 Х Х Х 8 Х Х 9 Х 1 2 3 Х В 3 8 9 Х Х Х Х Х 11 5 6 3 8 9 Х 11 Х Х Х Х 3 3 Х Х 3 3 Х Х Рис. 8.10, Матричное представление дпя рис. 8.8 после гауссова исключения. Чис- ло ги в позиции (1, у) указывает, что на шаге т алгоритма исключения в этой позиции возник ненулевой элемент нием строк и столбцов исходной матрицы.
Чтобы продемонстрировать, к чему это может привести, давайте пронумеруем узлы динамического манекена так, как показано на рис. 8.11. Соответствующая матрица приведена на рис. 8.12. Если мы теперь применим к этой матрице алгоритм гауссова исключения, то получим заполнение, показанное на рис. 8.13. Матрица на рис. 8.12 имеет те же 48 ненулевых элементов, что и на рис. 8.9, но располагаются они иначе, а это приводит к другому заполнению. Действительно, иэ рис. 8.13. видно, что в последнем случае возникают только 28 заполняющих элементов, а не 4б, как при первоначальном упорядочивании.
Рис. 8.11. Упорядочивание узлов динамического манекена, ориентированное на минимизацию ширины ленты Следовательно, необходимая память для хранения факториэованной формы переупорядоченной матрицы будет значительно меньше, чем для факторизованной формы исходной матрицы. Выше мы видели, что порядок, в котором исключаются элементы, влияет на степень заполнения матрицы.
Отсюда следует, что объем памяти для хранениг элементов матрицы и количество арифметических операций при исключении сильно зависят от выбора конкретного упорядочивания. При этом естественно возникают два следующих вопроса; 1. Какое упорядочивание неизвестных приводит к минимальному заполнению? 2. При каком упорядочивании неизвестных требуется минимальное число арифметических операций? Упорядочивание, которое дает минимальное заполнение, и упорядочивание с минимумом операций не обязательно совпадают. Интуитивно это ясно и иэ того, что элемент, который возникает на ранней стадии исключения, обычно приводит к большему числу операций, чем элемент, возникающий позже.
Установление упорядочивания, которое минимизирует заполнение или число операций, является задачей, решение которой требует исключительно много машинного времени. Поэтому на практике обычно не стремятся найти оптимальный алгоритм,.„а используют некоторые стандартные алгоритмы упорядочивания, которые работают сравнительно быстро и дают "хорошие" результаты. Качество алгоритмов определяется довольно субъективно на основе анализа их работы на ряде тестовых примеров. Упорядочивание, продемонстрированное на рис.
8.11 — 8.13, основано на идее получения матрицы с минимальной шириной ленты (вспомните определение из гл. 3). Другим алгоритмом упорядочивания, который мы при- 17. Дж. Ортега 257 1 2 3 4 5 6 7 8 9 Э и 12 13 14 х х Х Х Х Х Х 3 х х х х х 4 Х Х Х Х Х 5 Х Х Х Х х х х х Я х Х х х х х х х х х Х Х Х Х Х Х Х Х !4 Х Х Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
