Тернарний пошук#10169

Тернарний пошук (Розбір)

Нехай $f (x)$ — неперервна увігнута функція, яка має точку локального мінімуму на відрізку $[a; b]$ . Тернарний пошук дозволяє знайти цю точку.

includegraphicshttps://eolympusercontent.com/images/k07p00eoq979b0275n5ugbq6isВиберемо $g = a + (b - a) /3, h = a + 2 c d o t (b - a) /3$ g = a + (b - a) / 3, h = a + 2 \\cdot (b - a) / 3. Точки $g$ і $h$ ділять відрізок $[a; b]$ на три рівні частини (звідси й назва — тернарний пошук). Обчислимо значення $f (g)$ і $f (h)$ .

beginitemize

item Якщо $f (g) l e f (h)$ f(g) \\le f(h), то точка мінімуму функції $f$ лежить на відрізку $[a; h]$ , тому покладаємо $b = h$ b = h.

item Якщо $f (g) > f (h)$ f(g) > f(h), то точка мінімуму лежить на відрізку $[g; b]$ , тому покладаємо $a = g$ a = g.

enditemizeПроцес продовжується доти, поки $∣ a - b ∣ > e p s i l o n$ |a - b| > \\epsilon.

textbfПрикладУ прикладі задана функція $f (x) = x^{2} - 2 c d o t x - 35 = (x - 7) (x + 5)$ f(x) = x^2 - 2 \\cdot x - 35 = (x - 7) (x + 5). Її корені: $x_{1} = - 5, x_{2} = 7$ x_1 = -5, x_2 = 7. Мінімум функції досягається при

\nx ˚ = (x_{1} + x_{2}) /2 = (- 5 + 7) /2 = 1 \n ˚

\r\nx = (x_1 + x_2) / 2 = (-5 + 7) / 2 = 1\r\n

Задачу також можна розв'язати за допомогою математичної формули. Мінімум квадратичної функції $f (x) = a x^{2} + b x + c (a > 0)$ f(x) = ax^2 + bx + c~(a > 0) досягається в точці $x = - b / (2 a)$ x = -b / (2a).Слідовно, для функції $f (x) = x^{2} + a c d o t x + b$ f(x) = x^2 + a \\cdot x + b мінімум досягається при $x = - a /2$ x = - a / 2.

textbfРеалізація алгоритмуОголосимо константу $ɛ = 1 0^{- 7}$ ɛ = 10^{-7}.

beginlstlisting[language=C++]#define EPS 0.0000001

endlstlistingОголосимо функцію

textbff, мінімум якої потрібно знайти.

beginlstlisting[language=C++]f(double x)return x * x + a * x + b;

endlstlistingФункція

textbftriple знаходить мінімум функції $f (x)$ на відрізку $[a; b]$ .

beginlstlisting[language=C++]triple(double f(double x), double a, double b)double g, h;while (b - a > EPS)g = a + (b - a) / 3;h = a + 2 * (b - a) / 3;if (f(g) <= f(h)) b = h; else a = g;return (a + b) / 2;

endlstlistingОсновна частина програми. Читаємо вхідні дані. Запускаємо тернарний пошук. Знаходимо точку мінімуму функції $f (x)$ .

beginlstlisting[language=C++]("