КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Золотое сечение
Метод золотого сечения используется при поиске минимума функции одной вещественной переменной. Данный метод применим, в том числе и к недифференцируемым функциям. Пусть на отрезке [ a, b ] задана кусочно-непрерывная функция F (x) и она имеет, включая концы отрезка [ a, b ], один-единственный локальный минимум. Построим итерационный процесс, сходящийся к искомому значению локального минимума.
Рис.1. Иллюстрация к первому шагу итерационного
Выберем внутри отрезка [ a, b ] две точки x 1 и x 2. Сравним значения функции F друг с другом в четырех точка: F (a), F (x 1), F (x 2), F (b). Пусть, например, значение функции в точке x 1 минимально, т.е. минимум находится на одном из отрезком, примыкающих к точке x 1, тогда третий отрезок, не примыкающий к x 1 может быть отброшен. Таким отрезком является отрезок [ x 2, b ]. На рис.1 приведена схема первого шага итерационного процесса в методе золотого сечения. Жирной линией выделена пара отрезков, на которых находится искомый минимум, крестом обозначен отрезок, подлежащий отбрасыванию. На втором шаге итерационного процесса предыдущая процедура повторяется, но уже на отрезке [ a, x 2]. Опять выбирается пара точек x 1, x 3 на отрезке [ a, x 2], причем одна из них уже есть — это точка x 1. Вычисляются значения функции в этих точках, среди четырех значений F (a), F (x 1), F (x 3), F (x 2) находится минимум, отбрасывается отрезок, не примыкающий к точке с минимальным значением функции. Легко понять, что отбрасывается всегда один из двух крайних отрезков. Этот процесс можно продолжать неограниченно. Определимся с выбором точек на соответствующих отрезках. При выборе точек будем следовать правилу золотого сечения. Пусть на отрезке [ a, b ] выбрана некоторая точка x *, эта точка делит [ a, b ] на два отрезка: [ a, x *] и [ x *, b ]. Возможны два варианта: первый отрезок меньше второго и второй меньше первого. Для первого варианта (аналогично для второго ) воспользуемся правилом золотого сечения: отношение длины большего отрезка ко всему отрезку [ a, b ] равно отношению длины меньшего отрезка к длине большего . Соответствующая пропорция для первого варианта имеет следующий вид: . (4) Из двух уравнений (4) можно найти уравнение для коэффициента x: . (5)
Рис.2. Два варианта золотого сечения отрезка
При решении квадратного уравнения в (5) выбран положительный корень уравнения. Для второго варианта расположения точки на отрезке [ a, b ] получится аналогичное уравнение для коэффициента x. На рис.2 приведены оба варианта позиционирования точек и на отрезке [ a, b ] и соответствующие доли исходного отрезка, на которые делят точки исходный отрезок. Каждая из двух позиций точек и есть позиция золотого сечения отрезка. Из построения, а также согласно схеме рис.2, для точек и верно соотношение: или . (6) Согласно (6), зная одну из точек и , находим другую. В соответствие со схемой рис.2 будем выбирать пару точек на отрезке, т.е. точки x 1 и x 2 на первом шаге итерационного процесса являются точками золотого сечения отрезка [ a, b ]. На втором шаге итерационного процесса точка x 1 уже делит отрезок [a, x 2] согласно второму варианту золотого сечения. Осталось найти позицию золотого сечения первого варианта для точки x 3. Этот процесс можно продолжать неограниченно. После проведения очередного этапа итерационного процесса отрезок сокращается, т.к. отбрасывается меньшая часть (0,382я доля). Отрезок уменьшается в раза. После n шагов итерационного процесса длина отрезка составит x n долю длины первоначального отрезка. Таким образом, процесс при n ® ¥ сходится, т.к. длина отрезка уменьшается со скоростью геометрической прогрессии с показателем x» 0,618, т.е. метод золотого сечения всегда сходиться, причем линейно. Пусть на некотором шаге итерационного процесса анализируются четыре точки , из них две точки являются концами соответствующего отрезка. Найдем значения функции в этих точках и выберем среди них минимум. Пусть минимум реализуется в точке xi, т.е. . (7) Отбросим ту точку, которая максимально удалена от точки xi. Пусть такой точкой является точка xl, т.е. . (8) Определим позиционирование друг относительно друга оставшихся точек. Пусть, например, верно следующее неравенство . (9) Согласно (6), можно определить вторую, после точки xi, точку xp золотого сечения отрезка [ xk, xj ] по формуле: . (10) Этапы алгоритма золотого сечения (7) — (10) полностью описывают произвольный шаг итерационного процесса. Искомый минимум находится, где-то на отрезке [ xk, xj ], поэтому итерации могут быть прекращены по достижении заданной точности e, т.е. . Метод золотого сечения является аналогом метода деления отрезка пополам, но применительно к задаче отыскания минимума. Метод прост и экономичен и всегда сходится. Если на исходном отрезке несколько локальных минимумов, то процесс сойдется к одному из локальных минимумов не обязательно наименьшему. На листинге_№1 приведен код программы поиска минимума функции методом золотого сечения. Для примера выбрана несколько экзотическая, кусочно-дифференцируемая функция, имеющая на заданном отрезке три локальных минимума. За счет незначительного изменения положения левой границы исходного отрезка удается последовательно получить методом золотого сечения все три локальных минимума функции.
Листинг_№1 %Программа поиска минимума функции методом %золотого сечения %очищаем рабочее пространство clear all %определяем размеры исходного отрезка [a,b] a=0.95; b=3.5; %определяем функцию, минимум которой на %отрезке [a,b] находится f=@(x)x^2*sign(x-1)*sign(x-1.5)*... sign(x-2)*sign(x-2.5)*sign(x-3); %определяем точность нахождения точки минимума eps=1e-10; %определяем константу ksi ksi=(sqrt(5)-1)/2; %определяем левую и правую границы отрезка xl=a; xr=b; %определяем номер итерации k=0; %организуем цикл метода поиска точки минимума %методом золотого сечения while xr-xl>eps %определяем пару средних точек xl2 и xr2 %на отрезке [xl,xr] точек xl2=xr-ksi*(xr-xl); xr2=xl+ksi*(xr-xl); %находим значения минимизируемой функции %в четырех точках Fl=f(xl); Fl2=f(xl2); Fr2=f(xr2); Fr=f(xr); %перебор четырех вариантов минимума из %четырех значений функции Fl, Fl2, Fr2, Fr %минимально Fl if (Fl<=Fl2)&(Fl<=Fr2)&(Fl<=Fr) %отбрасывается точка xr xl=xl; xr=xr2; if xl2-xl>=xr-xl2 xr2=xl2; xl2=xl+xr-xr2; else xl2=xl2; xr2=xl+xr-xl2; end end %минимально Fl2 if (Fl2<=Fr)&(Fl2<=Fr2)&(Fl2<=Fr) %отбрасывается точка xr xl=xl; xr=xr2; if xl2-xr>xr-xl2 xr2=xl2; xl2=xl+xr-xr2; else xl2=xl2; xr2=xl+xr-xl2; end; end %минимально Fr2 if (Fr2<=Fr)&(Fr2<=Fl2)&(Fr2<=Fr) %отбрасываем точку xl xl=xl2; xr=xr; if xr2-xl2>=xr-xr2 xr2=xr2; xl2=xl+xr-xr2; else xl2=xr2; xr2=xl+xr-xl2; end end %минимально Fr if (Fr<=Fl)&(Fr<=Fl2)&(Fr<=Fr2) %отбрасываем точку xr xl=xl; xr=xr2; if xl2-xl>=xr-xl2 xr2=xl2; xl2=xl+xr-xr2; else xl2=xl2; xr2=xl+xr-xl2; end end k=k+1; %запоминаем полусумму крайних точек отрезка root(k)=0.5*(xr+xl); end %рисуем график зависимости значения точки %минимума от номера итерации plot(1:k,root);
На рис.3,а приведен график минимизируемой функции. Согласно графику функция имеет три локальных минимума x min = 1, 2, 3. Метод золотого сечения обязательно сходится к одному из локальных минимумов. Графики на рис.3,б, 3,в и 3,г показывает сходимость к локальным минимумам в точках x min = 1, 2, 3 при численных значениях левой границы исходного отрезка, равных a = 0,25; 0,5; 0,95 соответственно. Таким образом в методе золотого сечения, вычисление разных локальных минимумов (если они есть) возможно благодаря вариации одной или обеих границ исходного отрезка минимизации исследуемой функции.
Дата добавления: 2014-01-03; Просмотров: 549; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |