Глава 8. Методы одномерной минимизации

8.1. О задачах одномерной минимизации. Простой перебор

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

На первый взгляд кажется, что задача минимизации функции одного переменного является довольно элементарной. По-видимому, это мнение создается после первого знакомства с началами математического анализа. В самом деле, если функция φ(х), которую нужно минимизировать на отрезке [а, b], дифференцируема, то достаточно найти нули производной, присоединить к ним концы отрезка, выделить из этих точек локальные минимумы и, наконец, среди последних найти ту точку, в которой достигается абсолютный минимум.

Однако для широкого класса функций эта задача не так уж проста. Во-первых, задача решения уравнения φ' (х) = 0 может оказаться, как это и бывает в реальных ситуациях, весьма сложной. С другой стороны, в практических задачах часто неизвестно, является ли φ(x) дифференцируемой функцией.

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

Самым грубым в этой группе методов является метод, который каждому приходит в голову,- метод простого перебора.

Пусть φ(х) такова, что на отрезке [а, b] точка ее локального минимума х^* является точкой абсолютного минимума. Достаточно произвольным образом выбирается такая последовательность точек {x_k}, что

например,

после чего последовательно вычисляют значения φ(x_k) до тех пор, пока не наступит момент

Ясно, что

Затем вся процедура повторяется (но уже с меньшим шагом k) на отрезке [x_k-1, x_k+1]. И так до тех пор, пока не будут выполнены требования точности.