Bisection method with example.
The bisection method in mathematics is a root-finding method that repeatedly bisects an interval and then selects a sub-interval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods.
The bisection method, which is also called binary chopping, interval halving, or Bolzano’s method, is one type of incremental search method in which the interval is always divided in half. If a function changes sign over an interval, the function value at the midpoint is evaluated. The location of the root is then determined as lying at the midpoint of the subinterval within which the sign change occurs. The process is repeated to obtain refined estimates. Bisection method is always converges to two values.
Steps for solving Bisection method:
Step 1: Choose lower [latex s=1]f(x_l)[/latex] and upper [latex s=1]f(x_u)[/latex] guesses for the root such that the function changes sign over the interval. This can be checked by ensuring that
[latex s=2]f(x_l).f(x_u)<0[/latex]
Step 2: An estimate of the root [latex]f(x_u)[/latex] is determined by
[latex s=3]x_r = \frac{x_l + x_u}{2}[/latex]
Step 3: Make the following evaluations to determine in which sub-interval the root lies:
- If [latex s=1]f(x_l).f(x_r)<0[/latex] the root lies in the lower sub-interval. Therefore, set [latex s=1]x_u= x_r[/latex] and return to step 2.
- If [latex s=1]f(x_l).f(x_r)>0[/latex] the root lies in the upper sub-interval. Therefore, set [latex s=1]x_l= x_r[/latex] and return to step 2.
- If [latex s=1]f(x_l).f(x_r)=0[/latex] the root equals [latex s=1]x_r[/latex] terminate the computation.
Example:
Determine the real roots of [latex s=1]f(x) = -0.5x^2 + 2.4x + 4.5[/latex]:
Part a. Using the quadratic formula.
Part b. Using two iterations of the bisection method to determine the highest root. Employ initial guesses of [latex s=1]x_l= 5[/latex] and [latex s=1]x_u= 10[/latex].
Part c. Compute the estimated error [latex s=2]\epsilon_a[/latex] and the true error [latex s=2]\epsilon_t[/latex] after each iteration.
Solution:
Part a.
[latex s=3]x = \frac{{ – 2.4 \pm \sqrt {(2.4)^2 – 4(-0.5)(4.5)} }}{{2(-0.5)}}[/latex]
[latex s=2]x_1 = -1.441874, x_2 = 6.241874[/latex]
-*-*-*-*–*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
Part b.
[latex s=1]x_l=5[/latex] , [latex s=1]x_u=10[/latex]
First iteration:
Step 1:
[latex s=1]f(x) = -0.5x^2 + 2.4x + 4.5[/latex]
putting the [latex s=1]x_l=5 , x_u=10[/latex] one by one in above equation
[latex s=1]f(x_l) = -0.5(5)^2 + 2.4(5) + 4.5 = 4.5[/latex]
[latex s=1]f(x_u) = -0.5(10)^2 + 2.4(10) + 4.5 = -20.5[/latex]
[latex s=1]f(x_l).f(x_u) = (4.5)(-20.5) = -16<0[/latex]
[latex s=1][x_l , x_u]=[5 , 10][/latex]
brackets the root.
Step 2:
[latex s=3]x_r = \frac{x_l+x_u}{2}[/latex]
[latex s=3]x_r = \frac{5+10}{2}[/latex]
[latex s=2]x_r = 7.5[/latex]
Step 3:
[latex s=1]f(x_r) = f(7.5) = -0.5(7.5)^2 + 2.5(7.5) + 4.5 = -4.875[/latex]
[latex s=1]f(x_l).f(x_r) = (4.5)(-4.875) = -0.375 <0[/latex]
[latex s=2]x_u = x_r[/latex]
[latex s=2]x_u = 7.5[/latex]
updated intervals containing the root
[latex s=2][x_l , x_u][5 , 7.5][/latex]
Second iteration:
Step 1:
The updated interval is
[latex s=2][x_l , x_u][5 , 7.5][/latex]
Step 2:
[latex s=3]x_r = \frac{x_l+x_u}{2}[/latex]
[latex s=3]x_r = \frac{5+7.5}{2}[/latex]
[latex s=2]x_r = 6.25[/latex]
Step 3:
[latex s=1]f(x_r) = f(6.25) = -0.5(6.25)^2 + 2.5(6.25) + 4.5 = 0.59375[/latex]
[latex s=1]f(x_l)f(x_r)=(4.5)(0.59375)=2.671875>0[/latex]
so update the [latex s=2]x_l[/latex]
[latex s=2]x_l = x_r[/latex]
[latex s=2]x_l = 6.255[/latex]
The updated interval is
[latex s=2][x_l , x_u][6.25 , 7.5][/latex]
-*-*-*-*–*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
Part c.
Error for first iteration:
[latex s=2]\epsilon_t = \frac{|6.241874-7.5|}{|6.241874|} \times 100\% = 20\%[/latex]
[latex s=2]\epsilon_a = \frac{|10-5|}{|10+5|} \times 100\% = 33.33\%[/latex]
Error for first iteration:
[latex s=2]\epsilon_t = \frac{|6.241874-6.25|}{|6.241874|} \times 100\% = 0.13\%[/latex]
[latex s=2]\epsilon_a = \frac{|7.5-5|}{|7.5+5|} \times 100\% = 20\%[/latex]
Approximate relative error:
[latex s=2]error=\frac{|latestapproximation (x_r)-previousapproximation (x_r)|}{|latestapproximation (x_r)|}[/latex]
[latex s=2]error = \frac{|6.25-7.5|}{|6.25|}[/latex]
[latex s=2]error = 0.2[/latex]
[latex s=1]\%error = 0.2\times100 = 20\%[/latex]
That’s it. Note if you were asked to find more than 2 iterations the you have to do the same steps as we did before.
-*-*-*-*–*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
Matlab Code:
Comments