book

Numerical Methods for Roots of Polynomials - Part II

by J.M. McNamee, Victor Pan

July 2013

Intermediate to advanced

728 pages

18h 38m

English

Elsevier Science

Read now

Unlock full access

Cover image
Title page
Table of Contents
Copyright
Dedication
Acknowledgment
Preface
Introduction
References
Chapter 7. Bisection and Interpolation Methods
7.1 Introduction and History7.2 Secant Method and Variations7.3 The Bisection Method7.4 Methods Involving Quadratics7.5 Methods of Higher Order or Degree7.6 Rational Approximations
7.7 Hybrid Methods
7.8 Parallel Methods7.9 Multiple Roots7.10 Method of Successive Approximation7.11 Miscellaneous Methods Without Using Derivatives7.12 Methods Using Interval Arithmetic7.13 ProgramsReferences

Chapter 8. Graeffe’s Root-Squaring Method
8.1 Introduction and History8.2 The Basic Graeffe Process8.3 Complex Roots8.4 Multiple Modulus Roots8.5 The Brodetsky–Smeal–Lehmer Method8.6 Methods for Preventing Overflow8.7 The Resultant Procedure and Related Methods8.8 Chebyshev-Like Processes8.9 Parallel Methods8.10 Errors in Root Estimates by Graeffe Iteration8.11 Turan’s Methods8.12 Algorithm of Sebastião e Silva and Generalizations8.13 Miscellaneous8.14 ProgramsReferences
Chapter 9. Methods Involving Second or Higher Derivatives
9.1 Introduction9.2 Halley’s Method and Modifications9.3 Laguerre’s Method and Modifications9.4 Chebyshev’s Method9.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 Root10.2 Bernoulli’s Method for Complex and/or Multiple Roots10.3 Improvements and Generalizations of Bernoulli’s Method10.4 The Quotient-Difference Algorithm10.5 The Lehmer–Schur Method10.6 Methods Using Integration10.7 ProgramsReferences
Chapter 11. Jenkins–Traub, Minimization, and Bairstow Methods
11.1 The Jenkins–Traub Method11.2 Jenkins–Traub Method for Real Polynomials11.3 Precursors and Generalizations of the Jenkins–Traub Method11.4 Minimization Methods—The Downhill Technique11.5 Minimization Methods—Use of Gradient11.6 Hybrid Minimization and Newton’s Methods11.7 Lin’s Method11.8 Generalizations of Lin’s Method11.9 Bairstow’s Method11.10 Generalizations of Bairstow’s Method11.11 Bairstow’s Method for Multiple Factors11.12 Miscellaneous Methods11.13 ProgramsReferences
Chapter 12. Low-Degree Polynomials
12.1 Introduction12.2 History of the Quadratic12.3 Modern Solutions of the Quadratic12.4 Errors in the Quadratic Solution12.5 Early History of the Cubic12.6 Cardan’s Solution of the Cubic12.7 More Recent Derivations of the Cubic Solution12.8 Trigonometric Solution of the Cubic12.9 Discriminants of the Cubic12.10 Early Solutions of the Quartic12.11 More Recent Treatment of the Quartic12.12 Analytic Solution of the QuinticReferences
Chapter 13. Existence and Solution by Radicals
13.1 Introduction and Early History of the Fundamental Theorem of Algebra13.2 Trigonometric Proof-Gauss’ Fourth Proof13.3 Proofs Using Integration13.4 Methods Based on Minimization13.5 Miscellaneous Proofs13.6 Solution by Radicals (Including Background on Fields and Groups)13.7 Solution by Radicals: Galois TheoryReferences
Chapter 14. Stability Considerations
14.1 Introduction14.2 History14.3 Roots in the Left (or Right) Half-Plane; Use of Cauchy Index and Sturm Sequences14.4 Routh’s Method for the Hurwitz Problem14.5 Routh Method—the Singular Cases14.6 Other Methods for the Hurwitz Problem14.7 Robust Hurwitz Stability14.8 The Number of Zeros in the Unit Circle, and Schur Stability14.9 Robust Schur Stability14.10 Programs on StabilityReferences
Chapter 15. Nearly Optimal Universal Polynomial Factorization and Root-Finding
15.1 Introduction and Main Results15.2 Definitions and Preliminaries15.3 Norm Bounds15.4 Root Radii: Estimates and Algorithms15.5 Approximating the Power Sums of Polynomial Zeros15.6 Initial Approximate Splitting15.7 Refinement of Approximate Splitting: Algorithms15.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 Refinement15.11 Updating the Basic Polynomials15.12 Relaxation of the Initial Isolation Constraint15.13 The Bitwise Precision and the Complexity of Padé Approximation and Polynomial Splitting15.14 Perturbation of a Padé Approximation15.15 Avoiding Degeneration of Padé Approximations15.16 Splitting into Factors over an Arbitrary Circle15.17 Recursive Splitting into Factors: Error Norm Bounds15.18 Balanced Splitting and Massive Clusters of Polynomial Zeros15.19 Balanced Splitting via Root Radii Approximation15.20 -Centers of a Polynomial and Zeros of a Higher Order Derivative15.21 Polynomial Splitting with Precomputed -Centers15.22 How to Avoid Approximation of the Zeros of Higher Order Derivatives15.23 NAPF and PFD for Any Number of Fractions15.24 Summary and Comparison with Alternative Methods (Old and New). Some Directions to Further Progress15.25 The History of Polynomial Root-Finding and Factorization via Recursive Splitting15.26 ExercisesReferences
Index

Content preview from Numerical Methods for Roots of Polynomials - Part II

Chapter 15

Nearly Optimal Universal Polynomial Factorization and Root-Finding

J.M. McNamee and V.Y. Pan

Abstract

The zeros of a polynomial can be readily recovered from its linear factors. The linear factors can be approximated by first splitting a polynomial numerically into the product of its two nonconstant factors and then recursively splitting every computed nonlinear factor in similar fashion. For both the worst and average case inputs the resulting algorithms solve the polynomial factorization and root-finding problems within fixed sufficiently small error bounds by using nearly optimal arithmetic and Boolean time, that is using nearly optimal numbers of arithmetic and bitwise operations; in the case of a polynomial with integer coefficients ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Journey from Natural Numbers to Complex Numbers

Publisher Resources

ISBN: 9780444527301

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Numerical Methods for Roots of Polynomials - Part II

by J.M. McNamee, Victor Pan