Численные алгоритмы

Тернарный (троичный) поиск — это метод для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.

Алгоритм определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях.

Алгоритм Minimum(`f, a, b, epsilon`)
// Входные данные: непрерывная на `[a, b]` функция `f(x)`
// Выходные данные: Приближенное значение точки минимума
while `b-a>epsilon` do
`quad x_1 larr (2*a + b)//3; x_2 larr (a + 2*b)//3`
`quad` if `f(x_1)<f(x_2)`
`quad quad b larr x_2`
`quad` else
`quad quad a larr x_1`
return `a`

Тернарный поиск на каждом шаге вычисляет значение функции `f` дважды. Для уменьшения количества вычислений функции можно применить метод золотого сечения

1. На первой итерации заданный отрезок делится двумя точками `x_1=(a+phi*b)//Phi, x_2=(phi*a+b)//Phi`, где `Phi=1//phi=(1+sqrt{5})/2`, и рассчитываются значения в этих точках.
2. После чего отбрасывают тот из концов отрезка, к которому ближе оказалась точка, значение функции в которой максимально (для случая поиска минимума).
3. Процедура продолжается до тех пор, пока не будет достигнута заданная точность, но из-за свойств золотого сечения значение функции уже надо вычислять всего в одной новой точке.

Задания для практики

1. Найдите минимум функции `f(x)=x - ln x` с абсолютной ошибкой меньшей `10^{-1}`