Метод Ньютона. Метод Стеффенсена

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Метод Ньютона)
(→См. также: поправил ссылку)
 
(37 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
==Постановка задачи==
+
==Введение==
-
==Общие понятния==
+
Часто приходится искать методы для решения задач оптимизации, а когда нашли много методов, выбирать подходящий. Здесь мы рассмотрим и сравним два метода минимизации многомерных функций.
-
Если минимизируемая функция дважд непрерывно дифференцируема и производные <tex>J'(u), J''(u)</tex> просто вычисляются, то можно применять методы минимизации второго порядка, которые используют квадратичную часть разложения функции в ряд Тейлора. Поскольку квадратичная часть разложения аппроксимирует функцию гораздо точнее, чем линейная, то естесвенно ожидать, что методв второго порядка сходятся быстрее, чем методы первого. Метод Ньютона, имеющий квадратичную скорость сходимости на классе сильно выпуклых функций.
+
 
-
Говорят, что последовательность <tex>{u_k}</tex>сходитcz к <tex>u_*</tex> с линейной скоростью или со скоростью геометрической прогресси (со знаменателем q), если начиная с некоторго номера, выполняется неравенство <tex>|u_{k+1}-u_*|<q|u_k-u_*| (0<q<1);</tex> при выполнении неравенства <tex>|u_{k+1}-u_*|<q_k|u_k-u_*|</tex>, где <tex>{q_k}->0</tex>, говорят о сверхлинейной скорости сходимости последованояти <tex>{u_k}</tex> к <tex>u_*</tex>, а если здесь <tex>q_k=C|u_k-u_*|^{s-1}</tex>, т. е. <tex>|u_{k+1}-u_*|<C|u_k-u_*|^s</tex>, то говорят о скорости сходимсоти порядка s. При s=2, говорят о квадратичной скорости сходимости.
+
Необходимо ввести некоторые понятия.
 +
Если минимизируемая функция дважды непрерывно дифференцируема и производные <tex>J'(u), J''(u)</tex> просто вычисляются, то можно применять методы минимизации второго порядка, которые используют квадратичную часть разложения функции в ряд Тейлора. Поскольку квадратичная часть разложения аппроксимирует функцию гораздо точнее, чем линейная, то естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого. Метод Ньютона имеет квадратичную скорость сходимости на классе сильно выпуклых функций.
 +
Говорят, что последовательность <tex>{u_k}</tex> сходитcя к <tex>u_*</tex> с линейной скоростью или со скоростью геометрической прогрессии (со знаменателем q), если начиная с некоторого номера, выполняется неравенство <tex>|u_{k+1}-u_*|<q|u_k-u_*| (0<q<1);</tex> при выполнении неравенства <tex>|u_{k+1}-u_*|<q_k|u_k-u_*|</tex>, где <tex>{q_k}->0</tex>, говорят о сверхлинейной скорости сходимости последовательности <tex>{u_k}</tex> к <tex>u_*</tex>, а если здесь <tex>q_k=C|u_k-u_*|^{s-1}</tex>, т. е. <tex>|u_{k+1}-u_*|<C|u_k-u_*|^s</tex>, то говорят о скорости сходимости порядка s. При s=2, говорят о квадратичной скорости сходимости.
==Метод Ньютона==
==Метод Ньютона==
-
Рассмотирим метод Ньютона для задачи
+
Рассмотрим метод Ньютона для задачи
 +
 
 +
{{ eqno | 1 }}
 +
 
<tex> J(u)-> \inf; u \in U,</tex>
<tex> J(u)-> \inf; u \in U,</tex>
где <tex>J(u) _in C^2(U)</tex>, U - выпуклое замкнутое множество из E^n. Пусть <tex>u_0</tex>∈U - некоторое начальное приближение. Если известно k-е приближение <tex>u_k</tex>, то приращение функции J(u)∈ <tex>C^2(U)</tex> в точек <tex>u_k</tex> можно представить в виде
где <tex>J(u) _in C^2(U)</tex>, U - выпуклое замкнутое множество из E^n. Пусть <tex>u_0</tex>∈U - некоторое начальное приближение. Если известно k-е приближение <tex>u_k</tex>, то приращение функции J(u)∈ <tex>C^2(U)</tex> в точек <tex>u_k</tex> можно представить в виде
Строка 13: Строка 18:
Возьмем квадратичную часть этого приращения
Возьмем квадратичную часть этого приращения
-
{{eqno||2}}
+
 
 +
{{ eqno | 2 }}
 +
 
<tex> J_k(u)=<J'(u_k),u-u_k>+1/2*<J''(u_k)(u-u_k),u-u_k> </tex>
<tex> J_k(u)=<J'(u_k),u-u_k>+1/2*<J''(u_k)(u-u_k),u-u_k> </tex>
и определим вспомогательное приближение <tex>u_k</tex> из условий
и определим вспомогательное приближение <tex>u_k</tex> из условий
 +
 +
{{ eqno | 3 }}
<tex>u_k \in U, J_k(u_k)=\inf_U J_k(u).</tex>
<tex>u_k \in U, J_k(u_k)=\inf_U J_k(u).</tex>
Следущее (k+1)-e приближение будем искать в виде
Следущее (k+1)-e приближение будем искать в виде
 +
 +
{{ eqno | 4 }}
<tex>u_{k+1}=u_k+\alpha_k(\overline{u_k}-u_k), 0<\alpha_k<1. </tex>
<tex>u_{k+1}=u_k+\alpha_k(\overline{u_k}-u_k), 0<\alpha_k<1. </tex>
-
В зависимости от способа выбора величины <tex>\alpha_k</tex> в (4) можно получить различные варианты метода Ньютона. Укажем несколько наиболее употребительных способов выбора <tex>\alpha_k</tex>.
+
В зависимости от способа выбора величины <tex>\alpha_k</tex> в (4) можно получить различные варианты метода Ньютона. Укажем наиболее употребительный способ выбора <tex>\alpha_k</tex>.
-
===1) <tex>\alpha_k=1</tex>
+
<tex>\alpha_k=1</tex>
-
Тогда <tex>u_{k+1}=\overline{u_k} (k=0,1,\dots)</tex>, т. е. условие (3) сразу определяет следующее (k+1)-е приближение. Иначе говоря,
+
-
<tex> u_{k+1}\in U, J_k(u_{k+1})=\inf\limits_U J_k(u), k=0,1,\dots </tex>
+
{{ eqno | 5 }}
 +
