Using Optimization to Extract Roots of Real Coefficient Polynomials

[Namir]

I stumbled on the the Durand-Kerner method which locates the roots of a polynomial simultaneously using an iteration scheme that resembles the Gauss-Seidel method for solving systems of linear equations.

The Durand-Kerner method employs complex mathematics throughout it's calculations. The initial guess, all complex numbers, are rather arbitrary. The seem to work for most cases.

Here is a Matlab implementation.

Code:

function xroots = durand_kerner(polyCoeffs,toler)
% DURAND_KERNER calculates the roots of a polynomial simultaneously. The
% method is relatively simple and easy to implement. The Durand-Kerner
% algorithm resembles the Gauss–Seidel method for solving simultneous linear
% equations.

  n = length(polyCoeffs) - 1;
  xroots = zeros(n,1);
  for i=1:n
    xroots(i) = complex(0.4,0.9)^i;
  end
  bStop = false;
  while ~bStop
    lastRoots=xroots;
    for i=1:n
      prod = 1;
      for j=1:n
        if i~=j
          prod = prod * (xroots(i) - xroots(j));  
        end
      end
      xroots(i) = xroots(i) - polyval(polyCoeffs,xroots(i))/prod;
    end
    
    bStop = true;
    for i=1:n
      if abs(abs(lastRoots(i)) - abs(xroots(i)))>toler
        bStop = false;
        break;
      end
    end
  end
  
end

Here is a simple example:

Code:

>> C1=[1 -3 3 -5];
>> roots(C1)

ans =

   2.5874 + 0.0000i
   0.2063 + 1.3747i
   0.2063 - 1.3747i

>> xroots = durand_kerner(C1,1e-10)

xroots =

   2.5874 - 0.0000i
   0.2063 + 1.3747i
   0.2063 - 1.3747i