Численные методы безусловной оптимизации и решения нелинейных уравнений
Дж. Дэннис, Р. Шнабель
1988 г.
Монография известных американских специалистов, посвященная как теории численных методов оптимизации, так и вопросам реализации этих методов на ЭВМ. Особое внимание уделено наиболее эффективным методам ньютоновского типа. Приведены пакеты программ решения прикладных задач оптимизации. Для математиков-вычислителей, инженеров-исследователей, аспирантов и студентов вузов.Книга представляет собой подробное введение в численное решение задач безусловной оптимизации и систем нелинейных уравнений, не требующее от читателя глубоких знаний математических и вычислительных дисциплин. Работа над книгой была начата в 1977 г., поскольку мы считали, что к этому времени алгоритмы и теория решения таких задач малой и средней размерности достигли зрелого состояния и что был бы полезен подробный справочный материал. Книгу можно использовать при подготовке курса лекций для аспирантов или студентов-старшекурсников, а также ее можно рекомендовать для самостоятельного изучения научным работникам, инженерам и всем, кому рассматриваемые задачи интересны с практической точки зрения.
Оглавление
Обложка 1
Титульный лист оригинального издания 2
Титульный лист 3
Аннотация и выходные данные 4
Предисловие редактора перевода и переводчика 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
4.3. Необходимые и достаточные условия в задачах безусловной минимизации 103
4.4. Упражнения 106
5. Метод Ньютона решения нелинейных уравнений и безусловной минимизации 110
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
8.4. Другие формулы секущих для нелинейных уравнений 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
11. Методы решения задач со специальной структурой 284
11.1. Разреженный конечно-разностный метод Ньютона 285
11.2. Разреженные методы секущих 288
11.3. Вывод формул секущих с минимальными поправками 293
11.4. Анализ методов секущих с минимальными поправками 299
11.5. Упражнения 305
Приложение А. Модульная система алгоритмов безусловной минимизации и решения нелинейных уравнений 308
Предисловие 311
I. Описание 314
I.1. Назначение модульной системы алгоритмов 314
I.2. Организация модульной системы алгоритмов 316
I.3. Организация отдельных модулей 318
I.4. Ввод и вывод 323
I.5. Модули для основных алгебраических операций 324
II. Драйверные модули и руководство для безусловной минимизации 325
II.1. Алгоритм D6.1.1 (UMDRIVER). Драйвер модульной системы алгоритмов безусловной минимизации 325
II.2. Перечень модулей безусловной минимизации 329
II.3. Руководство 1. Выбор алгоритмических вариантов для безусловной минимизации 331
II.4. Руководство 2. Выбор параметров для безусловной минимизации 333
II.5. Руководство 3. Соображения относительно памяти для безусловной минимизации 336
II.6. Алгоритм D6.1.2 (UMEXAMPLE). Драйвер алгоритма безусловной минимизации, использующего линейный поиск, конечно-разностные градиенты и факторизованные аппроксимации гессиана по секущим 339
III. Драйверные модули и руководство для нелинейных уравнений 341
III.1. Алгоритм D6.1.3 (NEDRIVER). Драйвер модульной системы алгоритмов решения нелинейных уравнений 341
III.2. Перечень модулей для нелинейных уравнений 346
III.3. Руководство 4. Выбор алгоритмических вариантов решения нелинейных уравнений 347
III.4. Руководство 5. Выбор параметров для нелинейных уравнений 349
III.5. Руководство 6. Соображения относительно памяти для нелинейных уравнений 351
III.6. Алгоритм D6.1.4 (NEEXAMPLE). Драйвер алгоритма решения нелинейных уравнений, использующего поиск вдоль ломаной и конечно-разностную аппроксимацию якобиана 353
IV. Отдельные модули ((U) = использование только для безусловной минимизации; (N) = использование только для нелинейных уравнений) 354
IV.1. Модули, задаваемые пользователем (требования к ним) 354
(U) FN. Подпрограмма вычисления целевой функции $f(x)$ для безусловной минимизации 355
(U) GRAD. Подпрограмма вычисления вектора градиента $nabla f(x)$ (необязательная) 355
(U) HESS. Подпрограмма вычисления матрицы Гессе $nabla^2 f(x)$ (необязательная) 356
(N) FVEC. Подпрограмма вычисления функции $F(x)$, задающей нелинейные уравнения 357
(N) JAC. Подпрограмма вычисления матрицы Якоби $J(x)$ (необязательная) 357
IV.2. Модули, задаваемые разработчиком (частичное описание) 358
(U) UMINCK. Проверка входных параметров для безусловной минимизации 358
(N) NEINCK. Проверка входных параметров для нелинейных уравнений 360
IV.3. Алгоритмические модули (приведены полностью) 362
(N) NEFN. Вычисление суммы квадратов для нелинейных уравнений 362
А1.3.1 (MACHINEPS). Вычисление машинного эпсилон 363
(N) А3.2.1 (QRDECOMP). $QR$-разложение 363
(N) А3.2.2 (QRSOLVE). $QR$-решение 365
(N) А3.2.2а (RSOLVE). $R$-решение для $QR$-решения 366
А3.2.3 (CHOLSOLVE). Драйвер решения по Холесскому 366
А3.2.3а (LSOLVE). $L$-решение 367
A3.2.3b (LTSOLVE). $L^T$-решение 368
(N) АЗ.3.1 (CONDEST). Оценивание числа обусловленности верхней треугольной матрицы 368
А3.4.1 (QRUPDATE). Пересчет $QR$-разложения 370
А3.4.1a (JACROTATE). Вращение Якоби 371
(N) А3.4.2 (QFORM). Формирование $Q$ из $QR$-разложения 372
А5.4.1 (FDJAC). Конечно-разностная аппроксимация якобиана 373
(U) А5.5.1 (MODELHESS). Формирование гессиана модели 374
А5.5.2 (CHOLDECOMP). Возмущенное разложение Холесского 377
(U) А5.6.1 (FDHESSG). Конечно-разностная аппроксимация гессиана с использованием значений аналитически заданного градиента 379
(U) А5.6.2 (FDHESSF). Конечно-разностная аппроксимация гессиана с использованием значений функции 380
(U) А5.6.3 (FDGRAD). Аппроксимация градиента по разностям вперед 381
(U) А5.6.4 (CDGRAD). Аппроксимация градиента по центральным разностям 382
А6.3.1 (LINESEARCH). Линейный поиск 384
A6.3.1mod (LINESEARCHMOD). Линейный поиск с условием на производную по направлению 387
А6.4.1 (HOOKDRIVER). Драйвер локально ограниченного оптимального («криволинейного») шага 390
А6.4.2 (HOOKSTEP). Локально ограниченный оптимальный («криволинейный») шаг 392
А6.4.3 (DOGDRIVER). Драйвер шага вдоль кривой с двойным изломом 395
А6.4.4 (DOGSTEP). Шаг вдоль кривой с двойным изломом 396
А6.4.5. (TRUSTREGUP). Пересчет доверительной области модели 398
(N) А6.5.1 (НЕМОДЕЛ). Построение аффинной модели для нелинейных уравнений 402
(N) A6.5.1fac (NEMODELFAC). Построение аффинной модели для нелинейных уравнений с привлечением факторизованных формул секущих 405
(U) А7.2.1 (UMSTOP). Критерии останова для безусловной минимизации 408
(U) А7.2.2 (UMSTOP0). Критерии останова для безусловной минимизации перед начальной итерацией 409
(N) А7.2.3 (NESTOP). Критерии останова для нелинейных уравнений 411
(N) А7.2.4 (NESTOP0). Критерии останова для нелинейных уравнений перед начальной итерацией 413
(N) А8.3.1 (BPOYUNFAC). Формула пересчета Бройдена, нефакторизованная форма 414
(N) А8.3.2 (BROYFAC). Формула пересчета Бройдена, факторизованная форма 415
(U) А9.4.1 (BFGSUNFAC). Положительно определенная формула секущих (BFGS), нефакторизованная форма 416
(U) А9.4.2 (BFGSFAC). Положительно определенная формула секущих (BFGS), факторизованная форма 418
(U) А9.4.3 (INITHESSUNFAC). Начальное значение гессиана для формулы секущих в нефакторизованной форме 420
(U) А9.4.4 (INITHESSFAC). Начальное значение гессиана для формулы секущих в факторизованной форме 421
Приложение В. Тестовые задачи (Р. Шнабель) 422
Литература 425
Именной указатель 433
Предметный указатель 435
Оглавление 438
Выходные данные 440
Титульный лист оригинального издания 2
Титульный лист 3
Аннотация и выходные данные 4
Предисловие редактора перевода и переводчика 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
4.3. Необходимые и достаточные условия в задачах безусловной минимизации 103
4.4. Упражнения 106
5. Метод Ньютона решения нелинейных уравнений и безусловной минимизации 110
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
8.4. Другие формулы секущих для нелинейных уравнений 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
11. Методы решения задач со специальной структурой 284
11.1. Разреженный конечно-разностный метод Ньютона 285
11.2. Разреженные методы секущих 288
11.3. Вывод формул секущих с минимальными поправками 293
11.4. Анализ методов секущих с минимальными поправками 299
11.5. Упражнения 305
Приложение А. Модульная система алгоритмов безусловной минимизации и решения нелинейных уравнений 308
Предисловие 311
I. Описание 314
I.1. Назначение модульной системы алгоритмов 314
I.2. Организация модульной системы алгоритмов 316
I.3. Организация отдельных модулей 318
I.4. Ввод и вывод 323
I.5. Модули для основных алгебраических операций 324
II. Драйверные модули и руководство для безусловной минимизации 325
II.1. Алгоритм D6.1.1 (UMDRIVER). Драйвер модульной системы алгоритмов безусловной минимизации 325
II.2. Перечень модулей безусловной минимизации 329
II.3. Руководство 1. Выбор алгоритмических вариантов для безусловной минимизации 331
II.4. Руководство 2. Выбор параметров для безусловной минимизации 333
II.5. Руководство 3. Соображения относительно памяти для безусловной минимизации 336
II.6. Алгоритм D6.1.2 (UMEXAMPLE). Драйвер алгоритма безусловной минимизации, использующего линейный поиск, конечно-разностные градиенты и факторизованные аппроксимации гессиана по секущим 339
III. Драйверные модули и руководство для нелинейных уравнений 341
III.1. Алгоритм D6.1.3 (NEDRIVER). Драйвер модульной системы алгоритмов решения нелинейных уравнений 341
III.2. Перечень модулей для нелинейных уравнений 346
III.3. Руководство 4. Выбор алгоритмических вариантов решения нелинейных уравнений 347
III.4. Руководство 5. Выбор параметров для нелинейных уравнений 349
III.5. Руководство 6. Соображения относительно памяти для нелинейных уравнений 351
III.6. Алгоритм D6.1.4 (NEEXAMPLE). Драйвер алгоритма решения нелинейных уравнений, использующего поиск вдоль ломаной и конечно-разностную аппроксимацию якобиана 353
IV. Отдельные модули ((U) = использование только для безусловной минимизации; (N) = использование только для нелинейных уравнений) 354
IV.1. Модули, задаваемые пользователем (требования к ним) 354
(U) FN. Подпрограмма вычисления целевой функции $f(x)$ для безусловной минимизации 355
(U) GRAD. Подпрограмма вычисления вектора градиента $nabla f(x)$ (необязательная) 355
(U) HESS. Подпрограмма вычисления матрицы Гессе $nabla^2 f(x)$ (необязательная) 356
(N) FVEC. Подпрограмма вычисления функции $F(x)$, задающей нелинейные уравнения 357
(N) JAC. Подпрограмма вычисления матрицы Якоби $J(x)$ (необязательная) 357
IV.2. Модули, задаваемые разработчиком (частичное описание) 358
(U) UMINCK. Проверка входных параметров для безусловной минимизации 358
(N) NEINCK. Проверка входных параметров для нелинейных уравнений 360
IV.3. Алгоритмические модули (приведены полностью) 362
(N) NEFN. Вычисление суммы квадратов для нелинейных уравнений 362
А1.3.1 (MACHINEPS). Вычисление машинного эпсилон 363
(N) А3.2.1 (QRDECOMP). $QR$-разложение 363
(N) А3.2.2 (QRSOLVE). $QR$-решение 365
(N) А3.2.2а (RSOLVE). $R$-решение для $QR$-решения 366
А3.2.3 (CHOLSOLVE). Драйвер решения по Холесскому 366
А3.2.3а (LSOLVE). $L$-решение 367
A3.2.3b (LTSOLVE). $L^T$-решение 368
(N) АЗ.3.1 (CONDEST). Оценивание числа обусловленности верхней треугольной матрицы 368
А3.4.1 (QRUPDATE). Пересчет $QR$-разложения 370
А3.4.1a (JACROTATE). Вращение Якоби 371
(N) А3.4.2 (QFORM). Формирование $Q$ из $QR$-разложения 372
А5.4.1 (FDJAC). Конечно-разностная аппроксимация якобиана 373
(U) А5.5.1 (MODELHESS). Формирование гессиана модели 374
А5.5.2 (CHOLDECOMP). Возмущенное разложение Холесского 377
(U) А5.6.1 (FDHESSG). Конечно-разностная аппроксимация гессиана с использованием значений аналитически заданного градиента 379
(U) А5.6.2 (FDHESSF). Конечно-разностная аппроксимация гессиана с использованием значений функции 380
(U) А5.6.3 (FDGRAD). Аппроксимация градиента по разностям вперед 381
(U) А5.6.4 (CDGRAD). Аппроксимация градиента по центральным разностям 382
А6.3.1 (LINESEARCH). Линейный поиск 384
A6.3.1mod (LINESEARCHMOD). Линейный поиск с условием на производную по направлению 387
А6.4.1 (HOOKDRIVER). Драйвер локально ограниченного оптимального («криволинейного») шага 390
А6.4.2 (HOOKSTEP). Локально ограниченный оптимальный («криволинейный») шаг 392
А6.4.3 (DOGDRIVER). Драйвер шага вдоль кривой с двойным изломом 395
А6.4.4 (DOGSTEP). Шаг вдоль кривой с двойным изломом 396
А6.4.5. (TRUSTREGUP). Пересчет доверительной области модели 398
(N) А6.5.1 (НЕМОДЕЛ). Построение аффинной модели для нелинейных уравнений 402
(N) A6.5.1fac (NEMODELFAC). Построение аффинной модели для нелинейных уравнений с привлечением факторизованных формул секущих 405
(U) А7.2.1 (UMSTOP). Критерии останова для безусловной минимизации 408
(U) А7.2.2 (UMSTOP0). Критерии останова для безусловной минимизации перед начальной итерацией 409
(N) А7.2.3 (NESTOP). Критерии останова для нелинейных уравнений 411
(N) А7.2.4 (NESTOP0). Критерии останова для нелинейных уравнений перед начальной итерацией 413
(N) А8.3.1 (BPOYUNFAC). Формула пересчета Бройдена, нефакторизованная форма 414
(N) А8.3.2 (BROYFAC). Формула пересчета Бройдена, факторизованная форма 415
(U) А9.4.1 (BFGSUNFAC). Положительно определенная формула секущих (BFGS), нефакторизованная форма 416
(U) А9.4.2 (BFGSFAC). Положительно определенная формула секущих (BFGS), факторизованная форма 418
(U) А9.4.3 (INITHESSUNFAC). Начальное значение гессиана для формулы секущих в нефакторизованной форме 420
(U) А9.4.4 (INITHESSFAC). Начальное значение гессиана для формулы секущих в факторизованной форме 421
Приложение В. Тестовые задачи (Р. Шнабель) 422
Литература 425
Именной указатель 433
Предметный указатель 435
Оглавление 438
Выходные данные 440
3.58 МБ
Порядок:
от старых к новым
