Durand-Kerner算法的全局化*
The Globalization of Durand-Kerner Algorithm
-
摘要: 本文利用对称多项式与一元多项式之间的关系,结合连续同伦思想,构造了一条概率为1的正则同论曲线.然后,对这条同论路径,进行离散化跟踪,导出了一类带有步长参数的Durand-Kerner算法,我们证明了这类算法的整体收敛性,从而在理论上解决了人们关于Durand-Kerner算法具有整体性的推测.本文还深入讨论了步长参数的选择问题.最后,我们以足够的数值例子,检验了理论的正确性.
-
关键词:
- Durand-Kerner算法 /
- 连续同伦 /
- 路径跟踪 /
- 整体收敛性 /
- 点估计
Abstract: Making use of the theory of continuous ho motopy and the relation between symmetric polynomial and polynomial in one variable the authors devoted this article to constructing a regularly homotopic curve with probability one, Discrete tracing along this homotopic curve leads to a class of Durand-Kerner algorithm with step parameters.The convergence of this class of algorithms is given, whick solves the conjecture about the global property of Durand-Kerner algorithm,The problem for steplength selection is thoroughly discussed,Finally,sufficient numerical examples are used to verify our theory.-
Key words:
- Durand-Kerner algorithm /
- continuous homotopy /
- path tracing /
- global convergence /
- point estimation
-
[1] 赵风光、王德人,Smale估计理论与Durand-Kerner算法的收敛性,计算数学,2(1993),196-206 [2] 关士明,关于同时求解多项式所有根为Durand-Kerner算法的收敛性,科学通报,9(1982),515-517. [3] G.Alefeld and J.Herzberger,On the convergence speed of some algorithms for the simultaneous approgimation of polynomial roots.SIAM J,Namer,Artal,11(1974),237-243. [4] C.B,Garcia and W,I.Zangwill,Finding all solutions to polynomial systems and Other systems of equations,Meth 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,Szuer and J.Yorke,Numerical solution of a class of deficient polynomial systems,SIAM J.Numer,Anal,24(1987),435-451. [7] T.Y.Li,T,Szuer and J.Yorke,The Cheater's homotopy:An efficient procedare for solving systems of polyno mialequations,SIAM J.Numer,Anal,26(1989),1241-1251. [8] T,Y,Li,Z,Zeng and L,Cong Solving eigenvalue problems of real nonsysmetric matrices with real homotopies,SIMJ.Numer,Aual,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,Co mp,32(1978),887-899. [10] S,T,Schwartz.Nonlinear Functional Analysis Gordon and Breach,New York(1969). [11] E,Durand,Solutions na merigues des equations Algbriques,Tome I:E'qualions du Type F(x)=0,Raciues dun polgnome,Masson,Paris(1960). [12] Wang Deren and Zhao Fengguang,Complexity analysis of a process for Simultaneously obtaining nll zeros of polyno midis,Compufing,43(1989),187-197. [13] Wang Deren and Wu Yujiang,Some modifications of the parallel Halley iteralion method and their convergence,Compnting,38(1987),75-87. [14] Wang Deren and Zhao Fengguang,The theory of Smale's point estimation and its some annlication.JCAM,60(1993).253-264. [15] 徐森林、王则柯,《代数方程组和计算复杂性理论》.科学出版社(1989) [16] I.O.Kerner,Ein gesamtschritlverfahren zur berechnung der-nullotellen von polynomen.Numer Math,8(1966),290-294. [17] 莫宗坚等,《代数学》(上),北京大学出版社(1987). [18] E,L,Allgower and K,Georg,Numerical Continuation Methods,an Introduction,Springer-Verlag,New York(1990). [19] S,Smale,Newton's method estimates from data at one point.in The Morging of Discipdirres:New Dtrections in Pure,Applied and Computational Mathematics(R,Ewing,K-Gross,and G.Marfin Editors),Spring-Verlag,New York(1986).185-196.
点击查看大图
计量
- 文章访问数: 1863
- HTML全文浏览量: 60
- PDF下载量: 453
- 被引次数: 0