Feeds:
Posts

## Square Root Algorithm

The “Babylonian Algorithm” for approximating square roots is a great example of a recursive function or iterative calculation.  I first encountered this method in an undergraduate Real Analysis I took at University of Maine in 2002.  The basic idea is that we make a guess for the square root of a number (let’s say $\sqrt{60}$).  So we could guess $\sqrt{60} \approx 7.5$.  Then we divide $60 \div 7.5 = 8$ and then average our guess with the result of the division $\frac{7.5+8}{2} =7.75$ and then follow the process all over again $60 \div 7.75 \approx 7.742$ and $\frac{7.75+7.742}{2} \approx 7.746$ and continue this process until the desired accuracy is achieved.  $7.746$ is actually a pretty good result for $\sqrt{60}$.

I programmed this loop onto a TI84 calculator for fun and it works quite well. Pseudocode for this looks like:

Input A

A/2 = B

While abs(A-B^2) > 0.01 do

A/B=C

(B+C)/2=B

else

Display B

Then I wondered if I could do something similar for other roots.  I tried a fifth root program, but changed the “A/B = C” to “A/B^4=C” and tried to run the program, but it ended up in an infinite loop.  Somehow the process was skipping over the fifth root I was looking for.  I started with $\sqrt[5]{32}$ just to keep it simple.  The algorithm started with large values but as it got closer to 2, it failed converge on the desired answer.  Here’s the pseudocode for my first try:

Input A

(A+1)/2 = B

While abs(A-B^5) > 0.01 do

A/B^4=C

(B+C)/2=B

else

Display B

If you try this algorithm starting with:

32/2.3^4 = 1.1435

(2.3+1.1435)/2 = 1.72175

So far so good, 1.72175 is closer than 1.1435, but when we do 32/1.72175^4 we get 3.6414 which is farther away than 2.3 was.  So I decided to take a weighted average and made the algorithm:

Input A

(A+1)/2 = B

While abs(A-B^5) > 0.01 do

A/B^4=C

(4*B+C)/5=B

else

Display B

And it worked like a charm!  Then I extended this to other roots as:

Input A

Input R

(A+1)/2 = B

While abs(A-B^R) > 0.01 do

A/B^(R-1)=C

(R-1)*B+C)/R=B

else

Display B

And again – it works great!  I haven’t figured out the problem with the original fifth root algorithm I tried, but I think that the A/B^4 introduces something that throws it off.

## Graphing Complex Functions (Again)

Back in June of 2009, I wrote about the issues involved in graphing complex functions.  Since then, I’ve been showing this material to my students and discussing the relationship between graphing real-valued functions and graphing complex-valued functions.

As part of these talks, I’ve had to make explicit the difference between the Cartesian Plane and the Argand Diagram.  I’ve been doing this by showing the mapping of the points from the x-real number line to the y-real number line.  George Abdo and Paul Godfrey have a nice website that shows this process.

OK, then if we cross the x and y number lines to create the Cartesian Plane, we’ll see the picture of the graph that we’re used to.

Then, we have to consider the complex mapping.  In this situation, each x value is two-dimensional and is mapped to a two-dimensional y coordinate, like so:

(Click the picture for a better view, or check out the link to Prof. Abdo’s website)

But to show these together, as the Cartesian Plane does for real-valued functions would require 4 dimensions, which creates difficulty for human beings who normally have enough trouble with 3 dimensions.  What people have done instead is to take the x values from the complex plane and color them based on their corresponding y values.

Lawrence Crone at American University has some nice pictures showing this effect.

Andrew Bennett at Kansas State University has a nifty online complex graphing calculator on his website.  You can type in a formula and the software will show you a representation of the mapping.  I prefer the top view to see the roots, but the side view is interesting as well.

The graphing utility window is limited to complex x values a+bi in which a and b are both between 2 and -2, but this can be adjusted by right clicking on the window.

Something that shows up nicely on the complex grapher at the previous link are roots of unity – typing in z³-1 will show the cube roots of 1, both real and complex…

## NY Times on Complex Numbers

I posted about the Complex Numbers last summer, and also wrote about using Newton’s Method to find complex roots.

The New York Times math blog by Professor Steven Strogatz of Cornell University has an excellent post on complex numbers and Newton’s Method with some great graphics as well.

It ends with a wealth of sources on complex numbers, fractals and Newton’s Method and the interrelations among them.

The other posts from his blog are also well worth reading.

## Graphing Complex Functions

In graphing real valued functions, each x value chosen is a real number, and each corresponding y value is also a real number.

Because both the x and y values are one-dimensional real numbers, the relationship can be graphed on a plane, showing the x and y values together only requires TWO dimensions.

We can use the graph of the function relationship between x and y values to solve equations.

0= x²+5x+3

we can graph the function

y=x²+5x+3

and look to see what value(s) of x make the y be zero.

When we graph the function we look for the x values where the graph crosses the x-axis.  This is because the value of y is zero along the x-axis.

So the values of x that make y be zero in the graph of (y=x²+5x+3) are approximately x≈-0.70 and x≈-4.31

Frequently, we see quadratic (parabolic) graphs that don’t intersect the x-axis at all:

This is because there are no real values for x that make y be zero.  In the case of the graph above (y=x²+5x+9) all the x values we see along the x-axis make y a positive number.

Does this mean that there aren’t any x values that make y be zero?

No.  If we use the quadratic formula, we can find that there are complex-valued roots that are solutions of the equation

0=x²+5x+9

In this case, (x≈-2.5±1.658i) are the complex values of x that make y zero.

