Методы одномерной оптимизации. Метод Ньютона.

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

Пусть f(x) – дважды непрерывно дифференцируемая функция, причем f ''(x) > 0. Тогда, решение задачи минимизации функции f (x) сводится к решению нелинейного уравнения f '(x) = 0.

Метод Ньютона является наиболее эффективным методом решения нелинейных уравнений.

Пусть корень x* Î [a, b], так, что f '(a)f '(b) < 0. Положим x₀ = b. Проведем касательную к графику функции y = f '(x) в точке B₀ = (x₀, f '(x₀))

Рис. 1.5

Уравнение касательной будет иметь вид:

y – f '(x₀) = f"(x₀)(x – x₀). (1.16)

Первое пересечение получим, взяв абсциссу точки пересечения этой касательной с осью OX, т. е. положив в (1.16) y = 0, x = x1:

x₁ = x₀ – . (1.17)

Аналогично поступим с точкой B₁(x₁, f '(x₁)), затем с точкой B₂(x₂, f '(x₂)), и т. д. в результате получим последовательность приближений x1, x2, …, xn , …, причем

x_{n +1} = x_n – . (1.18)

Формула (1.18) является расчетной формулой метода Ньютона.

При заданной точности e > 0 вычисления по формуле (1.18) нужно вести до тех пор, пока не будет выполнено неравенство | f '(xn)| £ e, после чего полагают x* » x_n.