Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Метод средней точки (метод Больцано)





 

Данный метод является вариантом метода деления интервала пополам. Последовательные сокращения интервала неопределенности производятся на основе оценки производной минимизируемой функции в центре текущего интервала.

Начальный этап. Для запуска метода необходимо:

(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. Затем, по формуле

(1)

или

(2)

найти аппроксимирующий минимум 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;

}

}

}









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.