The globalization of Durand-Kerner algorithm. (English) Zbl 0905.65058
The construction of a regularly homotopic curve with probability one, based on homotopy theory and the relation between a symmetric polynomial and a polynomial in one variable, is proposed. The discrete tracing along this homotopic curve leads to a class of Durand-Kerner algorithms with stepsizes as parameters. The convergence of this class of algorithms is known, which solves the conjecture about the global property of the Durand-Kerner algorithm. The problem for steplength selection is also discussed. For the verification of the proposed theory a numerical example is given.
Reviewer: J.Vaníček (Praha)
MSC:
| 65H05 | Numerical computation of solutions to single equations |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 26C10 | Real polynomials: location of zeros |
| 30C15 | Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) |
Keywords:
continuous homotopy; path tracing; global convergence; point estimation; Durand-Kerner algorithms; steplength selectionReferences:
| [1] | Zhao Fengguang and Wang Deren, Theory of Smale’s point estimation and convergence of Durand-Kerner algorithm, Mathmatica Numerica Sinica, 2 (1993) 196-206. (in Chinese) · Zbl 0850.65089 |
| [2] | Zheng Shiming, On the convergence of Durand-Kerner algorithm for the simultaneous determination of polynomial roots. Chinese Science Bulletin, 9 (1982) 515-517. (in Chinese) |
| [3] | G. Alefeld and J. Herzberger, On the convegence speed of some algorithms for the simultaneous approximation of polynomial roots, SIAM J. Numer. Anal., 11 (1974), 237-243. · Zbl 0282.65038 · doi:10.1137/0711023 |
| [4] | C. B. Garcia and W. I. Zangwill, Finding all solution to polynomial systems and other systems of equations, Math. Prog., 16 (1979), 159-176. · Zbl 0409.65026 · doi:10.1007/BF01582106 |
| [5] | T. Y. Li and T. Sauer, Homotopy method for generalized eigenvalue problems Ax=aBx, LAA., 91 (1987), 65-74. · Zbl 0621.65028 |
| [6] | T. Y. Li, T. Souer and J. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM. J. Numer, Anal., 24 (1987), 435-451. · Zbl 0625.65039 · doi:10.1137/0724032 |
| [7] | T. Y. Li, T. Souer and J. Yorke, The Cheater’s homotopy: An efficient procedure for solving systems of polynomial equations, SIAM. J. Numer. Anal., 26 (1989), 1241-1251. · Zbl 0689.65032 · doi:10.1137/0726069 |
| [8] | T. Y. Li, Z. Zeng and Li. Cong, Solving eigenvalue problems of real nonsysmetric matrices with real homotopies, SIAM. J. Numer. Anal., 29 (1992), 229-248. · Zbl 0749.65028 · doi:10.1137/0729015 |
| [9] | Shui-Nee Chow, J. M. Paret and J. A. Yorke, Finding zeros of maps: Homotopy methods that are constructive with probaility one, Math. Comp., 32 (1978), 887-899. · Zbl 0398.65029 · doi:10.1090/S0025-5718-1978-0492046-9 |
| [10] | S. T. Schwartz, Nonlinear Functional Analysis, Gordon and Breach, New York (1969). |
| [11] | E. Durand, Solutions namériques des équations algébriquées, Tome I: E’quations du Type F(x)=0, Raciues d’un Polynôme, Masson Paris (1960). |
| [12] | Wand Deren and Zhao Fengguang, Complexity analysis of a process for simultaneously obtaining all zeros of polynomials, Computing, 43 (1989) 187-197. · Zbl 0685.65042 · doi:10.1007/BF02241861 |
| [13] | Wang Deren and Wu Yujiang, Some modifications of the parallel Halley iteration method and their convergence, Computing, 38 (1987), 75-87. · Zbl 0589.65041 · doi:10.1007/BF02253746 |
| [14] | Wang Deren and Zhao Fengguang, The theory of Smale’s point estimation and its some application, JCAM, 60 (1993), 253-264. · Zbl 0871.65046 |
| [15] | Xu Senlin and Wang Zeke, System of Algebraic Equations and Computational Complexity, Science Press (1989). (in Chinese) · Zbl 0552.65045 |
| [16] | I. O. Kerner, Ein gesamtschritlverfahren zur berechnung der nullstellen von polynomen, Numer Math., 8 (1966), 290-294. · Zbl 0202.43605 · doi:10.1007/BF02162564 |
| [17] | Mo Zongjian, et al, Algebra, Vol. 1, Peking University Press (1987). (in Chinese) |
| [18] | E. L. Allgower and K. Georg, Numerical Continuation Methods, an Introduction, Springer-Verlag, New York (1990). · Zbl 0717.65030 |
| [19] | S. Smale, Newton’s method estimates from data at one point, in The Morging of Disciplines: New Directions in Pure, Applied and Computational Mathematics (R. Ewing, K. Gross, and G. Martin Editors), Springer-Verlag, New York (1986), 185-196. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
