# The Polynomial Pivots as Initial Values for a New Root-Finding Iterative Method

Authors: Mario Lázaro; Pedro Martín; Antonio Agüero; Ignacio Ferrer
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

A new iterative method for polynomial root-finding based on the development of two novel recursive functions is proposed. In addition, the concept ofpolynomial pivots associated with these functions is introduced. The pivots present the property of lying close to some of the roots under certain conditions; this closeness leads us to propose them as efficient starting points for the proposed iterative sequences. Conditions for local convergence are studied demonstrating that the new recursive sequences converge with linear velocity. Furthermore, an a priori checkable global convergence test inside pivots-centered balls is proposed. In order to accelerate the convergence from linear to quadratic velocity, new recursive functions together with their associated sequences are constructed. Both the recursive functions (linear) and the corrected (quadratic convergence) are validated with two nontrivial numerical examples. In them, the efficiency of the pivots as starting points, the quadratic convergence of the proposed functions, and the validity of the theoretical results are visualized.


---

## Body

## 1. Introduction

Perhaps the oldest problem in numerical analysis deals with the search of polynomials’ roots. Since Abel and Galois proved the nonexistence of radical-based solutions for general polynomials or order higher than four, the only method to obtain the complete set of roots is numerical calculus and particularly the iterative methods. For any iterative method, a recursive function together with an initial guess is required. Most methods are focused on the local efficiency of the recursive schemes, convergence conditions, and velocity at the roots, whereas the study on where (and why) to start the iterative sequences is less considered. Hence, the challenge is to find reasonably efficient initial guesses, that is, starting points for the iterative sequences lying close to some of the roots.The problem of searching zeros of functions has been extensively discussed in several books on numerical analysis; see, for instance, [1–5]. In particular, a survey of methods specially developed for polynomials has been recently published by McNamee [6]. The latter has compiled an extensive bibliography [7–10] in which probably most of the published methods for root-finding are included. In addition, McNamee [6] has proposed an indicator to measure the efficiency of an iterative method and has applied it to the most common approaches. Other relevant reviews on algorithms to search zeros have been presented by Pan [11–14] and by Pan and Zheng [14].As mentioned, the location of initial approximations is of special relevance in iterative schemes so that the success or failure may largely depend on it. In the book of Kyurkchiev [15], a selection of initial approximations specially developed for simultaneous methods is listed. The roots’ bounds obtained from the polynomial coefficients have traditionally been a rough tool in some cases but useful tool for zeros’ locating. An interesting survey of these bounds is listed in [6]. The quotient-difference method [16] includes in addition an initial approximation, although for its construction all polynomial coefficients must be nonzero. Hubbard et al. [17] with the study of the convergence spectrum have proposed a finite and relatively small set of starting points assuring that, at least from one of them, the convergence of Newton’s method is guaranteed. Bini et al. [18] developed improved initial conditions for the known QR method. Petković et al. [19–21] have proposed parametric families of simultaneous root-finding methods based on the Hansen-Patrick formula [22]. Monsi et al. [23, 24] have introduced the named point symmetric single step procedure and its variants for finding zeros simultaneously. In addition, the necessary initial conditions to guarantee convergence using Smale’s point estimation theory [25] have been reviewed in [26–28]. Zhu [29–31] has analyzed the initial conditions of convergence for Durand-Kerner’s method and for the Newton-like simultaneous methods based on the parallel circular iteration. Lázaro et al. [32] proposed efficient recursive functions to reach eigenvalues in vibrating systems independently on the chosen starting point, showing global convergence in the whole complex plane. Kornerup and Muller [33] and Kjurkchiev [34] have also discussed the influence of starting points for certain Newton-Raphson iterations and for Euler-Chebyshev’s method, respectively. Saidanlu et al. [35] studied the conditions for determining initial approximations of exact roots for certain iterative matrix zerofinding method. The recently published book of Petković et al. [36] explores the development of powerful multipoint algorithms to solve nonlinear equations involved in research problems.In this paper, we consider then-order polynomial (1)p(x)=a0+a1x+a2x2+⋯+an-2xn-2+an-1xn-1+xn,where aj∈C for 0≤j≤n-1 and a0≠0. In the present paper, a pair of novel recursive functions for polynomial root-finding is proposed. In addition, associated with each one of these functions a characteristic complex number can be calculated from the polynomial coefficients an-1 and an-2. Both complex numbers, namedpivots, lay close to some root of the polynomial when they become large (in absolute value) with respect to the rest of polynomial coefficients. In fact, it is demonstrated that the pivots are attractive fixed points at the complex infinite. Conditions for local and global convergence of the new iterative scheme are provided; the convergence is demonstrated within a family of closed balls centered at the pivots under certaina priori conditions that can be verified. In fact, based on the theorem of global convergence, a test to identify the polynomial class for which the convergence is ensured is proposed. It is also proved that the velocity of convergence is linear; in order to accelerate the iterative process up to a quadratic order, new corrected recursive functions are proposed based on Steffensen acceleration approach. The corrected recursive functions present the same properties as those of the originals with respect to the pivots, but with quadratic convergence.In order to validate the theoretical results, two numerical examples are analyzed. In the first two, the results of the proposed recursive functions are studied for single and multiple roots, respectively. In the third example, the influence of the pivots is discussed. In addition, in this last example the test of global convergence is applied, directly relating the proposed pivots to the success of the iteration scheme.


## 2. The New Recursive Functions

### 2.1. Definitions and Previous Results

Based on the polynomial of (1), the following definition introduces two complex-valued functions of complex variable of special interest in this paper.Definition 1 (recursive functions).
Associated with the polynomialp(x) of (1) one introduces two functions X,Y:C→C defined as (2)X(z)=-J(z)+J2(z)-an-2(3)Yz=-Jz-J2z-an-2,where(4)Jz=12an-1+an-3z2+an-4z3+⋯+a0zn-1that will be named recursive functions (RF).As mentioned above,• represents the square root of a complex number whose branch line is R-∪{0}. Since the origin is the only branch point of the square root function so defined, the region of analyticity can consequently be expressed as (5)A=C∖U,where(6)U=0∪z∈C:J2z-an-2=0.The following proposition relates the polynomial roots with the fixed points of the defined functions.Proposition 2.
Ifa0≠0, then a complex number λ∈C is root of the polynomial p(x) if and only if it is a fixed point of either the function X(z) or Y(z).Proof.
Starting from the general form of the polynomial given by (1), we obtain an equivalent expression (7)px=a0+a1x+a2x2+⋯+an-2xn-2+an-1xn-1+xn=xn-2a0xn-2+a1xn-1+a2xn+⋯+an-3x+an-2hhhhha0xn-2+an-1x+x2=xn-2x2+2xJx+an-2,where J(x) is the function defined in (4). Now, the right-hand term of (7) can be handled to obtain the product of three terms in which we find the RF introduced in (2), (3): (8)px≡xn-2x-Xxx-Yx.Since a0≠0, the value x=0 cannot be a root. Hence, a complex number λ satisfies p(λ)=0 if and only if it is a fixed point of some of the RF; that is, either λ=X(λ) or λ=Y(λ).The following proposition presents a characterization of the multiple roots ofp(x)=0 through the derivatives of the functions X(z) and Y(z): (9)Xjz=djXdzj,Yjz=djYdzj,j≥1,∀z∈A.Proposition 3.
Letλ∈A be a root of p(x)=0. (i)
Ifλ=X(λ), then the root λ has multiplicity m≥2 if and only if  X′(λ)=1 and X(j)(λ)=0 for 2≤j≤m-1.(ii)
Ifλ=Y(λ), then the root λ has multiplicity m≥2 if and only if  Y′(λ)=1 and  Y(j)(λ)=0 for 2≤j≤m-1.Proof.
(i) Ifp(λ)=0 with multiplicity m≥2, it is verified that p(j)(λ)=0, for j=1,…,m-1. The function p(j)(z) can directly be calculated taking derivatives in (8). The first derivative evaluated at z=λ is (10)p′λ=n-2λn-3λ-Xλλ-Y(λ)+λn-21-X′λλ-Yλ+λn-2λ-X(λ)1-Y′(λ)=λn-21-X′λλ-Yλ=0,where the equality X(λ)=λ has been used. If Y(λ)=λ=X(λ), this equality would imply J2(λ)=an-2, where λ∉A, which is against the hypothesis; therefore, X′(λ)=1 necessarily holds. Evaluating now the jth derivative for 2≤k≤m-1 at z=λ results in(11)p(j)(λ)=-λn-2λ-Y(λ)X(j)(λ)=0and hence X(j)(λ)=0 for j=2,…,m-1. Reciprocally, from (10) it is immediately verified that p′(λ)=0 due to X′(λ)=1. From (11), if X(j)(λ)=0, for 2≤j≤m-1, p(j)(λ)=0 holds by induction.
(ii) Ifλ=Y(λ) then the polynomial derivatives evaluated at z=λ lead to (12)p′(λ)=λn-2λ-X(λ)1-Y′(λ)p(j)(λ)=-λn-2λ-X(λ)Y(j)(λ),j=2,…,m-1and hence the relationship between root multiplicity and the derivatives Y(j)(λ) is obtained following the same arguments as (i).Since each root of the polynomial is a fixed point of one of the functionsX(z) or Y(z), the question arises whether, starting at certain point and iterating these functions, the convergence to any of the root holds. The first step in our research is to introduce therecursive sequences associated with the equally named functions together with the concept ofpoint of attraction.Definition 4 (recursive sequence).
Letx0,y0∈C. One defines recursive sequences, {xk}k=1∞ and {yk}k=1∞, associated with the functions X(z) and Y(z) as the set of complex numbers calculated as (13)xk=X(xk-1),yk=Y(yk-1),k≥1.Definition 5 (point of attraction).
A complex numberλ is said to be a point of attraction of X(x) if there exists an initial point x0∈C, such that (14)λ=limk→∞xk.
Similarly, apoint of attraction of Y(x) is defined as the limit of the sequence {yn}. Obviously, any point of attraction is a root of p(x), but the reciprocal affirmation is not true.


### 2.2. Local Convergence

This subsection deals with the necessary conditions for the local convergence of the recursive sequences. The main result is presented in Theorem8. Previously, we introduce the lemma of McLeod in order to prove the Lipschitz continuity of complex-valued functions of complex variable. This result will be used repeatedly along the current work.Lemma 6 (McLeod [37]).
Letg(z):F→C be a complex function, analytic in a convex domain F⊂C. If [z1,z2]={ξz1+(1-ξ)z2:0≤ξ≤1}⊂F is the (closed) segment between two any points z1,z2∈F, then there exist two complex numbers w1,w2∈]z1,z2[ and certain ξ0,  0≤ξ0≤1 such that (15)g(z2)-g(z1)=(z2-z1)ξ0dg(w1)dz+(1-ξ0)dg(w2)dz.Corollary 7.
Ifc=max⁡z∈Fg′(z), then g(z2)-g(z1)≤cz2-z1.Proof.
Consider(16)g(z2)-g(z1)=ξ0g′(w1)+1-ξ0g′(w2)z2-z1≤ξ0g′(w1)+(1-ξ0)g′(w2)z2-z1≤ξ0c+(1-ξ0)cz2-z1=cz2-z1.Theorem 8.
Let one assume thatλ∈A is a single root of the equation p(x)=0 and that (17)J′(λ)<1+J(λ)λ.If X(λ)=λ, then there exist two positive real numbers δ>0 and 0<ν<1, such that (i)
the ballB(λ,δ)={z∈C:z-λ≤δ}⊂A;(ii)
λ is a point of attraction of X(z),  ∀x0∈B(λ,δ);(iii)
xk-λ≤νk/1-νX(x0)-x0, ∀x0∈B(λ,δ).Otherwise, if Y(λ)=λ, then there exist two positive real numbers δ>0 and 0<ν<1, such that (i)
the ballB(λ,δ)={z∈C:z-λ≤δ}⊂A;(ii)
λ is a point of attraction of  Y(z),  ∀y0∈B(λ,δ);(iii)
yk-λ≤νk/1-νY(y0)-y0, ∀y0∈B(λ,δ).Proof.
The proof is developed for the first case; that is,λ=X(λ); for the function Y(z) the procedure would be analogous. The demonstration is based on the application of the well-known Banach contraction principle. For that, it is only necessary to prove the contractivity and the self-mapping of X(x) in a closed ball centered at the root. Let us evaluate X′(z) in z=λ: (18)dX(λ)dz=J′(λ)1-J(λ)J2(λ)-an-2=J′λ-Jλ+J2λ-an-2J2λ-an-2=J′λXλXλ+Jλ=J′λλλ+Jλ=J′(λ)1+J(λ)λ<1.Since λ∈A and A⊂C is an open set, there exists δ1>0 such that the (closed) ball B(λ,δ1)⊂A. In addition, X′(z) is continuous at z=λ; therefore there exist certain real numbers δ2>0 and 0<ν<1 such that X′(z)≤ν<1, ∀z∈B(λ,δ2). If δ=min⁡{δ1,δ2}, it follows from Corollary 7 that X(z) is contractive in the ball B(λ,δ). Moreover, X:B(λ,δ)→B(λ,δ) is a self-mapping as can easily be demonstrated from the contractivity. Indeed, (19)X(z)-λ=X(z)-X(λ)≤νz-λ≤νδ<δ.Therefore, the hypothesis of Banach’s fixed point theorem is verified [38] and the convergence of the succession {xk}k=1∞ to the (unique) fixed point λ in B(λ,δ) is guaranteed. Furthermore, the error rate in each iteration can be bounded by (20)xn-λ≤νn1-νXx0-x0,∀x0∈Bλ,δ.Theorem8 does not cover the case of multiple roots since for all of them X′(λ)=1 holds, although this fact does not imply that these roots cannot be points of attraction. However in such cases the sequences will converge more slowly [2].The necessary condition imposed by (17) in the previous theorem allows predicting certain characteristics of the roots that present local convergence. Assuming that the absolute value of a root is greater than certain 1/ϵ>0, that is, λ≥1/ϵ, and denoting a=max⁡0≤k≤n-3ak, after some operations we obtain (21)J′(λ)≤a22ϵ3+3ϵ4+⋯+n-1ϵn=Oϵ3,1+J(λ)λ≤1+an-12ϵ+a2ϵ3+ϵ4+⋯+ϵn=1+O(ϵ).In view of this reasoning, it seems that roots withϵ≪1, that is, those with large absolute value, will present local convergence for some of the proposed recursive sequences. However, although intuitive, this result is not valid in general since the inequalities given by (21) do not guarantee (17). Let us improve the necessary conditions to impose on the polynomial coefficients to check convergence. For that, we define the concept ofpivots of a polynomial.


### 2.3. Global Convergence

For any iterative numerical scheme, it is always desirable to providea priori information about the convergence. If certain recursive sequence is convergent for any starting point inside certain complex set, it is said that such sequence is globally convergent. This section aimed to study the global convergence of the recursive sequences within sets with closed balls centered at two characteristic points of the polynomials u and v, namedpivots of the polynomial.Definition 9 (pivots).
One defines the pivots of polynomialp(x)=a0+a1x+⋯+an-2xn-2+an-1xn-1+xn to the following complex numbers: (22)u=-an-12+γ,v=-an-12-γ,where (23)γ=an-122-an-2.The pivots of a polynomial have the property of lying close to some root when these pivots are relatively large (in absolute value) with respect to the rest of polynomial coefficients. This may be an important advantage because the pivots can be used as effective initial guesses in a recursive scheme. This behavior is explained in the results of this section. The first result (Proposition10) states that the pivot u is a point of attraction in the (complex) infinite of X(z). The same argument holds for the pivot v and Y(z).Proposition 10.
Letu,v∈A be the pivots of the polynomial p(x); then (i)
limu→∞X(u)/u=1, limu→∞X′(u)=0;(ii)
limv→∞Y(v)/v=1, limv→∞Y′(v)=0.Proof.
(i) From the definition ofJ(z) given in (4), let us calculate the following limits: (24)limu→∞Ju=limu→∞12an-1+an-3u2+an-2u3+⋯+a0un-1=an-12(25)limu→∞J′u=limu→∞-122an-3u3+3an-2u4+⋯+(n-1)a0un=0.Now, from the expressions of X(z) and X′(z) given by (2), (18) and by (22), (24) (26)limu→∞X(u)u=limu→∞-J(u)+J2(u)-an-2u=limu→∞-an-1/2+an-1/22-an-2u=limu→∞uu=1limu→∞dXdz=limu→∞J′(u)X(u)X(u)+J(u)=limu→∞J′uXu/uXu/u+Ju/u=0·11+0=0.The proof for the function Y(z) is analogous.This result justifies the use of the family of closed balls centered atu and v as suitable sets for the global convergence of {xk} and {yk}, respectively. In what follows up to the next section, only the case of the recursive function X(z) will be rigorously analyzed. The proofs of the lemmas and theorems can easily be extrapolated to the case of Y(z).Let us assume thatu∈A and denote 0<r<u to the radius of the closed ball centered at u; that is, B(u,r)={z∈C:z-u≤r}.Lemma 11.
Letρr=u-r>0 be the distance between the origin and the ball B(u,r); that is, ρr=min⁡{z:z∈B(u,r)}. Let one denote a=max⁡0≤k≤n-3ak. If γ≠0, then for any z∈B(u,r)(i)
J(z)-an-1/2≤a/2ρrn-1ρrn-2-1/ρr-1≡ψr;(ii)
J(z)≤an-1/2+ψr;(iii)
J′(z)≤aρrn-1+ρrn-2-nρr-1-1/2ρrnρr-12≡ηr;(iv)
J2(z)-an-1/22≤ψran-1+ψr≡γ2αr;(v)
J2(z)-an-2-1/2≤1/γ1-αr,  αr<1.Proof.
(i) From the definition ofρr, z≥ρr holds for all z∈B(u,r). Consequently (27)J(z)-an-12=12an-3z2+an-4z3+⋯+a0zn-1≤12an-3z2+an-4z3+⋯+a0zn-1≤12az2+az3+⋯+azn-1≤12aρr2+aρr3+⋯+aρrn-1=a2ρr21+1ρr+⋯+1ρrn-3=a2ρrn-1ρrn-2-1ρr-1=ψr,where the expression of the general term of the sum ∑k=2n-1‍ρr-(k-2) has been used.
(ii) Using the previous result(28)J(z)≤Jz-an-12+an-12≤an-12+ψr.
(iii) Following the same reasoning as that of (27) (29)J′(z)=12-2an-3z3-3an-4z4-⋯-(n-1)a0zn≤122an-3z3+3an-4z4+⋯+(n-1)a0zn≤a22z3+3z4+⋯+n-1zn≤aρrn-1+ρrn-2-nρr-1-12ρrnρr-12≡ηr,where now the expression of the sum ∑k=1n-2‍(k+1)ρr-k has been used.
(iv) From the bounds calculated in (i) and (ii)(30)J2(z)-an-122≤J(z)-an-12J(z)+an-12≤ψran-12+ψr+an-12=ψran-1+ψr≡γ2αr.Here the number αr=ψran-1+ψr/γ2 has been introduced in order to simplify the notation in subsequent developments.
(v) Let us define the functionT(z) as that one which verifies the following identity: (31)J2(z)-an-2=γ1+T(z);after some direct operations and using the definition of γ2=an-12/4-an-2, we obtain T(z)=J2(z)-an-12/4/γ2. Consequently, (32)J2(z)-an-2-1/2=1γ11+T(z).Now, using Lemma 11(iv), it is verified that T(z)≤αr, ∀z∈B(u,r). Hence, assuming that αr<1 and expanding in power series (33)11+T(z)=∑k=0∞‍-12kTk(z)≤∑k=0∞‍-12kT(z)k≤∑k=0∞‍-12kαrk=∑k=0∞‍-1k-12kαrk=∑k=0∞‍-12k-αrk=11-αr.The same conclusions of this lemma can easily be extrapolated for pivotv, simply changing u by v in the above expressions. In this case, ρr=v-r>0 is defined as the distance between the origin and the ball B(v,r); that is, ρr=min⁡{z:z∈B(v,r)}.Lemma 12.
Under the same conditions of Lemma11, let us consider the positive real numbers that depend on the radius r of the ball B(u,r) centered at pivot u and depending on ρr=u-r: (34)Kr=ηr1+an-1+2ψr2γ1-αr,βr=ψrr+γr1-1-αr.If αr<1 and B(u,r)⊂A, then(i)
X′(z)≤Kr, ∀z∈B(u,r);(ii)
X(z)-u≤rβr, ∀z∈B(u,r).Proof.
(i) Evaluating the derivative ofX(z) at a point z∈B(u,r) and using the Lemmas 11(ii), (iii), and (v) (35)dXdz=J′(z)1-J(z)J2(z)-an-2≤J′(z)1+J(z)J2(z)-an-2≤ηr1+an-1/2+ψrγ1-αr=Kr.
(ii) From the definition ofT(z) given in (32) and Lemmas 11(i), (iv), and (v), the distance between X(z) and u can be bounded by (36)Xz-u≤Jz-an-12+J2z-an-2-an-122-an-2=Jz-an-12+γ1+Tz-γ=Jz-an-12+γ1+Tz-γ≤ψr+γ1+Tz-1≤ψr+γ∑k=0∞‍12kTkz-1=ψr+γ∑k=1∞‍12kTkz≤ψr+γ∑k=1∞‍12kT(z)k≤ψr+γ∑k=1∞‍12kαrk=ψr+γ∑k=1∞‍-1k+112kαrk=ψr+γ1-1-αr=rβr.With the help of the above lemmas, the main result on global convergence can already be presented.Theorem 13.
Letαr, Kr, and βr be the numbers defined in Lemmas 11 and 12. Also, let us assume that, for the radius r>0, the ball B(u,r)⊂A. If αr<1, Kr<1, and βr≤1, then there exists a unique single root λ∈B(u,r) of the polynomial p(x), which is point of attraction of the function X(z) for any x0∈B(u,r). Moreover, (37)xk-λ≤Krk1-KrX(x0)-x0,∀x0∈B(u,r).Proof.
Let us demonstrate thatX(z):B(u,r)→B(u,r) is a contractive self-mapping. Indeed, the contractivity arises from the inequality X′(z)≤Kr<1 deduced from Lemma 12(ii). Furthermore, if z∈B(u,r) the self-mapping can be demonstrated from Lemma 12(ii) and hypothesis βr≤1(38)X(z)-u≤rβr≤r.Hence, the complex number X(z)∈B(u,r), ∀z∈B(u,r).
Therefore, the Banach contraction principle can be applied ensuring that there exists a unique fixed pointλ∈B(u,r) of the function X(z) so that limn→∞xn=λ, for any x0∈B(u,r). Furthermore (39)xk-λ≤Krk1-KrX(x0)-x0.Lemma12 and Theorem 13 have been presented for describing the conditions under which global convergence towards fixed points of X(z) in balls of the form B(u,r) can be guaranteed. We can also find versions of these results for the function Y(z), for the pivot v and for the family of balls B(v,r). It is clear that, in such case, αr, βr, and Kr have exactly the same mathematical form although the meaning of r is now the radius of a ball centered at v and ρr=v-r is the distance between the origin and B(v,r). In order to be consistent in the presentation of the results we also write the associated lemma and theorem about convergence of sequences {yk} within balls B(v,r).Lemma 14.
Under the same conditions of Lemma11, let one consider the positive real numbers that depend on the radius r of the ball B(v,r) centered at pivot v and depending on ρr=v-r: (40)Kr=ηr1+an-1+2ψr2γ1-αr,βr=ψrr+γr1-1-αr.If αr<1 and B(v,r)⊂A, then(i)
Y′(z)≤Kr, ∀z∈B(v,r);(ii)
Y(z)-v≤rβr, ∀z∈B(v,r).Theorem 15.
Letαr, Kr, and βr be the numbers defined in Lemmas 11 and 14. Also, let one assume that, for the radius r>0, the ball B(v,r)⊂A. If αr<1, Kr<1, and βr≤1, then there exists a unique single root λ∈B(v,r) of the polynomial p(x), which is point of attraction of the function Y(z) for any y0∈B(v,r). Moreover, (41)yk-λ≤Krk1-KrY(y0)-y0,∀y0∈B(v,r).From the definition ofY(z) we have the two inequalities (42)dYdz=J′(z)-1-J(z)J2(z)-an-2≤J′(z)1+J(z)J2(z)-an-2Y(z)-v≤J(z)-an-12+J2(z)-an-2-an-122-an-2.Just comparing these expressions with (35), (36), it is clear that Y′(z) and Y(z)-v bounds have the same mathematical expressions as those of X′(z) and X(z)-u in B(u,r). Consequently, the proof of Lemma 14 and Theorem 15 can be omitted since they can be directly deduced from the proofs of Lemma 12 and Theorem 13.The necessary conditions of this theorem are given in terms of the three numbersαr, βr, and Kr, (30), (34), calledconvergence indexes and introduced in Lemmas 11, 12, and 14. These indexes can be used to construct ana priori test to check global convergence, since for their calculation no previous root-computing is needed. For that, chosen a radius r, the indexes ensure the convergence of the RF provided that αr,Kr<1 and βr≤1. If these inequalities are verified for ball B(u,r) as well as for B(v,r), then we can ensure that the two sequences {xk} and {yk} are convergent and the method reaches two different roots. On the opposite, if there does not exist radius r verifying αr<1, Kr<1, and βr≤1, for some ball B(u,r) or B(v,r), global convergence cannot bea priori ensured. The latter obviously is not synonymous of no convergence, because local convergence could still arise. Let us illustrate the application of this test with an example considering the 16th order polynomial (43)p(x)=x16+5x15+5x14-1.The test is equivalent to find at least a radius r>0 so that αr,Kr<1 and βr≤1 for both the sequences {xk} and {yk}. Thus, the indexes associated with the pivot v (global convergence of {yk}) are represented as function of the radius r in Figure 1. It can be observed that αr,βr,Kr<1 in the range 0.208<r<1.296, consequently ensuring the global convergence for any ball B(v,r) centered at v and radius in the previous range. Furthermore, ana priori estimation of the (linear) velocity of convergence can be calculated for rmin⁡=0.208, resulting in Kmin⁡=0.156. Otherwise, testing balls of the form B(u,r), centered at the other pivot u (global convergence of {xk}), we observe that αr>1 in the whole range 0<r<u. Note that although the recursive sequence {xk} does not pass the test, it locally converges to a root. The polynomial of (55) is an example that presents a good behavior with both recursive sequences, but the sequence {yk} passes the test, whereas the other {xk} does not. In general, the proposed test is somewhat conservative; in fact, several numerical experiences have shown that convergence of recursive sequences can succeed (starting at the pivots) for polynomials that do not pass the test.Figure 1
Test of global convergence for polynomialp(x)=x16+5x15+5x14-1.To conclude this section, we will make some remarks on the convergence to multiple roots. As proved in Proposition3, a root λ=X(λ) with multiplicity m≥2 verifies X′(λ)=1. Therefore, λ∈A cannot be contained in any closed ball B(u,r)⊂A verifying X′(z)≤Kr<1. In this case, the Banach contraction principle does not provide information on the convergence, although if it holds the scheme will present sublinear velocity [2] as shown in the numerical examples.


## 2.1. Definitions and Previous Results

Based on the polynomial of (1), the following definition introduces two complex-valued functions of complex variable of special interest in this paper.Definition 1 (recursive functions).
Associated with the polynomialp(x) of (1) one introduces two functions X,Y:C→C defined as (2)X(z)=-J(z)+J2(z)-an-2(3)Yz=-Jz-J2z-an-2,where(4)Jz=12an-1+an-3z2+an-4z3+⋯+a0zn-1that will be named recursive functions (RF).As mentioned above,• represents the square root of a complex number whose branch line is R-∪{0}. Since the origin is the only branch point of the square root function so defined, the region of analyticity can consequently be expressed as (5)A=C∖U,where(6)U=0∪z∈C:J2z-an-2=0.The following proposition relates the polynomial roots with the fixed points of the defined functions.Proposition 2.
Ifa0≠0, then a complex number λ∈C is root of the polynomial p(x) if and only if it is a fixed point of either the function X(z) or Y(z).Proof.
Starting from the general form of the polynomial given by (1), we obtain an equivalent expression (7)px=a0+a1x+a2x2+⋯+an-2xn-2+an-1xn-1+xn=xn-2a0xn-2+a1xn-1+a2xn+⋯+an-3x+an-2hhhhha0xn-2+an-1x+x2=xn-2x2+2xJx+an-2,where J(x) is the function defined in (4). Now, the right-hand term of (7) can be handled to obtain the product of three terms in which we find the RF introduced in (2), (3): (8)px≡xn-2x-Xxx-Yx.Since a0≠0, the value x=0 cannot be a root. Hence, a complex number λ satisfies p(λ)=0 if and only if it is a fixed point of some of the RF; that is, either λ=X(λ) or λ=Y(λ).The following proposition presents a characterization of the multiple roots ofp(x)=0 through the derivatives of the functions X(z) and Y(z): (9)Xjz=djXdzj,Yjz=djYdzj,j≥1,∀z∈A.Proposition 3.
Letλ∈A be a root of p(x)=0. (i)
Ifλ=X(λ), then the root λ has multiplicity m≥2 if and only if  X′(λ)=1 and X(j)(λ)=0 for 2≤j≤m-1.(ii)
Ifλ=Y(λ), then the root λ has multiplicity m≥2 if and only if  Y′(λ)=1 and  Y(j)(λ)=0 for 2≤j≤m-1.Proof.
(i) Ifp(λ)=0 with multiplicity m≥2, it is verified that p(j)(λ)=0, for j=1,…,m-1. The function p(j)(z) can directly be calculated taking derivatives in (8). The first derivative evaluated at z=λ is (10)p′λ=n-2λn-3λ-Xλλ-Y(λ)+λn-21-X′λλ-Yλ+λn-2λ-X(λ)1-Y′(λ)=λn-21-X′λλ-Yλ=0,where the equality X(λ)=λ has been used. If Y(λ)=λ=X(λ), this equality would imply J2(λ)=an-2, where λ∉A, which is against the hypothesis; therefore, X′(λ)=1 necessarily holds. Evaluating now the jth derivative for 2≤k≤m-1 at z=λ results in(11)p(j)(λ)=-λn-2λ-Y(λ)X(j)(λ)=0and hence X(j)(λ)=0 for j=2,…,m-1. Reciprocally, from (10) it is immediately verified that p′(λ)=0 due to X′(λ)=1. From (11), if X(j)(λ)=0, for 2≤j≤m-1, p(j)(λ)=0 holds by induction.
(ii) Ifλ=Y(λ) then the polynomial derivatives evaluated at z=λ lead to (12)p′(λ)=λn-2λ-X(λ)1-Y′(λ)p(j)(λ)=-λn-2λ-X(λ)Y(j)(λ),j=2,…,m-1and hence the relationship between root multiplicity and the derivatives Y(j)(λ) is obtained following the same arguments as (i).Since each root of the polynomial is a fixed point of one of the functionsX(z) or Y(z), the question arises whether, starting at certain point and iterating these functions, the convergence to any of the root holds. The first step in our research is to introduce therecursive sequences associated with the equally named functions together with the concept ofpoint of attraction.Definition 4 (recursive sequence).
Letx0,y0∈C. One defines recursive sequences, {xk}k=1∞ and {yk}k=1∞, associated with the functions X(z) and Y(z) as the set of complex numbers calculated as (13)xk=X(xk-1),yk=Y(yk-1),k≥1.Definition 5 (point of attraction).
A complex numberλ is said to be a point of attraction of X(x) if there exists an initial point x0∈C, such that (14)λ=limk→∞xk.
Similarly, apoint of attraction of Y(x) is defined as the limit of the sequence {yn}. Obviously, any point of attraction is a root of p(x), but the reciprocal affirmation is not true.


## 2.2. Local Convergence

This subsection deals with the necessary conditions for the local convergence of the recursive sequences. The main result is presented in Theorem8. Previously, we introduce the lemma of McLeod in order to prove the Lipschitz continuity of complex-valued functions of complex variable. This result will be used repeatedly along the current work.Lemma 6 (McLeod [37]).
Letg(z):F→C be a complex function, analytic in a convex domain F⊂C. If [z1,z2]={ξz1+(1-ξ)z2:0≤ξ≤1}⊂F is the (closed) segment between two any points z1,z2∈F, then there exist two complex numbers w1,w2∈]z1,z2[ and certain ξ0,  0≤ξ0≤1 such that (15)g(z2)-g(z1)=(z2-z1)ξ0dg(w1)dz+(1-ξ0)dg(w2)dz.Corollary 7.
Ifc=max⁡z∈Fg′(z), then g(z2)-g(z1)≤cz2-z1.Proof.
Consider(16)g(z2)-g(z1)=ξ0g′(w1)+1-ξ0g′(w2)z2-z1≤ξ0g′(w1)+(1-ξ0)g′(w2)z2-z1≤ξ0c+(1-ξ0)cz2-z1=cz2-z1.Theorem 8.
Let one assume thatλ∈A is a single root of the equation p(x)=0 and that (17)J′(λ)<1+J(λ)λ.If X(λ)=λ, then there exist two positive real numbers δ>0 and 0<ν<1, such that (i)
the ballB(λ,δ)={z∈C:z-λ≤δ}⊂A;(ii)
λ is a point of attraction of X(z),  ∀x0∈B(λ,δ);(iii)
xk-λ≤νk/1-νX(x0)-x0, ∀x0∈B(λ,δ).Otherwise, if Y(λ)=λ, then there exist two positive real numbers δ>0 and 0<ν<1, such that (i)
the ballB(λ,δ)={z∈C:z-λ≤δ}⊂A;(ii)
λ is a point of attraction of  Y(z),  ∀y0∈B(λ,δ);(iii)
yk-λ≤νk/1-νY(y0)-y0, ∀y0∈B(λ,δ).Proof.
The proof is developed for the first case; that is,λ=X(λ); for the function Y(z) the procedure would be analogous. The demonstration is based on the application of the well-known Banach contraction principle. For that, it is only necessary to prove the contractivity and the self-mapping of X(x) in a closed ball centered at the root. Let us evaluate X′(z) in z=λ: (18)dX(λ)dz=J′(λ)1-J(λ)J2(λ)-an-2=J′λ-Jλ+J2λ-an-2J2λ-an-2=J′λXλXλ+Jλ=J′λλλ+Jλ=J′(λ)1+J(λ)λ<1.Since λ∈A and A⊂C is an open set, there exists δ1>0 such that the (closed) ball B(λ,δ1)⊂A. In addition, X′(z) is continuous at z=λ; therefore there exist certain real numbers δ2>0 and 0<ν<1 such that X′(z)≤ν<1, ∀z∈B(λ,δ2). If δ=min⁡{δ1,δ2}, it follows from Corollary 7 that X(z) is contractive in the ball B(λ,δ). Moreover, X:B(λ,δ)→B(λ,δ) is a self-mapping as can easily be demonstrated from the contractivity. Indeed, (19)X(z)-λ=X(z)-X(λ)≤νz-λ≤νδ<δ.Therefore, the hypothesis of Banach’s fixed point theorem is verified [38] and the convergence of the succession {xk}k=1∞ to the (unique) fixed point λ in B(λ,δ) is guaranteed. Furthermore, the error rate in each iteration can be bounded by (20)xn-λ≤νn1-νXx0-x0,∀x0∈Bλ,δ.Theorem8 does not cover the case of multiple roots since for all of them X′(λ)=1 holds, although this fact does not imply that these roots cannot be points of attraction. However in such cases the sequences will converge more slowly [2].The necessary condition imposed by (17) in the previous theorem allows predicting certain characteristics of the roots that present local convergence. Assuming that the absolute value of a root is greater than certain 1/ϵ>0, that is, λ≥1/ϵ, and denoting a=max⁡0≤k≤n-3ak, after some operations we obtain (21)J′(λ)≤a22ϵ3+3ϵ4+⋯+n-1ϵn=Oϵ3,1+J(λ)λ≤1+an-12ϵ+a2ϵ3+ϵ4+⋯+ϵn=1+O(ϵ).In view of this reasoning, it seems that roots withϵ≪1, that is, those with large absolute value, will present local convergence for some of the proposed recursive sequences. However, although intuitive, this result is not valid in general since the inequalities given by (21) do not guarantee (17). Let us improve the necessary conditions to impose on the polynomial coefficients to check convergence. For that, we define the concept ofpivots of a polynomial.


## 2.3. Global Convergence

For any iterative numerical scheme, it is always desirable to providea priori information about the convergence. If certain recursive sequence is convergent for any starting point inside certain complex set, it is said that such sequence is globally convergent. This section aimed to study the global convergence of the recursive sequences within sets with closed balls centered at two characteristic points of the polynomials u and v, namedpivots of the polynomial.Definition 9 (pivots).
One defines the pivots of polynomialp(x)=a0+a1x+⋯+an-2xn-2+an-1xn-1+xn to the following complex numbers: (22)u=-an-12+γ,v=-an-12-γ,where (23)γ=an-122-an-2.The pivots of a polynomial have the property of lying close to some root when these pivots are relatively large (in absolute value) with respect to the rest of polynomial coefficients. This may be an important advantage because the pivots can be used as effective initial guesses in a recursive scheme. This behavior is explained in the results of this section. The first result (Proposition10) states that the pivot u is a point of attraction in the (complex) infinite of X(z). The same argument holds for the pivot v and Y(z).Proposition 10.
Letu,v∈A be the pivots of the polynomial p(x); then (i)
limu→∞X(u)/u=1, limu→∞X′(u)=0;(ii)
limv→∞Y(v)/v=1, limv→∞Y′(v)=0.Proof.
(i) From the definition ofJ(z) given in (4), let us calculate the following limits: (24)limu→∞Ju=limu→∞12an-1+an-3u2+an-2u3+⋯+a0un-1=an-12(25)limu→∞J′u=limu→∞-122an-3u3+3an-2u4+⋯+(n-1)a0un=0.Now, from the expressions of X(z) and X′(z) given by (2), (18) and by (22), (24) (26)limu→∞X(u)u=limu→∞-J(u)+J2(u)-an-2u=limu→∞-an-1/2+an-1/22-an-2u=limu→∞uu=1limu→∞dXdz=limu→∞J′(u)X(u)X(u)+J(u)=limu→∞J′uXu/uXu/u+Ju/u=0·11+0=0.The proof for the function Y(z) is analogous.This result justifies the use of the family of closed balls centered atu and v as suitable sets for the global convergence of {xk} and {yk}, respectively. In what follows up to the next section, only the case of the recursive function X(z) will be rigorously analyzed. The proofs of the lemmas and theorems can easily be extrapolated to the case of Y(z).Let us assume thatu∈A and denote 0<r<u to the radius of the closed ball centered at u; that is, B(u,r)={z∈C:z-u≤r}.Lemma 11.
Letρr=u-r>0 be the distance between the origin and the ball B(u,r); that is, ρr=min⁡{z:z∈B(u,r)}. Let one denote a=max⁡0≤k≤n-3ak. If γ≠0, then for any z∈B(u,r)(i)
J(z)-an-1/2≤a/2ρrn-1ρrn-2-1/ρr-1≡ψr;(ii)
J(z)≤an-1/2+ψr;(iii)
J′(z)≤aρrn-1+ρrn-2-nρr-1-1/2ρrnρr-12≡ηr;(iv)
J2(z)-an-1/22≤ψran-1+ψr≡γ2αr;(v)
J2(z)-an-2-1/2≤1/γ1-αr,  αr<1.Proof.
(i) From the definition ofρr, z≥ρr holds for all z∈B(u,r). Consequently (27)J(z)-an-12=12an-3z2+an-4z3+⋯+a0zn-1≤12an-3z2+an-4z3+⋯+a0zn-1≤12az2+az3+⋯+azn-1≤12aρr2+aρr3+⋯+aρrn-1=a2ρr21+1ρr+⋯+1ρrn-3=a2ρrn-1ρrn-2-1ρr-1=ψr,where the expression of the general term of the sum ∑k=2n-1‍ρr-(k-2) has been used.
(ii) Using the previous result(28)J(z)≤Jz-an-12+an-12≤an-12+ψr.
(iii) Following the same reasoning as that of (27) (29)J′(z)=12-2an-3z3-3an-4z4-⋯-(n-1)a0zn≤122an-3z3+3an-4z4+⋯+(n-1)a0zn≤a22z3+3z4+⋯+n-1zn≤aρrn-1+ρrn-2-nρr-1-12ρrnρr-12≡ηr,where now the expression of the sum ∑k=1n-2‍(k+1)ρr-k has been used.
(iv) From the bounds calculated in (i) and (ii)(30)J2(z)-an-122≤J(z)-an-12J(z)+an-12≤ψran-12+ψr+an-12=ψran-1+ψr≡γ2αr.Here the number αr=ψran-1+ψr/γ2 has been introduced in order to simplify the notation in subsequent developments.
(v) Let us define the functionT(z) as that one which verifies the following identity: (31)J2(z)-an-2=γ1+T(z);after some direct operations and using the definition of γ2=an-12/4-an-2, we obtain T(z)=J2(z)-an-12/4/γ2. Consequently, (32)J2(z)-an-2-1/2=1γ11+T(z).Now, using Lemma 11(iv), it is verified that T(z)≤αr, ∀z∈B(u,r). Hence, assuming that αr<1 and expanding in power series (33)11+T(z)=∑k=0∞‍-12kTk(z)≤∑k=0∞‍-12kT(z)k≤∑k=0∞‍-12kαrk=∑k=0∞‍-1k-12kαrk=∑k=0∞‍-12k-αrk=11-αr.The same conclusions of this lemma can easily be extrapolated for pivotv, simply changing u by v in the above expressions. In this case, ρr=v-r>0 is defined as the distance between the origin and the ball B(v,r); that is, ρr=min⁡{z:z∈B(v,r)}.Lemma 12.
Under the same conditions of Lemma11, let us consider the positive real numbers that depend on the radius r of the ball B(u,r) centered at pivot u and depending on ρr=u-r: (34)Kr=ηr1+an-1+2ψr2γ1-αr,βr=ψrr+γr1-1-αr.If αr<1 and B(u,r)⊂A, then(i)
X′(z)≤Kr, ∀z∈B(u,r);(ii)
X(z)-u≤rβr, ∀z∈B(u,r).Proof.
(i) Evaluating the derivative ofX(z) at a point z∈B(u,r) and using the Lemmas 11(ii), (iii), and (v) (35)dXdz=J′(z)1-J(z)J2(z)-an-2≤J′(z)1+J(z)J2(z)-an-2≤ηr1+an-1/2+ψrγ1-αr=Kr.
(ii) From the definition ofT(z) given in (32) and Lemmas 11(i), (iv), and (v), the distance between X(z) and u can be bounded by (36)Xz-u≤Jz-an-12+J2z-an-2-an-122-an-2=Jz-an-12+γ1+Tz-γ=Jz-an-12+γ1+Tz-γ≤ψr+γ1+Tz-1≤ψr+γ∑k=0∞‍12kTkz-1=ψr+γ∑k=1∞‍12kTkz≤ψr+γ∑k=1∞‍12kT(z)k≤ψr+γ∑k=1∞‍12kαrk=ψr+γ∑k=1∞‍-1k+112kαrk=ψr+γ1-1-αr=rβr.With the help of the above lemmas, the main result on global convergence can already be presented.Theorem 13.
Letαr, Kr, and βr be the numbers defined in Lemmas 11 and 12. Also, let us assume that, for the radius r>0, the ball B(u,r)⊂A. If αr<1, Kr<1, and βr≤1, then there exists a unique single root λ∈B(u,r) of the polynomial p(x), which is point of attraction of the function X(z) for any x0∈B(u,r). Moreover, (37)xk-λ≤Krk1-KrX(x0)-x0,∀x0∈B(u,r).Proof.
Let us demonstrate thatX(z):B(u,r)→B(u,r) is a contractive self-mapping. Indeed, the contractivity arises from the inequality X′(z)≤Kr<1 deduced from Lemma 12(ii). Furthermore, if z∈B(u,r) the self-mapping can be demonstrated from Lemma 12(ii) and hypothesis βr≤1(38)X(z)-u≤rβr≤r.Hence, the complex number X(z)∈B(u,r), ∀z∈B(u,r).
Therefore, the Banach contraction principle can be applied ensuring that there exists a unique fixed pointλ∈B(u,r) of the function X(z) so that limn→∞xn=λ, for any x0∈B(u,r). Furthermore (39)xk-λ≤Krk1-KrX(x0)-x0.Lemma12 and Theorem 13 have been presented for describing the conditions under which global convergence towards fixed points of X(z) in balls of the form B(u,r) can be guaranteed. We can also find versions of these results for the function Y(z), for the pivot v and for the family of balls B(v,r). It is clear that, in such case, αr, βr, and Kr have exactly the same mathematical form although the meaning of r is now the radius of a ball centered at v and ρr=v-r is the distance between the origin and B(v,r). In order to be consistent in the presentation of the results we also write the associated lemma and theorem about convergence of sequences {yk} within balls B(v,r).Lemma 14.
Under the same conditions of Lemma11, let one consider the positive real numbers that depend on the radius r of the ball B(v,r) centered at pivot v and depending on ρr=v-r: (40)Kr=ηr1+an-1+2ψr2γ1-αr,βr=ψrr+γr1-1-αr.If αr<1 and B(v,r)⊂A, then(i)
Y′(z)≤Kr, ∀z∈B(v,r);(ii)
Y(z)-v≤rβr, ∀z∈B(v,r).Theorem 15.
Letαr, Kr, and βr be the numbers defined in Lemmas 11 and 14. Also, let one assume that, for the radius r>0, the ball B(v,r)⊂A. If αr<1, Kr<1, and βr≤1, then there exists a unique single root λ∈B(v,r) of the polynomial p(x), which is point of attraction of the function Y(z) for any y0∈B(v,r). Moreover, (41)yk-λ≤Krk1-KrY(y0)-y0,∀y0∈B(v,r).From the definition ofY(z) we have the two inequalities (42)dYdz=J′(z)-1-J(z)J2(z)-an-2≤J′(z)1+J(z)J2(z)-an-2Y(z)-v≤J(z)-an-12+J2(z)-an-2-an-122-an-2.Just comparing these expressions with (35), (36), it is clear that Y′(z) and Y(z)-v bounds have the same mathematical expressions as those of X′(z) and X(z)-u in B(u,r). Consequently, the proof of Lemma 14 and Theorem 15 can be omitted since they can be directly deduced from the proofs of Lemma 12 and Theorem 13.The necessary conditions of this theorem are given in terms of the three numbersαr, βr, and Kr, (30), (34), calledconvergence indexes and introduced in Lemmas 11, 12, and 14. These indexes can be used to construct ana priori test to check global convergence, since for their calculation no previous root-computing is needed. For that, chosen a radius r, the indexes ensure the convergence of the RF provided that αr,Kr<1 and βr≤1. If these inequalities are verified for ball B(u,r) as well as for B(v,r), then we can ensure that the two sequences {xk} and {yk} are convergent and the method reaches two different roots. On the opposite, if there does not exist radius r verifying αr<1, Kr<1, and βr≤1, for some ball B(u,r) or B(v,r), global convergence cannot bea priori ensured. The latter obviously is not synonymous of no convergence, because local convergence could still arise. Let us illustrate the application of this test with an example considering the 16th order polynomial (43)p(x)=x16+5x15+5x14-1.The test is equivalent to find at least a radius r>0 so that αr,Kr<1 and βr≤1 for both the sequences {xk} and {yk}. Thus, the indexes associated with the pivot v (global convergence of {yk}) are represented as function of the radius r in Figure 1. It can be observed that αr,βr,Kr<1 in the range 0.208<r<1.296, consequently ensuring the global convergence for any ball B(v,r) centered at v and radius in the previous range. Furthermore, ana priori estimation of the (linear) velocity of convergence can be calculated for rmin⁡=0.208, resulting in Kmin⁡=0.156. Otherwise, testing balls of the form B(u,r), centered at the other pivot u (global convergence of {xk}), we observe that αr>1 in the whole range 0<r<u. Note that although the recursive sequence {xk} does not pass the test, it locally converges to a root. The polynomial of (55) is an example that presents a good behavior with both recursive sequences, but the sequence {yk} passes the test, whereas the other {xk} does not. In general, the proposed test is somewhat conservative; in fact, several numerical experiences have shown that convergence of recursive sequences can succeed (starting at the pivots) for polynomials that do not pass the test.Figure 1
Test of global convergence for polynomialp(x)=x16+5x15+5x14-1.To conclude this section, we will make some remarks on the convergence to multiple roots. As proved in Proposition3, a root λ=X(λ) with multiplicity m≥2 verifies X′(λ)=1. Therefore, λ∈A cannot be contained in any closed ball B(u,r)⊂A verifying X′(z)≤Kr<1. In this case, the Banach contraction principle does not provide information on the convergence, although if it holds the scheme will present sublinear velocity [2] as shown in the numerical examples.


## 3. Corrected Recursive Functions

### 3.1. Definitions and Previous Results

Since the velocity of the recursive scheme given by the proposed functionsX(z) and Y(z) is linear for single roots, the objective is to propose two new functions, whose associated recursive sequences present quadratic convergence. For that, we construct the following two functions based on Steffensen’s acceleration method [39] used for iterative fixed point schemes (more details can be found in [2]): (44)F(z)=X(z)-X′(z)z1-X′(z),G(z)=Y(z)-Y′(z)z1-Y′(z).We name these functionscorrected recursive functions (CRF); consequently, associated with them, there exist two recursive fixed-point schemes, named corrected recursive sequences and presented in the following definition.Definition 16 (corrected recursive sequences).
Letx^0,y^0∈A be two complex numbers and let F(z) and G(z) be the CRF. Let one define the associated corrected recursive sequences as (45)x^k=Fx^k-1,y^k=Gy^k-1,k≥1.As will be demonstrated, the introduction of the functionsF(z) and G(z) considerably improves the convergence velocity. In fact, both functions have the same properties as those of Steffensen’s method: (a) any fixed point of X(z) and Y(z) is point of attraction of F(z) and G(z) even for multiple roots, and (b) the convergence to the fixed points is quadratic for single roots.


### 3.2. Local Convergence

The present subsection deals with the local convergence of sequences{x^k}k=1∞ and {y^k}k=1∞. Let us see that effectively the introduction of F(z) and G(z) accelerates the convergence. Indeed, naming f(z)=z-X(z) and g(z)=z-Y(z), it is easy to prove that the corrected recursive sequences are Newton’s schemes of f and g; that is, (46)x^k=x^k-1-f(x^k-1)f′(x^k-1),y^k=y^k-1-g(y^k-1)g′(y^k-1).Consequently, the convergence can be resumed in the following theorem. The details of the proof can be found in reference [2].Theorem 17.
Letλ∈A be a root of the equation p(x)=0 with multiplicity m≥1.(i)
Ifλ=X(λ), then F(λ)=λ and F′(λ)=m-1/m. Furthermore, the sequence {x^k} locally converges to λ if m=1 with quadratic velocity and with linear velocity when m>1.(ii)
Ifλ=Y(λ), then G(λ)=λ and G′(λ)=m-1/m. Furthermore, the sequence {y^k} locally converges to λ with quadratic velocity when m=1 and with linear velocity when m>1.The previous theorem states that any root of the polynomialp(x) is a point of attraction of some corrected recursive function. If the initial guess is close enough to a root, it can be assured that the sequence converges. However, since the corrected recursive sequences are after all two Newton’s schemes, they are sensitive to the chosen initial guesses. Fortunately, the behavior of the CRF with respect to the pivots is the same as that of the RF. Thus, when the pivots u and v (see Definition 9) are relatively large in absolute value, at least one of them lies close to some root, which in turn is also high (in absolute value) respect to the other roots.


### 3.3. Global Convergence

As shown in Section2.3, the necessary conditions for global convergence of the RF X(z) and Y(z) are related to the location of u, v defined in (22). The main results were presented at Proposition 10 and Theorem 13. As with X(z) and Y(z), u, v also are points of attraction of the corrected recursive functions at the infinite. This property is demonstrated in the following proposition.Proposition 18.
Ifu,v∈A are the complex numbers defined by (22), then (i)
limu→∞F(u)/u=1, limu→∞F′(u)=0;(ii)
limv→∞G(v)/v=1, limv→∞G′(v)=0.Proof.
From the results obtained in Proposition10(47)limu→∞F(u)u=limu→∞X(u)-uX′(u)u1-X′(u)=u-0u1-0=1limv→∞G(v)v=limv→∞Y(v)-vY′(v)v1-Y′(v)=v-0v1-0=1.
Differentiating now two times (4) of J(z)(48)limu→∞J′′(u)=limu→∞122·3an-3u4+3·4an-2u5+⋯+(n-1)·na0un+1=0.Consequently, limu→∞uJ′′(u)=0 also holds. Hence (49)limu→∞X′′u=limu→∞-an-2J′u2Ju2-an-23/2-J′′(u)X(u)Ju2-an-21/2=limu→∞-an-2·0an-12/4-an-23/2-J′′(u)uan-12/4-an-21/2=0.In the same way, it is verified that limz→∞Y′′(z)=0. Finally, calculating the derivative of F(z) and G(z) and taking limits result in (50)limu→∞F′(u)=limu→∞X(u)-uX′′(u)1-X′(u)2=0limv→∞G′(v)=limv→∞Y(v)-vY′′(v)1-Y′(v)2=0.The previous proposition suggests that, under similar conditions as those imposed forX(z) and Y(z), global convergence in a closed ball centered in u or v for F(z) and G(z) can also be assured. Therefore, choosing x^0=u and y^0=v, the sequences {x^k} and/or {y^k} may converge to a root provided that u, v are large in absolute value. This choice considerably improves the efficiency of the recursive scheme because two good approximations are available as starting points. In fact, as will be shown in the numerical examples, the approximation given by F(u) or (and) G(v) becomes a very accurate estimation of one (two) root(s) of the polynomial.We think that the polynomial pivotsu, v and theirone-step initial approximations, F(u), G(v), represent the main advantage of the present method since they constitute themselves good estimations of one or even two roots for certain classes of polynomials. Hence, they could be used as initial guesses not only for the proposed recursive sequences but also within other efficient root-finding algorithms [40]. Another contribution of the present paper is to identify quantitatively this class of polynomials. For that, Theorem 13 on global convergence inside closed balls centered in the pivots, B(u,r) and B(v,r), is used. The theory shows that those polynomials that pass the test present global convergence in previously defined closed balls. Numerical experiences show that the pivots of these classes of polynomials usually lie close to some root. Furthermore, F(u) and/or G(v) represent in such cases a much more accurate approximation of this root, which in general coincides with the largest one. This latter affirmation was qualitatively advanced in Theorem 8 and in subsequent comments; see (21). Now, the following section which focused on the convergence region also validates this affirmation, showing a close relationship between theroot’s size (in the sense of its absolute value) and the quality of the proposed method.


### 3.4. Remarks on the Convergence Region

As proved in the theorems presented in this section, local convergence is always guaranteed for the corrected recursive functions. Therefore, choosing a starting point close enough to a root, the recursive sequence will converge. However, the following question arises: which complex number must be chosen as starting point? As well known, this is a key issue but very difficult to answer for any nonglobally convergent root finder. It was proved in the previous subsections that the pivots of the polynomial are a good choice under certain conditions. But how to relate the convergence region, that is, the set of valid initial points for which convergence holds, with the functionsF(z) and G(z)? As expected from the previous argumentation, roots with larger absolute value present also a wider convergence radius.To this end, firstly it will be demonstrated that ifλ is a fixed point of X(z) and F(z), it is verified that (51)limλ→∞djF(λ)dzj=0,j=2,3,….From the definition ofJ(z) and X(z) given in (4) and (2), it follows that the approximation order is (52)J(j)(λ)=O(λ-2-j),X(j)(λ)=O(λ-2-j),j=2,3,….Now, assuming thatλ is a single root (for multiple roots, the analysis would be analog and will be omitted), the second and the third derivative of F(z) at z=λ can be directly calculated from its definition given by (44), resulting in (53)F′′(λ)=-X′′(λ)1-X′(λ)2,F′′′(λ)=-3X′′(λ)1-X′(λ)2-2X′′′(λ)1-X′(λ).Note that sinceλ has multiplicity m=1, it is verified that X′(λ)≠1, from Proposition 3. Introducing the approximation order of (52) in (53), it follows that (54)F′′(λ)=O(λ-4),F′′′(λ)=O(λ-5).These expressions can easily be generalized by induction giving F(j)(λ)=O(λ-2-j) and consequently (51) holds.Secondly, let us consider the closed ballB(λ,δ) centered at the root λ with radius δ>0. From the theorem of Earle-Hamilton [41] on fixed points of analytical self-mappings, the sequence {x^k} starting at any point x0∈B(λ,δ) is convergent towards λ if there exists a positive real number 0<K(δ)<1 (in general depending on δ) so that (55)F(z)-λ<Kδδ.Since λ is a single root, F(λ)=λ and F′(λ)=0. The expansion of function F(z) around z=λ leads to (56)F(z)=λ+∑j=2∞‍F(j)(λ)j!z-λj.ApproximatingF(z) to the second order, the distance between F(z) and the root can be bounded by (57)F(z)-λ≈12F′′(λ)z-λ2≤F′′(λ)2δ2=F′′(λ)δ2δ≡K2(δ)δ,where K2(δ)<1 holds only if (58)δ<2F′′(λ)≡δ2.Therefore, a second order approximation of F(z) generates a radius of convergence δ2 inversely proportional to F′′(λ), which in turn tends to zero when the root increases in absolute value, as shown in (54).ApproximatingF(z) to the third order, the distance between F(z) and the root can be bounded by (59)F(z)-λ≈12!F′′(λ)z-λ2+13!F′′′(λ)z-λ3≤F′′λ2δ2+F′′′λ6δ3=F′′(λ)2δ+F′′′(λ)6δ2δ≡K3(δ)δand K3(δ)<1 holds only if (60)δ<-3F′′(λ)+9F′′(λ)2+24F′′′(λ)2F′′′(λ)≡δ3.Since, F′′(λ)=O(λ-4) and F′′′(λ)=O(λ-5), the radius of convergence δ3→∞ when λ→∞.For thepth order approximation of F(z), new values of the radius of convergence δp can be calculated as result of the following inequality: (61)Kpδ=F′′(λ)2!δ+F′′′(λ)3!δ2+⋯+F(p)(λ)p!δp-1<1.Intuitively, it can be generalized that the radius of convergenceδp associated with the pth approximation of F(z) also increases with the roots, so that (62)limλ→∞δp=∞.Therefore, the higher the root in absolute value, the larger the convergence region, so that the proposed numerical method is expected to work better in the sense that there exist many more starting points from which convergence will hold. In the numerical examples this behavior will be validated showing that the proposed method presents convergence towards the largest roots. In practice, those polynomials with relatively high absolute values of the pivots with respect to the rest of the polynomial coefficients will present good behavior with respect to the convergence.


## 3.1. Definitions and Previous Results

Since the velocity of the recursive scheme given by the proposed functionsX(z) and Y(z) is linear for single roots, the objective is to propose two new functions, whose associated recursive sequences present quadratic convergence. For that, we construct the following two functions based on Steffensen’s acceleration method [39] used for iterative fixed point schemes (more details can be found in [2]): (44)F(z)=X(z)-X′(z)z1-X′(z),G(z)=Y(z)-Y′(z)z1-Y′(z).We name these functionscorrected recursive functions (CRF); consequently, associated with them, there exist two recursive fixed-point schemes, named corrected recursive sequences and presented in the following definition.Definition 16 (corrected recursive sequences).
Letx^0,y^0∈A be two complex numbers and let F(z) and G(z) be the CRF. Let one define the associated corrected recursive sequences as (45)x^k=Fx^k-1,y^k=Gy^k-1,k≥1.As will be demonstrated, the introduction of the functionsF(z) and G(z) considerably improves the convergence velocity. In fact, both functions have the same properties as those of Steffensen’s method: (a) any fixed point of X(z) and Y(z) is point of attraction of F(z) and G(z) even for multiple roots, and (b) the convergence to the fixed points is quadratic for single roots.


## 3.2. Local Convergence

The present subsection deals with the local convergence of sequences{x^k}k=1∞ and {y^k}k=1∞. Let us see that effectively the introduction of F(z) and G(z) accelerates the convergence. Indeed, naming f(z)=z-X(z) and g(z)=z-Y(z), it is easy to prove that the corrected recursive sequences are Newton’s schemes of f and g; that is, (46)x^k=x^k-1-f(x^k-1)f′(x^k-1),y^k=y^k-1-g(y^k-1)g′(y^k-1).Consequently, the convergence can be resumed in the following theorem. The details of the proof can be found in reference [2].Theorem 17.
Letλ∈A be a root of the equation p(x)=0 with multiplicity m≥1.(i)
Ifλ=X(λ), then F(λ)=λ and F′(λ)=m-1/m. Furthermore, the sequence {x^k} locally converges to λ if m=1 with quadratic velocity and with linear velocity when m>1.(ii)
Ifλ=Y(λ), then G(λ)=λ and G′(λ)=m-1/m. Furthermore, the sequence {y^k} locally converges to λ with quadratic velocity when m=1 and with linear velocity when m>1.The previous theorem states that any root of the polynomialp(x) is a point of attraction of some corrected recursive function. If the initial guess is close enough to a root, it can be assured that the sequence converges. However, since the corrected recursive sequences are after all two Newton’s schemes, they are sensitive to the chosen initial guesses. Fortunately, the behavior of the CRF with respect to the pivots is the same as that of the RF. Thus, when the pivots u and v (see Definition 9) are relatively large in absolute value, at least one of them lies close to some root, which in turn is also high (in absolute value) respect to the other roots.


## 3.3. Global Convergence

As shown in Section2.3, the necessary conditions for global convergence of the RF X(z) and Y(z) are related to the location of u, v defined in (22). The main results were presented at Proposition 10 and Theorem 13. As with X(z) and Y(z), u, v also are points of attraction of the corrected recursive functions at the infinite. This property is demonstrated in the following proposition.Proposition 18.
Ifu,v∈A are the complex numbers defined by (22), then (i)
limu→∞F(u)/u=1, limu→∞F′(u)=0;(ii)
limv→∞G(v)/v=1, limv→∞G′(v)=0.Proof.
From the results obtained in Proposition10(47)limu→∞F(u)u=limu→∞X(u)-uX′(u)u1-X′(u)=u-0u1-0=1limv→∞G(v)v=limv→∞Y(v)-vY′(v)v1-Y′(v)=v-0v1-0=1.
Differentiating now two times (4) of J(z)(48)limu→∞J′′(u)=limu→∞122·3an-3u4+3·4an-2u5+⋯+(n-1)·na0un+1=0.Consequently, limu→∞uJ′′(u)=0 also holds. Hence (49)limu→∞X′′u=limu→∞-an-2J′u2Ju2-an-23/2-J′′(u)X(u)Ju2-an-21/2=limu→∞-an-2·0an-12/4-an-23/2-J′′(u)uan-12/4-an-21/2=0.In the same way, it is verified that limz→∞Y′′(z)=0. Finally, calculating the derivative of F(z) and G(z) and taking limits result in (50)limu→∞F′(u)=limu→∞X(u)-uX′′(u)1-X′(u)2=0limv→∞G′(v)=limv→∞Y(v)-vY′′(v)1-Y′(v)2=0.The previous proposition suggests that, under similar conditions as those imposed forX(z) and Y(z), global convergence in a closed ball centered in u or v for F(z) and G(z) can also be assured. Therefore, choosing x^0=u and y^0=v, the sequences {x^k} and/or {y^k} may converge to a root provided that u, v are large in absolute value. This choice considerably improves the efficiency of the recursive scheme because two good approximations are available as starting points. In fact, as will be shown in the numerical examples, the approximation given by F(u) or (and) G(v) becomes a very accurate estimation of one (two) root(s) of the polynomial.We think that the polynomial pivotsu, v and theirone-step initial approximations, F(u), G(v), represent the main advantage of the present method since they constitute themselves good estimations of one or even two roots for certain classes of polynomials. Hence, they could be used as initial guesses not only for the proposed recursive sequences but also within other efficient root-finding algorithms [40]. Another contribution of the present paper is to identify quantitatively this class of polynomials. For that, Theorem 13 on global convergence inside closed balls centered in the pivots, B(u,r) and B(v,r), is used. The theory shows that those polynomials that pass the test present global convergence in previously defined closed balls. Numerical experiences show that the pivots of these classes of polynomials usually lie close to some root. Furthermore, F(u) and/or G(v) represent in such cases a much more accurate approximation of this root, which in general coincides with the largest one. This latter affirmation was qualitatively advanced in Theorem 8 and in subsequent comments; see (21). Now, the following section which focused on the convergence region also validates this affirmation, showing a close relationship between theroot’s size (in the sense of its absolute value) and the quality of the proposed method.


## 3.4. Remarks on the Convergence Region

As proved in the theorems presented in this section, local convergence is always guaranteed for the corrected recursive functions. Therefore, choosing a starting point close enough to a root, the recursive sequence will converge. However, the following question arises: which complex number must be chosen as starting point? As well known, this is a key issue but very difficult to answer for any nonglobally convergent root finder. It was proved in the previous subsections that the pivots of the polynomial are a good choice under certain conditions. But how to relate the convergence region, that is, the set of valid initial points for which convergence holds, with the functionsF(z) and G(z)? As expected from the previous argumentation, roots with larger absolute value present also a wider convergence radius.To this end, firstly it will be demonstrated that ifλ is a fixed point of X(z) and F(z), it is verified that (51)limλ→∞djF(λ)dzj=0,j=2,3,….From the definition ofJ(z) and X(z) given in (4) and (2), it follows that the approximation order is (52)J(j)(λ)=O(λ-2-j),X(j)(λ)=O(λ-2-j),j=2,3,….Now, assuming thatλ is a single root (for multiple roots, the analysis would be analog and will be omitted), the second and the third derivative of F(z) at z=λ can be directly calculated from its definition given by (44), resulting in (53)F′′(λ)=-X′′(λ)1-X′(λ)2,F′′′(λ)=-3X′′(λ)1-X′(λ)2-2X′′′(λ)1-X′(λ).Note that sinceλ has multiplicity m=1, it is verified that X′(λ)≠1, from Proposition 3. Introducing the approximation order of (52) in (53), it follows that (54)F′′(λ)=O(λ-4),F′′′(λ)=O(λ-5).These expressions can easily be generalized by induction giving F(j)(λ)=O(λ-2-j) and consequently (51) holds.Secondly, let us consider the closed ballB(λ,δ) centered at the root λ with radius δ>0. From the theorem of Earle-Hamilton [41] on fixed points of analytical self-mappings, the sequence {x^k} starting at any point x0∈B(λ,δ) is convergent towards λ if there exists a positive real number 0<K(δ)<1 (in general depending on δ) so that (55)F(z)-λ<Kδδ.Since λ is a single root, F(λ)=λ and F′(λ)=0. The expansion of function F(z) around z=λ leads to (56)F(z)=λ+∑j=2∞‍F(j)(λ)j!z-λj.ApproximatingF(z) to the second order, the distance between F(z) and the root can be bounded by (57)F(z)-λ≈12F′′(λ)z-λ2≤F′′(λ)2δ2=F′′(λ)δ2δ≡K2(δ)δ,where K2(δ)<1 holds only if (58)δ<2F′′(λ)≡δ2.Therefore, a second order approximation of F(z) generates a radius of convergence δ2 inversely proportional to F′′(λ), which in turn tends to zero when the root increases in absolute value, as shown in (54).ApproximatingF(z) to the third order, the distance between F(z) and the root can be bounded by (59)F(z)-λ≈12!F′′(λ)z-λ2+13!F′′′(λ)z-λ3≤F′′λ2δ2+F′′′λ6δ3=F′′(λ)2δ+F′′′(λ)6δ2δ≡K3(δ)δand K3(δ)<1 holds only if (60)δ<-3F′′(λ)+9F′′(λ)2+24F′′′(λ)2F′′′(λ)≡δ3.Since, F′′(λ)=O(λ-4) and F′′′(λ)=O(λ-5), the radius of convergence δ3→∞ when λ→∞.For thepth order approximation of F(z), new values of the radius of convergence δp can be calculated as result of the following inequality: (61)Kpδ=F′′(λ)2!δ+F′′′(λ)3!δ2+⋯+F(p)(λ)p!δp-1<1.Intuitively, it can be generalized that the radius of convergenceδp associated with the pth approximation of F(z) also increases with the roots, so that (62)limλ→∞δp=∞.Therefore, the higher the root in absolute value, the larger the convergence region, so that the proposed numerical method is expected to work better in the sense that there exist many more starting points from which convergence will hold. In the numerical examples this behavior will be validated showing that the proposed method presents convergence towards the largest roots. In practice, those polynomials with relatively high absolute values of the pivots with respect to the rest of the polynomial coefficients will present good behavior with respect to the convergence.


## 4. Numerical Examples

### 4.1. Example  1

Let us consider the following13th order polynomial: (63)p1x=(x-2i)(x2-1)(x2+0.04)(x-1.5)×(x-0.5)(x+1.2)(x+3.5)(x+2i)×(x+6i)(x+1+i)(x-1-2i).The local convergence of the recursive functions is directly related to the first derivatives X′(λ) and Y′(λ) evaluated at the roots (see (18)), shown in Table 1 in absolute value. In view of the results, it can be ensured that the convergence of the sequence xk=X(xk-1) only holds for the root λ=-6i, since it is the only one for which X′(-6i)<1. Let us take the initial values of the sequences to be equal to the pivots calculated from (22); that is, (64)x0=x^0=u=-0.7674-5.7182i,y0=y^0=v=-1.9326+0.7182i.Hence, the recursive sequences {xk}, {yk} and the corrected {x^k}, {x^k} can be built. To visualize the convergence process, the iteration errors (65)eX(k)=xk-xk-1xk-1,e^F(k)=x^k-x^k-1x^k-1eY(k)=yk-yk-1yk-1,e^G(k)=y^k-y^k-1y^k-1are represented in Figure 2, which shows the linear decay of the sequence {xk} as demonstrated in Theorem 8. On the contrary, as predicted by Theorem 17 the convergence of the corrected recursive sequences {x^k} and {y^k} is quadratic, and this allows reaching the roots λ=-6i and λ=-3.5 with four and seven iterations, respectively. A tolerance of 10-12 for the iteration error has been assumed. Moreover, testing the recursive sequences for other starting points (not shown here), we find that they also converge in the great majority of cases. From Table 1, one can notice that F′′(λ) and G′′(λ) take their lowest values at these roots and therefore the first estimation of the convergence radius δ2 is higher than those in the other roots; see (58). This fact explains the satisfactory behavior of the method in this example and with these roots.Table 1
Results of local convergence for Example 1.
Fixed points ofX(z)
Fixed points ofY(z)
λ
|
X
′
(
λ
)
|
|
F
′
′
(
λ
)
|
δ
2
λ
|
Y
′
(
λ
)
|
|
G
′
′
(
λ
)
|
δ
2
-
6
i
0.240
0.099
20.202
-
3.5
1.775
1.116
1.792
-
2
i
7.074
2.870
0.696
1
+
2
i
6.904
7.959
0.251
-
1
-
i
16.012
19.723
0.101
2
i
5.715
8.484
0.235
-
1.2
10.924
17.757
0.112
1.5
13.707
18.629
0.107
-
1
28.299
82.769
0.024
1
60.455
134.280
0.015
-
0.2
i
8.424
E
+
7
8.410
E
+
8
2.378
E
-
9
0.5
1.223
E
+
4
4
.
936
E
+
4
4.048
E
-
5
0.2
i
9.359
E
+
7
9.344
E
+
8
2.141
E
-
9Figure 2
Example 1. Iteration errors. Pivots areu=-0.7674-5.7182i and v=-1.9326+0.7182i.Some remarks on the influence of the pivotsu and v can be made. The relative error between the root -6i and u=-0.76-5.72i is approximately 100(u+6i)/|-6i|≈13.6%. This confirms the theoretical result obtained in Proposition 10 and Theorem 13: roots relatively large (in absolute value) than the rest are close to the values u and v defined by (22). If, for example, instead of root -6i we take -12i, the pivot is updated to u=-0.42-11.89i and then the relative error becomes 100(u+12i)/|-12i|≈3.64%. It is important to note that the approximations given by u and v are closed-forms that depend on the polynomial coefficients, in particular on an-1 and an-2. These pivots had been proved to be an excellent initial estimation under certain conditions. Moreover, if these conditions hold, improved closed-forms can be constructed just evaluating F(u) or G(v) depending now on the complete set of coefficients. Thus, it can easily be verified that for the current example F(u)=0.0299-6.0178i and the relative distance with the root is only 100(F(u)+6i)/|-6i|≈0.58%, a very accurate one-step estimation.In order to compare the proposed method with another one of quadratic convergence, the iteration error for Newton’s method has also been represented in Figure2. If {tk} is Newton’s sequence, it is well known that the sequence is (66)tk+1=tk-p(tk)p′(tk).Since the pivots of the polynomial, u and v, are relatively close to the roots -6i and -3.5, it should be expected that also Newton’s sequence converges to these roots, if t0=u,v are the starting points. However, both sequences converge to -2i and -1 and they do it quadratically as shown in Figure 2. Note that some iterations are needed before Newton’s scheme finds the convergence region of the roots, iteration in which the quadratic convergence can be visualized. This shortcoming does not occur in this example with the proposed method, which provides not only recursive functions but also efficient initial guesses given by the pivots.


### 4.2. Example  2

In this example, the behavior of the method for multiple roots is examined using the polynomial(67)px=x-2i2(x2-1)(x2+0.04)×(x-1.5)(x-0.5)(x+1.2)×(x+3.5)(x+2i)(x+6i)(x+1+i)×(x-1-2i).Note that it has the same roots as those of Example 1, though now2i has multiplicity m=2. As in Example 1, the relevant values related to convergence are listed in Table 2. It can be observed that the double root exactly verifies Y′(2i)=1.0 as predicted by Theorem 13. Although this does not guarantee the convergence of {yk}, it may occur that, depending on the initial point y0, the approaching path lies inside the region where Y′(yk)<1 but close to the unity. In this case the convergence order becomes sublinear as can be seen for {yk} in Figure 3. As predicted by Theorem 17, the acceleration process through G(z) leads for this double root to a linear convergence that clearly can be visualized in Figure 3 for {y^k}. However, the iteration error is not able to decrease under approximately 10-9. This limit is due to the singularity of 2i in G(z) that, although removable, produces some numerical instabilities when the function is evaluated at the proximity of the root. The radius of convergence δ2 can also be estimated for the double root using a parallel development as that for single roots. The root 2i presents the largest value of δ2, the fact that can explain why the sequence, although linearly, converges to this root for initial values relatively far from the root; for example, the freely chosen y0=-4-4i.Table 2
Results of local convergence for Example 2.
Fixed points ofX(z)
Fixed points ofY(z)
λ
|
X
′
(
λ
)
|
|
F
′
′
(
λ
)
|
δ
2
λ
|
Y
′
(
λ
)
|
|
G
′
′
(
λ
)
|
δ
2
-
6
i
0.439
0.186
10.727
1
+
2
i
2.569
4.062
0.492
-
3.5
6.688
10.900
0.183
+
2
i
1.000
1.037
0.964
-
2
i
9.224
5.140
0.389
+
1.5
17.410
24.286
0.082
-
1
-
i
21.574
31.429
0.064
+
1
100.890
221.590
0.009
-
1.2
i
14.270
27.369
0.073
+
0.5
3.67
E
+
4
1.49
E
+
5
1.34
E
-
5
-
1
48.698
101.740
0.020
+
0.2
i
6.10
E
+
8
6.09
E
+
9
3.28
E
-
10
-
0.2
i
6.71
E
+
8
6.70
E
+
9
2.99
E
-
10Figure 3
Example 2. Iteration errors. Pivots areu=-1.22-5.50i and v=-1.48+2.50i.The results of the proposed method for functionsX(z) and F(z) are similar to those of Example 1. As shown in Table 2, the sequence {xk} again presents local convergence towards the root -6i with an approximate convergence radius δ2 significantly higher than those of the rest of fixed points of X(z).


## 4.1. Example  1

Let us consider the following13th order polynomial: (63)p1x=(x-2i)(x2-1)(x2+0.04)(x-1.5)×(x-0.5)(x+1.2)(x+3.5)(x+2i)×(x+6i)(x+1+i)(x-1-2i).The local convergence of the recursive functions is directly related to the first derivatives X′(λ) and Y′(λ) evaluated at the roots (see (18)), shown in Table 1 in absolute value. In view of the results, it can be ensured that the convergence of the sequence xk=X(xk-1) only holds for the root λ=-6i, since it is the only one for which X′(-6i)<1. Let us take the initial values of the sequences to be equal to the pivots calculated from (22); that is, (64)x0=x^0=u=-0.7674-5.7182i,y0=y^0=v=-1.9326+0.7182i.Hence, the recursive sequences {xk}, {yk} and the corrected {x^k}, {x^k} can be built. To visualize the convergence process, the iteration errors (65)eX(k)=xk-xk-1xk-1,e^F(k)=x^k-x^k-1x^k-1eY(k)=yk-yk-1yk-1,e^G(k)=y^k-y^k-1y^k-1are represented in Figure 2, which shows the linear decay of the sequence {xk} as demonstrated in Theorem 8. On the contrary, as predicted by Theorem 17 the convergence of the corrected recursive sequences {x^k} and {y^k} is quadratic, and this allows reaching the roots λ=-6i and λ=-3.5 with four and seven iterations, respectively. A tolerance of 10-12 for the iteration error has been assumed. Moreover, testing the recursive sequences for other starting points (not shown here), we find that they also converge in the great majority of cases. From Table 1, one can notice that F′′(λ) and G′′(λ) take their lowest values at these roots and therefore the first estimation of the convergence radius δ2 is higher than those in the other roots; see (58). This fact explains the satisfactory behavior of the method in this example and with these roots.Table 1
Results of local convergence for Example 1.
Fixed points ofX(z)
Fixed points ofY(z)
λ
|
X
′
(
λ
)
|
|
F
′
′
(
λ
)
|
δ
2
λ
|
Y
′
(
λ
)
|
|
G
′
′
(
λ
)
|
δ
2
-
6
i
0.240
0.099
20.202
-
3.5
1.775
1.116
1.792
-
2
i
7.074
2.870
0.696
1
+
2
i
6.904
7.959
0.251
-
1
-
i
16.012
19.723
0.101
2
i
5.715
8.484
0.235
-
1.2
10.924
17.757
0.112
1.5
13.707
18.629
0.107
-
1
28.299
82.769
0.024
1
60.455
134.280
0.015
-
0.2
i
8.424
E
+
7
8.410
E
+
8
2.378
E
-
9
0.5
1.223
E
+
4
4
.
936
E
+
4
4.048
E
-
5
0.2
i
9.359
E
+
7
9.344
E
+
8
2.141
E
-
9Figure 2
Example 1. Iteration errors. Pivots areu=-0.7674-5.7182i and v=-1.9326+0.7182i.Some remarks on the influence of the pivotsu and v can be made. The relative error between the root -6i and u=-0.76-5.72i is approximately 100(u+6i)/|-6i|≈13.6%. This confirms the theoretical result obtained in Proposition 10 and Theorem 13: roots relatively large (in absolute value) than the rest are close to the values u and v defined by (22). If, for example, instead of root -6i we take -12i, the pivot is updated to u=-0.42-11.89i and then the relative error becomes 100(u+12i)/|-12i|≈3.64%. It is important to note that the approximations given by u and v are closed-forms that depend on the polynomial coefficients, in particular on an-1 and an-2. These pivots had been proved to be an excellent initial estimation under certain conditions. Moreover, if these conditions hold, improved closed-forms can be constructed just evaluating F(u) or G(v) depending now on the complete set of coefficients. Thus, it can easily be verified that for the current example F(u)=0.0299-6.0178i and the relative distance with the root is only 100(F(u)+6i)/|-6i|≈0.58%, a very accurate one-step estimation.In order to compare the proposed method with another one of quadratic convergence, the iteration error for Newton’s method has also been represented in Figure2. If {tk} is Newton’s sequence, it is well known that the sequence is (66)tk+1=tk-p(tk)p′(tk).Since the pivots of the polynomial, u and v, are relatively close to the roots -6i and -3.5, it should be expected that also Newton’s sequence converges to these roots, if t0=u,v are the starting points. However, both sequences converge to -2i and -1 and they do it quadratically as shown in Figure 2. Note that some iterations are needed before Newton’s scheme finds the convergence region of the roots, iteration in which the quadratic convergence can be visualized. This shortcoming does not occur in this example with the proposed method, which provides not only recursive functions but also efficient initial guesses given by the pivots.


## 4.2. Example  2

In this example, the behavior of the method for multiple roots is examined using the polynomial(67)px=x-2i2(x2-1)(x2+0.04)×(x-1.5)(x-0.5)(x+1.2)×(x+3.5)(x+2i)(x+6i)(x+1+i)×(x-1-2i).Note that it has the same roots as those of Example 1, though now2i has multiplicity m=2. As in Example 1, the relevant values related to convergence are listed in Table 2. It can be observed that the double root exactly verifies Y′(2i)=1.0 as predicted by Theorem 13. Although this does not guarantee the convergence of {yk}, it may occur that, depending on the initial point y0, the approaching path lies inside the region where Y′(yk)<1 but close to the unity. In this case the convergence order becomes sublinear as can be seen for {yk} in Figure 3. As predicted by Theorem 17, the acceleration process through G(z) leads for this double root to a linear convergence that clearly can be visualized in Figure 3 for {y^k}. However, the iteration error is not able to decrease under approximately 10-9. This limit is due to the singularity of 2i in G(z) that, although removable, produces some numerical instabilities when the function is evaluated at the proximity of the root. The radius of convergence δ2 can also be estimated for the double root using a parallel development as that for single roots. The root 2i presents the largest value of δ2, the fact that can explain why the sequence, although linearly, converges to this root for initial values relatively far from the root; for example, the freely chosen y0=-4-4i.Table 2
Results of local convergence for Example 2.
Fixed points ofX(z)
Fixed points ofY(z)
λ
|
X
′
(
λ
)
|
|
F
′
′
(
λ
)
|
δ
2
λ
|
Y
′
(
λ
)
|
|
G
′
′
(
λ
)
|
δ
2
-
6
i
0.439
0.186
10.727
1
+
2
i
2.569
4.062
0.492
-
3.5
6.688
10.900
0.183
+
2
i
1.000
1.037
0.964
-
2
i
9.224
5.140
0.389
+
1.5
17.410
24.286
0.082
-
1
-
i
21.574
31.429
0.064
+
1
100.890
221.590
0.009
-
1.2
i
14.270
27.369
0.073
+
0.5
3.67
E
+
4
1.49
E
+
5
1.34
E
-
5
-
1
48.698
101.740
0.020
+
0.2
i
6.10
E
+
8
6.09
E
+
9
3.28
E
-
10
-
0.2
i
6.71
E
+
8
6.70
E
+
9
2.99
E
-
10Figure 3
Example 2. Iteration errors. Pivots areu=-1.22-5.50i and v=-1.48+2.50i.The results of the proposed method for functionsX(z) and F(z) are similar to those of Example 1. As shown in Table 2, the sequence {xk} again presents local convergence towards the root -6i with an approximate convergence radius δ2 significantly higher than those of the rest of fixed points of X(z).


## 5. Conclusions

In this paper, a new method for polynomial root-finding is presented. The key idea is the construction of two complex functions, called recursive functions, which can be used in a fixed-point recursive scheme. Necessary conditions for local and global convergence are provided. The latter are studied in a closed ball centered at two certain characteristic points, calledpivots of the polynomial. It is demonstrated that the pivots are fixed points of the recursive functions at the complex infinite. Necessarya priori conditions for global convergence are given in terms of the polynomial coefficients. In practice, if a root is in absolute value relatively larger than the others, one of the pivots lies at the proximity of such root. In such cases, the pivots have been demonstrated to be very good initial guesses, not only for the proposed recursive sequences but also for any existing iterative root-finding method. In practice, those polynomials whose pivots are relatively higher than the rest of the coefficients usually present convergence. In addition, the higher the absolute value of pivots, the faster the convergence.The convergence of the recursive sequences is linear and is not guaranteed for any initial point in the complex plane. For these reasons, corrected recursive functions are constructed to accelerate the convergence. These functions are inspired in the well-known Steffensen’s acceleration method and present the same properties: local convergence and the error-decay velocity quadratic for single roots and linear for multiple ones. The convergence region around the roots, that is, the set of complex values from which convergence holds, is studied. It is concluded that a direct relationship between the absolute value root and the convergence radius exists: the latter increases with the former.Finally, the theoretical results are validated with two numerical examples. In the first, the convergence of the proposed recursive sequences for a single-root polynomial is analyzed. This example clearly reveals the close connection between the pivots and the largest roots of the polynomial. In fact, under certain conditions, just evaluating the corrected recursive functions at the pivots can lead to a very accurate approximation of a root. In the second example the efficiency of the proposed method is studied for multiple roots. In them, as predicted by the theoretical results, the recursive sequences converge under a sublinear scheme, whereas the corrected sequences present now linear convergence. Further work is currently being developed to generalize the concept of polynomial pivots and to propose new more accurate initial approximations only based on the polynomial coefficients.



---

*Source: 413816-2015-03-23.xml*