7.2.1 Bisection

Let's start by trying to find the root of the polynomial $x^3-2x-5$. In other words, we are trying to find the value of $x$ that satisfies $x^3-2x-5=0$.^7.2 Use MATLAB's ezplot function to plot the function as shown in Fig. 7.2. Adjust the plot range until you have bracketed the root. Graphically determine the root near 2.1 by repeatedly narrowing the plot range. (Use axes or xlim and ylim.) Continue until you have determined the root to at least four decimal places.

Figure 7.2: Plot of the polynomial $x^3-2x-5$. The real root is near 2.1.

The bisection root-finding method is similar to what you just did ``by hand'' in that it constantly narrows the range containing the root until the root is known to the desired precision. It starts with a range that brackets one and only one root. The range is then divided in half. One half will contain the root, the other will not. The half containing the root is selected and divided in half again. Again the half containing the root is selected and the process is repeated until the range is small enough that the root is known to arbitrary precision. We'll give some additional details and list a sample M-file demonstrating the method. The initial range is specified by two points, $x_1$ and $x_2$. We know that a root is bracketed by these two points if the sign of $f(x_1)$ and $f(x_2)$ are not the same (one must be positive and the other negative, but it doesn't matter which is which). We divide the range ($x_2-x_1$) in halves by choosing a point $x_{\mathrm{new} }$ at their midpoint, $x_1+(x_2-x_1)/2$. If the root is on the left half then the sign of $f(x_1)\times f(x_{\mathrm{new}})$ will be negative, otherwise the root will be on the right half. If the root is on the left, then we want to assign the value of $x_{\mathrm{new} }$ to $x_2$ and perform the process again. If the root is on the right, then assign the value of $x_{\mathrm{new} }$ to $x_1$ and repeat. We stop the process when $\vert f(x_{\mathrm{new}})\vert<\epsilon$ where $\epsilon$ is some specified tolerance.

% Bisection method for root-finding
clear all; close all;

f=inline('x^3-2*x-5','x'); % Define f as an inline function

eps = 1e-14; % define the tolerance (what happens if it is too small? Try it!)
x1 = 2.0; x2 = 2.5; % Wide bracketing guesses taken from plot
xnew = x1+(x2-x1)/2; % Give xnew an initial value (not so important what it is)
step = 0; % Initialize step counter
while (abs(f(xnew))>eps) % Keep going until |f(xnew)| is REALLY small
    step = step + 1;     % record how many steps are required to find the root
    xnew = x1+(x2-x1)/2; % determine a new point in the middle of the current range
    disp([xnew f(xnew)]) 
    error(step) = f(xnew);  
    if (f(x1)*f(xnew) < 0)
        x2=xnew; % root is on left half of range
    else 
        x1 = xnew; % root is on right half of range
    end
end     
semilogy(abs(error),'.-') % Log plots don't work with negative data points
grid on                   % so we plot the absolute value of the error
xlabel('Number of bisections')
ylabel('|f(x_i)|')
title('Convergence of the bisection method for root-finding')