УДК 681.3.06(075.8)

ББК 32.973.26-018.2я73

У80

Устинов, С. М.

У80 Вычислительная математика / С. М. Устинов, В. А. Зимницкий. — СПб.:

БХВ-Петербург, 2009. — 336 с.: ил. — (Учебное пособие)

ISBN 978-5-9775-0318-1

Изложены аппроксимация функций и смежные вопросы, задачи линейной алгебры, нелинейные уравнения и системы, методы решения дифференциальных

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

Для студентов, аспирантов, преподавателей технических вузов и инженеров УДК 681.3.06(075.8) ББК 32.973.26-018.2я Рецензенты:

Козлов В. Н., д. т. н., профессор, проректор Санкт-Петербургского государственного политехнического университета (СПбГПУ) Александров А. М., д. т. н., профессор, зам. начальника Центра анализа и экспертизы ФГУП НПО «Импульс»

Группа подготовки издания:

Главный редактор Екатерина Кондукова Зам. главного редактора Татьяна Лапина Зав. редакцией Григорий Добин Редактор Анна Кузьмина Компьютерная верстка Натальи Смирновой Корректор Виктория Пиотровская Оформление обложки Елены Беляевой Зав. производством Николай Тверских Лицензия ИД № 02429 от 24.07.00. Подписано в печать 28.08.08.

Формат 701001/16. Печать офсетная. Усл. печ. л. 27,09.

Тираж 2000 экз. Заказ № "БХВ-Петербург", 194354, Санкт-Петербург, ул. Есенина, 5Б.

Санитарно-эпидемиологическое заключение на продукцию № 77.99.60.953.Д.003650.04. от 14.04.2008 г. выдано Федеральной службой по надзору в сфере защиты прав потребителей и благополучия человека.

Отпечатано с готовых диапозитивов в ГУП "Типография "Наука" 199034, Санкт-Петербург, 9 линия, © Устинов С. М., Зимницкий В. А., ISBN 978-5-9775-0318- Оглавление ВВЕДЕНИЕ

ГЛАВА 1. АППРОКСИМАЦИЯ ФУНКЦИЙ И СМЕЖНЫЕ ВОПРОСЫ

1.1. Общие сведения

1.2. Постановка задачи интерполирования

1.3. Интерполяционный полином Лагранжа. Остаточный член полинома Лагранжа

1.4. Выбор узлов интерполирования

1.5. Интерполяционный полином Ньютона для равно- и неравноотстоящих узлов

1.6. Интерполирование сплайнами

1.7. Интерполяционный полином Эрмита

1.8. Обратная интерполяция

1.9. Простейшие квадратурные формулы

1.9.1. Составные квадратурные формулы

1.9.2. Погрешности составных формул

1.10. Общий подход к построению квадратурных формул. Метод неопределенных коэффициентов

1.10.1. Квадратурные формулы Ньютона — Котеса

1.10.2. Квадратурные формулы Чебышева

1.10.3. Квадратурные формулы Гаусса

1.11. Адаптивные квадратурные формулы. Программа QUANC8

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

1.12.1. Влияние погрешности задания функции на точность

1.13. Среднеквадратичная аппроксимация функций. Постановка задачи......... 1.13.1. Дискретный случай. Весовые коэффициенты

1.13.2. Непрерывный случай. Понятие ортогональности

1.13.3. Ортогональные полиномы и их свойства

ГЛАВА 2. ЗАДАЧИ ЛИНЕЙНОЙ АЛГЕБРЫ

2.1. Обусловленность матриц

2.2. Метод Гаусса. LU-разложение матрицы. Программы DECOMP и SOLVE

2.3. Итерационные методы

IV Оглавление 2.4. Метод сопряженных градиентов

2.5. Решение проблемы собственных значений

2.5.1. Устойчивость проблемы собственных значений

2.5.2. Частичная проблема собственных значений. Степенной метод........... 2.5.3. Полная проблема собственных значений. QR-алгоритм

ГЛАВА 3. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ

3.1. Уточнение корней одного уравнения

3.2. Метод Ньютона для систем уравнений

3.3. Методы минимальных невязок Ракитского

ГЛАВА 4. РЕШЕНИЕ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

4.1. Методы Адамса. Локальная и глобальная погрешности.

Степень метода

4.2. Методы Рунге — Кутты. Программа RKF45

