Applied Mathematics
Vol.05 No.19(2014), Article ID:51207,7 pages
10.4236/am.2014.519283

Two New Iterated Maps for Numerical Nth Root Evaluation

Charles Corrêa Dias1, Fernanda Jaiara Dellajustina2, Luciano Camargo Martins2*

1Department of Electrical Engineering, Universidade do Estado de Santa Catarina (UDESC), Joinville, Brazil

2Department of Physics, Universidade do Estado de Santa Catarina (UDESC), Joinville, Brazil   Received 15 August 2014; revised 10 September 2014; accepted 6 October 2014

ABSTRACT

In this paper we propose two original iterated maps to numerically approximate the nth root of a real number. Comparisons between the new maps and the famous Newton-Raphson method are carried out, including fixed point determination, stability analysis and measure of the mean convergence time, which is confirmed by our analytical convergence time model. Stability of solutions is confirmed by measuring the Lyapunov exponent over the parameter space of each map. A generalization of the second map is proposed, giving rise to a family of new maps to address the same problem. This work is developed within the language of discrete dynamical systems.

Keywords:

Iterated Map, Nth Root of a Real Number, Numerical Method, Newton-Raphson Method, Dynamical System 1. Introduction

Recent applications of iterated maps in numerical analysis have been found in literature, using and extending the techniques of dynamical systems to the study of numerical algorithms and number theory  - . Application in technology and hardware devices are also frequent nowadays  -  .

We propose and study in this work two new methods for numerical root approximations, both of which based on iterated maps. In the following sections we present a detailed study of each map, their fixed points and stability, the occurrence of bifurcations and chaotic behavior.

Some common tools of nonlinear dynamics   are used to the study of the orbits, i.e., the numerical time series obtained for each map are investigated. The numerical approximations to solve the general equation , where and are obtained, but the validity of the results can be extended to .

In Section 2 we present a new map proposed by one of us (C. C. Dias), named as First Dias Map (FDM), showing the existence of a fixed point for roots in the range , and that this fixed point corresponds exactly to .

In Section 3, we generalize the FDM by adding a new parameter for studying the stability of its fixed point by defining a new class of maps called Weighted Average Map (WAM). For this class of maps, we investigate the dependence of the fixed point corresponding to the nth root of over the parameter space .

Finally, in Section 4, we measure and compare the Mean Convergence Time (MCT) for all the studied maps, for and , varying over an uniform grid of initial conditions and computing the average amount of iterations to converge to the root within the standard numerical double precision. An analytical model is proposed and used to confirm the numerical results of MCT with the analytical convergence time (ACT) for the WAM.

2. The First Dias Map (FDM)

The map which we will study now was created by Charles C. Dias to extract real roots of numbers numbers, by solving the equation . The proposed map is one-dimensional and is defined as (1.1)

Comparing this with the Newton-Raphson Method (NRM) equation and Babylonian Method (BABM)  noticed that this statement is a mixture of both, and the FDM is an arithmetic average between the linear and nonlinear terms in Equation (1.1), and can be used to approximate the nth root of for, as we shall see. Outside this interval of, this map presents chaotic dynamics through after entering a bifurcation cascade, whose roots having no longer relationship to the nth root of.

The base function that appears in the iterated map defined by Equation (1.1) can be derived dividing by, for, leading to

(1.2)

and adding at both sides, and dividing it by 2, we recover functional form of Equation (1.1).

2.1. Geometrical Construction

To construct geometrically the FDM time series, the first step is to find the auxiliary equations of the lines (see Figure 1), writing their slopes. From this figure, and, and the slopes

(1.3)

that for are.

Knowing that their linear coefficients are all, then all the auxiliary lines pass through the point, we obtain the working lines and the auxiliary points, the intersections points of the working lines with the -axis, are

(1.4)

and taking the arithmetic mean between the auxiliary points and the points we recover the original FDM equation (Equation (1.1)).

