Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

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

В ряде случаев требование априорного выбора числа n создает определенные неудобства. Например, в случае, когда не лимитировано количество вычислений значений функции φ(x), а критерием окончания процедуры вместо гарантированной точности определения величины х* (то есть длины отрезка [аn, bn]) является некоторой другой, скажем, точность определения величины φ(x*). Возникает проблема построения метода, не требующего определения вначале числа я, как это необходимо в методе Фибоначчи, и вместе с тем такого, точность которого (в смысле длины отрезка [аn, bn]) была бы не намного хуже точности метода Фибоначчи. Таким методом является так называемый метод золотого сечения, обладающий еще одним достоинством: его вычислительная схема укладывается в схему метода Фибоначчи. При этом первый этап - определение числа n и величины Fn/Fn+2 здесь отсутствует.

Пусть ck = const, k = 0, 1, ... Тогда из (8.9) следует


откуда


И так как 0≤c≤1/2, то

(8.21)

Схема метода очевидным образом упрощается по сравнению с предыдущей.

Поясним название метода. Как известно, точка yk осуществляет золотое сечение отрезка [ak-1, bk-1], если


Справедливость этого соотношения очевидна из (8.7) и условия


Наконец, сравним точность методов Фибоначчи и золотого сечения.

Из (8.13) и (8.21) получаем


Из формулы Бине*


* (Элементарное доказательство можно найти в [3]. )

следует, что для больших n


Тогда


Таким образом, длина отрезка [an, bn]з.с построенного методом золотого сечения, на 17% больше длины отрезка [аn, bn]фиб., построенного по методу Фибоначчи.

Заметим, что для достаточно больших n будет


то есть и метод Фибоначчи, и метод золотого сечения при больших п начинаются практически в одной и той же точке с0.

Заметим, что уже


поэтому иногда можно комбинировать оба метода: первые шаги делать по методу золотого сечения, а затем, когда оптимум достаточно близок, зафиксировать число n и переходить к методу Фибоначчи.

предыдущая главасодержаниеследующая глава






Выпущен открытый сервер навыков 0Mind для упрощения разработки ИИ

Создатель Всемирной паутины выступил против Facebook и Google

В Китае построят суперкомпьютер, способный выполнять квинтиллион вычислений в секунду

Использование нейронной сети для восстановления повреждённых изображений

В Китае робот сдал тест для поступления в университет

Россия будет защищена от внешнего отключения Рунета к 2021 году

О конференции Strata AI: будущее искусственного интеллекта

Китайский самообучающийся процессор сможет имитировать работу нервных клеток человека

Илон Маск работает над интерфейсом для подключения мозга к компьютеру

Загадка QWERTY: почему буквы на клавиатуре расположены не в алфавитном порядке

Нейронную сеть научили практически идеально копировать человеческий голос





© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"