Fancy Math Talk for Move Half Way

This post is on a really easy method to solve some hard problems, including locating a pretty fractal. It is called the bisection method, but you may know it as a high-low game. One person thinks of a number and the other guesses. The person who knows the number replies “high” or “low”. A good strategy is for the guesser to move half way between their most recent high and low guesses. Bisection is fancy math talk for “move half way”. The thing is that this method can solve hard problems and do COOL things. Read on to find out.

A Mathematical Example

function

Suppose we want to solve the equation shown in the above graph equal to zero, that is, find the place where it crosses the axis (marked with a red dot). Looking at the graph, the function is positive at x=3 and negative at x=2. Let’s run with that by playing a high-low game.

  • Half way between 2 and 3, f(2.5)=-0.875. That’s close to zero!
  • Let’s plug in 2.7; we get f(2.7)=2.183, which is positive.
  • Going down to 2.6 we get f(2.6)=0.576, still positive.
  • Going down to 2.55 we get f(2.55)=-0.168625. That’s negative so the answer is between 2.55 and 2.6.
  • Try 2.58 and we get f(2.58)=0.273512, which is positive.
  • Going down to 2.57 we get f(2.57)=0.124593, still positive.
  • Farther down at 2.56 we get f(2.56)=-0.022784, negative!
  • Go up a scootch to 2.562 and compute: f(2.562)=0.006568328, positive and small.

It’s possible to get much closer by continuing, but we have two zeros on the right side of the decimal. That’s close enough for many purposes. If we had split the answer exactly in half each time, instead of guessing a point between the last positive and the last negative results, we would have gotten closer to the correct answer faster; if we were doing this with a computer, that’s the way to go. On the other hand, a computer can do this way faster than we can, so why bother?

Why bother solving by bisection?

Repeat readers of Occupy Math have seen a number of fractals. You give the fractal algorithm some parameters and it draws a fractal. Here are two fractals using parameter value zero and one. The left fractal is too empty, the right one is all filled in. Let’s play a high-low game with the fractal parameter.

 

When the parameter is 0.5 we get another “too full” fractal

pic02

Going down to 0.25 we get a relatively empty fractal.

pic03

Going up to 0.37 we get another pretty empty fractal.

pic04

Going up to 0.43, another too empty fractal.

pic05

Going up to 0.47, still pretty empty.

pic06

Going up to 0.49, we are more interesting, but back to full.

pic07

Going down to 0.48, we get an empty fractal (but with curlicues)!

pic08

Going up to 0.485, better but still fairly empty.

pic09

Going up to 0.488, we get an interesting fractal with an empty middle.

pic10

Going up to 0.489, we get a fractal Occupy Math likes. Done!

pic11

When we are solving the equation equal to zero, the whole thing can be automated — no need for human judgment. When we are playing a high-low game with a fractal parameter, human judgment and artistic sense are needed pretty badly.

How important is the bisection method?

One of the dark secrets that we hide from students during algebra class is that most equations cannot be solved with algebra! The equations that can be solved are important and useful, but very often when solving practical problems we are forced to use techniques like the bisection method or Newton’s method to find the answer. The bisection method is used every day and is built into a lot of software.

Occupy Math’s example with the fractal is a technique he uses all the time to find cool fractals. It works starting with any pair of fractals where one is too empty and the other is too full. When Occupy Math finds one interesting fractal, this method can also be used to search near it for other interesting fractals. This means that the bisection method can be used to make art of a sort!

Occupy Math hopes that some math students will use the bisection method to solve problems in their math class. The method really is useful and, as we have seen, can be used in settings where the thing you are searching for is not numerical, e.g. “does this fractal look good?” If you find an application of the bisection method, please let us know by commenting or tweeting!

I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s