PaperlayerView exact revision on arXiv

Source-linked AI summary

Simultaneous Global Convergence Failure of Newton's and Halley's Methods in Degree Four

Alessio Basti, Tommaso Cremaschi

arXiv:2610.03246v1math.NAcs.NA

TL;DR

The degree-four gap asks whether Newton’s and Halley’s methods can both fail on the same quartic. The paper constructs and analytically verifies such an example, with distinct attracting cycles for the two methods. It also shows that a common extraneous attracting two-cycle is impossible for a quartic, while the corresponding cubic question remains open.

  • Problem

    Earlier work gave separate cubic failures and simultaneous failures in degrees d ≥ 5, leaving open whether Newton’s and Halley’s methods can both fail on the same quartic.

    Source: §1 · p. 1

  • Method

    The authors search a one-parameter quartic family prescribed with a Newton two-cycle, then prove attraction analytically using a two-interval contraction argument for Halley’s map.

    Source: §1 · p. 2

  • Results

    The quartic has distinct roots, a superattracting Newton two-cycle, and a distinct extraneous attracting Halley two-cycle with |µH| < 3/10; neither method has almost-everywhere root convergence.

    Source: §1 · p. 2

  • Takeaways & Limitations

    A quartic cannot have a common extraneous two-cycle attracting for both Newton’s and Halley’s methods.

    Source: §5 · p. 8

    Whether at least one method is generally convergent for every cubic remains unresolved; proving the cited conjecture would establish degree four as the least degree permitting simultaneous failure.

    Source: §5 · p. 9

Abstract

from arXiv · show

We construct an explicit quartic polynomial for which Newton's and Halley's root-finding methods both fail to converge to a root on nonempty open sets of initial values. The example can be found through a reproducible computational search within a one-parameter family of quartics designed to exhibit a prescribed Newton two-cycle. We then prove analytically that Newton's method has a superattracting two-cycle and that Halley's method has a distinct attracting extraneous two-cycle, using a two-interval contraction argument. This fills a degree-four gap in the simultaneous Newton--Halley failure problem. The computational approach also identifies another quartic with numerical evidence of simultaneous failure of Newton's, Halley's, and Schr\"oder's methods.

1. Introduction and main result

Degree four asks whether Newton’s and Halley’s methods can both fail to converge to roots for the same quartic, despite their strong local convergence near simple roots. The paper answers yes with an explicit example and distinct attracting cycles for the two methods.

1. Introduction and main result

  • The result answers the degree-four question left open by separate cubic failures and simultaneous failures constructed for every degree d ≥ 5.Collins and Hunter explicitly noted the remaining gap in degrees three and four.Source: §1 · p. 1
  • The quartic has distinct roots, a superattracting Newton cycle 0 ↔ 1, and a distinct extraneous attracting Halley cycle with |µH| < 3/10, so neither method has almost-everywhere root convergence.An extraneous attracting cycle has an open basin and thus captures a set of initial values of positive planar measure.Source: §1 · pp. 1–2
  • A deterministic search over rational parameters in a one-parameter quartic family prescribed with the Newton cycle finds a = −35/24 and suggests Halley trapping intervals.The family is designed to have the Newton two-cycle 0 ↔ 1.Source: §1 · p. 2
  • The proof establishes Newton’s exact superattracting cycle and proves Halley attraction by mapping two disjoint real intervals into one another and contracting the second iterate.This verifies the Halley cycle analytically rather than relying only on the numerical search.Source: §1 · p. 2
  • Unlike the higher-degree construction of Collins and Hunter, the two methods fail on this quartic through distinct attracting cycles; the result is a specific obstruction for the Newton–Halley pair alongside McMullen’s broader degree-four barrier [12].The paper also frames the common-cycle question separately: its quartic result does not use a shared cycle.Source: §1 · p. 2

2. Numerical search for the candidate

The section constructs a one-parameter quartic family with a prescribed Newton two-cycle, then searches that family numerically for an attracting Halley two-cycle. A critical point provides a consistent starting value, and the search tests candidate cycles before proposing intervals for verification.

2. Numerical search for the candidate

  • Imposing the Newton two-cycle 0 ↔1 yields a one-parameter family of monic quartics.The family is p_a(z) = z^4 + az^3 − (3 + 2a)z + (3 + 2a).Source: §2 · pp. 2–3
  • The function B_a has exactly one positive zero c_a in (0, 1), approximated by bisection on [0, 1] and used as a consistent starting point for every parameter.The cited text cautions that this particular orbit does not necessarily detect every attracting cycle.Source: §2 · p. 3
  • Each rational parameter is tested after 200 iterates using positivity, separation, closure residual, and multiplier-modulus conditions to screen for an attracting two-cycle.The separation condition distinguishes a two-cycle from an approximate fixed point; the closure residual tests near-return after two steps.Source: §2 · pp. 3–4
  • The first accepted parameter was the 89th tested, and the resulting numerical orbit suggested rational intervals for the later contraction proof.The parameter search follows the critical orbit rather than solving the two-cycle equation directly.Source: §2 · pp. 3–4

3. Proof of Theorem 1.1

The proof establishes an extraneous attracting Halley two-cycle by trapping points in two disjoint intervals and proving contraction of the return map. Together with the previously established superattracting Newton cycle, this gives a quartic with distinct roots for which neither method converges to a root for almost every initial value.

