FACTORIZATION OF A POLYNOMIAL

Abstract

The problem of finding the roots of a polynomial is the most occurring problem in many areas of applied mathematics as well as in engineering, rising either as a problem in itself or as an intermediate step in solving a more complex problem. Numerical methods for finding the, roots are often required in the analysis, design or implementation of control systems, stability problems, nonlinear circuits, differential and difference equations etc. The location of poles and roots of a network function, the determination of eigen values for a linear time invariant system and the root locus plot for a linear feed back system etc. are just but a few of the examples that involve the solution of a polynomial equation with real coefficients. In the analysis of non linear control systems where the describing function technique is employed, the describing function of a multivalued non-linearity is represented by a complex function. As such, the characteristic equation for the feed back system is a polynomial equation with complex coefficients. Also, in electromagnetic wave propagation in plasma, the index of refraction is governed by the Appleton-Hartee equation which, in fact, is a polynomial equation with complex coefficients. All these applications of a polynomial equation have led to the development of a great number of numerical methods for finding its roots. A number of numerical methods which generally take the form of an iterative procedure, have been practically applicable together with the rapid development of computers since last thirty years. Some of the well known basic methods are Newton-Raphson's method, Laguerre's method, Bernoulli's method, Muller's method, Lin's method, Bairstow's method, Lehmer Schur's method, Graeffe's method and Quotient-Difference method etc. Most of these methods are applicable to the polynomials having real coefficients only as it is much more difficult to find algorithms which solve the complex coefficients polynomial. Of course, Muller's method could give solution to complex polynomial but complex roots of higher multiplicities are not easily solvable by this method. The present thesis has been devoted to develop numerical methods to find out all the roots of a polynomial having integer or rational coefficients, real coefficients and complex coefficients. The thesis comprises the following eight chapters (iv) The Chapter I of the thesis is Introduction. In this chapter brief description of the applications of the root finding problem is illustrated. Functional properties of the" coefficients and roots are also described in brief. The details of few numerical methods are outlined and a brief account of the related studies done by various mathematicians are given.The Libraries of University of Roorkee, I.I.T. Delhi, Indian National Scientific Documentation Centre, New Delhi and personal efforts by requesting authors of research papers have been the provision sources for the study material. In Chapter II, the problem of finding the roots of a polynomials having rational coefficients is considered. The method is confined to those polynomials which are reducible into linear integer factors or integer quadratic factors. The linear factors, including their multiplicities, are obtained by applying Rational Zero Theorem and the polynomial is deflated accordingly by well known Horner's method. The functional properties of an integer polynomial are used to obtain the integer quadratic factors, if exist. These quadratic factors give all the irrational and complex roots of the polynomial. The method is tested on a number of polynomials having rational coefficients. The computed results are compared with available results obtained by different methods. It is found that the present method gives exact results in lesser amount of time. (v) In Chapter III, a composite method is presented for finding the roots of a polynomial having real coefficients. Since a small change in the magnitude of coefficients of a polynomial sometimes cause computational problems in root finding algorithms, as floating point arithmetic operations on such coefficients may render overflow or under flow. Therefore, to suppress overflow/underflow and roundoff error, it is desirable to supplement root finding methods with efficient algorithms for scaling down the variation in the coefficient magnitude of such polynomials before approximating their roots. In this chapter, we have considered the effect of variation in the magnitude of coefficients of a real polynomial on its roots when a root finding algorithm is applied. Our composite method consists of two basic parts. First, the input coefficients are scaled to minimize their variation of orders of magnitude. Secondly, the scaled polynomial is then factored through the deflation process by extracting a quadratic factor each time. The method has been tested on various well and ill-conditioned polynomials and with multiple roots. The roots obtained after scaling are more accurate and computed in lesser number of iterations as compared to that of the roots obtained without scaling the coefficients of the polynomials. In Chapter IV, a bisection method for finding the roots (counting their multiplicities) of a complex or real polynomial (vi) is considered. The method finds the number of roots in a given rectangle in the complex plane and computes the roots and their multiplicities by locating them on or near the boundary of a rectangle using principle of argument. The method is deflation free and computes all the roots within a specified accuracy along with their multiplicities. The method has been applied on different polynomials, complex or real, having simple as well as multiple roots. The method has proved itself to be better compared to that of Wilf's bisection method as it avoids formation of Sturm's sequences in order to compute the number of roots lying inside a closed rectangle or square. In Chapter V, two different methods are developed for finding out real polynomial factor of a complex polynomial in order to reduce the degree of a complex polynomial. Since real factor of a complex polynomial can be computed by finding out the greatest common divisor of its real and imaginary parts Of its coefficients. In case of polynomial having Gaussian integer coefficients, exact GCD having integer coefficients is obtained by applying Bareiss's integer preserving algorithm In case of polynomial having floating point coefficients, polynomial division may not yield the accurate GCD, Hence an approximate GCD is first obtained by applying Euclidean algorithm along with normalization criterion, which is further improved by iterative division. Thus a complex polynomial is divided into two sub-polynomials, one real and another complex polynomial of (vii) lesser degree. Real polynomial is solved by applying the deflated polynomial approximation method discussed in Chapter III and the reduced complex polynomial is solved by the method discussed in Chapter IV. In Chapter VI, a hybrid method for computing the roots of complex polynomial following Soukup's process is developed. The method starts with an initial guess value of the root as zero and the process is iteratively performed until the absolute of the evaluated value of the polynomial is less than certain specified accuracy. The multiplicity of the root thus obtained is determined using values of the given polynomial and its first derivative at the approximated intervals of roots. After determining the multiplicity of the root, Newton-Raphson method is applied to improve the root. Once a root and its multiplicity is determined, Soukup procedure is applied on the deflated polynomial of reduced degree. The method has been applied on various complex polynomials having multiple and simple roots. It is observed that the hybrid method performs well with simple as well as multiple roots. In Chapter VII, approximate roots of a complex polynomial are obtained by applying modified Laguerre's method and their multiplicities are determined by evaluating polynomial and its first and second derivative at the approximated interval of roots. Laguerre's method has long been known as one of the best for approximating roots of a polynomial. The sequential modification of Laguerre's method given by Hansen uses the root already obtained and avoids polynomial deflation. After finding an approximate root, its multiplicity is estimated using a function which involves polynomial value and its first and second derivative values as required in Laguerre's method. In order to improve there roots, complex circular arithmetic is applied. Circular arithmetic has been introduced as a necessary tool for the construction of an iterative procedure for determining all the roots simultaneously in terms of circular region. In order to reduce the amount of computational work, circular interval method based on Halley's like algorithm is applied after obtaining the roots and their multiplicities by Laguerre's method. It is observed that complex multiple roots as well as simple roots are greatly improved only after one step. The advantages and drawbacks of different proposed methods are discussed in Chapter VIII which is the concluding chapter of the thesis. The validity of different methods are tested by comparing the results obtained with exact or previously published results. The computed results are reported at the and of each chapter.