BISECTION METHOD INTERACTIVE E-BOOK

NONLINEAR EQUATIONS

MAJOR GENERAL

On non Internet Explorer browsers, the equations may not show up.

As an alternative or if you prefer,

you can see the pdf version of the ebook instead.

Title	An interactive e-book for illustrating Bisection Method of solving nonlinear equations
Creator	Autar K Kaw
Subject and Keywords	Bisection Method, Numerical Solution of Nonlinear Equations, Mathcad, Maple, Mathematica, Matlab, Simulations.
Description	An interactive E-book for illustrating Bisection method of finding roots of nonlinear equation. It includes links to simulations in Mathcad, Maple, Mathematica, and Matlab for the algorithm, convergence and the pitfalls; multiple-choice quizzes, problem set, and a power point presentation.
Publisher	Holistic Numerical Methods Institute, College of Engineering, University of South Florida, Tampa, FL 33620-5350.
Contributors	Nathan Collier, Jai Paul, Ginger Williams
Format	Text/HTML
Last Revised	March 10, 2008
Identifier	http://numericalmethods.eng.usf.edu/ebooks/bisection_03nle_ebook.pdf
Language	English
Rights	http://numericalmethods.eng.usf.edu/rights.htm

Table of Contents

Background

Test your knowledge of the background

Introduction

Algorithm

Power point presentation

Example

Simulation [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]

Convergence Simulation [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]

Pitfall: Slow convergence simulation [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]

Advantages

Drawbacks

Problem Sets

Multiple choice question examination

A set of homework assignment problems

Background

This is an example of how an instructor of a Numerical Methods course can develop an E-book on a single topic by using resources that are only available at the Holistic Numerical Methods Institute (HNMI) Website.

Although one of the primary advantages of a web-based resource is that one can use documents outside of its own domain, we are particularly using this example as a way to illustrate the holistic nature of the resources available at HNMI. You are welcome to modify and edit this e-book to suit your purpose.

Using the textbook document written in MS Word 2000 as a foundation, it was made interactive within MS Word 2000 by putting bookmarks and hyperlinks to background information, PowerPoint presentations, Mathcad simulations, historical anecdotes, multiple choice tests, problem sets, etc. Then the MS Word 2000 file was saved as a webpage and that is what you are about to read here.

Back to TOC

Introduction

Before you get started, see the

video

or/and test your knowledge on the background of solving nonlinear equations or go to the table of contents for particular information.

One of the first numerical methods developed to find the root of a nonlinear equation was the bisection method (also called Binary-Search method). The method is based on the following theorem.

Theorem: An equation, where is a real continuous function, has at least one root between and if (See Figure 1).

Note that if, there may or may not be any root between and (Figures 2 and 3). If, then there may be more than one root between and (Figure 4). So the theorem only guarantees one root betweenand.

Since the method is based on finding the root between two points, the method falls under the category of bracketing methods.

Since the root is bracketed between two points, and, one can find the mid-point, between and_. This gives us two new intervals

1. and , and
2. and.

Figure 1: At least one root exists between two points if the function is real, continuous, and changes sign

Figure 2: If function does not change sign between two points, roots of may still exist between the two points.

Figure 3: If the function does not change sign between two points, there may not be any roots between the two points.

Figure 4: If the function changes sign between two points, more than one root for may exist between the two points.

Is the root now between and, or between and? Well, one can find the sign of, and if then the new bracket is between and, otherwise, it is between and. So, you can see that you are literally halving the interval. As one repeats this process, the width of the interval becomes smaller and smaller, and you can “zero” in to the root of the equation. The algorithm for the bisection method is given as follows.

Back to TOC

Algorithm for Bisection Method

The steps to apply the bisection method to find the root of the equation are

1. Choose and as two guesses for the root such that, or in other words, changes sign between and.
2. Estimate the root, of the equation as the mid-point between and as

3. Now check the following
1. If, then the root lies between and; then and.
2. If, then the root lies between and; thenand .
3. If; then the root is_. Stop the algorithm if this is true.
4. Find the new estimate of the root

Find the absolute approximate relative error as

where

= estimated root from present iteration

= estimated root from previous iteration

5. Compare the absolute relative approximate error with the pre-specified relative error tolerance. If, then go to Step 3, else stop the algorithm. Note one should also check whether the number of iterations is more than the maximum number of iterations allowed. If so, one needs to terminate the algorithm and notify the user about it.

Look at the PowerPoint presentation of Bisection Method or see the classroom lecture video.

Back to TOC

Example

You are working for ‘DOWN THE TOILET COMPANY’ that makes floats for ABC commodes. The ball has a specific gravity of 0.6 and has a radius of 5.5 cm. You are asked to find the distance to which the ball will get submerged when floating in water.

Figure 5. Floating ball problem

The equation that gives the depth to which the ball is submerged under water is given by

Use the bisection method of finding roots of equations to find the depth to which the ball is submerged under water. Conduct three iterations to estimate the root of the above equation. Find the absolute relative approximate error at the end of each iteration, and the number of significant digits at least correct at the end of each iteration.

Solution

From the physics of the problem, the ball would be submerged between and,

where

,

that is

Lets us assume

Check if the function changes sign between and

Hence

So there is at least one root between and, that is between 0 and 0.11.

Iteration 1

The estimate of the root is

Hence the root is bracketed between and, that is, between 0.055 and 0.11. So, the lower and upper limits of the new bracket are

At this point, the absolute relative approximate error, cannot be calculated as we do not have a previous approximation.

Iteration 2

The estimate of the root is

Hence, the root is bracketed between and, that is, between 0.055 and 0.0825. So the lower and upper limit of the new bracket is

The absolute relative approximate error, at the end of iteration #2 is

None of the significant digits are at least correct in the estimated root of because the absolute relative approximate error is greater than 5%.

Iteration 3

Hence, the root is bracketed between and, that is, between 0.055 and 0.6875. So the lower and upper limit of the new bracket is

The absolute relative approximate error, at the ends of iteration#3 is

Still none of the significant digits are at least correct in the estimated root of the equation as the absolute relative approximate error is greater than 5%.

Seven more iterations were conducted and these iterations are shown in the table below.

Table 1: Root of f(x)=0 as function of number of iterations for bisection method.

Iteration	xl	xu	xm	%	f(xm)
1