Bernoulli's and QD method

A.C. Aitken, Further numerical studies in algebraic equations and matrices, Proc. Roy. Soc. Edinburgh Sect. A 51 (1931) 80--90.

A.C. Aitken, On Bernoulli's numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh 46 (1926) 289--305.

A.C. Aitken, The contributions of E.T. Whittaker to algebra and numerical analysis, Proc. Edinburgh Math. Soc. 11 (1958) 31--38.

G. Baker and P. Graves-Morris, Padé approximants I (Addison-Wesley, London, 1981) 96--102.

G. Baker, Recursive calculation of Padé approximants, in: P.R. Graves-Morris, Ed., Padé approximants and their applications (Springer, Berlin, 1972) 83--92.

M. Balfour and A.J. McTernan, The Numerical Solution of Equations (Heinemann, London, 1st ed., 1967).

H. Bandemer, Zur Berechnung der Nullstellen von Polynomen mit dem QD-Algorithmus von Rutishauser, Z. Angew. Math. Mech. 42 (1962) 566--568.

F.L. Bauer, Beiträge zur Entwicklung numerischer Verfahren für programmgesteuerte Rechenanlagen, I. Quadratisch konvergente Durchführung der Bernoulli--Jacobischen Methode zur Nullstellenbestimmung von Polynomen, Sitzungsber. Math.-Natur. Kl. Bayer. Acad. Wiss. (1954--1955) 275--303; II. Direkte Factorisierung eines Polynoms, Sitzungsber. Math.-Natur. Kl. Bayer. Akad. Wiss. (1956--1957) 163--203.

F.L. Bauer, The g-algorithm, J. Soc. Indust. Appl. Math. 8 (1960) 1--17.

F.L. Bauer and Kl. Samelson, Polynomkerne und Iterationsverfahren, Math. Z. 67 (1957) 93--98.

F.L. Bauer, The quotient-difference algorithm and epsilon-algorithms, in: On Numerical Approximation (Univ. of Wisconsin Press, Madison, WI, 1959) 361--370.

F.L. Bauer, Quadratische Konvergenz der Bernoullischen Methode, Z. Angew. Math. Mech. 34 (1954) 287.

F.L. Bauer, Das Verfahren der abgekürtzen Iteration für algebraische Eigenwerteprobleme, insbesondere zur Nullstellenbestimmung eines Polynoms, Z. Angew. Math. Phys. 7 (1956) 17--32.

F.L. Bauer, Nonlinear sequence transformations, in: Approximation of Functions (Elsevier, Amsterdam, 1965) 134--151.

L. Berg, Numerisches Faktorisierung von Polynomen, Z. Angew. Math. Mech. 58 (1978) 245--249.

W.G. Bickley, On Smith's method for calculation of the roots of polynomial equations, Math. Gaz. 46 (1962) 32.

D. Bini, Complexity of parallel polynomial computations, in: D.J. Evans, Ed., Parallel Computation: Methods, Algorithms and Applications (Adam Hilger, 1989) 115--126.

P.A. Brooker, The solution of algebraic equations on the Edsac, Proc. Cambridge Philos. Soc. 48 (1952) 255--270.

R.A. Buckingham, Numerical Methods (Pitman, London, 1957) 251--304.

A. Bultheel, Zeros of a rational function defined by its Laurent expansion, in: H. Werner and H.J. Bunger, Eds., Padé Approximation and its Applications, Bad Honnef, 1983, Lecture Notes in Math. 1071 (Springer, New York, 1984) 34--48.

F. Cajori, A History of Mathematics (Macmillan, New York, 2nd ed., 1919).

B. Carnahan, H.A. Luther and J.O. Wilkes, Applied Numerical Methods (Wiley, New York, 1969) 141--209.

L. Cerlienco and F. Piras, Successioni ricorrenti lineari e algebra dei polinomi, Rend. Mat. Ser. 7 1 (2) (1981) 305--318.

F. Cohn, Über die in recurrirender Weise gebildeten Grössen und ihren Zusammenhang mit den algebraischen Gleichungen, Math. Ann. 44 (1894) 473--538.

P.D. Crout, A procedure for obtaining the zeros of functions or their derivatives by Lagrangean interpolation, J. Math. and Phys. 39 (1960) 141--150.

