Существенным недостатком, ограничивающим применение метода Фибоначчи, является то, что стратегия поиска зависит от заранее заданного числа экспериментов. Поэтому на практике часто используется более простой метод золотого сечения. Заметим, что иногда комбинируют эти два метода: первые шаги делают по методу золотого сечения, а когда экстремум достаточно близок, вычисляют число n, исходя из требуемой точности поиска, и переходят к методу Фибоначчи.
Основная идея метода золотого сечения состоит в следующем [2,9]. Пусть имеем исходный отрезок единичной длины. Пробные точки будем располагать симметрично относительно концов отрезка. Воспользуемся соотношением (19):
но не будем принимать во внимание соотношение (15), т.к. оно зависит от n. Вместо этого пусть будет постоянным отношение длин последовательных отрезков [1,2]:
Пусть пробные точки y1 и z1 отстоят от концов единичного отрезка на расстоянии t (величина t пусть будет больше половины единичного отрезка). При симметричной стратегии расположение точек, длина отрезка, остающегося после исключения, будет равна t независимо от того, какое значение функции в пробных точках окажется меньшим (см. рисунок 2.4). Длина отбрасываемого отрезка при этом равна (1-t). Тогда для отрезка единичной длины соотношение (27) записывается в виде
Рис. 2.4. Расположение точек при поиске минимума функции методом «Золотого сечения».
Из последнего соотношения получаем уравнение t2 = 1-t. Решение последнего уравнения позволяет получить значение 
Для исходного отрезка [a0, b0] получаем формулы, определяющие положение двух пробных точек
Так как точка y1 делит отрезок [a0, b0] на две части так, что отношение длины всего отрезка к большей части равно отношению большей части к меньшей, то такое деление называется золотым сечением. После проведения n испытаний получаем интервал неопределенности, равный
Метод золотого сечения обладает несколько меньшей скоростью сходимости, чем метод Фибоначчи. Однако при большом n длины интервалов поиска, полученные с помощью обоих методов, практически не различаются. Метод золотого сечения требует сравнительно небольшого объема памяти ЭВМ и прост в реализации.
Алгоритм поиска экстремума функции f(x) на интервале [a0; b0] с использованием метода золотого сечения состоит из следующих шагов [3]:
1 Задать a0, b0 – границы интервала поиска экстремума функции f(x);
t = 0.618 - константа.
2 Вычислить
и значение f(y1), f(z1).
3 Если f(y1) £ f(z1), то положить a1 = a, b1 = z1 и перейти к п. 4; иначе положить a1 = y1, b1 = b0 и перейти к п. 4.
4 Положить k = 1.
5 Если f(yk) £ f(zk), то вычислить yk+1 = ak+bk-yk, f(yk+1) и перейти к п. 6; иначе положить yk+1 = zk, f(yk+1) = f(zk) и перейти к п. 7.
6 Положить zk+1 = yk, f(zk+1) = f(yk) и перейти к п. 8.
7 Вычислить zk+1 = ak+bk-zk, f(zk+1) и перейти к п. 8.
8 Если f(yk+1) £ f(zk+1), то положить ak+1 = ak, bk+1 = zk+1 и перейти к п. 9; иначе положить ak+1 = yk+1, bk+1 = bk и перейти к п. 9.
9 Вычислить xk = (ak+1 + bk+1) / 2.
10 Если k = 1, то перейти к п. 5; иначе перейти к п. 11.
11 Если | xk-1 – xk | £ e, то закончить поиск, иначе положить k = k+1 и перейти к п. 5.
Пример 5. Найти минимум функции 
Решение: В таблице 2 приведены первые 5 итераций данного метода.
Таблица 2.
| a | b | y | z | f(y) | f(z) | xk | k | |
| 0 | 2 | 0 | ||||||
| Итерация 1 | 0,76394 | 2 | 0,76394 | 1,23606 | 0,125432 | -0,06157 | 1 | |
| Итерация 2 | 1,23606 | 2 | 1,23606 | 1,52788 | -0,06157 | -0,09198 | 1,61803 | 1 |
| Итерация 3 | 1,52788 | 2 | 1,52788 | 1,70818 | -0,09198 | -0,09702 | 1,76394 | 2 |
| Итерация 4 | 1,70818 | 2 | 1,70818 | 1,8197 | -0,09702 | -0,09703 | 1,85409 | 3 |
| Итерация 5 | 1,70818 | 1,88848 | 1,18197 | 1,88848 | -0,09703 | -0,09619 | 1,79833 | 4 |
Дальнейшие расчеты ведутся аналогично по алгоритму. Решение с заданной точностью найдено на 22 итерации при 
0 коммент.:
Отправить комментарий