<tex>\alpha_k=1, k=0,1,\dots </tex>
 +
Тогда <tex>u_{k+1}=\overline{u_k} (k=0,1,\dots)</tex>, т.е. условие (3) сразу определяет следующее (k+1)-е приближение. Иначе говоря,
-
Таким образом получаем систему линейный уровнений, которую необходимо решать на каждой итерации.
+
{{ eqno | 6 }}
 +
<tex> u_{k+1}\in U, J_k(u_{k+1})=\inf\limits_U J_k(u), k=0,1,\dots </tex>
 +
В частности, когда U=E^n, в точке минимума функции J_k(u) ее производная J'_k(u) обращается в нуль. Таким образом, получаем систему линейных уравнений относительно <tex>u_{k+1}-u_k</tex>, которую необходимо решать на каждой итерации.
 +
 +
{{ eqno | 7 }}
<tex> J'_k(u_{k+1})=J'(u_k)+J''(u_k)(u_{k+1}-u_k)=0. </tex>
<tex> J'_k(u_{k+1})=J'(u_k)+J''(u_k)(u_{k+1}-u_k)=0. </tex>
 +
 +
Если матрица <tex>J''(u_k)</tex> невырожденная, то имеем
 +
 +
{{ eqno | 8 }}
 +
<tex> u_{k+1}=u_k-(J''(u_k))^{-1}J'(u_k), k=0,1,\dots </tex>
 +
 +
== Метод Стеффенсена==
 +
В методе Ньютона необходимо на каждой итерации вычислять матрицу вторых производных. Поэтому, когда вычисление матрицы вторых производных требует больших объемов вычислений, трудоемкость каждой итерации значительно возрастает. Таким образом, требуется метод, который может обойти эту проблему. Одним из таких методов является метод Стеффенсена, который является разностным аналогом метода Ньютона. Матрица вторых производных заменяется разностным отношением первых производных градиента по специальным узловым точкам.
 +
Применим этот метод к решению следующей системы уравнений:
 +
<tex>J'(u)=[J_{u^1},\ldots,J_{u^n}(u)]=0</tex>, получим следующий итерационный метод решения задачи минимизации
 +
{{eqno | 1}}
 +
<tex>J(u)->\inf, u \in U=E^n</tex>.
 +
 +
Если приближение <tex>u_k (k\ge 0)</tex> уже известно, то следующее приближение <tex>u_{k+1}</tex> определяется так:
 +
{{eqno | 2}}
 +
<tex>u_{k+1}=u_k-(J'(u_k,u_k-\beta_kJ'(u_k)))^{-1}J'(u_k), k=0, 1, \ldots,</tex>
 +
 +
где \beta_k - числовой параметр, <tex>J'(u,v)={J_{ij}(u,v)}</tex> - матрица разделенных разностей первых производных, определяемая по правилу:
 +
 +
