Durand-Kerner算法的全局化<sup>*</sup>

王德人; 赵风光

Durand-Kerner算法的全局化^*

王德人¹,
赵风光²

1.
上海大学数学系, 上海 201800;
2.
复旦大学, 上海 200433

基金项目: * 国家自然科学基金

计量
- 文章访问数: 2031
- HTML全文浏览量: 82
- PDF下载量: 454
- 被引次数: 0
出版历程
- 收稿日期: 1995-10-16
- 修回日期: 1997-06-23
- 刊出日期: 1997-11-15

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

摘要

摘要: 本文利用对称多项式与一元多项式之间的关系,结合连续同伦思想,构造了一条概率为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.
- Durand-Kerner algorithm /
- continuous homotopy /
- path tracing /
- global convergence /
- point estimation

HTML全文

参考文献(19)

[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.