Вычисл. матем. (курсовые ИТ-101) / Вычислительная математика / Полезные книги для выполнения курсовой / Эффективные алгоритмы выч матем / kniga / 1E_PAG

РОССИЙСКАЯ АКАДЕМИЯ НАУК

ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ

СЕВЕРО-ВОСТОЧНЫЙ НАУЧНЫЙ ЦЕНТР

СЕВЕРО-ВОСТОЧНЫЙ КОМПЛЕКСНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ

В. Ю. БЕЛАШОВ, Н.М. ЧЕРНОВА

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ И ПРОГРАММЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

Магадан 1997

УДК 681.3.06

Белашов В.Ю., Чернова Н.М. Эффективные алгоритмы и программы вы­чис­ли­тель­ной математики. Магадан: СВКНИИ ДВО РАН, 1997. 160 с.

В книге представлены результаты работы авторов по отбору наиболее эффек­тивных (оп­ти­мальных) алгоритмов, реализующих методы как традиционных, так и практически не встре­ча­ю­щих­ся в монографической и справочной литературе разделов вычислительной математики, на­при­мер вычисли­тель­ные методы в теории чисел, комбинаторике, теории спецфункций, те­о­рии спектральных пре­об­ра­зо­ва­ний и т.п. Каждый тематический раздел включает краткое введение в теорию с постулированием ос­нов­ных положений и серию оптимальных алгоритмов, ре­а­ли­зу­ю­щих тот или иной метод, с подробными комментариями и примерами тестовых расчетов. В книге более 200 текстов процедур, написанных на языке Turbo Pascal.

Для специалистов, работа которых связана с решением задач на ЭВМ, аспирантов и сту­ден­тов вузов по рекомендации Министерства общего и профессионального образования Российской Федерации.

Табл. 90. Ил. 25. Библиогр.: 97 назв.

Ответственный редактор

доктор физико-математических наук В.Н.Доровский

Утверждено к печати Ученым советом СВКНИИ ДВО РАН

Belashov V.Yu., Chernova N.M. Effective algorithms and programs of applied mathematics. Magadan: NEISRI FEB RAS, 1997. 160 р.

This book is a result of selection of the most effective (optimum) algorithms realizing the methods of traditional topics and nontraditional ones which are not found in the monograph and reference books (for example, calculational methods in the number theory, combinatorics, the theory of mathematical functions and theory of orthogonal transforms etc.). Each subject section includes brief summary of the theory with postulating of main principles and a number of optimum algorithms being provided with the detail comments and the examples of their testing. The book includes more than 200 procedures written in Turbo Pascal.

Ó Белашов В.Ю., Чернова Н.М., 1997 г.

ISBN 5-7442-1013-Х Ó СВКНИИ ДВО РАН, 1997 г.

Ó СВНЦ ДВО РАН, 1997 г.

Ó Оформление оригинал-макета Черновой Н.М., 1997 г.

