Полищук А.П., Семериков С.А.

Методы вычислений в классах языка С++: Учебное пособие. – Кривой Рог: Издательский отдел КГПИ, 1999. – 350 с., ил.

Учебное пособие содержит классический вузовский набор алгоритмов вычислительной математики, ориентированных на программную реализацию средствами языка С++. Использование объектно-ориентированной методологии значительно облегчает усвоение курса за счет расширения языка новыми типами данных (векторы, полиномы, матрицы и др.), приближающих программную запись к естественной математической.

Для студентов высших учебных заведений, аспирантов, научных и инженерно-технических работников.

ISBN 5-7763-2587-0

Рецензенты:

А.Н. Марюта – д-р техн. наук, проф., заведующий кафедрой экономической кибернетики Днепропетровского государственного университета

А.И. Олейников – д-р. физ.-мат. наук, проф., заведующий кафедрой математики Криворожского государственного педагогического института

© А.П. Полищук, С.А. Семериков, 1999

Оглавление

0. Введение................................................................................ 8

0.1. Приближенные вычисления............................................ 8

0.2. Численные методы и программирование...................... 9

0.3. Особенности машинных вычислений.......................... 14

0.4. Структура учебного пособия....................................... 17

1. Специальные классы математических объектов и операции над ними 20

1.1. Комплексные числа....................................................... 20

1.1.1. Основные понятия.................................................. 20

1.1.2. Операции над комплексными числами.................. 21

1.1.2.1. Операции сравнения......................................... 21

1.1.2.2. Алгебраические операции................................ 21

1.1.2.2.1. Сложение и вычитание............................... 21

1.1.2.2.2. Умножение................................................. 21

1.1.2.2.3. Деление....................................................... 21

1.1.2.2.4. Возведение в степень (формула Муавра). 22

1.1.3. Определение программного класса комплексных чисел 22

1.2. Векторы......................................................................... 26

1.2.1. Основные понятия.................................................. 26

1.2.2. Определение программного класса многомерных векторов 29

1.3. Полиномы...................................................................... 50

1.3.1. Общие сведения...................................................... 50

1.3.2. Операции над полиномами.................................... 52

1.3.3. Вычисление значений полиномов.......................... 53

1.3.4. Вычисление корней полиномов............................. 54

1.3.5. Определение программного класса полиномов.... 56

2. Матрицы и задачи линейной алгебры................................ 88

2.1. Общие сведения о матрицах и матричных операциях 88

2.2. Методы решения основных задач линейной алгебры. 92

2.2.1. Методы решения систем линейных алгебраических уравнений (СЛАУ) 93

2.2.1.1. Метод Гаусса для решения СЛАУ, вычисления определителей и обращения матриц 94

2.2.1.2. Предварительная факторизация матриц (разложение в произведение двух матриц) в задачах решения СЛАУ.............................................................. 96

2.2.1.2.1. Факторизация матриц по методу Холецкого 96

2.2.1.3. Метод ортогонализации для решения СЛАУ. 98

2.2.1.4. Итерационные методы решения СЛАУ........ 100

2.2.1.4.1. Проблема сходимости итерационных методов 100

2.2.2. Методы вычисления собственных значений матриц 102

2.2.2.1. Метод неопределенных коэффициентов....... 103

2.2.2.2. Метод Данилевского...................................... 103

2.2.2.3. QR-алгоритм для несимметрических матриц 105

2.2.2.4. Метод Леверрье-Фаддеева............................. 107

2.2.2.5. Итерационный степенной метод................... 108

2.2.2.6. Метод Крылова............................................... 109

2.2.3. Метод наименьших квадратов (МНК)................. 110

2.3. Программная реализация матричного класса........... 115

2.3.1. Общее описание структуры матричного класса. 115

2.3.2. Интерфейсный файл реализации матричного класса matrix.h 137

2.4. Программная реализация методов вычисления собственных значений и собственных векторов матриц............................................................................................. 161

2.4.1. Метод неопределенных коэффициентов............. 161

2.4.2. Программная реализация метода Крылова вычисления собственных значений 164

2.4.3. Метод Леверрье-Фаддеева вычисления коэффициентов характеристического полинома 166

2.5. Элементы линейного программирования.................. 167

2.5.1. Общая постановка задачи.................................... 167

2.5.2. Примеры задач линейного программирования... 168

2.5.2.1. Задача о пищевом рационе............................ 168

2.5.2.2. Задача о распределении ресурсов................. 168

2.5.2.3. Задача планирования перевозок (транспортная задача) 169

2.5.3. Симплекс-метод решения задачи линейного программирования 170

2.5.3.1. Приведение системы к стандартной, удобной для преобразований форме 171

2.5.3.2. Алгоритм замены базисных переменных...... 171

2.5.3.3. Алгоритм поиска опорного решения ОЗЛП. 172

2.5.3.3.1. Алгоритм выбора разрешающего элемента для приближения к опорному решению 172

2.5.3.4. Алгоритм поиска оптимального решения..... 173

2.5.4. Транспортная задача линейного программирования 173

2.5.4.1. Общие сведения.............................................. 173

2.5.4.2. Формирование опорного плана..................... 176

2.5.4.3. Циклические переносы перевозок для улучшения плана 176

2.5.4.4. Метод потенциалов........................................ 177

2.5.5. Транспортная задача при небалансе запасов и заявок 179

2.5.6. Транспортная задача с временным критерием... 180

2.6. Программная реализация задач линейного программирования 181

2.6.1. Симплекс-метод решения ОЗЛП......................... 181

2.6.2. Программная реализация метода решения транспортной задачи 189

3. Аналитическое приближение функций, заданных таблично 198

3.1. Общая постановка задачи........................................... 198

3.2. Общая методика решения задач аппроксимации...... 201

3.2.1. Алгебраическая интерполяция............................. 203

3.2.1.1. Классический интерполяционный полином.. 203

3.2.1.2. Метод интерполяции Лагранжа..................... 203

3.2.1.3. Интерполяционный полином Ньютона......... 205

3.2.1.4. Интерполяция сплайнами.............................. 208

3.2.1.5. Аппроксимация функций по методу наименьших квадратов 212

3.2.2. Программная реализация класса аппроксимирующих функций 213

4. Численное интегрирование и дифференцирование табличных функций 220

4.1. Численное интегрирование......................................... 220

4.1.1. Вычисление определенных интегралов............... 220

4.1.1.1. Классификация методов................................. 220

4.1.2. Программная реализация методов численного интегрирования 225

4.2.Численное дифференцирование.................................. 227

5. Введение в численные методы решения дифференциальных уравнений 231

5.1. Обыкновенные дифференциальные уравнения (общие сведения) 231

5.2. Процессы как объект исследования и управления.... 232

5.3. Операционное исчисление и его применение к исследованию динамики линейных систем 241

5.3.1. Общие сведения.................................................... 241

5.3.1.1. Правила операционного исчисления............. 243

5.3.2. Решение линейных уравнений с постоянными коэффициентами 245

5.3.2.1. Передаточные функции линейных динамических систем 248

5.3.2.2. Частотные характеристики динамических систем 251

5.3.2.3. Фазовые портреты динамических систем..... 252

5.3.2.4. Ограничения области применения символического метода 252

5.3.3. Программная реализация класса символического метода 253

5.4. Конечно-разностные методы решения задачи Коши для линейных и нелинейных ОДУ 283

5.4.1. Одношаговые методы........................................... 284

5.4.1.1. Метод Эйлера................................................. 285

5.4.1.2. Методы Рунге-Кутта 2-го порядка................ 286

5.4.1.3. Метод Рунге-Кутта 4-го порядка................... 288

5.4.2. Многошаговые методы (методы Адамса)........... 289

5.4.3. Проблема устойчивости....................................... 292

5.4.4. Программная реализация численных методов решения задачи Коши 294

5.5. Двухточечные краевые задачи................................... 300

5.5.1. Метод конечных разностей для линейных краевых (граничных) задач 300

5.5.2. Метод стрельбы для граничных задач................ 303

5.5.3. Программная реализация класса граничных задач 306

6. Численные методы решения систем нелинейных уравнений (СНУ) и поиска экстремумов функций 310

6.1. Общая постановка задачи........................................... 310

6.2. Решение нелинейных уравнений................................ 311

6.2.1. Функция одной переменной при отсутствии помех 311

6.2.1.1. Методы последовательного сокращения интервала неопределенности 312

6.2.1.2. Рекуррентные методы уточнения текущей оценки значения корня 315

6.2.2. Уточнение корня функции одной переменной в условиях помех 316

6.2.2.1. Методы стохастической аппроксимации...... 316

6.3. Методы поиска экстремума функций......................... 317

6.3.1. Унимодальные функции одного аргумента при отсутствии помех 317

6.3.1.1. Метод дихотомии........................................... 317

6.3.1.2. Метод Фибоначчи.......................................... 317

6.3.1.3. Метод золотого сечения................................ 318

6.3.2. Многомерный поиск экстремума......................... 319

6.3.2.1. Метод координатного спуска........................ 319

6.3.2.2. Метод градиента (наискорейшего спуска или крутого восхождения или метод Бокса-Уилсона) 320

6.3.2.3. Последовательный симплексный поиск (ПСМ) субоптимальной области в многомерном пространстве................................................................ 322

6.3.2.3.1. Вводные замечания.................................. 322

6.3.2.3.2. Алгоритм последовательного симплексного метода 324

6.3.2.3.3. Подготовительные операции................... 324

6.3.2.3.4. Алгоритм поиска...................................... 326

6.3.2.3.5. Преимущества метода............................. 326

6.3.2.3.6. Недостатки метода................................... 327

6.4. Программная реализация класса подпрограмм для поиска экстремума унимодальных в заданном интервале функций одной переменной............................. 327

6.5. Программная реализация класса подпрограмм для многомерного поиска экстремума унимодальных функций.............................................................................. 334

Приложение. Как переносить данные в Ехсеl и отображать графики зависимостей 342

Литература............................................................................. 346