Durand–Kerner method

The Weierstrass (Durand - Kerner ) process ( W (DK) method) is an iterative method for the simultaneous determination of all zeros of a univariate polynomial. It is named after Karl Weierstrass, who developed it as part of a proof for the fundamental theorem of algebra 1859-1891, and E. Durand and Kerner Realty, which in 1960 and 1966 respectively transferred into a computer algorithm.

The procedure

It is a standardized univariate polynomial with complex coefficients and leading coefficient 1 This is according to the fundamental theorem of algebra exactly n zeros and can be decomposed into linear factors,

From this formula, each of the zeros can be formally isolated, it is

This formula can be understood as a trivial fixed point iteration, the iteration

Is stationary obvious after the first iteration in the zero point.

If in the iteration of the other zeros of good approximations, there remains a fixed point and each iteration, which starts in the vicinity of the zero point, converges to these. The iteration of the W ( DK ) method arises when now be determined for all the zeros at the same time using this iteration proximity effects, and enters each specific approximation of a zero immediately in the determination of the nearest approximations of the other zeros.

At the beginning of each iteration n are pairwise distinct complex numbers. For the first step, these numbers can be chosen randomly, but different in pairs, in later steps are these figures for approximations of the zeros of p ( X).

The tuple is associated with the polynomial that has these complex numbers as zeros. From this polynomial, the derivative with respect to the indeterminates X is determined. There are

From p ( X) and the derivative, the Weierstrass corrections, k = 1, ..., n is determined and obtain the corrected result and tuple as input in the next iteration.

The iteration can be stopped, for example, if the correction is below a pre-determined return accuracy. ( The calculation accuracy should be slightly higher than this return accuracy. )

Variants of the method

The derivation given above determines the new approximations simultaneously, in parallel, from the old approximations. In the simplest implementation, the method but not the Aufdatierungen and thus the new approximations are sequentially sequentially determined. Therefore, the idea offers to use any new approximation of a zero immediately instead of the old. This difference between parallel and sequential Aufdatierung corresponds to the procedure analogous to the Jacobi and Gauss - Seidel method for iterative solution of linear systems of equations.

The sequential variant converges faster in many cases, however, this speed advantage is to be taken seriously in theory. The parallel version allows the use of faster polynomial method, such as Karatsuba or Schönhage - roads in the calculation of Aufdatierung at high polynomial degrees.

Example

To solve is the cubic equation. As Starttupel am elected by the complex parameter. This results in the following first iteration for the parallel variant of the iteration

And for the sequential variant of the iteration

In the first 4 iterations of both variants, the triple is seemingly chaotic moves from step 5 are being increasingly more decimal constant iteration 8 in parallel or 7 in the sequential case confirm the correctness of iteration 7 and 6, respectively, within the stated accuracy. This general behavior is characteristic of this method.

As a 3rd degree equation with real coefficients has p ( X) is a real root and a complex conjugate pair of zeros. The approximations satisfy this pattern. After the record set by Vieta eg the sum of all zeros must be the negative of the coefficient of the second highest degree, by being 3. This is also confirmed in the approximations.

Justification as Newton's method

The - at least local - Convergence of the Weierstrass iteration arises from their interpretation as a multidimensional Newton's method. The system of equations to results from the comparison of the coefficients of the same degree in the desired identity

Since the polynomials are normalized on both sides ( the höchstgradige coefficient is 1), the identity is trivial in degree n and there are n equations for the n unknowns.

In general, this identity is not satisfied. The correction in each step of the Newton iteration arises from the requirement that the identity

Is to first order fulfilled. From the Taylor expansion of the first order in the linear equation

Every single correction can it be by inserting

Be gained, what the above mentioned Weierstrass correction results.

A global convergence proof of this method has already been given in (K. Weierstrass 1891) as an alternative proof of the fundamental theorem of algebra.

Error estimation using Gerschgorin circles

An error estimation and an alternative derivation of the method is given in the article at the rate of Gerschgorin. After that are contained in the union of the circular disks in each iteration all zeros of the polynomial p ( X). Are the circular disks are pairwise disjoint, so each contains exactly one zero. (A. Neumaier 2003) shows the same statement for the slightly smaller circular disks