- Durand-Kerner method
In
numerical analysis , the Durand–Kerner method (established 1960–66) or method of Weierstrass (established 1859–91) is aroot-finding algorithm for solvingpolynomial equations. In other words, the method can be used to solve numerically the equation: ƒ("x") = 0
where ƒ is a given polynomial, which can be taken to be scaled so that the leading coefficient is 1.
Explanation
The explanation is for equations of degree four. It is easily generalized to other degrees.
Let the polynomial ƒ be defined by
:ƒ("x") = "x"4 + "ax"3 + "bx"2 + "cx" + "d"
for all "x".
The known numbers "a, b, c, d" are the
coefficient s.Let the (complex) numbers "P,Q,R,S" be the roots of this polynomial ƒ.
Then
:ƒ("x") = ("x" − "P")("x" − "Q")("x" − "R")("x" − "S")
for all "x". One can isolate the value "P" from this equation,
:
The substitution :is a strongly stable fixed point
iteration in that every initial point "x" ≠ "Q,R,S" delivers after one iteration the root "P".If one replaces the zeros "Q", "R" and "S" by approximations , , , 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":
:"p"0 := (0.4 + 0.9 i)0 ;:"q"0 := (0.4 + 0.9 i)1 ; :"r"0 := (0.4 + 0.9 i)2 ; :"s"0 := (0.4 + 0.9 i)3 ;
There is nothing special about choosing 0.4 + 0.9 i except that it is neither a
real number nor aroot of unity .Make the substitutions for "n" = 1,2,3,··· :where are again the Weierstrass updates.
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 with a radius .Here one has , so the centers are the next iterates of the Weierstrass iteration, and radii that are multiples of the Weierstrass updates. If the roots of ƒ("X") are all well isolated (relative to the computational precision) and the points are sufficidently close approximations to these roots, then all the disks will become disjoint, so each one contains exactly one zero. The midpoints of the circles will be better approximations of the zeros.
Every conjugate matrix of "A" is as well a companion matrix of ƒ("X"). Choosing "T" as diagonal matrix leaves the structure of "A" invariant. The root close to is contained in any isolated circle with center regardless of "T". Choosing the optimal diagonal matrix "T" for every index results in better estimates (see ref. Petkovic et al 1995).
Convergence results
The connection between the Taylor series expansion and Newton's method suggests that the distance from to the corresponding root is of the order , if the root is well isolated from nearby roots and the approximation is sufficiently close to the root. So after the approximation is close, Newton's method converges "quadratically"; that is: the error is squared with every step (which will greatly reduce the error once it is less than 1). 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 ƒ.
For the conclusion of linear convergence there is a more specific result (see ref. Petkovic et al 1995). If the initial vector and its vector of Weierstrass updates satisfies the inequality
:
Wikimedia Foundation. 2010.