Back to MAIN
In the year 1834 Nikolaj Ivanovich Lobachevsky (1.Dec. 1792  24.Febr.1856) found a way to approximate the
roots of algebraic equations. This method has been discovered independently in the year 1837 by the German
mathematician Karl Heinrich Graeffe (7.Nov.1799  2.Dec.1873) and the French mathematician Germinal
Pierre Dandelin (12.Apr.1794  15.Febr.1847). We can see it today as a very convenient numerical method.
Before we start here, we should be aware of the fact that the equation:P(x) = x^{n}+a_{1}x^{n1}+a_{2}x^{n2}+ ... +a_{n}=0,
with the roots r_{1},r_{2}, ... ,r_{n} and a given symetrical polynomial F[x_{1},x_{2},...,x_{n}], we can determine the number
s = F[r_{1},r_{2},...,r_{n}] without solving our original equation P(x) = 0.
As a consequence  in case of a given equation: P_{1}(x)=a_{0}x^{n}+a_{1}x^{n1}+a_{2}x^{n2}+ ... +a_{n}=0, and its roots
r_{1},r_{2}, ... ,r_{n} we can find(without solving P_{1}) an other polynomial P_{k}(x)=a^{k}_{0}(xr^{k}_{1})(xr^{k}_{2})...(xr^{k}_{n}), eg which has
roots which are exactly the squares, cubes etc. of the roots of P_{1}(x).
Just as an example, if the roots of the (above given)polynomial P(x) are x_{1},x_{2},x_{3},x_{4},x_{5} then we can express the
sum of their 5^{th} powers as:(under the given index set {1,2,3,4,5})
S[x^{5}_{i}] := x^{5}_{1}+x^{5}_{2}+x^{5}_{3}+x^{5}_{4}+x^{5}_{5} ; following this notation, we can now deduct:
S[x^{4}_{i}]S[x_{i}] = S[x^{5}_{i}] + S[[x^{4}_{i}x_{j}];i < j] ==> S[x^{5}_{i}] = S[x^{4}_{i}]S[x_{i}]S[x^{4}_{i}x_{j};i < j]= a_{1}S[x^{4}_{i}]S[x^{4}_{i}x_{j};i < j], but
S[x^{3}_{i}]S[x_{i}x_{j};i < j] = S[x^{4}_{i}x_{j};i < j] + S[x^{3}_{i}x_{j}x_{k};i < j < k] ==> S[x^{4}_{i}x_{j};i < j] = a_{2}S[x^{3}_{i}]  S[x^{3}_{i}x_{j}x_{k};i < j < k], but
S[x^{2}_{i}]S[x_{i}x_{j}x_{k};i < j < k] = S[x^{3}_{i}x_{j}x_{k};i < j < k] + S[x^{2}_{i}x_{j}x_{k}x_{l};i < j < k < l] .. which means that
S[x^{3}_{i}x_{j}x_{k};i < j < k] = a_{3}S[x^{2}_{i}]  S[x^{2}_{i}x_{j}x_{k}x_{l};i < j < k < l] .. and finally
S[x_{i}]S[x_{i}x_{j}x_{k}x_{k};i < j < k < l] = S[x^{2}_{i}x_{j}x_{k}x_{l};i < j < j < l] + S[x_{i}x_{j}x_{k}x_{l}x_{m};i < j < k < l < m] ..and so
S[x^{2}x_{i}x_{j}x_{k}x_{l};i < j < j < l] = a_{4}S[x_{i}]  5a^{5} summarized as :
S[x^{5}_{i}] = a_{1}S[x^{4}_{i}]a_{2}S[x^{3}_{i}]a_{3}S[x^{2}_{i}]a_{4}S[x_{i}]5a_{5} and by setting q_{k}:=a^{k}_{1}+a^{k}_{2}+...+a^{k}_{n} we can reformulate it
as a general statement:
If the a_{i} are elementary symetrical functions of the variables x_{1},x_{2},...,x_{n}, then for all k < n+1 holds:
q_{k}+a_{1}q_{k1}+...+a_{k1}q_{1}+ka_{k} = 0


