Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол
Материал из MachineLearning.
м («Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол.» переименована в «[[Метод Ньютона. Проб) |
|||
(21 промежуточная версия не показана) | |||
Строка 1: | Строка 1: | ||
== Постановка задачи одномерной оптимизации == | == Постановка задачи одномерной оптимизации == | ||
Задача одномерной оптимизации определяется следующим образом: | Задача одномерной оптимизации определяется следующим образом: | ||
- | # ''Допустимое множество'' — множество <tex>\mathbb{X} | + | # ''Допустимое множество'' — множество <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). | ||
- | Тогда решить задачу <tex>f(x)\to \min_ | + | Тогда решить задачу <tex>f(x)\to \min_{x\in\mathrm{X}}</tex> означает одно из: |
- | # Показать, что <tex>\mathbb{X}=\ | + | # Показать, что <tex>\mathbb{X}=\not\bigcirc</tex>. |
- | # Показать, что целевая функция <tex>f( | + | # Показать, что целевая функция <tex>f(x)</tex> не ограничена. |
- | # Найти <tex> | + | # Найти <tex>x^*\in\mathbb{X}:\;f(x^*)=\min_{x\in\mathbb{X}}f(\vec{x})</tex>. |
- | # Если <tex>\not\exists | + | # Если <tex>\not\exists x^* </tex>, то найти <tex>\inf_{x\in\mathbb{X}}f(x)</tex>. |
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <tex>x_0</tex> таких, что всюду в некоторой их окрестности <tex>f(x)\ge f(x_0)</tex> для минимума и <tex>f(x)\le f(x_0)</tex> для максимума. | Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <tex>x_0</tex> таких, что всюду в некоторой их окрестности <tex>f(x)\ge f(x_0)</tex> для минимума и <tex>f(x)\le f(x_0)</tex> для максимума. | ||
Если допустимое множество <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> аппроксимируется своим уравнением касательной: | ||
+ | |||
+ | <p align='center'><tex>y = f'(x^k) + (x - x^k)f''(x^k)</tex></p>, | ||
+ | |||
+ | а точка <tex>x^{k+1}</tex> выбирается как пересечение этой прямой с осью <tex>Ox</tex>, т.е. | ||
+ | |||
+ | <p align='center'><tex>x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>.</p> | ||
+ | |||
+ | Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция <tex>f(x)</tex> имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных <tex>f'(x)</tex> и <tex>f''(x)</tex>, что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа. | ||
+ | |||
+ | Когда начальная точка итераций <tex>x_0</tex> достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется. | ||
+ | |||
+ | Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности. | ||
+ | |||
+ | === Ограничения === | ||
+ | Пускай задано уравнение <tex>f(x)=0\!</tex>, где <tex>f(x):\;\mathbb{X} \to \mathbb{R}\!</tex> и надо найти его решение. | ||
+ | |||
+ | Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. | ||
+ | '''Теорема Канторовича.''' | ||
+ | |||
+ | ''Если существуют такие константы <tex>A,B,C\!</tex>, что:'' | ||
+ | # ''<tex>\frac{1}{|f'(x)|}<A\!</tex> на <tex>[a,\;b]\!</tex>, то есть <tex>f'(x)\!</tex> существует и не равна нулю;'' | ||
+ | # ''<tex>\left|\frac{f(x)}{f'(x)}\right|<B\!</tex> на <tex>[a,\;b]\!</tex>, то есть <tex>f(x)\!</tex> ограничена;'' | ||
+ | # ''<tex>\exist f''(x)\!</tex> на <tex>[a,\;b]\!</tex>, и <tex>|f''(x)|\leq C \leq \frac{1}{2AB}\!</tex>;'' | ||
+ | ''Причём длина рассматриваемого отрезка <tex>|a-b|<\frac{1}{AB}\left(1- \sqrt{1-2ABC}\right)\!</tex>. Тогда справедливы следующие утверждения:'' <br /> | ||
+ | # ''на <tex>[a,\;b]\!</tex> существует корень <tex>x^*</tex> уравнения <tex>f(x)=0:\quad\exist x^*\in[a,\;b]: f(x^*)=0\!</tex>;'' | ||
+ | # ''если <tex>x_0=\frac{a+b}{2}\!</tex>, то итерационная последовательность сходится к этому корню: <tex>\left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*\!</tex>;'' | ||
+ | # ''погрешность может быть оценена по формуле <tex>|x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!</tex>.'' | ||
+ | |||
+ | Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода: <br /> | ||
+ | :: <tex>|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\!</tex> | ||
+ | |||
+ | Тогда ограничения на исходную функцию <tex>f(x)\!</tex> будут выглядеть так: | ||
+ | # функция должна быть ограничена; | ||
+ | # функция должна быть гладкой, дважды дифференцируемой; | ||
+ | # её первая производная <tex>f'(x)</tex> равномерно отделена от нуля; | ||
+ | # её вторая производная <tex>f''(x)\!</tex> должна быть равномерно ограничена. | ||
+ | |||
+ | В случае решения задачи оптимизации под функцией понимаем ее производную. | ||
+ | |||
+ | === Проблема области сходимости === | ||
+ | Запишем итерационный процесс: | ||
+ | |||
+ | <p align='center'><tex>x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>.</p> | ||
+ | |||
+ | Известно, что условием сходимости этого процесса будет неравенство | ||
+ | |||
+ | <p align='center'><tex>|S'(x)| \le q < 1</tex>,</p> | ||
+ | |||
+ | где <tex>S(x) = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>, отсюда получем условие сходимости: | ||
+ | |||
+ | <p align='center'><tex>|\frac{f'(x)f'''(x)}{(f'(x))^2}| \le q < 1</tex>.</p> | ||
+ | |||
+ | В силу того что мы ищем корень уравнения <tex>f'(x) = 0</tex>, существует такая окрестность, где <tex>|S'(x)| \le q < 1</tex>, но в общем случае эта область будет мала, то есть нужно подбирать начальное приближение достаточно близко расположенным к корню. | ||
+ | |||
+ | '''Теорма о сходимости метода Ньютона''' | ||
+ | ''Пусть <tex>x^*</tex> - простой вещественный корень уравнения <tex>f(x) = 0</tex>, а функция <tex>f(x)</tex> - дважды дифференцируема в некоторой окрестности <tex>U_r(x^*)</tex>, причем первая произодная нигде не обращается в нуль.'' | ||
+ | |||
+ | ''Тогда, следуя обозначениям'' | ||
+ | |||
+ | <p align='center'><tex>0 < m_1 = \inf_{x\in U_r(x^*)}|f'(x)|, M_2 = \sup_{x\in U_r(x^*)}|f''(x)|</tex>,</p> | ||
+ | |||
+ | ''При выборе начального приближения <tex>x^0</tex> из той же окрестности <tex>U_r(x^*)</tex> такого, что '' | ||
+ | |||
+ | <p align='center'><tex>\frac{M_2|x^0 - x^*|}{2m_1} = q < 1</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-м шаге буддет справедлива оценка:'' | ||
+ | |||
+ | <p align='center'><tex>|x^k - x^*| \le q^{2^k - 1}|x^0 - x^*|</tex>.</p> | ||
+ | == Метод парабол == | ||
+ | |||
+ | Относительно метода Ньютона этот метод обладает тем преимуществом, что он не требует вычисления производных функции <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>. | ||
+ | |||
+ | == Числовой пример == | ||
+ | Сравним работу методов Ньютона и парабол на примере много экстремальной функции <tex>x^3 + 10sin(5x)</tex> при одинаковом начальном приближении: | ||
+ | [[Изображение:Newton_result.png|thumb|300px|Поиск экстремума]] | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | ! <tex>k</tex> (номер итерации) | ||
+ | ! <tex>x_n^k</tex> полученное методом Ньютона | ||
+ | ! <tex>x_p^k</tex> полученное методом парабол | ||
+ | ! <tex>f'(x_n^k)</tex> | ||
+ | ! <tex>f'(x_p^k)</tex> | ||
+ | |- | ||
+ | | 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 | ||
+ | |} | ||
+ | |||
+ | Код функций на С++, с помощью которых были произведены все расчеты можно скачать [[Media:Newton&Parabola.zip|тут]]. | ||
+ | |||
== Литература == | == Литература == | ||
+ | * ''А.А.Самарский, А.В.Гулин.'' Численные методы М.: Наука, 1989. | ||
+ | * ''А.А.Самарский.'' Введение в численные методы М.: Наука, 1982. | ||
+ | * ''Н.В.Соснин.'' Численные методы. Конспект лекций (сост. Д.В.Ховратович, Е.А.Попов). | ||
+ | * ''М.М.Потапов.'' Методы оптимизаций. Конспект лекций (сост. М.Л.Буряков). | ||
+ | * ''Е.А.Волков.'' Численные методы. — М.: Физматлит, 2003. | ||
+ | |||
== Смотри также == | == Смотри также == | ||
* [[Практикум ММП ВМК, 4й курс, осень 2008]] | * [[Практикум ММП ВМК, 4й курс, осень 2008]] | ||
[[Категория:Учебные задачи]] | [[Категория:Учебные задачи]] | ||
+ | [[Категория:Численные методы безусловной оптимизации|Ньютона]] |
Текущая версия
Содержание |
Постановка задачи одномерной оптимизации
Задача одномерной оптимизации определяется следующим образом:
- Допустимое множество — множество ;
- Целевую функцию — отображение ;
- Критерий поиска (max или min).
Тогда решить задачу означает одно из:
- Показать, что .
- Показать, что целевая функция не ограничена.
- Найти .
- Если , то найти .
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек таких, что всюду в некоторой их окрестности для минимума и для максимума.
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.
Метод Ньютона
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции производится при помощи отыскания стационарной точки, т.е. точки , удовлетворяющей уравнению , которое решается методом Ньютона.
Если – точка, полученная на k-м шаге, то функция аппроксимируется своим уравнением касательной:
а точка выбирается как пересечение этой прямой с осью , т.е.
.
Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных и , что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа.
Когда начальная точка итераций достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
Ограничения
Пускай задано уравнение , где и надо найти его решение.
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Теорема Канторовича.
Если существуют такие константы , что:
- на , то есть существует и не равна нулю;
- на , то есть ограничена;
- на , и ;
Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:
- на существует корень уравнения ;
- если , то итерационная последовательность сходится к этому корню: ;
- погрешность может быть оценена по формуле .
Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:
Тогда ограничения на исходную функцию будут выглядеть так:
- функция должна быть ограничена;
- функция должна быть гладкой, дважды дифференцируемой;
- её первая производная равномерно отделена от нуля;
- её вторая производная должна быть равномерно ограничена.
В случае решения задачи оптимизации под функцией понимаем ее производную.
Проблема области сходимости
Запишем итерационный процесс:
.
Известно, что условием сходимости этого процесса будет неравенство
,
где , отсюда получем условие сходимости:
.
В силу того что мы ищем корень уравнения , существует такая окрестность, где , но в общем случае эта область будет мала, то есть нужно подбирать начальное приближение достаточно близко расположенным к корню.
Теорма о сходимости метода Ньютона Пусть - простой вещественный корень уравнения , а функция - дважды дифференцируема в некоторой окрестности , причем первая произодная нигде не обращается в нуль.
Тогда, следуя обозначениям
,
При выборе начального приближения из той же окрестности такого, что
,
итерационная последовательность
будет сходиться к , причем для погрешности на k-м шаге буддет справедлива оценка:
.
Метод парабол
Относительно метода Ньютона этот метод обладает тем преимуществом, что он не требует вычисления производных функции . Однако, его сходимость может быть гарантирована лишь для достаточно регулярных функций (непрерывных и много раз дифференцируемых).
В этом методе вычисляется значение функции сразу в трех близлежащих точках , , , где h – малое число. Через эти три точки проводится интерполяционная парабола:
.
Минимум параболы достигается при , т.е. при . Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:
.
Числовой пример
Сравним работу методов Ньютона и парабол на примере много экстремальной функции при одинаковом начальном приближении:
(номер итерации) | полученное методом Ньютона | полученное методом парабол | ||
---|---|---|---|---|
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.