Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол
Материал из MachineLearning.
Строка 24: | Строка 24: | ||
а точка <tex>x^{k+1}</tex> выбирается как пересечение этой прямой с осью <tex>Ox</tex>, т.е. | а точка <tex>x^{k+1}</tex> выбирается как пересечение этой прямой с осью <tex>Ox</tex>, т.е. | ||
- | <tex>x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}</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>f(x)</tex> имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных <tex>f'(x)</tex> и <tex>f''(x)</tex>, что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа. | ||
Строка 61: | Строка 61: | ||
Запишем итерационный процесс: | Запишем итерационный процесс: | ||
- | <tex>x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>. | + | <p align='center'><tex>x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>.</p> |
Известно, что условием сходимости этого процесса будет неравенство | Известно, что условием сходимости этого процесса будет неравенство | ||
- | <tex>|S'(x)| \le q < 1</tex>, | + | <p align='center'><tex>|S'(x)| \le q < 1</tex>,</p> |
где <tex>S(x) = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>, отсюда получем условие сходимости: | где <tex>S(x) = x^k - \frac{f'(x^k)}{f''(x^k)}</tex>, отсюда получем условие сходимости: | ||
- | <tex>|\frac{f'(x)f'''(x)}{(f'(x))^2}| \le q < 1</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>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>, причем первая произодная нигде не обращается в нуль. | + | ''Пусть <tex>x^*</tex> - простой вещественный корень уравнения <tex>f(x) = 0</tex>, а функция <tex>f(x)</tex> - дважды дифференцируема в некоторой окрестности <tex>U_r(x^*)</tex>, причем первая произодная нигде не обращается в нуль.'' |
- | Тогда, следуя обозначениям | + | ''Тогда, следуя обозначениям'' |
- | <tex>0 < m_1 = \inf_{x\in U_r(x^*)}|f'(x)|, M_2 = \sup_{x\in U_r(x^*)}|f''(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> такого, что | + | ''При выборе начального приближения <tex>x^0</tex> из той же окрестности <tex>U_r(x^*)</tex> такого, что '' |
- | <tex>\frac{M_2|x^0 - x^*|}{2m_1} = q < 1</tex>, | + | <p align='center'><tex>\frac{M_2|x^0 - x^*|}{2m_1} = q < 1</tex>,</p> |
- | итерационная последовательность | + | ''итерационная последовательность'' |
- | <tex>x^{k+1} = x^k - \frac{f(x^k)}{f'(x^k)}, k = 0,1, \dots</tex> | + | <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-м шаге буддет справедлива оценка:'' |
- | <tex>|x^k - x^*| \le q^{2^k - 1}|x^0 - x^*|</tex>. | + | <p align='center'><tex>|x^k - x^*| \le q^{2^k - 1}|x^0 - x^*|</tex>.</p> |
== Метод парабол == | == Метод парабол == | ||
Версия 22:13, 16 ноября 2008
Содержание |
Постановка задачи одномерной оптимизации
Задача одномерной оптимизации определяется следующим образом:
- Допустимое множество — множество ;
- Целевую функцию — отображение ;
- Критерий поиска (max или min).
Тогда решить задачу означает одно из:
- Показать, что .
- Показать, что целевая функция не ограничена.
- Найти .
- Если , то найти .
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек таких, что всюду в некоторой их окрестности для минимума и для максимума.
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.
Метод Ньютона
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции производится при помощи отыскания стационарной точки, т.е. точки , удовлетворяющей уравнению , которое решается методом Ньютона.
Если – точка, полученная на k-м шаге, то функция аппроксимируется своим уравнением касательной:
а точка выбирается как пересечение этой прямой с осью , т.е.
.
Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных и , что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа.
Когда начальная точка итераций достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
Ограничения
Пускай задано уравнение , где и надо найти его решение.
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Теорема Канторовича.
Если существуют такие константы , что:
- на , то есть существует и не равна нулю;
- на , то есть ограничена;
- на , и ;
Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:
- на существует корень уравнения ;
- если , то итерационная последовательность сходится к этому корню: ;
- погрешность может быть оценена по формуле .
Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:
Тогда ограничения на исходную функцию будут выглядеть так:
- функция должна быть ограничена;
- функция должна быть гладкой, дважды дифференцируемой;
- её первая производная равномерно отделена от нуля;
- её вторая производная должна быть равномерно ограничена.
В случае решения задачи оптимизации под функцией понимаем ее производную.
Проблема области сходимости
Запишем итерационный процесс:
.
Известно, что условием сходимости этого процесса будет неравенство
,
где , отсюда получем условие сходимости:
.
В силу того что мы ищем корень уравнения , существует такая окрестность, где , но в общем случае эта область будет мала, то есть нужно подбирать начальное приближение достаточно близко расположенным к корню.
Теорма о сходимости метода Ньютона Пусть - простой вещественный корень уравнения , а функция - дважды дифференцируема в некоторой окрестности , причем первая произодная нигде не обращается в нуль.
Тогда, следуя обозначениям
,
При выборе начального приближения из той же окрестности такого, что
,
итерационная последовательность
будет сходиться к , причем для погрешности на k-м шаге буддет справедлива оценка:
.
Метод парабол
Относительно метода Ньютона этот метод обладает тем преимуществом, что он не требует вычисления производных функции . Однако, его сходимость может быть гарантирована лишь для достаточно регулярных функций (непрерывных и много раз дифференцируемых).
В этом методе вычисляется значение функции сразу в трех близлежащих точках , , , где h – малое число. Через эти три точки проводится интерполяционная парабола:
.
Минимум параболы достигается при , т.е. при . Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:
.