Durand–Kerner method: Difference between revisions

Revision as of 15:07, 3 November 2020

Revision as of 15:11, 3 November 2020

Line 212:

==Convergence results==

The connection between the Taylor series expansion and Newton's method suggests that the distance from <math>z_k + w_k</math> to the corresponding root is of the order <math>O\big(|w_k|^2\big)</math>, 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 <math>\vec z = (z_1, \dots, z_n)</math> is close to some permutation of the vector of the roots of &fnof;''f''.

For the conclusion of linear convergence there is a more specific result (see ref. Petkovic et al. 1995). If the initial vector <math>\vec z</math> and its vector of Weierstrass updates <math>\vec w = (w_1, \dots, w_n)</math> satisfies the inequality

: <math>\max_{1 \le k \le n}\big |w_k\big| \le \frac1frac{1}{5n} \min_{1 \le j < k \le n}\big |z_k - z_j\big|,</math>

then this inequality also holds for all iterates, all inclusion disks <math>\textstyle D\leftbig(z_k + w_k, (n - 1) |w_k|\rightbig)</math>

are disjoint, and linear convergence with a contraction factor of ''1/2'' holds. Further, the inclusion disks can in this case be chosen as

: <math>\textstyle D\left(z_k + w_k, \frac14tfrac14 |w_k|\right),\qquadquad k = 1, \dots, n,</math>

each containing exactly one zero of &fnof;''f''.

==References==