Wednesday, June 16, 2010

Roots of polinomials

Альбом: Math

Mathworld article about polynomial roots contains an interesting idea. Consider polynomials of some order N with coefficients ±1:

P(x) = xN ± xN-1 ± xN-2 ± ... ± 1.

Apparently, there are 2N-1 different polynomials of order N. What are their roots look like on a complex plane? Picture below shows roots (white points) of all 16 polynomials of the 5th order:

But what if we take polynomials of the higher power?.

Picture at the top is the answer. If shows all roots of the all ±1 polynomials of order 21. there is 220*21 = 22'020'096 roots in total, so most of them are indistinguishable. Areas, where roots are denser are brighter. Bright horizontal line in the center, corresponds the real roots.

This root amp do not change appearance significantly with the order: increasing order only makes it more detailed and slightly changes size of the pinned-out black areas on the main circle.

Additionally to the obvious horizontal and vertical symmetry, this image also symmetric relative to the inversion, because if P(x) is a ±1 polynomial of order N, then xNP(1/x) is also ±1 polynomial, and its roots are inverse of the original ones.
The picture has obviously fractal nature, and similar to the IFS fractals. Here is zoom-up of the side:
Альбом: Math

Saturday, April 3, 2010

Nelder-Mead fractals

Nelder-Mead method is a commonly used numeric method for solving optimization problems in several dimensions. Like many other iterative methods, it can produce interesting fractal images.
Like almost any numeric method for approximate solution, Nelder-Mead method requires the initial approximation to be specified. Speaking more precisely, for N-dimensional problem, this method requires N+1 initial point. Particularly, for 2-dimensional problems, 3 points must be specified.
In the cases, when the problem has several solutions, choice of the initial approximation determines (in some unpredictable way), which solution will be found, and some choices can give no convergence and no solution at all.
How initial choice relates to the convergence speed? The above picture shows that this relation is not an obvious one. Here is the recipe to obtain this picture:
  • Consider the problem of minimizing the famous Rozenbrock banana function using Nelder-Mead algorithm.
  • Use the following initial points: P1 = {0,-1}, P2={0,1}, and solve the problem for every point P3={x,y} withing the picture plane.
  • Count, how many steps method would require to reach to the minimum {1,1} with some precision.
  • Paint the pixels on the plane with different colors, according to the number of steps.
Here are more samples.
Minimizing the Rozenbrock function:
Альбом: Math

Zoomed fragment of the above:
Альбом: Math

Function with two minimums: f(x,y)=((x-1)2+y2)((x+1)2+y2)
Альбом: Math

Simple function with 1 minimum at (0,0): f(x,y) = x2+y2

Альбом: Math