Mar

21

An accessible Calculus book and Benjamin Franklin’s secret passion

By Antonio Cangiano. Filed under Suggested reading | 5 Comments 

It has been a while since my last book recommendation. I’ll take the opportunity of the Easter longer weekend to write about two books that were recently released and I just finished reading. The first one is an atypical Calculus book, while the second one is a popular mathematics title which is historical and biographical in nature.

The first book is The Calculus Lifesaver: All the Tools You Need to Excel at Calculus.

Before I even start talking about the actual book, let me just tell you that this is a steal. I don’t know what the publisher was thinking, but a 750 page, recently published book on Calculus never sells for such a low price. On Amazon it sells for $16, which is a ridiculously low price for this 5 star tome. The average Calculus book is far from cheap, so this excellent guide is a pure bargain. Now, let’s talk about the content of the book.

I’m very exigent when it comes to Calculus books and usually like a very formal and rigorous style. Most people don’t. Many tend to like accessible books that speak to them in plain English. And this book is marketed as such. This is supposed to be an extra aid, on top of a regular textbook, to make Calculus more accessible. However, it stands on its own, thanks to its comprehensiveness and clarity. If commonly adopted Calculus books puzzle you, or if you are studying on your own, this is the book for you. Every step is clearly explained and it doesn’t fail when it comes to covering all the pre-requisites/fundamentals. Thanks to its style and approach, pretty much anyone who’s willing to learn, will. I’d even recommend it to high school students who wish to learn more about this subject, because I don’t think they would have any trouble following along. The tone is informal, friendly and often even funny, making it one of the least boring math books I’ve ever read. I highly recommend it to those who are struggling and would like to really understand the subject.

The second book is Benjamin Franklin’s Numbers: An Unsung Mathematical Odyssey.

Most geeks admire Ben Franklin, and not only for patriotic reasons. He was a brilliant, vibrant mind who made contributions to several fields. There isn’t a lack of biographies about the man. Or even good ones at that. What this short (and sweet) book does though, is to cover Franklin as a mathematician, a side of the genius that is often hidden or disputed. This hardcover focuses on Magic Squares and Franklin’s contribution to this field, even though he wrongly considered them as enjoyable, but useless in practice. Benjamin Franklin’s Numbers: An Unsung Mathematical Odyssey is filled with mathematical puzzles and will be a pleasure to read for those who can appreciate small challenges and the historical importance of Pasles’ research.


If you enjoyed this post, then make sure you subscribe to our RSS Feed.

Mar

6

Polynomial Root-finding with the Jenkins-Traub Algorithm

By David Binner. Filed under Applied Math, Tutorial | 3 Comments 

The Jenkins-Traub Algorithm is a standard in the field of numerical computation of polynomial roots, fundamentally developed as a numerical algorithm specifically for the task of computing polynomial roots. In other words, (i) because it was planned from the outset for numerical purposes rather than being simply an adaptation of an analytic formula, it is extremely robust, effectively minimizing the effects of computer round-off error, while (ii) also being extremely efficient compared to more general methods not written specifically for the task of computing polynomial roots; in fact, the algorithm converges to polynomial roots at a rate better than quadratic. Furthermore, since being introduced over thirty years ago, the algorithm has had time to be rigorously tested and has successfully proven its quality; as a result, it has gained a wide distribution as evidenced by its incorporation in commercial software products and the posting on the NETLIB website of source code for programs based on the algorithm.

An Introduction to the Field of Root-finding

Given a function which is defined in terms of one or more independent variables, the roots (also called zeros) of the equation are the values of the independent variable(s) for which the function equals 0:

\displaystyle f(z1, z2, z3, z4, z5, . . . ) = 0

Note that, in general, the z values are complex numbers, comprised of real and imaginary components (indicated by the i): z = x + iy.

Consider the following equation:

\displaystyle 2z_{1} + 0.5z_{2}z_{3} + 3.14z_{4}^{2}+1.414\ln(z_{5})=23

The values of z_{1}, z_{2}, z_{3}, z_{4} and z_{5} which satisfy this equation may not be possible by analytical methods, so the equation would be rearranged into the following form:

\displaystyle 2z_{1} + 0.5z_{2}z_{3} + 3.14z_{4}^{2}+1.414\ln(z_{5}) - 23 = 0

which is of the form

\displaystyle f(z1, z2, z3, z4, z5) = 0

Once in this form (the standard form), solving the original equation becomes a matter of finding the z_{1}, z_{2}, z_{3}, z_{4} and z_{5} values for which f equals 0, and well-developed fields of mathematics and computer science provide several root-finding techniques for solving such a problem. Note that since the theme of this article is polynomial root-finding, further examples will focus on single-variable equations, specifically, polynomials.

Analytical Root-finding Techniques

Consider the following quadratic equation:

\displaystyle f(z) = z^{2} + z - 2

This equation is a second-degree polynomial–the highest power applied to the independent variable is 2. Consequently, this equation has two roots; an n-degree polynomial equation has n roots.

Because the equation is a simple polynomial, a first approach to finding its zeros might be to put the equation into the form (z - \alpha_{1})(z - \alpha_{2}) and make a few educated guesses; a person could quickly determine that \alpha_{1} = 1 (a strictly real result) is one root of this equation. This root could then be divided out of the original polynomial

\displaystyle \frac{(z^{2} + z -2)}{(z-1)} = (z+2)

to yield the second root: \alpha_{2} = -2.

In this simple example, the two roots were found easily; the second root was found immediately after the first one was known. However, in most real-world problems the roots of a quadratic are not found so easily. Furthermore, in problems where the original polynomial is of degree greater than two, when one root is found, the other roots do not follow immediately — more sophisticated techniques are required.

Among the techniques available are analytical ones, in other words, techniques that yield explicit, algebraic results. For example, in the case of a quadratic equation, explicit expressions for the two roots are possible via the Quadratic Formula: once a quadratic equation is arranged into the standard form

\displaystyle \bold{a}z^{2} + \bold{b}z + \bold{c} = 0

(a, b and c are known constants), the two roots are found via the Quadratic Formula:

\displaystyle \alpha = \frac{{ - b \pm \sqrt {b^2 - 4ac} }}{{2a}}

The quantity within the square root sign (b^2 - 4ac) is called the discriminant and determines whether the solution is complex or strictly real. If the discriminant is less than 0, the numerator contains an imaginary component and the roots are, therefore, complex. If the discriminant is greater than or equal to 0, the solutions are real. In fact, if the discriminant is 0, the two roots are real and equal:

\displaystyle \alpha_{1} = \frac{{ - b + \sqrt {0} }}{{2a}} = \frac{-b}{2a}

\displaystyle \alpha_{2} = \frac{{ - b - \sqrt {0} }}{{2a}} = \frac{-b}{2a}

In addition to the Quadratic Formula for quadratic equations, analogous formulae exist for polynomials of degree three and four. However, for polynomials of degree five and higher, analytical solutions are not possible (except in special cases), only numerical solutions are possible.

Numerical Root-finding Techniques

For the multitude of real-world problems that are not amenable to an analytical solution, numerical root-finding is a well-developed field offering a wide variety of tools from which to choose; many computer programs written for the computation of roots are based on algorithms that make them applicable to the computation of roots of functions in addition to polynomials, and virtually all of them employ an iterative approach that terminates once the desired degree of tolerance has been achieved. For example, the bisection method is a simple and reliable method for computing roots of a function when they are known ahead of time to be real only. The algorithm starts with the assumption that a zero is somewhere on a user-supplied interval [a,b]. In other words, the function value f(a) is of the opposite sign of f(b) – in going from a to b, f either goes from being positive to being negative, or it goes from being negative to being positive. A point, m, in the middle of the interval [a,b] is then selected. The function is evaluated at point m: f(m). If the sign of f(m) is the same as the sign of f(a), the desired zero is not in the interval [a,m]. In this case, the interval is cut in half and the new interval becomes [m,b]. On the other hand, if the sign of f(m) is not the same as the sign of f(a), the desired zero is in the interval [a,m]. In this case, the interval is cut in half and the new interval becomes [a,m]. This process is repeated until either the interval converges to a desired tolerance or a value of f is found that is within an acceptable tolerance, in which case the value of z at this point is the value returned by the program as the root.

In addition to the bisection method, more elegant–and faster converging–techniques are available: the False Position method, Brent’s method, the Newton-Raphson method, the secant method, and others. The Newton-Raphson method uses the function and its derivative to quickly converge to a solution. This method is good for situations in which the derivatives are either known or can be calculated with a low computational cost. In other situations, the cost of computing derivatives may be too high. The secant method, by comparison, does not require the use of derivatives, but the calculation of each iterate requires the use of the two previous iterates and does not converge to a solution as quickly as the Newton-Raphson method. In some situations, this method, too, may be deemed impractical. Usually, when some thought is given to a problem, a particular technique can be applied to it that is more appropriate than another. In fact, for some problems, one technique may fail to find a solution at all, whereas another technique will succeed. For other problems, several techniques may, indeed, be able to solve the problem and the numerical analyst may select the one that is simply more computationally efficient.

The Jenkins-Traub Algorithm