A. Cuyt, in: A. Cuyt and L. Wuytack, Eds., Nonlinear Methods in Numerical Analysis, North-Holland Math. Stud. 136, Stud. Comput. Math. 1 (North-Holland, Amsterdam, 1987) 220--237.

M. D'Ocagne, Mémoire sur les suites récurrentes, J. École Poly. 64 (1894) 151--224.

J.E. Dennis, J.F. Traub and R.P. Weber, Algorithms for solvents of matrix polynomials, SIAM J. Numer. Anal. 15 (1978) 523--533.

B. Dimsdale, On Bernouilli's method for solving algebraic equations, Quart. Appl. Math. 6 (1948) 77.

D. Dobbs and R. Hanks, A modern course on the theory of equations (Polygonal Publishers., 2nd ed., 1992).

D.E. Dobbs and R. Hanks, A Modern Course on the Theory of Equations (Polygonal Publ. House, Passic, NJ, 1980).

H. Eltermann, Die Lösung algebraischer und transzendenter Gleichungen mit Hilfe von rekursiven Folgen, Z. Angew. Math. Mech. 32 (1952) 231--232.

L. Euler, Introductio in Analysii Infinitorum, I (1748) Chapter 17.

C.M. Fiduccia, An efficient formula for linear recurrences, SIAM J. Comput. 14 (1985) 106--112.

L. Fox and L. Hayes, Polynomial factorization and the QD algorithm, Linear Algebra Appl. 1 (1968) 445--463.

C.E. Fröberg, Introduction to Numerical Analysis (Addison-Wesley, Reading, MA, 1969).

T.C. Fry, Some numerical methods for locating roots of polynomials, Quart. Appl. Math. 3 (1945) 89--105.

C.F. Gerald, Applied Numerical Analysis (Addison-Wesley, Reading, MA, 1984) 1--79.

W.B. Gragg, The Padé table and its relation to certain algorithms of numerical analysis, SIAM Rev. 14 (1972) 1--62.

W.B. Gragg and A.S. Householder, On a theorem of Koenig, Numer. Math. 8 (1966) 465--468.

D. Greenspan, On popular methods and extant problems in the solution of polynomial equations, Math. Mag. 31 (1957--1958) 239--253.

D. Gries and G. Levin, Computing Fibonacci numbers (and similarly defined functions) in log time, Inform. Process. Lett. 11 (2) (1980) 68--69.

W. Heitzinger, I. Troch and G. Valentin, Praxis Nichtlinearer Gleichungen (Hanser Verlag, München, 1985).

P. Henrici, Essentials of Numerical Analysis (Wiley, New York, 1982) 90--103; 136--168.

P. Henrici, Quotient-difference algorithms, in: A. Ralston and H.S. Wilf, Eds., Mathematical Methods for Digital Computers, Vol. II (Wiley, New York, 1967) 35--62.

P. Henrici, Applied and Computational Complex Analysis, Vol. I (Wiley, New York, 1974) 433--552.

P. Henrici, Some applications of the quotient-difference algorithm, Proc. Sympos. Appl. Math. 15 (1963) 159--183.

P. Henrici, The quotient-difference algorithm, Nat. Bur. Standards Appl. Math. Ser. 49 (1958) 23--46.

P. Henrici, New developements concerning the quotient-difference algorithm, in: H. Werner et al., Eds., Computational Aspects of Complex Analysis (Reidel, Boston, 1983) 149--168.

P. Henrici and B.O. Watkins, Finding zeros of a polynomial by the Q-D algorithm, Comm. ACM 8 (1965) 570--574.

A.S. Householder, The Numerical Treatment of a Single Nonlinear Equation (McGraw-Hill, New York, 1970).

A.S. Householder, Principles of Numerical Analysis (McGraw-Hill, New York, 1953) 86--132.

A.S. Householder, The Padé table, the Frobenius identities, and the QD algorithm, Linear Algebra Appl. 4 (1971) 161--174.

A.S. Householder, Multigradients and the zeros of transcendental functions, Linear Algebra Appl. 4 (1971) 175--182.

A.S. Householder, Schröder and Trudi: A historical excursion, SIAM Rev. 16 (1974) 344--348.

A.S. Householder and G.W. Stewart III, Bigradients, Hankel determinants, and the Padé table, in: B. Dejon and P. Henrici, Eds., Constructive Aspects of the Fundamental Theorem of Algebra (Wiley/Interscience, New York, 1969) 131--150.

E. Isaacson and H.B. Keller, Analysis of Numerical Methods (Wiley, New York, 1966) 85--133.

G. Jacobi, Observatiunculae ad theoriam aequationum pertinentes, J. Reine Angew. Math. 13 (1835) 340--352.

M.A. Jenkins, Bernouilli's method with implicit shifting, J. Assoc. Comput. Mach. 20 (1973) 539--544.

W. Jennings, First Course in Numerical Methods (MacMillan, New York, 1964) 5--12; 23--39.

W.B. Jones and A. Magnus, Computation of poles of two-point Padé approximants and their limits, J. Comput. Appl. Math. 6 (2) (1980) 105--119.

J. König, Über eine Eigenschaft der Potenzreihen, Math. Ann. 23 (1884) 447--449.

J. König, Ein allgemeiner Ausdruck für die ihrem absoluten Betrage nach kleinste Wurzel der Gleichung nten Grades, Math. Ann. 9 (1876) 530--540.

D. Kershaw, An analysis of the method of L. Fox and L. Hayes for the factorization of a polynomial, Linear Algebra Appl. 86 (1987) 179--187.

S. Kulik, On the solution of algebraic equations, Proc. Amer. Math. Soc. 10 (1959) 185--192.

G.N. Lance, Numerical Methods for High Speed Computers (Iliffe, London, 1960) 123--137.

G.R. Lindfield and J.E.T. Penny, Microcomputers in Numerical Analysis (Wiley, New York, 1989) Chapter 2.

F. Locher, A stability test for real polynomials, Numer. Math. 66 (1993) 33--40.

K. Margaritis and D.J. Evans, A systolic ring architecture for solving polynomial equations, Internat. J. Comput. Math. 25 (1988) 189--201.

K. Margaritis and D.J. Evans, A systolic ring architecture for solving polynomial equations, in: David J. Evans, Ed., Systolic Algorithms (Gordon and Breach, 1991) 55--68.

K. Margaritis and D.J. Evans, Systolic designs for Bernoulli's method, Parallel Comput. 15 (1990) 227--240.

D. Markovitch, On a new method of calculating the roots of algebraic equations, Math. Gaz. 49 (1965) 388.

G.M. Megson, O. Brudaru and D. Comish, Systolic designs for Aitken's root-finding methods, Parallel Comput. 18 (1992) 415--429.

N.S. Mendelsohn, The computation of complex proper values and vectors of a real matrix with applications to polynomials, Math. Comp. 11 (1957) 91--94.

M. Mignotte, Note sur la méthode Bernoulli, Numer. Math. 26 (1976) 325--326.

M. Mignotte, Some problems about polynomials, in: R.D Jenks, Ed., Proc. 1976 ACM Symp. on Symbolic and Algebraic Computation (1976) 227-- 228.

D.G. Moursund, Examination of multiple roots and root clusters of a polynomial using the Bernoulli procedure, J. Assoc. Comput. Mach. 12 (1965) 169--174.

I. Munro, Some results concerning efficient and optimal algorithms, in: Third Annual ACM Symp. on the Theory of Computers, Shaker Heights (1971) 40--44.

W.D. Munro, Some iterative methods for determining zeros of functions of a complex variable, Pacific J. Math. 9 (1959) 555--566.

E. Netto, Vorlesungen über Algebra (Teubner, Leipzig, 1896).

F.W.J. Olver, The evaluation of zeros of high-degree polynomials, Philos. Trans. Roy. Soc. London Ser. A 244 (1952) 385--415.

R. Perrin, Sur la résolution des équations numériques au moyen des suites récurrentes, C.R. Acad. Sci. Paris 120 (1894) 990--993.

A. Ralston and P. Rabinowitz, A First Course in Numerical Analysis (McGraw-Hill, New York, 2nd ed., 1987) 354.

J.R. Rice, Numerical Methods, Software and Analysis (McGraw-Hill, New York, 1983) 217--264.

J.R. Rice and S. Rosen, NAPSS -- a numerical analysis problem solving system, in: Proc. ACM 21st National Conf. (1966) 51--56.

C. Runge, Separation und Approximation der Wurzeln, in: Encyklopädie der Mathematischen Wissenschaften, I, 1 (Teubner, Leipzig, 1898) 404--448.

H. Rutishauser, On a modification of the QD-algorithm with Graeffe-type convergence, Z. Angew. Math. Phys. 13 (1962) 493--496; also: in: C.M. Popplewell, Ed., Proc. IFIP Congress 62 (North-Holland, Amsterdam, 1963) 93--96.

H. Rutishauser, Eine Formel von Wronski und ihre Bedeutung für den Quotienten-Differenzen-Algorithmus, Z. Angew. Math. Phys. 7 (1956) 164--169.

H. Rutishauser, Anwendungen des Quotientin-Differenzen Algorithms, Z. Angew. Math. Phys. 5 (1954) 496--508.

H. Rutishauser, Der Quotienten-Differenzen-Algorithmus, Z. Angew. Math. Phys. 5 (1954) 233--251.

H. Rutishauser, Stabile Sonderfälle des Quotienten-Differenzen-Algorithmus, Numer. Math. 5 (1963) 95--112.

H. Rutishauser, Ein infinitesimales Analogon zum Quotient-Differenzen Algorithmus, Arch. Math. (Basel) 5 (1954) 132--137.

K. Samelson, Faktorisierung von Polynomen durch funktionale Iteration, Bayer. Akad. Wiss. Math.-Natur. Kl. Abh. 95 (1959) 1--25.

J. Schröder, Factorization of polynomials by generalized Newton procedures, in: B. Dejon and P. Henrici, Eds., Constructive Aspects of the Fundamental Theorem of Algebra (Wiley/Interscience, New York, 1969) 295--320.

W. Seewald, Quotient-differnece algorithm: proof of Rutishauser's rule, Numer. Math. 40 (1982) 93--98.

J. Shortt, An iterative algorithm to calculate Fibonacci numbers in O(logn) arithmetic operations, Inform. Process. Lett. 7 (1978) 299--303.

G.S. Smith, A new method of calculating roots of algebraic equations, Math. Gaz. 44 (1960) 241--245; ibid. 51 (1967) 233--236.

G.W. Stewart, On a companion operator for analytic functions, Numer. Math. 18 (1971) 26--43.

E.L. Stiefel, An Introduction to Numerical Mathematics (Academic Press, New York, 1963).

A.N. Stokes, A stable quotient-difference algorithm, Math. Comp. 34 (1980) 515--519.

W.C. Taylor, A neglected method for resolution of polynomial equations, J. Franklin Inst. 257 (1954) 459--464.

R.F. Thomas Jr, Corrections to numerical data on Q-D algorithm, Letter to Editor, Comm. ACM 9 (1966) 322--323.

D.D. Tosic and D.V. Tosic, A modification of Bernoulli's method for evaluations of zeros of polynomials, in: D. Herceg, Ed., Numerical Methods and Approximation Theory, Novi Sad, 1985 (University of Novi Sad, 1985) 149--154.

F.J. Urbanek, An O(logn) algorithm for computing the nth element of the solution of a difference equation, Inform. Process. Lett. 11 (1980) 66--67.

J. Van Iseghem, Convergence of the vector QD-algorithm. Zeros of vector orthogonal polynomials, J. Comput. Appl. Math. 25 (1) (1989) 33--46.

H. Weber, Traité d'Algèbra Supérieure (Gauthier-Villars, Paris, 1898).

H. Weber, Lehrbuch der Algebra (Chelsea, New York).

E.T. Whittaker and G. Robinson, The Calculus of Observations (London, 4th ed., 1944) 78--131.

H.S. Wilf, Mathematics for the Physical Sciences (Wiley, New York, 1962) 82--107.

H.S. Wilf, The numerical solution of polynomial equations, in: A. Ralston and H.S. Wilf, Eds., Mathematical Methods for Digital Computers (Wiley, New York, 1960) 233--241.

T.C. Wilson and J. Shortt, An O(logn) algorithm for computing general order-k Fibonacci numbers, Inform. Process. Lett. 10 (1980) 68--75.

D.M. Young and R.T. Gregory, A Survey of Numerical Mathematics, Vol. I (Addison-Wesley, Reading, MA, 1972) 93--245.

V.L. Zaguskin, Handbook of Numerical Methods for the Solution of Algebraic and Transcendental Equations (Pergamon, Oxford, 1961).

V. Zakian, Evaluation of largest or smallest zero of a polynomial, Electron. Lett. 6 (1970) 217--219.