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




Лабораторная работа №3

Поиск экстремума функции одной переменной

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

Описание метода

Оказывается, что еще лучшие результаты по сравнению с методом локализации могут быть полу­чены, если деление интервала [a, b], в котором находится экстремум, производить не на целое число частей, а в определенном иррациональном отношении.

Допустим, что на концах интервала [а, b],т. е. при х(0)=а и x(3)=b, атакже в двух некоторых внутренних его точках x(1) и х(2) значения функции R(х) известны. Это дает возможность выбрать один из подынтервалов [х(0), х(2)] или [х(1), х(3)], где будет локализовано экстремальное значение R(x).

Предположим, что экстремум локализован в интервале [х(1), х(3)](рисунок 4). Поставим теперь задачу, как выбрать точку х(4) внутри интервала [х(1), х(3)], чтобы точки х(2) и х(4) делили интервал [х(1), х(3)] в таком отношении, в каком точки х(1) и х(2)делят исходный интервал [х(0), х(3)]. Очевидно, что это накладывает опреде­ленные условия и на выбор точек х(1) и х(2) внутри исходного интервала [х(0), х(3)].

Естественно принять, что длины подынтервалов [х(0), х(2)] и [х(1), х(3)]одинаковы, т. е.

x(2)-x(0)=x(3)-x(1) (3,1)

 

и, следовательно, интервалы [х(0), х(2)] и [х(1), х(3)] также равны.

Введем обозначение:

y1=x(1)-x(0)=x(3)-x(2). (3,2)

Тогда для интервала [х(1), х(3)]потребуем также, чтобы его подынтервалы [х(0), х(2)] и [х(4), х(3)] были равны и обозначим:

y2=x(2)-x(1)=x(3)-x(4) . (3,3)

Для того чтобы точки x(2) и x(4) делили интервал [х(1), х(3)] в таком отношении, как точки х(1) и х(2) делят интервал [х(0), х(3)], необходимо выполнение условия:

 

. (3,4)

 

 

 

Рис. 4. Одномерный поиск методом „золотого сечения"

 

Обозначим длину исход­ного интервала [х(0), х(3)] че­рез у, т. е. положим:

у = х{3} - х{0} = b - a (3,5)

Тогда можно записать:

x(3) - x(1)=y - y1 (3,6)

y2=y -2y1 (3,7)

Подставляя выражения (3,5)—(3,6) в условие (3,4), после преобразований получим:

z2 – 3z + 1 = 0 (3,8)

Здесь через z обозначено отношение

(3,9)

которое, естественно, должно быть меньше 1, поэтому решением уравнения (3,8) будет:

(3,10)

Найденное значение отношения z носит название золотого се­чения. Его замечательная особенность заключается в следующем. Если в исходном делении интервала [х(0), х(3)] точки x(1) и x(2) от­стоят на z( х(3) - х(0)) от концов, то в его любом подынтервале [х(0), х(2)] или [х(1), х(3)] можно так выбрать положение следующей точки х(4), которая также отстоит на расстоянии z(х(2)(0))от конца подынтервала, что деление подынтервала будет подобно делению исходного интервала.

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

(3,11)

от длины исходного.

Алгоритм поиска экстремума при этом складывается из сле­дующих этапов:

1. Вычисляются и запоминаются значения функции R(x) на концах исходного интервала [х(0), х(3)],т. е. значения R(x(0)) и R(x(3)).

2. Вычисляется и запоминается значение функции R(x(1)), где

(3,12)

3. Вычисляются и запоминаются значения функции R(x(2)), где

(3,13)

4. По найденным значениям R(x(0)), R(x(1)), R(x(2)) и R(x(3)) определяется, подынтервал, в котором локализован экстремум, со­стоящий из двух подынтервалов l1 и l2 неравной длины.

5. Внутри большего интервала l2 находится точка, отстоящая от конца общего интервала l1 + l2 на расстоянии

(3,14)

В этой точке рассчитывается значение функции R(x), после чего снова выбирается сокращенный подынтервал в интервале l1+l2, локализующий экстремум, т. е. вычисления повторяются, начиная с п. 4 до тех пор, пока не будет получена требуемая точ­ность нахождения положения экстремума.

Для изложения алгоритма нетрудно вывести следующую фор­мулу для оценки точности определения экстремума при заданном числе расчетов значений функции R(x):

(3,15)

где Δ — абсолютная ошибка в определении положения экстремума после s вычислений значении R(x).

Для сравнения с рассмотренным выше алгоритмом поиска де­лением интервала на четыре части при s = 21 из формулы (3,15) находим:

(3,16)

Другими словами, при применении метода «золотого сечения» для того же числа расчетов значений R(x) достигаемая точность в 10 раз выше. Для больших значений s выигрыш в точности бу­дет еще существеннее.

 

3.2 Описание блок-схемы алгоритма поиска экстремума

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

Приразработке блок-схемы алгоритмаприняты следующие обозначения: х(1)=х(0), х(2)=х(1), х(3)=х(2)…, х(4)=х(3). Это связано как и в предыдущей работе с организацией итерационных и циклических процедур. В блок-схеме также рассмотрен пример нахождения экстремума для параболической функции R = ах2 + вх + с, имеющий один экстремум.

