{"id":625,"date":"2020-09-16T22:30:51","date_gmt":"2020-09-17T05:30:51","guid":{"rendered":"http:\/\/gantovnik.com\/bio-tips\/?p=625"},"modified":"2020-09-16T22:30:51","modified_gmt":"2020-09-17T05:30:51","slug":"97-finding-roots-on-an-interval-with-the-bisection-method","status":"publish","type":"post","link":"https:\/\/gantovnik.com\/bio-tips\/2020\/09\/97-finding-roots-on-an-interval-with-the-bisection-method\/","title":{"rendered":"#97 Finding roots on an interval with the bisection method."},"content":{"rendered":"<p>#97 Finding roots on an interval with the bisection method.<\/p>\n<p>One of the simplest algorithms for solving equations of the form f(x)=0 is called the bisection method. <\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\nfrom math import exp\r\ndef bisection(f,a,b,tol= 1e-3):\r\n    if f(a)*f(b) &gt; 0:\r\n        print(f'No roots or more than one root in &#x5B;{a},{b}]')\r\n        return\r\n    m = (a+b)\/2\r\n\r\n    while abs(f(m)) &gt; tol:\r\n        if f(a)*f(m) &lt; 0:\r\n            b = m\r\n        else:\r\n            a = m\r\n        m = (a+b)\/2\r\n    return m\r\n\r\n#call the method for f(x)= x**2-4*x+exp(-x)\r\nf = lambda x: x**2-4*x+exp(-x)\r\nsol = bisection(f,-0.5,1,1e-6)\r\nprint(f'x = {sol:g} is an approximate root, f({sol:g}) = {f(sol):g}')\r\n<\/pre>\n<p>Output:<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\nx = 0.213348 is an approximate root, f(0.213348) = -3.41372e-07\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>#97 Finding roots on an interval with the bisection method. One of the simplest algorithms for solving equations of the form f(x)=0 is called the bisection method. from math import exp def bisection(f,a,b,tol= 1e-3): if f(a)*f(b) &gt; 0: print(f&#8217;No roots or more than one root in &#x5B;{a},{b}]&#8217;) return m = (a+b)\/2 while abs(f(m)) &gt; tol: [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","_lmt_disableupdate":"yes","_lmt_disable":"","jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-625","post","type-post","status-publish","format-standard","hentry","category-python"],"modified_by":"gantovnik","jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p8bH0k-a5","jetpack_likes_enabled":true,"jetpack-related-posts":[{"id":96,"url":"https:\/\/gantovnik.com\/bio-tips\/2018\/12\/bisection-method\/","url_meta":{"origin":625,"position":0},"title":"#16 Bisection method using python","author":"gantovnik","date":"2018-12-31","format":false,"excerpt":"[code language=\"python\"] import os import matplotlib.pyplot as plt import numpy as np os.chdir('\/home\/vg\/Downloads\/projects\/ex16') os.getcwd() f = lambda x: np.exp(x)-2 tol=0.1 a,b=-2,2 x=np.linspace(-2.1,2.1,1000) fig,ax=plt.subplots(1,1,figsize=(12,4)) ax.plot(x,f(x),lw=1.5) ax.axhline(0,ls=':',color='k') ax.set_xticks([-2,-1,0,1,2]) ax.set_xlabel(r'$x$',fontsize=18) ax.set_ylabel(r'$f(x)$',fontsize=18) fa,fb=f(a),f(b) ax.plot(a,fa,'ko') ax.plot(b,fb,'ko') ax.text(a,fa+0.5,r\"$a$\",ha='center',fontsize=18) ax.text(b,fb+0.5,r\"$b$\",ha='center',fontsize=18) n=1 while b-a &gt; tol: m=a+(b-a)\/2 fm=f(m) ax.plot(m,fm,'ko') ax.text(m,fm-0.5,r\"$m_%d$\" % n,ha='center') n=n+1 if (np.sign(fa)==np.sign(fm)): a,fa=m,fm else: b,fb=m,fm\u2026","rel":"","context":"In &quot;optimization&quot;","block_context":{"text":"optimization","link":"https:\/\/gantovnik.com\/bio-tips\/category\/optimization\/"},"img":{"alt_text":"example16","src":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2018\/12\/example16.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2018\/12\/example16.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2018\/12\/example16.png?resize=525%2C300 1.5x"},"classes":[]},{"id":1758,"url":"https:\/\/gantovnik.com\/bio-tips\/2023\/01\/335-solution-of-nonlinear-equation-using-brent-method-in-python\/","url_meta":{"origin":625,"position":1},"title":"#335 Solution of nonlinear equation by Brent&#8217;s method in python","author":"gantovnik","date":"2023-01-06","format":false,"excerpt":"Brent's method is a hybrid root-finding algorithm combining the bisection method, the secant method, and inverse quadratic interpolation. ex335.py [code language=\"python\"] import numpy as np import matplotlib.pyplot as plt import scipy.optimize as optimize def f(x): return 2*x - 1 + 2*np.cos(np.pi*x) x = np.linspace(0.0,2.0,201) y=f(x) plt.plot(x,y,label='$2x - 1 + 2\\\\cos(\\\\pi\u2026","rel":"","context":"In &quot;optimization&quot;","block_context":{"text":"optimization","link":"https:\/\/gantovnik.com\/bio-tips\/category\/optimization\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2023\/01\/ex335.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2634,"url":"https:\/\/gantovnik.com\/bio-tips\/2024\/07\/436-non-convex-univariate-function-optimization-using-brents-method-in-python\/","url_meta":{"origin":625,"position":2},"title":"#436 Non-convex univariate function optimization using Brent&#8217;s method in python","author":"gantovnik","date":"2024-07-18","format":false,"excerpt":"Brent\u2019s method is an optimization algorithm that combines a bisecting algorithm (Dekker\u2019s method) and inverse quadratic interpolation. It can be used for constrained and unconstrained univariate function optimization. The Brent-Dekker method is an extension of the bisection method. It is a root-finding algorithm that combines elements of the secant method\u2026","rel":"","context":"In &quot;optimization&quot;","block_context":{"text":"optimization","link":"https:\/\/gantovnik.com\/bio-tips\/category\/optimization\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2024\/07\/ex436.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2024\/07\/ex436.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2024\/07\/ex436.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":1742,"url":"https:\/\/gantovnik.com\/bio-tips\/2023\/01\/204-mandelbrot-fractal-using-python-2-2-2-2-2-2-2-2-2\/","url_meta":{"origin":625,"position":3},"title":"#330 Gradient method using python","author":"gantovnik","date":"2023-01-03","format":false,"excerpt":"golden.py [code language=\"python\"] import math as mt def golden(f,a,b,tol=1.0e-10): # Golden section method for determining x # that minimizes the scalar function f(x). # The minimum must be bracketed in (a,b). c1 = (mt.sqrt(5.0)-1.0)\/2.0 c2 = 1.0 - c1 nIt = int(mt.ceil(mt.log(tol\/abs(a-b))\/mt.log(c1))) # first step x1 = c1*a + c2*b\u2026","rel":"","context":"In &quot;optimization&quot;","block_context":{"text":"optimization","link":"https:\/\/gantovnik.com\/bio-tips\/category\/optimization\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2023\/01\/ex330.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":1738,"url":"https:\/\/gantovnik.com\/bio-tips\/2023\/01\/204-mandelbrot-fractal-using-python-2-2-2-2-2-2-2-2\/","url_meta":{"origin":625,"position":4},"title":"#329 Golden section method using python","author":"gantovnik","date":"2023-01-03","format":false,"excerpt":"golden.py [code language=\"python\"] import math as mt def golden(f,a,b,tol=1.0e-10): # Golden section method for determining x # that minimizes the scalar function f(x). # The minimum must be bracketed in (a,b). c1 = (mt.sqrt(5.0)-1.0)\/2.0 c2 = 1.0 - c1 nIt = int(mt.ceil(mt.log(tol\/abs(a-b))\/mt.log(c1))) # first step x1 = c1*a + c2*b\u2026","rel":"","context":"In &quot;optimization&quot;","block_context":{"text":"optimization","link":"https:\/\/gantovnik.com\/bio-tips\/category\/optimization\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2023\/01\/ex329.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":101,"url":"https:\/\/gantovnik.com\/bio-tips\/2018\/12\/solution-of-system-of-nonlinear-equations\/","url_meta":{"origin":625,"position":5},"title":"Solution of system of nonlinear equations","author":"gantovnik","date":"2018-12-31","format":false,"excerpt":"import os import matplotlib.pyplot as plt import numpy as np import scipy os.chdir('\/home\/vg\/Downloads\/projects\/ex17') os.getcwd() def f(x): return [x[1]-x[0]**3-2*x[0]**2+1,x[1]+x[0]**2-1] tol=0.1 a,b=-2,2 x=np.linspace(-3,2,5000) y1=x**3+2*x**2-1 y2=-x**2+1 fig,ax=plt.subplots(figsize=(8,4)) ax.plot(x,y1,'k',lw=1.5) ax.plot(x,y2,'k',lw=1.5) sol1=scipy.optimize.fsolve(f,[-2,2]) sol2=scipy.optimize.fsolve(f,[1,-1]) sol3=scipy.optimize.fsolve(f,[-2,-5]) sols=[sol1,sol2,sol3] colors=['r','b','g'] for idx,s in enumerate(sols): ax.plot(s[0],s[1],colors[idx]+'*',markersize=15) for m in np.linspace(-4,3,80): for n in np.linspace(-20,20,40): x_guess=[m,n] sol=scipy.optimize.fsolve(f,x_guess) idx = (abs(sols-sol)**2).sum(axis=1).argmin() ax.plot(x_guess[0],x_guess[1],colors[idx]+'.')\u2026","rel":"","context":"In &quot;python&quot;","block_context":{"text":"python","link":"https:\/\/gantovnik.com\/bio-tips\/category\/python\/"},"img":{"alt_text":"example17","src":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2018\/12\/example17.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2018\/12\/example17.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/gantovnik.com\/bio-tips\/wp-content\/uploads\/2018\/12\/example17.png?resize=525%2C300 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/posts\/625","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/comments?post=625"}],"version-history":[{"count":0,"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/posts\/625\/revisions"}],"wp:attachment":[{"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/media?parent=625"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/categories?post=625"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/gantovnik.com\/bio-tips\/wp-json\/wp\/v2\/tags?post=625"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}