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


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

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 и переходить к методу Фибоначчи.

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





Пользовательский поиск


Диски от INNOBI.RU




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