THE GLOBALIZATION OF DURAND-KERNER ALGORITHM

Applied Mathematics and Mechanics (English Edition) ›› 1997, Vol. 18 ›› Issue (11): 1045-1057.

THE GLOBALIZATION OF DURAND-KERNER ALGORITHM

赵风光¹, 王德人²

1. Shanghai University, Shanghai 201800, P. R. China;
2. Fudan University, Shanghai 200433, P. R. China

收稿日期:1996-10-16 修回日期:1997-06-23 出版日期:1997-11-18 发布日期:1997-11-18
基金资助:
Project supported by the National Natural Science Foundation of China

THE GLOBALIZATION OF DURAND-KERNER ALGORITHM

Wang Deren¹, Zhao Fengguang²

1. Shanghai University, Shanghai 201800, P. R. China;
2. Fudan University, Shanghai 200433, P. R. China

Received:1996-10-16 Revised:1997-06-23 Online:1997-11-18 Published:1997-11-18
Supported by:
Project supported by the National Natural Science Foundation of China

摘要/Abstract

摘要： Making use of the theory of continuous homotopy and the relation betweensymmetric polynomtal and polynomtal in one variable the arthors devoted ims article to constructing a regularly homotopic curve with probability one. Discrete tracingalong this honlotopic curve leads 10 a class of Durand-Kerner algorithm with stepparameters. The convergernce of this class of algorithms is given, which solves theconjecture about the global property of Durand-Kerner algorithm. The.problem forsteplength selection is thoroughly discussed Finally, sufficient numerical examples areused to verify our theory

关键词: Durand-Kerner algorithm, continuous homotopy, path tracing, global convergence, point estimation

Abstract: Making use of the theory of continuous homotopy and the relation betweensymmetric polynomtal and polynomtal in one variable the arthors devoted ims article to constructing a regularly homotopic curve with probability one. Discrete tracingalong this honlotopic curve leads 10 a class of Durand-Kerner algorithm with stepparameters. The convergernce of this class of algorithms is given, which solves theconjecture about the global property of Durand-Kerner algorithm. The.problem forsteplength selection is thoroughly discussed Finally, sufficient numerical examples areused to verify our theory

Key words: Durand-Kerner algorithm, continuous homotopy, path tracing, global convergence, point estimation

赵风光;王德人. THE GLOBALIZATION OF DURAND-KERNER ALGORITHM[J]. Applied Mathematics and Mechanics (English Edition), 1997, 18(11): 1045-1057.

Wang Deren;Zhao Fengguang. THE GLOBALIZATION OF DURAND-KERNER ALGORITHM[J]. Applied Mathematics and Mechanics (English Edition), 1997, 18(11): 1045-1057.

参考文献

[1] Zhao Fengguang and Wang Deren, Theory of Smale's point estimation and convergence of Durand-Kerner algorithm, Mnrhmnrico Nurrrcrica Sinica, 2 (1993), 196-206. (in Chinese).
[2] Zheng Shirring, On the convergence of Durand-Kerner algorithm for the simultaneous determination of polynomial roots. Chine se Science Bullrrin, 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 .
[4] C. B. Garcia and W. 1. Zangwill, Finding all solution to polynomial systems and other systems of equations, Mach. Prog., 16(1979), 159-176.
[5] T. Y. Li and T. Sauer, Homotopy method for generalized eigenvalue problems Ax=aBx,LAA., 91 (1987), 65-74.
[6] T. Y. Li, T. Souer and J. Yorke, Numerical solution of a class of deficient polynomial systems, SLA}11. J. Nruncr, Anal., 24 (1987). 435-451.
[7] T. Y. Li, T. Souer and J. Yorke, The Cheater's homotopy: An efficient procedure for solving systems of polynomial equations, SIAM. J. Nuruer. Anal., 26 (1989), 1241-1251.
[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.
[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.
[10] S. T. Schwartz, h'orrlirtear Fmtctional Arralosis, Gordon and Breach, New York (1969).
[11] E. Durand, Solutions nameriques des equations algebriquees, Tome I: E'quatioras du Type F(x)=0, Raciues d'urr Poltvrortre, Masson, Paris(1960).
[12] Wand Deren and Zhao Fengguang, Complexity analysis of a process for simultaneously obtaining all zeros of polynomials, Cortrprrtirrg, 43(1989), 187-197.
[13] Wang Deren and Wu Yujiang, Some modifications of the parallel Halley iteration method and their convergence, Contptrring, 38(1987), 75-87.
[14] Wang Deren and Zhao Fengguang, The theory of Smale's point estimation and its some application, JCAM, 60 (1993), 253-264.
[15] Xu Senlin and Wang Zeke, Sostem of Algebraic Eqrratious arid ComptrtationAl Contplexitr, Science Press(1989). (in Chinese).
[16] I. O. Kerner, Ein gesamtschritlverfahren zur berechnung der nullstellen von polynomen, Nurtter Math., 8(1966), 290-294.
[17] Mo Zongjian, et al, Algebra, Vol, I,Peking University Press(1987). (in Chinese).
[18] E. L. Allgower and K. Georg, h'rurrerical Coruiruration Mcrlrods, an Introduction, Springer-Verlag, New York(1990).
[19] S. Smale, Newton's method estimates from data at one point, in The Morging of Disciplines: New Directions in Pure. Alrplied and Contprrtationrrl lllatlrenratics (R. Ewing).K. Gross, and G. Martin Editors, Sprinoer-Verlag. New York (1986),185-196.

THE GLOBALIZATION OF DURAND-KERNER ALGORITHM

THE GLOBALIZATION OF DURAND-KERNER ALGORITHM

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

本文评价

[1]	曾友芳白延琴简金宝唐春明. Two new predictor-corrector algorithms for second-order cone programming[J]. Applied Mathematics and Mechanics (English Edition), 2011, 32(4): 521-532.
[2]	朱志斌简金宝张聪. An SQP algorithm for mathematical programs with nonlinear complementarity constraints[J]. Applied Mathematics and Mechanics (English Edition), 2009, 30(5): 659-668.
[3]	王一晶王龙. ADAPTIVE GENERALIZED PREDICTIVE CONTROL OF SWITCHED SYSTEMS[J]. Applied Mathematics and Mechanics (English Edition), 2005, 26(5): 647-.
[4]	修乃华;高自友. CONVERGENCE OF A MODIFIED SLP ALGORITHM FOR THE EXTENDED LINEAR COMPLEMENTARITY PROBLEM[J]. Applied Mathematics and Mechanics (English Edition), 2001, 22(5): 602-608.