Namespaces
Variants
Actions

Difference between revisions of "Parabola method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
p0711601.png
 +
$#A+1 = 21 n = 0
 +
$#C+1 = 21 : ~/encyclopedia/old_files/data/P071/P.0701160 Parabola method
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A method for calculating the roots of a polynomial
 
A method for calculating the roots of a polynomial
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711601.png" /></td> </tr></table>
+
$$
 +
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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711602.png" /> as interpolation points, one forms the Lagrange interpolation polynomial (cf. [[Lagrange interpolation formula|Lagrange interpolation formula]]) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711603.png" />. This will be a polynomial of degree two. Both its roots can be found, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711604.png" /> is taken as the nearest of them to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711605.png" />. After this, instead of the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711606.png" />, one takes the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711607.png" /> and repeats the process. It has been empirically established that the sequence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711608.png" /> 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 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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p0711609.png" /> is the triple of numbers at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116010.png" />-th stage, then, using the notation
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116011.png" /></td> </tr></table>
+
$$
 +
= z - z _ {i} ,\ \
 +
h _ {i}  = z _ {i} - z _ {i-} 1 ,\ \
 +
h _ {i-} 1  = z _ {i-} 1 - z _ {i-} 2 ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116012.png" /></td> </tr></table>
+
$$
 +
\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
 
the Lagrange interpolation polynomial has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116013.png" /></td> </tr></table>
+
$$
 +
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} ) ] +
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116014.png" /></td> </tr></table>
+
$$
 +
+
 +
P _ {n} ( z _ {i} ).
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116015.png" /></td> </tr></table>
+
The roots of  $  L  ^ {(} i) ( \lambda ) $
 +
are found by the formula
  
The roots of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116016.png" /> are found by the formula
+
$$
 +
\lambda =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116017.png" /></td> </tr></table>
+
$$
 +
= \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116018.png" /></td> </tr></table>
+
\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
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116019.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116020.png" />, the smallest in modulus is taken and then one continues the calculations with
+
From the two possible values of $  \lambda $,  
 +
the smallest in modulus is taken and then one continues the calculations with
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071160/p07116021.png" /></td> </tr></table>
+
$$
 +
\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 [[#References|[1]]], [[#References|[3]]]).
 
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 [[#References|[1]]], [[#References|[3]]]).

Latest revision as of 08:04, 6 June 2020


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
How to Cite This Entry:
Parabola method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Parabola_method&oldid=15551
This article was adapted from an original article by G.D. Kim (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article