..and in the same way we would be able to show that if k > n
q_{k}+a_{1}q_{k1}+a_{2}q_{k2}...+a_{n}q_{kn}= 0


These both equations we know as Newton's recursion formula's . In the case n=4 we would obtain:
q_{1}+a_{1}=0,
q_{2}+a_{1}q_{1}+2a_{2}=0,
q_{3}+a_{1}q_{2}+a_{2}q_{1}+3a_{3}=0,
q_{4}+a_{1}q_{3}+a_{2}q_{2}+a_{3}q_{1}+4a_{4}=0,
q_{5}+a_{1}q_{4}+a_{2}q_{3}+a_{3}q_{2}+a_{4}q_{1}=0
q_{6}+a_{1}q_{5}+a_{2}q_{4}+a_{3}q_{3}+a_{4}q_{2}=0,
q_{7}+a_{1}q_{6}+a_{2}q_{5}+a_{3}q_{4}+a_{4}q_{3}=0, e.t.c. and consequently..
q_{1}=a_{1}, q_{2}= a^{2}_{1}2a_{2}, q_{3}=a^{3}_{1}+3a_{1}a_{2}3a_{3}
q_{4}= a^{4}_{1}4a^{2}_{1}a_{2}+4a_{1}a_{3}+2a^{2}_{2}4a_{4}
q_{5}=a^{5}_{1}+5a^{3}_{1}a_{2}5a^{2}_{1}a_{3}5a_{1}a^{2}_{2}+5a_{1}a_{4}+5a_{2}a_{3} e.t.c.
A small sparkling spinoff from all of this:
if we have P_{1}(x)=a_{0}x^{n}+a_{1}x^{n1}+a_{2}x^{n2}+ ... +a_{n}=0, and our roots r_{1},r_{2},...,r_{n}, then r^{2}_{1}+r^{2}_{2}+...+r^{2}_{n}=a^{2}_{1}2a_{2}
which means that if a^{2}_{1} <= 2a_{2}, then at least one pair of roots must be complex.(we assume also a_{n} not 0,
and n > 2)
One important remaining point here:
Lets once look again at our P_{1}(x)=a_{0}x^{n}+a_{1}x^{n1}+a_{2}x^{n2}+ ... +a_{n}=0, with the roots r_{1},r_{2},...,r_{n}, and that means :
P_{1}(x)=a_{0}(xr_{1})(xr_{2}) ... (xr_{n}), and therefore P_{1}(x)=(1)^{n}a_{0}(x+r_{1})(x+r_{2}) ... (x+r_{n}). What we look for is
a polynomial Q_{2}(x) having r^{2}_{1},r^{2}_{2},...,r^{2}_{n} as roots  without solving P_{1}(x)=0, of course.
But (1)^{n}P_{1}(x)P_{1}(x)=a^{2}_{0}(x^{2}r^{2}_{1})(x^{2}r^{2}_{2}) ... (x^{2}r^{2}_{n})=Q_{2}(z) with z=x^{2}, and by decomposing P_{1}(x)=H_{1}(x)+xH_{2}(x),
where H_{1}(x) consists of even exponents of x, and xH_{2}(x) of the odd ones, we can conclude that
P_{1}(x)=H_{1}(x)xH_{2}(x), eg:
Q_{2}(x)=(1)^{n}[H^{2}_{1}(x)x^{2}H^{2}_{2}(x)]


