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

а с другой стороны, из (12) следует, что

так что

В силу единственности фибоначчиева представления вместе с (14) это дает

Кроме того, как уже указывалось, φ2 = 1. Следовательно, а, а потому и b, обязаны иметь вид из формулы (11).

Это значит, что соблюдается условие 4).

Наконец, ясно, что в условиях выполненного по­строения с ростом разности координат позиции долж­ны возрастать и сами координаты. Это значит, что выполняется 5).

Таким образом, построенная система пар чисел является решением игры Г, содержащим (0,0). Ввиду доказанной единственности такого решения она долж­на совпадать с результатом построения из п. 16.

Фибоначчиевы представления чисел позволяют для каждого натурального числа непосредственно указы­вать «парное» ему. Найдем, например, «пару» к числу 31. Для этого числа мы имеем Ф(31)=1010010. Полученное представление оканчивается одним нулем. Значит, представление, парное к нему, получается в результате отбрасывания последнего нуля, т. е. будет 101001; оно является фибоначчиевым представлением числа 13 + 5+ 1 = 19.

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

Предварительно докажем вспомогательную лемму.

Лемма. Пусть γ и δ — положительные иррацио­нальные числа, для которых

(15)

Тогда среди чисел

(16)

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

Доказательство. Заметим прежде всего, что γ, δ > 1. Возьмем далее произвольное натуральное N и рассмотрим все натуральные значения п, для которых [пγ]< N, т. е. пγ < N, или п так что этому

неравенству удовлетворяют все натуральные числа

Аналогично для всех

будет [пδ] < N. Значит, среди чисел 1, 2, ..., N будет всего

чисел вида 16). Но числа

неявляются целыми. Значит,

Поэтому, складывая эти неравенства и учитывая (15), мы получаем

Значит, средняя часть написанного соотношения есть целое число, лежащее строго между N — 2 и N. Таким числом является N— 1:

Таким образом, для любого натурального N среди чисел, меньших N, будет ровно N—1 чисел вида (16): ими будут все натуральные числа, меньше N. Нам остается сослаться на произвольность числа N.

19. Пары чисел ([пγ], ([пγ]) удовлетворяют усло­виям 1)—3) теоремы п. 15. Чтобы они удовлетворяли также условиям 4) и 5) этой теоремы, нужно, чтобы при любом натуральном п было

Но так как

это равносильно тому, чтобы при любом п было

Но, как легко проверить, последнее возможно лишь при δ=1+γ. т. е. ввиду (15) — при

oткуда

или

так что ввиду положительности γ —

и

Таким образом, координаты выигрывающих по­зиций в игре Г поддаются непосредственному вычи­слению как пары

20. Закончим наше изложение небольшой геомет­рической шуткой. Сейчас мы наглядно «докажем», что 64=65. Возьмем для этого квадрат со стороной 8 и разрежем его на четыре части, как это показано на рис. 18. Эти части мы сложим в прямоугольник (рис. 19) со сторонами 13 и 5, т. е. с площадью, рав­ной 65.

Рис. 18. Рис19.

Объяснение этому, на первый взгляд загадочному, явлению найти нетрудно. Все дело в том, что точки А, В, С и D на рис. 19 на самом деле не лежат на одной прямой, а являются вершинами параллело­грамма, площадь которого как раз и равна «лишней» единице.

Это правдоподобное, но неверное «доказательство» заведомо ложного высказывания (такие «доказатель­ства» называются софизмами), можно проделать еще более наглядно и «убедительно», если вместо квад­рата со стороной 8 взять квадрат со стороной, равной некоторому числу Фибоначчи с достаточно большим четным номером, и2п. Разобьем этот квадрат на части (рис. 20) и сложим из этих частей прямоугольник (рис. 21). «Пустота» в виде параллелограмма, вытянутого вдоль диагонали прямоугольника имеет площадь, равную единице.

Рис. 20. Рис. 21.

Наи­большая ширина этой щели, т. е. высота параллело­грамма, равна, как легко вычислить,

Поэтому если мы возьмем квадрат со стороной 21 см и «превратим» его в прямоугольник со сторо­нами 34 и 13 см, то наибольшая ширина щели полу­чится

т. е. около 0,4 мм, что почти незаметно для глаза.

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

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

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

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

Рис. 22. К определению пробных точек в методе золотого сечения

Пробная точка х1, отрезка [0; l] перейдет в пробную точку х'2 =1 - τ нового отрезка [0; г]. Чтобы точки делили отрезки и в одном и том же соотношении, должно выполнятся равенствоили τ2=1— τ, откуда находим положительное значение

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

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

(17)

Замечания:

1 Точки х1 и х2 из (40) обладают следующим свойством: каждая из

них делит отрезок [а; b ] на две части так, что отношение длинны всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а ; b ]. Это и объясняет название рассматриваемого метода.

2 На каждой итерации исключения отрезков с пробными точками (17) одна из них переходит на следующий отрезок и значение f(х) в этой точке вычислять не следует. Если новым отрезком становится [а; х2 ], то на него переходит пробная точка = х] исходного отрезка, становясь его второй пробной точкой (х'2 = х1) (рис. 22). В случае перехода к отрезку [х1;b] пробная точка = х2 исходного отрезка становится первой пробной точкой отрезка [х1;b].