Кафедра ИСиТ УО ВГТУ
  • Специальности
    • Экономика электронного бизнеса
    • Информационные системы
    • Information Control Systems
  • Каталог
  • Сайт кафедры
  • Сервисы
    • GitLab
    • JupyterHub
    • Soft
  1. ИСиТ
  2. РиОИИС
  3. Практика
  4. Лаб. работа “Методы одномерной оптимизации”
  • ИСиТ
    • АОС
      • Теория
        • Введение в операционные системы
        • Управление памятью
        • Управление процессами
        • Система ввода-вывода
        • Информационная безопасность
        • Виртуализация
      • Слайды
      • Практика
    • РВПсИПП
      • Теория
        • Настройка среды разработки для PHP
        • Введение в PHP
        • Работа с базами данных в PHP
        • Объектно-ориентированные возможности PHP
        • Разработка web-приложений на базе фреймворков
        • Основы Laravel
        • Шаблоны в Laravel
        • Модели и базы данных в Laravel
        • Формы и валидация в Laravel
        • Аутентификация и авторизация в Laravel
        • Создание REST API в Laravel
        • Работа с файлами и изображениями в Laravel
        • Тестирование и отладка в Laravel
        • Введение в фреймворк Symfony
        • Маршруты и контроллеры в Symfony
        • Шаблоны и Twig в Symfony
        • Формы и валидация в Symfony
        • Доступ к базам данных в Symfony
        • Аутентификация и авторизация в Symfony
        • Сервисы и зависимости в Symfony
        • Создание REST API в Symfony
        • Работа с файлами и медиа в Symfony
        • Сравнение и выбор фреймворка
        • Развертывание веб-приложения
      • Практика
        • Регистрация в JupyterHub
        • Лаб. работа “Основы PHP”
        • Лаб. работа “Массивы в PHP”
        • Лаб. работа “Создание веб-приложений с использованием Slim”
        • Лаб. работа 1 “Создание нового приложения Laravel”
        • Лаб. работа 2 “Добавление главной страницы и базовых маршрутов”
        • Лаб. работа 3 “Создание моделей, миграций и сидеров”
        • Лаб. работа 4 “Создание индексных страниц и пагинация”
        • Лаб. работа 5 “Создание форм для работы с сущностями”
        • Лаб. работа 6 “Работа с файлами (эмуляция S3-хранилища)”
        • Лаб. работа “Создание маршрутов в Laravel”
        • Лаб. работа “Работа с базами данных в Laravel”
        • Лаб. работа “Работа с формами в Laravel”
        • Лаб. работа “Аутентификация и авторизация в Laravel”
        • Лаб. работа “Работа с файлами в Laravel”
        • Лаб. работа “Тестирование и оптимизация в Laravel”
        • Лаб. работа “Создание REST API в Laravel”
        • Лаб. работа “Основы Symfony”
        • Лаб. работа “Шаблоны и представления в Symfony”
        • Лаб. работа “Работа с базами данных в Symfony”
        • Лаб. работа “Формы и аутентификация в Symfony”
        • Лаб. работа “Сервисы и зависимости в Symfony”
        • Лаб. работа “REST API в Symfony”
        • Лаб. работа “Работа с медиа контентом в Symfony”
        • Лаб. работа “Создание и развертывание проекта”
        • Расчетно-графическая работа: Разработка веб-приложения с использованием Laravel
          • Методические рекомендации по выполнению работы
          • Варианты заданий для расчетно-графической работы
    • ПСП
      • Теория
        • Введение
        • Протокол HTTP
        • Программирование с использованием сокетов
      • Практика
        • Программное обеспечение
        • Лаб. работа “Почтовые протоколы”
        • Лаб. работа “Протокол FTP”
        • Лаб. работа “Протокол HTTP”
        • Лаб. работа “Программирование сетевых приложений с использованием сокетов”
        • Лаб. работа “Обзор базовых конструкций и основных элементов языка”
        • Лаб. работа “Структурные элементы класса, методы взаимодействия объектов и организация наследования”
        • Лаб. работа “Типы исключительных ситуаций и процесс их обработки”
        • Лаб. работа “Потоки ввода/вывода и работа с файлами”
        • Лаб. работа “Организация потоков, параллельной обработки, синхронизации и распределённой обработки синхронизуемых участков кода”
        • Лаб. работа “Структурные механизмы языка программирования для реализации полиморфизма в программах”
        • Лаб. работа “Средства языка для организации работы в сети. Основные классы и интерфейсы реализации сетевого взаимодействия”
        • Лаб. работа “Библиотеки и средства внедрения визуальных компонент для организации GUI-интерфейсов пользователя. Обработка событий”
        • Лаб. работа “Концепция распределённой обработки данных и технологии удалённой обработки данных”
      • Темы курсовых проектов по дисциплине “Программирование сетевых приложений”
    • Компьютерные сети
      • Теория
        • Введение в компьютерные сети
        • Топологии сетей
        • Кодирование и мультиплексирование
        • Стеки протоколов
        • Адресация в компьютерных сетях
        • Система доменных имен (DNS)
        • Программирование с использованием сокетов
        • Введение в PHP
        • Протокол HTTP
        • Введение в компьютерные сети
      • Практика
        • Программное обеспечение
        • Регистрация в JupyterHub
        • Лаб. работа “Почтовые протоколы”
        • Лаб. работа “Протокол FTP”
        • Лаб. работа “Протокол HTTP”
        • Лаб. работа “Программирование сетевых приложений с использованием сокетов”
        • Лаб. работа “Основы PHP”
        • Лаб работа “Массивы в PHP”
    • РиОИИС
      • Слайды
      • Теория
        • Классификация оптимизационных задач
        • Генетические алгоритмы
        • Системы массового обслуживания
        • Теория игр
        • Машинное обучение
        • Глубокое обучение (Deep learning)
        • Основы функционального программирования
        • Основы программирования на Haskell
        • Введение в логическое программирование
        • Инференция и рассуждения в логическом программировании
        • Разработка экспертных систем
        • Интеллектуальные системы и их архитектура
        • Веб-скрэйпинг
        • Сбор данных с открытых API
      • Практика
        • JupyterHub
        • Лаб. работа “Основы программирования на Python”
        • Лаб. работа “Функции в Python”
        • Лаб. работа “Рекурсия в Python”
        • Лаб. работа “Итераторы в Python”
        • Лаб. работа “Методы одномерной оптимизации”
        • Лаб. работа “Методы многомерной оптимизации”
        • Лаб. работа “Линейное программирование”
        • Лаб. работа “Генетические алгоритмы”
        • Лаб. работа “Haskell”
        • Лаб. работа “Логическое программирование”
        • Лаб. работа “Сбор данных с помощью веб-скрейпинга”
        • Лаб. работа “Предобработка данных”
        • Лаб. работа “Машинное обучение: классификация”
        • Лаб. работа “Создание и обучение простейших нейронных сетей”
        • Лаб. работа “Системы массового обслуживания”
        • Лаб. работа “Обработка естественного языка”
        • Лаб. работа “Компьютерное зрение”
        • Лаб. работа “Нейросети и глубокое обучение”
    • КСКР
      • Практика
        • Лаб. работа “Одномерные и двумерные массивы в C#”
        • Лаб. работа “Обращение матриц в C#”
    • Системное программирование
      • Слайды
      • Слайды
      • Теория
        • Управление памятью в Windows
        • Файловые операции в Windows
        • Управление процессами в Windows
        • Графический интерфейс Windows
        • ОС Unix
      • Практика
        • Лаб. работа “Работа с динамической памятью в Windows”
        • Лаб. работа “Операции с файлами в Windows”
        • Лаб. работа “Управление процессами в Windows”
        • Лаб. работа “Работа с виртуальной машиной Linux”
        • Лаб. работа “Язык командного энтерпритатора Shell”
        • Лаб. работа “Работа с файлами в Linux”
        • Лаб. работа “Работа с процессами в Linux”
    • ИППРПО
      • Теория
      • Практика
        • Лаб. работа “Язык командного энтерпритатора Shell”
        • Лаб. работа “Управление процессами в Shell”
        • Лаб. работа “Управление файловой системой в Shell”
        • Лаб. работа “Управление пакетами в ОС Linux”
        • Лаб. работа “Сетевые инструменты в Linux”
        • Лаб. работа “Мониторинг и анализ системы Linux”
        • Лаб. работа “Основы Docker. Управление контейнерами”
        • Лаб. работа “Docker: Сети”
        • Лаб. работа "Docker: Образы"
        • Лаб. работа “Docker Compose: Управление многоконтейнерными приложениями”
        • Лаб. работа “CI/CD с GitLab”

