Anomalies in the convergence of Traub-type methods with memory

1 INTRODUCTION

Iterative methods are useful tools to approximate the solution α of a nonlinear equation f (x)=0, where or of a nonlinear system of equations F(x)=0, . This area of numerical analysis has experienced great growth in recent years, with the design of new iterative schemes that improve the speed of convergence and the computational efficiency of the classical methods. Possibly, advances in the computational field of mathematics have enabled this development.

Given the variety of iterative schemes that exist in the literature, different classifications can be considered. The order of convergence1 gives an idea about the speed of convergence of the method to find the solution. The efficiency index, introduced by Ostrowsky2, links the order of convergence with the number of functional evaluations in each iteration. The presence or absence of derivatives in the iterative expression of the scheme restricts the problems that can be solved if these derivatives cannot be calculated. Moreover, iterative methods are classified depending if only one previous iteration is required (scheme without memory) or it is necessary to employ more than one (scheme with memory).

According to the Kung-Traub conjecture,3 iterative methods without memory with d functional evaluations per iteration have order of convergence at most 2^d−1. For this reason, the order of convergence of a method can be improved by including information from several previous iterations to get the next estimation, transforming it in a method with memory. When this upper bound is reached, the scheme is called optimal. This upper bound can be avoided if we work with methods with memory. We found in the literature several researchers with important results in this area, highlighting the works of Petković,4-6 Chun and Neta,7 or Soleymani et al8, 9 among others.10-13 Most of these works are based on the inclusion of an accelerating parameter in the iterative expression of a usually known iterative scheme.

To analyze the order of convergence of an iterative method with memory, we use the following result. 14

Theorem 1.Let ψ be an iterative method with memory that generates a sequence {x_k} of approximations of root α, and let this sequence converge to α. If there exist a nonzero constant η and nonnegative numbers t_i, i=0,1,…,m such that the inequality

holds being e_k=x_k−α, then the R-order of convergence of the iterative method ψ satisfies the inequality O_R(ψ,α) ≥ s^∗, where s^∗ is the unique positive root of the equation

It is known14 that R-order implies the classical order of convergence and we denote by {f_k}∼{g_k} when sequence {f_k/g_k} tends to a constant when k→+∞.

In recent years, it is usual to analyze the stability of known and new iterative methods in terms of the wideness of the set of converging initial approximations when they are applied on low-degree polynomials. This analysis is usually made by using techniques from complex discrete dynamical systems. However, when memory is introduced in the iterative methods, these tools cannot be applied. Campos et al15, 16 introduced a new procedure that constructs multidimensional real dynamical systems from these schemes with memory in order to analyze their dependence on initial estimations. When there exists a dependence on a real parameter, also it is possible to select those members of the parametric family with better stability properties.

In this work, starting from a well-known third-order method without memory, we perform in Section 2 a new family of iterative methods by including parameters on the original scheme. Then, we develop step by step the inclusion of memory on the resulting scheme to enhance the original order of convergence. The result is a uniparametric family of iterative methods with memory with higher order of convergence. After we introduce some basics on real dynamics with memory in Section 3, the stability analysis of the family with memory is studied in Section 4 by using real dynamical tools on the multidimensional rational function resulting from applying the proposed class of iterative methods on low-degree polynomial. Finally, Section 5 is devoted to the main conclusions of this work.

2 DESIGNING THE FAMILY OF METHODS WITH MEMORY

The iterative expression of the third-order Traub's scheme1 is

(1)

In this work, method 1 is modified by including two parameters and analyzing their role in the error equation. In particular, one of these parameters will be properly fixed to generate a family of iterative methods with memory, capitalizing this role. The dynamical analysis of the iterative methods allows the knowledge of their stability in terms of dependence of initial estimations. Therefore, the resulting family with memory will be applied on arbitrary quadratic polynomials.

When two parameters are included in the first and second steps of method 1, the scheme results is

(2)

The biparametric family 2 holds the original order of convergence, for all real β and γ, as shows the following result.

Theorem 2.Let be a real differentiable function in an open interval I. If α∈I is a simple real root of f (x)=0 and x₀ is close enough to α, then sequence {x_k} generated by 2 converges to α with order of convergence 3 for any real value of parameters β and γ, being the error equation:

(3)

where e_k=x_k−α and .

Proof.By using Taylor expansions around α, f (x_k) can be written as

and

Then, the first step of method 2 turns into

From the development and the previous ones, the error equation of family 2 is

Then, the order of convergence of family 2 is three for all value of the parameters β and γ.

Although family 2 has third order of convergence as Traub's method, the presence of parameter β in the lower term of the error equation allows the inclusion of memory. Let us note in Equation 3 that, for β=−c₂, the method reaches order 4 but c₂ cannot be used as α is unknown. Therefore, an approximation of is needed to increase the order of convergence.

In order to get an approximation for β without adding new functional evaluations, we use a Newton's interpolation polynomial of second degree.

(4)

Now, the value of β is approximated by

(5)

Replacing β by β_k in 2, we obtain the iterative expression

(6)

with x₀ and x₁ initial approximations.

The following result shows that the order of convergence of family 6, which is denoted by MMγ, results in 3.30.

Proof.The error equation 3 can be written as

(7)

Let us denote by e_k,y=y_k−α for all k. Expanding  f (x_k), f (x_k−1), and f ( y_k−1) by Taylor series on α, we have

where .

From the previous developments and the definition of N(t) given by 4, the lower terms for parameter β_k are

where denotes all the elements that the sum of the exponents of e_k, e_k−1 and e_k−1,y is at least 3.

Then, it is satisfied

(8)

Let the R-order of the method be at least p, so it means that

where D_k,p tends to the asymptotic error constant, D_p, when k→∞. Equivalently,

(9)

and then,

(10)

By using 8 and 9 in 7, we have

(11)

Finally, if we match the exponents of e_k in 10 and 11, we obtain the equation

whose only positive root gives the order of convergence of method MMγ, by using Theorem 1. This root is

Section 3 is devoted to describe the dynamical tools that we need to analyze the dynamical behavior of family MMγ (Section 4).

3 BASICS ON REAL MULTIDIMENSIONAL DYNAMICS

The main fundamentals about dynamical analysis for iterative procedures that include memory are introduced in the following. Further information can be found in other work Campos et al15, 16 and Chicharro et al,17, 18 wherein these fundamentals are developed. Moreover, the application of these concepts on diverse schemes with memory is also performed in the aforementioned references.

In general, an iterative procedure that uses m previous iterations in its iterative expression to obtain the next estimation can be expressed as

being the starting guesses x₀,x₁,…,x_m, m ≥ 1.

Let us remark that, for m=0, the iterative method does not include memory. For the sake of simplicity, we are developing the case of m=1. Therefore, the standard form results in

where x₀ and x₁ are initial guesses. However, function cannot have fixed points. Therefore, we define an auxiliary map such that

Let us also assume that the iterative scheme is applied on a polynomial p(x), so the resulting iteration function ϕ(x_k,x_k−1) is rational.

If (x_k−1,x_k) is a fixed point of Υ, then Υ(x_k−1,x_k)=(x_k−1,x_k) so, x_k+1=x_k and x_k=x_k−1. Hence, we define a discrete dynamical system from the iterative method with memory. In this way, is defined as

(12)

The orbit of a point x by Υ is defined as the set of images {x,Υ(x),Υ²(x),…,Υⁿ(x),…}.

Moreover, as a point x=(z,x) is defined as a fixed point x^F=(z,x)^F of Υ if

and if a fixed point x^F of operator Υ is different from (x^r,x^r), where x^r is a root of polynomial p(x), it is called strange fixed point. A point x_T is T-periodic if and , for t<T. A T-periodic point is hyperbolic when the eigenvalues of the associated Jacobian matrix Υ′(x_T) satisfy |λ_j|≠1, for all j. The asymptotical behavior of a periodic hyperbolic point x_T is characterized in the following result.19

Let us remark that a hyperbolic point is called saddle point if there exist an eigenvalue λ_i such that |λ_i|<1 and another eigenvalue λ_j such that |λ_j|>1. If all the eigenvalues satisfy |λ_j|=0, it is superattracting. The set of preimages of any order of a T-periodic point x^∗ is called basin of attraction

4 DYNAMICS ON MMγ

Based on the concepts introduced in Section 3, the dynamics of the family with memory MMγ when it is applied on quadratic polynomials is analyzed in this section.

Let us consider the following quadratic polynomials:

