Метод деления отрезка пополам python

Метод половинного деления на Python

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

Алгоритм метода половинного деления (дихотомии)

Процесс решения начинается с выбора отрезка [a, b], содержащего корень уравнения. Затем находим среднюю точку m = (a + b) / 2 и вычисляем значение функции f(m). Если f(m) равно нулю или достаточно близко к нулю, то мы заканчиваем процесс и возвращаем значение m как приближенный корень уравнения. Если f(m) имеет тот же знак, что и f(a), то корень находится в отрезке [m, b], и мы заменяем a на m. Если же f(m) имеет тот же знак, что и f(b), то корень находится в отрезке [a, m], и мы заменяем b на m. Метод продолжается до тех пор, пока не будет достигнута требуемая точность.

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

Пошагово напишем код для метода половинного деления

• Определяется функция half_interval_method(a, b, tol=0.001, max_iters=100) , которая реализует метод половинного деления. Она принимает начальный интервал [a, b], точность результата tol и максимальное количество итераций max_iters .

def half_interval_method(a, b, tol=0.001, max_iters=100):

• Если f(c) = 0 или длина интервала (b — a) / 2 меньше заданной точности tol , то возвращаем c – найденный корень.

• Иначе, увеличиваем счетчик итераций i на 1 и проверяем, на каком конце интервала f имеет такой же знак, как и f(c) . Если f(c) * f(a) > 0 , то корень находится в правой половине интервала [c, b], и мы обновляем значение a = c . В противном случае, корень находится в левой половине интервала [a, c], и мы обновляем значение b = c .

i += 1 if f(c) * f(a) > 0: a = c else: b = c

Метод половинного деления, полный код

def f(x): """ Функция, которую нужно решить Замените эту функцию своей собственной """ return x**3 - 4*x - 9 def half_interval_method(a, b, tol=0.001, max_iters=100): """ Метод половинного деления для решения уравнения f(x) = 0 a: левый конец начального интервала b: правый конец начального интервала tol: точность результата max_iters: максимальное количество итераций """ i = 0 while i < max_iters: c = (a + b) / 2 if f(c) == 0 or (b - a) / 2 < tol: return c i += 1 if f(c) * f(a) >0: a = c else: b = c return None # Пример использования a = -10 b = 10 root = half_interval_method(a, b) if root: print(f"Корень уравнения: ") else: print("Не удалось найти корень уравнения")

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

Результат же выполнения моей функции с заданным ей уравнением равен:

Источник

Методом деления пополам вычислить единственный корень на заданном отрезке

Задано уравнение f(x)=0. Методом деления пополам вычислить единственный корень на заданном отрезке [a,b] с точностью е=0,00001.

Вычислить корень уравнения на отрезке методом деления отрезка пополам
Дана функция f(x)=2×2-5x+1. Вычислить корень уравнения f(x)=0 на отрезке (1,3) методом деления.

Методом деления отрезка пополам найти корень уравнения 2^x+5x-3=0 на отрезке [0;10]
Методом деления отрезка пополам найти корень уравнения 2^x+5x-3=0 на отрезке .

Найти корень уравнения на отрезке методом деления отрезка пополам
написать рекурсивную функцию Root(f,b,e),которая методом деления отрезка пополам находит с.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

from math import fabs def f( x ): return x*(x + 3) - 5 def dihotomia( a, b, eps ): ksi = ( a + b ) / 2.0 if ( fabs( f(a) - f(b) )  eps ) or ( fabs( f(ksi) )  eps ): return ( a + b ) / 2.0 if ( f( a )*f( ksi )  0.0 ): return dihotomia( a, ksi, eps ) else: return dihotomia( ksi, b, eps ) a = 0 b = 3 eps = 0.00001 print( dihotomia( a, b, eps ) );

1) Если функция такова, что f(a)==f(b) или даже f(a) != f(b) и они разных знаков, но модуль разности меньше eps, функция сразу вернет 0.5*(a+b).

2) На каждом витке рекурсии происходит 5 вычислений функции (хотя достаточно одного).

3) При выборе интервала смены знака используется умножение, что может вызвать переполнение. Ну, это мелочь.

Сообщение от Catstail

Если функция такова, что f(a)==f(b) или даже f(a) != f(b) и они разных знаков, но модуль разности меньше eps, функция сразу вернет 0.5*(a+b).

Функция «сразу вернет» решение, так как оно найдено

Сообщение от Catstail

Неужели, покажите код с одним вызовом функции

Сообщение от Catstail

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

Итого из трёх замечаний 2,5 верных, а так — все хорошо.

Сообщение было отмечено mik-a-el как решение

Решение

Сообщение от regio1961

— вот итерационная версия, в которой на каждый виток цикла приходится один вызов. Не проблема сделать и рекурсивную версию.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

from math import fabs def f(x): return x*(x+3)*(x-10) def sgn(x): if (x>0): return 1 elif (x0): return -1 else: return 0 def root(a,b,epsX,epsF): fa=f(a) # эти два вычисления fb=f(b) # делаются один раз до входа в цикл if sgn(fa)*sgn(fb)>0: # здесь переполнения не будет никогда return None # если функция не меняет знак while(True): c=0.5*(a+b) fc=f(c) # единственное вычисление в цикле if (fabs(fc)epsF) or (fabs(b-a)epsX): return c elif sgn(fa)*sgn(fc)0: b=c fb=fc else: a=c fa=fc a=0.0 b=5.0 r=root(a,b,1e-8,1e-14) print(r)

Источник

Реализации алгоритмов/Метод бисекции

В результате прогона программы на устройстве ввода-вывода должен получиться следующий вывод:

