Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод Ньютона. В методе Ньютона последовательность точек спуска определяется формулой (4)
|
|
В методе Ньютона последовательность точек спуска определяется формулой (4). Для текущей точки xk направление и величина спуска определяется вектором pk = – (f ''(xk)) –1·f '(xk). Хотя в определении вектора pk фигурирует обратная к f ''(xk) матрица (f ''(xk)) –1, на практике нет необходимости вычислять последнюю, так как направление спуска pk можно найти как решение системы линейных уравнений
f ''(xk)·pk = – f '(xk) (5) каким-нибудь из методов.
Схема алгоритма.
| шаг 1: | На первой итерации, при k = 0, вводятся начальное приближение x0 и условие останова ε 3. Вычисляются градиент f '(x0) и матрица f ''(x0). | ||||
| шаг 2: | Определяется направление спуска pk, как решение системы линейных уравнений f ''(xk)·pk = – f '(xk) ( например, методом исключений Гаусса). | ||||
| шаг 3: | Определяется следующая точка спуска: xk+1 = xk + pk. | ||||
| шаг 4: | Вычисляются в этой точке xk+1 градиент f '(xk+1) и матрица f ''(xk+1). | ||||
| Если ||f '(xk+1)|| £ ε 3, то поиск на этом заканчивается и полагается x = xk+1 и y = f(xk+1). Иначе k = k + 1 и переход к шагу 2. |
Особенностью метода Ньютона является то, что для квадратичной целевой функции он находит минимум за один шаг, независимо от начального приближения x0 и степени овражности.
В общем случае, когда минимизируемая функция не квадратична, вектор pk = – (f ''(xk)) –1·f '(xk) не указывает в точку её минимума, однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент. Этим и объясняется более высокая сходимость метода Ньютона по сравнению с градиентными методами при минимизации овражных целевых функций.
Недостатками метода Ньютона является то, что он, во-первых, предполагает вычисление вторых производных и, во-вторых, может расходиться, если начальное приближение находится слишком далеко от минимума.
Методы с регулировкой шага (методы Ньютона – Рафсона)
Удачный выбор начального приближения x0 гарантирует сходимость метода Ньютона. Однако отыскание подходящего начального приближения – далеко не простая задача. Поэтому необходимо как-то изменить формулу (4), чтобы добиться сходимости независимо от начального приближения. Доказано, что в некоторых предположениях для этого достаточно в методе Ньютона кроме направления движения (f ''(x)) –1·f '(x) выбирать и длину шага вдоль него. Такие алгоритмы называются методами Ньютона с регулировкой шага (методами Ньютона – Рафсона) и выглядят так:
xk+1 = xk – ak(f ''(xk)) –1·f '(xk). (6)
Как и в градиентных методах величина ak выбирается так, чтобы обеспечить убывание целевой функции на каждой итерации. Мы рассмотрим два способа выбора шага ak. Первый из них связан с проверкой неравенства
f(xk + akpk) – f(xk) £ d·ak(f '(xk), pk), (7)
где pk = – (f ''(xk)) –1·f '(xk) – направление спуска, а 0 < d < ½ – некоторое заданное число, общее для всех итераций. Если это неравенство выполнено при ak = 1, то шаг принимается равным единице и осуществляется следующая итерация. Если нет – дробится до тех пор, пока оно не выполнится.
Схема метода Ньютона – Рафсона с дроблением шага.
| шаг 1: | На первой итерации, при k = 0, вводятся исходные данные x0, d, ε 3. Вычисляются значения градиента f '(x0) и матрица f ''(x0). | ||||
| шаг 2: | Присваивается a = 1. Определяется направление спуска pk, как решение системы линейных уравнений f ''(xk)·pk = – f '(xk). | ||||
| шаг 3: | Проверяется условие f(xk + akpk) – f(xk) £ d·ak(f '(xk), pk). Если выполняется, то переход к шагу 4.Иначе дробим значение шага a (например, a = a/2) и повторяем шаг 3. | ||||
| шаг 4: | Определяется следующая точка: xk+1 = xk + a·pk. | ||||
| Вычисляются значение градиента f '(xk+1) в точке xk+1. | ||||
| шаг 6: | Если ||f '(xk+1)|| £ ε 3, то поиск на этом заканчивается и полагается x = xk+1 и y = f(xk+1). Иначе k = k + 1 и переход к шагу 2. |
Второй метод определения шага ak в схеме (6), как и в методе наискорейшего спуска состоит в минимизации функции
f(xk + akpk) = min f(xk + akpk).
Схема метода Ньютона – Рафсона с выбором оптимального шага. α ≥ 0
| шаг 1: | При k = 0, вводятся x0, ε 3. Вычисляются f '(x0) и f ''(x0). | ||||
| шаг 2: | Определение направления спуска pk, как решение системы линейных уравнений f ''(xk)·pk = – f '(xk). | ||||
| Определяется следующая точка спуска: xk+1 = xk + apk, где a - решение задачи одномерной оптимизации: min f(xk + apk). | |||||
| шаг 4: | Вычисляются в точке xk+1: f '(xk+1) и f ''(xk+1). | ||||
| Если ||f '(xk+1)|| £ ε 3, то поиск заканчивается и полагается x = xk+1 и y = f(xk+1). α ≥ 0 Иначе k = k + 1 и переход к шагу 2. |
Модификации метода Ньютона
Значительные трудности, возникающие при практической реализации метода Ньютона, связаны с необходимостью вычислить матрицу f ''(x). Мы рассмотрим две модификации метода Ньютона, которые используют не точные значения, а некоторые приближённые аналоги матрицы вторых производных. В результате уменьшается трудоёмкость методов, но, конечно, ухудшается их сходимость.
В качестве первой модификации метода Ньютона рассмотрим следующий алгоритм:
xk+1 = xk – ak(f ''(xk)) –1·f '(xk), ak ≥ 0. (8)
здесь для построения направления спуска используется один раз вычисленная и обращённая матрица вторых производных f ''(x0).
Схема модификации I метода Ньютона.
| шаг 1: | При k = 0, вводятся x0, ε 3. Вычисляются f '(x0) и f ''(x0). | ||||
| шаг 2: | Определение обратной матрицы (f ''(x0))–1. | ||||
| шаг 3: | Определение направления спуска pk: pk = – f '(xk)·(f ''(x0))–1. | ||||
| шаг 4: | Определение следующей точки: xk+1 = xk + a·pk, где a – решение задачи одномерной минимизации функции φ (a) = f(xk + a·pk), при a ≥ 0. | ||||
| Вычисление в точке xk+1.градиента f '(xk+1) | ||||
| шаг 6: | Если ||f '(xk+1)|| £ ε 3, то поиск заканчивается и полагается x = xk+1 и y = f(xk+1). Иначе k = k + 1 и переход к шагу 3. |
В рассмотренной схеме для выбора шага ak используется способ аналогичный исп–му в методе наискорейшего спуска. Но можно было бы воспользоваться и способом аналогичным используемому в градиентном методе с дроблением шага.
Если матрица f ''(x) положительно определена, то итерационный процесс (d) является одной одной из модификаций градиентного спуска, независимо от начального приближения x0.