But now we are better prepared for our little rendezvous with an idea which now celebrates its 170^{th} birthday.
As a nature of the thing, we can ask us the question, if the polynomials Q_{2},Q_{4},Q_{8},Q_{16}..(having the 2^{n}th power
of the original polynomial as roots) can help us to find r_{1},r_{2},...,r_{n} in a numerical way. The answer to that
question is yes. Lets assume, we know all r_{i} and lets for a moment also assume they are all real and different,
so after reindexing we have: r_{1} > r_{2} > r_{3} > ... > r_{n1} > r_{n} .. so if we take Q_{2k} = a_{0,k}x^{n}+a_{1,k}x^{n1}+...+a_{n,k}=0
and the known relations we see that:
a_{1,k}/a_{0,k} = r^{2k}_{1}+r^{2k}_{2}+ ... +r^{2k}_{n} = r^{2k}_{1}[1+(r^{2k}_{2}/r^{2k}_{1})+...+(r^{2k}_{n}/r^{2k}_{1})]
+a_{2,k}/a_{0,k} = r^{2k}_{1}r^{2k}_{2}+r^{2k}_{1}r^{2k}_{3} + ... + r^{2k}_{n1}r^{2k}_{n} = r^{2k}_{1}r^{2k}_{2}(1+r^{2k}_{3}/r^{2k}_{2} + ... + r^{2k}_{n1}r^{2k}_{n}/r^{2k}_{1}r^{2k}_{2})
a_{3,k}/a_{0,k} = r^{2k}_{1}r^{2k}_{2}r^{2k}_{3}+r^{2k}_{1}r^{2k}_{2}r^{2k}_{4} + ... + r^{2k}_{n2}r^{2k}_{n1}r^{2k}_{n} = r^{2k}_{1}r^{2k}_{2}r^{2k}_{3}(1+(r^{2k}_{4}/r^{2k}_{3}) + ... + (r^{2k}_{n2}r^{2k}_{n1}r^{2k}_{n}/ r^{2k}_{1}r^{2k}_{2}r^{2k}_{3}))
....
..etc..
....
(1)^{n}a_{n,k}/a_{0,k} = r^{2k}_{1}r^{2k}_{2} ... r^{2k}_{n1}r^{2k}_{n}
.. with other words...
a_{1,k}/(a_{0,k}r^{2k}_{1})=1+(r^{2k}_{2}/r^{2k}_{1})+...+(r^{2k}_{n}/r^{2k}_{1})
a_{2,k}/(a_{1,k}r^{2k}_{2})=(1+r^{2k}_{3}/r^{2k}_{2} + ... + r^{2k}_{n1}r^{2k}_{n}/r^{2k}_{1}r^{2k}_{2}) / 1+(r^{2k}_{2}/r^{2k}_{1})+...+(r^{2k}_{n}/r^{2k}_{1})
a_{3,k}/(a_{2,k}r^{2k}_{3})=(1+(r^{2k}_{4}/r^{2k}_{3}) + ... + (r^{2k}_{n2}r^{2k}_{n1}r^{2k}_{n}/ r^{2k}_{1}r^{2k}_{2}r^{2k}_{3}))/1+r^{2k}_{3}/r^{2k}_{2} + ... + r^{2k}_{n1}r^{2k}_{n}/r^{2k}_{1}r^{2k}_{2}
..etc
a_{n,k}/(a_{n1,k}r^{2k}_{n})=1/1+(r^{2k}_{2}/r^{2k}_{1})+...+(r^{2k}_{n}/r^{2k}_{1})
But as r^{2k}_{i+1}/r^{2k}_{i} < 1, all a_{i+1,k}/(a_{i,k}r^{2k}_{i+1}) must converge to 1 if i > infinity. That means for "larger" values k,
we have
r^{2k}_{i+1} ~ a_{i+1,k}/a_{i,k}


