- •Оглавление
- •§ 2. Существование и единственность интерполяционного многочлена
- •§ 3. Интерполяционный многочлен Лагранжа
- •§ 4. Погрешность интерполяционного многочлена Лагранжа
- •§ 5. Минимизация погрешности интерполяционного многочлена Лагранжа. Многочлен Чебышева
- •§ 6. Схема Эйткена
- •§ 7. Численное дифференцирование
- •§ 8. Погрешность простейших формул численного дифференцирования
- •§ 9. Разделенные разности. Многочлен Ньютона.
- •§ 10. Интерполяция с кратными узлами
- •§ 11. Кубическая сплайн-интерполяция
- •ГлаваIii. Численное интегрирование
- •§ 1. Простейшие квадратурные формулы. Составные формулы
- •§ 2. Метод неопределенных коэффициентов
- •§ 3. Формулы Ньютона-Котеса
- •§ 4. Формулы Гаусса
- •§ 5. Погрешность квадратурных формул. Правило Рунге.
- •ГлаваIv. Численные методы алгебры
- •§1. Системы линейных уравнений: метод простых итераций, метод Зейделя
- •§2. Метод наискорейшего спуска
- •§ 3. Обратная интерполяция для решения нелинейных уравнений
- •§ 4. Системы нелинейных уравнений: метод простых итераций
- •§ 5. Системы нелинейных уравнений: метод Ньютона
- •§ 6. Методы спуска
- •Глава V. Дифференциальные уравнения и системы
- •§ 1. Задача Коши для обыкновенных дифференциальных уравнений: применение формулы Тейлора
- •§ 2. Метод Эйлера. Методы Рунге-Кутта
- •§ 3. Конечно-разностные методы
- •§ 4. Уравнения второго порядка
§ 5. Системы нелинейных уравнений: метод Ньютона
Идея метода: Пусть — приближенное решение уравнения(7), достаточно близкое к искомому точному решению. В окрестностиуравнение (7) заменяется линейным уравнением (вспомогательной линейной задачей), решение которого берется в качестве следующего приближения.
1 случай) m = 1, т.е. одно уравнение f(x) = 0 с одной неизвестной.
Пусть x0 — "хорошее" начальное приближение.
—линейное уравнение, заменяющее исходное
—решение линейного уравнения
—рекуррентная формула, метод Ньютона
Геометрическая иллюстрация метода:
На следующем рисунке показана ситуация зацикливания:
Общий случай)
Дано: (7)
Опр. Линейный оператор назовем производной отображенияв точке, еслипри.
Действие линейного оператора совпадает с произведением матрицыA на вектор , где,,
Пусть — точно решение уравнения (7);
—некоторое приближение, близкое к ;
тогда .
рекуррентная формула, метод Ньютона.
Замечание: Матрица A–1 (зависящая от ) существует тогда и только тогда, когдаA невырожденная.
Теорема (о сходимости метода Ньютона) (без док-ва)
При выполнении условий:
"аналог сжимаемости": для некоторогоa1 ≥ 0, любого и любого, где;
"аналог дифференцируемости": , для некоторогоa2 ≥ 0, любых ;
и при итерационный процесс Ньютона сходится с оценкой погрешности
.
§ 6. Методы спуска
По аналогии с методами спуска для системы линейных уравнений заменим задачу решения системы (7) задачей минимизации функции.
Идея методов спуска:
1) Выбирается начальное приближение ;
2) Выбирается направление, в котором убывает;
3) В этом направлении от выбирается следующее приближение;
4) По рекуррентной формуле последовательно находят приближения ,…,;
5) Последнее приближение .
1 способ) Покоординатный спуск
Пусть .
Подставим в значения всех координат, кроме первой переменной.
Получим функцию от одной переменной. Найдем ее точку минимума. Это будет x1(1).
Затем подставим в x1(1) и значения всех остальных координат , кроме второй переменной.
Получим функцию от одной переменной. Найдем ее точку минимума. Это будет x1(2). Продолжая таким образом, получим . И т.д.
Проиллюстрируем поведение алгоритма для m = 2.
Модификации алгоритма:
1) Случайный покоординатный спуск — порядок переменных выбирается случайным образом.
2) "Метод муравьиной кучи" — покоординатный спуск выполняется для нескольких разных нулевых приближений.
Недостатки алгоритма:
1) Не гарантирует сходимости.
2) Не гарантирует приближение к глобальному экстремуму.
2 способ) Метод наискорейшего спуска.
Использует рекуррентную формулу , где– некоторый параметр, определяемый из условия:
.
3 способ) Условная минимизация
Задача: Найти точку , в которой достигается минимум, при условиях в виде неравенств или равенств:
Методы решения таких задач получили название математическое программирование.
Если все функции , , являются линейными — линейное программирование. Если есть нелинейные функции — нелинейное программирование. Если искомое решение должно состоять из целых чисел — целочисленное программирование.