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

Введение

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

Основные понятия

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

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

Используем точки, расположенные симметрично относительно середины отрезка  : ,

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

1. .

2. .

3. .

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

Метод золотого сечения

Точка  является золотым сечением отрезка  , если отношение длины всего отрезка к длинебольшей части равно отношению большей части к длине меньшей части , т. е. . Аналогично, точка , симметричная точке относительно середины отрезка, является вторым золотым сечением этого отрезка.

Так как точки  и симметричны относительно середины отрезка , то можно записать

,

где  . Свойство золотого сечения: точка одновременно является золотым сечением отрезка , а другая точка  золотым сечением отрезка  .

При поиске минимума функции используется следующий алгоритм:

1. На исходном отрезке  по формуле (8.1) при найдем точки и , а затем разность.

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

3. На полученном отрезке  находятся два сечения и . При этом возможны три случая:

1. .

2. .

3. .

4. По приведенной схеме находятся отрезки  , и т. д., с учетом того, что в случаях 1) и 2) значение или целевой функции уже получено на предыдущем шаге .

5. Точность приближенного равенства  на -м шаге вычислений можно оценить неравенством ,

где  .

Метод сканирования

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

Сравним возможные значения функции  и . Возможны три варианта продолжения приближения к точке минимума.

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

2. значение функции возросло. В этом случае полагаем, что начальной точкой вычислений является точка  , а меньшим шагом для продолжения вычислений – величина , где - некоторое целое число, . Далее производим вычисления по схеме 1 или 2 до достижения требуемой точности.

3. (маловероятно). Принимается либо  при достижении требуемой точности .

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

Шаги метода:

1. Выбор начального интервала: Задаем начальный интервал [a, b], где f(a) и f(b) — значения функции на концах интервала. Предполагается, что f(a) > f(b) (или наоборот, в зависимости от того, ищем ли мы минимум или максимум). На этом этапе мы выбираем интервал [a, b], в котором будем искать минимум функции f(x). Важно, чтобы функция была непрерывной на этом интервале, и чтобы значения функции на концах интервала были различны (то есть f(a) ≠ f(b)). Это условие гарантирует наличие минимума внутри интервала.

Пример:

Рассмотрим функцию f(x) = (x - 2)² + 1

Допустим, мы хотим найти минимум функции f(x) = (x - 2)² + 1. Мы можем выбрать начальный интервал [0, 4].

• Вычисляем значения:

f(0) = (0 - 2)² + 1 = 5

f(4) = (4 - 2)² + 1 = 5

Здесь значения равны, поэтому необходимо выбрать другой интервал, например, [0, 3]:

f(3) = (3 - 2)² + 1 = 2

Теперь у нас есть: f(0) = 5, f(3) = 2, и мы можем продолжать.

2. Проверка условий. Перед началом итераций важно убедиться, что:

f(a) и f(b) имеют разные знаки (в случае поиска корней), или что мы ожидаем минимум внутри интервала.

3. Вычисление середины

Описание:

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

c = a + b / 2

Эта точка будет использована для оценки значения функции и дальнейшего сужения интервала.

Пример:

Для интервала [0, 3]:

• Середина:

c = 0 + 3 / 2 = 1.5

Теперь вычислим значение функции в этой точке:

f(1.5) = (1.5 - 2)² + 1 = 1.25

4. Сравнение значений функции

Описание:

Сравниваем значения функции в точках a, b и c:

• Если f(c) < f(b), это означает, что минимум может находиться между a и c. Обновляем границы: b = c.

• Если f(c) > f(b), это означает, что минимум может находиться между c и b. Обновляем границы: a = c.

• Если f(c) = f(b), можно выбрать любое направление, так как минимум может находиться в любом из них.

Пример:

Сравниваем:

• f(0) = 5

• f(3) = 2

• f(1.5) = 1.25

Так как f(1.5) < f(3), обновляем границы:

• Теперь у нас: a = 0, b = 1.5.

5. Повторение процесса

Описание:

Процесс повторяется с новым интервалом [a, b]. На каждой итерации снова вычисляем середину и сравниваем значения функции до тех пор, пока длина интервала |b - a| не станет меньше заданной точности ∊.

Пример:

Новый интервал: [0, 1.5]

• Середина:

c = 0 + 1.5 / 2 = 0.75

Вычисляем значение функции:

f(0.75) = (0.75 - 2)² + 1 = 3.0625

Сравниваем:

• f(0) = 5

• f(1.5) = 1.25