The field of numerical root-finding is so well-developed that the use of a good-quality numerical program is recommended — when numerical results are sought — even when an analytical solution to a problem is known. In other words, even though an analytical solution to, say, the quartic equation exists, writing a computer program that simply implements the textbook formula is not recommended; computer round-off errors often render results of such programs meaningless. The use of a robust numerical program, based upon sound theory and an excellent algorithm, and coded to thoroughly deal with computer round-off errors, is the recommended action. The Jenkins-Traub Algorithm is such an algorithm; it is a three-stage, extremely effective, globally convergent algorithm designed specifically for computing the roots of polynomials.

Stage One is the “No Shift” stage; the main purpose of this stage is to accentuate the smaller zeros. The search for a zero is started by taking an initial guess of 0 for a fixed number, M, of iterations (M is usually assigned the value 5 on the basis of numerical experience(1)).

Stage Two is the “Fixed Shift” stage, the purpose of this stage is to separate zeros of equal or almost equal magnitude. As a starting point in this stage, the following value is used:

\displaystyle s = \beta e^{i\theta}

\beta is a lower bound on the magnitudes of the probable zeros in the cluster. \theta could be taken at random, since the cluster could be anywhere in the complex plane; however, in practice \theta is usually initialized to 49°, putting s near the middle of the first quadrant of the complex plane. After a certain number of iterations, if s does not converge to a root, s is assigned a new value by increasing \theta by 94°. Repeated attempts would have the search for a root start with points in all four quadrants of the complex plane until the search is returned to the first quadrant. Should the search, indeed, return to the first quadrant, successive cycles start at points 16° away from the starting point of the preceding cycle.

Stage Three is the “Variable Shift” stage, which is terminated when the computed value of the polynomial at a possible zero is less than or equal to a specified bound.

In addition to the three fundamental stages around which it was developed, the Jenkins-Traub Algorithm incorporates several other techniques for making it as effective as possible. One of those techniques is deflation of the polynomial by synthetic division each time a root is found. Consider the following monic polynomial:

\displaystyle z^n + \bold{a_{n-1}}z^{n-1}+ \bold{a_{n-2}}z^{n-2}+\bold{a_{n-3}}z^{n-3} + \ldots + \bold{a_{1}}z + \bold{a_0} = 0

The \bold{a_i} are known constants and, in general, are complex. Now say the root z_1 (z_1 = x + iy) has been found. Synthetic division would be employed to divide that root out of the original polynomial:

\displaystyle \frac{z^n + \bold{a_{n-1}}z^{n-1}+ \bold{a_{n-2}}z^{n-2}+\bold{a_{n-3}}z^{n-3} + \ldots + \bold{a_0}}{z-z_1}

to yield

\displaystyle \bold{b_{n-1}}z^{n-1}+ \bold{b_{n-2}}z^{n-2}+\bold{a_{b-3}}z^{n-3} + \ldots + \bold{b_0}

The \bold{b_i} are new constants. The root-finding process is then repeated on this new–simpler–polynomial. As each root is found, the polynomial becomes successively simpler and each successive iteration of the algorithm involves, in general, fewer computations.

For polynomials whose coefficients are real only, when a complex root is found (z_1 = x + iy), an additional benefit arises: that root’s complex conjugate is also a root (z_2 = x - iy). In other words, two roots are computed — and the polynomial can be deflated by two degrees — in a single iteration of the algorithm. Furthermore, this deflation involves real only, rather than complex, operations; the product of these two roots is a real quadratic equation:

\displaystyle (z-z_1)(z - z_2) = z^2 - 2xz + (x^2 + y^2)

In this case, synthetic division is employed on the polynomial as follows:

\displaystyle \frac{z^n + \bold{a_{n-1}}z^{n-1}+ \bold{a_{n-2}}z^{n-2}+\bold{a_{n-3}}z^{n-3} + \ldots + \bold{a_0}}{z^2 - 2xz + (x^2 + y^2)}

In fact, for computing roots of polynomials which have only real coefficients, a modified version of the Jenkins-Traub Algorithm has been written which incorporates several features that take advantage of the characteristics of real-only polynomials to yield significant decreases in program execution time; “If the complex and real algorithms are applied to the same real polynomial, the real algorithm is about four times as fast.”(4)

The Jenkins-Traub Algorithm not only deflates the polynomial as roots are computed, it computes the roots roughly in order of increasing magnitude. This approach is taken because deflation of a polynomial can be unstable unless done by factors in order of increasing magnitude. By starting the search for roots with an initial guess of 0, as is done in Stage One, roots are, indeed, computed roughly in order of increasing magnitude, the factors by which the polynomial is successively deflated are roughly in order of increasing magnitude — the deflation of the polynomial is made quite stable.

As a quick check of the effectiveness of the Jenkins-Traub Algorithm, consider a contrived numerical example:

