Подразделы

Другие разделы

Дата и время

07/01/2026 12:52:30

Авторизация

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

Вычислительная математика Классификация ошибок вычислений Алгоритмы численного интегрирования Алгоритмы для решения нелинейных уравнений Алгоритмы для поиска экстремума

Алгоритмы для поиска экстремума

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

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

--

Алгоритм 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}`

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

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

Алгоритмы для поиска экстремума