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

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

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

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

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

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

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

Предположим, что экстремум локализован в интервале [х⁽¹⁾, х⁽³⁾](рисунок 4). Поставим теперь задачу, как выбрать точку х⁽⁴⁾ внутри интервала [х⁽¹⁾, х⁽³⁾], чтобы точки х⁽²⁾ и х⁽⁴⁾ делили интервал [х⁽¹⁾, х⁽³⁾] в таком отношении, в каком точки х⁽¹⁾ и х⁽²⁾делят исходный интервал [х⁽⁰⁾, х⁽³⁾]. Очевидно, что это накладывает опреде­ленные условия и на выбор точек х⁽¹⁾ и х⁽²⁾ внутри исходного интервала [х⁽⁰⁾, х⁽³⁾].

Естественно принять, что длины подынтервалов [х⁽⁰⁾, х⁽²⁾] и [х⁽¹⁾, х⁽³⁾]одинаковы, т. е.

x⁽²⁾-x⁽⁰⁾=x⁽³⁾-x⁽¹⁾ (3,1)

 

и, следовательно, интервалы [х⁽⁰⁾, х⁽²⁾] и [х⁽¹⁾, х⁽³⁾] также равны.

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

y₁=x⁽¹⁾-x⁽⁰⁾=x⁽³⁾-x⁽²⁾. (3,2)

Тогда для интервала [х⁽¹⁾, х⁽³⁾]потребуем также, чтобы его подынтервалы [х⁽⁰⁾, х⁽²⁾] и [х⁽⁴⁾, х⁽³⁾] были равны и обозначим:

y²=x⁽²⁾-x⁽¹⁾=x⁽³⁾-x⁽⁴⁾ . (3,3)

Для того чтобы точки x⁽²⁾ и x⁽⁴⁾ делили интервал [х⁽¹⁾, х⁽³⁾] в таком отношении, как точки х⁽¹⁾ и х⁽²⁾ делят интервал [х⁽⁰⁾, х⁽³⁾], необходимо выполнение условия:

 

. (3,4)

 

 

 

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

 

Обозначим длину исход­ного интервала [х⁽⁰⁾, х⁽³⁾] че­рез у, т. е. положим:

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

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

x⁽³⁾ - x⁽¹⁾=y - y₁ (3,6)

y₂=y -2y₁ (3,7)

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

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

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

(3,9)

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

(3,10)

Найденное значение отношения z носит название золотого се­чения. Его замечательная особенность заключается в следующем. Если в исходном делении интервала [х⁽⁰⁾, х⁽³⁾] точки x⁽¹⁾ и x⁽²⁾ от­стоят на z( х⁽³⁾ - х⁽⁰⁾) от концов, то в его любом подынтервале [х⁽⁰⁾, х⁽²⁾] или [х⁽¹⁾, х⁽³⁾] можно так выбрать положение следующей точки х⁽⁴⁾, которая также отстоит на расстоянии z(х⁽²⁾-х⁽⁰⁾)от конца подынтервала, что деление подынтервала будет подобно делению исходного интервала.

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

(3,11)

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

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

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

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

(3,12)

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

(3,13)

4. По найденным значениям R(x⁽⁰⁾), R(x⁽¹⁾), R(x⁽²⁾) и R(x⁽³⁾) определяется, подынтервал, в котором локализован экстремум, со­стоящий из двух подынтервалов l₁ и l₂ неравной длины.

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

(3,14)

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

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

(3,15)

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

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

(3,16)

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

 

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

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

Приразработке блок-схемы алгоритмаприняты следующие обозначения: х₍₁₎=х(⁰), х₍₂₎=х(¹), х₍₃₎=х(²⁾…, х₍₄₎=х(³). Это связано как и в предыдущей работе с организацией итерационных и циклических процедур. В блок-схеме также рассмотрен пример нахождения экстремума для параболической функции R = ах² + вх + с, имеющий один экстремум.

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

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

В блоке 5 производится расчет двух подынтервалов L₁ и L₂ неравной длины, здесь же определяется расстояние – 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 производится расчет сокращенного подынтервала, в котором локализован экстремум. При этом координата точки точки х₍₁₎ не изменяется, конец нового сокращенного интервала смещается в третью точку, т.е х₍₄₎ = х₍₃₎, а новая точка х₍₃₎ смещается во вторую точку, т.е. х₍₃₎=х₍₂₎. Для нахождения последней четвертой точки с номером 2 к координате первой точки необходимо прибавить значение величины L, которая была рассчитана в блоке 5. Здесь же производятся соответствующие переприсваивания целевой функции. Если же минимум расположен в третьей точке, то управление передается на блок 18, где производятся аналогичные переприсваивания, только для другого – правого сокращенного подынтервала.

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

 

Задание

1. Возьмите у преподавателя исходные данные: а, в, с, ε, х₍₁₎ и х₍₄₎.

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

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

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

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

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

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