Welcome to AE Resources

ROOT FINDING

Root Finding with Complex Numbers

In some engineering applications, either solution of algebraic equations involves roots that are complex numbers, or the algebraic equations themselves involve complex numbers (in addition to possible roots). Thus, it is necessary to understand how to program both types of problems. The use of complex numbers requires care, as illustrated in the discussion on complex numbers.

Fortunately, most of the root finding methods available can be modified to include complex numbers, whether in the equation and/or in the roots. One mathematical concept to be aware of is the concept of complex conjugate pairs. That is they appear as r±i expressions.

Consider the equation x² = d. When d = 4, then the root is real and the bisection code

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!  Uses bisection method to find square root
!
!   x*x - c  = 0
!   over the interval [a,b]
!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
PROGRAM sqrt
  IMPLICIT NONE
  INTEGER :: nmax, n
  REAL :: tol, d
  REAL :: a, b, c
  REAL :: fa, fc

  WRITE(*,*) ’ Input Constant d (x^2-d=0) ’
  READ(*,*) d
  WRITE(*,*) ’ Input Lower and Upper Limits’
  READ(*,*) a, b

  tol = 0.0001
  nmax = 100

  fa = f(a,d)
  c = (a + b ) /2.
  fc = f(c,d)
  n = 1

  DO WHILE (n <= nmax)
     IF((b-a)/2.0 < tol) THEN
       WRITE(*,*) ’Root’,c,’gives’,fc,’after’,n,’iterations’
       EXIT
     ENDIF
     IF(fa*fc > 0.0) THEN
        a = c
     ELSE
        b = c
     ENDIF
     c = (a + b ) /2.
     fc = f(c,d)
     n = n + 1
  ENDDO

CONTAINS

   REAL  FUNCTION F(x,n)
   REAL :: x
   REAL :: n
   f = x*x - n
   END FUNCTION F
   
END PROGRAM

Input Constant d (x^2-d=0) 
4.
  Input Lower and Upper Limits
0.,3.
 Root   1.9999695 gives  -1.2207031E-04 after 15 iterations

So after fifteen iterations, the real root 2.0 is obtained (within the significant digits of the tolerance provided - decreasing the value of the tolerance increases accuracy). Increasing to seven significant digits only requires a few more iterations. Although only one root is computed, mathematically it is known that a real square root is symmetric about zero.

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., x² − rx − e). A simple scheme to deflate an n^th-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.

← Previous Page