# n this module, I include a file called Bisection Technique. I use an example similar to the textbook described in section 2.1. I start to solve the example by hand

n this module, I include a file called Bisection Technique. I use an example similar to the textbook described in section 2.1. I start to solve the example by hand and complete it using MATLAB. After reading the Bisection technique lesson 4 and section 2.1 of the textbook, answer the following discussion question in your own words. When running the Bisection method in lesson 4 (program 1.1), with a tolerance of 0.001 the answer is 1.3652 which is equivalent to p9 according to the table 2.1 from the textbook. When running p13 in lesson 4 (program 1.2), the answer is 1.3651 which is equivalent to p13. Which one of the answers do you think is the most accurate answer closest to the solution and why? Which of the two calculation methods do you prefer and why? Elaborate in your answers. file attached Lesson 4 Bisection Technique To find a solution or root of an equation f(x) we can apply the bisection method, which is an approximation technique to get closer and closer to the value of the root by dividing the interval in half after each iteration. The bisection method or binary search technique is based on the Intermediate Value Theorem. Suppose f is a continuous function on the interval [a,b] with f(a) and f(b) of opposite sign, the Intermediate Value Theorem implies that a number p exists in [a,b] with f(p) = 0. The method calls for a repeated halving or bisecting of subintervals of [a,b] and at each step locating the half containing p. Example: Does f(x) = x 3 +4x 2 -10 has a root or solution in [a,b] = [1,2]? 1) Let’s check if f(1) and f(2) have opposite signs according to the Intermediate Value Theorem. f(a) = f(1) = (1) 3 + 4(1) 2 – 10 = -5 (negative) f(b) = f(2) = (2) 3 + 4(2) 2 – 10 = 8+16-10 = 14 (positive) The answer is yes, which means since f is continuous there must be a solution in the interval [1,2]. 2) Let p be the solution we are searching for and let p1 be the first midpoint of [a,b] = [1,2]. p1 = (a+b)/2 = (1+2)/2 = 3/2 = 1.5 f(p1) = f(1.5) = (1.5) 3 +4(1.5) 2 -10 = 2.375 (positive) 3) If f(p1) = 0 then p1 is the root or the solution, so p= p1. Done. Otherwise, if f(p1) is not equal to zero, which is the case, we’re going to replace either a or b by p1 to obtain a new interval closer to the root or the solution. How do we know which one to replace? Simple. The goal is to keep two intervals of which their functions have opposite signs when we calculate the function f at these two intervals. The question to ask is rather which of the two f(a) and f(b) has opposite sign to the function f(p1) ? a) If f(p1) and f(a) have the same sign, then they don’t satisfy the Intermediate Value Theorem. We replace a by p1 , so the new interval that contains the solution p will be [p1, b]. b) If f(p1) and f(a) have opposite signs, then they satisfy the Intermediate Value Theorem. We replace b by p1 so the new interval that contains the solution p will be [a, p1]. In our case, f(a) which is f(1) has opposite sign to f(p1) which is f(1.5) . We replace ( b which is 2 by p1 which is 1.5). The new interval that contains a solution is [a, p1] = [1, 1.5]. Next we go back to step 2 and step 3 by repeating this process again to find the new midpoint p2, check if p2 is the solution, if not obtain a new interval. Let’s continue with steps 2 and 3. Step 2: a. let p2 be the second midpoint of [a, p1] = [1, 1.5]. p2 = (a+p1)/2 = (1+1.5)/2 = 2.5/2 = 1.25 f(p2) = f(1.25) = (1.25) 3 +4(1.25) 2 -10 = -1.796875 (negative) Step 3: Which of the two f(a) and f(p1) has opposite sign to the function f(p2) OR Which of the two f(1) and f(1.5) has opposite sign to the function f(1.25) ? f(a) = f(1) = -5; f(p1) = f(1.5) = 2.375; f(p2) = f(1.25) = -1.796875 The answer is f(p1) = f(1.5) and f(p2) = f(1.25), so we replace a by p2. Therefore, the new interval that contains a solution is: [p2, p1] = [1.25, 1.5]. We repeat steps 2 and 3 again and again until f(midpoint) = 0 or within a Tolerance, let’s say 0.001 = 10 -4 . To do this we can use the MATLAB tool. The following program 1.1 can be used to find the root of the same function using bisection method with a tolerance of 0.001 = 10 -4 %Program 1.1 Bisection Method %Computes approximate solution of f(x)=0 %Input: inline function f; a,b such that f(a)*f(b)<0, % and tolerance tol %Output: Approximate solution xc function xc = bisect(f,a,b,tol) if sign(f(a))*sign(f(b)) >= 0, error(‘f(a)f(b)<0 not satisfied!') %ceases execution end fa=f(a); fb=f(b); k = 0; while (b-a)/2>tol c=(a+b)/2; fc=f(c); if fc == 0 %c is a solution, done break end if sign(fc)*sign(fa)<0 % a and c make the new interval b=c;fb=fc; else % c and b make the new interval a=c;fa=fc; end end xc=(a+b)/2; %new midpoint is best estimate 1. Copy and paste this program in MATLAB in the editor window. 2. Save the program as bisect. 3. To run the program, type the following in the command window: >> bisect(@(x) x^3+4*x^2-10,1,2,0.0001) @(x) x^3+4*x^2-10 represents the function 1,2 represents the interval 0.01 represents the Tolerance. The output is: ans = 1.3652 The following MATLAB program 1.2 can be used to find the root of the same function using bisection method with 13 iterations meaning that we will find the midpoint 13 times pn = p13. %Program 1.2 Bisection Method function [x e] = mybisect(f,a,b,n) % function [x e] = mybisect(f,a,b,n) % Does n iterations of the bisection method for a function f % Inputs: f — an inline function % a,b — left and right edges of the interval % n — the number of bisections to do. % Outputs: x — the estimated solution of f(x) = 0 % e — an upper bound on the error format long c = f(a); d = f(b); if c*d > 0.0 error(‘Function has same sign at both endpoints.’) end disp(‘ x y’) for i = 1:n x = (a + b)/2; y = f(x); disp([ x y]) if y == 0.0 % solved the equation exactly e = 0; break % jumps out of the for loop end if c*y < 0 b=x; else a=x; end end e = (b-a)/2; 1. Copy and paste this program in MATLAB in the editor window. 2. Save the program as bisection. 3. To run the program, type the following in the command window: >> bisection(@(x) x^3+4*x^2-10,1,2,13) @(x) x^3+4*x^2-10 represents the function 1,2 represents the interval 13 represents the number of iterations. The output is: x y 1.500000000000000 2.375000000000000 1.250000000000000 -1.796875000000000 1.375000000000000 0.162109375000000 1.312500000000000 -0.848388671875000 1.343750000000000 -0.350982666015625 1.359375000000000 -0.096408843994141 1.367187500000000 0.032355785369873 1.363281250000000 -0.032149970531464 1.365234375000000 0.000072024762630 1.364257812500000 -0.016046690754592 1.364746093750000 -0.007989262812771 1.364990234375000 -0.003959101522923 1.365112304687500 -0.001943659010067 ans =

## Leave a Reply

Want to join the discussion?Feel free to contribute!