Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




Для того чтобы уменьшить отрезок неопределённости [a,b], нам необходимо вычислить значение целевой функции f(x), по крайней мере, в двух точках на отрезке [a,b].

В результате этих двух экспериментов отрезок неопределённости сузится до отрезка [a,x2] или [x1,b]. Так как у нас нет никаких оснований предпочесть один из этих вариантов, то точки x1 и x2 должны быть симметричны относительно середины отрезка [a,b]. В этом случае длины отрезков [a,x2] и [x1,b] будут равны. Таким образом, остаётся вопрос как выбрать точку x1.

В методе золотого сечения точка x1 выбирается из соображения, что должно выполняться соотношение:

т.е. точка x1 делит отрезок [a,b] по правилу «золотого сечения», где λ - есть «золотое отношение». Точка x2 определяется как точка симметричная к x1 относительно середины отрезка.

В результате экспериментов у нас получается отрезок неопределённости [a,x2], содержащий точку x1, или отрезок неопределённости [x1б], содержащий точку x2. Оказывается, что остающаяся точка на суженном отрезке неопределённости делит его вновь по правилу «золотого сечения». Следовательно, чтобы, в свою очередь, уменьшить новый отрезок неопределённости, нам не достаёт одного эксперимента, а именно, вычисления целевой функции в точке, симметричной к оставшейся точке относительно середины этого нового отрезка. Всё продемонстрировано на рисунке,

а)

б)

где буквы со штрихами обозначают новый отрезок неопределённости. Вариант а) соответствует случаю, если новым отрезком неопределённости будет [a,x2], а вариант б) – отрезку [x1,b].

В приводимой ниже схеме алгоритма остающиеся отрезки неопределённости переименовываются каждый раз как [a,b], а точки, в которых проводятся эксперименты на этом отрезке, обозначается через x1 и x2, причём . Кроме того, y1 и y2 имеют следующие значения: y1 =f(x1) и y2 =f(x2).

 

Схема алгоритма

Шаг1. Задаются a,b,ε и λ=1.618… Вычисляют .

Шаг2. а) Если , то полагают и вычисляют .

б) Если y1>y2, то полагают и вычисляют .

Шаг3. Если b-a>ε, то переходят к шагу 2. Иначе если y1<y2, то полагают и если y1≥y2, то полагают и

Закончить поиск.

После каждой итерации длина отрезка неопределённости уменьшается в λ раз. Так как первая итерация начинается после двух экспериментов, то после N экспериментов длина отрезка неопределённости будет .

Метод чисел Фибоначчи

Этот метод применяется, когда число экспериментов N заранее задано. Метод чисел Фибоначчи, также как и метод золотого сечения относится к симметричным методам, т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка. Вот только выбор точки x1 происходит на основе других соотношений. Для этого используются числа Фибоначчи: , где и F0=F1=1.Точка x1 определяется из соотношения:



т.е. . Точка x1 делит [a,b] на две неравные части. Отношение малого отрезка к большему равно . Точка x2 определяется как точка, симметричная к x1 относительно середины отрезка [a,b]. Поэтому . При этом будет выполняться условие x1<x2.

В результате экспериментов в точках x1 и x2 у нас получится отрезок неопределённости [a,x2], содержащий точку x1, или отрезок неопределённости [x1,b], содержащий точку x2. Остающаяся точка делит новый отрезок неопределённости на две неравные части в отношении:

. То есть в методе Фибоначчи остающаяся точка делит отрезок на две неравные части в пропорциях определяемых числами Фибоначчи. Так на к-ом шаге это отношение равно а длины отрезков равны: и . Всё это показано на рисунке:

а)

б)

Для того чтобы в свою очередь уменьшить получившийся отрезок неопределённости, надо определить симметричную точку относительно середины отрезка и произвести эксперимент в ней. Этот процесс продолжается, пока не будет проведено N экспериментов.

Схема алгоритма

Шаг 1. Задаются a,b,N Вычисляются числа Фибоначчи . Определяется:

Шаг 2. а) Если y1≤y2, то полагают и вычисляют .

б) Если y1>y2, то полагают и вычисляют .

Повторить шаг 2 N-2 раза.

Шаг 3. Если y1<y2, то полагают и . Если y1≥y2, то полагают и .

Закончить поиск.



Длина отрезка неопределённости в методе Фибоначчи .


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал