Boundedness and simple connectivity of the basins of attraction for some numerical methods

Jordi Canela, Antonio Garijo, Xavier Jarque · 2025

Read Boundedness and simple connectivity of the basins of attraction for some numerical methods by Jordi Canela, Antonio Garijo, Xavier Jarque (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22704.txt.

Introduction

Jordi Canela, Antonio Garijo, and Xavier Jarque wrote a 2025 math paper on methods that find the roots of equations. Such methods start from a guess and step toward an answer. For each root, the set of starts that lead to it is called its basin, and the shape of that set matters for trust in the method.

The authors study two classic methods on a matched family of equations. They ask when the basin for a root stays bounded and when it forms one simple region. They show cases where one method gives a bounded basin. The results help explain when these methods behave in a safe, clear way.

Catalog record

CREATORJordi Canela, Antonio Garijo, Xavier Jarque
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22704

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Boundedness and simple connectivity of the basins of attraction for some numerical methods Thanks: The first and third authors are supported by the project CIGE/2023/102 funded by Generalitat Valenciana and by the project PID2023-147252NB-I00 financed by MICIU/AEI MCIN/AEI/10.13039/501100011033 and by FEDER, UE. The first author is also supported by the project UJI-B2022-46 funded by Universitat Jaume I. The second author is supported by the project 2021SGR-633 funded by Generalitat de Catalunya. The third author is also supported by the Spanish State Research Agency, through the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M) Jordi Canela, Antonio Garijo, Xavier Jarque Abstract . In this paper we study the dynamics of Halley’s and Traub’s root-finding algorithms applied to a symmetric family of polynomials of degree d + 1 ≥ 3 d+1\geq 3 . We discuss the (un)boundedness and simple connectivity of the immediate basins of attraction of the fixed points associated to the roots of the polynomials. In particular, we show the existence of polynomials for which the immediate basin of attraction of a root is bounded under Halley’s method. Keywords: Holomorphic dynamics, Julia and Fatou sets, basins of attraction, root-finding algorithms, simple connectivity, unboundedness. 1. Introduction The study of discrete dynamical systems generated by the iterates of root-finding algorithms has been a cornerstone for understanding these algorithms not only as useful local tools for finding the desired solutions of non-linear equations, but also as a means to determine good initial conditions for efficiently finding all solutions. It was Cayley [ Cay79 ] who first considered Newton’s method applied to low-degree polynomials in one complex variable as a global dynamical system on the Riemann sphere. His idea opened an immense field of mathematical research that we now call holomorphic dynamics. Roughly speaking, the idea behind the dynamical system approach to find the solutions of a given equation is to construct a function (also called method) with two basic properties. On the one hand, the solutions of the non-linear equation are (super)-attracting fixed points of the method, so initial conditions close to the solutions converge to the solutions as fast as possible. On the other hand, it is sought that for most initial conditions the iterations generated by the function converge to those solutions of the equation. These dynamical systems lie at the intersection of theoretical work on dynamical systems and applied mathematics. The rationale supporting this claim is that, by studying the topological and geometrical properties of the (immediate) basins of attraction associated with the fixed points of the dynamical system—a natural source of theoretical inquiry—we deepen our understanding of how to design better methods and how to identify good sets of initial conditions to explicitly find (or approximate) the desired solutions of non-linear equations. Nonetheless, the general problem of solving non-linear equations requires some concreteness: regularity of the equation, finiteness or infiniteness of solutions, dimension and topology of the phase space, etc. For each case, the methodology and output(s) might differ substantially. Accordingly, we introduce next some notation and describe the framework in which we will develop our study. This introduction is expanded in Section 2 , where we present the main concepts and results of complex dynamics used along the paper. For a more detailed introduction to the theory of rational iteration see, for instance, [ CG93 , Bea91 , Mil06 ] . Let p be a polynomial in one complex variable. Then, by applying a root-finding algorithm to p we obtain a (rational) map F_{p}:\hat{\mathbb{C}}\to\hat{\mathbb{C}} , where \hat{\mathbb{C}}:=\mathbb{C}\cup\{\infty\} denotes the Riemann sphere. Moreover, every root \alpha of p is a (locally) attracting fixed point of F_{p} : F_{p}(\alpha)=\alpha and if an initial condition z_{0} is close enough to \alpha then the sequence of iterates \{F_{p}^{n}(z_{0})\} converges to \alpha . When we study the dynamical system induced by the iterates of F_{p} we aim to understand the asymptotic behaviour of the sequences \{z_{n}=F_{p}^{n}(z_{0})\} for any seed z_{0}\in\mathbb{C} . As we already mentioned, if p(\alpha)=0 then F_{p}(\alpha)=\alpha and, since \alpha is locally attracting, we have \displaystyle\lim_{n\to\infty}z_{n}=\alpha if z_{0}\approx\alpha . This fact allows to introduce the notion of basin of attraction for any root \alpha of p as A_{F_{p}}(\alpha)=\{z\in\mathbb{C}\ |\ F_{p}^{n}(z)\to\alpha\text{ as }n\to\infty\}. The immediate basin of attraction of \alpha , denoted by A^{\star}_{F_{p}}(\alpha) , is the connected component of A_{F_{p}}(\alpha) that contains \alpha . Notice that A_{F_{p}}(\alpha) and A^{\star}_{F_{p}}(\alpha) are open sets. The connected components of A_{F_{p}}(\alpha) are part of the well-known Fatou set of F_{p} while their boundary, denoted by \partial A_{F_{p}}(\alpha) , belongs to the Julia set (see details in Section 2 ). The most well-known and studied root-finding algorithm is induced by the map (1) F_{p}(z):=N_{p}(z)=z-\frac{p(z)}{p^{\prime}(z)} known as the Newton’s map . It is well known that N_{p}(\alpha)=\alpha , \ \alpha\in\mathbb{C}, if and only if p(\alpha)=0 . Using appropriate coordinates, we also have N_{p}(\infty)=\infty . Moreover, if \alpha is a simple root of p , then it is a super-attracting fixed point of N_{p} , i.e. N^{\prime}_{p}(\alpha)=0 (multiple roots of p are attracting but not super-attracting, 0<|N^{\prime}_{p}(\alpha)|<1 ). On the other hand, z=\infty is a repelling fixed point, i.e. |N^{\prime}_{p}(\infty)|>1 . In [ HSS01 ] the authors show how to use a deep understanding on the topology and geometry of A_{N_{p}}(\alpha) in order to generate a universal set \mathcal{S}_{d} of initial conditions (only depending on the degree d of the polynomial p ) such that iterating those points one can find all roots of any degree d polynomial. Their result is based on the fact that A^{\star}_{N_{p}}(\alpha) are unbounded and simply connected and a key part of the argument is based on the fact that N_{p} has no other finite fixed points than the roots of p . See also [ Shi09 ] . Despite Newton’s method plays a central role among all root-finding algorithms it has some limitations. For instance its local order of convergence is two. Over the years there has appeared alternatives root-finding algorithms with higher convergence rate so that, locally, they approach faster the roots of p . Among the cubic root-finding algorithms (local order of convergence three) the most well-known are Halley’s and Traub’s methods: H_{p} and T_{p} , respectively. Halley’s method belongs to the (discrete) family of König’s root-finding methods (see [ BH03 ] ) with local degree of convergence n to simple roots of a polynomial. For n=2 König’s method coincides with Newton’s method while Halley’s method corresponds to n=3 . Traub’s method is a modification of Newton’s method where p^{\prime}(z) is reused every other iterate (see [ Tra64 ] ). Halley’s method H_{p} and Traub’s method T_{p} are obtained as follows: H_{p}(z):=z-\frac{p(z)p^{\prime}(z)}{\left(p^{\prime}(z)\right)^{2}-\frac{1}{2}p(z)p^{\prime\prime}(z)}\quad\quad\mbox{and}\quad\quad T_{p}(z):=N_{p}(z)-\frac{p(N_{p}(z))}{p^{\prime}(z)}. As mentioned earlier, both maps define cubic root-finding algorithms that offer better local convergence to simple roots than Newton’s method. However, this local improvement comes at a cost when we consider the associated global dynamics on \hat{\mathbb{C}} . We previously argued that a key property of Newton’s method is that its finite fixed points coincide with the roots of the polynomial p . This property, which is key for the understanding of the dynamics of N_{p} , no longer holds neither for Halley’s nor for Traub’s method. The other key property used in [ HSS01 ] to obtain the

Read the complete text