Your Roots Are Showing

An exploration of polynomial roots and pretty fractals

Polynomials

Polynomials are a function of the form a_0 + a_1x + a_2x^2 + ... + a_nx^n, a_n \neq 0

e.g. x+5 = y

images/heart.jpg

Ok, so what's a root?

The root of a polynomial p is a value a such that p(a) = 0.

e.g. The root of x+5 = 0 is -5, because the expression is only true if we set x equal to -5.

images/carrot.jpg

Why are these a big deal?

It's often handy to know for what values a function will evaluate to 0. As a simple example, the trajectory of a projectile can be modelled with a quadratic equation, and the roots will tell you where the projectile will hit the ground.

More useful, factoring equations is at the heart of RSA, a widely use cryptographic scheme.

More interesting, it's used to find the eigenvalues of a matrix.

Multiplicities

The number of times a polynomial has a root at a given point.

e.g. (x+1)(x+1)(x+1) = x^3 + 3x^2 + 3x + 1 has multiplicity 3 at x = -1.

Bounds on Roots

The one I understand best: x < max(a_i) (Cauchy)

Wikipedia's answer

Easy Roots

Easy Roots

images/cubic.gif

Easy Roots

images/quartic-formula.png

The problem:

In 1824, Niels Henrik Abel (with help from LaGrange and Ruffini) proved that it was not possible to algebraically find the roots of polynomial of degree greater than 5.

Other Possibilities:

Newton's Method

The basic idea: x_{n+1} = x_n + \frac{f(x_n)}{f'(x_n)}

images/NewtonRGB.jpg

Fixed Point Iteration

x_{n+1} = g(x_n) where g(x_n) = x_n - \frac{f(x_n)}{f'(x_n)}

images/cobweb.gif

Secant

Draw a secant line between a, b | a< \alpha, b> \alpha , and set x-axis intercept as new a.

Bisection

Choose values a, b | a < \alpha, b> \alpha, determine whether root is above or below \frac{a-b}{2}, and then set \frac{a-b}{2} to be the new a or b.

Root Density Plot

images/deg5.png

Mandelbrot Set

The set of complex numbers c such that z_{n+1} = {z_n}^2 + c remains bounded (doesn't diverge under iteration)(I think)

images/mandelbrot.jpg

Problem Conditioning

Finding polynomial roots is an ill-conditioned problem. This means that small errors can dramatically affect results.

Wilkinson's Polynomial

images/wilkinson.png

In plain english: by creating a polynomial (x-1)(x-2)(x-3) ... (x-n), we know that it has roots at the integers up to n.

images/wilkinson-expanded.png

Why is this hard?

As we've seen, finding roots is really more of an art than a science.

Questions?