If we could see x values on the Complex Plane, then we would see these roots on the graph, but, as I mentioned in a previous post, this creates some difficulties.

The picture from Wikipedia that I posted recently is a graph of a different function from the ones above.

Even though it’s not the same graph, it does show one method to try to get around the difficulties of graphing relationships in the Complex Plane.

The picture

shows the Complex Plane of all x values.  The y values are interpreted by the color and intensity of each x value on the Complex Plane.  The roots (and asymptotes) for the function in this picture are indicated by the points or holes or peaks (however you want to think of them) that we see in the picture.

I haven’t done enough research with this method of graphing to know all the details of how it is colored and how to tell the roots from the asymptotes, but I find it both visually and mathematically beautiful.

## Rational, Irrational and Complex

Roots of Polynomials

Rene Descartes determined that if there existed rational roots for a polynomial with integer coefficients, then these roots would be related to the leading coefiicient and constant term in the manner stated in the Rational Roots Theorem.  When I was in high school in the early 80s, we used this theorem to determine all possible rational roots and then used synthetic division to determine which ones actually were roots.  From there, you can decompose the polynomial into factors and try to determine any complex roots.

I still teach the Rational Roots Theorem, but make allowances for today’s technology.  Instead of asking the students to determine all possible rational roots and test them out, we graph the polynomial and use the calculator to determine the rational roots.  Then, we use these roots to break the polynomial down into prime factors, which can allow the students to determine complex roots that did not appear on the graph (I sometimes refer to the complex roots as Sir Not Appearing in This Film).

What if the roots aren’t rational? and other complications

The polynomials I use for exercises, quizzes and tests are set up so that each breaks down to a series of linear factors and one quadratic factor with complex roots, with all the factors having integer coefficients.

But – what if this isn’t the case, or what if there are irrational real roots?  How can we find the complex roots of a polynomial in these situations?

Answer: Newton’s Method.  Newton’s Method is fairly easy to understand in application to finding real roots on the Cartesian Plane, but it also works just as well to find complex roots.  Choosing various real and complex seed values for Newton’s Method leads to finding both the real and the complex roots.

Something very interesting about this process is that if we color the seed values from the complex plane based on which root they eventually lead to, the colored depiction of the complex plane that is produced appears fractal in nature.  Each collection of seed values that leads to the same root is said to lie in a particular Newton Basin.

Here is a great website on Newton Basins.

And another one here.

Here is a look at how they approach this topic at MIT.

## ORMATYC

I went to Lincoln City this past weekend for the ORMATYC Conference.  ORMATYC is the Oregon Mathematical Association of Two Year Colleges and is a part of the larger group AMATYC, the American Mathematical Association of Two Year Colleges.

Just about every year, we have a conference in Lincoln City – this is the fifth one I’ve attended.  It’s a great experience to get together with other community college math instructors from Oregon to talk about math and math education.  It’s a valuable forum to find out what other schools are doing in their math classes and how we compare with those other schools.

In attending this conference every year, I have learned more about both math and math education.  In some cases it was about how to present a particular topic in class, while in other cases it was something that provided additional background information about the topics I teach so that I can share these ideas with my students.

In addition to being exposed to new ideas about math and math education, another positive aspect of this conference is being part of a community.  After 5 years, I have gotten to know some of the other instructors and have a better idea about which talks to attend while I’m there.

This year, I saw Jim Ballard of OIT Klamath Falls give a talk on the mathematics of finance.  There was a lot of discussion about the current economic situation and he didn’t really get a chance to talk about the Black-Scholes equations which are somewhat controversial, but have been used in mathematical finance for over 20 years.  I wrote about math and finance in an earlier post.

I also attended a session with Ron Wallace of Blue Mountain CC about deciding which topics to teach and which to leave out in the math curriculum.  He asked if anyone there had used the quadratic formula in their lives outside of teaching in the past five years.  I was the only one to raise my hand.

I did use the quadratic formula a few years ago when my Mom asked me about the cost of Medicare Part D programs.  The formula for pricing in Medicare Part D is quadratic in that it initially becomes more expensive the longer you wait to enroll, but the money you save by not enrolling right away can offset the higher premiums you end up paying.

On Friday afternoon I went to a presentation by Art Peck of Lane CC.  I had seen his talk last year about the connection between the Fibonacci Sequence and the Mandelbrot Set, which was excellent.  This year, he talked about applications of mathematics to environmental problems, including alternative energy.  There is a lot of mathematics involved in scientific research that is focused on the environment.  For particular examples, he mentioned a textbook and companion website that have been developed and have some great application questions.

This is an important time for alternative energy generation and research directed at the environment in general.  I wrote an earlier post about the Solar Tres project.  The development of electric car motors and batteries has reached a point that production of “all-electric” car models is happening now.  One of my calculus textbooks has a cover page addressed to the instructor saying “The first person to invent a car that runs on water may be sitting right in your classroom.”

On Saturday morning, I saw a presentation by Geza Laszlo called “Rational Approximations of Roots of Polynomials.”  This is a very interesting topic.  It has connections to some of the material we cover in MTH 111 about roots of polynomials, but it is more closely related to the ideas we discuss in MTH 116 about using Newton’s method to approximate a square root.

Newton’s method uses calculus, but the method itself was known to the Greeks, even though they did not have formal knowledge of the methods of calculus.  The idea of approximating irrational numbers with rational numbers is also of great importance in constructing a musical scale.  Attempting to approximate (log3)/(log2) with a rational number determines how an octave will be separated into notes and how accurate the scale will be.