Джордж, Лю - Численное решение больших разреженных систем уравнений (947498)
Текст из файла
Москва кМнр» 1984 А. Джордж Дж. Лю Численное решение больших разреженных систем уравнений Перевод с ангпийского Х Д. Икрамова ЬБК 22.108 Д42 УЛК 512.8 + 518.12 В книге известны» америкааских математиков.вычислителей описаны есе основные иетоды решения раареженных положительно определеннмх кииейнык систем Впервме в монографической литературе налагаются алгоритмы параллельных и вложенных сечений, ревработанные А Джорджем и преднавначеинме для систем метода конечнмх ьлементов Включены тенеты фортранныя программ, реалнауюшне описанные методы Для математиков-приклаанпков, для всех, кто свнаан с Решением раврежеииых линейных систем, лля студентов и аспирантов факультетов пряхладиой ма- тематики 1702070000 — 05 1 57 84 04!(01) — 84 ББК б!8 Редакция лигиерагиуры ио магиемагиичееким наукам © 1981 Ьу Ргеп11се На11, 1псч Епб!еогоод С1!Нй, 14.
5, © Перевод Ва русский язык, «Мвр», 1984 Джордж А., Лю Дж. Д42 Численное решение больших разреженных систем уравнений: Пер. с англ. — Мя Мир, 1984. — 333 с., ил. От переводчика Книга американских математиков Джорджа и Лю посвящена вопросам машинной реализации метода Холесского для решения линейных систем с симметричными положительно определенными матрицами. Системы предполагаются разреженными; в то же время, как правило, допускается использование только оперативной памяти. При таком серьезном ограничении повышение порядка решаемых систем возможно лишь за счет максимальной эксплуатации их разреженности.
Центральная проблема в методах исключения — это способ выбора главных элементов. Для систем общего вида обычно принимается компромисс между требованием численной устойчивости процесса и желанием по возможности сохранить разреженность матрицы. При этом использование разреженности основывается исключительно на структуре матричного графа, в то время как выбор по устойчивости зависит от числовых значений элементов. Отсюда следует, что для класса систем общего вида с различными матрицами одинаковой структуры априорный выбор порядка исключения, вообще говоря, невозможен. Иначе обстоит дело в симметричном положительно определенном случае.
Здесь численная устойчивость обеспечена при любом порядке исключения, что позволяет подчинить выбор главных элементов единственной цели — наиболее полному ис. пользованию разреженности. В книге представлены — и реализованы в виде фортранных подпрограмм — все основные современные подходы к обработке разреженных структурно симметричных систем: методы, ориентированные на уменьшение профиля; методы, основанные на локальной минимизации заполнения (алгоритм минимальной степени); блочные методы; наконец, методы сечений для коиечиоэлементных систем. В каждый из названных методов, либо в теоретическую разработку, либо в практическую реализацию, авторы внесли собственный значительный вклад. В особенности это относится к Алану Джорджу — одному из ведущих американских экспертов по разреженным матрицам.
Имя Джорджа известно советским специалистам главным образом в связи с разработанным им оригинальным алгоритмом упорядочения плоских коиечиоэлементарных графов. В нашей литературе этот 6 От переводчика алгоритм обычно называют методом гнездовых или крестовых сечений (разбиений). В предлагаемом переводе принят третий вариант названия — алгоритм вложенных сечений Этим термином, по-видимому правильнее всего отражающим существо метода, я обязан В. Д. Чубаню Книга адресована широком> кругу читателей — вычислителей и инженеров, — занимающихся решением больших разреженных систем. Она может составить основу спецкурса для студентов факультетов прикладной математики.
Для понимания материала достаточно скромной математической подгоговки — знания вводного курса линейной алгебры и языка Фортран. Можно сказать без преувеличения, что книга Джорджа и Лю отражает самый передовой уровень математического обеспечения в данной области. Советскому читателю она принесет большую пользу. Х. Икрамов Предисловие Назначение этой книги — ввести читателя в важную практическую задачу машинного решения больших разреженных систем линейных уравнений.
У этой проблемы много граней — от фундаментальных вопросов, касаюшихся внутренней сложности некоторых задач, до менее точно определенных вопросов, связанных с построением эффективных структур данных и составлением машинных программ. Чтобы ограничить объем книги и при этом не пожертвовать подробностью изложении, мы решили сузить ее предмет случаем симметричных положительно определенных систем уравнений.
Такие системы возникают очень часто в различных областях науки и инженерных приложениях По тем же причинам мы ограничиваемся разбором только одного конкретного метода в рамках каждого общего подхода к решению больших разреженных положительно определенных систем. Например, среди многих методов приближенной минимизации ширины ленты матрицы мы выбрали лишь один, который в нашей практике показал себя достаточно хорошо. Наша цель— познакомить читателя с важнейшими идеями, а вовсе не предложить метод, который обязательно будет самым эффективным для интересуюшей его конкретной задачи.
Мы надеемся, что, ознакомившись с книгой, читатель сможет вынести обоснован'-' ные суждения относительно прчменимости и полезности излагаемых в ней идей и методов решения разреженных систем. Характеристики алгоритмов для разреженных матриц могут очень сильно зависеть от качества их машинной реализации; сложность же реализации весьма различна для разных алгоритмов. Поэтому, хотя анализ алгоритмов для разреженных матриц с помощью карандаша и бумаги полезен, он отнюдь не достаточен.
Мы считаем, что изучение и использование подпрограмм, реализующих такие алгоритмы, является существенной составной частью хорошего вводного курса в эту важную область научных вычислений Исходя из этого, мы включили в книгу листинги фортранных подпрограмм и их подробное обсуждение. В Приложении А описана процедура доводки подпрограмм до состояния, при котором они полностью готовы к вводу в машину.
Мы благодарны Мэри Уонг за превосходное качество перепечатки первоначального варианта рукописи, а Энн Трип де Рош 8 Предисловие и Эзер Пант — за терпеливость при печатании многочисленных переделок. Мы признательны также многим нашим студентам за помощь в устранении ошибок, содержавшихся в ранних версиях книги. Особой благодарносзи заел>живают Хамза Рашваи и Эсмонд Нг, тщательно проверившие ее окончательный вариант. Написание книги заняло у иас много времени, которое иначе принадлежало бы нашим женам и детям. Мы благодарим своих жеи за терпение и понимание и посвящаем эту книгу им. Алая Джордж Джозеф Дю 1.
Введение $1.0. Об этой книге В нашей книге речь идет об эффективных машинных методах для решения больших разреженных систем линейных алгебраических уравнений. Предполагается, что читатель усвоил начала линейной алгебры и знаком со стандартными матричными обозначениями и операциями. Полезно было бы и знакомство с терминологией теории графов, однако оно не является обязательным, поскольку все необходимые понятия и обозначения будут нведены там, где они нужны. Это книга о аь<численалх, и в ней содержится ряд фортранных подпрограмм, предназначенных для изучения н использования.
Поэтому читатель должен хотя бы в некоторой мере владеть Фортраном, а в идеальном случае иметь доступ к вычислительной машине, с тем чтобы пропускать программы, использующие подпрограммы из этой книги. Успешность алгоритмов для разреженных матриц, возможно, более, чем в какой- либо другой области вычислений, зависит от качества их машинной реализации, т. е. машинной программы, исполняющей алгоритм. Реализация этих алгоритмов связана с использованием довольно сложных схем хранения, и степень сложности весьма различна для разных алгоритмов. Некоторые алгоритмы, очень привлекательные «на бумаге», совсем не таковы на практике вследствие усложненности и неэффективности их реализации.
Другие, теоретически не столь красивые алгоритмы могут оказаться более практичными, поскольку их реализация проста и требует лишь очень небольших чнакладных расходов». По этим и другим причинам, которые прояснятся позднее, мы включили в книгу фортранные подпрограммы, реализующие многие из обсуждаемых а ней алгоритмов. Мы приводим также результаты некоторых численных экспериментов, иллюстрирующие отмеченные выше проблемы реализации и дающие читателю некоторую информацию о времени и памяти, необходимых для вычислений с разреженными матрицами на типовой машине.
Подпрограммы были тщательно оттестированы; они написаны на машинно-независимом подмножестве Фортрана ()<убег !974) и без каких-либо изменений они должны правильно работать для большинства машинных систем. Они будут полезным 10 Гл ! Вьедение дополнением к библиотеке любого вычислительного центра, выполняющего научныс расчесы. У авторов можно получп|ь записанные на ленту копии подпрограмм вместе с тестовыми задачами, обсуждаемыми и используемыми в главе 9. Мы надеемся, что эта кни~а будет полезна по крайней мере в двух отношениях.
Во-первых, она может служи~ь учебником для студентов-старшекурсников и аспирантов факультетов прикладной и вычислительной математики, а также инженерных специальностей. Упражнения в конце каждой главы имеют целью проверку усвоения материала читателем, указание направлений дальнейшего исследования и конкретных важных задач. Некоторые упражнения требуют использования и/или модификации составленных нами программ, поэтому желательно иметь доступ к машине, оснащенной для работы на Фортране, с необходимыми программами в библиотеке. Книга должна послужить также полезным справочником для научных работников н инженеров, которым приходится решать задачи с большими положительно определенными матрицами.
Несмотря иа специальность рассматриваемого класса задач, существенная часть (а возможно, и большинство) линейных систем, возникающих в научных и инженерных расчетах, обладает этим свойством Это достаточно большой класс для того, чтобы заслуживать отдельного рассмотрения. Вдобавок, как мы увидим позже, решение задач с большими, разреженными положительно определенными матрицами коренным образом отличается от решения задач общего вида.
Характеристики
Тип файла DJVU
Этот формат был создан для хранения отсканированных страниц книг в большом количестве. DJVU отлично справился с поставленной задачей, но увеличение места на всех устройствах позволили использовать вместо этого формата всё тот же PDF, хоть PDF занимает заметно больше места.
Даже здесь на студизбе мы конвертируем все файлы DJVU в PDF, чтобы Вам не пришлось думать о том, какой программой открыть ту или иную книгу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
