3 Легко проверить, что х1 = а + b - х2 и х2 = а + b – х1. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (17).

4 В конце вычислений по методу золотого сечения в качестве приближенного значения x* можно взять середину последнего из последних полученных отрезков

На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношениипоэтому в результате п итераций его длина становитсяТаким образом, точность εп определения точки x* после п итераций находится из равенства

(18)

а условием окончания поиска точки x* с точностью ε служит неравенство

Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х1 и х2 по формулам (17). Вычислить f(х1) и f(х2). Положить

Шаг 2. Проверка на окончание поиска: если εп> ε, то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f(х1)≤f(х2), то положить b=x2, x2=x1, f(x2)= f(х1), х1= b–τ(b-а) и вычислить f(х1), иначе - положить а=х1, х1=х2, f(х1)=f(х2), х2=а+τ(b - а) и вычислить f(х2).

Положить εп = τεп и перейти к шагу 2.

Шаг 4. Окончание поиска: положить

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

Решить задачу приведенную ранее

f(x) = х4 +е-х → min,

х [0;l], ε = 0,1.

Итерация 1

Шаг 1. Находим:

х1= 0,382, х2 =0,618, f(x1)=0,704. f(x2)= 0,685, ε п =0,5.

Шаг 2. ε п = 0,5 > ε=0,1, поэтому переходим к шагу 3.

Шаг 3. f(x1)>f(x2), поэтому полагаем а=0,382, х1 =-0,618, f(x1)= 0,685, х2 =0,764, εп=0,309 и вычисляем f(x2)=0.807. Переходим к следующей итераиии, начиная с шага 2.

НЕ нашли? Не то? Что вы ищете?

Результаты вычислений на остальных итерациях представлены в табл. 2.

Таблица 2

Таким образом,

Замечание. Число итераций, необходимое для достижения заданной точности ε, можно найти из условия εп≤ε с учетом соотношения (18)

Так как N вычислений f(x) позволяют выполнить N-1 итераций

метода золотого сечения, то достигнутая в результате этих вычислений точность определения х * составляет

(19)

При решении задач оптимизации однопараметрических функций не всегда можно заранее определить, сколько раз придется вычислять функцию. Метод "золотого сечения" достаточно эффективен, так как при этом не требуется знать n - количество вычислений функции, определяемое вначале. После того как выполнено j вычислений, исходя из тех же соображений, что и ранее, записываем

L_{j-1} = L_j + L_{j+1} (20)

Однако если n не известно, то мы не можем использовать условие Ln-1=Ln-е. Если отношение последующих интервалов будет постоянным, т. е.

\frac{L_{j-1}}{L_j} = \frac{L_j}{L_{j+1}} = \frac{L_{j+1}}{L_{j+2}} = \ldots = \tau , (21)

то

\frac{L_{j-1}}{L_j}

т. е.

\tau = 1+ 1/ \tau

Таким образом,

\tau^2 - \tau - 1 = 0,

откуда

\tau = (1 + \sqrt{5})/2 \approx 1,618033989.

Тогда

\frac{L_{j-1}}{L_{j+1}}

Следовательно,

\frac{L_1}{L_n} = \tau^{n-1},

т. е.

L_n = \frac{L_1}{\tau^{n-1}} (22)

В результате анализа двух рассмотренных значений функции будет определен тот интервал, который должен исследоваться в дальнейшем. Этот интервал будет содержать одну из предыдущих точек и следующую точку, помещаемую симметрично ей. Первая точка находится на расстоянии L1/t от одного конца интервала, вторая - на таком же расстоянии от другого. Поскольку

\lim_{n

то видно, что поиск методом "золотого сечения" является предельной формой поиска методом Фибоначчи.

Таким образом, если ищется интервал (х0, х3) и имеются два значения функции f1 и f2 в точках x1 и x2, то следует рассмотреть два случая (рис. 23).


Рис. 23.

Метод гарантирует нахождение минимума в самых неблагоприятных условиях, однако он обладает медленной сходимостью.

Схема алгоритма метода "золотого сечения" представлена на рис. 24

Схема алгоритма метода "золотого сечения".


Рис. 24.  Схема алгоритма метода "золотого сечения".

Здесь c- константа,

c= \begin{cases} \phantom{-} 1 & (\text{поиск минимума функции} \; F(x)), \\ -1 & (\text{поиск максимума функции} \; F(x)), \end{cases}

При выводе x - координата точки, в которой функция F(x) имеет минимум (или максимум), FM – значение функции F(x) в этой точке.

Второй метод деления отрезка пополам. Этот метод, использующий на каждой итерации три пробные точки, обеспечивает последовательное уменьшение длины отрезка, содержащего х*, ровно вдвое.

Рассмотрим способ исключения отрезков, применяемый в рассматриваемом методе.

Разделим отрезок [a;b] на четыре равные части пробными точками

Сравним значения f(x1) и f(x2). Если f(x1) < f(x2), то уменьшенный вдвое отрезок поиска точки х* найден - это [а;х2]. Если же f(x1)> f(x2), то произведем еще одно сравнение значений f(x) при f(x2)< f(x3) перейдем к отрезку [x2:b].

Отметим, что каким бы ни оказался новый отрезок, одна из уже использованных пробных точек переходит на его середину, становясь новой точкой х2. Таким образом, для проведения следующей итерации на вновь полученном отрезке потребуется вычисление не более двух новых значений f(x) (либо только в точке х1, либо еще и в точке x3).

Перечислим основные шаги алгоритма второго метода деления отрезка пополам.

Шаг 1. ПоложитьВычислить значение f(x2) и перейти к шагу 2.

Шаг 2. Положить Вычислить значение f(x1) и перейти к шагу 3.

Шаг 3. Сравнить f(x1) и f(x2). Еслито продолжить поиск на отрезке [a;х2], положив

и перейти к шагу 5, иначе — положитьвычислить значение f(x3) и перейти к шагу 4.

Шаг 4. Сравнить f(x2) и f (х3). Если то перейти к отрезку [х1;х2] , положив а= х1, b = х3, иначе - продолжить поиск на отрезке [х2;b], положив Перейти к шагу 5.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97