The choice of these three polynomials is based on the fact that every case of roots is analyzed. In this way, note that polynomial does not have real roots, the polynomial has a unique real root in x^∗=0 with multiplicity 2, and the polynomial has two real roots .

4.1 Analysis of the rational functions

In order to analyze the dynamical features, family MMγ is applied on the quadratic polynomials introduced previously. The resulting rational functions are analyzed in order to find their associated fixed points and their asymptotical behavior, showing the performance of the family depending on the initial estimations.

When family MMγ is applied over , we get the fixed-point operator

(13)

For calculating the fixed points of 13, we must solve z=x and Υ⁻(z,x)=(z,x). Then, the vectorial function Υ⁻(z,x) has two superattracting fixed points, and , that agree with the roots of the considered polynomial. In addition, the roots of the polynomial

also satisfy Υ⁻(x,x)=(x,x). Since we are working in real dynamics, from among the roots of , we only consider the strange fixed points in those regions where they are real. Then, the operator has a strange fixed point for all value of γ, denoted by , and two strange fixed points, , defined only when γ∈(−∞,−γ^∗)∪(γ^∗,+∞), being γ^∗≈3.38143 one of the roots of the polynomial .

Their stability depends on the value of the parameter. By analyzing the eigenvalues of the Jacobian matrix (Υ⁻)′(z,x) for each strange fixed point according to Theorem 4, we obtain that is always repelling for all real γ≠0 (see Figure 1A, where both eigenvalues are coincident and bigger than one, in absolute value), is a saddle point for γ∈(−∞,−γ^∗)∪(γ^∗,+∞) (it can be seen in Figure 1B that one eigenvalue is very close but lower than one and the other eigenvalue is bigger than one, in absolute value) and is saddle or attracting depending on the value of γ (in Figure 1C, different areas are observed where both eigenvalues are lower or bigger than one, in absolute value).

Due to the diversity of behavior of strange fixed points, these details can be summarized in Table 1 and Proposition 1.

Table 1. Stability of the strange fixed points of Υ⁻(z,x) depending on γ

