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

## 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.

## 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)

## Easy Roots

• Linear: For a_1x + a_0 = 0 x = \frac{-a_0}{a_1}
• Quadratic: x = \frac{-a_2 \pm \sqrt{a_2 - 4*a_1*a_3}}{2*a_1}

## 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
• Fixed Point Iteration
• Secant Method
• Bisection

## Newton's Method

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

## Fixed Point Iteration

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

## 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.

## 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)

## Problem Conditioning

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

## Wilkinson's Polynomial

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.

## Why is this hard?

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