Метод дихотомии (половинного деления).

Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B].

Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.

В начале вычислений возлагают А{0}= А, B{0}= B.

На s-у шаге определяют величины

L{s} = (А{s}+ B{s} D)/2

R{s}= (А{s}+ B{s}+ D)/2

где D > 0 — достаточно малое число. Возлагают

А{s+1}= А{s}, B{s+1}= R{s}, если F(L{s}) £ F(R{s})

А{s+1}= L{s}, B{s+1}= B{s}, если F(L{s})> F(R{s}).

Итерации продолжают до тех пор, пока не будет выполняться неравенство

B{s} А{s} £ e,

где e>0 — заданное число, которое определяет погрешность решения задачи.

За приближенное решение задачи принимают

x* = (А{s}+ B{s})/2, y* = F(x*).

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).