Содержание

  • Постановка задачи
  • Локализация экстремума
  • Теоретические сведения
    • Общая постановка задачи одномерной оптимизации
    • Метод оптимального пассивного поиска
    • Метод дихотомии
    • Метод золотого сечения
    • Метод Фибоначчи
    • Сравнительная характеристика методов
  • Практическая реализация методов
    • Метод оптимального пассивного поиска в MS Excel
    • Метод дихотомии
    • Метод золотого сечения
    • Метод Фибоначчи
  • Сравнительный анализ методов
  • Варианты индивидуальных заданий
  1. ИСиТ
  2. РиОИИС
  3. Практика
  4. Лаб. работа “Методы одномерной оптимизации”

Лаб. работа “Методы одномерной оптимизации”

Разработка и оптимизация интеллектуальных информационных систем
Практика
Автор

Бизюк Андрей

Дата публикации

12 февраля 2026 г.

Постановка задачи

Найти точку минимума функции с заданной погрешностью

\[ f(x)=(x-8)^2-7 \]

Локализация экстремума

Определим отрезок, на котором находится точка минимума

Функция имеет единственную точку минимума на отрезке \([0;20]\)

Теоретические сведения

Общая постановка задачи одномерной оптимизации

Задача одномерной минимизации заключается в нахождении точки \(x^*\), в которой унимодальная функция \(f(x)\) достигает своего минимального значения на заданном отрезке \([a, b]\):

