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

Пусть кусочно-непрерывна на отрезке и имеет на нем только один локальный минимум. Построим итерационный процесс, сходящийся к этому минимуму.

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

На отрезке снова надо выбрать две внутренние точки и вычислить в них и на концах отрезка значения функции, и сделать следующий шаг процесса. Но на предыдущем шаге вычислений мы уже нашли на концах нового отрезка и в одной его внутренней точке . Поэтому достаточно выбрать внутри еще одну точку , определить в ней значение функции и провести необходимые сравнения. Это вчетверо уменьшает объем вычислений на одном шаге процесса.

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

Иными словами, требуется разделить отрезок так, чтобы отношение между меньшей частью и большей частью было равно отношению между большей частью и целым отрезком.

или

. Сложим эти уравнения

, но , поэтому ,

, D=5,

То есть, после очередного вычисления длина отрезка уменьшается на 0.618. После n вычислений функции длина отрезка поиска минимума составит 0.618ⁿ^-3 долю первоначальной величины (три первых вычисления в точках a, b и t₁ еще не сокращают его длины). При длина отрезка стремится к нулю как геометрическая прогрессия со знаменателем 0.618, то есть метод золотого сечения всегда сходится линейно.

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

Образуем последовательность чисел так, что каждое следующее число будет суммой двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Это последовательность Фибоначчи. Найдем отношения предыдущего слагаемого к последующему:

1/2 = 0.500, 8/13 = 0.615,

2/3 = 0.666, 13/21 = 0.619,

3/5 = 0.600, 21/34 = 0.618,

5/8 = 0.625, 34/55 = 0.618.

Чем больше номер члена последовательности, тем ближе отношение к золотому сечению.

Кроме того: 0.618+1=1.618

1.618*0.618=1

1-0.618=0.382

0.618*0.618=0.382

2.618-1.618=1

2.618*0.382=1

2.618*0.618=1.618

1.618*1.618=2.618.

Алгоритм метода золотого сечения поиска минимума функции.

Пусть для единообразия , . На первом шаге выберем , . После сравнения может быть отброшена точка с любым номером, и далее точки будут перенумерованы беспорядочно. Пусть на данном шаге есть 4 точки , из которых какие-то две являются концами отрезка. Выберем ту точку, в которой функция принимает наименьшее значение; пусть это оказалась точка : .

Затем отбрасываем ту точку, которая более всего удалена от ; пусть этой точкой оказалась :

Минимум находится внутри оставшегося отрезка. Если его длина меньше заданной точности вычислений, то находим его середину и считаем ее искомым минимумом. Значение функции в этой точке указывает глубину минимума.

Метод золотого сечения напоминает метод дихотомии поиска корня уравнения. он применим и к недифференцируемым функциям и всегда сходится; сходимость его линейна. Если на отрезке [a, b] функция имеет несколько минимумов, то процесс сойдется к одному из них, но не обязательно к наименьшему.

Пример. Найти минимум функции на отрезке с точностью 0.3.