Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ SIAM Reviewarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
SIAM Review
Article
Data sources: UnpayWall
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
SIAM Review
Article . 1971 . Peer-reviewed
Data sources: Crossref
versions View all 2 versions
addClaim

The Numerical Factorization of a Polynomial

The numerical factorization of a polynomial
Authors: Householder, A. S.; Stewart, G. W.;

The Numerical Factorization of a Polynomial

Abstract

A number of methods can be found in the literature for the numerical factorization of a polynomial, and references to some are given in the bibliography below. Well-known examples are those of Lin and of Bairstow. Many are quadratically convergent, but most require a sufficiently close initial factorization to start with. The method of Graeffe and the qd algorithm are not ordinarily thought of as methods of factorization, but either provides, in principle, factors of the given polynomial whose zeros are zeros of equal modulus of the given polynomial. These do not require initial approximations, and the Graeffe method (but not the qd algorithm) is quadratically convergent. But neither is self-correcting, so that errors accumulate, and any approximate factor either produces may require further refinement by a method that is self-correcting. Naturally the extraction of a single zero is a special case of factorization in which one of the factors is linear, and this is to be understood throughout. A number of these methods can be related to a method that seems to have been proposed first by Sebastiao e Silva (for brevity he will hereafter be referred to as S-S) in 1941. Although Bairstow's method is a member of this class, and was published in 1914, it is only in terms of the theory set forth by S-S and further elaborated by Bauer that the relations among these methods can be properly understood. The purpose of the present note is to attempt to show in a heuristic and expository manner how some of the algorithms to which allusion has been made can be regarded as natural outgrowths of the basic S-S theory (in this connection, however, see also Stewart [26]). At the outset a theorem will be stated that is somewhat more general than the original S-S theorem. For the proof of the general theorem reference is made to Householder [15], but a proof of the S-S theorem itself will be sketched that is rather different in form from the usual one, and that can be extended, though with certain complications, to the more general theorem. This particular proof has the further advantage that the usually troublesome confluent case introduces only mild complications. A somewhat different proof has been given by Glenisson and Derwidue [12], [13] who seem to have discovered the algorithm independently. The S-S algorithm is, like the method of Bernoulli and the method of Graeffe (and of Dandelin and Lobachevsky), based on the idea of root powering, but the algorithm is different. Like these methods, it does not require an initial approximation. In one form it is quadratically convergent, like the method of Graeffe. A method that is quadratically convergent and does not require an initial approximation will be said to have Graeffe-type convergence. But the S-S algorithm, unlike the method of Graeffe, can be made error-correcting.

Keywords

Numerical computation of solutions to single equations

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    8
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
8
Average
Top 10%
Average
bronze