\[ x^* = \arg\min_{x \in [a, b]} f(x) \]

Под унимодальностью понимается свойство функции, при котором на отрезке \([a, b]\) существует единственная точка минимума \(x^*\), и функция монотонно убывает при \(x < x^*\) и монотонно возрастает при \(x > x^*\).

Все методы одномерной оптимизации основаны на процедуре уточнения отрезка неопределенности — интервала, гарантированно содержащего точку минимума.

Метод оптимального пассивного поиска

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

Основная идея

Пусть требуется найти минимум унимодальной функции \(f(x)\) на отрезке \([a, b]\) с точностью \(\varepsilon\). Выберем \(N\) точек \(x_1, x_2, \ldots, x_N\) на этом отрезке. После вычисления значений функции во всех точках, минимум найдем среди вычисленных значений.

Оптимальное распределение точек

Для обеспечения точности \(\varepsilon\) необходимо расположить точки на расстоянии \(2\varepsilon\) друг от друга. Первую точку размещаем на расстоянии \(\varepsilon\) от левого конца отрезка:

\[ x_1 = a + \varepsilon \]

Последующие точки размещаем с шагом \(2\varepsilon\):

\[ x_i = x_{i-1} + 2\varepsilon, \quad i = 2, 3, \ldots, N \]

Количество точек

Необходимое количество точек \(N\) определяется из условия охвата всего отрезка:

\[ N = \frac{b - a}{2\varepsilon} \]

Оценка погрешности

Максимальная погрешность метода оптимального пассивного поиска не превышает \(\varepsilon\):

\[ |x_{opt} - x^*| \leq \varepsilon \]

Достоинства и недостатки

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

Недостатки: - Большое количество вычислений функции - Неэффективное использование информации о поведении функции

Метод дихотомии

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

Основная идея

На каждой итерации отрезок неопределенности \([a, b]\) делится пополам. В центре отрезка выбираются две симметричные точки на малом расстоянии \(\delta\) от середины:

\[ c = \frac{a + b}{2}, \quad x_1 = c - \delta, \quad x_2 = c + \delta \]

Параметр \(\delta\) — малое число (\(\delta \ll \varepsilon\)), необходимое для того, чтобы различать значения функции в близких точках.

