Parabola method

A method for calculating the roots of a polynomial

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

with complex coefficients, based on interpolation by polynomials of degree 3. The parabola method allows one to find all zeros of the polynomial without preliminary information about initial approximations. The convergence of the parabola method is established only empirically. Close to a simple zero the rate of convergence is nearly quadratic.

The calculation scheme of the parabola method is as follows. With respect to arbitrary complex numbers $ z _ {0} , z _ {1} , z _ {2} $ as interpolation points, one forms the Lagrange interpolation polynomial (cf. Lagrange interpolation formula) for $ P _ {n} ( z) $. This will be a polynomial of degree two. Both its roots can be found, and $ z _ {3} $ is taken as the nearest of them to $ z _ {2} $. After this, instead of the points $ z _ {0} , z _ {1} , z _ {2} $, one takes the points $ z _ {1} , z _ {2} , z _ {3} $ and repeats the process. It has been empirically established that the sequence $ z _ {0} , z _ {1} \dots $ constructed in this way converges to a root of the polynomial. The calculated root is factored out, and then the method is applied to the resulting polynomial of lower degree.

The calculation formulas of the parabola method are: If $ z _ {i-} 2 , z _ {i-} 1 , z _ {i} $ is the triple of numbers at the $ i $- th stage, then, using the notation

$$ h = z - z _ {i} ,\ \ h _ {i} = z _ {i} - z _ {i-} 1 ,\ \ h _ {i-} 1 = z _ {i-} 1 - z _ {i-} 2 , $$

$$ \lambda = \frac{h}{h _ {i} } ,\ \lambda _ {i} = \frac{h _ {i} }{h _ {i-} 1 } ,\ \delta _ {i} = 1 + \lambda _ {i} , $$

the Lagrange interpolation polynomial has the form

$$ L ^ {(} i) ( \lambda ) = \ \frac{\lambda ^ {2} }{\delta _ {i} } [ P _ {n} ( z _ {i-} 2 ) \lambda _ {i} ^ {2} - P _ {n} ( z _ {i-} 1 ) \lambda _ {i} \delta _ {i} + P _ {n} ( z _ {i} ) \lambda _ {i} ] + $$

$$ + \frac \lambda {\delta _ {i} } [ P _ {n} ( z _ {i-} 2 ) \lambda _ {i} ^ {2} - P _ {n} ( z _ {i-} 1 ) \delta _ {i} ^ {2} + P _ {n} ( z _ {i} ) ( \lambda _ {i} + \delta _ {i} ) ] + $$

$$ + P _ {n} ( z _ {i} ). $$

The roots of $ L ^ {(} i) ( \lambda ) $ are found by the formula

$$ \lambda = $$

$$ = \ \frac{- 2P _ {n} ( z _ {i} ) \delta _ {i} }{g _ {i} \pm \sqrt {g _ {i} ^ {2} - 4P _ {n} ( z _ {i} ) \delta _ {i} \lambda _ {i} [ P _ {n} ( z _ {i-} 2 ) \lambda _ {i} - P _ {n} ( z _ {i-} 1 ) \delta _ {i} + P _ {n} ( z _ {i} ) ] } } , $$

where

$$ g _ {i} = P _ {n} ( z _ {i-} 2 ) \lambda _ {i} ^ {2} - P _ {n} ( z _ {i-} 1 ) \delta _ {i} ^ {2} + P _ {n} ( z _ {i} ) ( \lambda _ {i} + \delta _ {i} ) . $$

From the two possible values of $ \lambda $, the smallest in modulus is taken and then one continues the calculations with

$$ \lambda _ {i+} 1 = \lambda ; \ \ h _ {i+} 1 = \lambda _ {i+} 1 h _ {i} ; \ \ z _ {i+} 1 = z _ {i} + h _ {i+} 1 . $$

When implementing this process on a computer, there may occur overflow in the computation of the value of the polynomial at a certain point. The appearance of large numbers is also possible in the calculation of the roots of the polynomials of degree 2. There is a sequence of methods specifically designed to avoid this phenomenon (see [1], [3]).

References

[1]	V.V. Voevodin, "Numerical methods of algebra. Theory and algorithms" , Moscow (1966) (In Russian)
[2]	J.H. Wilkinson, "The algebraic eigenvalue problem" , Oxford Univ. Press (1969)
[3]	N.S. Bakvalov, "The stable calculation of polynomial values" USSR Comp. Math. Math. Phys. , 11 : 6 (1971) pp. 263–271 Zh. Vychisl. Mat. i Mat. Fiz. , 11 (1971) pp. 1568–1574