Метод Ньютона. Метод Стеффенсена
Материал из MachineLearning.
(→Метод Ньютона) |
|||
| Строка 33: | Строка 33: | ||
<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> в (4) можно получить различные варианты метода Ньютона. Укажем наиболее употребительный способ выбора <tex>\alpha_k</tex>. |
<tex>\alpha_k=1</tex> | <tex>\alpha_k=1</tex> | ||
| Строка 43: | Строка 43: | ||
<tex> u_{k+1}\in U, J_k(u_{k+1})=\inf\limits_U J_k(u), k=0,1,\dots </tex> | <tex> u_{k+1}\in U, J_k(u_{k+1})=\inf\limits_U J_k(u), k=0,1,\dots </tex> | ||
| - | Таким образом получаем систему линейных уровнений относительно <tex>u_{k+1}-u_k</tex>, которую необходимо решать на каждой итерации. | + | В часности, когда U=E^n, в точке минимума функции J_k(u) ее производная J'_k(u) обращается в нуль.Таким образом получаем систему линейных уровнений относительно <tex>u_{k+1}-u_k</tex>, которую необходимо решать на каждой итерации. |
{{ eqno | 7 }} | {{ eqno | 7 }} | ||
| Строка 53: | Строка 53: | ||
<tex> u_{k+1}=u_k-(J''(u_k))^{-1}J'(u_k), k=0,1,\dots </tex> | <tex> u_{k+1}=u_k-(J''(u_k))^{-1}J'(u_k), k=0,1,\dots </tex> | ||
| - | + | == Сходимость метода Ньютона == | |
| - | + | ||
| - | <tex></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>. | ||
Версия 20:19, 24 ноября 2008
Содержание |
Постановка задачи
Общие понятния
Если минимизируемая функция дважд непрерывно дифференцируема и производные просто вычисляются, то можно применять методы минимизации второго порядка, которые используют квадратичную часть разложения функции в ряд Тейлора. Поскольку квадратичная часть разложения аппроксимирует функцию гораздо точнее, чем линейная, то естесвенно ожидать, что методв второго порядка сходятся быстрее, чем методы первого. Метод Ньютона, имеющий квадратичную скорость сходимости на классе сильно выпуклых функций.
Говорят, что последовательность
сходитcz к
с линейной скоростью или со скоростью геометрической прогресси (со знаменателем q), если начиная с некоторго номера, выполняется неравенство
при выполнении неравенства
, где
, говорят о сверхлинейной скорости сходимости последованояти
к
, а если здесь
, т. е.
, то говорят о скорости сходимсоти порядка s. При s=2, говорят о квадратичной скорости сходимости.
Метод Ньютона
Рассмотирим метод Ньютона для задачи
где
, U - выпуклое замкнутое множество из E^n. Пусть
∈U - некоторое начальное приближение. Если известно k-е приближение
, то приращение функции J(u)∈
в точек
можно представить в виде
Возьмем квадратичную часть этого приращения
и определим вспомогательное приближение из условий
Следущее (k+1)-e приближение будем искать в виде
В зависимости от способа выбора величины в (4) можно получить различные варианты метода Ньютона. Укажем наиболее употребительный способ выбора
.
Тогда
, т. е. условие (3) сразу определяет следующее (k+1)-е приближение. Иначе говоря,
В часности, когда U=E^n, в точке минимума функции J_k(u) ее производная J'_k(u) обращается в нуль.Таким образом получаем систему линейных уровнений относительно , которую необходимо решать на каждой итерации.
Если матрица невырожденная, то имеем
Сходимость метода Ньютона
Метод Стефенсена
В методе Ньютона необходимо на каждой итерации вычислять матрицу вторых производных. Поэтому, когда вычисление матрицы вторых производных требует больших объемов вычислений, трудоемкость каждой итерации значительно возрастает. Таким образом, требуется метод, который может обойти эту проблему. Одним из методов является метод Стефенсена, который является разностным аналогом метода Ньютона. Матрица вторых производных заменяется разностным отношением первых производных градиента по специальным узловым точкам.
Применим этот метод к решению следущей системы уравнений:
, получим следущий итерационный метод решения задачи минимизации
.
