×

Discrete versus continuous Newton’s method: A case study. (English) Zbl 0669.65037

Author’s summary: We consider the damped Newton’s method \(N_ h(z)=z- hp(z)/p'(z),\) \(0<h<1\) for polynomials p(z) with complex coefficients. For the usual Newton’s method \((h=1)\) and polynomials p(z), it is known that the method may fail to converge to a root of p and rather leads to an attractive periodic cycle. \(N_ h(z)\) may be interpreted as an Euler step for the differential equation \(\dot z=-p(z)/p'(z)\) with step size h. In contrast to the possible failure of Newton’s method, we have that for almost all initial conditions to the differential equation that the solutions converge to a root of p. We show that this property generally carries over to Newton’s method \(N_ h(z)\) only for certain nondegenerate polynomials and for sufficiently small step sizes \(h>0\). Further we discuss the damped Newton’s method applied to the family of polynomials of degree 3.
Reviewer: E.Allgower

MSC:

65H05 Numerical computation of solutions to single equations
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barna B.: Ueber die Divergenzpunkte des Newton’schen Verfahrens zur Bestimmung von Wurzeln algebraischer Gleichungen, II,Publ. Math. Debrecen 4 (1956) 384-397. · Zbl 0073.10603
[2] Blanchard P.: Complex analytic dynamics on the Riemann sphere,Bull. A.M.S. 11, (1984), 35-141. · Zbl 0558.58017 · doi:10.1090/S0273-0979-1984-15240-6
[3] Braess D.: Ueber die Einzugsgebiete der Nullstellen von Polynomen beim Newton-Verfahren,Numer. Math. 29 (1977), 123-132. · Zbl 0363.65033 · doi:10.1007/BF01389318
[4] Brolin H.: Invariant sets under iteration of rational functions,Arkiv foer Matematik 6 (1965), 103-144. · Zbl 0127.03401 · doi:10.1007/BF02591353
[5] Curry J. H., Garnett L., and Sullivan D.: On the iteration of a rational function: computer experiments with Newton’s method?,Commun. Math. Phys. 91 (1983), 267-277. · Zbl 0524.65032 · doi:10.1007/BF01211162
[6] Jongen H. T., Jonker P., and Twilt F.: The continuous, desingularized Newton-method for meromorphic functions,Acta Applic. Math. 13 (1988), 81-121 (this issue). · Zbl 0701.58031 · doi:10.1007/BF00047503
[7] Peitgen, H. O., Pruefer, M., and Schmitt, K.: Newton flows for real systems of equations, preprint (1986).
[8] Peitgen H. O. and Richter P.:The Beauty of Fractals, Springer-Verlag, New York, 1986. · Zbl 0601.58003
[9] Peitgen H. O., Saupe D., and v. Haeseler F.: Cayley’s problem and Julia sets,Math. Intelligencer 6 (1984), 11-20. · Zbl 0549.68101 · doi:10.1007/BF03024150
[10] Smale S.: On the efficiency of algorithms of analysis,Bull. A.M.S. 13 (1985), 87-121. · Zbl 0592.65032 · doi:10.1090/S0273-0979-1985-15391-1
[11] Vrscay W. R.: Julia sets and Mandelbrot-like sets associated with higher order Schroeder rational iteration functions: A computer assisted study,Math. of Computation 46 (1986), 151-169. · Zbl 0597.58013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.