1,94 Численные методы безусловной оптимизации и решения нелинейных уравнений: Пер. с англ. — М.: Мир, 1988. — 440 с., ил.
ISBN 5-03-001102-1
Монография известных американских специалистов, посвященная как теории численных методов оптимизации, так и вопросам реализации этих методов на ЭВМ. Особое внимание уделено наиболее эффективным методам ньютоновского типа. Приведены пакеты программ решения прикладных задач оптимизации.
Для математиков-вычислителей, инженеров-исследователей, аспирантов и -студентов вузов.
Предисловие редактора перевода и переводчика
Вниманию читателя предлагается книга американских специалистов в области численного анализа Джона Дэнниса, мл., и Роберта Шнабеля. Она посвящена двум важным и тесно между собой связанным разделам: безусловной минимизации и решению нелинейных уравнений. Наряду с серьезным теоретическим материалом, отражающим современное состояние исследований в рассматриваемой области, в книге большое внимание уделяется вопросам программной реализации численных методов и их преподавания в высшей школе.
Авторы сознательно ограничились рассмотрением численных методов ньютоновского (квазиньютоновского) типа. Класс этих методов отличает концептуальное единство и достаточная широта охвата, причем на практике такие методы— одни из наиболее эффективных. Общая идея методов такова: на каждой итерации сначала строится модельная аппроксимация исходной задачи (линейная в случае нелинейных уравнений и квадратичная для безусловной минимизации), а затем на основе ее решения находится новое приближение. По такой же схеме проводится исследование сходимости. Впервые столь подробно в литературе на русском языке излагаются метод доверительной области, квазиньютоновские методы типа секущих и др. Методы, не вошедшие в указанный класс, в достаточной мере представлены ссылками на литературу. В связи с тем что в оригинале имеется только одна ссылка на работу советских авторов, мы решили указать несколько отечественных монографий, содержащих обширные списки литературы. Полагаем, что книга вполне пригодна для формирования у читателя целостного представления о современном состоянии численных методов "минимизации и решения нелинейных уравнений.
Более четверти книги занимают два приложения, написанные Робертом Шнабелем. В отличие от несколько схематич-
Оглавление
Предисловие редактора перевода и переводчика .......... 5
Предисловие к русскому изданию.............. 7
Предисловие....................... 9
Глава 1. Введение.................... 14
1.1. Постановки задач................. 14
1.2. Характерные особенности встречающихся на практике задач 18
1.3. Арифметика конечной точности и измерение ошибок .... 24
1.4. Упражнения................... 27
Глава 2. Нелинейные задачи с одной переменной......... 29
2.1. О том, чего не следует ожидать........... 29
2.2. Метод Ньютона решения одного уравнения с одним неизвестным ..................... 31
2.3. Сходимость последовательностей действительных чисел . . 34
2.4. Сходимость метода Ньютона............ 36
2.5. Глобально сходящиеся методы решения одного уравнения с одним неизвестным................ 40
2.6. Методы для случая, когда производные не заданы .... 44
2.7. Минимизация функции одной переменной........ 50
2.8. Упражнения........... .......53
Глава 3. Основы вычислительной линейной алгебры ........ 58
3.1. Векторные и матричные нормы, ортогональность..... 59
3.2. Решение систем линейных уравнений и разложения матриц 65
3.3. Погрешности при решении линейных систем....... 71
3.4. Формулы пересчета матричных разложений....... 76
3.5. Собственные значения и положительная определенность . . 79
3.6. Линейная задача о наименьших квадратах....... 82
3.7. Упражнения................... 88
Глава 4. Основы анализа функций многих переменных ....... 91
4.1. Производные и многомерные модели ......... 91
4.2. Конечно-разностные производные в многомерном случае . . 100
Оглавление 439
4.3. Необходимые и достаточные условия в задачах безусловной минимизации...................}03
4.4. Упражнения...................1"°
Глава 5. Метод Ньютона решения нелинейных уравнений и безусловной
минимизации...................НО
5.1. Метод Ньютона' решения систем нелинейных уравнений . .110
5.2. Локальная схрдимость метода Ньютона ....... 114
5.3. Теорема Канторовича и теорема о сжимающем отображении 116
5.4. Методы с конечно-разностными производными для решения систем нелинейных уравнений............ 119
5.5. Метод Ньютона безусловной минимизации....... 125
5.6. Методы с конечно-разностными производными для безусловной минимизации................. 130
5.7. Упражнения . . ,................. 134
Глава 6. Глобально сходящиеся модификации метода Ньютона . . . . 138
6.1. Общая квазиньютоновская схема.........139
6.2. Направления спуска ....:...........140
6.3. Линейный поиск...............• . • 144
6.3.1. Результаты исследования сходимости при надлежащем выборе шагов................ 149
6.3.2. Выбор «шага дроблением........... 155
6.4. Подход: модель — доверительная область........ 160
6.4.1. Локально ограниченный оптимальный («криволинейный») шаг..................165
6.4.2. Шаг с двойным изломом............171
6.4.3. Пересчет доверительной области.........176
6.5. Глобальные методы решения систем нелинейных уравнений 180
6.6. Упражнения...................187
Глава 7. Критерии останова, масштабирование и тестирование .... 190
7.1. Масштабирование................. 190
7.2. Критерии останова...............'. . 195
7.3. Тестирование................... 198
7.4. Упражнения................... 202
Глава 8. Методы секущих для решения систем нелинейных уравнений 204
8.1. Метод Бройдена . . '...............205
8.2. Анализ локальной сходимости метода Бройдена.....211
8.3. Реализация квазиньютоновских алгоритмов, использующих
Йэрмулу пересчета Бройдена.............223 ругне формулы секущих для нелинейных уравнений . . . 227
8.5. Упражнения...................229
Глава 9. Методы секущих для безусловной минимизации......232
9.1. Симметричная формула секущих Пауэлла........ 233
9.2. Симметричные положительно определенные формулы секущих 237
9.3. Локальная сходимость положительно определенных методов секущих.....................243
9.4. Реализация квазиньютоновских алгоритмов, использующих положительно определенные формулы секущих......248
9.5. Еще один результат, касающийся сходимости положительно определенных методов секущих...........252
9.6. Другие формулы секущих для безусловной минимизации . . 252
9.7. Упражнения.................... 254
Глава 10. Нелинейная задача о наименьших квадратах ....... 259
10.1. Постановка нелинейной задачи о наименьших квадратах . . 259
10.2. Методы типа Гаусса — Ньютона...........263
10.3. Методы полностью ньютоновского типа.........271
10.4. Некоторые другие соображения относительно решения нелинейных задач о наименьших квадратах......... 277
10.5. Упражнения...................280
X Глава 11. Методы решения задач со специальной структурой .... 284
11.1. Разреженный конечно-разностный метод Ньютона.....285
11.2. Разреженные методы секущих............288
11.3. Вывод формул секущих с минимальными поправками . . . 293
11.4. Анализ методов секущих с минимальными поправками . . 299 i
11.5. Упражнения...................305
Приложение А. Модульная система алгоритмов безусловной минимизации
и решения нелинейных уравнений (Р. Шнабель) . . . 308
Приложение В~ Тестовые задачи (Р. Шнабель).......... 422
Литература....................... 425
Именной указатель..................... 432
Предметный указатель ................... 434
Цена: 300руб.
