Метод половинного деления (он же метод бисекции, дихотомии) — это итеративный численный метод для приближенного нахождения корня непрерывной функции на заданном интервале. Он основан на последовательном делении интервала пополам и выборе той половины, на концах которой функция сохраняет противоположные знаки, что гарантирует наличие корня в этом интервале. Процесс продолжается до тех пор, пока длина интервала не станет меньше заданной точности, обеспечивая сходимость к корню.
Пусть дано уравнение f(x) = 0, причем функция f(x) непрерывна на отрезке [a; b] и f(a) * f(b) < 0 (рис. 1). Для вычисления корня уравнения
f(x) = 0, принадлежащего отрезку [a; b], найдем середину этого отрезка . Если f(x1) ≠ 0, то для продолжения вычислений выберем ту из частей данного отрезка [a, x1] или [x1,b], на концах которой функция f(x) имеет противоположны знаки. Концы нового отрезка обозначим через a1 и b1.
Рис. 1. График метода половинного деления
Новый суженный промежуток [a1; b1] снова делим пополам и проводим вычисления по разобранной схеме. В результате получаем либо точный корень уравнения f(x) = 0 на каком-то этапе, либо последовательность вложенных отрезков [a; b], [a1; b1], …[an; bn], таких, что 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, переменные fa и f1, а также счетчик step. Далее пользователю предлагается ввести через пробел границы отрезка и точность вычисления корня. Введенные значения считываются с использованием оператора cin. Затем выполняется проверка условия f(a) * f(b) > 0. Если знаки функции на концах отрезка совпадают, то произведение f(a) * f(b) будет положительным, что означает отсутствие гарантированного корня на этом интервале. В этом случае выводится сообщение об отсутствии решения и выполнение программы завершается выводом функцией return 1.
Рис. 4. Основной код программы: ввод числовых значений переменных и их проверка
После проверки условия на наличие корня на заданном интервале идет цикл (рис. 5), в котором вычисляется значение x1 – середина текущего интервала по формуле , вычисляется значение функции f(x) в точке x1, т. е. f1 = f(x1), и значение функции в точке a, которое присваивается переменной fa. После этого производится проверка условия fa * f1 < 0. Если произведение отрицательно, то это означает, что корень лежит в левой половине интервала [a, x1], и правая граница интервала b обновляется значением x1. В противном случае корень лежит в правой половине интервала [x1, b], и левая граница интервала a обновляется значением x1. Вычисляется длина текущего интервала [a, b] и присваивается переменной d.
После счетчик итераций step увеличивается на 1. Выводится номер текущей итерации, приближенное значение корня x1 и длина текущего интервала d. Вывод осуществляется с использованием fixed и setprecision() для обеспечения фиксированного формата и точности представления чисел с плавающей точкой.
Проверяется, не является ли текущее значение f1 нулем. Если f1 равно нулю, это означает, что точный корень найден, переменной d присваивается значение 0, программа завершается.
Рис. 5. Основной код программы: процесс вычисления
Цикл do-while продолжает выполняться до тех пор, пока длина интервала d больше или равна заданной точности e. После завершения цикла вызывается функция для вывода полученного приближенного значения корня, и программа завершается.
В результате запуска программы в консоли отладки код выводит результат, представленный ниже (рис. 7). В целях наглядной демонстрации работоспособности и корректности разработанного алгоритма, в качестве примера было использовано уравнение f(x) = 4 - ex - 2x2 = 0 (x > 0). Методом половинного деления с точностью e = 10-2 необходимо найти корень данного уравнения, при этом искомый корень принадлежит отрезку [0; 1].
Рис. 7. Консольотладки Microsoft Visual Studio
Представленный в работе алгоритм не ограничивается исключительно уравнением f(x) = 4 - ex - 2x2 = 0. Данная программа разработана с целью обеспечения универсальности и применимости к широкому классу уравнений вида f(x) = 0. Алгоритм требует лишь наличия начального интервала [a; b]. Это условие является достаточным для запуска и корректной работы алгоритма, вне зависимости от конкретного вида функции f(x).
В результате в рамках данной работы был разработан и проанализирован алгоритм метода половинного деления для численного решения уравнений вида f(x) = 0. Теоретический анализ показал, что метод отличается надежностью сходимости при условии непрерывности функции и наличия корня на заданном интервале, однако характеризуется сравнительно медленной скоростью сходимости и неприменимостью для нахождения корней четной кратности.
Результатом практической части работы стала программная реализация алгоритма на языке C++ с использованием интегрированной среды разработки Microsoft Visual Studio. Разработанный алгоритм включает в себя инициализацию переменных, проверку условий для наличия корня, итерационное сужение интервала, проверку условия сходимости и форматированный вывод полученного приближения корня и достигнутой погрешности.
Таким образом, данная статья представляет собой комплексное исследование метода половинного деления, включающее в себя теоретический анализ, разработку алгоритма, его программную реализацию и тестирование. Полученные результаты могут служить основой для дальнейшего изучения и применения метода бисекции в более сложных вычислительных задачах, а также для разработки более эффективных методов численного решения нелинейных уравнений. Представленный программный код может быть использован как основа для дальнейшей модификации и интеграции в более сложные вычислительные проекты.
Список литературы
Практическое руководство по методам вычислений с приложением программ для персональных компьютеров : учеб. пособие / В. И. Ракитин, В. Е. Первушин. – Москва : Высш. шк., 1998. – 383 с. : ил. – ISBN 5-06-003342-2.
Численные методы : учебник и практикум для вузов / У. Г. Пирумов [и др.] ; под редакцией У. Г. Пирумова. — 5-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2023. — 421 с. — (Высшее образование). — ISBN 978-5-534-03141-6. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/510769/ (дата обращения: 15.01.2025).
Численные методы : учебное пособие для среднего профессионального образования / А. В. Зенков. — 2-е изд., перераб. и доп. — Москва : Издательство Юрайт, 2024. — 136 с. — (Профессиональное образование). — ISBN 978-5-534-16731-3. — Текст : электронный // Образовательная платформа Юрайт [сайт]. — URL: https://urait.ru/bcode/538502/ (дата обращения: 15.01.2025).