The Globalization of Durand-Kerner Algorithm

Wang Deren; Zhao Fengguang

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 1997 > 18(11): 975-986

Wang Deren, Zhao Fengguang. The Globalization of Durand-Kerner Algorithm[J]. Applied Mathematics and Mechanics, 1997, 18(11): 975-986.

Citation:

Wang Deren, Zhao Fengguang. The Globalization of Durand-Kerner Algorithm[J]. Applied Mathematics and Mechanics, 1997, 18(11): 975-986.

Citation:

Wang Deren, Zhao Fengguang. The Globalization of Durand-Kerner Algorithm[J]. Applied Mathematics and Mechanics, 1997, 18(11): 975-986.

PDF( 770 KB)

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 Date: 1995-10-16
Rev Recd Date: 1997-06-23
Publish Date: 1997-11-15

Abstract

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

FullText(HTML)

References(19)

References

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