Question

How could a root finding algorithm like the bisection method be used to approximate a value such as sqrt(3). In other words how can a root finding algorithm find an x value with a given y value? Write a script to illustrate this usage scenario. Compare the output of your script with the result from a calculator. You must use matlab!! using a while loop.

Answer 1

The idea of bisection algorithm is based on the following ideas:

1) If for a given interval, the function changes its sign at the endpoints, it must have atleast 1 root in that interval

2) Keep shortening the interval by bisecting (dividing in half) the original interval (iteratively), untill you reach the shortest such interval which satisfies the required precision or gets limited by the local computation i.e. number of iterations.

Please find the 1) Function script 2) Driver program to call this function script as the following:

NOTE:

- The function script must be kept within a file with the same name as that of the function.

- The function file and the driver program script must be kept in the same folder/location

%================= Function script ================

function [root,iter,error_values] = myBisection(fh,low,high,tol,max_iter)

for i=1:max_iter    % Iterate upto allowed number of iterations
  
mid=(low+high)/2;   % Divide the interval in half

error_values = abs(feval(fh,mid)); % Estimate error

if feval(fh,low)*feval(fh,high)>0   % Verify the change in sigh
    root=NaN;
    iter=NaN;
    error_values = NaN;
    break;
elseif (error_values<tol)           % Verify the tolerance in root estimation
    root = mid;
    iter=i;
    break;
else                                % Reassign the interval
    if(feval(fh,mid)*feval(fh,low)<0)
        high = mid;
    elseif (feval(fh,mid)*feval(fh,high)<0)
        low = mid;
    end
end
  
end
end

%===========================================

The following sample driver script attempts to find the root of sin(x) within the interval [3,4]. Intuitively, it should be . The required precision is 10^-4 and maximum allowed iterations are 100.

%============== Driver Script ==============

fh=@(x) sin(x);
low=3;
high=4;
tol=1e-4;
max_iter=100;
[root,iter,error_values] = myBisection(fh,low,high,tol,max_iter)

%=====================================

output:

root =   3.141601562500000

iter =    10

error_values =     8.908910206643689e-06

As one can see, the algorithm find the required root within the precision in 10 iterations itself.

Hope this helps!

************ PLEASE THUMBS UP!!!!!!!!! ************