• f(0.75) = 3.0625

Так как f(0.75) > f(1.5), обновляем границы:

• Теперь у нас: a = 0.75, b = 1.5.

Преимущества метода половинного деления

• Простота реализации: Легко реализовать в программировании.

• Гарантия сходимости: При выполнении условий метод гарантированно найдет минимум.

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

Недостатки метода половинного деления

• Медлительность: Может потребоваться много итераций для достижения желаемой точности.

• Неэффективность для многомерных функций: Метод работает только для одномерных функций.

4. Графическое представление

Таблица функции f(x)= 2x^2-7x+2.

метод половинного деления			е=	0,001	f(x)= 2x^2-7x+2
a	x	b	f(a)	f(x)	f(a)*f(x)	точность
3,1	3,25	3,4	-0,48	0,375	-0,18	---
3,1	3,175	3,25	-0,48	-0,06375	0,0306	---
3,175	3,2125	3,25	-0,06375	0,152813	-0,00974	---
3,175	3,19375	3,2125	-0,06375	0,043828	-0,00279	---
3,175	3,184375	3,19375	-0,06375	-0,01014	0,000646	---
3,184375	3,189063	3,19375	-0,01014	0,016802	-0,00017	---
3,184375	3,186719	3,189063	-0,01014	0,003322	-3,4E-05	---
3,184375	3,185547	3,186719	-0,01014	-0,00341	3,46E-05	---
3,185547	3,186133	3,186719	-0,00341	-4,5E-05	1,54E-07	вып

Рис.1. Диаграмма поиска минимума функции

Рис.2. Схема алгоритма уточнения корней по методу половинного деления

Пример кода для создания графика на языке Python:

import numpy as np

import matplotlib.pyplot as plt

# Определяем функцию

def f(x):

return (x - 2)**2 + 1

# Интервал

a = 0

b = 4

x = np.linspace(-1, 5, 100)

y = f(x)

# Создаемграфик

plt.plot(x, y, label='f(x) = (x - 2)^2 + 1')

plt.axhline(0, color='black', lw=0.5)

plt.axvline(0, color='black', lw=0.5)

# Начальныйинтервал

plt.fill_betweenx(y, a, b, color='gray', alpha=0.5, label='Интервал [a, b]')

# Итерации метода

for i in range(3): # Пример последовательных приближений корня уравнения

c = (a + b) / 2

plt.plot(c, f(c), 'ro') # Точка c

if f(c) < f(a) and f(c) < f(b):

b = c

elif f(c) > f(a):

a = c

else:

b = c

plt.title('Поиск минимума функции методом половинного деления')

plt.xlabel('x')

plt.ylabel('f(x)')

plt.legend()

plt.grid()

plt.show()

Применение данного метода в различных областях.

Метод половинного деления (или метод бисекции) — это численный метод, который используется для поиска корней уравнений и оптимизации функций. В контексте поиска минимума функции одной переменной он может быть применён в различных областях. Вот несколько примеров:

1. Экономика:

• Оптимизация прибыли: Метод может использоваться для нахождения цен, при которых прибыль максимальна, или для минимизации затрат.

2. Инженерия:

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

3. Физика:

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

4. Компьютерные науки:

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

5. Медицина:

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

6. Экология:

• Управление ресурсами: Метод может помочь в оптимизации использования природных ресурсов, минимизируя воздействие на окружающую среду.

7. Финансовый анализ:

• Определение минимальных рисков: В инвестиционном анализе метод может использоваться для нахождения портфелей с минимальными рисками при заданной доходности.

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

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

Заключение

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

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

1. Куликов, В. И. Методы поиска экстремумов функций одной переменной: Учебное пособие. — М.: Высшая школа, 2010. — 256 с.

2. Смирнов, Н. Н. Численные методы и их применение в оптимизации: Учебное пособие для вузов. — СПб.: Питер, 2018. — 312 с.

3. Тихонов, А. Н., Арнольд, В. И. Уравнения и задачи оптимизации: Учебник / А. Н. Тихонов, В. И. Арнольд. — М.: Наука, 1979. — 400 с.

4. Зенков, А. В. Методы численного поиска минимума: учебное пособие / А. В. Зенков. — Екатеринбург: Издво Урал. ун-та, 2017. — 150 с.

5. Голубев, В. П., Кузнецов, А. А. Основы численных методов оптимизации: Учебное пособие / В. П. Голубев, А. А. Кузнецов. — М.: Физматлит, 2015. — 280 с.

Код для цитирования: Скопировать