Алгоритм

  1. Вычислить значения функции \(f(x_1)\) и \(f(x_2)\) в точках \(x_1\) и \(x_2\)
  2. Сравнить значения функции:
    • Если \(f(x_1) < f(x_2)\), то минимум находится на левой половине отрезка. Новый отрезок: \([a, x_2]\)
    • Если \(f(x_1) > f(x_2)\), то минимум находится на правой половине отрезка. Новый отрезок: \([x_1, b]\)
    • Если \(f(x_1) = f(x_2)\), то минимум находится в центре. Новый отрезок: \([x_1, x_2]\)
  3. Проверить условие остановки: \(b - a < \varepsilon\)
  4. Если условие не выполнено, вернуться к шагу 1

Условие сходимости

Итерации продолжаются до тех пор, пока длина отрезка неопределенности не станет меньше заданной точности:

\[ b - a < \varepsilon \]

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

Количество вычислений функции

На каждой итерации выполняются два вычисления функции. Количество итераций можно оценить как:

\[ n \approx \log_2\left(\frac{b - a}{\varepsilon}\right) \]

Общее количество вычислений функции: \(N \approx 2n\).

Достоинства и недостатки

Достоинства: - Простота алгоритма - Быстрая сходимость по сравнению с пассивным поиском - Гарантированная сходимость для унимодальных функций

Недостатки: - Два вычисления функции на каждой итерации - Требует выбора параметра \(\delta\)

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

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

Золотое сечение

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

\[ \frac{a + b}{a} = \frac{a}{b} = \tau \]

Отсюда получаем характеристическое уравнение:

\[ \tau^2 - \tau - 1 = 0 \]

Положительный корень этого уравнения:

\[ \tau = \frac{1 + \sqrt{5}}{2} \approx 1.618034 \]

Обратное значение:

\[ \frac{1}{\tau} = \frac{\sqrt{5} - 1}{2} \approx 0.618034 \]

Основная идея

Пусть отрезок неопределенности \([a, b]\). Выберем две внутренние точки:

\[ x_1 = b - \frac{b - a}{\tau}, \quad x_2 = a + \frac{b - a}{\tau} \]

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

Алгоритм

  1. Вычислить начальные точки: \[ x_1 = b - \frac{b - a}{\tau}, \quad x_2 = a + \frac{b - a}{\tau} \]
  2. Вычислить значения функции \(f(x_1)\) и \(f(x_2)\)
  3. Сравнить значения функции:
    • Если \(f(x_1) < f(x_2)\), новый отрезок: \([a, x_2]\), при этом \(x_1\) становится внутренней точкой нового отрезка
    • Если \(f(x_1) \geq f(x_2)\), новый отрезок: \([x_1, b]\), при этом \(x_2\) становится внутренней точкой нового отрезка
  4. На каждой последующей итерации вычисляется только одно новое значение функции
  5. Проверить условие остановки: \(b - a < \varepsilon\)
  6. Если условие не выполнено, вернуться к шагу 3

Эффективность метода

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

Количество вычислений функции

Количество итераций:

\[ n \approx \frac{\ln(\frac{b - a}{\varepsilon})}{\ln(\tau)} \approx 1.44 \ln\left(\frac{b - a}{\varepsilon}\right) \]

Общее количество вычислений функции: \(N \approx n + 1\).

Достоинства и недостатки

Достоинства: - Одно вычисление функции на каждой итерации (после первой) - Высокая скорость сходимости - Не требует настройки параметров - Гарантированная сходимость для унимодальных функций

Недостатки: - Более сложная реализация по сравнению с методом дихотомии

Метод Фибоначчи

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

Числа Фибоначчи

Последовательность Фибоначчи определяется рекуррентным соотношением:

\[ F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}, \quad n \geq 2 \]

Первые числа Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Основная идея

Метод использует числа Фибоначчи для оптимального разбиения отрезка неопределенности. Если заранее известно количество итераций \(n\), метод Фибоначчи минимизирует конечную длину отрезка неопределенности.

Алгоритм

Пусть задано количество итераций \(n\). Начальный отрезок \([a_0, b_0]\).

  1. Вычислить \(n\) чисел Фибоначчи: \(F_0, F_1, \ldots, F_n\)
  2. Вычислить начальные точки: \[ x_1 = a_0 + \frac{F_{n-1}}{F_n}(b_0 - a_0), \quad x_2 = a_0 + \frac{F_{n-2}}{F_n}(b_0 - a_0) \]
  3. Вычислить значения функции \(f(x_1)\) и \(f(x_2)\)
  4. На \(k\)-й итерации (\(k = 1, 2, \ldots, n-1\)):
    • Если \(f(x_1) < f(x_2)\), новый отрезок: \([a_k, x_2]\), вычислить новую точку \(x_1\)
    • Если \(f(x_1) \geq f(x_2)\), новый отрезок: \([x_1, b_k]\), вычислить новую точку \(x_2\)
  5. На последней итерации принять \(x^* = \frac{a_n + b_n}{2}\)

Формулы для точек

На \(k\)-й итерации точки вычисляются по формулам:

\[ x_1 = a_k + \frac{F_{n-k-1}}{F_{n-k}}(b_k - a_k), \quad x_2 = a_k + \frac{F_{n-k}}{F_{n-k+1}}(b_k - a_k) \]

Оптимальность метода

Метод Фибоначчи является оптимальным в том смысле, что для заданного количества вычислений функции \(n\) он минимизирует длину финального отрезка неопределенности.

Связь с методом золотого сечения

При \(n \to \infty\) метод Фибоначчи стремится к методу золотого сечения, так как:

\[ \lim_{n \to \infty} \frac{F_{n-1}}{F_n} = \frac{1}{\tau} \]

Достоинства и недостатки

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

Недостатки: - Требует предварительного задания количества итераций - Необходимо вычислять числа Фибоначчи - Более сложная реализация

Сравнительная характеристика методов

Метод Вычислений функции на итерацию Сходимость Особенности
Оптимальный пассивный поиск Все заранее Медленная Простота, параллелизация
Дихотомия 2 Средняя Простота реализации
Золотое сечение 1 (после первой) Быстрая Оптимальный баланс
Фибоначчи 1 (после первой) Быстрая Теоретически оптимален

Практическая реализация методов

Метод оптимального пассивного поиска в MS Excel

Для решения задачи методом оптимального пассивного поиска будем использовать MsExcel или LibreOffice.

Зададим исходные данные

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

Выберем погрешность \(\epsilon = 0.5\). Количество точек найдем по формуле \(N=\frac{x_{max}-x_{min}}{2\epsilon}=\frac{20-0}{2\times 0.5}=20\)

Выберем точки \(x_i,\ i=1..N\), в которых нужно найти значение функции. Согласно методу оптимального пассивного поиска, точка \(x_1\) должна иметь координату \(x_{min}+\epsilon\). Остальные точки находятся по формуле: \(x_i=x_{i-1}+2\epsilon,\ i=2..N\).

Найдем значение функции для всех \(x_i\):

Построим график \(f(x)\) по полученным данным. Нужно вставить диаграмму точечного типа, а затем выбрать данные для нее.

Определим точку минимума и минимальное значение функции. Напишем формулы, которые найдут эти значения автоматически. Для этого нам потребуются функции МИН, ПОИСКПОЗ и ИНДЕКС.

Таким образом мы получили следующее решение:

\[ x_{opt}=7.5,\ f(x_{opt})=-6.75 \]

Найденное значение \(x_{opt}\) отличается от истинной точки минимума \(x^*=8\) на величину, не превышающую \(\epsilon\), следовательно, мы выполнили условие задачи.

Метод дихотомии

Для решения задачи методом дихотомии необходимо реализовать алгоритм на языке Python.

Итеративная реализация

import matplotlib.pyplot as plt
import numpy as np

def f(x):
    """Целевая функция"""
    return (x - 8)**2 - 7