Figure 2(a) shows the cobweb for the FDM time series for and, and Table 1 (top) shows time series used in this figure. In this example, the convergence to the root is achieved after only five steps, considering the standard double precision, and is exactly the same time series of NRM for these parameters. Figure 2(b)

Figure 1. The FDM schematic geometrical path construction.

(a) (b)

Figure 2. The FDM cobwebs for: (a); (b).

shows a numerical development of the FDM series for the parameters and, based on the time series shown in Table 1 (bottom), where the convergence to the root occurs after 27 steps. Some intermediary time steps are omitted in this table.

2.2. Fixed Point and Stability Analysis

Solving we find the FDM fixed point to be. Applying the stability criterion  , to the

map function, whose derivative is we obtain,

and solving the last equation we have the range of parameter where the fixed point of the map is stable.

2.3. Numerical Results

The FDM time series have different dynamics depending on the parameters, presenting a fixed point, periodicity or chaos, as occurs to the logistic map  .

To measure the rate of divergent orbits, i.e., the sensitive dependence on initial conditions, we can use is characteristic Lyapunov exponent. From Figure 3(a) we see that, at, FDM enters a bifurcation cascade, therefore its fixed point is no longer stable. In the white to gray regions the exponent is negative indicating that for this region of parameters the FDM not is chaotic, and at the black stripes the Lyapunov exponent

Table 1. FDM time series for for (top) and (bottom).

goes to zero signing the period bifurcations. The yellow to red regions indicate the a positive Lyapunov exponents, the signature of chaos.

The FDM bifurcation diagram, discarded a transient of 103 iterations and plotted the next 500 values of, is depicted in Figure 3(b). The values of studied are uniformly distributed in a grid of 600 points in the interval. Also plotted over the bifurcation diagram is the exact root, the fixed point of the map, plotted in black.

We also study numerically the FDM return diagrams for different values of the parameter, for and, as seen in Figure 3(c) and Figure 3(d), respectively.

3. The Weighted Average Map (WAM)

Instead of adding, if a more general term is added in Equation (1.2), we get a new map (WAM) that depends on parameters, and. The new parameter is a positive real number and corresponds to the weight of the linear term of the map. This term is directly linked to the parameter, since for each value of there is a minimum value of for the fixed point to be stable, as we shall see.

Adding to both sides of Equation (1.2) we gain

(1.5)

and after collecting and dividing by it leads to the new map (WAM),

(1.6)

and solving its fixed point equation we obtain the expected value.

3.1. Fixed Point and Stability Analysis

Applying the stability criterion  , i.e., , to the map function whose derivative is and solving this inequality we obtain to

guarantee fixed point stability, and Figure 4 shows the line corresponding to this condition, below which the fixed point is unstable. As is increased the value of should also be increased to avoid the unstable region, where the time series do not converges to the fixed point.

3.2. WAM Subclasses and Hierarchy

A special subclass of WAM is FDM, when, so that the fixed point on the map according to Figure 4, is stable in the range for, thus in accordance with the stability analysis the fixed point loses stability

(a) (b)(c) (d)

Figure 3. (a) FDM Lyapunov exponent over the parameter space; (b) the bifurcation diagram showing the stable fixed point for; return diagrams for and: (c); (d).

(a) (b)

Figure 4. For, (a) the numerical results of WAM MCT (n, p) and (b) the analytical model for WAM ACT (n, p).

at. Other very important subclass is NRM, for, so that the weight is chosen within the stable region.

For NRM, the derivative of the mapping function at the fixed point is null, satisfying the stability criterion and resulting in the most efficient rate of convergence of the time series near the fixed point. When the starting point is chosen far away from the fixed point, we observe numerically that the initial rate of convergence is greater for FDM, in general. Finally, there is a third subclass of WAM, the Babylonian square root method (BABM), for and, the oldest and perhaps the most efficient known method to solve the equation. At this parameters, WAM reduces itself to BABM, therefore the same occurs with FDM and NRM. The hierarchy of WAM subclasses are shown in Figure 5.

