Метод золотого сечения

Для того чтобы уменьшить отрезок неопределённости [a, b], нам необходимо вычислить значение целевой функции f(x), по крайней мере, в двух точках на отрезке [a, b].

В результате этих двух экспериментов отрезок неопределённости сузится до отрезка [a, x₂] или [x₁, b]. Так как у нас нет никаких оснований предпочесть один из этих вариантов, то точки x₁ и x₂ должны быть симметричны относительно середины отрезка [a, b]. В этом случае длины отрезков [a, x₂] и [x₁, b] будут равны. Таким образом, остаётся вопрос как выбрать точку x₁.

В методе золотого сечения точка x₁ выбирается из соображения, что должно выполняться соотношение:

т.е. точка x₁ делит отрезок [a, b] по правилу «золотого сечения», где λ - есть «золотое отношение». Точка x₂ определяется как точка симметричная к x₁ относительно середины отрезка.

В результате экспериментов у нас получается отрезок неопределённости [a, x₂], содержащий точку x₁, или отрезок неопределённости [x₁б], содержащий точку x₂. Оказывается, что остающаяся точка на суженном отрезке неопределённости делит его вновь по правилу «золотого сечения». Следовательно, чтобы, в свою очередь, уменьшить новый отрезок неопределённости, нам не достаёт одного эксперимента, а именно, вычисления целевой функции в точке, симметричной к оставшейся точке относительно середины этого нового отрезка. Всё продемонстрировано на рисунке,

а)

б)

где буквы со штрихами обозначают новый отрезок неопределённости. Вариант а) соответствует случаю, если новым отрезком неопределённости будет [a, x₂], а вариант б) – отрезку [x₁, b].

В приводимой ниже схеме алгоритма остающиеся отрезки неопределённости переименовываются каждый раз как [a, b], а точки, в которых проводятся эксперименты на этом отрезке, обозначается через x₁ и x₂, причём . Кроме того, y₁ и y₂ имеют следующие значения: y₁ =f(x₁) и y₂ =f(x₂).

Схема алгоритма

Шаг1. Задаются a, b, ε и λ =1.618… Вычисляют .

Шаг2. а) Если , то полагают и вычисляют .

б) Если y₁> y₂, то полагают и вычисляют .

Шаг3. Если b-a> ε, то переходят к шагу 2. Иначе если y₁< y₂, то полагают и если y₁≥ y₂, то полагают и

Закончить поиск.

После каждой итерации длина отрезка неопределённости уменьшается в λ раз. Так как первая итерация начинается после двух экспериментов, то после N экспериментов длина отрезка неопределённости будет .

Метод чисел Фибоначчи

Этот метод применяется, когда число экспериментов N заранее задано. Метод чисел Фибоначчи, также как и метод золотого сечения относится к симметричным методам, т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка. Вот только выбор точки x₁ происходит на основе других соотношений. Для этого используются числа Фибоначчи: , где и F₀=F₁=1.Точка x₁ определяется из соотношения:

т.е. . Точка x₁ делит [a, b] на две неравные части. Отношение малого отрезка к большему равно . Точка x₂ определяется как точка, симметричная к x₁ относительно середины отрезка [a, b]. Поэтому . При этом будет выполняться условие x₁< x₂.

В результате экспериментов в точках x₁ и x₂ у нас получится отрезок неопределённости [a, x₂], содержащий точку x₁, или отрезок неопределённости [x₁, b], содержащий точку x₂. Остающаяся точка делит новый отрезок неопределённости на две неравные части в отношении:

. То есть в методе Фибоначчи остающаяся точка делит отрезок на две неравные части в пропорциях определяемых числами Фибоначчи. Так на к -ом шаге это отношение равно а длины отрезков равны: и . Всё это показано на рисунке:

а)

б)

Для того чтобы в свою очередь уменьшить получившийся отрезок неопределённости, надо определить симметричную точку относительно середины отрезка и произвести эксперимент в ней. Этот процесс продолжается, пока не будет проведено N экспериментов.

Схема алгоритма

Шаг 1. Задаются a, b, N Вычисляются числа Фибоначчи . Определяется:

Шаг 2. а) Если y₁≤ y₂, то полагают и вычисляют .

б) Если y₁> y₂, то полагают и вычисляют .

Повторить шаг 2 N-2 раза.

Шаг 3. Если y₁< y₂, то полагают и . Если y₁≥ y₂, то полагают и .

Закончить поиск.

Длина отрезка неопределённости в методе Фибоначчи .