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

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





 

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

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

(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 Размещенные материалы защищены законодательством РФ.