| Abstract: | In linear algebra, the eigenvalues of a matrix are equivalently defined as the zeros of its characteristic polynomial. Determining the zeros of polynomials by the computation of the eigenvalues of a corresponding companion matrix turns the table on the usual definition. In this dissertation, the work of Newbery has been expanded and a (complex) symmetric or nonsymmetric companion matrix associated with a given characteristic polynomial has been constructed. Schmeisser's technique for the construction of a tridiagonal companion matrix associated with a polynomial with real zeros has been generalized to polynomials with complex zeros. New matrix algorithms based on Schmeisser's and Fiedler's companion matrices are developed. The matrix algorithm which is based on Schmeisser's matrix uses no initial values and computes the simple and multiple zeros with high accuracy. The algorithms based on Fielder's matrices are applied recursively, and require initial values as approximations to the true zeros of the polynomial. A few techniques concerning the choice of the required initial values are also presented. An important part of this thesis is the design of a new composite three-stage matrix algorithm for finding the real and complex zeros of polynomials. The composite algorithm reduces a polynomial with multiple zeros to another polynomial with simple zeros which are then computed with high accuracy. The exact multiplicities of these zeros are then calculated by means of Lagouanelle's limiting formula. The QR algorithm has been used in all the algorithms to find the eigenvalues of the companion matrices. The effectiveness of these algorithms is illustrated by presenting numerical results based on polynomials taken from the literature and considered to be ill-conditioned, as well as random polynomials with randomly generated zeros in small and large clusters. Polynomials are represented and evaluated in quadruple precision; but it suffices to use a double precision QR algorithm in order to obtain almost double precision in the zeros of polynomials. |