2.4 Computer Spreadsheet Implementations.2.4.1 The Bairstow Spreadsheet.The Bairstow spreadsheet comprises four separate sheets. The first contains basic instructions, an area for the input of polynomial coefficients, and an area for the display of the roots found, with real and imaginary components presented in the form ai ± j bi. The input of initial guesses of r and s are not necessary because, via testing, optimum values have been found for a very wide range of polynomial characteristics, and are selected according to the coefficient inputs. However, a facility for the manual input of r and s has been provided should it be so required. Also included in this sheet, is the possible multiple root error warning message, shown just below the root output display. The second sheet in this spreadsheet is the Bairstow process calculation sheet which does not require user intervention. It is displayed during operation, where it shows not only the root determination process in operation, but also the part multiplicity root check algorithm, and the divergence, hunting and reduced equation corruption avoidance mechanisms, (for this last, see Section 2.4.4). Note that sometimes during operation, this sheet appears to "freeze", with only the cycle counter and the accuracy limit counter operating. This is normal and means that the iteration amplitude has reduced to zero, and the accuracy limit is being counted down to meet that attained by the iteration process, i.e. the hunting avoidance mechanism. The third sheet contains the new algorithm for the extraction of the (n - 1) multiples plus one singular root. Finally, the fourth sheet contains further information and instructions, the latter primarily the procedure to be adopted when possible multiple root errors have been indicated in the results. A disclaimer on the use of this spreadsheet is also included here.
2.4.2 The Polynomial Construction Spreadsheet.This spreadsheet comprises three separate sheets. The first will generate any polynomial up to order 10 from the input of its real/complex roots. This sheet is provided primarily for twofold use. First, in removing multiple root errors in those roots found via the Bairstow spreadsheet. To that end a facility has been included to enable the detailed and precise iteration, positive or negative, of any root component. This process allows the reformulation of the coefficients of the original equation, so removing multiple root errors and thereby obtaining a set of very precise roots. The second purpose of this sheet is to determine, again from a reconstruction of the original polynomial, the correct roots of an equation with complex coefficients when it contains roots with both positive and negative imaginary components The second sheet deals with the multiplication of any two polynomials of order 1 to 5, with either real or complex coefficients. It is primarily provided to enable multiplication of complex conjugate polynomials, so that equations with complex coefficients can be analysed in the Bairstow spreadsheet for their roots.
The third sheet once again contains further information, instructions and a
disclaimer.
Microsoft EXCEL 97 or later is needed to run them.
2.4.3 Testing.The testing discussed here concerns only the Bairstow spreadsheet. It is emphasised that it is of course not possible to test all configurations of polynomials, there being for even just quadratics, an infinite number etc. The results quoted below can therefore only be considered as typical, and variations may be experienced either up or down depending upon any polynomial analysed. When just singular roots are involved, they were all correctly identified to an accuracy of at least 0.001%, albeit only to the displayed four decimal places. The cases tested were a combination of very small, very large and a mixture of same, covering both real and complex conjugate roots.
The major part of the test programme was concerned with polynomials that
contained a multiplicity of identical roots. In the group of polynomials of
orders 3 to 10 inclusive, there are 127 possible combinations of multiple
roots. All of these were tested with both integer and four decimal place
roots with results as shown in the following table.
Note: The nomenclature 3+1+1 means a triple root plus two singles etc. All of the above discrepancies were able to be eliminated via the Polynomial Construction facility. Note that where there were n multiple roots, no errors were encountered, and with respect to the new algorithm for (n - 1) multiple roots plus a single, again no errors resulted.
2.4.4 Limitations.Apart from the obvious limitations deliberately included of displayed output to a maximum of 4 decimal places, and the maximum order of polynomial being 10, (5 for those with complex coefficients), there are two other limitations of the application presented here. When the roots are greatly separated, the method can give fictitious results. This is because if a very large root is taken in conjunction with a very small one, the accuracy with which the small root is taken is governed by that applicable to the large. This can cause the small root to be very inaccurate, which in turn can corrupt the reduced equation so resulting in the rest of the roots also being grossly wrong. To avoid this wherever possible, a method of detecting corruption of the reduced equation has been incorporated. When this is triggered, the process is halted, the values of r and s varied, and the process re-initialised and re-started. In extreme cases this form of corruption can persist after adjustment of r and s. In such cases the avoidance procedure will trigger for a maximum of 10 times with increasingly large values of r and s adjustment. Subsequently, the root finding process is allowed to continue. In these cases the results should be carefully checked via the Polynomial Construction spreadsheet facility to ensure that the roots found are good. With regard to this feature, it is also very important to note that, there are a number of polynomials which inherently exhibit the criteria used here to test for corruption of a reduced equation. i.e. equations containing complex roots or real roots with mixed parity. These equations will, after the above 10 times test, be factored correctly. The penalty incurred by way of delay in these equations being analysed, is merely a matter of a few seconds. The second limitation concerns the computational hardware. All computers are subject to very small rounding errors, and when computing with very large numbers, these can become significant. This limits the size of a0 in this application to between 1E-9 and 1E+40. Outside of this range, accuracy may in some cases be in excess of that quoted in Table 2.1. A warning message is shown accordingly.
M3 Version 1.0.0
Ó
P.G.Bass, January 2010
| ||||||||||||||||||||||||||||||||||||||||
On to the Next Section:- Conclusions Back to the Introduction to this Paper:- Bairstow Polynomial Roots Back to the Home Page for this Site:- Home |