Is this polynomial root finding algorithm below known, and under what conditions for the choice of polynomial coefficients does it find at least one root?
Description of the algorithm:
- Consider the polynomial:
$$a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 = 0$$
- Replace $x^n$ with $y^n$ so that the expression becomes:
$$a_n y^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 = 0$$
- Solve for $y$ and you will get:
$$y_1 = \frac{(-1)^{1}(-1)^{\frac{1}{n}}(a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
$$y_2 = \frac{(-1)^{2}(-1)^{\frac{2}{n}}(a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
$$y_3 = \frac{(-1)^{3}(-1)^{\frac{3}{n}}(a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
$$\vdots$$
$$y_n = \frac{(-1)^{n}(-1)^{\frac{n}{n}}(a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
- Replace $y_1...y_n$ with $x_1...x_n$ and replace all $x$ in the $n$-th equation with $x_n$:
$$x_1 = \frac{(-1)^{1}(-1)^{\frac{1}{n}}(a_{n-1} x_1^{n-1} + \cdots + a_2 x_1^2 + a_1 x_1 + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
$$x_2 = \frac{(-1)^{2}(-1)^{\frac{2}{n}}(a_{n-1} x_2^{n-1} + \cdots + a_2 x_2^2 + a_1 x_2 + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
$$x_3 = \frac{(-1)^{3}(-1)^{\frac{3}{n}}(a_{n-1} x_3^{n-1} + \cdots + a_2 x_3^2 + a_1 x_3 + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
$$\vdots$$
$$x_n = \frac{(-1)^{n}(-1)^{\frac{n}{n}}(a_{n-1} x_n^{n-1} + \cdots + a_2 x_n^2 + a_1 x_n + a_0)^{\frac{1}{n}}}{(a_n)^{\frac{1}{n}}}$$
- Use $x_n=0$ as the seed point and iterate each equation in 4. infinitely many times. In the program below they are iterated 4000 times.
It then appears that when iterating the equations in 4. at least one of them will converge to a zero.
(*start*)
(*Mathematica 8*)
Clear[x, polynomial, X, y, polynomialdegree];
polynomialdegree = 7;
ycoefficient = RandomInteger[{-4, 4}]; polynomial =
Sum[RandomInteger[{-4, 4}]*x^n, {n, 0, polynomialdegree - 1}] +
If[ycoefficient == 0, -1, ycoefficient]*y^polynomialdegree;
Print["The polynomial is: ", polynomial];
nn = 4000;
Do[Clear[x, X, y]; X = y /. Solve[polynomial == 0, y][[i]];
x = 0;
Table[x = N[Round[X, 10^-30], 30], {n, 1, nn}];
y = x;
Print["x = ", x, " polynomial value at x is: ", polynomial];, {i, 1,
polynomialdegree}]
(*end*)
What I am really asking is to find a polynomial such that the proposed root finding algorithm fails.
Edit 10.9.2016:
This version of the algorithm works for complex numbers:
(*start*)
(*Mathematica 8*)
Clear[x, polynomial, X, y, polynomialdegree];
polynomialdegree = 5;
ycoefficient = -Rationalize[RandomComplex[{-10 - 10*I, 10 + 10*I}],
0]; polynomial =
Sum[Rationalize[RandomComplex[{-10 - 10*I, 10 + 10*I}], 0]*x^n, {n,
0, polynomialdegree - 1}] +
If[ycoefficient == 0, -1, ycoefficient]*y^polynomialdegree;
Print["The polynomial is: ", polynomial];
nn = 8000;
Do[Clear[x, X, y];
X = y /. Solve[polynomial == 0, y, WorkingPrecision -> 100][[i]];
x = 10;
Table[x = N[Round[X, 10^-30], 30], {n, 1, nn}];
y = x;
Print["x", i, " = ", x, " polynomial value at x", i, " is: ",
polynomial];, {i, 1, polynomialdegree}]
(*end*)