Тогда следующее направление вычисляется по формуле:

где непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.

Это выражение может быть переписано в более удобном итеративном виде:

Алгоритм

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

· Пусть на некотором шаге мы находимся в точке , и — направление антиградиента. Положим , где выбирают либо (стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с ), либо (алгоритм Полака–Райбера). После чего найдем минимум в направлении и обозначим точку минимума . Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив и повторив шаг.

Формализация

1. Задаются начальным приближением и погрешностью:

2. Рассчитывают начальное направление:

3.

o Если или , то и останов.

o Иначе если , то и переход к 3; иначе и переход к 2.

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

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

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

Обоснование

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

Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:

В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна, окончательная формула для такова:

С учётом этого функцияопределяется выражением:

Эта функция в окрестности корня осуществляет сжимающее отображение^[1] , и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню уравнения .

Рисунок 1 - Иллюстрация метода Ньютона (синим изображена функция , нуль которой необходимо найти, красным — касательная в точке очередного приближения ). Здесь мы можем увидеть, что последующее приближение лучше предыдущего .

Геометрическая интерпретация

Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.

Пусть — определённая на отрезке и дифференцируемая на нём вещественнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:

где α — угол наклона касательной в точке .

Следовательно искомое выражение для имеет вид: