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

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

Пусть дано уравнение f(x) = 0, причем функция f(x) непрерывна на отрезке [a; b] и f(a) * f(b) < 0 (рис. 1). Для вычисления корня уравнения
f(x) = 0, принадлежащего отрезку [a; b], найдем середину этого отрезка . Если f(x₁) ≠ 0, то для продолжения вычислений выберем ту из частей данного отрезка [a, x₁] или [x₁,b], на концах которой функция f(x) имеет противоположны знаки. Концы нового отрезка обозначим через a₁ и b_1.

Рис. 1. График метода половинного деления

Новый суженный промежуток [a₁; b₁] снова делим пополам и проводим вычисления по разобранной схеме. В результате получаем либо точный корень уравнения f(x) = 0 на каком-то этапе, либо последовательность вложенных отрезков [a; b], [a₁; b₁], …[a_n; b_n], таких, что f(a) * f(b) < 0 (при n = 1, 2, …), а [1, с.37-38].

Погрешность метода половинного деления определяется достаточно очевидным соотношением (которое, впрочем, может быть строго доказано)

,

которое указывает на скорость сходимости метода: с увеличением k погрешность стремится к нулю не медленнее геометрической прогрессии со знаменателем q = 1/2 [2, с.33-34].

Рассмотрим свойства дихотомии. Положительные:

а) идейная простота метода;

б) непритязательность к свойствам функции f(x): она должна быть лишь непрерывной, а дифференцируемость не предполагается.

К сожалению, отрицательные свойства перевешивают:

в) очень медленная сходимость;

г) неприменимость к вычислению корней четной кратности;

д) неприменимость к решению систем уравнений [3, c.51].

Перед началом программной реализации нахождения решений для уравнений f(x) = 0 на языке программирования необходимо иметь блок-схему для того, чтобы наглядно увидеть необходимые этапы при написании кода. Готовая схема включает в себя переменные a, b – концы отрезка [a; b], содержащего корень уравнения и e – заданную точность вычисления корня. (рис. 2)

Рис. 2. Блок-схема программы для решений уравнений вида f(x)=0

На основе блок-схемы для программного решения уравнений вида f(x) = 0 методом половинного деления был разработан алгоритм, написанный на языке программирования C++, с целью обеспечения эффективного и точного вычисления данного метода. Вычисления в программе были разделены на несколько ключевых этапов. Вся программная реализация кода производилась в интегрированной среде разработки программного обеспечения – Microsoft Visual Studio.

На первом этапе программы (рис. 3) выполняется реализация начальной части алгоритма для поиска корня уравнения f(x) = 0 методом половинного деления. Код включает в себя объявление заголовочных файлов (для работы с вводом/выводом, форматирования результата и работы математических функций) и объявление двух глобальных переменных с плавающей точкой. Далее следует реализация функции, в которой задается вид уравнения, корень которого требуется найти, и функции output_of_result(), в которой выводится значение найденного приближения корня уравнения и значение погрешности приближения с точностью до 7 знаков после запятой, т. е. данная функция выполняет форматированный вывод полученных результатов численного решения уравнения методом половинного деления, включая приближенное значение корня и достигнутую погрешность.

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

Следующий этап представляет собой написание основного кода программы, в котором будут происходить непосредственно вычисления уравнения f(x) = 0 (рис. 4). Сначала объявляются переменные типа float для хранения границ интервала a и b, требуемой точности e, переменные f_a и f₁, а также счетчик step. Далее пользователю предлагается ввести через пробел границы отрезка и точность вычисления корня. Введенные значения считываются с использованием оператора cin. Затем выполняется проверка условия f(a) * f(b) > 0. Если знаки функции на концах отрезка совпадают, то произведение f(a) * f(b) будет положительным, что означает отсутствие гарантированного корня на этом интервале. В этом случае выводится сообщение об отсутствии решения и выполнение программы завершается выводом функцией return 1.

Рис. 4. Основной код программы: ввод числовых значений переменных и их проверка

После проверки условия на наличие корня на заданном интервале идет цикл (рис. 5), в котором вычисляется значение x₁ – середина текущего интервала по формуле , вычисляется значение функции f(x) в точке x₁, т. е. f₁ = f(x₁), и значение функции в точке a, которое присваивается переменной f_a. После этого производится проверка условия f_a * f₁ < 0. Если произведение отрицательно, то это означает, что корень лежит в левой половине интервала [a, x₁], и правая граница интервала b обновляется значением x₁. В противном случае корень лежит в правой половине интервала [x₁, b], и левая граница интервала a обновляется значением x₁. Вычисляется длина текущего интервала [a, b] и присваивается переменной d.

После счетчик итераций step увеличивается на 1. Выводится номер текущей итерации, приближенное значение корня x₁ и длина текущего интервала d. Вывод осуществляется с использованием fixed и setprecision() для обеспечения фиксированного формата и точности представления чисел с плавающей точкой.

Проверяется, не является ли текущее значение f₁ нулем. Если f₁ равно нулю, это означает, что точный корень найден, переменной d присваивается значение 0, программа завершается.

Рис. 5. Основной код программы: процесс вычисления

Цикл do-while продолжает выполняться до тех пор, пока длина интервала d больше или равна заданной точности e. После завершения цикла вызывается функция для вывода полученного приближенного значения корня, и программа завершается.

В результате запуска программы в консоли отладки код выводит результат, представленный ниже (рис. 7). В целях наглядной демонстрации работоспособности и корректности разработанного алгоритма, в качестве примера было использовано уравнение f(x) = 4 - e^x - 2x² = 0 (x > 0). Методом половинного деления с точностью e = 10^-2 необходимо найти корень данного уравнения, при этом искомый корень принадлежит отрезку [0; 1].

Рис. 7. Консольотладки Microsoft Visual Studio

Представленный в работе алгоритм не ограничивается исключительно уравнением f(x) = 4 - e^x - 2x² = 0. Данная программа разработана с целью обеспечения универсальности и применимости к широкому классу уравнений вида f(x) = 0. Алгоритм требует лишь наличия начального интервала [a; b]. Это условие является достаточным для запуска и корректной работы алгоритма, вне зависимости от конкретного вида функции f(x).

В результате в рамках данной работы был разработан и проанализирован алгоритм метода половинного деления для численного решения уравнений вида f(x) = 0. Теоретический анализ показал, что метод отличается надежностью сходимости при условии непрерывности функции и наличия корня на заданном интервале, однако характеризуется сравнительно медленной скоростью сходимости и неприменимостью для нахождения корней четной кратности.

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

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

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

1. Практическое руководство по методам вычислений с приложением программ для персональных компьютеров : учеб. пособие / В. И. Ракитин, В. Е. Первушин. – Москва : Высш. шк., 1998. – 383 с. : ил. – ISBN 5-06-003342-2.

2. Численные методы : учебник и практикум для вузов / У. Г. Пирумов [и др.] ; под редакцией У. Г. Пирумова. — 5-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2023. — 421 с. — (Высшее образование). — ISBN 978-5-534-03141-6. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/510769/ (дата обращения: 15.01.2025).

3. Численные методы : учебное пособие для среднего профессионального образования / А. В. Зенков. — 2-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2024. — 136 с. — (Профессиональное образование). — ISBN 978-5-534-16731-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/538502/ (дата обращения: 15.01.2025).