def dichotomy_iterative(f, a, b, epsilon, delta, visualize=True):
    """
    Метод дихотомии (итеративная реализация)
    
    Параметры:
    f - целевая функция
    a, b - границы отрезка
    epsilon - точность
    delta - малое смещение от центра
    visualize - строить ли визуализацию
    
    Возвращает:
    x_opt - найденная точка минимума
    f_opt - значение функции в точке минимума
    iterations - количество итераций
    history - история сужения отрезка
    """
    iterations = 0
    history = [(a, b)]  # История для визуализации
    
    if visualize:
        # Подготовка графика
        fig, axes = plt.subplots(2, 1, figsize=(12, 10))
        
        # Верхний график - функция с точками
        x_points = np.linspace(a, b, 500)
        y_points = f(x_points)
        axes[0].set_ylim(-10, 10)
        axes[0].plot(x_points, y_points, 'b-', linewidth=2, label='f(x)')
        axes[0].grid(True, alpha=0.3)
        axes[0].set_xlabel('x')
        axes[0].set_ylabel('f(x)')
        axes[0].set_title('Метод дихотомии: поиск минимума')
        
        # Нижний график - сужение отрезка
        axes[1].set_xlim(0, 20)
        axes[1].set_ylim(-1, 21)
        axes[1].set_xlabel('Номер итерации')
        axes[1].set_ylabel('Отрезок [a, b]')
        axes[1].set_title('Сужение отрезка неопределенности')
        axes[1].grid(True, alpha=0.3)
    
    while b - a >= epsilon:
        iterations += 1
        
        # Вычисляем точки
        c = (a + b) / 2
        x1 = c - delta
        x2 = c + delta
        
        # Вычисляем значения функции
        f1 = f(x1)
        f2 = f(x2)
        
        if visualize:
            # Отображаем точки на графике функции
            axes[0].plot([x1, x2], [f1, f2], 'ro', markersize=8)
            axes[0].annotate(f'iter {iterations}', (x1, f1), 
                          xytext=(5, 5), textcoords='offset points', fontsize=8)
            axes[0].plot([a, b], [f(c), f(c)], 'g--', alpha=0.5)
            
            # Отображаем отрезок на нижнем графике
            axes[1].plot([iterations, iterations], [a, b], 'b-', linewidth=2)
            axes[1].plot(iterations, a, 'go', markersize=6)
            axes[1].plot(iterations, b, 'ro', markersize=6)
        
        # Сравниваем значения и сужаем отрезок
        if f1 < f2:
            b = x2
        elif f1 > f2:
            a = x1
        else:
            a = x1
            b = x2
        
        history.append((a, b))
    
    # Результат
    x_opt = (a + b) / 2
    f_opt = f(x_opt)
    
    if visualize:
        axes[0].plot(x_opt, f_opt, 'g*', markersize=20, label=f'x_opt = {x_opt:.6f}')
        axes[0].legend()
        
        # Добавляем текст с результатами
        result_text = f'Результат:\nx_opt = {x_opt:.6f}\nf_opt = {f_opt:.6f}\nИтерации: {iterations}'
        axes[1].text(0.5, 0.8, result_text, transform=axes[1].transAxes, 
                    fontsize=12, verticalalignment='center',
                    bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))
        
        plt.tight_layout()
        plt.savefig('dichotomy_visualization.png', dpi=300, bbox_inches='tight')
        plt.show()
    
    return x_opt, f_opt, iterations, history

# Параметры задачи
a = 0
b = 20
epsilon = 0.001
delta = 0.00001

# Запуск метода
x_opt, f_opt, iterations, history = dichotomy_iterative(f, a, b, epsilon, delta)

print(f"Результат метода дихотомии (итеративный):")
print(f"x_opt = {x_opt:.9f}")
print(f"f_opt = {f_opt:.9f}")
print(f"Количество итераций: {iterations}")
print(f"Финальный отрезок: [{history[-1][0]:.6f}, {history[-1][1]:.6f}]")
print(f"Длина отрезка: {history[-1][1] - history[-1][0]:.6f}")

Результат работы программы:

Результат метода дихотомии (итеративный):
x_opt = 8.000185105
f_opt = -6.999999966
Количество итераций: 15
Финальный отрезок: [7.999870, 8.000500]
Длина отрезка: 0.000630

Рекурсивная реализация

