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