EXPLANATION FILE OF PROGRAM LIN =============================== Lin's Method ------------ The discussion deals with two root-seeking algoruthms that capitalize on the specific functional form of polynomials. the first method, that of Lin, (*) applies the knowledge that the complex roots of real-valued coefficient poly- nomials come in complex conjugate pairs, and that an iterative procedure involving synthetic division can be employed to extract a quadratic factor using only real-number operations. The second technique to be discussed, that of Bairstow, (**) (see file Bairstow.txt) is an extension of the Lin method and contains a Newton iteration step that accelerates convergence. Lin's method is based on the simple observation that if complex roots occur, they must exist in complex conjugate pairs. This means that any polynomial of degree two or greater must contain a quadratic factor having only real coef- ficients. We will take as our starting polynomial the following standard form: 2 n P(z) = a + a z + a z + ... + z (7.10.1) 0 1 2 Note that it is irnplicitly assumed that an = 1. If we arbitrarily pick a qua- dratic factor z^2 + Az + B, then P(z) can be rewritten as 2 n-2 P(z) = (z + Az + B) (B + B z + ... + z ) + B + B (7.10.2) 2 3 1 0 If, by some means, the quadratic factor were chosen so that B1 = 0 and B2 = 0, then the two roots of that factor would also be roots of P(z). Therefore, the goal is to determine A and B so that B1 = 0 and B0 = 0. By comparing like powers of z in equations (7.10.1) and (7.10.2), we get the following sequence of equations: B = A - A n-1 n-1 B = A - B n-2 n-2 ---------------- B = A - AB - BB n-j n-j n+1-j n+2-j A = (A - BB )/B 1 3 2 B = A / B 0 2 (This is an application of the uniqueness theorem for polynomials. If two polynomials are equal, then the coefficients of like powers are equal). If A and B are only guesses, then the last two equations offer a means to partially correct those guesses. This new estimate pair can then be employed to make another pass through the set of equations in order to derive yet another improved estimate. As usual, the algorithm is not perfect. Convergence is not always ensured, especially when multiple roots are encountered. Also, convergence may be very slow. This is aggravated by the observation that small relative errors in the final estimates of A and B result in much larger relative errors in the finally derived roots. To demonstrate this last comment, we will consider the quadratic factor x^2 + 2x + (1 + eps), where eps represents the error in the coefficient, B. The corresponding roots are -1 + sqrt(eps) and -1 - sqrt(eps). Even if the error in the coefficient is small, say 1O-6, the error in the root can be large (e.g., 10-3). This observation regarding the error is factored into the algo- rithm by using the square of the convergence criterion. The Lin algorithm has been implemented in program LIN. For the examples ta- ken, the initial values of A and B were chosen quite arbitrarily: A = pi and B = sqrt(2). Other choices could be 1) A = A , B = A : the iteration tends to seek out the largest n-1 n-2 roots. 2) A = A , B = A : the iteration tends to seek out the smallest 1 0 roots. 3) A = 0, B = 0: this appears to be an effective starting point in many cases. As an exercise, experiment with different starting values. In the first two examples, the polynomial examined was P(z) = z(z - l)(z - 2)(z - 3)(z - 4). The z = 0 root was determined quite accurately, but convergence was slow, as indicated by the error in the z = 1 root. The second two examples involved the stress-case polynomial P(z) = (z + 1)^5, multiple roots. Convergence occurred, but again, it was very slow. Lin's algorithm is a reasonably straightforward application of some of the basic properties of polynomials and iterative procedures. Its major drawback is that it is only slowly convergent. Also, it is limited to polynomials of the fourth degree and higher. ln the file bairstow.txt, we will consider a more complicated, but a much more rapidly convergent algorithm, Bairstow's method. ----------------------------------------------------------------------------- (*) The discussion here is based on that given in A Practical Guide to Computer Methods, by T. E. Shoup. (**) For further information, see the reference given above, as weil as Nume- rical Calculaiions and Algorithms, by R. Becket and J. Hurt: Computer Methods for Science and Engineering, by R. L. LaFara; and Introduction to Applied Numerical Analysis, by R. Hamming. From [BIBLI 01]. ----------------------------------------------------------------------------- End of file lin.txt