Computer Science\/Numerical Methods\/ Bisection method ( With complete introduction)<\/p>\n
[fvplayer id=”107″]<\/p>\n
The Bisection Method<\/strong> is a numerical technique used to find the roots of a function f(x) = 0<\/strong> in a given interval [a, b]<\/strong>. It is based on the Intermediate Value Theorem (IVT)<\/strong>, which states that:<\/p>\n If a continuous function f(x) changes sign between two points a and b (i.e., f(a) * f(b) < 0), then there exists at least one root in the interval [a, b].<\/em><\/p>\n<\/blockquote>\n Choose an interval [a, b]<\/strong> such that f(a) * f(b) < 0<\/strong> (i.e., f(x) changes sign). c=a+b2c = \\frac{a + b}{2}<\/span>c<\/span>=<\/span><\/span>2a<\/span>+<\/span>b<\/span><\/span>\u200b<\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/span><\/p>\n Check the function value at c:<\/strong><\/p>\n Find the root of f(x) = x\u00b3 – 4x – 9<\/strong> using the bisection method in the interval [2, 3]<\/strong>.<\/p>\n Step 1: Check the function values at endpoints<\/strong><\/p>\n f(2)=(2)3\u22124(2)\u22129=8\u22128\u22129=\u22129f(2) = (2)^3 – 4(2) – 9 = 8 – 8 – 9 = -9<\/span>f<\/span>(<\/span>2<\/span>)<\/span>=<\/span><\/span>(<\/span>2<\/span>)3<\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>4<\/span>(<\/span>2<\/span>)<\/span>\u2212<\/span><\/span>9<\/span>=<\/span><\/span>8<\/span>\u2212<\/span><\/span>8<\/span>\u2212<\/span><\/span>9<\/span>=<\/span><\/span>\u2212<\/span>9<\/span><\/span><\/span><\/span><\/span> f(3)=(3)3\u22124(3)\u22129=27\u221212\u22129=6f(3) = (3)^3 – 4(3) – 9 = 27 – 12 – 9 = 6<\/span>f<\/span>(<\/span>3<\/span>)<\/span>=<\/span><\/span>(<\/span>3<\/span>)3<\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>4<\/span>(<\/span>3<\/span>)<\/span>\u2212<\/span><\/span>9<\/span>=<\/span><\/span>27<\/span>\u2212<\/span><\/span>12<\/span>\u2212<\/span><\/span>9<\/span>=<\/span><\/span>6<\/span><\/span><\/span><\/span><\/span><\/p>\n Since f(2) * f(3) < 0<\/strong>, a root exists in [2, 3]<\/strong>.<\/p>\n Step 2: Compute Midpoint<\/strong><\/p>\n c=2+32=2.5c = \\frac{2 + 3}{2} = 2.5<\/span>c<\/span>=<\/span><\/span>22+<\/span>3<\/span>\u200b<\/span><\/span><\/span><\/span><\/span>=<\/span><\/span>2.5<\/span><\/span><\/span><\/span><\/span> f(2.5)=(2.5)3\u22124(2.5)\u22129=15.625\u221210\u22129=\u22123.375f(2.5) = (2.5)^3 – 4(2.5) – 9 = 15.625 – 10 – 9 = -3.375<\/span>f<\/span>(<\/span>2.5<\/span>)<\/span>=<\/span><\/span>(<\/span>2.5<\/span>)3<\/span><\/span><\/span><\/span><\/span><\/span><\/span>\u2212<\/span><\/span>4<\/span>(<\/span>2.5<\/span>)<\/span>\u2212<\/span><\/span>9<\/span>=<\/span><\/span>15.625<\/span>\u2212<\/span><\/span>10<\/span>\u2212<\/span><\/span>9<\/span>=<\/span><\/span>\u2212<\/span>3.375<\/span><\/span><\/span><\/span><\/span><\/p>\n Since f(2) * f(2.5) < 0<\/strong>, update b = 2.5<\/strong>.<\/p>\n Step 3: Repeat until required accuracy is achieved<\/strong> Always Convergent<\/strong> (as long as f(a) * f(b) < 0). Slow Convergence<\/strong> (linear order).\n
\u00a0Steps to Apply the Bisection Method<\/strong><\/h4>\n
Find the midpoint (c):<\/strong><\/p>\n\n
Repeat steps 2 & 3 until<\/strong> the root is found with the required accuracy (\u03b5 tolerance level)<\/strong>.<\/li>\n<\/ul>\n\u00a0Example Problem<\/strong><\/h4>\n
Continuing this process, we get a refined root x \u2248 2.75<\/strong> after multiple iterations.<\/p>\n\u00a0Advantages of the Bisection Method<\/strong><\/h4>\n
Simple and easy to implement<\/strong>.
Works for any continuous function<\/strong>.<\/p>\n\u00a0Limitations of the Bisection Method<\/strong><\/h4>\n
Cannot find multiple roots in the same interval<\/strong>.
Requires initial interval selection<\/strong> where sign change occurs.<\/p>\n\u00a0Python Code Implementation<\/strong><\/h4>\n
def<\/span> f<\/span>(x<\/span>):
\nreturn<\/span> x**3<\/span> - 4<\/span>*x - 9<\/span><\/code><\/code>def<\/span> bisection<\/span>(a, b, tol<\/span>):
\nif<\/span> f(a) * f(b) >= 0<\/span>:
\nprint<\/span>(“Invalid interval, no sign change detected.”<\/span>)
\nreturn<\/span> None<\/span><\/p>\n<\/code><\/code>while<\/span> (b – a) \/ 2.0<\/span> > tol:
\nc = (a + b) \/ 2.0<\/span>
\nif<\/span> f(c) ==