4.3. Устойчивость методов. Ограничение на шаг интегрирования и явление жесткости

4.4. Численное решение систем линейных дифференциальных уравнений с постоянной матрицей

4.5. Решение краевой задачи. Методы стрельбы и конечных разностей......... 4.6. Решение краевой задачи. Введение в проекционные методы

4.7. Введение в методы решения уравнений в частных производных............. ГЛАВА 5. ВВЕДЕНИЕ В МИНИМИЗАЦИЮ ФУНКЦИЙ

5.1. Минимизация функции одной переменной

5.2. Введение в многомерную минимизацию

5.3. Явление овражности и дифференциальное уравнение линии спуска....... 5.3.1. Метод барьерных функций

5.3.2. Метод штрафных функций

ГЛАВА 6. И КОЕ-ЧТО ЕЩЕ...

6.1. Сингулярное разложение матрицы и его использование в методе наименьших квадратов

6.1.1. Сингулярное разложение матрицы

6.1.2. Метод наименьших квадратов с использованием сингулярного разложения

6.1.3. Псевдообратная матрица

6.2. Понятие некорректно поставленной задачи

6.3. Свойства жестких систем дифференциальных уравнений

ПРИЛОЖЕНИЯ

ПРИЛОЖЕНИЕ 1. КОНЕЧНЫЕ РАЗНОСТИ, СУММЫ,

П1.1. Конечные разности и их свойства

П1.2. Разделенные разности и их свойства

П1.3. Суммирование функций

П1.4. Разностные уравнения

П1.4.1. Линейное разностное уравнение первого порядка

П1.4.2. Линейные разностные уравнения порядка выше первого................ ПРИЛОЖЕНИЕ 2. ЛИНЕЙНЫЕ (ВЕКТОРНЫЕ) ПРОСТРАНСТВА

ПРИЛОЖЕНИЕ 3. ЭЛЕМЕНТЫ ТЕОРИИ МАТРИЦ

П3.1. Общие сведения о матрицах

П3.2. Операции с матрицами

П3.3. Собственные значения и собственные векторы матриц

П3.4. Нормы матриц

П3.5. Матричный ряд и матричные функции

П3.6. Некоторые свойства матричной экспоненты

П3.7. Аналитическое решение систем линейных дифференциальных уравнений с постоянной матрицей

П3.8. Аналитическое решение систем линейных разностных уравнений с постоянной матрицей

П3.9. Устойчивость решений дифференциальных и разностных уравнений

ПРИЛОЖЕНИЕ 4. СТЕПЕННЫЕ АСИМПТОТИЧЕСКИЕ РАЗЛОЖЕНИЯ.................. ПРИЛОЖЕНИЕ 5. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

П5.1. Упражнения

П5.1.1. Введение

П5.1.2. Погрешность арифметических операций

П5.1.3. Конечные разности и суммирование функций

П5.1.4. Линейное разностное уравнение порядка выше первого................. П5.1.5. Интерполяция функций

П5.1.6. Численное дифференцирование и квадратурные формулы............. П5.1.7. Среднеквадратичная аппроксимация и ортогональные полиномы

П5.1.8. Задачи на матрицы. Векторно-матричное решение систем дифференциальных и разностных уравнений на основе формулы Лагранжа — Сильвестра

П5.1.9. Решение систем нелинейных уравнений

П5.1.10. Устойчивость численных методов решения систем обыкновенных дифференциальных уравнений

П5.2. Лабораторные работы

П5.2.1. Интерполяция и квадратурные формулы (программы SPLINE, SEVAL, QUANC8)

П5.2.2. Решение систем линейных алгебраических уравнений (программы DECOMP и SOLVE)

П5.2.3. Решение систем обыкновенных дифференциальных уравнений (программа RKF45)

П5.2.4. Проблема собственных значений и преобразования Хаусхолдера и Гивенса

П5.3. Курсовая работа

П5.3.1. Вычисление орбиты корабля "Аполлон"

П5.3.2. Решение краевой задачи методом стрельбы

П5.3.3. Решение краевой задачи конечно-разностным методом с использованием метода Ньютона

П5.3.4. Решение задачи параметрической идентификации (оценка параметров электрической цепи)

