<- previous index next ->
Consider the Maple root finding"
root12g.html
In general the roots of a polynomial are complex numbers.
A general purpose root finder for polynomials is difficult to
develop. Fortunately, some very smart people have written the
function, cpoly, that can take a general polynomial with complex
coefficients and find the complex roots. It also works with
real coefficients and real roots.
MatLab root finding for polynomials is just r = roots(p)
Where p is the vector of polynomial coefficients and
r is the vector of roots. Both r and p may be complex.
The Fortran code, including the test program (driver) is
419.for in Fortran IV, compiles with g95
419_f.out is the output of many test cases
The Java code, including the test program (driver) is
c419.java in standard Java
c419.out is the output of many test cases
The Ada code, including the test program (driver) is
long_complex_polynomial_roots.ada in Ada
To understand how some iterative methods can converge quickly,
consider how to compute sqrt when you have no math library:
sqrt.c
sqrt_c.out
So, since the sqrt iteration was basically Newtons method,
why not just use Newtons method to find roots?
here is how it works, even for complex roots.
f(x) = 0
guess x
x_next = x - f(x)/f'(x) f'(x) is the derivative of f(x)
repeat until |x_next-x| < epsilon
newton.c
newton_c.out
Notice the oscillation in the last few steps.
The problem can come from a bad guess that causes a big
oscillation. The problem can come from hitting an x
where f'(x) is zero. Thus, there have been many workarounds.
"cpoly" is one of the most general solutions.
<- previous index next ->