Поиск минимума: метод половинного деления для унимодальных функций одной переменной с реализацией на языке C++ - Студенческий научный форум

XVII Международная студенческая научная конференция Студенческий научный форум - 2025

Поиск минимума: метод половинного деления для унимодальных функций одной переменной с реализацией на языке C++

Ванина С.А. 1, Балабан Е.И. 1
1Коломенский институт (филиал) Московского политехнического университета
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

Одной из ключевых задач в математике является поиск минимума функции. Особенно интересным является поиск минимума унимодальных функций, которые обладают единственным минимумом на заданном интервале. Метод половинного деления представляет собой эффективный численный метод, позволяющий находить этот минимум с высокой точностью.

Точка глобального минимума: число x = b называется точкой глобального минимума или просто точкой минимума функции f(x) на множестве U, если выполняется неравенство f(b) ≤ f(x) для всех
x ∈ U.

Точка локального минимума: Число x ∈ U называется точкой локального минимума функции f(x), если выполняется неравенство f(x) ≤ f(y) для всех y, достаточно близких к x. Это означает, что существует ε > 0, такое что неравенство выполняется для любого ρ(x, y) ≤ ε .

Глобальный минимум функции f(x) является также и локальным минимумом, однако обратное утверждение, в общем случае, неверно.

Множество точек минимума функции f(x) на множестве X может быть пустым, состоять из конечного или бесконечного числа точек.

Унимодальные функции.

Непрерывная функция y = f(x) называется унимодальной на отрезке
[a, b], если:

• Точка x* локального минимума функции принадлежит отрезку [a, b];

• Для любых двух точек отрезка x₁ и x₂ , расположенных по одну сторону от точки минимума, точке x₁ , более близкой к точке минимума, соответствует меньшее значение функции. То есть, как при x* < x₁ < x₂, так и при
x₂ < x₁ < x* справедливо неравенство f(x₁) < f(x₂) .

Рис. 1. Строго унимодальная, непрерывная, дифференцируемая функция

Рис. 2. Нестрого унимодальная, непрерывная, дифференцируемая функция

Достаточное условие унимодальности функции f(x) на отрезке [a, b] содержится в следующей теореме: если функция f(x) дважды дифференцируема на отрезке [a, b] и выполняется условие f''(x) > 0 в любой точке этого отрезка, то функция f(x) является унимодальной на отрезке [a, b].

Метод половинного деления для нахождения минимума функции
и блок-схема алгоритма.

Метод основан на делении текущего отрезка [a, b] где содержится иско мый экстремум, на две равные части с последующим выбором одной из половин, в которой локализуется минимум в качестве следующего текущего отрез ка. Экстремум локализуется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на δ=ε /2, где ε — по грешность решения задачи оптимизации.

Основные шаги алгоритма заключаются в следующем:

1. Определение начального интервала поиска.

2. Вычисление середины интервала и значений функции в крайних и средних точках.

3. Сужение интервала до той половины, которая содержит минимум.

4. Повторение шагов 2-3 до достижения необходимой точности.

Рис. 3. Блок-схема алгоритма половинного деления

Переход к практическому примеру.

Теперь, когда мы рассмотрели теоретические аспекты метода половинного деления и унимодальности функций, давайте перейдем к практическому примеру. Мы будем использовать функцию, для которой мы можем определить границы унимодальности и применить метод половинного деления для нахождения минимума.

Пример:

Для функции f(x) = x2 / (2-x) найти промежуток X с R, на котором она унимодальна,а также найти приближенное решение этой задачи с точностью ε = 10-2 методом половинного деления.

Решение:

Для начала необходимо найти производные заданной функции:

f ' (x) = (4x - x2)/ (2-x)2;

f '' (x) = 8/ (2-x)3.

Анализируя вторую производную, можно сделать вывод, что f''(x) > 0 при x < 2. Это указывает на то, что функция имеет единственный минимум на интервале
(-;2).
При исследовании первой производной, мы установили, что f'(x) = 0 при
x = 0. Дополнительно, проанализировав знак производной по обе стороны от критической точки, определили, что x = 0 является минимумом функции.

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

Реализация алгоритма половинного деления на C++

Начало программы включает в себя объявление директив и подключение необходимых библиотек. Используется стандартная библиотека ввода-вывода и математические функции. После этого объявляются переменные, которые будут использоваться для хранения значений концов отрезка [a, b]. Затем программа запрашивает у пользователя ввод этих значений (Рисунок 4).

Рис. 4. объявление директив и подключение библиотек, объявление переменных, вод данных с клавиатуры пользователя

На девятой строке кода определена функция, для которой будет производиться поиск минимума.

Примечание: если необходимо найти минимум для другой функции, следует просто заменить определение функции на девятой строке на нужное выражение.

После запроса границ отрезка описана реализация метода половинного деления. Программа будет делить отрезок пополам до тех пор, пока не достигнет нужной точности (Рисунок 5).

Рис. 5. Основной алгоритм и вывод результата

После завершения цикла, программа выводит результат (Рисунок 6).

Рис. 6. Консольный вывод программы

Заключение

В данной статье рассмотрены основные определения, такие как глобальный и локальный минимумы, а также условия унимодальности.

Анализ функции f(x) = x2 / (2-x) продемонстрировал, как с помощью производных можно определить границы унимодальности и выявить точку минимума. Практическая реализация метода на языке C++ показала, как алгоритм может быть реализован на компьютере, что делает его доступным для широкого круга пользователей и различных приложений.

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

Список литературы

  1. Гончаров, В. А.  Методы оптимизации : учебное пособие для вузов / В. А. Гончаров. — Москва : Издательство Юрайт, 2024. — 191 с. — (Высшее образование). — ISBN 978-5-9916-3642-1. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/534423 (дата обращения: 10.01.2025).

  2. Прокопенко Н. Ю. Методы оптимизации [Текст]: учеб. пособие /Н. Ю. Прокопенко; Ниже гор. гос. архитектур. - строит. ун-т. – Н. Новгород: ННГАСУ, 2018. – 118 с.

  3. Ракитин В. И., Первушин В. Е. (1998). Практическое руководство по методам вычислений с приложением программ для персональных компьютеров: Учеб. пособие. М.: Высш. шк., 1998 – 383 с.

Просмотров работы: 16