<tex>u^j\ne v^j </tex>&nbsp;:&nbsp;<tex> \frac{J_{u^i}(v^1,\ldots,v^{j-1},u^j,u^{j+1},\ldots,u^n)-J_{u^i}(v^1,\ldots,v^{j-1},v^j,u^{j+1},\ldots,u^n)}{u^j-v^j}</tex> ,
 +
<tex>u^j=v^j </tex>&nbsp; : &nbsp;<tex> J_{u^i u^j}(v^1,\ldots,v^{j-1},v^j,u^{j+1},\ldots,u^n) </tex>,
 +
 +
где <tex>J_{ij}(u,v)</tex> - элемент i-й строки j-го столбца матрицы <tex>J'(u,v)</tex>,а <tex> J_{u^i}(u), J_{u^i u^j}(u) </tex>, как и выше, обозначает первые и, соответственно, вторые производные по переменным <tex>u^i, u^j</tex> функции J(u) (i,j=1,...,n). J(u) дважды непрерывно дифференцируема.
 +
 +
==Числовой пример==
 +
 +
Рассмотрим работу программы, реализующую метод Стефенсена.
 +
Функция для минимизации : <tex>f(x)=40(x_4-x_0)^2+40(x_3-x_0)^2+40(x_2-x_0)^2+40*(x_1-x_0)^2+(x_0^2-3)^2</tex>
 +
 +
{|class = "standard"
 +
! rowspan = 2 | <tex> \varepsilon </tex>
 +
! colspan = 3 | Метод Стеффенсена
 +
|-
 +
!Число итераций
 +
!Найденное решение
 +
!Значение функции
 +
|-
 +
| 0.1
 +
| 2 || (1.75942 1.75937 1.75937 1.75937 1.75937) || 0.000977495
 +
|-
 +
| 0.01
 +
| 11 || (1.69302 1.69297 1.69297 1.69297 1.69297) || 0.000387751
 +
|-
 +
| 0.0000001
 +
| 14 || (1.69312 1.69307 1.69307 1.69307 1.69307)|| 0.000316642
 +
|-
 +
|}
 +
 +
Как мы можем наблюдать на данном примере, метод Стеффенсена обеспечивает быструю сходимость, не теряя при этом в точности.
 +
 +
==Программная реализация==
 +
* [[Media:AlinaSteffensen.zip|Реализация метода Стеффенсена]]
 +
 +
== См. также ==
 +
* [[Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол]]
 +
 +
==Список литературы==
 +
 +
* ''Ф.П.Васильев.''&nbsp; Численные методы решения экстремальных задач. Наука 1988г.
 +
 +
[[Категория:Численные методы безусловной оптимизации|Ньютона]]

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

Содержание

Введение

Часто приходится искать методы для решения задач оптимизации, а когда нашли много методов, выбирать подходящий. Здесь мы рассмотрим и сравним два метода минимизации многомерных функций.

Необходимо ввести некоторые понятия. Если минимизируемая функция дважды непрерывно дифференцируема и производные J'(u), J''(u) просто вычисляются, то можно применять методы минимизации второго порядка, которые используют квадратичную часть разложения функции в ряд Тейлора. Поскольку квадратичная часть разложения аппроксимирует функцию гораздо точнее, чем линейная, то естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого. Метод Ньютона имеет квадратичную скорость сходимости на классе сильно выпуклых функций. Говорят, что последовательность {u_k} сходитcя к u_* с линейной скоростью или со скоростью геометрической прогрессии (со знаменателем q), если начиная с некоторого номера, выполняется неравенство |u_{k+1}-u_*|<q|u_k-u_*| (0<q<1); при выполнении неравенства |u_{k+1}-u_*|<q_k|u_k-u_*|, где {q_k}->0, говорят о сверхлинейной скорости сходимости последовательности {u_k} к u_*, а если здесь q_k=C|u_k-u_*|^{s-1}, т. е. |u_{k+1}-u_*|<C|u_k-u_*|^s, то говорят о скорости сходимости порядка s. При s=2, говорят о квадратичной скорости сходимости.

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

Рассмотрим метод Ньютона для задачи

( 1 )

J(u)-> \inf; u \in U, где J(u) _in C^2(U), U - выпуклое замкнутое множество из E^n. Пусть u_0∈U - некоторое начальное приближение. Если известно k-е приближение u_k, то приращение функции J(u)∈ C^2(U) в точек u_k можно представить в виде

J(u)-J(u_k)=<J'(u_k),u-u_k>+1/2*<J''(u_k)(u-u_k),u-u_k>+o(|u-u_k|^2)