\displaystyle f(z) = (z - 1.001)(z - 0.998)(z - 1.00002)(z - 0.99999)

The roots of this polynomial are very close and should test how effectively the algorithm discerns near-multiple roots:

1.001
0.998
1.00002
0.99999

In addition, the polynomial is real-only so that readers may confirm the results with a free, ready-to-use, online Javascript program (URL given below).

Expanded, the test polynomial becomes

\displaystyle \displaystyle z^{4} - 3.99901z^{3} + 5.9970279898z^{2} - 3.9970259795802z + 0.9990079897802004

and the solutions computed by the Javascript root-finder follow:

0.9980051486669109
0.9998618452719573
1.0001539207016332
1.0009890853594987

The program, in fact, did a very good job:

  1. no errors were returned,
  2. no erroneous imaginary components were found,
  3. four distinct roots were computed, and
  4. the computed roots are extremely close to the exact roots (round-off errors are unavoidable).

Conclusion

Since its introduction in 1969 (in Michael Jenkins’ PhD thesis) the Jenkins-Traub Algorithm has been rigorously tested and has proven itself as an excellent algorithm for the computation of the roots of polynomials. It is extremely robust, is globally convergent for any distribution of zeros, and converges at a better than quadratic rate. Attesting to its high quality is the fact that source code for programs (written in FORTRAN) based on the algorithm have been posted on the NETLIB site, a repository of high-quality numerical programs; the complex coefficient version is posted as CPOLY (http://www.netlib.org/toms/419) and a real coefficient only version has been posted as RPOLY (http://www.netlib.org/toms/493). Translations into C++ and Javascript are also available; for example, Polynomial Root-finder (http://www.akiti.ca/PolyRootRe.html) is a Javascript translation of RPOLY and has been successfully tested with data published in Jenkins’ PhD thesis. In addition, the algorithm is incorporated in commercial software products (i.e. Mathematica). The proven effectiveness of the Jenkins-Traub Algorithm and its wide-spread distribution make it an extremely important tool in the toolbox of numerical analysts.

References

  1. “A First Course in Numerical Analysis: Second Edition”
    Anthony Ralston and Philip Rabinowitz
    McGraw-Hill Book Company
    New York
    1978
  2. “Numerical Methods and Software”
    David Kahaner, Cleve Moler, Stephen Nash
    Prentice-Hall, Inc.
    Englewood Cliffs, New Jersey
    1989
  3. “Numerical Recipes. The Art of Scientific Computing.”
    William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling
    Cambridge University Press
    New York
    1986
    (3rd edition now available.)
  4. Wikipedia
    Jenkins-Traub Algorithm for Polynomial Zeros
  5. Jenkins, M.A. Three-stage variable-shift iterations for the solution of polynomial equations with a posteriori error bounds for the zeros. Diss., Rep. CS 138, Comput. Sci.
    Dep., Stanford U., Stanford, Cal., 1969.

This article was written by David Binner. You can visit his math site at http://akiti.ca. If you’d like to write for Math-Blog.com, please email us at submissions@math-blog.com.


If you enjoyed this post, then make sure you subscribe to our RSS Feed.

Jan

23

Getting Math help in realtime

By Antonio Cangiano. Filed under Math Websites | 1 Comment 

Chances are that in the process of learning (or re-learning) mathematical concepts you will often find yourself in need of some clarification. That’s normal and nothing to be ashamed of. It actually means that you are absorbing something new and challenging. This can become an issue, particularly if you are self-taught and therefore don’t have the help of a “formal” teacher to give you authoritative answers. Sometimes you can find clarification along the way as you learn more about a given topic. Other times you are stuck with an exercise, but are still able to verify the solution with the help of a CAS. But what happens when you really have questions and you can’t find answers on your own?

Sure you can Google and with a bit of luck and skill find a helpful page. You may even decide to ask your question in a forum or in a proper newsgroup. However none of these resources are particularly interactive. There are many advantages which derive from a direct “realtime” conversation with other mathematically inclined people who are ready to provide assistance. There is an excellent Math chat that you can join if you want to ask for advice or get help on any mathematical subject. Below you’ll find the details needed to access it from your IRC client:

Server: irc.freenode.net
Channel: #math

If you are new to IRC and don’t have a client, you can use this web based interface to access it. In general though I do advise that you get a good client and familiarize yourself with the system. These are a few free clients that I recommend:

Windows: XChat 2
Mac OS X: Colloquy
Linux: XChat

Be friendly and respectful, don’t expect to be spoon-fed, and you’ll find this an invaluable resource. Occasionally you may even spot me there. :)


If you enjoyed this post, then make sure you subscribe to our RSS Feed.

← Previous Page — Next Page →