Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Поиск корней уравнения методом перебора и методом деления пополам на Python
Общие положения
Вообще уравнения типа f(x)=0 довольно типичное. При линейном уравнении, уравнениях второй и третьей степени решение можно выразить аналитически, а вот дальше уже не факт. Может удастся решить аналитически, а может нет. Чаще всего нет. Кроме того, функция ведь не обязательно должна выражаться многочленом. Соответственно получаем хорошую задачу для программистов, со склонностью к математике.
Первое, что хотелось бы заметить, численный поиск корня (корней) уравнения вида f(x)=0 производится на промежутке, а не вообще. Да, промежуток можно сделать очень большим, но всё равно он будет конечным.
Второй момент. Основная идея того, что нам попался корень на промежутке, это изменения знака функции на концах. Т.е., грубо говоря, график функции пересек ось 0X, т.е. прошёл через ноль. Разумеется, мы должны понимать, что критерий неоднозначный, так как функция может пройти через ноль чётное количество раз и тогда критерий не сработает. Честно вам скажу, у меня нет ответа, как справится с этой проблемой численно, кроме того, чтобы уменьшать размеры промежутка. Разумеется, есть ещё аналитический подход и есть математические системы, способные его проводить, но этого мы здесь не касаемся. И так критерий понятен, за работу, товарищи.
Метод перебора
Метод перебора строится на простом принципе. Будем двигаться по промежутку с некоторым шагом, вычисляя значение функции в каждой точке. Как только знак функции измениться это и будет признаком того, что мы напали на корень. При этом будем считать значением корня середину между двумя найденными точками. Заведомо полагаем, что шаг прохода на столько мал, что между двумя соседними точками может быть только по одному пересечению оси 0X.
Заметим, что метод перебора позволяет найти все корни (с оговорками выше). С другой стороны метод же перебора позволяет найти все промежутки с одним корнем и можно к таким промежуткам применить другие методы определения корней. В этом смысле метод перебора универсален.
Ниже программа присматривает заданный промежуток в поисках корней уравнения (sin(x)).
Результат выполнения программы
4.999998083753952e-06
3.1415950000101973
6.283184999929385
9.424774999810452
Если посмотреть на результаты, то они вполне удовлетворительны. Для этого достаточно сравнить math.pi и полученный результат.
В программе ниже функция get_ends() выдаёт список "подозрительный" промежутков, т.е. промежутков, на которых вероятно есть по одному корню. Результат выполнения функции можно использовать для поиска корней другими методами.
Результата выполнения программы
(-1.916246048422115e-12, 9.999998083753952e-06) (3.1415900000101975, 3.1416000000101976) (6.283179999929385, 6.283189999929385) (9.424769999810453, 9.424779999810452) (12.566369999691519, 12.566379999691518) (15.707959999572585, 15.707969999572585) (18.849549999453654, 18.849559999453653)
Т.е. мы получили материал для дальнейшего более точного поиска корней на указанных промежутках.
Метод деления пополам
Метод деления пополам (половинного деления), в действительности нам уже знаком. Это тот самый двоичный поиск.
Программа ниже осуществляет поиск корня уравнения по данному алгоритму.
Результат выполнения программы
3.141592407226563
3.141592653589793
Нижнее значение соответствует math.pi. В программе также предусмотрена ситуация, когда корней нет или, возможно, их чётное число в двух половинках промежутка.
Метод как видим не плохой. И, как мы уже сказали, его можно использовать совместно с последовательным поиском. В начале ищем все промежутки, где есть корень, а потом применяем к каждому промежутку метод половинного деления.
Замечание
Читатель, надеюсь, понимает, уравнение типа f1(x)=f2(x) легко сводится к решению уравнения f1(x)-f2(x)=0, т.е. как раз к уравнению, которое мы и рассматривали в статье.
Ну, пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.