ОГЛАВЛЕНИЕ Предисловие	7
Глава 1. Численные методы алгебры	9
§ 1. Элементарная алгебра	9
1.1. Комплексная арифметика. Извлечение корней n-й степени из ком­плек­с­но­го числа	9
1.2. Комбинаторика. Бином Ньютона и родственные формулы	10
1.3. Вычисление символа Якоби	12
1.4. Разложение многочлена на множители	13
1.5. Вычисление корней полиномов с целыми коэффициентами в форме прос­тых дробей	14
§ 2. Решение нелинейных алгебраических уравнений с одной переменной	15
2.1. Задача отделения корней. Уточнение корней методом половинного де­ле­ния (метод дихотомии)	15
2.2. Приближенное решение уравнения F(x)=0 методом хорд (секущих)	18
2.3. Приближенное решение уравнения F(x)=0 методом касательных (Нью­то­на)	20
2.4. Приближенное решение уравнения F(x)=0 комбинированным методом (хорд и касательных)	22
2.5. Приближенное решение уравнения F(x)=0 методом итераций	23
2.6. Приближенное решение уравнения F(x)=0 методом парабол	25
2.7. Методы ускорения сходимости	27
§ 3. Методы решения систем линейных и нелинейных уравнений	28
3.1. Метод исключения Гаусса для систем линейных уравнений	28
3.2. Метод главных элементов	31
3.3. Решение систем нелинейных уравнений методом Ньютона	32
3.4. Решение систем линейных уравнений методом квадратного корня	35
3.5. Решение систем линейных уравнений методом итераций	36
3.6. Решение систем линейных уравнений методом Зейделя	37
§ 4. Алгебра матриц	38
4.1. Вычисление собственных векторов и собственных значений матриц по методу Кры­лова	39
4.2.Вычисление собственных векторов и собственных значений матриц по методу Данилевского	42
4.3. Вычисление собственных векторов и собственных значений сим­мет­ри­чес­кой матрицы методом Якоби	47
4.4. Задача обращения матриц и вычисления главного определителя по схеме Гаусса	49
4.5. Обращение симметрической матрицы методом квадратных корней	50
4.6. Обращение матрицы и решение системы линейных алгебраических урав­не­ний	51
4.7. Умножение уплотненной симметрической матрицы на пря­мо­у­голь­ную	53
4.8. Корректировка обратной матрицы после изменения одного элемента в пря­мой матрице	53
4.9. Матрица причинно-следственных отношений	54
Глава 2. Интерполирование и экстраполирование функций	55
§ 1. Построение интерполяционного полинома Лагранжа по заданным зна­че­ниям функции	55

§ 2. Построение интерполяционного полинома Ньютона по заданным зна­че­ниям функции	57
§ 3. Интерполяция по Эйткену	60
§ 4. Интерполяция функции кубическими сплайнами	60
§ 5. Тригонометрическая интерполяция	64
§ 6. Полиномиальная аппроксимация производных любого порядка таб­ли­ч­но за­дан­ной функции	65
Глава 3.Численное дифференцирование и интегрирование	67
§ 1. Численное дифференцирование с помощью интерполяционных фор­мул Нью­то­на и Лагранжа	67
§ 2. Численное интегрирование по простейшим формулам	69
§ 3. Вычисление определенного интеграла методом Симсона	71
§ 4. Интегрирование квадратурными формулами Ньютона - Котеса и мето­дом “три вось­мых”	72
§ 5. Интегрирование с автоматическим выбором количества узлов методом Рунге	74
§ 6. Интегрирование с автоматическим выбором количества узлов	75
§ 7. Вычисление интеграла по Ромбергу	76
§ 8. Интерполяция, дифференцирование и интегрирование функций в одной про­цедуре	78
§ 9. Вычисление комплексного криволинейного интеграла	79
Глава 4.Приближенные методы интегрирования обыкновенных дифференциальных урав­нений и систем	81
§ 1. Приближенное решение обыкновенного дифференциального уравнения ме­то­дом Эй­ле­ра	81
§ 2. Приближенное решение обыкновенного дифференциального уравнения ме­то­дом Эй­ле­ра с уточнением	82
§ 3. Приближенное решение обыкновенного дифференциального уравнения ме­то­дом Адам­са	84
§ 4. Приближенное решение обыкновенного дифференциального уравнения ме­то­дом Рун­ге - Кутта	86
§ 5. Приближенное решение обыкновенного дифференциального уравнения ме­то­дом про­гон­ки	87
Глава 5.Специальные функции и алгоритмы их вычисления	90
§ 1. Гамма-функция и связанные с ней функции	90
§ 2. Некоторые интегральные функции	94
§ 3. Неполные эллиптические интегралы I и II рода	97
§ 4. Полные эллиптические интегралы I и II рода	97
§ 5. Функции Бесселя целого порядка	98
§ 6. Модифицированные функции Бесселя	103

