Simultaneous point estimates for Newton's method

MaRDI QIDQ1864771zbMATH OpenFDO

Authors Yanyan Li

Publication date 19 September 2003

Published in BIT (Search for Journal in Brave)

zbMATH Keywords

comparison of methodshomotopy methodsNewton iterationNewton's methodpolynomial rootspractical conditions for convergencesimultaneous methods

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05)

Review text

The primary aim of this paper is the establishment of a practical condition guaranteeing the convergence of the one-dimensional Newton iteration from \(n\) pairwise distinct approximations to \(n\) pairwise distinct zeros of a polynomial. The new condition is practical in that the error estimate used involves only function evaluations already computed in the course of computing the Newton iteration, as opposed to, for example, the error estimate found in \textit{X. Wang} and \textit{D. Han}'s work [Sci. China, Ser. A 33, 135-144 (1990; Zbl 0699.65046)]. Convergence is guaranteed to be simultaneous and quadratic, and is \(O(n)\) faster than the method proven in the author's thesis. The error estimate may be used for polynomial root approximation based on homotopy methods [see, e.g. \textit{M. Shub} and \textit{S. Smale}, J. Am. Math. Soc 6, 459-501 (1993; Zbl 0821.65035)]. Additionally, combining the techniques used by \textit{P. Tilli} [Computing, 59, 307-324 (1997; Zbl 0891.65051)] with the new estimate leads to a practical homotopy method using Newton iterations, rather than Durand-Kerner iterations.

Recommendations

• The simultaneous approximation of polynomial roots
• Point estimation of simultaneous methods for solving polynomial equations: A survey. II.
• Convergence conditions of some methods for the simultaneous computation of polynomial zero
• Point estimation and some applications to iterative methods
• Point estimation of root finding methods

Cited in

(5)

• On the convergence of Schröder's method for the simultaneous computation of polynomial zeros of unknown multiplicity
• Unified convergence analysis for Picard iteration in n-dimensional vector spaces
• Convergence of Newton, Halley and Chebyshev iterative methods as methods for simultaneous determination of multiple polynomial zeros
• Geometry of polynomials and root-finding via path-lifting
• Globally convergent, iterative path-following for algebraic equations

This page was built for publication: Simultaneous point estimates for Newton's method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1864771)