Optimal inequality factor for Durand-Kerner's and Tanabe's methods

Octavian Cira; Cristian Mihai Cira

doi:10.33993/jnaat402-1043

Authors

Octavian Cira "Aurel Vlaicu" University, Arad, Romania
Cristian Mihai Cira Auburn University, USA

DOI:

https://doi.org/10.33993/jnaat402-1043

Keywords:

root-finding methods, polynomial zeros, simultaneous inclusion methods, Durand-Kerner's method, Tanabe's method, convergence, computational efficiency

Abstract views: 226

Abstract

The convergence condition for the simultaneous inclusion methods is \(w^{(0)}<c(a,b,n)d^{(0)}\), where \(w^{(0)}\) is the maximum Weierstrass factor \(W^{0}_k\), \(k\in I_n\), and \(d^{0}\) is the minimum distance between \(z^{(0)}_1\), \(z^{(0)}_2\), \(\ldots\), \(z^{(0)}_n\), the distinct approximations of the simple roots of the polynomial \(\zeta_1\), \(\zeta_2\),\(\,\ldots\), \(\zeta_n\). The i-factor (inequality-factor) is the positive real function \(c(a,b,n)=\tfrac{1}{an+b}\). The article presents the optimum i-factor for the simultaneous inclusion methods Durand-Kerner and Tanabe.

Downloads

Download data is not yet available.

References

N. H. Abel, Beweis der Unmoglichkeit, algebraische Gleichungen von hoheren Graden als dem vierten allgemein aufzulosen, J. Reine Angew. Math., 1, Reprinted in Abel, N. H. Œ (Ed. L. Sylow and S. Lie), Christiania (Oslo), Norway, 1881. Reprinted in New York: Johnson Reprint Corp., pp. 66-87, 1988, pp. 65-84, 1826, https://doi.org/10.1515/crll.1826.1.65 DOI: https://doi.org/10.1515/crll.1826.1.65

K. Weierstrass, Neuer Beweis des Satzes, dass jede ganze rationale Funktion einer Veränderlichen dargestellt werden kann als ein Product aus linearen Funktionen dertelben Verändelichen, Ges. Werke, 3, pp. 251-269, 1903. https://doi.org/10.1017/cbo9781139567886.018 DOI: https://doi.org/10.1017/CBO9781139567886.018

I. E. Durand, Solutions Numérique des Équations Algébriques. Équations du Type F(x)=0; Racines d'une Polynôme, Masson, Paris, 1, pp. 279-281, 1960.

K. Docev, An Alternative Method of Newton for Simultaneous Calculation of All the Roots of a Given Algebraic Equation, Phys. Math. J. Bulgar. Acad. Sci., 5, No. 2, pp. 136-139, 1962 (in bulgarian).

W. Börsch-Supan, A posteriori error bounds for the zeros of polynomials, Numer. Math., 5, pp. 380-398, 1963, https://doi.org/10.1007/bf01385904 DOI: https://doi.org/10.1007/BF01385904

I. O. Kerner, Simultaneous Displacement of Polynomial Roots if Real and Simple, Comm. ACM, 9, pp. 273, 1966, https://doi.org/10.1145/365278.365527 DOI: https://doi.org/10.1145/365278.365527

W.Börsch-Supan, Residuenabschätzung für Polynom-Nullstellen mittels Lagrange Interpolation, Numer. Math. 14, pp. 287-296, 1970, https://doi.org/10.1007/bf02163336 DOI: https://doi.org/10.1007/BF02163336

D. Braess and K. P. Handeler, Simultaneous inclusion of the zeros of polynomial, Numer. Math., 21, pp. 161-165, 1973. https://doi.org/10.1007/bf01436301 DOI: https://doi.org/10.1007/BF01436301

A. W. M. Nourein, An iteration formula for the simultaneous determination of the zeroes of polynomial, J. Comput. Appl. Math., 4, pp. 251-254, 1975, https://doi.org/10.1016/0771-050x(75)90016-9 DOI: https://doi.org/10.1016/0771-050X(75)90016-9

K. Tanabe, Behavior of the sequences around multiple zeros generated by some simultaneous methods for solving algebraic equations, Tech. Rep. Inf. Procces. Numer. Anal., 4-2, pp. 1-6, 1983 (in Japanese).

D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1986, address: Middlesex, England.

C. Carstensen, Anwendungen von Begleitmatrizen, Z. Angew. Math., 71. pp. 809-812, 1991.

C. Carstensen, Inclusion of the roots of polynomial based on Gerschgorin's theorem, Numer. Math., 59, pp. 349-360, 1991, https://doi.org/10.1007/bf01385785 DOI: https://doi.org/10.1007/BF01385785

