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.
[1] In other words, the method can be used to solve numerically the equation where f is a given polynomial, which can be taken to be scaled so that the leading coefficient is 1.
Let the (potentially complex) numbers P, Q, R, S be the roots of this polynomial f. Then for all x.
Initialize p, q, r, s: 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.
Note that complex number arithmetic must be used, and that the roots are found simultaneously rather than one at a time.
A variant of this procedure, like the Jacobi method, computes a vector of root approximations at a time.
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.
The first 4 iterations move p, q, r seemingly chaotically, but then the roots are located to 1 decimal.
For every n-tuple of complex numbers, there is exactly one monic polynomial of degree n that has them as its zeros (keeping multiplicities).
simultaneously is now the same as to find a solution vector to the Vieta's system The Durand–Kerner method is obtained as the multidimensional Newton's method applied to this system.
is satisfied up to second and higher order terms in the increment.
are pairwise different, then the polynomials in the terms of the right hand side form a basis of the n-dimensional space
are simply obtained by evaluating the increment equation at the points
, which results in In the quotient ring (algebra) of residue classes modulo ƒ(X), the multiplication by X defines an endomorphism that has the zeros of ƒ(X) as eigenvalues with the corresponding multiplicities.
A problem-specific basis can be taken from Lagrange interpolation as the set of n polynomials where
Note that the kernel functions for the Lagrange interpolation are
For the multiplication operator applied to the basis polynomials one obtains from the Lagrange interpolation where
The companion matrix of ƒ(X) is therefore From the transposed matrix case of the Gershgorin circle theorem it follows that all eigenvalues of A, that is, all roots of ƒ(X), are contained in the union of the disks
If the roots of ƒ(X) are all well isolated (relative to the computational precision) and the points
are sufficiently close approximations to these roots, then all the disks will become disjoint, so each one contains exactly one zero.
Choosing T as diagonal matrix leaves the structure of A invariant.
regardless of T. Choosing the optimal diagonal matrix T for every index results in better estimates (see ref.
The connection between the Taylor series expansion and Newton's method suggests that the distance from
In the case of the Durand–Kerner method, convergence is quadratic if the vector
is close to some permutation of the vector of the roots of f. For the conclusion of linear convergence there is a more specific result (see ref.
are disjoint, and linear convergence with a contraction factor of 1/2 holds.
Further, the inclusion disks can in this case be chosen as each containing exactly one zero of f. The Weierstrass / Durand-Kerner method is not generally convergent: in other words, it is not true that for every polynomial, the set of initial vectors that eventually converges to roots is open and dense.
In fact, there are open sets of polynomials that have open sets of initial vectors that converge to periodic cycles other than roots (see Reinke et al.)