def dichotomy_recursive(f, a, b, epsilon, delta, count=0, history=None):
    """
    Метод дихотомии (рекурсивная реализация)
    
    Параметры:
    f - целевая функция
    a, b - границы отрезка
    epsilon - точность
    delta - малое смещение от центра
    count - счетчик итераций
    history - история сужения отрезка
    
    Возвращает:
    (x_opt, f_opt, count, history) - точка минимума, значение функции, 
                                      количество вычислений, история
    """
    if history is None:
        history = [(a, b)]
    
    # Проверка условия остановки
    if b - a < epsilon:
        x_opt = (a + b) / 2
        f_opt = f(x_opt)
        return x_opt, f_opt, count, history
    
    # Вычисляем точки
    c = (a + b) / 2
    x1 = c - delta
    x2 = c + delta
    
    # Вычисляем значения функции
    f1 = f(x1)
    f2 = f(x2)
    count += 2
    
    # Сравниваем значения и рекурсивно вызываем функцию
    if f2 < f1:
        history.append((x1, b))
        return dichotomy_recursive(f, x1, b, epsilon, delta, count, history)
    else:
        history.append((a, x2))
        return dichotomy_recursive(f, a, x2, epsilon, delta, count, history)

# Запуск рекурсивного метода
x_opt_rec, f_opt_rec, count_rec, history_rec = dichotomy_recursive(f, a, b, epsilon, delta)

print(f"\nРезультат метода дихотомии (рекурсивный):")
print(f"x_opt = {x_opt_rec:.9f}")
print(f"f_opt = {f_opt_rec:.9f}")
print(f"Количество вычислений функции: {count_rec}")
print(f"Финальный отрезок: [{history_rec[-1][0]:.6f}, {history_rec[-1][1]:.6f}]")

Результат работы рекурсивной реализации:

Результат метода дихотомии (рекурсивный):
x_opt = 8.000185105
f_opt = -6.999999966
Количество вычислений функции: 30
Финальный отрезок: [7.999870, 8.000500]

Визуализация процесса оптимизации

При запуске программы создается график, показывающий:

  1. Верхний график: функция \(f(x)\) с отмеченными точками вычислений на каждой итерации
  2. Нижний график: последовательное сужение отрезка неопределенности

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

Задание для самостоятельной реализации

Реализуйте метод золотого сечения на языке Python для нахождения минимума функции \(f(x) = (x-8)^2 - 7\) на отрезке \([0, 20]\) с точностью \(\varepsilon = 0.001\).

Требования к реализации

  1. Функция золотого сечения: Напишите функцию golden_section(f, a, b, epsilon), которая реализует итеративный алгоритм метода золотого сечения.

  2. Параметры функции:

    • f — целевая функция
    • a, b — границы отрезка
    • epsilon — требуемая точность
  3. Алгоритм:

    • Вычислить коэффициент золотого сечения: \(\tau = \frac{1 + \sqrt{5}}{2}\)
    • На первой итерации вычислить две точки: \[ x_1 = b - \frac{b - a}{\tau}, \quad x_2 = a + \frac{b - a}{\tau} \]
    • На каждой последующей итерации вычислять только одну новую точку
    • Сравнивать значения функции и сужать отрезок неопределенности
    • Продолжать до выполнения условия: \(b - a < \varepsilon\)
  4. Возвращаемые значения:

    • x_opt — найденная точка минимума
    • f_opt — значение функции в точке минимума
    • iterations — количество итераций
    • evaluations — количество вычислений функции
    • history — список кортежей (a, b, x1, x2) для каждой итерации
  5. Визуализация: Добавьте построение графика, аналогичного визуализации метода дихотомии, с отображением:

    • Функции с отмеченными точками вычислений
    • Последовательного сужения отрезка неопределенности

Ожидаемый результат

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

x_opt ≈ 7.9995
f_opt ≈ -7.0000
Количество итераций: ~20-22
Количество вычислений функции: ~21-23

Контрольные вопросы

  1. Почему метод золотого сечения требует только одно вычисление функции на каждой итерации (после первой)?
  2. Каким свойством обладают точки \(x_1\) и \(x_2\) в методе золотого сечения?
  3. Сравните эффективность методов дихотомии и золотого сечения по количеству вычислений функции.

Метод Фибоначчи

Задание для самостоятельной реализации

Реализуйте метод Фибоначчи на языке Python для нахождения минимума функции \(f(x) = (x-8)^2 - 7\) на отрезке \([0, 20]\) с точностью \(\varepsilon = 0.001\).