§ 7. Функции Бесселя дробного порядка	107
Глава 6. Математическая обработка экспериментальных данных (введение в ма­те­ма­ти­чес­кую статистику)	110
§ 1. Основные понятия математической статистики	110
§ 2. Математические оценки экспериментальных данных. Проверка гипотезы нор­маль­ного распределения	110
§ 3. Классификация по одному признаку	115
3.1. Введение. Типы факторов	115
3.2. Классификация по одному признаку с разным количеством наблюдений	115
3.2.1. Равное число наблюдений	115
3.2.2. Неравное число наблюдений	116
3.3. Пример проверки гипотезы	116
3.4. Рациональные схемы вычислений	117
§ 4. Классификация по нескольким признакам	117
4.1. Двустороняя классификация с повторениями	117
4.2. Удобные вычислительные формулы	118
4.3. Иерархическая классификация по двум признакам	119
4.4. Многосторонняя классификация с повторениями	119
4.5. Рациональные вычислительные схемы для табл. 6.10	120
§ 5. Некоторые вопросы преобразования данных	121
Глава 7. Математическая обработка экспериментальных данных (введение в ре­гре­с­си­он­ный и корреляционный анализ)	122
§ 1. Эмпирические линейные зависимости	122
1.1. Методы построения линейных зависимостей и уточнение их параметров	122
1.2. Вычислительный алгоритм, процедуры и формальные параметры	123
1.3. Контрольный пример	124
§ 2. Выбор эмпирических формул для анализа нелинейных зависимостей	125
§ 3. Преобразование нелинейной зависимости в линейную методом пре­об­ра­зо­ва­ни­я­ ко­ординат	127
§ 4. Гармонический анализ экспериментальных данных	128
§ 5. Корреляционный анализ экспериментальных данных	130
5.1. Построение корреляционной матрицы	130
5.2. Вычислительный алгоритм, процедуры и формальные параметры	131
5.3. Контрольный пример	131
Глава 8. Математическая обработка экспериментальных данных (специальные методы ана­лиза)	133
§ 1. Анализ корреляционной матрицы методом корреляционных плеяд	133
§ 2. Метод Буркова	135
§ 3. Анализ корреляционной матрицы методом корреляционных профилей	136
§ 4. Метод главных компонент (многофакторный анализ)	137
Глава 9. Математическая обработка экспериментальных данных (спектральный анализ вре­менных рядов)	149

§ 1. Тестирование временных рядов на стационарность	149
§ 2. Спектральный анализ временных рядов	151
2.1. Ряд Фурье, преобразование Фурье, алгоритм БПФ	151
2.2. Вычисление амплитудного спектра, спектра мощности и фазового спектра ме­то­дом БПФ	154
2.3. Вычисление корреляционных последовательностей и свертки методом БПФ	155
2.4. Синтез сигналов с помощью БПФ	157
Литература	158

ПРЕДИСЛОВИЕ

В настоящее время существует обширная литература, в которой рассматриваются отдельные раз­делы вы­чис­ли­тель­ной математики (численное интегрирование, в том числе интегрирование как обык­новенных диф­ференциальных уравнений, так и уравнений в частных производных, численное диф­фе­рен­ци­ро­вание, методы решения задач линейной алгебры, обработ­ка данных эксперимента и пр.). Од­на­ко все известные издания посвящены либо из­ло­жению теоретических ас­пектов со­от­вет­ст­ву­ю­щих разделов вы­числительной математики, т.е. в них отсутствуют ука­зания на конкретные прило­же­ния и практически не включены примеры конкретных ал­го­рит­мов и текстов программ (не говоря уже о примерах тестовых расчетов), либо представляют со­бой сборники чисто алгоритмов и про­грамм без какого бы то ни было, пусть элементарного, вве­дения в теорию используемых методов вы­чис­лений. Все это создает ис­кус­ствен­ный барьер между специалистами в области вычислительной ма­тематики и поль­зо­ва­те­лями не математиками, которым по роду своей деятельности в той или иной сфере (ес­тес­твен­ные и экономические науки, техника, система образования и т.п.) приходится ре­шать зада­чи с помощью соответствующих методов вычислений.

К сожалению, в литературе часто не уделяется вни­мание уже разработанным и признанным весьма эффективными алгоритмам, кото­рые широко ис­поль­зовались для решения прикладных задач на ЭВМ серий ЕС и БЭСМ.

