Определение: «золотым сечением» отрезка называется его деление на две части таким образом, что отношение длины отрезка к его большей части равно отношению большей части к меньшей.

Следовательно, для отрезка единичной длины: 1/ t = t /(1- t) ® t²+t -1=0 ®

Алгоритм метода «золотого сечения» при поиске минимума функции f (x) включает операции:

1) интервал (а, b) делится точками х₁, х₂ в отношении «золотого сечения»:

x₁ = a +(b-a)× (3- )/2, x₂ = b- (b-a)× (3- )/2;

2) вычисляются значения функции f (x₁) и f (x₂);

3) если f (x₁) < f (x₂), то от интервала (а, b) отсекается его правая часть: b = x₂, в противном случае - левая: a = x₁;

4) в случае b = x₂ точка x₁ осуществляет «золотое сечение» нового интервала (а, b) и играет в нем роль точки х₂, а точка х₁ нового интервала определяется аналогично п.1); при а=х₁ наоборот - х₁ = х₂, а точка х₂ нового интервала (а, b) определяется как в п.1).

Для нового интервала (а, b) вновь выполняются действия п.п. 2)-4), причем

в п.2) значение функции f (x) вычисляется один раз: только для вновь определяемой точки х₁ или х₂. Процесс деления интервала продолжается до тех пор, пока его длина не станет меньше заданной точности: b-а < e. При завершении процесса поиска за точку минимума принимается значение х* = (а+b)/2.

Число модификаций исходного интервала (a, b) при использовании метода «золотого сечения» больше, чем при использовании метода Больцано (от интерва-

ла отсекается не половина, а 0.382 его длины), но количество вычислений значения функции f (x) существенно меньше. Поэтому в случаях, когда значение f (x) вычисляется достаточно долго, метод «золотого сечения» имеет заметное преимущество перед методом Больцано.

Пошаговый метод применяется в тех случаях, когда интервал (а, b) оси х, содержащий точку экстремума функции f (x) неизвестен, но известно, что экстре-мум находится в окрестности экспериментально найденной точки х₀. Этот метод применяется на практике значительно чаще методов Больцано и «золотого сечения», т.к. условие сходимости его алгоритма намного проще: для этого достаточно, чтобы функция f (x) была непрерывна в окрестности т. х₀.

При поиске минимума функции метод заключается в

следующем:

1) выполняется пробный шаг от точки х₀ с целью выбора направления поиска:

x = x₀ + x (x ~ 0.5× e) и вычисляются значения f (х₀), f (х);

2) если f (х) < f (х₀), то величина основного шага, с которым осуществляется движение в направлении убывания функции, положительна (h > 0), в противном случае - отрицательна (h < 0);

3) движение в выбранном направлении с шагом h: x_k+1 = x_k+h, k =0, 1, 2...

осуществляется до тех пор, пока f (x_k+1) < f (x_k);

4) если f (x_k+1) ≥ f (x_k), то при выполнении условия h < ε процесс поиска заканчивается, а если h ³ ε, то шаг дробится: h =| h |/ p, p > 1 и осуществляется возврат

к п. 1) с начальной точкой х₀ = x_k.

В качестве коэффициента дробления шага p используют 2, 3, 5, но чаще всего p = e = 2.71828. По завершении процесса поиска за точку экстремума принимается значение x* =(x_k+1 + x_k)/2.