В методе перебора точки xi , в которых определяются значения f (x) ,

выбираются заранее (прямые методы пассивного поиска). Если же для выбора очередной точки вычисления f (x) использовать информацию, содержащуюся в

уже найденных ее значениях, то поиск точки минимума можно сделать более эффективным, т.е. сократить число определяемых для этого значений f (x)

(прямые методы последовательного поиска). Метод поразрядного поиска является одним из таких методов.

f (x1 ) ≥ f (x2 ) . Описанную процедуру можно повторить необходимое число раз,

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

Чтобы относительное уменьшение отрезка на каждой итерации не зависело от того, какая из его частей исключается из дальнейшего рассмотрения, пробные точки имеет смысл располагать симметрично относительно середины исходного отрезка. В зависимости от способа выбора пробных точек в этом случае получаются различные методы исключения отрезков. Рассмотрим только методы дихотомии и золотого сечения.

2.4.Метод дихотомии

Вэтом методе пробные точки x1 и x2 располагаются близко к середине очередного

отрезка [a, b] , т.е.

где δ − малое число. При этом отношение длин нового и исходного отрезков

τ = bb−−xa1 = xb2 −−aa близко к 12 , этим и объясняется название метода.

Отметим, что для любых точек x1 и x2 величина τ > 12 , поэтому указанный

выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска x .

24

Вконце вычислений методом дихотомии в качестве приближенного значения

xберут середину последнего из найденных отрезков [a, b] , убедившись

предварительно, что достигнуто неравенство b −2 a ≤ε .

Алгоритм метода деления отрезка пополам следующий.

Шаг 1. Определить x1 и x2 по формуле (2.3) и вычислить f (x1 ) и f (x2 ) .

Перейти к шагу 2.

Шаг 2. Сравнить f (x1 ) и f (x2 ) . Если f (x1 ) ≤ f (x2 ) , то перейти к отрезку [a, x2 ] , положив b = x2 , иначе − к отрезку [x1 , b], положив a = x1 . Перейти к шагу 3.

Если εn > ε , то перейти к следующей итерации, вернувшись к шагу 1. Если εn ≤ ε ,

то завершить поиск x , перейдя к шагу 4.

Шаг 4. Положить x ≈ x = a +2 b , f ≈ f (x) .

Необходимо обратить внимание на следующее.

1. Число δ из (2.3) выбирается на интервале (0, 2ε) с учетом следующих

соображений:

а) чем меньше δ , тем больше относительное уменьшение длины отрезка на каждой итерации;

б) при чрезмерно малом δ сравнение значений функции f (x) в точках x1 и x2 ,

отличающихся на величину δ , затруднительно, поэтому необходимо учитывать количество верных разрядов функции f (x) при задании аргумента x .

2.Число n итераций метода дихотомии, необходимое для определения точки

xс точностью ε , определяется неравенством

при котором одна из них становится пробной точкой на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода золотого сечения, кроме первой, ограничиться определением только одного значения f (x) , так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и x2 , обладающие указанным свойством.

Рассмотрим сначала отрезок [0,1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть x2 =τ , тогда симметрично расположенная точка x1 =1−τ (рис.2.1).

Рис.2.1. Иллюстрация выбора пробных точек в методе золотого сечения

Для произвольного отрезка [a, b] выражения для пробных точек примут вид

27

На каждой итерации отрезок поиска точки минимума уменьшается в одном и

а условием окончания поиска точки x с точностью ε служит неравенство εn ≤ ε .

Необходимо обратить внимание на следующее.

1. Точки x1 и x2 из (2.6) обладают следующим свойством: каждая из них делит отрезок [a, b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей части отрезка. Точки с таким свойством называются точками золотого сечения отрезка [a, b] . Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (2.6) одна из

итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя (2.6).

4.В конце вычислений по методу золотого сечения в качестве приближенного значения x можно взять середину последнего из полученных отрезков x = a +2 b .

5.Число итераций, необходимое для достижения заданной точности ε , можно

найти из условия εn ≤ ε с учетом соотношения (2.7)