Numerical Methods for Roots of Polynomials - Part I

by McNamee

• ISBN13: 9780444527295
• ISBN10: 044452729X
• Format: Hardcover
• Copyright: 2007-08-17
• Publisher: Elsevier Science

Summary

This book (along with volume 2 covers most of the traditional methods for polynomial root-finding such as Newtons, as well as numerous variations on them invented in the last few decades. Perhaps more importantly it covers recent developments such as Vincents method, simultaneous iterations, and matrix methods. There is an extensive chapter on evaluation of polynomials, including parallel methods and errors. There are pointers to robust and efficient programs. In short, it could be entitled A Handbook of Methods for Polynomial Root-finding. This book will be 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. - Gives description of high-grade software and where it can be down-loaded. - Very up-to-date in mid-2006; long chapter on matrix methods. - Includes Parallel methods, errors where appropriate. - Invaluable for research or graduate course.

Table of Contents

Preface	p. vii
Contents	p. ix
Introduction	p. xiii
Evaluation, Convergence, Bounds	p. 1
Horner's Method of Evaluation	p. 1
Rounding Errors and Stopping Criteria	p. 4
More Efficient Methods for Several Derivatives	p. 7
Parallel Evaluation	p. 8
Evaluation at Many Points	p. 11
Evaluation at Many Equidistant Points	p. 14
Accurate Evaluation	p. 17
Scaling	p. 22
Order of Convergence and Efficiency	p. 23
A Priori Bounds on (Real or Complex) Roots	p. 26
References for Chapter 1	p. 33
Sturm Sequences and Greatest Common Divisors	p. 37
Introduction	p. 37
Definitions and Basic Theorem	p. 37
Application to Locating Roots	p. 38
Elimination of Multiple Roots	p. 40
Detection of Clusters of Zeros (Near-Multiple)	p. 43
Sturm Sequences (or gcd's) Using Integers	p. 47
Complex Roots (Wilf's Method)	p. 49
References for Chapter 2	p. 51
Real Roots by Continued Fractions	p. 53
Fourier and Descartes' Theorem	p. 53
Budans's Theorem	p. 54
Vincent's Theorem	p. 55
Akritas' Improvement of Vincent's Theorem	p. 56
Applications of Theorem 3.4.1	p. 60
Complexity of m	p. 60
Choice of the a[subscript i]	p. 61
Cauchy's Rule	p. 62
Appendix to Chapter 3. Continued Fractions	p. 62
References for Chapter 3	p. 65
Simultaneous Methods	p. 67
Introduction and Basic Methods	p. 67
Conditions for Guaranteed Convergence	p. 72
Multiple Roots	p. 80
Use of Interval Arithmetic	p. 84
Recursive Methods	p. 90
Methods Involving Square Roots, Second Order Derivatives, etc	p. 92
Effect of Rounding Errors	p. 100
Gauss-Seidel and SOR Variations	p. 102
Real Factorization Methods	p. 108
Comparison of Efficiencies	p. 114
Implementation on Parallel Computers	p. 117
Miscellaneous Methods	p. 120
A Robust and Efficient program	p. 121
References for Chapter 4	p. 123
Newton's and Related Methods	p. 131
Definitions and Derivations	p. 131
Early History of Newton's Method	p. 135
Computable Conditions for Convergence	p. 137
Generalizations of Newton's Method	p. 141
Methods for Multiple Roots	p. 151
Termination Criteria	p. 158
Interval Methods	p. 161
Parallel Methods	p. 173
Hybrid Methods Involving Newton's Method	p. 175
Programs	p. 189
Miscellaneous Methods Related to Newton's	p. 190
References for Chapter 5	p. 196
Matrix Methods	p. 207
Methods Based on the Classical Companion Matrix	p. 207
Other Companion Matrices	p. 214
Methods with 0(N[superscript 2]) Operations	p. 231
Methods Designed for Multiple Roots	p. 257
Methods for a Few Roots	p. 289
Errors and Sensitivity	p. 294
Miscellaneous Methods and Special Applications	p. 304
Programs and Packages	p. 314
References for Chapter 6	p. 316
Index	p. 323
Table of Contents provided by Ingram. All Rights Reserved.