Welcome to AE Resources
Converted document
When expanding to complex numbers, the “line” search must now become a “planar” search. The search must approach the root from both the real and complex directions. Each of these must be taken independently.
One way to avoid using the complex roots is to use a modified form of Newton’s method that permits operations only on real parameters. This is known as Bairstow’s method. Bairstow’s method for solving polynomials relies on the process known as polynomial deflation. That is, it reduces the order of the polynomial using synthetic division. For real roots, a monomial factor (e.g., x − d) is used to deflate the polynomial, while for complex roots, a quadratic factor (e.g., x2 − rx − e). A simple scheme to deflate an nth-order polynomial by the factor x − t is: 
r = a(n)
a(n) = 0.0
DO i=n-1, 0, -1
     s = a(i)
     a(i) = r
     r = s + r * d
ENDDO
If x − d is one of the roots of the polynomial, then the remainder, r will be zero. The coefficients of the quotient are stored in a during the loop.
For complex roots, the original polynomial:
(1) fn(x) = a0 + a1x + a2x2 + ... + anxn
becomes lower by two orders (n − 2) after deflating by the quadratic:
(2) fn − 2(x) = b2 + b3x + ... + bnxn − 2
with a remainder R = b1(x − d) + b0. The deflation scheme is similar to the real root scheme: 
b(n)=a(n)
b(n-1) = a(n-1) + r*b(n)
DO i=n-2, 0, -1
     b(i)=a(i)+r*b(i+1)+e*b(i+2)
ENDDO
While n >  = 3, the polynomial will be deflated. When the polynomial is a quadratic, then the two roots can be computed using the simple quadratic rule:
(3) x = (r±√(r2 + 4*e))/(2)
If the polynomial is first order, then x =  − e ⁄ r. The roots of the quadratic equation can be easily computed using 
SUBROUTINE quad(r,e,r1,i1,r2,i2)
REAL :: r, e, r1, i1, r2, i2, d
d = r2 + 4*e
IF (d > 0.0) THEN
         r1 = 0.5 * (r + SQRT(d))
         r2 = 0.5 * (r - SQRT(d))
         i1 = 0.0
         i2 = 0.0
ELSE
         r1 = r/2
         r2 = r1
         i1 = SQRT(ABS(d))*0.5
         i2 = -i1
ENDIF
END SUBROUTINE quad
← Previous Page
← Previous Page