3. Proof of Theorem 1.1

  • Rational center estimates and derivative bounds verify the interval inclusions and contraction conditions for the proposed intervals.The center-image errors are bounded by 1/40000 and 1/5000, respectively.Source: §3 · pp. 5–6
  • Two disjoint closed intervals are mapped into one another, and a contractive return map yields a unique alternating two-cycle with multiplier modulus below 3/10.The interval criterion also establishes uniqueness of the cycle within the intervals.Source: §3 · pp. 4, 6
  • The reflected two-cycle is extraneous because F is positive on both intervals, while denominator bounds ensure the Halley map is holomorphic near the cycle.Holomorphicity makes the real attracting cycle an attracting complex dynamical cycle with an open basin.Source: §3 · pp. 4, 6
  • Newton’s and Halley’s methods both have extraneous attracting two-cycles for a quartic with four distinct roots, so neither has almost-everywhere root convergence.The Halley cycle has a nonempty open basin; the Newton cycle is superattracting.Source: §3 · pp. 5–6

4. Numerical simulations

Matched basin portraits show root-attracted and cycle-attracted regions for both methods, while representative real orbits approach nonroot cycles with nonvanishing polynomial residuals. The simulations illustrate the proved dynamics and distinguish local visual patterns from global reliability comparisons.

Simulation setup

  • The portraits sample the same two complex-plane regions on a uniform 1600 × 1200 grid, with 200 iterations and absolute proximity tolerance 10−8.The methods use identical windows, equal-aspect axes, and the same color key; four labels mark roots, vermilion marks cycle proximity, and light gray marks unclassified orbits.Source: §4 · p. 6

Numerical basin portraits

  • The common zoom contains cycle-attracted regions for both methods but no polynomial root, while the overview assigns most sampled initial values to roots.The larger Halley patch in this selected window is not a comparison of global reliability.Source: §4 · p. 6, Figure 2 · p. 7, Figure 1 · p. 7

Representative real orbits

  • The two-step difference decreases rapidly in both representative real orbits while the polynomial residual stays away from zero.For Newton, the observed even iterates approach 0, where P(0) = 2; Halley’s corresponding residual is numerically close to 2.2337.Source: §4 · p. 7, Figure 3 · p. 8

5. Discussion

The explicit quartic fills the degree-four gap for simultaneous Newton–Halley failure, with distinct attracting cycles for the two methods. The discussion proves that such cycles cannot be a common attracting two-cycle, notes a shared open basin, and reports numerical evidence for a three-method example.

Degree-four obstruction

  • The quartic gives Newton and Halley distinct extraneous attracting two-cycles, filling the degree-four gap in simultaneous failure for the pair.Unlike the construction of Collins and Hunter for degrees d ≥5, the cycles here are distinct.Source: §5 · p. 8

Common-cycle question

  • A quartic cannot have a common extraneous two-cycle that is attracting for both Newton’s and Halley’s methods.Any such common cycle has Halley multiplier 36 and is therefore repelling for Halley.Source: §5 · p. 8

Basin intersection

  • Starting from z0 = −1/2, both methods are attracted to their respective extraneous cycles, and their open basins therefore intersect in an open neighborhood.The cycles are distinct, but their failure basins need not be disjoint.Source: §5 · p. 8

Extension to Schröder’s method

  • The search can screen additional root-finding methods for extraneous attracting cycles, allowing their periods to differ.For the quartic with a = −576/395, computations indicate Newton, Halley, and Schröder cycles of periods 2, 2, and 3, respectively; estimated multipliers are µH ≈0.091 and µS ≈−0.005.Source: §5 · pp. 8–9

Certification caveat

  • The numerically located cycles for Q may be certified by the interval argument, but the additional bounds and certificates are not included.Source: §5 · p. 9

Open question

  • The degree-three question remains whether every cubic has at least one of Newton’s and Halley’s methods generally convergent, as conjectured by Collins and Hunter.A proof together with Theorem 1.1 would establish degree four as the least degree for simultaneous failure of almost-everywhere root convergence for the pair.Source: §5 · p. 9

Appendix A. Auxiliary proofs

The appendix proves attraction of Halley’s two-cycle through a two-interval contraction and rules out a common attracting Newton–Halley two-cycle for quartics. Its arguments use interval bounds and an affine normalization of the proposed common cycle.

Halley interval argument

  • A contractive return map on one of two disjoint intervals yields a unique fixed point of the second iterate and hence an attracting Halley two-cycle.The intervals are mapped into one another, and their disjointness makes the resulting points a two-cycle.Source: Appendix A · p. 9

Interval bounds

  • Monotonicity and endpoint evaluations establish the polynomial bounds; the resulting bounds ensure D has no zeros on either interval, so h has no poles there.D decreases on I and increases on J.Source: Appendix A · p. 9

Common-cycle contradiction

  • For a proposed common extraneous cycle, an affine change of variable normalizes its points to 0 and 1 while preserving the cycle multiplier; the appendix concludes the cycle is repelling for Halley.The proof uses that the points are extraneous and have finite Newton images.Source: Appendix A · pp. 10–11
Loading 2610.03246v1…