Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 5
Текст из файла (страница 5)
Существуют два распространенных способа решения такой системы, отличающиеся лишь порядком выполнения операций. В первом способе используются лишь скалярные произведения. Определяющие уравнения таковы; е ««« ° ° ° 01 «..001 й 22 Решение тререольлыл систем 33 34 Гя. а Вводные сведения для ю'=1,2... й (2.2.1) Последовательность вычислений изображена иа рисунке И Лаяькейшик оброиьеииа" ие врсйуешся Васо чоспсь дьшислеиа; П Восвуп к ней оспирыш Вычисяяеетая П часпсь Р Вброиьений пока не проискодипо Во втором способе подматрицы из Т используются таким же образом, как в варианте внешних произведений алгоритма разложения.
Определяющие уравнения выглядят так: для с=1,2, ..., М х; Ь,/б, ь,+, ь,+, !ь+ га (2.2.2) Ьн Заметим, что эта схема позволяе~ использовать разреженность решения я. Если в начале ь-го шага Ь| оказывается нулем, то н х, — нуль, и весь шаг может быть опущен. Порядок обращения к коэффициентам системы показан на рисунке. Яояьнвдшик обраиьений И ие требуется Ршо чесать 1ычиспена; П досшул и ней опекрьпп Пб Вычисяявпая часась 1-1 ~Эр~щений 1 ~ пока не прсискайипа В 2.2. Решение треугольных систем 35 В первом методе решения обращение к элементам нижней треугольной матрицы происходит строка за строкой, поэтому здесь применимы строчные схемы хранения.
Если матрица хранится по столбцам, то более уместен второй метод. Интересно отметить, что этот метод, с его ориентацией на столбцы, часто используется для решения верхней треугольной системы Ьтх* у, где Ь вЂ” нижняя треугольная матрица, хранимая посредством строчной схемы. 2.2.2. Число операций Установим теперь некоторые простые результаты, касающиеся решения треугольных систем. Они будут нужны позже при подсчете числа операций. Рассмотрим решение системы Тх Ь е невырожденной нижней треугольной матрицей Т. Лемма 2.2.1. Число операций при вьшислвнии х равно 2 (т)(Т,г)1хг Ф О).
Доказательство, Из (2.2.2) следует, что если х;ча О, то Ьй шаг требует ц(Тм) операций. Следствие 2.2.2. Если разреженность решения х не используется (т. в. х считается плотным вектором), то число операций при вычислении х равно т1(Т). Таким образом, при решении системы Тх= Ь, где Т и х плотные, число операций есть — гЧ ()и'+ 1). (2.2.3) Приводимые ниже результаты указывают некоторые. связи между структурой правой части Ь и структурой решения х нижней треугольной системы. Лемма 2.2.3 и следствие 2.2.5 опираются на предположение о неуничтожении, т.
е. если для двух ненулевых величин выполняется сложение или вычитание, то результат не равен нулю. Это значит, что в анализе мы игнорируем любые нули, которые могли появиться вследствие 2очного взаимного уничтожения. Такое уничтожение происходит редко, и, чтобы его предсказать, нужно знать числовые значения Т и Ь. Но и в этом случае подобное предсказание, вообще говоря, затруднительно, особенно в машинной арифметике, подверженной ошибкам округлений, Зб Гл а Вводные сведения Лемма 2.2.3.
В предположении о неуничтожении из Ь?~0 следует х, чьО. Доказательство. Поскольку Т невырожденна, 1„чь 0 для 1 = ! ( гт(. Теперь нужный результат следует из предположения о неуничтожении и определяющего уравнения (2.2,1) для х!. Лемма 2.2.4, Пусть х — решение системы Тх = Ь.
Если Ь, = О для 1(г(Ь, то х, = 0 для 1 ( ! ~ А. Следствие 2.2.5. При предположении о неуничтозхении справедливо неравенство т)(Ь) = т)(х), Упражнения 2.2Л. Используя ленцу 2.2.1, показать, что разложение по схеме окаймления требует Ф-! 1 2 ~, (ч(ь„!)-1)(ч(т.!)+2) ! ! операций. 2.2.2. Показать, что обратная к невырождениой нижней треугольной матрице также нижняя треугольная (использовать лемму 2.2.4). 2.2.3.
Пусть Т вЂ” невырожденная нижняя треугольная матрица со свойством распространения, т.е. !с!-, Ф О для 2 ( ! ( й!. а) Показать, что при решении системы Тх = Ь иэ Ь! чь О следует х! ть О для 1 ( / ( й'. б) Показать, что т-' — заполненная нижняя треугольная матрица. 2.2.4. Зависит ли лемма 2.2.! от предположения о неуничтожепии? Объ. яснить. Ответить на тот же вопрос в отношении теоремы 2.1.2 и леммы 2.2.4, 2.2.б. Доказать результат, аналогичный лемме 22,4, для верхних треугольных матриц.
2.2.6. Предположим, что нужно решить большое число нижних треугольных систем вида йу = Ь порядка М, причем и Ь, и векторы Ь разрежены. Известно, что для этих систем разрежены и решения у. Имеется выбор из двух схем хранения х., иллюстрируемый ниже примером порядка б; одна из этих схем ориентирована на хранение по столбцам; другая — на хранение по строкам. Какую иэ них вы выбралн бы н почему? Если бы вы написали фортранную программу для решения таких систем с выбранной структурой хранения, то было ли бы время исполнения пропорционально числу выполняемых операций? Объяснить. (Считайте, что число выполняемых операций равно по меньшей мере О(?У).) 3 О 0 2 204 0395 О О 7'0 7 а 2.2.
Решение треугольных систем 87 Индексы сшалбца() чааяоУыя зняченан Ин1екснатн Юекшар Сдана 2 Индексы ашная часяадыв аначнная Ин3вканыб йвмр 5 8 9 10 2.2.7. Пусть Е н И' — йГ Х Н нижние треугольные матрицы с ненулевыми диагональными элементами, не являюшиеся разреженными. Указать приблизительное число операций для вычисления Š— 'Ит То же самое в отношении вычисления ИттВ' 2.2.8.
Пусть л = 1+2(р — !) для некоторого положительного целого й, и пусть Ит — и Х р плотная (псевдо) нижняя треугольная матрица. Это значит, что Ит имеет нуля выше позиции 1 + (! — 1)й в столбце й элементы в остальных позициях не равны нулю. Пример с п 7 и р = 4 приведен ниже. Указать примерное число операций при вычислении В"Ит как функцию от и и р. 2.2.9. Пусть Š— невыро кденная л Х л нижняя треугольная матрица, а И' — матрица, описанная в упр.
2.2.8. Указать примерное число операций при вычислении Е-'И' как функцию от л и р. 2.2.10. а) Предположим, что А = ЕЕт, где Е описана в упр. 2.2.9, причем ц(Егч) ) 2, 1 <» ! ~ и — 1. В предположении о неуничтожеиии показать, что вычисление А ' путем решения уравнений Е)2= 2 и ЕтТ = Ит приводит к заполненной матрице. б) Пусть А — несимметричная матрица с треугольным разложением ЕК где Š— нижняя треугольная матрица с единицами на диагонали, а (7 — верхняя треугольная. Сформулировать условия и результаты, аналогичные усло- виям и результатам утверждения а).
За Гл д В«одни« сведения $2.3. Некоторые практические замечания Целью изучения разреженной матричной технологии решения линейных систем является снижение стоимости использования разреженности данной системы. Сравнивая в разделе 2.1.3 решение плотной и трехдиагональной системы, мы видели, что можно достигнуть огромных сокрашений в запросах к памяти и вычислительной работе.
Имеются различные схемы хранения разреженных матриц, отличающиеся способом использования нулей. В некоторых случаях допускается хранение части нулей в обмен на упрощение схемы хранения; в других — используются все нули системы, В главах 4 — 8 мы обсудим наиболее распространенные разреженные схемы решения линейных систем. Выбор метода хранения, естественно, влияет на запросы к памяти и на использование стратегии упорядочения (выбор матрицы перестановки Р). Кроме того, он оказывает существенное воздействие на реализацию разложения и решения, а следовательно, на сложность программ и время исполнения.
Однако, независимо от того какая схема разреженного хранения используется, в вычислительном процессе в целом могут быть выделены четыре фазы. Шаг ! (упорядочение). Найти «хорошее» упорядочение (перестановку Р) для данной матрицы А с учетом выбранного метода хранения. Шаг 2 (распределение памяти). Определить необходимую информацию о множителе Холесского «, матрицы РАР' с тем, чтобы сформировать подходящую схему хранения. Шаг 3 (разложение). Разложить переупорядоченную матрицу РАРг в произведение 1.1.г. Шаг 4 (решение греугольньнх систем).
Решить системы Еу = = Ь и Егх = у. После этого положить х = Ргх. Даже при заданном методе хранения имеется много способов для выбора упорядочения, определения подходящей структуры хранения и выполнения реальных вычислений. Схему разреженного хранения вместе с соответствующей комбинацией упорядочения/распределения памяти/разложения/решения мы будем в дальнейшем называть методом решения. Чаще всего называемыми задачами при выборе метода решения являются: а) уменьшить запросы к памяти; б) уменьшить время исполнения; в) уменьшить некоторую комбинацию памяти и времени исполнения; эта комбинация отражает относительную цену ресурсов в стоимости использования машинной системы. Хотя есть и другие критерии, иногда управляющие выбором метода, названные являются главными. Они иллюстрируют трудности, связанные с оценкой стратегии. 3 2.8, Некоторые крактитеские вамекакия 39 Чтобы можно было заявить, что один метод лучше другого в смысле одной из указанных выше мер, нужно иметь возможность точно оценить эту меру для каждого метода, а такая оценка значительно сложнее, чем кажется.
Рассмотрим вначале критерий машинной памяти. 2Л!. Запросы к памяти Память, используемая для хранения разреженных матриц, обычно состоит из двух частей: основной памяти, содержащей числовые значения, и накладной памяти, где хранятся указатели, индексы и другая информация, нужная для запоминания Рнс. 3.3.П Основная я наклалная память лля двух раалняных методов.
структуры матрицы и облегчения доступа к числовым значениям. Поскольку за машинную память приходится платить независимо от того, как оиа используется, всякая оценка запросов к памяти для данного метода решения должна включать описание способа, которым будут храниться матрица или матрицы, так чтобы в этой оценке накладная память могла быть учтена наряду с основной. Сравнение двух различных стратегий с точки зрения критерия памяти может сводиться к сравнению существенно различных структур данных, имеющих весьма различающуюся на.
кладную память. Поэтому метод, предпочтительный в смысле величины основной памяти, может уступать конкуренту, если в сравнении учитывается и накладная память. Эту ситуацию иллюстрирует рис. 2.3.1. В качестве простого примера рассмотрим два упорядочения матрицы на рис. 2.3.2 и соответствующие множители в'. и Х. Эле. менты нижнего треугольника к, (исключая диагональ) хранятся построчно в едином массиве; параллельный массив содержит их столбцовые индексы. Третий массив указывает положение каждой строки, а четвертый хранит диагональные элементы в, 40 Гл 2 Вводные сведения Длн хранения матрицы з. использована так называемая профильная схема, описываемая в главе 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