From the definition of the Lyapunov characteristic exponent for a unidimensional map we conclude that the derivative of the mapping function at the fixed point defines the rate of convergence of its time series, discarded the transient. For WAM, it is easy to show that, so that this derivative assumes the value when (FDM) and is zero only if (NRM or BABM, if). In Figure 3(c) we observe that, for FDM reduces to NRM, and in Figure 3(d), we observe that.

4. Mean Convergence Time (MCT)

This section reports the numerical results for the mean convergence time (MCT) for NRM, FDM and WAM, based on the average number of iterates to converge within different precisions, from single to double. For this, we varied on a uniform grid with 103 points in the interval, varying the initial condition on a second uniform grid with points, whose limits are given by a maximum relative difference of 25% around the exact value of the root of at each point. Using this schema, the MCT is computed for cubic roots, and for WAM we set. Figures 6(a)-(c) show the numerical results.

In Figure 6(a) we see that the NRM MCT is close to 4, which means that after 4 iterations, on average, there has been convergence to the root. From this figure, we conclude that FDM is around 10 times slower than NRM, and WAM is around has twice the speed of FDM. In this test, the most efficient is NRM, with the lowest MCT.

Both NRM and FDM belong to the same WAM family, as discussed in Section 3, and the stability of the fixed point of WAM depends on the parameters and. Changing the parameter of WAM we get a new map subclass, for example, for have the FDM. From these fact, we tried to detect numerically the

Figure 5. Hierarchy of the WAM subclasses.

(a) (b) (c)

Figure 6. Numerical results of MCT for cubic roots calculation with different precisions from to for (a) NRM; (b) FDM and (c) WAM with.

optimal value of the parameter, to minimize the ACT over the whole WAM family. For this we used a FORTRAN program to measure extensively the WAM MCT varying parameters on a uniform grid of points, for a radicand. The result for is shown in Figure 4(a). The region in gray corresponds to unstable fixed point map WAM, as found in Section 1.3. The other colors seen in the graph are the regions of stability of the fixed point. For best visualization the MCT scale of this figure is truncated at a maximum value of 20, and higher values as inked light gray.

We can see in Figure 4(a) that, as we approach the line that corresponds to the weighting term, NRM shows the minimum MCT over this line and therefore the most efficient of all studied maps is the NRM.

Summarizing the key information about NRM, FDM and WAM, with the numerical results for the MCT within double precision for these maps, for the parameters and, as shown in Table 2.

Analytical Convergence Time Model

The Lyapunov characteristic exponent for a unidimensional map usually defined by

can be approximate by since the derivative of the mapping function at the fixed point defines the rate of convergence of its time series, after discarded the transient.

For WAM, it is easy to show that, so that this derivative assumes the value when (FDM) and is zero only if (NRM or BABM, if). In Figure 3(c) we observe that, for FDM reduces to NRM, and in Figure 3(d),.

Using the original Lyapunov’s idea, the characteristic exponent measures the average rate of convergence between two solutions separated by an initial distance, that is the case of time series dominated by a fixed point. For this orbits, the distance after iterates is so that, if we assume that one orbit is initialized at and other at, i.e., the initial distance is unitary between orbits, we can use last equation to measure the error found in the second orbit, the root to be approximated. Within the standard double precision, the maximum error is of order, where is the number of decimal significants, typically places.

Applying the natural logarithm to both sides of the above equation we have for the number of

iterations needed to reduces the error in the second orbit to. In the same manner we defined MCT, we define now the analytical convergence time (ACT), estimated by

(1.7)

valid for any fixed point of a unidimensional map, where the approximated was used.

Applying this model to our more general map (WAM), we have

(1.8)

of the parameters and. To double precision this approximated model function is plotted in Figure 4(b), that is remarkably very close to the numerical version plotted in Figure 4(a). Both figures uses the same color palette and truncated maximum, for better comparisons.

Table 2. MCT numerical results for NRM, FDM and WAM maps.