C. B. Boyer and U. C. Merzbach , A History of Mathematics, CHAPTER: The Renaissance, Wiley, address: New York, edition: 2an, pp. 282-287, 1991.

M. S. Petković, C. Trajković and M. Carstensen, Weierstrass' formula and zero-finding methods, Numer. Math., 69, pp. 353-372, 1995, https://doi.org/10.1007/s002110050097 DOI: https://doi.org/10.1007/s002110050097

M. S. Petković, On initial conditions for the convergence of simultaneous root finding methods, Computing, 57, pp. 163-177, 1996, https://doi.org/10.1007/bf02276878 DOI: https://doi.org/10.1007/BF02276878

M. S. Petković and J. Herceg, Point estimation and safe convergence of root-finding simultaneous methods, Scientific Review, 21-22, pp. 117-130, 1996.

G. Birkhoff and S. Mac Lane, Galois Theory, CHAPTER: 15 in A Survey of Modern Algebra, PUBLISHER: Macmillan, address: New York, edition: 5th, pp. 395-421, 1996.

R. M. Corless, G. H. Gonnet, D. E. G. Hare , D. J. Jeffrey and D. E. Knuth, On the Lambert Function, Adv. Comput. Math., 5, pp. 329-359, 1996, https://doi.org/10.1007/bf02124750 DOI: https://doi.org/10.1007/BF02124750

M. S. Petković, J. Herceg and S. Ilić, Point Estimation Theory and its Applications, Institute of Mathematics, address: Novi Sad, 1997.

M. S. Petković and J. Herceg, Börsch-Supan-like methods: Point estimation and parallel implementation, Inter. J. Comput. Math., 64, pp. 117-130, 1997. DOI: https://doi.org/10.1080/00207169708804595

M. S. Petković and S. Ilić, Point estimation and the convergence of Ehrlich-Aberth metod, Publ. Inst. Math., 62, pp. 141-149, 1997.

P. Batra, Improvement of a convergence condition for the Durand-Kerner iteration, J. of Comp. and Appl. Math., 96 2, pp. 117-125, 1998, https://doi.org/10.1016/s0377-0427(98)00109-5 DOI: https://doi.org/10.1016/S0377-0427(98)00109-5

M. S. Petković, J. Herceg and S. Ilić, Safe Convergence of Simultaneous Methods for Polynomial Zeros, Numerical Algorithms, 17, pp. 313-331, 1998, https://doi.org/10.1023/a:1016688508558 DOI: https://doi.org/10.1023/A:1016688508558

M. S. Petković, J. Herceg and S. Ilić, Point estimation and some applications to iterative methods, BIT, 38, pp. 112-126, 1998, https://doi.org/10.1007/bf02510920 DOI: https://doi.org/10.1007/BF02510920

M. S. Petković and J. Herceg, On the convergence of Wang-Zheng's metod, J. Comput. Appl. Math., 91, pp. 123-135, 1998, https://doi.org/10.1016/s0377-0427(98)00034-x DOI: https://doi.org/10.1016/S0377-0427(98)00034-X

D. S. Dummit and R. M. Foote, Galois Theory, CHAPTER:14 in Abstract Algebra, Prentice-Hall, address: New York, edition: 2nd Englewood Cliffs, pp. 471-570, 1998.

M. S. Petković and J. Herceg, Point estimation of simultaneous methods for solving polynomial equations:a survey, J. Comput. Appl. Math., 136, pp. 183-207, 2001. DOI: https://doi.org/10.1016/S0377-0427(00)00620-8

O. Cira, Metode numerice pentru rezolvarea ecuaţiilor algebrice, Ed. Academiei Române, 2005, Bucureşti, (in Romanian).

O. Cira and C. M. Cira, The optimum convergence condition for the Durand-Kerner type simultaneous inclusion method, SYNASC 2006 - 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 171-174, 2006, address: Timişoara, România, month: 26-29 September, publisher: IEEE Computer Society, Los Alamitos California, Washington, Tokyo. DOI: https://doi.org/10.1109/SYNASC.2006.74

M. S. Petković, Point estimation of root finding methods, Springer, 2008, Lecture Notes in Mathematics 1933, https://doi.org/10.1007/978-3-540-77851-6 DOI: https://doi.org/10.1007/978-3-540-77851-6

Mathworld, howpublished: http://mathworld.wolfram.com, 30 Aug. 2010.

Wolfram, http://www.wolfram.com/products/mathematica, 30 Sept. 2010.