Возьмем квадратичную часть этого приращения

( 2 )

J_k(u)=<J'(u_k),u-u_k>+1/2*<J''(u_k)(u-u_k),u-u_k>

и определим вспомогательное приближение u_k из условий

( 3 )

u_k \in U, J_k(u_k)=\inf_U J_k(u).

Следущее (k+1)-e приближение будем искать в виде

( 4 )

u_{k+1}=u_k+\alpha_k(\overline{u_k}-u_k), 0<\alpha_k<1.

В зависимости от способа выбора величины \alpha_k в (4) можно получить различные варианты метода Ньютона. Укажем наиболее употребительный способ выбора \alpha_k. \alpha_k=1

( 5 )

\alpha_k=1, k=0,1,\dots Тогда u_{k+1}=\overline{u_k} (k=0,1,\dots), т.е. условие (3) сразу определяет следующее (k+1)-е приближение. Иначе говоря,

( 6 )

u_{k+1}\in U, J_k(u_{k+1})=\inf\limits_U J_k(u), k=0,1,\dots

В частности, когда U=E^n, в точке минимума функции J_k(u) ее производная J'_k(u) обращается в нуль. Таким образом, получаем систему линейных уравнений относительно u_{k+1}-u_k, которую необходимо решать на каждой итерации.

( 7 )

J'_k(u_{k+1})=J'(u_k)+J''(u_k)(u_{k+1}-u_k)=0.

Если матрица J''(u_k) невырожденная, то имеем

( 8 )

u_{k+1}=u_k-(J''(u_k))^{-1}J'(u_k), k=0,1,\dots

Метод Стеффенсена

В методе Ньютона необходимо на каждой итерации вычислять матрицу вторых производных. Поэтому, когда вычисление матрицы вторых производных требует больших объемов вычислений, трудоемкость каждой итерации значительно возрастает. Таким образом, требуется метод, который может обойти эту проблему. Одним из таких методов является метод Стеффенсена, который является разностным аналогом метода Ньютона. Матрица вторых производных заменяется разностным отношением первых производных градиента по специальным узловым точкам. Применим этот метод к решению следующей системы уравнений: J'(u)=[J_{u^1},\ldots,J_{u^n}(u)]=0, получим следующий итерационный метод решения задачи минимизации

( 1)

J(u)->\inf, u \in U=E^n.

Если приближение u_k (k\ge 0) уже известно, то следующее приближение u_{k+1} определяется так:

( 2)

u_{k+1}=u_k-(J'(u_k,u_k-\beta_kJ'(u_k)))^{-1}J'(u_k), k=0, 1, \ldots,

где \beta_k - числовой параметр, J'(u,v)={J_{ij}(u,v)} - матрица разделенных разностей первых производных, определяемая по правилу:

u^j\ne v^j  :  \frac{J_{u^i}(v^1,\ldots,v^{j-1},u^j,u^{j+1},\ldots,u^n)-J_{u^i}(v^1,\ldots,v^{j-1},v^j,u^{j+1},\ldots,u^n)}{u^j-v^j} , u^j=v^j   :   J_{u^i u^j}(v^1,\ldots,v^{j-1},v^j,u^{j+1},\ldots,u^n) ,

где J_{ij}(u,v) - элемент i-й строки j-го столбца матрицы J'(u,v),а J_{u^i}(u), J_{u^i u^j}(u) , как и выше, обозначает первые и, соответственно, вторые производные по переменным u^i, u^j функции J(u) (i,j=1,...,n). J(u) дважды непрерывно дифференцируема.

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

Рассмотрим работу программы, реализующую метод Стефенсена. Функция для минимизации : f(x)=40(x_4-x_0)^2+40(x_3-x_0)^2+40(x_2-x_0)^2+40*(x_1-x_0)^2+(x_0^2-3)^2

\varepsilon Метод Стеффенсена
Число итераций Найденное решение Значение функции
0.1 2 (1.75942 1.75937 1.75937 1.75937 1.75937) 0.000977495
0.01 11 (1.69302 1.69297 1.69297 1.69297 1.69297) 0.000387751
0.0000001 14 (1.69312 1.69307 1.69307 1.69307 1.69307) 0.000316642

Как мы можем наблюдать на данном примере, метод Стеффенсена обеспечивает быструю сходимость, не теряя при этом в точности.

Программная реализация

См. также

Список литературы

  • Ф.П.Васильев.  Численные методы решения экстремальных задач. Наука 1988г.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0._%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%A1%D1%82%D0%B5%D1%84%D1%84%D0%B5%D0%BD%D1%81%D0%B5%D0%BD%D0%B0»