|
Методы одномерной минимизацииМетод Свенна - 1
Метод Свенна организует начальную локализацию минимума унимодальной функции, т.е. простой одномерный поиск с удвоением шага, критерием окончания которого является появление признака возрастания функции. Начальный этап. (1) задать произвольную начальную точку x0ÎRn (2) выбрать начальный шаг h=Dx=0,01 Основной этап Шаг 1. Установить направление убывания функции. Для этого взять x2=x1+h. Если f(x1) <f(x2), то поменять направление движения: h1=-h1 и взять x2=x1+h1. Шаг 2. Вычислить fk в точках xk+1=xk+hk, где k=2,3,4,…,m-1; hk=2hk-1 – движение с удвоением шага, до тех пор, пока не придём в точку xm такую, что f(xm)<f(xm-1). Шаг 3. Установить начальный интервал локализации минимума a1=xm-2 b1=xm
double swanna(double &h,double &x1,double &x2) { x2=x1+h; if (f(x2)>f(x1)) { h=-h; x2=x1+h; } while(f(x2)<f(x1)) { x1=x2; x2=x1+h; h=h*2; } return (x2); } Метод Свенна - 2
if (x1!=0) h=0.01*x1; else h=0.01;
if (proiz_f(x1)>0) h=-h; x2=x1+h; while (proiz_f(x2)*proiz_f(x1)>0) { x1=x2; x2+=h; h=2*h; } a=x1; b=x2; if (b<a) { x2=a; a=b; b=x2; } Метод Свенна - 3
Метод золотого сечения
Метод золотого сечения – это процедура одномерного поиска минимума на интервале [a1,b1] или [0,1]. На каждом шаге пробная точка lk или mk внутри текущего интервала локализации [ak,bk] делит его в отношении, постоянном для всех интервалов - золотое сечение. Можно показать, что , откуда , следовательно , значит . Одним из корней этого уравнения является t1=0,618 – первое золотое число. Отметим, что t12=0,6182=0,382 – второе золотое число. Следует отметить, что в методе золотого сечения имеет место правило симметрии (эквидистантности) точек относительно концов интервала, а также правило одного вычисления, т.е. на каждой итерации требуется одно и только одно новое вычисление (кроме первой итерации), т.к. точки на соседних итерациях совпадают.
Алгоритм ЗС-1 Начальный этап (1) Выбрать погрешность расчёта e=10-3¸10-7. Получить начальный интервал методом Свенна. (2) Вычислить стартовые точки l1=a1+0,382L1, m1=a1+0,618L1 (следует отметить, что золотые числа следует вычислять точно) (3) Принять k=1 – счётчик числа итераций Основной этап Шаг 1.Сократить ТИЛ рассмотрением 2-х ситуаций: (1) Если f(l)<f(m),то ak+1=ak bk+1=mk mk+1=lk lk=ak+1+0,382Lk+1 иначе ak+1=lk bk+1=bk lk+1=mk mk=ak+1+0,618Lk+1 (2) Положить k=k+1, Lk+1=|bk+1-ak+1| Шаг 2. Проверить критерий окончания поиска: если |ak+1-bk+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.
double GSS(double a, double b) // golden section search - 1 { double tau1, tau2, lyambda, sigma, eps = 0.001; tau1 = (sqrt(5.0) - 1) / 2; // золотые числа tau2 = pow(tau1,2); lyambda = a + tau2 * abs(b - a); // начальные точки sigma = a + tau1 * abs(b - a); while (abs(b - a) > eps) // пока не достигнется нужная точность { if (f(lyambda) < f(sigma)) // определение направления сокращения { b = sigma; // сокращение интервала sigma = lyambda; lyambda = a + tau2 * abs(b - a); } else { a = lyambda; lyambda = sigma; sigma = a + tau1 * abs(b - a); } } return (lyambda + sigma) / 2; // середина интервала - аппроксимирующий минимум } Алгоритм ЗС-2 Начальный этап (4) Выбрать погрешность расчёта e=10-3¸10-7. Получить начальный интервал методом Свенна. (5) Вычислить стартовые точки l1=a1+0,382L1, m1=a1+0,618L1 (следует отметить, что золотые числа следует вычислять точно) (6) Принять k=1 – счётчик числа итераций Основной этап Шаг 1. Взять очередную пробную точку x2=ak+bk-x1, симметричную исходной и сократить ТИЛ рассмотрением 4-х возможных ситуаций: (1) Если (x1<x2) и (f(x1)<f(x2)) то b=x2; (2) Если (x1<x2) и (f(x1)>=f(x2)) то a=x1; (3) Если (x1>x2) и (f(x1)<f(x2)) a=x2; (4) Если (x1>x2) и (f(x1)>=f(x2)) b=x1; Увеличить счётчик числа итераций k=k+1 Шаг 2. Проверить критерий окончания поиска: если |ak+1-bk+1|£e - остановиться – минимум найден. Точнее фиксируем аппроксимирующий минимум как . Иначе вернуться на шаг 1.
double zoloto2(double a,double b) { double tau1,tau2,eps=0.0001,x1,x2; tau1 = (sqrt(5.0) - 1) / 2; // золотые числа tau2 = pow(tau1,2); x1=a+tau1*(abs(b-a)); x2=a+b-x1;
while (abs(b-a)>eps) { if ((x1<x2) && (f(x1)<f(x2))) b=x2; if ((x1<x2) && (f(x1)>=f(x2))) { a=x1; x1=x2; } if ((x1>x2) && (f(x1)<f(x2))) a=x2; if ((x1>x2) && (f(x1)>=f(x2))) { b=x1; x1=x2; } x2=a+b-x1; } return (x1); }
Метод Фибоначчи
Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом интервале [a, b], отличающейся от процедуры золотого сечения тем, что очередная пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F0 = F1 = 1, Fk+1 = Fk + Fk-1, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и e - константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.
int Fib(int n) // n-ое число Фибоначчи { if (n > 1) return Fib(n-1)+Fib(n-2); else return 1; } Алгоритм Фибоначчи-1
Начальный этап (1) Задать константу e, начальный интервал [a1, b1], длину конечного интервала Ln и определить число n так, чтобы выполнялось условие Fn > (b1 - a1)/Ln. (2) Взять две пробные точки l1 = a1 + (Fn-2/Fn)(b1 - a1) и m1 = a1 + (Fn-1/Fn)(b1-a1). Положить k = 1. Основной этап Шаг 1. Сократить текущий интервал локализации: (1) Если f(lk) < f(mk), то положить ak+1 = ak, bk+1 = mk,mk+1 =lk и вычислить новую точку lk+1 = ak+1 + (Fn-k-2/Fn-k)Lk+1, где Lk+1 = bk+1 - ak+1; перейти на шаг 2. (2) Если f(lk)>> f(mk),то положить ak+1 =lk, bk+1 = bk, lk+1 = mk и вычислить mk+1 = ak+1 + (Fn-k-1/Fn-k) Lk+1. Шаг 2. Проверить критерий окончания поиска: (1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1. Шаг 3. Найти аппроксимирующий минимум х(*): (1) Положить mk = lk + e. (2) Если f(lk) > f(mk), то x(*) = (lk + bk)/2. В противном случае - x(*) = (ak + mk)/2.
double Fibonacci(double a, double b, int &kFib) // Fibonacci - 1 { double lyambda, mu, eps = 0.0001, Ln = eps * 0.01; int n = 0; while (Fib(n) < (b - a) / Ln) // вычисление числа n n++; lyambda = a + (Fib(n - 2)*(b - a)) / Fib(n); // начальные точки mu = a + (Fib(n - 1)*(b - a)) / Fib(n); while (kFib < n - 1) // КОП: k = n - 1 { if (f(lyambda) < f(mu)) // определение направления сокращения { b = mu; // сокращение интервала mu = lyambda; lyambda = a + (Fib(n - kFib - 2)*(b - a)) / Fib(n - kFib); } else { a = lyambda; lyambda = mu; mu = a + (Fib(n - kFib - 1)*(b - a)) / Fib(n - kFib); } kFib++; } if (f(lyambda) > f(mu)) // определение конечного интервала return (lyambda + b) / 2; // середина интервала - аппроксимирующий минимум else return (a + mu) / 2; } Алгоритм Фибоначчи-2
Начальный этап (1) Задать константу e, начальный интервал [a1, b1], длину конечного интервала Ln и определить число n так, чтобы выполнялось условие Fn > (b1 - a1)/Ln. (2) Выбрать одну пробную точку . Положить k = 1. Основной этап Шаг 1. Проверить критерий окончания поиска: если k=n, то остановиться и положить x*=x2. Шаг 2. Сократить текущий интервал локализации рассмотрением 4-х ситуаций, аналогично методу золотого сечения-2.
double fibonachchi2(double a,double b,int n) { double x1,x2,eps=0.0001; x1=a+(Fib(n-1)/Fib(n))*(abs(a-b));//+ (pow(-1,n))*eps/Fib(n); int k = 1; x2=a+b-x1;
while (k!=n) { if ((x1<x2) && (f(x1)<f(x2))) b=x2; if ((x1<x2) && (f(x1)>=f(x2))) { a=x1; x1=x2; } if ((x1>x2) && (f(x1)<f(x2))) a=x2; if ((x1>x2) && (f(x1)>=f(x2))) { b=x1; x1=x2; } x2=a+b-x1; k++; } return x1; } Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|