Небольшая книга датских специалистов, отражающая опыт разработки программ для разреженных несимметричных систем. Авторы сосредоточили внимание на «скандинавском» варианте решения задачи, подробно обсуждают возможности его применения. Много внимания уделено деталям разреженной технологии — динамическим структурам хранения, организации выбора главного элемента.

Для математиков-прикладников, для разработчиков программ, для студентов и аспирантов университетов.

Небольшая книга датских математиков О. Эстербю и 3. Златева излагает современный подход к программной реализации метода Гаусса для разреженных несимметричных линейных систем. Она не пересекается с другими известными советскому читателю книгами той же тематики: ни с книгой: Р. Тьюарсон. Разреженные матрицы (М.: Мир, 1977), где описана технология, популярная в 60-е годы; ни с недавней книгой: Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений (М.: Мир, 1984), целиком сосредоточенной на симметричном положительно определённом случае.

Есть по меньшей мере два принципиальных момента, которые усложняют программирование метода Гаусса для несимметричных систем по сравнению с системами симметричными и знакоопределёнными — различие схем хранения и проблема роста элементов. Для знакоопределённых систем разумную — в смысле сохранения разреженности — последовательность исключения можно определить, не зная числовых значений элементов матрицы и оперируя только с её графом. Найдя эту последовательность, выяснив, где появятся новые ненулевые элементы — так называемое заполнение, — и зарезервировав для них место, реальное исключение можно проводить при статичной схеме хранения. В несимметричном случае для достижения численной устойчивости приходится накладывать ограничения на относительную величину главных элементов. В результате априорный выбор порядка исключения становится невозможным, что заставляет обращаться к динамическим структурам.

Качество вычисляемого решения может пострадать, если в процессе исключения некоторые элементы матрицы сильно возрастают по сравнению с уровнем элементов, исходной системы. Для положительно определённой матрицы роста элементов не происходит, какова бы ни была последовательность исключения; в несимметричном же случае (и в особенности для разреженных матриц, где требования к величине главного элемента не так строги) контроль роста необходим.

Сказанное, вероятно, объясняет, почему сложно создавать программы метода Гаусса для разреженных несимметричных систем. Отметим, например, что описание одной из наиболее авторитетных современных программ для этого класса систем, а именно программы MA28 английской школы, вылилось в пухлую брошюру объёмом в 150 страниц (содержащую, правда, и текст программы). Описание (уже без текста) другой известной программы Y12M (одним из разработчиков является 3. Златев) составило том 121 шпрингеровской серии «Lecture Notes in Computer Science», где опубликована в оригинале и данная книга.

Авторы представляют весьма активную датскую школу программирования разреженных систем, для подхода которой характерна большая роль, отводимая итерационному уточнению. То, что этот процесс позволяет — даже для не слишком хорошо обусловленных систем — получать решения практически с полной машинной точностью, давно известно из практики случая плотных систем. Его минусы — увеличение требований к памяти (нужно хранить коэффициенты исходной системы) и некоторое (не очень, впрочем, значительное) увеличение времени счёта. Неожиданно оказывается, что для многих разреженных систем применению итерационного уточнения сопутствуют как повышение точности, так и сокращение памяти и вычислительной работы. Почему это так, читатель узнает из книги; здесь мы не будем раскрывать её секрета.

В книге суммирован многолетний опыт датских специалистов, накопленный в процессе создания ряда программ для разреженных систем. Составлена она таким образом, что первые четыре её главы можно рассматривать как пособие для начинающих разработчиков программ для разреженных систем. Особняком стоит пятая глава. Здесь авторы задались целью показать, что техника, использованная ими при реализации метода Гаусса, имеет более широкую область приложений; например, аналогичным образом можно реализовать ряд известных прямых алгоритмов для линейных задач метода наименьших квадратов. На мой взгляд, принятая в этой главе форма изложения затрудняет понимание самого по себе довольно очевидного тезиса. К тому же предполагается, что читатель знаком с упомянутыми алгоритмами. Лицам, заинтересованным в содержании гл. 5, можно рекомендовать в качестве предварительного чтения мой обзор «Разреженные линейные задачи метода наименьших квадратов» («Итоги науки и техники», серия «Математический анализ», т. 23).

ПРЕДИСЛОВИЕ ПЕРЕВОДЧИКА
X. Икрамов

Книги на ту же тему

1. Прикладные итерационные методы, Хейгеман Л., Янг Д., 1986
2. Технология разреженных матриц, Писсанецки С., 1988
3. Итерационные методы для разреженных линейных систем: Учебное пособие. — В 2-х томах. Том 1, Саад Ю., 2013
4. Численное решение больших разреженных систем уравнений, Джордж А., Лю Д., 1984
5. Разреженные матрицы, Тьюарсон Р., 1977
6. Численные методы для симметричных линейных систем: Прямые методы, Икрамов Х. Д., 1988
7. Численное решение систем линейных алгебраических уравнений, Форсайт Д., Моулер К., 1969
8. Вычислительная линейная алгебра. Теория и приложения, Деммель Д., 2001
9. Матрицы и вычисления, Воеводин В. В., Кузнецов Ю. А., 1984
10. Теория матриц. — 3-е изд., Гантмахер Ф. Р., 1967
11. Матричный анализ, Хорн Р., Джонсон Ч., 1989
12. Основы линейной алгебры и некоторые её приложения. Учебное пособие, Блох Э. Л., Лошинский Л. И., Турин В. Я., 1971
13. Введение в алгебру. Часть II. Линейная алгебра: Учебник для вузов. — 3-е изд., Кострикин А. И., 2004
14. Основы линейной алгебры. — 3-е изд., перераб., Мальцев А. И., 1970
15. Определители и матрицы. — 2-е изд., Боревич З. И., 1970
16. Сборник задач по линейной алгебре. — 5-е изд., стереотип., Проскуряков И. В., 1974
17. Разностные схемы газовой динамики, Самарский А. А., Попов Ю. П., 1975
18. Устойчивость разностных схем, Самарский А. А., Гулин А. В., 1973
19. Вычислительные методы решения прикладных граничных задач, На Ц., 1982
20. Вычислительные методы в физике, Поттер Д., 1975
21. Введение в вычислительную физику: Учебное пособие: Для вузов, Федоренко Р. П., 1994
22. Введение в метод конечных элементов, Норри Д., де Фриз Ж., 1981
23. Введение в численные методы решения дифференциальных уравнений, Ортега Д., Пул У., 1986
24. Численное решение задач гидромеханики, Рихтмайер Р., ред., 1977
25. Численные методы анализа: Приближение функций, дифференциальные и интегральные уравнения, Демидович Б. П., Марон И. А., Шувалова Э. З., 1963
26. Численные методы. — 3-е изд., доп. и перераб., Бахвалов Н. С., Жидков Н. П., Кобельков Г. М., 2004
27. Методы вычислительной математики, Марчук Г. И., 1977
28. Численные методы для научных работников и инженеров. — 2-е изд., испр., Хемминг Р. В., 1972
29. Численные методы для научных работников и инженеров, Хемминг Р. В., 1968