Основы теории оптимизации (стр. 17 )

При выводе x – координата точки, в которой функция F(x) имеет минимум (или максимум), FM – значение функции F(x) в этой точке.

on_load_lecture(); 2. Метод "золотого сечения"

Следующий из методов одномерной оптимизаци называется методом "золотого сечения".

Рассмотрим геометрическую суть метода «золотое сечение».

Числа Фибоначчи и метод золотого сечения

1. Разделим отрезок АВ единичной длины (рис. 13) на две части так, чтобы большая из его частей явля­лась средним пропорциональным между меньшей его частью и всем отрезком.

Рис. 4.

Обозначим для этого искомую длину большей ча­сти отрезка через х. Очевидно, длина его меньшей части при этом будет равна 1—х, и условие задачи даст пропорцию

(5)

откуда

(6)

Положительным корнем (6) является так что отношения в пропорции (5) равны

каждое. Такое деление (точкой C1) называется деле­нием в среднем и крайнем отношении. Его часто на­зывают также золотым делением или золотым се­чением.

Если взять отрицательный корень уравнения (6), то делящая точка C2 окажется вне отрезка АВ (такого рода деление в геометрии называется внешним деле­нием), как это видно из рис. 4. Легко показать, что и здесь мы имеем дело с золотым сечением;

2. Фактическое построение точки, делящей отре­зок золотым сечением, осуществляется без труда.

Рис. 5. Рис. 6.

Пусть АВ = 1; восставим из точки А перпендику­ляр и возьмем точку

Е, для которой (рис. 5). Тогда

Проведя из Е, как из цент­ра, дугу через А до пересече­ния с ЕВ в точке D, мы полу­чаем

Наконец, проведя через D дугу с центром в В, мы находим искомую точку С1. Точку внешнего деления С2 можно найти из условия АС2 =ВС1.

3. Золотое сечение довольно часто используется в оптимизации. Например, для квадрата, вписанного в по­лукруг (см. рис. 6), точка С делит золотым сечением отрезок АВ.

Сторона а10 правильного десятиугольника (рис. 7), вписанного в круг радиуса R, как известно, равна

т. е. 2R sinl8°.

Рис. 7

Вычислим sin 18° На основании известных формул тригонометрии

так что

(7)

Так как из (33) следует, что

и потому sin 18° является одним из корней уравнения

или

Разложив левую часть последнего уравнения на множители, мы получаем

от куда

Так как sin 18° есть положительное число, отличное от имеем

Заметим для дальнейшего, что

Таким образом,

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

Практически при вычислении а10 можно вместо α брать отношение соседних чисел Фибоначчи и считать приближенно, что а10 есть или даже

4. Рассмотрим правильный пятиугольник. Его диа­гонали образуют правильный звездчатый пятиуголь­ник (рис. 8),

Рис. 8

Угол AFD равен 108°, а угол ADF равен 36°. Зна­чит, по теореме синусов

Так как очевидно, что AF = AC, должно быть

и точка С делит отрезок AD золотым сечением.

Но тогда, по определению золотого сечения,

Замечая, что AB = CD, мы получаем

Таким образом, среди отрезков

каждый последующий в α раз больше предыдущего. Пусть читатель попутно проверит, что и

5. Возьмем прямоугольник со сторонами а и b и будем вписывать в него наибольшие возможные квад­раты, как это показано на рис. 9.

Рис. 9.

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

Если разбивать так на квад­раты прямоугольник, стороны которого относятся как соседние числа Фибоначчи (рис. 10), то, как известно, все квадраты, кроме двух самых маленьких, будут раз­личными.

Рис. 10

Так как стороны всех этих квадратов равны соот­ветственно и1, и2, …, ип, их суммарная площадь, оче­видно, равна

Но это есть площадь разбиваемого нами прямоуголь­ника, равная ипип+1.

Таким образом, при любом п

6. Пусть теперь отношение сторон прямоугольника равно α. (Такие прямоугольники мы будем для крат­кости называть прямоугольниками золотого сечения.) Докажем, что, вписав в прямо­угольник золотого сечения наи­больший возможный квадрат (рис. 11), мы снова получим пря­моугольник золотого сечения.

Рис. 11

В самом деле,

по условию AD = AE = EF, так как АEFD — квадрат.

Значит

Но

так что

На рис. 12 показано, как прямоугольник золотого сечения может быть «почти весь» исчерпан квадратами І, ІІ, ІІІ, ...

Рис. 12

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

Заметим, что если в квадрат вписать прямоуголь­ник золотого сечения І и квадраты ІІ и ІІІ, как это показано на рис. 13, то оставшийся прямоугольник тоже окажется прямоугольником золотого сечения.

Рис. 13.

7. По аналогии с прямоугольниками золотого се­чения можно говорить и о треугольниках золотого се­чения: остроугольном — с углами 36°, 72° и 72° и тупо­угольном — с углами 108°, 36° и 36°. На рис. 14 видно, как остроугольный треугольник зо­лотого сечения разбивается на меньшие три треугольника зо­лотого сечения, и обозначены величины углов и отрезков.

Рис. 14.

8. Природа дает нам мно­гочисленные примеры располо­жений однородных предметов, описываемых числами Фибо­наччи.

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