КнигоПровод.Ru29.03.2024

/Наука и Техника/Математика

Прямые методы для разреженных матриц — Эстербю О., Златев З.
Прямые методы для разреженных матриц
Научное издание
Эстербю О., Златев З.
год издания — 1987, кол-во страниц — 120, тираж — 9000, язык — русский, тип обложки — мягк., масса книги — 140 гр., издательство — Мир
КНИГА СНЯТА С ПРОДАЖИ
Сохранность книги — хорошая

Lecture Notes in Computer Science
Edited by G. Goos and J. Hartmanis
157
OLE ØSTERBY
ZAHARI ZLATEV
DIRECT METHODS
FOR SPARSE MATRICES


Springer-Verlag, 1983

Пер. с англ. Х. Д. Икрамова

Формат 60x90 1/16. Бумага книжно-журнальная. Печать высокая
ключевые слова — разреженн, линейн, численн, гаусс, знакоопределённ, матриц, графов, ma28, y12m, итерац, обусловленн, вычислител, марковиц, gms, k-шагов, двухшагов

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

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


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

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

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

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

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

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

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

ОГЛАВЛЕНИЕ

Предисловие переводчика5
Предисловие7
 
Глава 1. Введение10
 
1.1. Гауссово исключение10
1.2. Разреженные матрицы13
1.3. Тестовые матрицы14
1.4. Пример19
1.5. Содержание глва 2—519
 
Глава 2. Методы хранения21
 
2.1. Требования к входной информации21
2.2. Переупорядочение структуры22
2.3. Процесс исключения28
2.4. Хранение заполнения31
2.5. Сборка мусора35
2.6. О хранении матрицы38
2.7. Классификация задач39
2.8. Сравнение упорядоченных и связных списков42
 
Глава 3. Стратегия выбора главного элемента45
 
3.1. Для чего переставлять строки и столбцы?45
3.2. Стратегия Марковица46
3.3. Обобщённая стратегия Марковица (GMS)47
3.4. Улучшенная обобщённая стратегия Марковица (GMS)50
3.5. Реализация стратегии выбора56
3.6. Другие стратегии58
 
Глава 4. Интерационное уточнение60
 
4.1. Сходимость итерационного уточнения60
4.2. Барьер62
4.3. Сравнение требований к памяти63
4.4. Время счёта67
4.5. Выбор барьера и коэффициента устойчивости70
4.6. Когда и как пользоваться итерационным уточнением73
4.7. Итерационное уточнение и задачи наименьших квадратов75
4.8. Оценка числа обусловленности79
4.9. Робастность и надёжность79
4.10. Заключительные замечания об итерационном уточнении и барьерах82
 
Глава 5. Другие прямые методы83
 
5.1. Линейные задачи метода наименьших квадратов83
5.2. Общий k-шаговый прямой метод84
5.3. Специальные случаи общего метода88
5.4. Обобщённое итерационное уточнение91
5.5. Ортогональные преобразования95
5.6. Стратегия выбора главного элемента99
5.7. Двухшаговый метод, основанный на ортогональных преобразованиях102
5.8. Численные результаты103
 
Приложение: программы, упоминаемые в тексте107
Список обозначений110
Литература111

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

  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

© 1913—2013 КнигоПровод.Ruhttp://knigoprovod.ru