Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол
Материал из MachineLearning.
Строка 15: | Строка 15: | ||
Если допустимое множество <tex>\mathbb{X}=\mathbb{R}</tex>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''. | Если допустимое множество <tex>\mathbb{X}=\mathbb{R}</tex>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''. | ||
== Метод Ньютона == | == Метод Ньютона == | ||
- | == Метод | + | Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция <tex>f(x)</tex> дважды непрерывно дифференцируема. Отыскание минимума функции <tex>f(x)</tex> производится при помощи отыскания стационарной точки, т.е. точки <tex>x^*</tex>, удовлетворяющей уравнению <tex>f'(x)=0</tex>, которое решается методом Ньютона. |
+ | |||
+ | |||
+ | Если <tex>x^k</tex> – точка, полученная на k-м шаге, то функция <tex>f'(x)</tex> аппроксимируется своим уравнением касательной: | ||
+ | |||
+ | <tex>y = f'(x^k) + (x - x^k)f''(x^k)</tex>, | ||
+ | |||
+ | а точка <tex>x^{k+1}</tex> выбирается как пересечение этой прямой с осью <tex>Ох</tex>, т.е. | ||
+ | |||
+ | <tex>x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>. | ||
+ | |||
+ | Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция <tex>f(x)</tex> имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных <tex>f'(x)</tex> и <tex>f''(x)</tex>, что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа. | ||
+ | |||
+ | Когда начальная точка итераций <tex>x_0</tex> достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется. | ||
+ | |||
+ | Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности. | ||
+ | |||
+ | == Метод парабол == | ||
+ | |||
+ | Относительно метода Ньютона этот метод обладает тем преимуществом, что он не требует вычисления производных функции <tex>f (x)</tex>. Однако, его сходимость может быть гарантирована лишь для достаточно регулярных функций (непрерывных и много раз дифференцируемых). | ||
+ | |||
+ | В этом методе вычисляется значение функции сразу в трех близлежащих точках <tex>x_0 - h</tex>, <tex>x_0</tex>, <tex>x_0 + h</tex>, где h – малое число. Через эти три точки проводится интерполяционная парабола: | ||
+ | |||
+ | <tex>y = ax^2 + bx + c</tex>. | ||
+ | |||
+ | Минимум параболы достигается при <tex>y = 2ax + b = 0</tex>, т.е. при <tex>x^* = /frac{-b}{2a}</tex>. Для трех точек получаем систему трех линейных уравнений для коэффициентов ''a'', ''b'', ''c''. Находим ''a'' и ''b'' и тогда: | ||
+ | |||
+ | <tex>x^{k+1} = x^k - 0.5h\frac{f(x^k + h) - f(x^k - h)}{f(x^k + h) - 2f(x^k) + f(x^k - h)}</</tex>. | ||
+ | |||
+ | |||
== Совмещение метода Ньютона и Парабол == | == Совмещение метода Ньютона и Парабол == | ||
== Численный пример == | == Численный пример == |
Версия 21:04, 16 ноября 2008
Содержание |
Постановка задачи одномерной оптимизации
Задача одномерной оптимизации определяется следующим образом:
- Допустимое множество — множество ;
- Целевую функцию — отображение ;
- Критерий поиска (max или min).
Тогда решить задачу означает одно из:
- Показать, что .
- Показать, что целевая функция не ограничена.
- Найти .
- Если , то найти .
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек таких, что всюду в некоторой их окрестности для минимума и для максимума.
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.
Метод Ньютона
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции производится при помощи отыскания стационарной точки, т.е. точки , удовлетворяющей уравнению , которое решается методом Ньютона.
Если – точка, полученная на k-м шаге, то функция аппроксимируется своим уравнением касательной:
,
а точка выбирается как пересечение этой прямой с осью , т.е.
.
Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных и , что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа.
Когда начальная точка итераций достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
Метод парабол
Относительно метода Ньютона этот метод обладает тем преимуществом, что он не требует вычисления производных функции . Однако, его сходимость может быть гарантирована лишь для достаточно регулярных функций (непрерывных и много раз дифференцируемых).
В этом методе вычисляется значение функции сразу в трех близлежащих точках , , , где h – малое число. Через эти три точки проводится интерполяционная парабола:
.
Минимум параболы достигается при , т.е. при . Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:
.