Отметим также, что практически отсутствует специальная литература (включаю­щая как те­о­­ре­ти­ческие аспекты методов, так и примеры программ), посвященная наиболее эффективным и оп­ти­маль­ным с точки зрения затрат машинного времени и памяти ЭВМ алгоритмам и до­ступ­ная ши­ро­ко­му кругу пользователей. Справоч­ники или слишком элементарны (на­пи­са­­­ны на уровне первых версий языка Бейсик и про­­грам­мируемых микрокалькуляторов) или со­дер­­жат описание методов и примеры про­грамм лишь по отдельным разделам вычислительной ма­­те­ма­тики. Этими же недостатками стра­да­ет как переводная, так и ори­ги­наль­ная иностранная литература, не говоря уже о раз­ра­­бот­ках ино­стран­ных фирм (к сожалению, малодо­ступ­ных широкому кру­гу отечественных поль­зо­ва­те­­лей).

Авторы сделали попытку в той или иной мере устранить от­ме­чен­ные недостатки путем сис­те­ма­ти­зированного изложения алгоритмов с краткими предварительными сведениями по теории ис­поль­зу­емых мето­дов по всем, включенным в издание, раз­делам вычислительной математики.

Наряду с наиболее эффективными алгоритмами, разработанными в последнее вре­мя, книга со­дер­жит оригинальные полученные авторами результаты. Что касается алгоритмов, раз­ра­бо­тан­ных дру­­гими специалистами, то при подготовке на­стоящего издания их тща­тель­но отбирали, учи­ты­вая эф­­фек­тивность, оп­тимальность (оценка проводилась по скорости получения результатов и за­тратам ре­сур­сов ЭВМ). Мы повторили тестирование на персональных компьютерах типа IBM PC и вы­пол­ни­ли ре­­ше­ние контрольных примеров для широкого диапазона входных параметров.

Основное содержание книги составляют лекционные курсы “Численные методы”, “Вы­чис­ли­тель­ная математика” и “Вычислительная физика”, которые авторы читают в течение по­след­­них пяти лет в Международном педагогическом университете г.Магадана для студентов фи­зи­­ко-ма­те­ма­ти­чес­кого факультета и аспирантов соответству­ющих специальностей. О развитии ме­тодов вы­числительной математики и построения алгоритмов чис­ленного решения при­клад­ных задач мы не­од­но­кратно докладывали на различных оте­чественных и международных кон­ференциях и симпозиумах.

Материал разбит на тематические разделы, соответствующие традици­онно вы­деляемым об­ластям с включением таких, практически не встречающихся в из­даниях по­доб­но­го плана раз­де­лов, как, например, вычислительные методы в теории чи­сел, комбинаторике, те­о­рий спец­фун­к­ций и спектральных преобразований и т.п. Каждый тематический раздел со­дер­жит крат­кое вве­де­ние в теорию с постулировани­ем основных положений (поэтому в книге от­сут­ст­ву­ет такой раз­дел, как общее вве­­­дение) и серию оптимальных алгоритмов с их про­грам­мной ре­а­ли­­з­а­цией на языке Turbo Pascal того или иного метода с подробными ком­мен­тариями и при­мерами тестовых расчетов.

Хотелось бы отметить, что мы стара­лись построить книгу так, что­бы поль­зо­ватель, работающий в конкретной предметной области и не являющийся специалистом не­по­сред­ственно в вы­чис­ли­тель­ной матема­тике, мог без особого труда выбрать наиболее эффектив­ный метод численного решения сво­ей задачи. И, наконец, ав­то­ры надеются, что ме­то­дика подбора и изложения материала позволит спе­­циалистам использовать это из­да­ние в каче­стве на­стольной кни­ги-справочника по эффективным ал­горитмам и про­грам­­мам вычислительной математики.

Главы 1-3 написаны авторами совместно, главы 4, 6-8 - Н.М.Черновой, предисловие, гла­вы 5, 9 и заключение - В.Ю.Белашовым. Работа по отбору, написанию и тестированию алго­рит­мов про­во­ди­лась соответственно.

Авторы выражают свою признательность Л.И.Из­май­­ло­ву за поддержку, без которой пуб­ли­кация книги вряд ли бы­ла бы воз­мож­ной, а также М.А.Трум­­пе за техничес­кую помощь в под­го­товке графического материала.