In numerical analysis, the Weierstrass method or Durand–Kerner method, discovered by Karl Weierstrass in 1891 and rediscovered independently by Durand in 1960 and Kerner in 1966, is a root-finding algorithm for solving polynomial equations. In other words, the method can be used to solve numerically the equation
f(x) = 0,
where f is a given polynomial, which can be taken to be scaled so that the leading coefficient is 1.
Explanation
This explanation considers equations of degree four. It is easily generalized to other degrees.
Let the polynomial f be defined by
for all x.
The known numbers a, b, c, d are the coefficients.
Let the (potentially complex) numbers P, Q, R, S be the roots of this polynomial f.
Then
for all x. One can isolate the value P from this equation:
So if used as a fixed-point iteration
it is strongly stable in that every initial point x0 ≠ Q, R, S
delivers after one iteration the root P = x1.
Furthermore, if one replaces the zeros Q, R and S
by approximations q ≈ Q, r ≈ R, s ≈ S, such that q, r, s are not equal to P, then P is still a fixed point of the perturbed fixed-point iteration
since
Note that the denominator is still different from zero. This fixed-point iteration is a contraction mapping for x around P.
The clue to the method now is to combine
the fixed-point iteration for P with similar iterations
for Q, R, S into a simultaneous iteration for all roots.
Initialize p, q, r, s:
p0 := (0.4 + 0.9i)0, q0 := (0.4 + 0.9i)1, r0 := (0.4 + 0.9i)2, s0 := (0.4 + 0.9i)3.
There is nothing special about choosing 0.4 + 0.9i except that it is neither a real number nor a root of unity.
Make the substitutions for n = 1, 2, 3, ...:
Re-iterate until the numbers p, q, r, s
essentially stop changing relative to the desired precision. They then have the values P, Q, R, S in some order and in the chosen precision. So the problem is solved.
Note that complex number arithmetic must be used, and that the roots are found simultaneously rather than one at a time.
Variations
This iteration procedure, like the Gauss–Seidel method for linear equations, computes one number at a time based on the already computed numbers. A variant of this procedure, like the Jacobi method, computes a vector of root approximations at a time. Both variants are effective root-finding algorithms.
One could also choose the initial values for p, q, r, s
by some other procedure, even randomly, but in a way that
they are inside some not-too-large circle containing also the roots of f(x), e.g. the circle around the origin with radius , (where 1, a, b, c, d are the coefficients of f(x)) and that they are not too close to each other, which may increasingly become a concern as the degree of the polynomial increases.
If the coefficients are real and the polynomial has odd degree, then it must have at least one real root. To find this, use a real value of p0 as the initial guess and make q0 and r0, etc., complex conjugate pairs. Then the iteration will preserve these properties; that is, pn will always be real, and qn and rn, etc., will always be conjugate. In this way, the pn will converge to a real root P. Alternatively, make all of the initial guesses real; they will remain so.
Example
This example is from the reference 1992. The equation solved is . The first 4 iterations move p, q, r seemingly chaotically, but then the roots are located to 1 decimal. After iteration number 5 we have 4 correct decimals, and the subsequent iteration number 6 confirms that the computed roots are fixed. This general behaviour is characteristic for the method. Also notice that, in this example, the roots are used as soon as they are computed in each iteration. In other words, the computation of each second column uses the value of the previous computed columns.
{ |class="wikitable" |---- !it.-no. !p !q !r |---- !0 | +1.0000 + 0.0000i | +0.4000 + 0.9000i | −0.6500 + 0.7200i |---- !1 | +1.3608 + 2.0222i | −0.3658 + 2.4838i | −2.3858 − 0.0284i |---- !2 | +2.6597 + 2.7137i | +0.5977 + 0.8225i | −0.6320−1.6716i |---- ! 3 | +2.2704 + 0.3880i | +0.1312 + 1.3128i | +0.2821 − 1.5015i |---- ! 4 | +2.5428 − 0.0153i | +0.2044 + 1.3716i | +0.2056 − 1.3721i |---- ! 5 | +2.5874 + 0.0000i | +0.2063 + 1.3747i | +0.2063 − 1.3747i |---- ! 6 | +2.5874 + 0.0000i | +0.2063 + 1.3747i | +0.2063 − 1.3747i |---- |} Note that the equation has one real root and one pair of complex conjugate roots, and that the sum of the roots is 3.