Ch2. Finding a Roots - The Bisection Method

Where to Look for Roots

So far, you have estimated roots by plotting the function and visually locating the root. Numerical root finding methods can't visually locate a root; they must rely on other ways to know where to look for a root.

The Intermediate Value Theorem

The simplest root finding method, the bisection method, makes use of the Intermediate Value Theorem (IVT) to identify where a root must be.

Consider any continuous function f(x).

Choose a value x_{neg} such that f(x_{neg}) is negative.

Choose another value x_{pos} for which f(x_{pos}) is positive.

The Intermediate Value Theorem guarantees there must be at least one root between x_{neg} and x_{pos}.

As long as x_{neg} and x_{pos} are chosen appropriately, there will always be a root between x_{neg} and x_{pos}. (You don't know how many there are, but you can be sure there has to be at least one.)

x_{neg} and x_{pos} are said to bracket the root between them.

Task1 - Find Brackets for a Root

In this activity, you will identify brackets for the roots of the function f(x)=0.5-\sin(x)-x^2

within the interval x \in [-2, 1]. A plot of the function has been created for you.

x = linspace(-2,1);
y = 0.5-sin(x) -x.^2
plot(x,y);
hold on
plot([-2 1], [0 0]);
hold off
grid on

1.

Consider the root near x=0.4. Choose an appropriate value x_{pos} such that f(x_{pos})>0. Assign the value to the variable xp.

Again for the root near x=0.4, choose an appropriate value x_{neg} such that f(x_{neg}) < 0. Assign the value to the variable xn.

xp = 0;
xn = 0.5;

2.

Most root finding algorithms require a starting interval that brackets the root. The interval is represented by a two element vector containing the left and right endpoints of the interval.

Now consider the root near x=−1.2. Choose appropriate values x_{neg} and x_{pos} that bracket the root. Use the values to create a two element vector x0 that represents an interval bracketing the root.

x0 = [-1.5 -1]

The Bisection Method Algorithm

The Bisection Method

The bisection method is a simple and robust root finding algorithm. Like all numerical root finding algorithms, the method starts with an initial guess and refines it until the root is located within a certain tolerance.

The Algorithm

The bisection method needs two things to find a root:

1.

a continuous function

2.

an interval bracketing the desired root

The method iteratively halves the interval and uses the Intermediate Value Theorem (IVT) to determine which half contains the root. The more iterations the bisection method runs, the smaller the interval containing the root will be and the more accurate the estimate of the root.

Let's visualize the steps of the bisection method by applying it to the function f(x) = \cos(x) -x

f(x) is a continuous function, so the IVT guarantees a root between x_p and x_n.

Calculate the midpoint between x_n and x_p.

Evaluate f(x) at the midpoint x_{mp}. Since f(x_{mp})>0, the root must be between x_{mp} and x_n.

Update x_p to be the value of x_{mp}, and repeat the method on the new interval.

Find the midpoint x_{mp}. This repeated bisection of the interval gives the method its name.

Evaluate f(x) at the midpoint x_{mp}. This time f(x_{mp})<0, so the root must be between x_{mp} and x_p.

Update xn with xmp, and repeat the method. Notice that the interval is shrinking around the root.

xmp is getting closer to the root as the method is repeated.

Eventually, the root is found to be approximately 0.7391.

Task1 - Approximate a Root Using the Bisection Method

In this activity, you will continue investigating the function f(x) = 0.5-\sin(x) - x^2 and its root near x=0.4. You will perform the first two iterations of the bisection method.

The variables xn and xp have been defined for you. These contain values that form a bracket for the root.

xp = -0.5, xn = 0.8;

1.

Calculate the midpoint between xp and xn by averaging the two values. Assign the result to the variable xmp.

xmp = ((xn + xp)/2);

2.

Recall that f(x) = 0.5-\sin(x) - x^2. Calculate f(x_{mp}) and assign the result to the variable ymp. You may want to leave off the semicolon to see the result.

ymp = 0.5-sin(xmp)-xmp^2

3.

To repeat the bisection method, you need to update the value of either x_{neg} or x_{pos} using the midpoint x_{mp}.

If y_{mp} is less than 0, then x_{neg}= x_{mp}.

If y_{mp} is greater than 0, then x_{pos} = x_{pos}.

Update either xn or xp with the value xmp. The variable you change depends on the sign (+ or -) of ymp.

if ymp > 0 
	xp = xmp
else 
	xn = xmp
end

4.

You can recall a command that you previously entered by using the up arrow key at the command line.

Recalculate the midpoint xmp using the updated brackets xn and xp.

xmp = ((xn + xp)/2)

5.

Calculate ymp for the new value of xmp using the same command from task 2.

ymp = 0.5-sin(xmp)-xmp^2

6.

Update xn or xp depending on the sign (+ or -) of ymp.

if ymp > 0 
	xp = xmp
else 
	xn = xmp
end

7.

Recalculate the midpoint xmp using the updated brackets xn and xp.

This value is the approximate location of the root after two iterations of the bisection method. You may want to leave off the semicolon to display the result.

xmp - ((xn + xp)/2)

Task2 - Implement the Bisection Method

You completed a few iterations of the bisection method manually, but it's time consuming to get an accurate estimation of the root this way.

Instead, a script can automate the bisection method algorithm to provide the desired accuracy.

In this activity, you will implement the bisection method for the function

f(x) = 0.5-\sin(x)-x^2 to find its root near x=0.4. The script provided is almost complete.

1.

In the previous activity, this rule was established to update the brackets:

If y_{mp} is less than 0, then x_{neg}= x_{mp}.

If y_{mp} is greater than 0, then x_{pos} = x_{pos}.

The rule can be implemented as an if/else statement in MATLAB.

The script implements the bisection method algorithm. Complete the if/else statement it contains to update the brackets xn and xp based on the value of ymp.

% create brackets
xp = -0.5;
xn = 0.8;

% calculate the midpoint
xmp = (xn+xp)/2;

% calculate f(xmp)
ymp = 0.5 - sin(xmp) - xmp.^2;

% define the Bisection Method using for loop
for iteration = 1:5
    if ymp < 0
        % ymp is less than zero
        xn = xmp;
    else
        % ymp is greater than zero
        xp = xmp'
    end
    xmp = (xn + xp) / 2;
    ymp = 0.5 - sin(xmp) - xmp.^2;
end

% display the root value
xmp
ymp

% plot the function and the root
xvals = linspace(0.1,0.5);
yvals = 0.5 - sin(xvals) - xvals.^2;
plot(xvals,yvals)
hold on
plot([0.1 0.5],[0 0])
plot(xmp,ymp,'r.','MarkerSize',30)
hold off
grid on

2.

For any value of n, you can repeat code n times using a for loop.

The script repeats the bisection method using a for loop, and the value chosen for n in the for loop determines the accuracy of the root.

Change for loop for while loop iterations so that the final value of ymp is less than 0.001.

while abs(ymp) > 0.001
	if ymp < 0
        % ymp is less than zero
        xn = xmp
    else
        % ymp is greater than zero
        xp = xmp
    end
    xmp = (xn + xp) / 2;
    ymp = 0.5 - sin(xmp) - xmp.^2;
end

Where to Look for Roots

So far, you have estimated roots by plotting the function and visually locating the root. Numerical root finding methods can't visually locate a root; they must rely on other ways to know where to look for a root.

The Intermediate Value Theorem

The simplest root finding method, the bisection method, makes use of the Intermediate Value Theorem (IVT) to identify where a root must be.

Consider any continuous function f(x).

Choose a value x_{neg} such that f(x_{neg}) is negative.

Choose another value x_{pos} for which f(x_{pos}) is positive.

The Intermediate Value Theorem guarantees there must be at least one root between x_{neg} and x_{pos}.

As long as x_{neg} and x_{pos} are chosen appropriately, there will always be a root between x_{neg} and x_{pos}. (You don't know how many there are, but you can be sure there has to be at least one.)

x_{neg} and x_{pos} are said to bracket the root between them.

Task1 - Find Brackets for a Root

In this activity, you will identify brackets for the roots of the function f(x)=0.5-\sin(x)-x^2

within the interval x \in [-2, 1]. A plot of the function has been created for you.

x = linspace(-2,1);
y = 0.5-sin(x) -x.^2
plot(x,y);
hold on
plot([-2 1], [0 0]);
hold off
grid on

1.

Consider the root near x=0.4. Choose an appropriate value x_{pos} such that f(x_{pos})>0. Assign the value to the variable xp.

Again for the root near x=0.4, choose an appropriate value x_{neg} such that f(x_{neg}) < 0. Assign the value to the variable xn.

xp = 0;
xn = 0.5;

2.

Most root finding algorithms require a starting interval that brackets the root. The interval is represented by a two element vector containing the left and right endpoints of the interval.

Now consider the root near x=−1.2. Choose appropriate values x_{neg} and x_{pos} that bracket the root. Use the values to create a two element vector x0 that represents an interval bracketing the root.

x0 = [-1.5 -1]

The Bisection Method Algorithm

The Bisection Method

The bisection method is a simple and robust root finding algorithm. Like all numerical root finding algorithms, the method starts with an initial guess and refines it until the root is located within a certain tolerance.

The Algorithm

The bisection method needs two things to find a root:

1.

a continuous function

2.

an interval bracketing the desired root

The method iteratively halves the interval and uses the Intermediate Value Theorem (IVT) to determine which half contains the root. The more iterations the bisection method runs, the smaller the interval containing the root will be and the more accurate the estimate of the root.

Let's visualize the steps of the bisection method by applying it to the function f(x) = \cos(x) -x

f(x) is a continuous function, so the IVT guarantees a root between x_p and x_n.

Calculate the midpoint between x_n and x_p.

Evaluate f(x) at the midpoint x_{mp}. Since f(x_{mp})>0, the root must be between x_{mp} and x_n.

Update x_p to be the value of x_{mp}, and repeat the method on the new interval.

Find the midpoint x_{mp}. This repeated bisection of the interval gives the method its name.

Evaluate f(x) at the midpoint x_{mp}. This time f(x_{mp})<0, so the root must be between x_{mp} and x_p.

Update xn with xmp, and repeat the method. Notice that the interval is shrinking around the root.

xmp is getting closer to the root as the method is repeated.

Eventually, the root is found to be approximately 0.7391.

Task1 - Approximate a Root Using the Bisection Method

In this activity, you will continue investigating the function f(x) = 0.5-\sin(x) - x^2 and its root near x=0.4. You will perform the first two iterations of the bisection method.

The variables xn and xp have been defined for you. These contain values that form a bracket for the root.

xp = -0.5, xn = 0.8;

1.

Calculate the midpoint between xp and xn by averaging the two values. Assign the result to the variable xmp.

xmp = ((xn + xp)/2);

2.

Recall that f(x) = 0.5-\sin(x) - x^2. Calculate f(x_{mp}) and assign the result to the variable ymp. You may want to leave off the semicolon to see the result.

ymp = 0.5-sin(xmp)-xmp^2

3.

To repeat the bisection method, you need to update the value of either x_{neg} or x_{pos} using the midpoint x_{mp}.

If y_{mp} is less than 0, then x_{neg}= x_{mp}.

If y_{mp} is greater than 0, then x_{pos} = x_{pos}.

Update either xn or xp with the value xmp. The variable you change depends on the sign (+ or -) of ymp.

if ymp > 0 
	xp = xmp
else 
	xn = xmp
end

4.

You can recall a command that you previously entered by using the up arrow key at the command line.

Recalculate the midpoint xmp using the updated brackets xn and xp.

xmp = ((xn + xp)/2)

5.

Calculate ymp for the new value of xmp using the same command from task 2.

ymp = 0.5-sin(xmp)-xmp^2

6.

Update xn or xp depending on the sign (+ or -) of ymp.

if ymp > 0 
	xp = xmp
else 
	xn = xmp
end

7.

Recalculate the midpoint xmp using the updated brackets xn and xp.

This value is the approximate location of the root after two iterations of the bisection method. You may want to leave off the semicolon to display the result.

xmp - ((xn + xp)/2)

Task2 - Implement the Bisection Method

You completed a few iterations of the bisection method manually, but it's time consuming to get an accurate estimation of the root this way.

Instead, a script can automate the bisection method algorithm to provide the desired accuracy.

In this activity, you will implement the bisection method for the function

f(x) = 0.5-\sin(x)-x^2 to find its root near x=0.4. The script provided is almost complete.

1.

In the previous activity, this rule was established to update the brackets:

If y_{mp} is less than 0, then x_{neg}= x_{mp}.

If y_{mp} is greater than 0, then x_{pos} = x_{pos}.

The rule can be implemented as an if/else statement in MATLAB.

The script implements the bisection method algorithm. Complete the if/else statement it contains to update the brackets xn and xp based on the value of ymp.

% create brackets
xp = -0.5;
xn = 0.8;

% calculate the midpoint
xmp = (xn+xp)/2;

% calculate f(xmp)
ymp = 0.5 - sin(xmp) - xmp.^2;

% define the Bisection Method using for loop
for iteration = 1:5
    if ymp < 0
        % ymp is less than zero
        xn = xmp;
    else
        % ymp is greater than zero
        xp = xmp'
    end
    xmp = (xn + xp) / 2;
    ymp = 0.5 - sin(xmp) - xmp.^2;
end

% display the root value
xmp
ymp

% plot the function and the root
xvals = linspace(0.1,0.5);
yvals = 0.5 - sin(xvals) - xvals.^2;
plot(xvals,yvals)
hold on
plot([0.1 0.5],[0 0])
plot(xmp,ymp,'r.','MarkerSize',30)
hold off
grid on

2.

For any value of n, you can repeat code n times using a for loop.

The script repeats the bisection method using a for loop, and the value chosen for n in the for loop determines the accuracy of the root.

Change for loop for while loop iterations so that the final value of ymp is less than 0.001.

while abs(ymp) > 0.001
	if ymp < 0
        % ymp is less than zero
        xn = xmp
    else
        % ymp is greater than zero
        xp = xmp
    end
    xmp = (xn + xp) / 2;
    ymp = 0.5 - sin(xmp) - xmp.^2;
end

Where to Look for Roots

So far, you have estimated roots by plotting the function and visually locating the root. Numerical root finding methods can't visually locate a root; they must rely on other ways to know where to look for a root.

The Intermediate Value Theorem

The simplest root finding method, the bisection method, makes use of the Intermediate Value Theorem (IVT) to identify where a root must be.

Consider any continuous function f(x).

Choose a value x_{neg} such that f(x_{neg}) is negative.

Choose another value x_{pos} for which f(x_{pos}) is positive.

The Intermediate Value Theorem guarantees there must be at least one root between x_{neg} and x_{pos}.

As long as x_{neg} and x_{pos} are chosen appropriately, there will always be a root between x_{neg} and x_{pos}. (You don't know how many there are, but you can be sure there has to be at least one.)

x_{neg} and x_{pos} are said to bracket the root between them.

Task1 - Find Brackets for a Root

In this activity, you will identify brackets for the roots of the function f(x)=0.5-\sin(x)-x^2

within the interval x \in [-2, 1]. A plot of the function has been created for you.

x = linspace(-2,1);
y = 0.5-sin(x) -x.^2
plot(x,y);
hold on
plot([-2 1], [0 0]);
hold off
grid on

1.

Consider the root near x=0.4. Choose an appropriate value x_{pos} such that f(x_{pos})>0. Assign the value to the variable xp.

Again for the root near x=0.4, choose an appropriate value x_{neg} such that f(x_{neg}) < 0. Assign the value to the variable xn.

xp = 0;
xn = 0.5;

2.

Most root finding algorithms require a starting interval that brackets the root. The interval is represented by a two element vector containing the left and right endpoints of the interval.

Now consider the root near x=−1.2. Choose appropriate values x_{neg} and x_{pos} that bracket the root. Use the values to create a two element vector x0 that represents an interval bracketing the root.

x0 = [-1.5 -1]

The Bisection Method Algorithm

The Bisection Method

The bisection method is a simple and robust root finding algorithm. Like all numerical root finding algorithms, the method starts with an initial guess and refines it until the root is located within a certain tolerance.

The Algorithm

The bisection method needs two things to find a root:

1.

a continuous function

2.

an interval bracketing the desired root

The method iteratively halves the interval and uses the Intermediate Value Theorem (IVT) to determine which half contains the root. The more iterations the bisection method runs, the smaller the interval containing the root will be and the more accurate the estimate of the root.

Let's visualize the steps of the bisection method by applying it to the function f(x) = \cos(x) -x

f(x) is a continuous function, so the IVT guarantees a root between x_p and x_n.

Calculate the midpoint between x_n and x_p.

Evaluate f(x) at the midpoint x_{mp}. Since f(x_{mp})>0, the root must be between x_{mp} and x_n.

Update x_p to be the value of x_{mp}, and repeat the method on the new interval.

Find the midpoint x_{mp}. This repeated bisection of the interval gives the method its name.

Evaluate f(x) at the midpoint x_{mp}. This time f(x_{mp})<0, so the root must be between x_{mp} and x_p.

Update xn with xmp, and repeat the method. Notice that the interval is shrinking around the root.

xmp is getting closer to the root as the method is repeated.