γ
]−∞,−γ∗∗]	Repelling	Saddle point	Repelling
]−γ∗∗,−γ∗]	Repelling	Saddle point	Attracting
]−γ∗,0[	Repelling	Not real	Not real
]0,−γ∗[	Repelling	Not real	Not real
[−γ∗,γ∗∗[	Repelling	Saddle point	Attracting (γ∗≠γ∗∗)
]γ∗∗,+∞[	Repelling	Saddle point	Repelling

Proposition 1.Rational function Υ⁻(z,x) has different number of fixed points, (i∈{1,2,3,4,5}), depending on the value of parameter γ. In particular,

• (i) and , whose components correspond to the roots of polynomial , are superattracting fixed points, with independence of the value of γ. In case of γ=0, the rational operator is simplified and points and are the only fixed points of Υ⁻(z,x);
• (ii) when γ≠0, three roots of polynomial can be real: is real for any γ≠0 and it is a repelling strange fixed point; is real for γ∈]−∞,−γ^∗[∪[γ^∗,+∞[, being γ^∗≈3.38143, and it is a saddle strange fixed point in all its domain; finally, is real for γ∈]−∞,−γ^∗]∪]γ^∗,+∞[, and it is an attracting strange fixed point in ]−γ^∗∗,−γ^∗[∪]γ^∗,γ^∗∗[, being γ^∗∗≈4.4668, and repelling in γ∈]−∞,−γ^∗]∪]γ^∗∗,+∞[; in the boundaries of these intervals, it is a neutral or parabolic strange fixed point.

On the other hand, by applying family MMγ on polynomial , the resulting rational operator is

(14)

All the real fixed points of Υ⁺(z,x), if they exist, are strange fixed points, since the polynomial does not have real roots. In the following result, we establish the number and stability of the strange fixed points; moreover, the proof is omitted, as it is similar to that of Proposition 1.

Proposition 2.Rational function Υ⁺(z,x) has different number of fixed points, (i∈{1,2,3}), depending on the value of γ. In particular,

• (i) if γ=0, the rational operator is simplified and there are no strange fixed point;
• (ii) when γ≠0, three roots of polynomial can be real: is real for any γ≠0 and it is a repelling strange fixed point; and are real for γ∈]−γ^♯,0[∪]0,γ^♯[, being γ^♯≈4.62389, being their character repelling.

Finally, the rational function associated to family MMγ applied on is

(15)

and the following result can be proven in a similar way as the previous ones.

Proposition 3.Rational function Υ⁰(z,x) has an only attracting fixed point , whose components correspond to the roots of polynomial for any value of parameter γ. Moreover, it has a strange fixed point , being γ≠0, that is repelling.

Then, after explaining some fundamentals about the main dynamical representations for methods with memory, the basins of attraction corresponding to the attracting fixed points of operators Υ⁻, Υ⁺, and Υ⁰ are depicted.

4.2 Dependence on the initial estimations

The basins of attraction of the corresponding periodic points of a method are represented in the dynamical plane. Several implementations have been made, such as in the works of Chicharro et al20 and Varona.21 However, there are some modifications in the dynamical planes when we work with two-dimensional real dynamics instead of complex dynamics. For the first case, the current iterate x_k and the previous iterate x_k−1 are represented as the abscissae and the ordinates, respectively. Operator Υ(z,x) is studied on a mesh of values of z and x as initial guesses that correspond to the previous and the current iterates x_k−1 and x_k, respectively. The basin of each attracting point is depicted with a different nonblack color. Taking a point of the mesh as an initial estimation, we paint it with the color associated to the basin of the attracting fixed point which it falls in; otherwise, the starting point is plotted in black. As described in Section 4.1, the analysis is performed over the second-degree polynomial.

The dynamical planes of some methods belonging to family MMγ when it is applied on quadratic polynomials are shown in Figures 2-6. For each operator, different values of γ have been chosen by selecting regions where the number of strange fixed points varies. Orange color denotes convergence to for or to for . Blue color is used to denote the convergence to for . The attracting points are represented with white stars, whereas the strange fixed points with white squares. In addition, if there is convergence to a strange fixed point, the initial guess is depicted in purple. The starting points are selected over a mesh of 500×500 points in (z,x)∈[−20,20]×[−20,20]. We set the convergence of each initial iterate to an attracting point when the difference between its successive iterates and one of the attracting points is less than 10⁻⁶ being the number of iterations lower than 50.

Figures 2-4 represents some dynamical planes of Υ⁻(z,x). The values for the parameter γ∈{−5,3.5,3} have been chosen. Then, for γ=−5, the associated methods of MMγ have three strange fixed points , and for γ=3, there is only one strange fixed point, . As we can see, in these cases, there is full convergence to or . This is the expected behavior for Figures 2 and 3 as the strange fixed points are repelling or saddle (and there are no attracting periodic orbit). The strange fixed points are represented with white squares and laid in the Julia set, as it is expected.

The dynamical planes of family MMγ on for the values of the parameter considered are shown in Figure 5. For γ=−4, methods have two repelling strange fixed points . Moreover, in the second case, is a saddle point. It is observed that the dynamical planes are always completely black since the initial estimations do not reach to any real zero. This result agrees with the previous analysis, where it has been obtained that the only fixed points of the rational operator Υ⁺ where strange fixed points and they were not attracting in any case.

The application of MMγ on results in a dynamical plane whose behavior is the expected one since the strange point is always repelling and lay in the Julia set; in Figure 6, all the starting approximations in the Fatou set tend to the unique zero of the polynomial.

5 CONCLUSIONS

A new family of iterative methods with memory have been constructed starting from the classical Traub's method of third order of convergence. The proposed family has performed the inclusion of memory by including parameters in the iterative expression. The proper replacement of an accelerating parameter by using the expression of the error equation and the Newton's interpolation polynomial of second order has given a uniparametric family with order of convergence 3.30. Regarding the original iterative method, the value of the order of convergence has increased.

The study of the stability has been performed by means of dynamical analysis. Since the iterative scheme include memory, the complex dynamics has been replaced by the multidimensional real dynamics. Quadratic polynomials have been used as nonlinear functions for the analysis of the method. The choice of the polynomials is based on the different number of roots. For each particular case, we have chosen a particular value of the parameter to represent the basins of attraction of the associated method of the family.

In all cases, the stability has shown a good performance, as it is represented in the dynamical planes. In particular, for the polynomials that have real roots, every initial guess not only converges but also tends its orbit to the real root, showing that family MMγ behaves properly.