|
|
Метод средней точки (метод Больцано)
Данный метод является вариантом метода деления интервала пополам. Последовательные сокращения интервала неопределенности производятся на основе оценки производной минимизируемой функции в центре текущего интервала. Начальный этап. Для запуска метода необходимо: (1) задать [a1,b1]- начальный интервал локализации минимума, на границах которого знаки производных различны, т.е. f'¢(a1)f'¢(b1)<0; e - малое положительное число; (2) положить к=1 и перейти к основному этапу. Основной этап Шаг 1. Взять пробную точку хk в центре текущего интервала и проверить критерий окончания поиска: (1) xk = (ak + bk)/2; (2) если ½f'¢(xk)½ ≤ e и Lk= ½bk - ak½≤ e, то остановиться (хk = х* -аппроксимирующий минимум). Шаг 2. Сократить текущий интервал: (1) Если f ¢(xk) > 0, то положить ak+1 = ak и bk+1 =xk, в противном случае - ak+1 =xk, bk+1 =bk; (2) заменить k на k+1 и вернуться на шаг 1.
double bolzan(double a,double b) //---- Метод Больцано { double x1,eps=0.0001; //---- Инициализация переменных. x1=(a+b)/2; //---- Пробная точка в центре интервала
while ((abs(proiz_f(x1))>eps) && (abs(b-a)>eps)) //---- КОП. { if (proiz_f(x1)>0) b=x1; else a=x1; x1=(a+b)/2; //---- Подсчет пробной точки. } return (x1); } С плавающими координатами double Bolzano(double a, double b) { double x1, a0, eps = 0.001; a0 = a; // расстояние от настоящего 0 до минимума b = b - a; a = 0; // смещение начала координат x1 = (a + b) / 2; while ((abs(proiz_f(x1))>eps) && (abs(b - a)>eps)) // КОП { if (proiz_f(x1) > 0) b = x1; // (b = x1 - a0)??? else { a0 = a0 + x1; b = b - x1; } x1 = (a + b) / 2; } x1 = x1 + a0; // вычисление координаты минимума от настоящего нуля return (x1); } Метод квадратичной интерполяции – экстраполяции Данный метод относится к классу прямых методов, опирающихся на идею построения аппроксимирующего полинома второго порядка на основании информации о значениях функции в n+1 точке – узлах интерполяции. Начальный этап 1. Выбрать произвольную точку x1ÎRn 2. Задаться величиной шага h=0.001 3. Определить погрешность 4. Положить счётчик числа итераций равным 1, а также b=x1 Основной этап Шаг 1. Вычислить fi в 3-х точках: a, b и с – центральной (b) и двух соседних: a=b-h, c=b+h. Затем, по формуле
или
найти аппроксимирующий минимум d Шаг 2. Проверить критерий близости 2-х точек b и d
Если оба условия выполняются – фиксируем аппроксимирующий минимум
и останавливаемся. Если оба критерия не выполняются, полагаем b=d и возвращаемся на шаг 1.
Метод ДСК: Начальный этап: 1) задать x0 – произвольная начальная точка. 2) выбрать шаг h равным 0.01…0.001(если x0 = 0) или 0.01*|x0|(если x0 не = 0). 3) e1=e2 (0.01…0.001) Основной этап: Шаг 1: Получить 3 равностоящих точки методом Свенна2: 1) Установить направление убывания целевой функции. Для этого надо взять x2=x1+h. Если f1<f2, то надо поменять направление движения (h=- h и взять x2=x1+h). 2) xk+1=xk+2* hk-1 пока не будет xm-1: fm-1< fm. 3) xm+1=(xm+xm-1)/2. 4) Из f(xm+1)и f(xm-1) взять минимальную 5) Переименовать а= xm-2 b= xm-1 с= xm+1 или а= xm-1 b= xm+1 с= xm Шаг 2: Найти d=b+1/2*((b-a)*(f(a)-f(c))/(f(a)-2*f(b)+f(c))); Шаг 3: КОП: Если l(d-b)/bl<=e1 и l(f(d)-f(b))/f(b)l<=e2 выполняются, то x*=(b-d)/2 Иначе: x0 = min(f(b),f(d)) и h1=h/2 goto Шаг1.
double DSK(double a, double b, int &kDSK) // Davies - Swann - Campey { double x1 = 0, x2, x0, eps = 0.0001, h, c, d; if (x1!= 0) // задаем шаг h = 0.01*x1; else h = 0.01; do { x2 = x1 + h; if (f(x1) < f(x2)) // смена направления движения { h = -h; x2 = x1 + h; // вычисление следующей точки } while (f(x1) > f(x2)) // пока функция не начнет расти { x0 = x1; x1 = x2; x2 = x1 + h; h = h * 2; // движение с удвоением шага } c = (x1 + x2) / 2; // определение центра последнего интервала if (f(x1) < f(c)) // определение меньшей из центральных точек { b = x1; // переименовывание точек отрезка a = x0; } else { a = x1; b = c; c = x2; } d = b + 1/2*((b - a)*(f(a) - f(c))) / (f(a) - 2 * f(b) + f(c)); // вычисление аппрокс. минимума h = h / 2; // уменьшение шага kDSK++; } while (abs((d - b) / b) <= eps && abs((f(d) - f(b)) / f(b)) <= eps); // КОП return fmin(b, d); // определение меньшего значеия - минимум }
Метод Пауэлла Метод Пауэлла является одним из самых популярных методов. Эффективен как и рассмотренный ранее алгоритм квадратичной интерполяции – экстраполяции, если начальная точка x1Îd(x*). Начальный этап 1. Выбрать ε1, ε2, h. 2. Взять 3 точки a, b, c на равных на равных интервалах. Предполагается, что сработал метод Свенна и получен интервал [a, b]. a=a; c=b; b=(a+c)/2; Основной этап 1. Найти аппроксимирующий минимум на 1-й итерации по формуле:
на последующих итерациях по формуле:
2. Проверить критерии близости двух точек:
Если он выполняется, принять Если не выполняется, то из 2-х точек b и d выбрать «лучшую» - в которой наименьшее значение функции, обозначить её как b, а 2 соседние с ней – a и c. Далее рассмотреть 4 ситуации аналогично ЗС-2. 3. Положить k=k+1 и вернуться на шаг 1. double Pauell(/*double alpha_a,double alpha_b*/) { double alpha_a,alpha_b, alpha_x; methodSwann(&alpha_a,&alpha_b); double alpha_c = alpha_b; alpha_b = (alpha_c + alpha_a)/2; double alpha_d=0.5*(f(alpha_a)*(alpha_b*alpha_b-alpha_c*alpha_c) + f(alpha_b)*(alpha_c*alpha_c-alpha_a*alpha_a) + f(alpha_c)*(alpha_a*alpha_a-alpha_b*alpha_b))/(f(alpha_a)*(alpha_b-alpha_c)+f(alpha_b)*(alpha_c-alpha_a)+f(alpha_c)*(alpha_a-alpha_b));
//while ((abs((alpha_b-alpha_d)/alpha_b)>eps) || (abs((f(alpha_b)-f(alpha_d))/f(alpha_b))>eps)) while (1) { if(f(alpha_b) >= f(alpha_d)) { if(alpha_b >= alpha_d) { alpha_c = alpha_b; }
else { alpha_a = alpha_b; } alpha_b = alpha_d; } else { if(alpha_b >= alpha_d) { alpha_a = alpha_d; } else { //alpha_b = alpha_d; alpha_c = alpha_d; }
} alpha_d = (alpha_a+alpha_b)/2 + 0.5 * (((f(alpha_a) - f(alpha_b))*(f(alpha_a) - f(alpha_b))*(alpha_b - alpha_c)*(alpha_c - alpha_a))/(f(alpha_a)*(alpha_b - alpha_c) + f(alpha_b)*(alpha_c - alpha_a) + f(alpha_c)*(alpha_a - alpha_b))); (k)++; if((fabs((alpha_b-alpha_d)/alpha_b) <= eps) || (fabs((f(alpha_b)-f(alpha_d)) / f(alpha_b)) <= eps)) break; if(k > 20) break; }
alpha_x = (alpha_b+alpha_d)/2; return alpha_x; }
Метод Давидона Начальный этап 1. Выбрать ε, x0, p, α1 2. Предполагается, что сработал метод Свенна и получен интервал [a, b]. Основной этап 1. Найти аппроксимирующий минимум, т.е. точку d по формулам:
2. Проверить КОП: если y`r≤ ε, то остановиться, х=a+αrp. Иначе: сократить ТИЛ: если y`r <0, то [r,b], если y`r >0, то [a,r]. Положить k=k+1 и вернуться на шаг 1.
double david(double a, double b) { double eps = 0.0001, gam, w, z, d, k = 0;
while (1) { z = df(a) + df(b) + (3 * (f(a) - f(b))) / (b - a); w = sqrt(z*z - df(a)*df(b)); gam = (z - df(a) + w) / ((df(b) - df(a) + 2 * w))*(b - a); d = a + gam; k++; //cout<<"\n---------DEVID NOW RUNNING k: "<<k<<"-------\n";
if (df(d) <= eps) { cout << "DAVID k: " << k << "\n"; cout << "DAVID gam: " << gam << "\n\n"; return (gam); } else { if (df(gam)<0) b = gam; else a = gam; } } }   Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
(1)
(2)
и 
; 
и остановиться.