Требования к реализации

  1. Генерация чисел Фибоначчи: Напишите вспомогательную функцию fibonacci_numbers(n), которая возвращает список из \(n+1\) чисел Фибоначчи:

    def fibonacci_numbers(n):
        """Генерирует первые n+1 чисел Фибоначчи"""
        fib = [0, 1]
        for i in range(2, n + 1):
            fib.append(fib[i-1] + fib[i-2])
        return fib
  2. Определение количества итераций: Найдите минимальное \(n\) такое, что: \[ \frac{b - a}{F_n} < \varepsilon \] где \(F_n\) — \(n\)-е число Фибоначчи.

  3. Функция метода Фибоначчи: Напишите функцию fibonacci_search(f, a, b, epsilon), которая реализует алгоритм метода Фибоначчи.

  4. Алгоритм:

    • Вычислить необходимое количество итераций \(n\) и сгенерировать числа Фибоначчи
    • На первой итерации вычислить две точки: \[ x_1 = a + \frac{F_{n-1}}{F_n}(b - a), \quad x_2 = a + \frac{F_{n-2}}{F_n}(b - a) \]
    • На каждой последующей итерации вычислять только одну новую точку
    • Сравнивать значения функции и сужать отрезок неопределенности
    • На последней итерации принять \(x^* = \frac{a + b}{2}\)
  5. Возвращаемые значения:

    • x_opt — найденная точка минимума
    • f_opt — значение функции в точке минимума
    • iterations — количество итераций
    • evaluations — количество вычислений функции
    • history — список кортежей с историей сужения отрезка
  6. Визуализация: Добавьте построение графика, аналогичного визуализации метода дихотомии.

Ожидаемый результат

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

x_opt ≈ 7.9995
f_opt ≈ -7.0000
Количество итераций: ~20-22
Количество вычислений функции: ~21-23

Дополнительное задание

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

Контрольные вопросы

  1. В каком смысле метод Фибоначчи является оптимальным?
  2. Какое ограничение имеет метод Фибоначчи по сравнению с методом золотого сечения?
  3. Что происходит с отношением \(\frac{F_{n-1}}{F_n}\) при \(n \to \infty\)?
  4. Почему метод Фибоначчи дает результат, близкий к методу золотого сечения?

Сравнительный анализ методов

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

Метод Количество итераций Количество вычислений функции Точность Время выполнения
Оптимальный пассивный поиск
Дихотомия (итеративная)
Дихотомия (рекурсивная)
Золотое сечение
Фибоначчи

Варианты индивидуальных заданий

Реализуйте все методы одномерной оптимизации для вашей функции. Найдите точку минимума с точностью \(\varepsilon = 0.001\) на указанном отрезке.

  1. \(f(x) = x^2 + 3x + 2\), отрезок \([-3, 1]\)
  2. \(f(x) = e^{0.5x} - 2x\), отрезок \([0, 5]\)
  3. \(f(x) = \sin(2x) + x\), отрезок \([0, \pi]\)
  4. \(f(x) = -\ln(2x + 1)+x\), отрезок \([0, 3]\)
  5. \(f(x) = 2x^3 - 5x^2 + x + 3\), отрезок \([0, 2]\)
  6. \(f(x) = -\sqrt{3x} + x\), отрезок \([0, 5]\)
  7. \(f(x) = \cos(2x) + \frac{1}{x+1}\), отрезок \([0, \pi]\)
  8. \(f(x) = x \cdot \ln(0.5x + 1)\), отрезок \([0, 5]\)
  9. \(f(x) = 3x^3 - 2x^2 + 4x - 1\), отрезок \([0, 1]\)
  10. \(f(x) = \frac{1}{2}x^2 - 2x + 4\), отрезок \([0, 5]\)
  11. \(f(x) = e^{-0.5x} + \cos(x)\), отрезок \([0, \pi]\)
  12. \(f(x) = \frac{1}{x^2} + 2x + 1\), отрезок \([0.5, 3]\)
  13. \(f(x) = \tan(0.5x) + x^2\), отрезок \([0, 1]\)
  14. \(f(x) = \frac{1}{x} + \sqrt{2x}\), отрезок \([0.5, 3]\)
  15. \(f(x) = \sinh(0.5x) + 0.5x\), отрезок \([0, 2]\), где \(\sinh(x)=\frac{e^x-e^{-x}}{2}\)
Наверх
Лаб. работа “Итераторы в Python”
Лаб. работа “Методы многомерной оптимизации”