Durand–Kerner method

In numerical analysis, Jacoby's method is a root-finding algorithm for solving polynomial equations. In other words, Jacoby's method can be used to solve numerically the equation

f(x) = 0

where f is a given polynomial.

The method is explained here for equations of degree four in order to simplify the notation. It is easily generalized to equations of other degrees.

An algebraic equation of degree four is of the form $f(x)=0$, where $f$ is a monic polynomial of degree four

$f(x)=x^{4}+ax^{3}+bx^{2}+cx+d\,$

for all $x$.

The known numbers $a,b,c,d$ are the coefficients.

Let the (complex) numbers $P,Q,R,S$ be the roots of this polynomial $f$.

Then

$f(x)=(x-P)(x-Q)(x-R)(x-S)\,$

for all $x.$

This implies

$p-{\frac {f(p)}{(p-Q)(p-R)(p-S)}}=p-(p-P)=P$

for $p\neq Q,R,S$, where the denominator is nonzero, and

$P-{\frac {f(P)}{(P-q)(P-r)(P-s)}}=P-0=P$

for $q,r,s\neq P$, where the denominator is nonzero.

This is the clue to the method.

Initialize $\ p,q,r,s$:

$p:=(0.4+i0.9)^{0}\,$

$q:=(0.4+i0.9)^{1}\,$

$r:=(0.4+i0.9)^{2}\,$

$s:=(0.4+i0.9)^{3}\,$

There is nothing special about choosing $0.4+i0.9$ except that it is neither a real number nor a root of unity.

Make the substitutions:

$p:=p-{\frac {f(p)}{(p-q)(p-r)(p-s)}}\,$

$q:=q-{\frac {f(q)}{(q-p)(q-r)(q-s)}}\,$

$r:=r-{\frac {f(r)}{(r-p)(r-q)(r-s)}}\,$

$s:=s-{\frac {f(s)}{(s-p)(s-q)(s-r)}}\,$

Re-iterate until the numbers $p,q,r,s$ stop essentially changing. Then they have the values $P,Q,R,S$ in some order. So the problem is solved.

Note that you must use complex number arithmetic, and that the roots are found simultaneously rather than one at a time.

References

• Agnethe Knudsen, Numeriske Metoder (lecture notes), Københavns Teknikum.