Lobachevskii method

Graeffe method, Dandelin method

A method for simultaneously calculating all roots of a polynomial. Suppose that the roots $ r _ {1} \dots r _ {n} $ of the polynomial

$$ \tag{1 } f ( z) = a _ {0} z ^ {n} + \dots + a _ {n-1} z + a _ {n\ } = $$

$$ = \ a _ {0} ( z - r _ {1} ) \dots ( z - r _ {n} ) ,\ a _ {0} \neq 0, $$

satisfy the inequalities

$$ \tag{2 } | r _ {1} | \gg \dots \gg | r _ {n} | . $$

As approximations to the roots one can take the ratios $ a _ {i} / a _ {i-1} $, $ i = 1 \dots n $.

Now suppose that the roots of $ f ( z) $, although not satisfying (2), are all distinct in absolute value. The Lobachevskii method consists in applying to the equation $ f ( z) = 0 $ the process of squaring, which after sufficiently many repetitions leads to an equation with roots satisfying (2). Squaring consists in going over from a polynomial $ f _ {k} ( z) $ to a polynomial $ f _ {k+1} ( z) $ of the same degree but with as roots the squares of the roots of $ f _ {k} ( z) $. The transition is carried out by recurrence formulas.

The Lobachevskii method can be applied if there are groups of roots equal in absolute value, though this leads to complications in the logic and formulas of the method. The advantage of the method is that it does not require initial approximations to the roots of the polynomial. In the case of roots distinct in absolute value the rate of convergence of the process is asymptotically quadratic.

However, the Lobachevskii method is numerically unstable, since the process of squaring leads to very rapid accumulation of the computational error. In this connection, attempts have been made to give the Lobachevskii method a self-correcting form. For example, for the calculation of the roots of (1) a sequence of polynomials $ g _ {k} ( z) $ of degree $ \leq n- 1 $ is constructed, connected by the relations

$$ g _ {k+1} ( z) = zg _ {k} ( z) - \phi _ {k} f ( z) ,\ k = 0 , 1 ,\dots ; \ g _ {0} ( z) = 1 ; $$

hence

$$ g _ {k} ( z) = z ^ {k} ( \mathop{\rm mod} f ( z) ) . $$

For every fixed $ k $ one looks for polynomials $ g _ {k,p} ( z) $ defined as follows:

$$ g _ {k,1} ( z) = g _ {k} ( z) ; $$

for $ p \geq 2 $, $ g _ {k,p} ( z) $ is a polynomial of the form

$$ \psi _ {p-2} ( z) f ( z) + \phi _ {p-1} ( z) g _ {k} ( z) , $$

having degree $ \leq n- p $. If the roots of $ f ( z) $ satisfy the inequalities

$$ | r _ {1} | \geq \dots \geq | r _ {p} | > | r _ {p+1} | \geq \dots \geq | r _ {n} | , $$

then

$$ \lim\limits _ {k \rightarrow \infty } g _ {k,p} = \frac{f ^ { * } ( z) }{( z - r _ {1} ) \dots ( z - r _ {p} ) } , $$

where $ f ^ { * } ( z) $ is the polynomial $ f ( z) $ normalized by dividing by the coefficient at the leading term. Thus, from the original polynomial one picks out the factors corresponding to groups of roots equal in absolute value (see [3]). The method was proposed by N.I. Lobachevskii in 1834 (see [1]).

References

[1]	N.I. Lobachevskii, "Collected works" , 4 , Moscow-Leningrad (1948) (In Russian)
[2]	I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[3]	J. Sebastião e Silva, "Sur une méthode de approximation semblable à celle de Gräffe" Portug. Math. , 2 (1941) pp. 271–279
[4]	A.S. Householder, G.W. Stewart, "The numerical factorization of a polynomial" SIAM Rev. , 13 (1971) pp. 38–46

Comments

The basic idea of squaring the roots rests on the simple observation that

$$ ( - 1) ^ {n} f (- z) f( z) = \ a _ {0} ^ {2} \prod_{i=1}^ { n } ( z ^ {2} - r _ {i} ^ {2} ) $$

is a polynomial in $ z ^ {2} $ with roots $ r _ {1} ^ {2} \dots r _ {n} ^ {2} $. For a systematic treatment in the case of complex roots cf. also [a1]. The method is most often referred to as Graeffe's root squaring method.

References

[a1]	S. Brodetsky, G. Smeal, "On Graeffe's method for complex roots" Proc. Cambridge Philos. Soc. , 22 (1924) pp. 83–87
[a2]	F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1974)