Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Численный пример)
 
(4 промежуточные версии не показаны)
Строка 1: Строка 1:
== Постановка задачи одномерной оптимизации ==
== Постановка задачи одномерной оптимизации ==
Задача одномерной оптимизации определяется следующим образом:
Задача одномерной оптимизации определяется следующим образом:
-
# ''Допустимое множество'' — множество <tex>\mathbb{X} \subseteq \texbb{R}</tex>;
+
# ''Допустимое множество'' — множество <tex>\mathbb{X} \subseteq \mathbb{R}</tex>;
# ''Целевую функцию'' — отображение <tex>f:\;\mathbb{X}\to\mathbb{R}</tex>;
# ''Целевую функцию'' — отображение <tex>f:\;\mathbb{X}\to\mathbb{R}</tex>;
# ''Критерий поиска'' (max или min).
# ''Критерий поиска'' (max или min).
Строка 14: Строка 14:
Если допустимое множество <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>, которое решается методом Ньютона.
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция <tex>f(x)</tex> дважды непрерывно дифференцируема. Отыскание минимума функции <tex>f(x)</tex> производится при помощи отыскания стационарной точки, т.е. точки <tex>x^*</tex>, удовлетворяющей уравнению <tex>f'(x)=0</tex>, которое решается методом Ньютона.
Строка 86: Строка 87:
''итерационная последовательность''
''итерационная последовательность''
-
<p align='center'><tex>x^{k+1} = x^k - \frac{f(x^k)}{f'(x^k)},&nbsp; k = 0,1, \dots</tex></p>
+
<p align='center'><tex>x^{k+1} = x^k - \frac{f(x^k)}{f'(x^k)}, k = 0,1, \dots</tex></p>
''будет сходиться к <tex>x^*</tex>, причем для погрешности на k-м шаге буддет справедлива оценка:''
''будет сходиться к <tex>x^*</tex>, причем для погрешности на k-м шаге буддет справедлива оценка:''
Строка 103: Строка 104:
<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>.
<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>.
-
== Численный пример ==
+
== Числовой пример ==
Сравним работу методов Ньютона и парабол на примере много экстремальной функции <tex>x^3 + 10sin(5x)</tex> при одинаковом начальном приближении:
Сравним работу методов Ньютона и парабол на примере много экстремальной функции <tex>x^3 + 10sin(5x)</tex> при одинаковом начальном приближении:
[[Изображение:Newton_result.png|thumb|300px|Поиск экстремума]]
[[Изображение:Newton_result.png|thumb|300px|Поиск экстремума]]
Строка 170: Строка 171:
[[Категория:Учебные задачи]]
[[Категория:Учебные задачи]]
 +
[[Категория:Численные методы безусловной оптимизации|Ньютона]]

Текущая версия

Содержание

Постановка задачи одномерной оптимизации

Задача одномерной оптимизации определяется следующим образом:

  1. Допустимое множество — множество \mathbb{X} \subseteq \mathbb{R};
  2. Целевую функцию — отображение f:\;\mathbb{X}\to\mathbb{R};
  3. Критерий поиска (max или min).

Тогда решить задачу f(x)\to \min_{x\in\mathrm{X}} означает одно из:

  1. Показать, что \mathbb{X}=\not\bigcirc.
  2. Показать, что целевая функция f(x) не ограничена.
  3. Найти x^*\in\mathbb{X}:\;f(x^*)=\min_{x\in\mathbb{X}}f(\vec{x}).
  4. Если \not\exists x^* , то найти \inf_{x\in\mathbb{X}}f(x).

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x_0 таких, что всюду в некоторой их окрестности f(x)\ge f(x_0) для минимума и f(x)\le f(x_0) для максимума.

Если допустимое множество \mathbb{X}=\mathbb{R}, то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Метод Ньютона

Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция f(x) дважды непрерывно дифференцируема. Отыскание минимума функции f(x) производится при помощи отыскания стационарной точки, т.е. точки x^*, удовлетворяющей уравнению f'(x)=0, которое решается методом Ньютона.


Если x^k – точка, полученная на k-м шаге, то функция f'(x) аппроксимируется своим уравнением касательной:

y = f'(x^k) + (x - x^k)f''(x^k)

,

а точка x^{k+1} выбирается как пересечение этой прямой с осью Ox, т.е.

x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}.

Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция f(x) имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных f'(x) и f''(x), что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа.

Когда начальная точка итераций x_0 достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.

Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.

Ограничения

Пускай задано уравнение f(x)=0\!, где f(x):\;\mathbb{X} \to \mathbb{R}\! и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Теорема Канторовича.

Если существуют такие константы A,B,C\!, что:

  1. \frac{1}{|f'(x)|}<A\! на [a,\;b]\!, то есть f'(x)\! существует и не равна нулю;
  2. \left|\frac{f(x)}{f'(x)}\right|<B\! на [a,\;b]\!, то есть f(x)\! ограничена;
  3. \exist f''(x)\! на [a,\;b]\!, и |f''(x)|\leq C \leq \frac{1}{2AB}\!;

Причём длина рассматриваемого отрезка |a-b|<\frac{1}{AB}\left(1- \sqrt{1-2ABC}\right)\!. Тогда справедливы следующие утверждения:

  1. на [a,\;b]\! существует корень x^* уравнения f(x)=0:\quad\exist x^*\in[a,\;b]: f(x^*)=0\!;
  2. если x_0=\frac{a+b}{2}\!, то итерационная последовательность сходится к этому корню: \left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*\!;
  3. погрешность может быть оценена по формуле |x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!.

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

|x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}=\frac{1}{2}\frac{B}{2^{n-2}}\left((2ABC)^{2^{n-2}}\right)^2=\alpha |x^*-x_{n-1}|^2\!

Тогда ограничения на исходную функцию f(x)\! будут выглядеть так:

  1. функция должна быть ограничена;
  2. функция должна быть гладкой, дважды дифференцируемой;
  3. её первая производная f'(x) равномерно отделена от нуля;
  4. её вторая производная f''(x)\! должна быть равномерно ограничена.

В случае решения задачи оптимизации под функцией понимаем ее производную.

Проблема области сходимости

Запишем итерационный процесс:

x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}.

Известно, что условием сходимости этого процесса будет неравенство

|S'(x)| \le q < 1,

где S(x) = x^k - \frac{f'(x^k)}{f''(x^k)}, отсюда получем условие сходимости:

|\frac{f'(x)f'''(x)}{(f'(x))^2}| \le q < 1.

В силу того что мы ищем корень уравнения f'(x) = 0, существует такая окрестность, где |S'(x)| \le q < 1, но в общем случае эта область будет мала, то есть нужно подбирать начальное приближение достаточно близко расположенным к корню.

Теорма о сходимости метода Ньютона Пусть x^* - простой вещественный корень уравнения f(x) = 0, а функция f(x) - дважды дифференцируема в некоторой окрестности U_r(x^*), причем первая произодная нигде не обращается в нуль.

Тогда, следуя обозначениям

0 < m_1 = \inf_{x\in U_r(x^*)}|f'(x)|, M_2 = \sup_{x\in U_r(x^*)}|f''(x)|,

При выборе начального приближения x^0 из той же окрестности U_r(x^*) такого, что

\frac{M_2|x^0 - x^*|}{2m_1} = q < 1,

итерационная последовательность

x^{k+1} = x^k - \frac{f(x^k)}{f'(x^k)}, k = 0,1, \dots

будет сходиться к x^*, причем для погрешности на k-м шаге буддет справедлива оценка:

|x^k - x^*| \le q^{2^k - 1}|x^0 - x^*|.

Метод парабол

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

В этом методе вычисляется значение функции сразу в трех близлежащих точках x_0 - h, x_0, x_0 + h, где h – малое число. Через эти три точки проводится интерполяционная парабола:

y = ax^2 + bx + c.

Минимум параболы достигается при y = 2ax + b = 0, т.е. при x^* = \frac{-b}{2a}. Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:

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)}.

Числовой пример

Сравним работу методов Ньютона и парабол на примере много экстремальной функции x^3 + 10sin(5x) при одинаковом начальном приближении:

Поиск экстремума
Поиск экстремума
k (номер итерации) x_n^k полученное методом Ньютона x_p^k полученное методом парабол f'(x_n^k) f'(x_p^k)
0 1.3 1.3 53.89938129 53.89938129
1 2.472235424 2.472080749 67.28692280 67.27673489
2 1.449211232 1.452275085 34.85893188 34.25354559
3 1.626598277 1.624678936 -5.832725638 -5.389540219
4 1.601301575 1.601390533 0.095723918 0.074598093
5 1.60170464 1.601718525 1.59821E-05 -0.003280363
6 1.601704707 1.601718641 4.0945E-13 -0.00330785

Код функций на С++, с помощью которых были произведены все расчеты можно скачать тут.

Литература

  • А.А.Самарский, А.В.Гулин.  Численные методы М.: Наука, 1989.
  • А.А.Самарский.  Введение в численные методы М.: Наука, 1982.
  • Н.В.Соснин.  Численные методы. Конспект лекций (сост. Д.В.Ховратович, Е.А.Попов).
  • М.М.Потапов.  Методы оптимизаций. Конспект лекций (сост. М.Л.Буряков).
  • Е.А.Волков.  Численные методы. — М.: Физматлит, 2003.

Смотри также

Личные инструменты