MLoop 3

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

save

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

[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] в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

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

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

 

 

Ссылки

Related Images: