Градиентный поиск методом Ньютона

Выше было показано, что процесс градиентного поиска для одной переменной является критическим при , т. е. когда

В этом случае процесс за один шаг сходится к квадратичным функциям СКО и алгоритм его реализации называется методом Ньютона, так как он связан с элементарными вычислениями при нахождении корней полинома. Рассмотрим теперь вопрос применения этого метода к функциям одного весового коэффициента (одной переменной) и затем распространим его на рабочую функцию многих переменных.

Метод Ньютона [2] является прежде всего методом нахождения нулей функции, допустим функции , т. е. методом решения уравнения . Он состоит в том, что задается начальное значение , а затем для вычисления следующей оценки находится первая производная . Как показано на рис. 4.4, w находится как пересечение касательной в точке с осью w. Таким образом, из рис. 4.4

или

Следующую точку, вычисляют, используя в качестве начальной точки , и т. д. В общем случае

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

Равенство (4.22) называют непрерывной формой метода Ньютона, так как в явном виде использована непрерывная функция и ее производная. Кроме того, существует и применяется дискретная форма этого метода, когда необходимо вычислить .

Рис. 4.4. Метод Ньютона при нахождении пуля функции состоит в переходе от к по касательной к

Полагая, что функция известна, или ее можно точно вычислить, на основании формулы обратной разности можно определить

Подставляя эту приближенную формулу в (4.22), получаем выражение для дискретной формы метода Ньютона:

(4.24)

Отметим, что в (4.24), а также в (4.22) на каждой итерации необходимо проверять, не обращается ли знаменатель в нуль. Пока будем пользоваться непрерывной формой метода Ньютона.

Как и выше, поиск минимума рабочей функции методом Ньютона необходимо начать с уравнения вида . В общем случае этим уравнением, как и в (2.16), является уравнение или , так как требуется найти минимум . Таким образом, для рабочей функции одной переменной

Поэтому, например, непрерывная форма (4.22) принимает вид

Отметим, что дискретная форма алгоритма в соответствии с (4.23) теперь представляет собой аппроксимацию второй производной функции

Если рабочая функция является квадратичной, как это было во всех предыдущих рассуждениях, то применение метода Ньютона приводит, как показано на рис. 4.2, к решению за один шаг. Подстановка (4.2) в (4.26) при дает

Таким образом, метод Ньютона прост для применения в случае одной переменной, когда рабочая функция является квадратичной и определена для всех значений

Возможны два случая, когда метод Ньютона усложняется. Во-первых, бывает необходимо вычислить и в (4.26), когда точно не известна функция Вопрос оценки градиента обсуждается в гл. 5. Во-вторых, рабочая функция может не быть квадратичной. До сих пор рассматривался только такой адаптивный линейный сумматор, для которого — квадратичная функция, но ниже вводятся другие адаптивные структуры, имеющие неквадратичные рабочие функции. Пример такой системы приведен на рис. 4.5, где изображен график рабочей функции для конкретного рекурсивного адаптивного фильтра. Отметим, что даже если рабочая функция является неквадратичной, то при начальном весовом коэффициенте метод Ньютона приводит почти к оптимальной точке всего лишь после четырех итераций. Однако при некоторых начальных значениях весового коэффициента для данного примера метод Ньютона не приводит к оптимуму. Дальнейшее рассмотрение этого примера проводится в упражнениях 7—9.