Для запуска алгоритма в блоке 1 (см. рисунок 5) предусмотрен ввод следующих переменных: параметров функции – а, в, с; заданные (начальные) концы интервала - х(1) и х(4); заданная точность расчета - ε (которая должна сравниваться с критерием окончания поиска); начальное значение счетчика шагов - n (количество расчетов функции цели – R) и значение индекса k (номера точки интервала, в которой находится минимальное значение функции цели) условно равного единице в начальный момент.

В блоке 2 производится расчет координат точек х(2) и х(3), а в блоках 3 и 4 в цикле (i=1,… 4) рассчитываются значения функций во всех четырех точках исходного интервала. На этом первый этап подготовки исходных данных завершается и управление передается на блоки 5-21 для организации итерационных процедур локализации экстремума функции и сокращения длины диапазона.

В блоке 5 производится расчет двух подынтервалов L1 и L2 неравной длины, здесь же определяется расстояние – L, которое принимается как критерий окончания поиска. Этот критерий в блоке 6 сравнивается с

 

 


Нет

       
 
   
 

 

 


11 k=i Rmin=Ri

 
 

 


19 R(2)=ax2(2)+bx(2)+c

 


Рис. 5. Блок-схема алгоритма метода золотого сечения

заданной точностью ε, если величина критерия будет меньше ε – в блоке 7 производится вывод результатов поиска и алгоритм завершает свою работу. В противном случае управление передается на блоки 8-11, в которых осуществляется поиск минимальной функции – Rmin и соответствующей координаты точки – k.

После завершения цикла в блоке 9 при i=4 управление передается на блоки 12 и 14, где проверяется номер точки минимальной функции цели – k на принадлежность его либо первой точке, либо четвертой точке. Если минимум находится на границах интервала (в первой или четвертой точке), то это говорит о том, что первоначальный интервал выбран неверно, и его необходимо расширить либо влево при k=1, либо – вправо, при k=4.

В блоке 16 производится выбор подынтервала в котором локализован экстремум. Если минимум расположен в точке 2 (k=2), то в блоке 17 производится расчет сокращенного подынтервала, в котором локализован экстремум. При этом координата точки точки х(1) не изменяется, конец нового сокращенного интервала смещается в третью точку, т.е х(4) = х(3), а новая точка х(3) смещается во вторую точку, т.е. х(3)(2). Для нахождения последней четвертой точки с номером 2 к координате первой точки необходимо прибавить значение величины L, которая была рассчитана в блоке 5. Здесь же производятся соответствующие переприсваивания целевой функции. Если же минимум расположен в третьей точке, то управление передается на блок 18, где производятся аналогичные переприсваивания, только для другого – правого сокращенного подынтервала.

Локализация экстремума в правом или левом сокращенном подынтервале с помощью золотого сечения, позволяет производить расчет функции цели только лишь один раз за итерацию либо в блоке 19, либо в блоке 20. Поэтому в отличии от предыдущей работы в блоке 21 счетчик увеличивает свое значение на единицу, а не две единицы как в методе локализации. После чего очередная итерация завершается и управление передается на блок 5, где производятся расчет параметров для нового сокращенного интервала.

 

Задание

1. Возьмите у преподавателя исходные данные: а, в, с, ε, х(1) и х(4).

2. Составьте программу в среде Matlab, реализующую алгоритм метода локализации экстремума (см. рисунок 5).

3. Найдите с помощью программы минимальное значение функции – R(k) и ее координату – x(k), также скорость сходимости алгоритма, т.е. число шагов – n.

4. Дополните программу, реализующую алгоритм рисунка 3, фрагментами, позволяющими вывести кривую R(x) с найденными R(k) и x(k).

5. Измените начальный диапазон (задайте начальные координаты х(1) и х(4)), как в сторону его увеличения, так и в сторону уменьшения. Проанализируйте полученные при этом результаты поиска.

6. Попробуйте сместить начало или конец начального диапазона за точку экстремума – x(k). Проверьте сработают ли при этом блоки 13 и 15.

7. Измените значение величины критерия окончания поиска – ε сначала в два раза больше, а затем в два раза меньше. Повторите расчеты и сравните полученные результаты с результатами пункта3.

8. Сравните полученные в п.п. 3-7 результаты с аналогичными результатами лабораторной работы №2.

9. Подготовьте отчет с анализом полученных результатов.

 

Контрольные вопросы

1. Насколько уменьшается интервал после каждой итерации локализации экстремума целевой функции?

2. В чем состоит замечательная особенность «золотого сечения», позволяющая локализовать экстремум за одно вычисление функции цели в каждой итерации?

3. Что предусмотрено алгоритмом в случае, если экстремум будет расположен за пределами первоначального интервала?

4. Объясните механизм выбора минимальной функции R(k) и соответствующей координаты х(k) в блоках 9-11?

5. Почему в блок-схеме алгоритма не предусмотрен блок сравнения k=3?

6. Чем отличаются операции переприсвоения в блоке 17 от аналогичных операций блока 18?

7. Почему в блоке 21 значение счетчика шагов увеличивается на одну, а не две единицы?

8. Почему в качестве критерия окончания поиска принята величина L?

9. Почему в каждой итерации требуется рассчитывать функцию цели только один раз?

10. В каких блоках алгоритма производится расчет значений новой функции цели?

 

Таблица 4

Диапазон изменения исходных данных для локализации

экстремума функции одной переменной методом золотого сечения

 

a b c x(1) x(4) ε
-10; +10 -10; +10 -10; +10 -10; +10 -10; +10 0,01;0,001

Примечание: Конкретные значения исходных данных каждому студенту дает преподаватель в пределах указанных диапазонов.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: