Numerical Methods for Roots of Polynomials - Part II

Dedication

Acknowledgment

Preface

Introduction

References

Chapter 7. Bisection and Interpolation Methods

7.1 Introduction and History

7.2 Secant Method and Variations

7.3 The Bisection Method

7.4 Methods Involving Quadratics

7.5 Methods of Higher Order or Degree

7.6 Rational Approximations

7.7 Hybrid Methods

7.8 Parallel Methods

7.9 Multiple Roots

7.10 Method of Successive Approximation

7.11 Miscellaneous Methods Without Using Derivatives

7.12 Methods Using Interval Arithmetic

7.13 Programs

References

Chapter 8. Graeffe’s Root-Squaring Method

8.1 Introduction and History

8.2 The Basic Graeffe Process

8.3 Complex Roots

8.4 Multiple Modulus Roots

8.5 The Brodetsky–Smeal–Lehmer Method

8.6 Methods for Preventing Overflow

8.7 The Resultant Procedure and Related Methods

8.8 Chebyshev-Like Processes

8.9 Parallel Methods

8.10 Errors in Root Estimates by Graeffe Iteration

8.11 Turan’s Methods

8.12 Algorithm of Sebastião e Silva and Generalizations

8.13 Miscellaneous

8.14 Programs

References

Chapter 9. Methods Involving Second or Higher Derivatives

9.1 Introduction

9.2 Halley’s Method and Modifications

9.3 Laguerre’s Method and Modifications

9.4 Chebyshev’s Method

9.5 Methods Involving Square Roots

9.6 Other Methods Involving Second Derivatives

References

Chapter 10. Bernoulli, Quotient-Difference, and Integral Methods

10.1 Bernoulli’s Method for One Dominant Root

10.2 Bernoulli’s Method for Complex and/or Multiple Roots

10.3 Improvements and Generalizations of Bernoulli’s Method

10.4 The Quotient-Difference Algorithm

10.5 The Lehmer–Schur Method

10.6 Methods Using Integration

10.7 Programs

References

Chapter 11. Jenkins–Traub, Minimization, and Bairstow Methods

11.1 The Jenkins–Traub Method

11.2 Jenkins–Traub Method for Real Polynomials

11.3 Precursors and Generalizations of the Jenkins–Traub Method

11.4 Minimization Methods—The Downhill Technique

11.5 Minimization Methods—Use of Gradient

11.6 Hybrid Minimization and Newton’s Methods

11.7 Lin’s Method

11.8 Generalizations of Lin’s Method

11.9 Bairstow’s Method

11.10 Generalizations of Bairstow’s Method

11.11 Bairstow’s Method for Multiple Factors

11.12 Miscellaneous Methods

11.13 Programs

References

Chapter 12. Low-Degree Polynomials

12.1 Introduction

12.2 History of the Quadratic

12.3 Modern Solutions of the Quadratic

12.4 Errors in the Quadratic Solution

12.5 Early History of the Cubic

12.6 Cardan’s Solution of the Cubic

12.7 More Recent Derivations of the Cubic Solution

12.8 Trigonometric Solution of the Cubic

12.9 Discriminants of the Cubic

12.10 Early Solutions of the Quartic

12.11 More Recent Treatment of the Quartic

12.12 Analytic Solution of the Quintic

References

Chapter 13. Existence and Solution by Radicals

13.1 Introduction and Early History of the Fundamental Theorem of Algebra

13.2 Trigonometric Proof-Gauss’ Fourth Proof

13.3 Proofs Using Integration

13.4 Methods Based on Minimization

13.5 Miscellaneous Proofs

13.6 Solution by Radicals (Including Background on Fields and Groups)

13.7 Solution by Radicals: Galois Theory

References

Chapter 14. Stability Considerations

14.1 Introduction

14.2 History

14.3 Roots in the Left (or Right) Half-Plane; Use of Cauchy Index and Sturm Sequences

14.4 Routh’s Method for the Hurwitz Problem

14.5 Routh Method—the Singular Cases

14.6 Other Methods for the Hurwitz Problem

14.7 Robust Hurwitz Stability

14.8 The Number of Zeros in the Unit Circle, and Schur Stability

14.9 Robust Schur Stability

14.10 Programs on Stability

References

Chapter 15. Nearly Optimal Universal Polynomial Factorization and Root-Finding

15.1 Introduction and Main Results

15.2 Definitions and Preliminaries

15.3 Norm Bounds

15.4 Root Radii: Estimates and Algorithms

15.5 Approximating the Power Sums of Polynomial Zeros

15.6 Initial Approximate Splitting

15.7 Refinement of Approximate Splitting: Algorithms

15.8 Refinement of Splitting: Error Norm Bounds

15.9 Accelerated Refinement of Splitting. An Algorithm and the Error Bound

15.10 Computation of the Initial Basic Polynomial for the Accelerated Refinement

15.11 Updating the Basic Polynomials

15.12 Relaxation of the Initial Isolation Constraint

15.13 The Bitwise Precision and the Complexity of Padé Approximation and Polynomial Splitting

15.14 Perturbation of a Padé Approximation

15.15 Avoiding Degeneration of Padé Approximations

15.16 Splitting into Factors over an Arbitrary Circle

15.17 Recursive Splitting into Factors: Error Norm Bounds

15.18 Balanced Splitting and Massive Clusters of Polynomial Zeros

15.19 Balanced Splitting via Root Radii Approximation

15.20 -Centers of a Polynomial and Zeros of a Higher Order Derivative

15.21 Polynomial Splitting with Precomputed -Centers

15.22 How to Avoid Approximation of the Zeros of Higher Order Derivatives

15.23 NAPF and PFD for Any Number of Fractions

15.24 Summary and Comparison with Alternative Methods (Old and New). Some Directions to Further Progress

15.25 The History of Polynomial Root-Finding and Factorization via Recursive Splitting

15.26 Exercises

References

Index