Page 189 - Excel for Scientists and Engineers: Numerical Methods

166 EXCEL: NUMERICAL METHODS

procedure towards a particular root, as illustrated by the results for the same
polynomial shown in Figure 8-27.

Figure 8-27. The root that is returned can be very sensitive to the choice of trial value.
(folder 'Chapter 08 Examples', workbook 'Newton-Raphson Function', sheet 'Newton-Raphson')
If no root is found after 100 cycles of iteration, the function returns the #N/A
error value.
The advantage of this custom function compared to Goal Seek ... is, of
course, that if the coefficients aa, bb, cc, or dd are changed, the value of the root
is automatically updated.

Bairstow's Method
to Find All Roots of a Regular Polynomial
A regular polynomial is one that contains only integer powers of x. The
Bairstow (or Bairstow-Lin) method finds all roots, both real and imaginary, of a
regular polynomial with real coefficients. The method involves the successive
extraction of quadratic factors from the original polynomial of degree N and
subsequent reduced polynomials of degree N-2, N-4 and so on. The quadratic
formula is then used to obtain pairs of roots, either real or complex, from the
quadratic factors. If the degree of the polynomial is odd, then the remainder,
after extracting quadratic factors, will be a linear factor, yielding the final root
directly.
The calculation proceeds as follows. For the polynomial
y = + U,,-lX"-l + . . . + UlX + uo (8-8)
performing synthetic division by a trial quadratic
x2 +px + q (8-9)

yields a quotient and a remainder.
+
y = (x* +PX + 4) (b,,~"-~ b,,-l~n-3 + . . . + b2) + (RX + S) (8-10)
If (x2 +px + q) is an exact divisor, then the remainder (Rx + S) will be zero.
Our task therefore is to find the values of p and q that make (Rx + S, equal to
zero. This will make (x2 + YX + s) a quadratic factor of the polynomial.