You are previewing Numerical Methods for Roots of Polynomials - Part II.
O'Reilly logo
Numerical Methods for Roots of Polynomials - Part II

Book Description

Numerical Methods for Roots of Polynomials - Part II along with Part I (9780444527295) covers most of the traditional methods for polynomial root-finding such as interpolation and methods due to Graeffe, Laguerre, and Jenkins and Traub. It includes many other methods and topics as well and has a chapter devoted to certain modern virtually optimal methods. Additionally, there are pointers to robust and efficient programs. This book is invaluable to anyone doing research in polynomial roots, or teaching a graduate course on that topic.



  • First comprehensive treatment of Root-Finding in several decades with a description of high-grade software and where it can be downloaded
  • Offers a long chapter on matrix methods and includes Parallel methods and errors where appropriate
  • Proves invaluable for research or graduate course

Table of Contents

  1. Cover image
  2. Title page
  3. Table of Contents
  4. Copyright
  5. Dedication
  6. Acknowledgment
  7. Preface
  8. Introduction
    1. References
  9. Chapter 7. Bisection and Interpolation Methods
    1. 7.1 Introduction and History
    2. 7.2 Secant Method and Variations
    3. 7.3 The Bisection Method
    4. 7.4 Methods Involving Quadratics
    5. 7.5 Methods of Higher Order or Degree
    6. 7.6 Rational Approximations
    7. 7.7 Hybrid Methods
    8. 7.8 Parallel Methods
    9. 7.9 Multiple Roots
    10. 7.10 Method of Successive Approximation
    11. 7.11 Miscellaneous Methods Without Using Derivatives
    12. 7.12 Methods Using Interval Arithmetic
    13. 7.13 Programs
    14. References
  10. Chapter 8. Graeffe’s Root-Squaring Method
    1. 8.1 Introduction and History
    2. 8.2 The Basic Graeffe Process
    3. 8.3 Complex Roots
    4. 8.4 Multiple Modulus Roots
    5. 8.5 The Brodetsky–Smeal–Lehmer Method
    6. 8.6 Methods for Preventing Overflow
    7. 8.7 The Resultant Procedure and Related Methods
    8. 8.8 Chebyshev-Like Processes
    9. 8.9 Parallel Methods
    10. 8.10 Errors in Root Estimates by Graeffe Iteration
    11. 8.11 Turan’s Methods
    12. 8.12 Algorithm of Sebastião e Silva and Generalizations
    13. 8.13 Miscellaneous
    14. 8.14 Programs
    15. References
  11. Chapter 9. Methods Involving Second or Higher Derivatives
    1. 9.1 Introduction
    2. 9.2 Halley’s Method and Modifications
    3. 9.3 Laguerre’s Method and Modifications
    4. 9.4 Chebyshev’s Method
    5. 9.5 Methods Involving Square Roots
    6. 9.6 Other Methods Involving Second Derivatives
    7. References
  12. Chapter 10. Bernoulli, Quotient-Difference, and Integral Methods
    1. 10.1 Bernoulli’s Method for One Dominant Root
    2. 10.2 Bernoulli’s Method for Complex and/or Multiple Roots
    3. 10.3 Improvements and Generalizations of Bernoulli’s Method
    4. 10.4 The Quotient-Difference Algorithm
    5. 10.5 The Lehmer–Schur Method
    6. 10.6 Methods Using Integration
    7. 10.7 Programs
    8. References
  13. Chapter 11. Jenkins–Traub, Minimization, and Bairstow Methods
    1. 11.1 The Jenkins–Traub Method
    2. 11.2 Jenkins–Traub Method for Real Polynomials
    3. 11.3 Precursors and Generalizations of the Jenkins–Traub Method
    4. 11.4 Minimization Methods—The Downhill Technique
    5. 11.5 Minimization Methods—Use of Gradient
    6. 11.6 Hybrid Minimization and Newton’s Methods
    7. 11.7 Lin’s Method
    8. 11.8 Generalizations of Lin’s Method
    9. 11.9 Bairstow’s Method
    10. 11.10 Generalizations of Bairstow’s Method
    11. 11.11 Bairstow’s Method for Multiple Factors
    12. 11.12 Miscellaneous Methods
    13. 11.13 Programs
    14. References
  14. Chapter 12. Low-Degree Polynomials
    1. 12.1 Introduction
    2. 12.2 History of the Quadratic
    3. 12.3 Modern Solutions of the Quadratic
    4. 12.4 Errors in the Quadratic Solution
    5. 12.5 Early History of the Cubic
    6. 12.6 Cardan’s Solution of the Cubic
    7. 12.7 More Recent Derivations of the Cubic Solution
    8. 12.8 Trigonometric Solution of the Cubic
    9. 12.9 Discriminants of the Cubic
    10. 12.10 Early Solutions of the Quartic
    11. 12.11 More Recent Treatment of the Quartic
    12. 12.12 Analytic Solution of the Quintic
    13. References
  15. Chapter 13. Existence and Solution by Radicals
    1. 13.1 Introduction and Early History of the Fundamental Theorem of Algebra
    2. 13.2 Trigonometric Proof-Gauss’ Fourth Proof
    3. 13.3 Proofs Using Integration
    4. 13.4 Methods Based on Minimization
    5. 13.5 Miscellaneous Proofs
    6. 13.6 Solution by Radicals (Including Background on Fields and Groups)
    7. 13.7 Solution by Radicals: Galois Theory
    8. References
  16. Chapter 14. Stability Considerations
    1. 14.1 Introduction
    2. 14.2 History
    3. 14.3 Roots in the Left (or Right) Half-Plane; Use of Cauchy Index and Sturm Sequences
    4. 14.4 Routh’s Method for the Hurwitz Problem
    5. 14.5 Routh Method—the Singular Cases
    6. 14.6 Other Methods for the Hurwitz Problem
    7. 14.7 Robust Hurwitz Stability
    8. 14.8 The Number of Zeros in the Unit Circle, and Schur Stability
    9. 14.9 Robust Schur Stability
    10. 14.10 Programs on Stability
    11. References
  17. Chapter 15. Nearly Optimal Universal Polynomial Factorization and Root-Finding
    1. 15.1 Introduction and Main Results
    2. 15.2 Definitions and Preliminaries
    3. 15.3 Norm Bounds
    4. 15.4 Root Radii: Estimates and Algorithms
    5. 15.5 Approximating the Power Sums of Polynomial Zeros
    6. 15.6 Initial Approximate Splitting
    7. 15.7 Refinement of Approximate Splitting: Algorithms
    8. 15.8 Refinement of Splitting: Error Norm Bounds
    9. 15.9 Accelerated Refinement of Splitting. An Algorithm and the Error Bound
    10. 15.10 Computation of the Initial Basic Polynomial for the Accelerated Refinement
    11. 15.11 Updating the Basic Polynomials
    12. 15.12 Relaxation of the Initial Isolation Constraint
    13. 15.13 The Bitwise Precision and the Complexity of Padé Approximation and Polynomial Splitting
    14. 15.14 Perturbation of a Padé Approximation
    15. 15.15 Avoiding Degeneration of Padé Approximations
    16. 15.16 Splitting into Factors over an Arbitrary Circle
    17. 15.17 Recursive Splitting into Factors: Error Norm Bounds
    18. 15.18 Balanced Splitting and Massive Clusters of Polynomial Zeros
    19. 15.19 Balanced Splitting via Root Radii Approximation
    20. 15.20 -Centers of a Polynomial and Zeros of a Higher Order Derivative
    21. 15.21 Polynomial Splitting with Precomputed -Centers
    22. 15.22 How to Avoid Approximation of the Zeros of Higher Order Derivatives
    23. 15.23 NAPF and PFD for Any Number of Fractions
    24. 15.24 Summary and Comparison with Alternative Methods (Old and New). Some Directions to Further Progress
    25. 15.25 The History of Polynomial Root-Finding and Factorization via Recursive Splitting
    26. 15.26 Exercises
    27. References
  18. Index