Метод дихотомииПусть задана унимодальная функция f(x). Необходимо найти минимум функции на отрезке [a,b], которому принадлежит точка локального минимума x*. Для сужения отрезка унимодальности используем точки x1, x2, расположенные симметрично относительно середины отрезка [a,b]. Пусть известен отрезок [an-1;bn-1], находим середину отрезка: Вычисляем значения функции в точках xn±δ, сравниваем их: 1) если f(xn-δ)<f(xn+δ), то an=an-1, bn=xn+δ 2) если f(xn-δ)>f(xn+δ), то an= xn-δ, bn=bn-1 В результате приходим к последовательности вложенных отрезков, таких что точка локального минимума принадлежит каждому из них и является общим пределом последовательности.
|
