Изменения

'''Троичный поиск''' {{---}} метод поиска минимума или максимума функции на отрезке.

Рассмотрим функцию этот алгоритм на примере поиска минимума (поиск максимума аналогичен). Пусть функция <tex>f(x)</tex> на отрезке <tex>[a, b]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, у в которой он достигается. Посчитаем значения функции в точках <tex> x_1 = a + \frac{(b-a)}{3} </tex> и <tex> x_2 = a + \frac{2(b-a)}{3} </tex>. Так как в точке <tex>x_{min}</tex> минимум, то до нее на отрезке <tex>[a, b]</tex> функция убывает, а после нее {{---}} возрастает, то есть минимум<tex> \forall x', x'' \in [a, b]: \\a < x' < x'' < x_{min} \Rightarrow f(a) > f(x') > f(x'') > f(x_{min}) \\x_{min} < x' < x'' < b \Rightarrow f(x_{min}) < f(x') < f(x'') < f(b) </tex>. Значит <tex>f(x_1) < f(x_2) \Rightarrow x_{min} \in [a, x_2]</tex>, аналогично <tex>f(x_1) > f(x_2) \Rightarrow x_{min} \in [x_1, b]</tex>. Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть <tex> b-a < \varepsilon </tex>.