Value of function: -0.0000000027 Left bound equal: 1.1461932193 Middle of line segment: 1.1461932203 Right bound equal: 1.1461932212 Numbers of iterations equal: 30

На языке Matlab [ править ]

function [res, err] = bisection(fun, left, right, tol) if fun(left)*fun(right) > 0 error('Значения функции на концах интервала должны быть разных знаков'); end; %Деление отрезка пополам middle = 0.5*(left +right); %Итерационный цикл while abs(fun(middle)) > tol %Нахождение нового интервала left = left*(fun(left)*fun(middle)  0) + middle*(fun(left)*fun(middle) > 0); right = right*(fun(right)*fun(middle)  0) + middle*(fun(right)*fun(middle) > 0); %Деление нового интервала пополам middle = 0.5*(left +right); end res = middle; err = abs(fun(middle)); 

Пример работы алгоритма для поиска корня функции y = tan(x) на интервале [1; 2] с точностью 1e-3. Результат вполне ожидаемый:

[res, err] = bisection('tan', 1, 2, 1e-3) res = 1.5713 err = 9.7656e-004 

На языке Python [ править ]

import math func_glob = lambda x: 2 * x ** 3 - 3 * x ** 2 - 12 * x - 5 func_first = lambda x: 6 * x ** 2 - 6 * x - 12 a1, b1 = 0.0, 10.0 e = 0.001 def half_divide_method(a, b, f): x = (a + b) / 2 while math.fabs(f(x)) >= e: x = (a + b) / 2 a, b = (a, x) if f(a) * f(x)  0 else (x, b) return (a + b) / 2 def newtons_method(a, b, f, f1): x0 = (a + b) / 2 x1 = x0 - (f(x0) / f1(x0)) while True: if math.fabs(x1 - x0)  e: return x1 x0 = x1 x1 = x0 - (f(x0) / f1(x0)) import pylab import numpy X = numpy.arange(-2.0, 4.0, 0.1) pylab.plot([x for x in X], [func_glob(x) for x in X]) pylab.grid(True) #pylab.show() print ('root of the equation half_divide_method %s' % half_divide_method(a1, b1, func_glob)) print ('root of the equation newtons_method %s' % newtons_method(a1, b1, func_glob, func_first)) 

См. также [ править ]

Источник

Решение уравнений методом деления отрезка пополам

Уровень B. Составить две программы, одна из которых выделяет все интервалы, на которых находятся корни, а вторая запрашивает границы очередного интервала и выводит найден-ный корень уравнения, а также число шагов, которые потребовались для достижения задан-ной точности.
Пример:
Введите границы интервала:
1.5 2
Решение: 1.7201
Число шагов: 8

Возникли трудности при решении, выдает ошибку

Решение уравнения методом деления отрезка пополам
Найти корень уравнения 0.1(x^2)-x*ln(x) = 0 на отрезке с точностью e = 10^(-5) , используя метод.

Вычислите корень n-й степени методом деления отрезка пополам
Дано действительное число a и натуральное n. Вычислите корень n-й степени из числа Для решения.

Найти корень уравнения методом деления отрезка пополам
Найти какой-нибудь корень уравнения 2*cos(5+x)–3sin(2–x)=0 на отрезке с заданной точностью E =.

Рекурсивная программа, которая методом деления отрезка пополам находит с точностью EPS корень уравнения
Напишите рекурсивную программу, которая по заданным A, B и EPS методом деления отрезка пополам.

Метод деления отрезка пополам
Напишите функцию реализующую алгоритм поиска минимума функции методом деления отрезка пополам. С.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

from math import sin def fun(x): return sin(x)**2 - 1/2 def bound(xo, xn, dx): while xo  xn: if fun(xo) * fun(xo+dx)  0: yield xo, xo+dx xo += dx def bisec(left, right, eps, c=0): x = (left + right) / 2 if abs(right - left)  eps: return x, c elif fun(left) * fun(x)  0: return bisec(left, x, eps, c+1) else: return bisec(x, right, eps, c+1) a, b, dx, eps= -10, 10, 1, 1e-5 for x in bound(a,b,dx): xi, cnt = bisec(*x, eps) print(f' ')

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include #include using namespace std; double f(double x) { // здесь нужно вставить вашу функцию } int main() { double a, b; int n; double eps = 1e-6; cout  "Введите границы интервала: "; cin >> a >> b; double fa = f(a); double fb = f(b); if (fa * fb > 0) { cout  "На заданном интервале нет корней"  endl; return 0; } double c = (a + b) / 2; double fc = f(c); double prevC = c; while (abs(c - prevC) > eps) { if (fa * fc  0) { b = c; fb = fc; } else { a = c; fa = fc; } prevC = c; c = (a + b) / 2; fc = f(c); } cout  "Интервалы, на которых находятся корни: ["  a  ", "  b  "]"  endl; return 0; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include #include using namespace std; double f(double x) { // здесь нужно вставить вашу функцию } int main() { double a, b; int n; double eps = 1e-6; cout  "Введите границы интервала: "; cin >> a >> b; double fa = f(a); double fb = f(b); if (fa * fb > 0) { cout  "На заданном интервале нет корней"  endl; return 0; } double c = (a + b) / 2; double fc = f(c); double prevC = c; n = 0; while (abs(c - prevC) > eps) { if (fa * fc  0) { b = c; fb = fc; } else { a = c; fa = fc; } prevC = c; c = (a + b) / 2; fc = f(c); n++; } cout  "Решение: "  c  endl; cout  "Число шагов: "  n  endl; return 0; }

Источник