Локальный максимум | C++ для приматов

Используйте метод золотого сечения для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] локальный максимум функции $f\left( x \right) = \ln \left(1+ x^{2} - \cos x \right) - e^{\sin \pi x}$ на отрезке $\left[a;b\right]$ .

Входные данные

[latex]a, b[/latex] — концы отрезка, на котором требуется найти максимум, и точность [latex]\varepsilon[/latex].

Выходные данные

Точка локального максимума и локальный максимум в формате [latex](x_{max}, y_{max})[/latex].

Тесты

[latex]\varepsilon[/latex]	[latex]a[/latex]	[latex]b[/latex]	[latex](x_{max}, y_{max})[/latex]
[latex]0.001[/latex]	[latex]1.05[/latex]	[latex]2.2[/latex]	[latex](1.74435, 0.951781)[/latex]
[latex]0.0001[/latex]	[latex]1.05[/latex]	[latex]2.2[/latex]	[latex](1.74417, 0.951781)[/latex]
[latex]0.0001[/latex]	[latex]5.7[/latex]	[latex]8[/latex]	[latex](7.57498, 3.68407)[/latex]
[latex]0.0001[/latex]	[latex]3[/latex]	[latex]4[/latex]	[latex](3.61901, 2.31289)[/latex]

Алгоритм

Для начала проанализируем данную нам функцию. Найдем ее область определения.

[latex]D(f) = x^2 + 1 + \cos x > 0 [/latex]
[latex]D(f) = x^2 + 1 + \cos x = x^2 + [/latex] [latex]\frac{1}{2}[/latex] [latex] \cos^2[/latex] [latex]\frac{x}{2}[/latex] [latex] > 0[/latex] [latex]\forall[/latex] [latex]x[/latex] [latex]\in [/latex] [latex] \mathbb{R}[/latex]

Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику).
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывных, унимодальных функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума [latex]x_{max}[/latex].

[latex]x_1 \le[/latex] [latex]x_2 \le[/latex] [latex]x_{max}[/latex] [latex]\Rightarrow[/latex] [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]
[latex]x_1 \ge[/latex] [latex]x_2 \ge[/latex] [latex]x_{max}[/latex] [latex]\Rightarrow[/latex] [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]

Отсюда следует, что если функция [latex]f(x)[/latex] унимодальна на отрезке [latex][a; b][/latex], то максимум этой функции единственен, а локальные минимумы обязательно располагаются на его концах. Так как данная нам функция не является таковой, то для корректного применения метода и получения желаемого результата мы будем собственноручно задавать такие отрезки, на которых представленная функция унимодальна (их несложно выделить по графику).

Проведя анализ функции, обратимся к самому методу золотого сечения.

Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки [latex]x_1[/latex] и [latex]x_2[/latex] такие, что

[latex]\frac{b — a}{b — x_1}[/latex] [latex]= \frac{b — a}{x_2 — a} =[/latex] [latex]\varphi[/latex] [latex] = \frac{1 + \sqrt{5}}{2}[/latex]

То есть точка [latex]x_1[/latex] делит отрезок [latex][a; x_2][/latex] в отношении золотого сечения. Аналогично [latex]x_2[/latex] делит отрезок [latex][x_1; b][/latex] в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

На первом шаге исходный отрезок делим двумя симметричными относительно его центра точками и находим значение в этих точках.
После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой минимально, откидываем.
На следующем шаге следует найти всего одну новую точку.
Повторяем до тех пор, пока не будет достигнута заданная точность.

Код программы:

#include <iostream>
#include <math.h>
using namespace std;

const double goldenRatio = (1 + sqrt(5)) / 2; // "Золотое" число

// Рассматриваемая нами функция
double function(double x) {
	return log(1 + x * x - cos(x)) - pow(M_E, sin(M_PI * x));
}

int main() {
	double a, b; // Концы отрезка
	double accuracy; // Точность, с которой мы находим локальный максимум
	double x1, x2; // Точки, делящие текущий отрезок в отношении золотого сечения
	cin >> a >> b >> accuracy;
	while (fabs(b - a) > accuracy) {
		   x1 = b - (b - a) / goldenRatio; 
	       x2 = a + (b - a) / goldenRatio;
	       if (function(x1) <= function(x2)) // Условие для поиска максимума
	           a = x1; 
	       else 
	           b = x2;
	} // Выполняем, пока не достигнем заданной точности
	cout << "(" << (a + b) / 2 << ", " << function((a + b) / 2) << ")"; 
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

const double goldenRatio = (1 + sqrt(5)) / 2; // "Золотое" число

// Рассматриваемая нами функция

double function(double x) {

return log(1 + x * x - cos(x)) - pow(M_E, sin(M_PI * x));

}

int main() {

double a, b; // Концы отрезка

double accuracy; // Точность, с которой мы находим локальный максимум

double x1, x2; // Точки, делящие текущий отрезок в отношении золотого сечения

cin >> a >> b >> accuracy;

while (fabs(b - a) > accuracy) {

x1 = b - (b - a) / goldenRatio;

x2 = a + (b - a) / goldenRatio;

if (function(x1) <= function(x2)) // Условие для поиска максимума

a = x1;

else

b = x2;

} // Выполняем, пока не достигнем заданной точности

cout << "(" << (a + b) / 2 << ", " << function((a + b) / 2) << ")";

return 0;

}

Ссылки

Код программы
Больше информации о методе золотого сечения:
Источник 1; Источник 2; Источник 3;

Related Images:

В массиве [latex]A(n)[/latex] найти и напечатать номера (индексы) локальных максимумов, то есть таких [latex]a_{i}[/latex], что [latex]a_{i-1}<a_{i}>a_{i+1}[/latex].

Значение	Результат
8 5 3 8 6 7 2 9 5	2 4 6

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	double x[n];
	for(int i=0; i<n; i++){
		cin >> x[i];
	}
	for(int j=1; j<=(n-2); j++){
		if((x[j]>x[j+1])&&(x[j]>x[j-1])){
			cout << j << " ";
		}	
	
	}
	
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double x[n];

for(int i=0; i<n; i++){

cin >> x[i];

}

for(int j=1; j<=(n-2); j++){

if((x[j]>x[j+1])&&(x[j]>x[j-1])){

cout << j << " ";

}

return 0;

}

Для решения данной задачи зададим массив. После этого создадим цикл, в котором будем каждую итерацию проверять, удовлетворяет ли новое значение нашему условию и если да, то выводить на печать его номер.