It is absolutely clear, that we could have taken any exponent  not just only powers of 2, we took it for practical
reasons
One possible solution using k4 can be:
/some preliminaries
mod:{xy xbar x}
dix:{x@&~(!#x) in y}
f:{dix[x;&mod[(!#x);2]]}
xexp:{exp y*log x}
xe2:{xexp[2f;x]}
abs:{xx}
rot:{,/(0;mod[x;#y])_y}
q:{+/rot'[!#x;(,/'(s#'x) *\:+,x),\:(s+12*s:#x)#0]}
/lobachevsky .. just the correct sign needs to be verified after run .. a trivial K exercise
lb:{xexp[(abs@  %/(1,1) _\: x {f@ (q@ 1f*x*~b)  q@ 1f*x*b:mod . ((!#x);2)}/1f*y);%xe2 x]}
Sample 1: x^{5}2x^{4}19x^{3}+13x^{2}+36x5 .. lb . (4;1 2 19 13 36 5) returns:
x_{1}=5.001294, x_{2}=3.548031, x_{3}= 1.675143, x_{4}= 1.258001, x_{5}=0.133711
..the exakt solutions are (6 digits)
x_{1}=5.000000, x_{2}= 3.548948, x_{3}=1.674056, x_{4}= 1.258819, x_{5}=0.133711
..we see here that the polynomials having the 16^{th} power as roots of the original polynomial(eg.. we handle
here polynomials of degree 80) bring us actually very close to the real world..as we said, just ignoring the sign.
The precision (although very convincing in a normal case) is not the real strength of this method. The advantage
of the brilliant Lobachevsky approach is clearly, that we get all solutions in one go.
By definition, the assumption of strictly decreasing absolute values of the roots excludes the search for complex
solutions
If we are interested in the search for the complex roots  we slightly change our approach .. Just as an
illustrative display for a cubic polynomial(..and real coefficients), having one pair of complex solutions:
We assume that, r_{1}=Re^{it} and r_{2}=Re^{it} and r_{1}=r_{2}>r_{3},
so: r^{k}_{1}+r^{k}_{2}+r^{k}_{3}=R^{k}(e^{ikt}+e^{ikt})+r^{k}_{3}=R^{k}(2cos kt + r^{k}_{3}R^{k})=a_{1,k}/a_{0,k}
and
a_{2,k}/a_{0,k}=r^{k}_{1}r^{k}_{2}+r^{k}_{1}r^{k}_{3}+r^{k}_{2}r^{k}_{3}=R^{2k}[1+2(r_{3}/R)^{k}cos kt] and a_{3,k}/a_{0,k} = r^{k}_{1}r^{k}_{2}r^{k}_{3} = R^{2k}r^{k}_{3}
(.. in case of r_{1}=r_{2}<r_{3} we would take a_{1,k}/a_{0,k}=r^{k}_{3}[1+2(R/r_{3})^{k}cos kt]
and a_{2,k}/a_{0,k}=r^{k}_{3}R^{k}(2cos kt+(R/r_{3})^{k}] and a_{3,k}/a_{0,k} = R^{2k}r^{k}_{3}..)
So..a_{3,k}/a_{2,k} ~ r^{k}_{3} as (r_{3}/R)^{k} goes to 0 if k goes to infinity, and a_{1,k}/a_{0,k} ~ r^{k}_{3}, and a_{2,k}/a_{0,k}~R^{2k}
Sample 2: P(x) = x^{3}+4x^{2}2x20=0, by taking Q_{16}(z)=z^{3}8.446003*10^{7}z^{2}+1.000553*10^{16}z6.5536*10^{20}
, which means R~3.162332 and r_{3}~1.999931,(the correct figures are r_{3}=2 and R=3.162278)
Based on the knowledge of r_{3}=1.999931 and that r_{1}+r_{2}+r_{3}=4 follows...that cos t = 0.5R^{1}(5.999931)
So, we obtain (as sign is not determined) t = 2.819756 resp. t = 0.3218366 ... a verification would tell us,
that the first solution is the correct one., So r_{1}=3+i and r_{2}=3i.
One friendly hint here: in case of cubic polynomial with only real solutions, all polynomials Q_{2k}(x)
must have positive roots, which means their coefficients must have the sign pattern ( +  +  ), which
is not the case in our example, consequently our cubic polynomial must have complex solutions.
It is by definition clear, that polynomials with real solutions having the same absolute value cannot be
handled by this method but those are just exceptional cases.
Back to MAIN
©++ MILAN ONDRUS