ЛИТЕРАТУРА

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Введение Это учебное пособие написано на базе лекций, читавшихся на факультете технической кибернетики Санкт-Петербургского государственного политехнического университета. Их основы более тридцати лет назад были заложены профессором Ю. В. Ракитским, а затем многократно перерабатывались и расширялись авторами.

В настоящее время имеется достаточное количество учебников с названием "Численные методы" или похожим на него. В первую очередь, следует отметить книгу Н. С. Бахвалова и др. [1], построенную на основе лекций, читавшихся на механико-математическом факультете и факультете вычислительной математики и кибернетики МГУ. Этот весьма фундаментальный и обстоятельный курс характеризуется большой продолжительностью и сочетает необходимую строгость изложения с обсуждением многих реально возникающих на практике проблем. В качестве предыдущей версии университетского курса следует упомянуть книгу И. С. Березина и Н. П. Жидкова [2, 3]. Имеется также большое число книг, в основном, для студентов инженерных специальностей, где авторы приводят многочисленные методы, к сожалению, без должного обоснования, ориентируя читателей на использование стандартных программ.

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

Так, например, важное место в пособии занимают проблема плохой обусловленности при решении линейных систем алгебраических уравнений, явление жесткости в дифференциальных уравнениях и явление овражности при минимизации функций, имеющие в своей основе немало общего и заставляющие расплачиваться либо точностью решения, либо большим объемом вычислений. В-третьих, дать первое представление о том, как строится программное обеспечение для обсуждаемых методов. За основу и в качестве примера были взяты программы из книги Дж. Форсайта, М. Малькольма, К. Моулера "Машинные методы математических вычислений" [14]. И, хотя на русском языке был издан ее переработанный и расширенный вариант [7], без ущерба для понимания основных проблем предпочтение было отдано [14] в связи с публикацией полного текста всех используемых программ непосредственно в книге. В-четвертых, ставилась цель построить изложение так, чтобы оно отвечало курсу объемом порядка тридцати лекций.

Перечисленные цели во многом противоречили друг другу, и достигнутый компромисс целиком определялся субъективными взглядами авторов. Так, например, материал, посвященный методам решения систем линейных алгебраических уравнений и уравнений в частных производных, следует считать лишь введением в эти разделы. Более подробно они изложены в учебниках, приведенных в списке литературы. Оговоренное количество лекций не позволило отразить такие безусловно важные проблемы, как работа с разреженными матрицами и параллельные вычисления. Для самостоятельного ознакомления с ними можно рекомендовать книги [38, 26, 55, 21, 35] и др.

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

В тексте пособия содержится некоторое количество вопросов для читателя.

Об ответах на них при первом чтении можно не задумываться. Однако более серьезная работа над лекциями заставит вернуться к ответам для уточнения и закрепления полученных знаний. В ряде случаев вопросы носят откровенно провокационный и даже математически некорректный характер и не имеют однозначного ответа. Здесь основная цель — заставить студента задуматься и самостоятельно осмыслить обсуждаемые проблемы.

Предполагается, что читатель знаком с курсом высшей математики в традиционном объеме для технического вуза, а также с материалами, размещенными в приложениях. При самостоятельном изучении пособия мы рекомендуем начинать с материалов первых четырех приложений. Когда пособие используется при чтении лекций, сведения из приложений можно излагать частями по мере возникновении в них потребности в остальных главах.

В приложении 5 отражены примеры упражнений, лабораторных и курсовых тика требует самостоятельных методических указаний большого объема с детальной проработкой. В данном случае авторы пытались лишь проиллюстрировать возможное наполнение практических занятий и тем самым помочь студенту, самостоятельно изучающему пособие, а также молодому преподавателю.

Приводимый список литературы существенно ограничен и не претендует на полноту. С одной стороны, это перечень "универсальных" учебников, ориентированных на разнообразные численные методы широкого круга задач [1— 15]. С другой стороны, у вдумчивого и пытливого читателя часто возникает вопрос: "А что еще можно почитать на эту тему?" Для этих студентов мы и делаем ссылки, также не претендующие на полноту:

глава 2 — [48, 46, 19, 20, 25, 29, 30, 36, 39, 47, 49];

глава 3 — [34, 27];

глава 4 — [50, 51, 16, 33, 40, 42, 43, 52];

глава 5 — [18, 24, 27, 37, 40, 54];

глава 6 — [32, 40, 45];

приложения — [23, 22, 46, 17, 31, 44, 53].