A modified Bairstow method for multiple zeros of a polynomial
| Autor: | F. M. Carrano |
|---|---|
| Rok vydání: | 1973 |
| Předmět: | |
| Zdroj: | Mathematics of Computation. 27:781-792 |
| ISSN: | 1088-6842 0025-5718 |
| DOI: | 10.1090/s0025-5718-1973-0334492-5 |
| Popis: | A modification of Bairstow's method to find multiple quadratic factors of a polynomial is presented. The nonlinear system of equations of the Bairstow method is replaced by high order partial derivatives of that system. The partiais are computed by a repetition of the Bairstow recursion formulas. Numerical results demonstrate that the modified method converges in many cases where the Bairstow method fails due to the multiplicity of the quadratic factor. Rail (4) has described a generalization of Newton's method for simultaneous nonlinear equations with multiple roots. This may be applied to solve the nonlinear Bairstow equations; however, it fails in some cases due to near-zero divisors. Examples are presented which illustrate the behavior of the author's algorithm as well as the methods of Rail and Bairstow. 1. Introduction. Bairstow's method (1) is a well-known algorithm to determine quadratic factors of a polynomial with real coefficients. It is limited, however, in that convergence is quadratic only if the zeros are complex conjugate pairs of multiplicity one, or are real of multiplicity at most two. For higher multiplicities it is impractically slow or subject to failure. An extension of the Bairstow method is described which relaxes this limitation. An algorithm due to Rail (4) for solving simultaneous nonlinear equations with multiple roots is also discussed in the context of Bairstow's procedure. 2. Newton's Method. The ideas to be presented are analogous to Newton's method and some of its modifications, and hence we begin our discussion at this point. Consider the polynomial P(x) with zero a. The Newton iteration function is (1) x - P(x)/P'(x). If a is a zero of multiplicity m, we consider two modified iteration functions, both of which are quadratically convergent. The first is obtained by observing that a is a simple zero of Pim~v(x). An application of Newton's method then gives (2) x - P{m-1)(x)/P^)(x). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|