Finding Roots

This tutorial explores two methods for finding the root of an equation: the bisection method and Newton's method. The bisction method is first mentioned in Chapter 9 as a way to find nuumerical solutions to equations in one unknown, for example x^2 = 5. Because this is a simple equation, we know that the answer is

	x = sqrt(5) ~= 2.24

To solve this equation using bisection we first manipulate it algebraically so that one side is zero (finding a root refers to finding out where an equation is equal to zero). So, to solve the equation using a root method, we first turn it into

	x^2 - 5 = 0

To use the bisection method we find two numbers such that the equation when evaluated at one number is positive and at the other is negative. This is oftern done through educated guessing. We then narrow the gap between the two until the bisection point (the point halfway in x between the guesses), when plugged into the equation, is sufficiently close to 0. How close the answer must be to 0 depends on what kind of problem you are solving. If you are figuring the best cant of a road at a specific point, then getting within two decimal places of 0 is sufficient. If you are pinpointing the spot in someone's body where hyper? waves should meet to break apart a tumor, then you will need more precision. In the equation x^2 - 5, since it's an x^2 equation with just a constant, the equation is concave up. The equation is 0 at

	sqrt(5) and -sqrt(5)

and the minimum is at 0 (f(0)=-5). So, the equation is positive when

	x <-sqrt(5) and x > sqrt(5).

We can choose our positive point anywhere the equation is positive and our negative point anywhere the equation is negative. Lets choose x = -5 for the positive guess and x = -1 for the negative guess. Click the following button to start the graphical example of the problem x^2 - 5 = 0 using the guesses x = -5 for the positive guess and x = -1 for the negative guess.

If you see this, then Java is not running in your browser!
An applet would normally go here...

As you can see from the applet, one of the guesses (the pink) is positive in f(x) and one (the red) is negative. The next step in bisection is to find the bisection point, the one point exactly halfway between the points (in x). The bisection point for our purposes is

	pos guess = -5
	neg guess = -1

	bisection = pos guess - 1/2(neg guess + pos guess)
	          = -5 - 1/2( -5 + -1)
	          = -5 - 1/2( -6 )
	          = -5 + 3
		  = -2

If you look at the bottom of the applet you will see the coordinates for the positive guess, the negative guess, and the bisection point. The bisection point is indeed at -2 for x. When we plug this into the function, we get

	x^2 - 5 = (-2)^2 - 5
	        = 4 - 5
	        = -1

and, the y coordinate for the bisection point is -1 (so, we're fairly close already to 0).

To find a root using bisection, press the 'Step' button. This will give you one step in the bisection method. A blue ball will appear between the two other balls. This is the bisection point, the midpoint between the two guesses (in x). Then, if the bisection point is positive in y, the positive ball will move down to the bisection point and that will become the positive guess. If the bisection point is negative in y, the negative ball will move up to the bisection point and that will become the new negative guess. Try pushing the step button a few times. If the graphics are too fast or slow, you can change them by choosing 'Speed' under 'Preferences'.

Now, we have

	pos guess = -5
	neg guess = -2
	
	bisection = pos guess - 1/2(neg guess - pos guess)
	          = -5 - 1/2( -5 - -2)
	          = -5 - 1/2( -3 )
	          = -5 + 1.5
		  = -3.5

The numbers underneath the plot are the coordinates of the guesses and the bisection point. They are color-coded to their associated dots.

If you have pushed step several times, the guesses should now be much closer together, perhaps so close that they look like one ball. But, suppose you want to make sure that it is very close to 0, perhaps within .001. This is closer than you can see from the plot as it is. We can, however, zoom in on one portion of the plot. The easiest way to do this is to use the mouse to show what rectangle we want to zoom in on (you will want this rectangle will have the guesses in it). Point the mouse to the left and above the dots, then press down on the mouse button and drag the mouse down and to the right. A rectangle will be drawn showing the section which will be zoomed in on. When you let up on the mouse the plot will redraw, showing only the section in the rectangle. Try this on the plot, putting a rectangle closely around the two guesses. The x and y axes will be more detailed, so that you can see how far apart the guesses are and how far from 0 you still are in y. To get within .001 of 0, you will use 14 steps. At 14 steps, you will see that the x, y coordinates for the bisection point are

	x: -2.23621	y: -0.000617519

and since, to be within .001, the absolute value of 0 - y must be less than .001,

	| 0 - .000617519 | = .000619519 < .001

Zoom in whith a button. Use this to explain the zoom-in menu options. Zoom out again, giving them instructions on how to set the zoom using zoom-by 5 or zoom rectangle.

Next switch function, explaining that menu.

Make up a lesson for Newton's method.