5. Conclusions

In the study of iterated maps to extract the real root of real numbers we have applied some common tools from nonlinear dynamics that allowed us to predict the fixed point of the studied maps associated with the nth root of, and their stabilities could be analyzed in details.

We conclude, through the geometric argument used to recover the original analytical form of FDM, that both NRM and FDM can be reduced to averages between two terms, one linear and other nonlinear. From this observation, we generalize the original FDM idea to a new family of maps on which we add a new parameter, whose value defines the stability of the map, the WAM. We show that FDM and NRM belong to this family of maps, being FDM recover when and NRM when.

The mean convergence time (MCT) numerical results indicate that NRM is the most efficient subclass of the more general weighted average map (WAM) proposed in this work, as pointed out in Figure 4(a), over the line. The analytical model for ACT is in complete agreement with the numerical results for WAM, the most general class of map studied. The model presented in Equation 1.7 is general, and can be adapted to any unidimensional map to study its fixed point attractor.

The main results of this work are obtained for, but their generalization is straightforward over the complex set.

Acknowledgements

This work was partially supported by the Brazilian agency Conselho Nacional de Desenvolvimento Cientfico e Tecnológico―CNPq and Universidade do Estado de Santa Catarina―UDESC.

References

1. Faber, X. and Voloch, J.F. (2011) On the Number of Places of Convergence for Newton’s Method over Number Fields. Journal de Theorie des Nombres de Bordeaux, 23, 387-401.
2. Grau-Sánchez, M. and Daz-Barrero, J.L. (2011) A Technique to Composite a Modified Newton’s Method for Solving Nonlinear Equations. ArXiv e-prints.
3. Pan, B., Cheng, P. and Xu, B. (2005) In-Plane Displacements Measurement by Gradient-Based Digital Image Correlation. SPIE Proceedings, 5852, 544-551.
4. Amin, A.M., Thakur, R., Madren, S., Chuang, H.-S., Thottethodi, M., Vijaykumar, T., Wereley, S.T. and Jacobson, S.C. (2013) Software-Programmable Continuous-Flow Multi-Purpose Lab-on-a-Chip. Microfluidics and Nanofluidics, 15, 647-659. http://dx.doi.org/10.1007/s10404-013-1180-2
5. Mungan, C.E. and Lipscombe, T.C. (2012) Babylonian Resistor Networks. European Journal of Physics, 33, 531. http://dx.doi.org/10.1088/0143-0807/33/3/531
6. Senthilpari, C., Mohamad, Z.I. and Kavitha, S. (2011) Proposed Low Power, High Speed Adder-Based 65-nm Square Root Circuit. Microelectronics Journal, 42, 445-451. http://dx.doi.org/10.1016/j.mejo.2010.10.015
7. Sun, T., Tsuda, S., Zauner, K.-P. and Morgan, H. (2010) On-Chip Electrical Impedance Tomography for Imaging Biological Cells. Biosensors and Bioelectronics, 25, 1109-1115. http://dx.doi.org/10.1016/j.bios.2009.09.036
8. Ausloos, M. and Dirickx, M. (2005) The Logistic Map and the Route to Chaos: From the Beginnings to Modern Applications. Springer, New York.
9. Eve, J. (1963) Starting Approximations for the Iterative Calculation of Square Roots. The Computer Journal, 6, 274- 276. http://dx.doi.org/10.1093/comjnl/6.3.274
10. Dellajustina, F.J. and Martins, L.C. (2014) The Hidden Geometry of the Babylonian Square Root Method. Accepted by Applied Mathematics, August.
11. Lyapunov, A.M. (1992) The General Problem of the Stability of Motion. International Journal of Control, 55, 531- 534. http://dx.doi.org/10.1080/00207179208934253
12. Schuster, H.G. and Just, W. (2005) Deterministic Chaos: An Introduction. 4th Edition, John Wiley & Sons, New York. http://dx.doi.org/10.1002/3527604804

NOTES

*Corresponding author.