Computing the Zeros of Polynomials using the Divide and Conquer Approach
Michael R. Farmer · 2014
This is to certify that this PhD thesis is, to the best of my knowledge, entirely my own work, except where explicitly stated in the text, and that it has not been submitted, either in part or whole, for a degree at this or any other University. Signed...................................................................... ii The thesis describes two algorithms for locating all the zeros of arbitrary real or complex polynomials. This approach consists of two distinct stages. The first stage is called the search stage. Here, the complex plane is searched systematically for regions containing zeros of the original polynomial. This is essentially the “Divide and Conquer Approach ” of the title. Regions containing zeros are sub-divided into smaller regions which may contain zeros. During this process, those regions that do not contain zeros are discarded. This process is iteratively refined until the total number of zeros in the regions, i.e. those containing zeros, equals the degree of the polynomial. The centres of these regions are therefore approximations to the zeros themselves, some of which may be multiple in number. At this point, the algorithm switches to the second, or iterative, stage. Here, Iteration Functions (IFs) are used to accelerate convergence to the values of the zeros (to computational precision). Whilst carrying out this research we discovered new families of IFs that do not appear in the technical literature. The derivations of these IFs are in the body of the thesis. These IFs are showcased by showing their outputs for each of the polynomials tested. These outputs demonstrate the different orders of covergence of the IFs and other interesting features, explanations of which are included in Chapter 7, starting on page 87, of the thesis. A database of over 200 poynomials was built up and its contents are listed in Chapter 6, starting on page 66, and the results of applying our two-stage process to these polynomials are summarised in the thesis. Some of these polynomials are of high degree. iii