Newton’s method and high-order algorithms for the n-th root computation

François Dubeau

Département de mathématiques Faculté des sciences, Université de Sherbrooke 2500, boul. de l’Université, Sherbrooke (Qc), Canada, J1K 2R1 francois.dubeau@usherbrooke.ca

Abstract. We analyze two modifications of the Newton’s method to accelerate the convergence of the n-th root computation of a strictly positive real number. From these modifications, we can define new algorithms with prefixed order of convergence p ∈ ℕ, p ≥ 2. Moreover an affine combination of the two modified methods, depending on one parameter, leads to a family of methods of order p, but of order p + 1 for a specific value of the parameter.

AMS Subject Classification : 65-01, 11B37, 65B99, 65D99, 65H05.

Key Words : n-th root, Newton’s method, high-order method.

1. Introduction

The computation of the n-th root r^{1/n} of a strictly positive real number r is an old problem [1, 14]. Recently several authors have suggested high-order methods for the computation of r^{1/2}. In [10] and [18], continued fraction expansions are used to derive such methods. In [12], methods similar to those presented in [18] are obtained as a special case of a determinantal family of root-finding methods [11]. Also, methods based on a modification of the Newton’s method are obtained in [9]. For the computation of the n-th root r^{1/n}, general high-order methods can be derived from the application of the Newton’s method to an appropriate modified function [3]. Also third and fourth order methods are presented in [8]. Finally, using combinations of basic functions identified for methods proposed in [3] and [9], new high-order methods are derived for the computation of r^{1/2} in [15] .

In this paper we consider extensions of the Newton’s method applied to the function

(1.1)  f(x) = x^{n} − r

to find the n-th root of r. In order to accelerate the convergence, we consider the following two possibilities. As suggested in [6], [4], the first possibility use a modification of the function f(x) and then apply the Newton’s method on the modified function. In fact we consider F (x) = g(x)f(x) and then consider the iteration

(1.2)  x_{k+1} = Φ_{0}(x_{k}) = x_{k} − \frac{F (x_{k})}{F^{(1)}(x_{k})}.

This approach, used in [3], is summarized in Section 2. The second possibility is to modify the Newton’s method by changing the step size of the correction when we apply it to f(x). Hence we look for a good choice of G(x) and we consider the iteration

(1.3)  x_{k+1} = Φ_{1}(x_{k}) = x_{k} − G(x_{k})\frac{f(x_{k})}{f^{(1)}(x_{k})}.

This approach was used in [9] for the square-root computation and is extended in Section 3 to the computation of the n-th root. Finally in Section 4 we consider combinations of the p-th order methods obtained in Sections 2 and 3 of the form

(1.4)  x_{k+1} = Φ_{λ}(x_{k}) = (1 − λ)Φ_{0}(x_{k}) + λΦ_{1}(x_{k}).

We obtain new p-order methods for any values of the parameter λ except for a specific value for which the new method is of order p + 1.

2. Newton’s method on F (x) = g(x)f(x).

To get high order method for finding r^{1/n}, we try to find a function g_{p}(x) such that

F_{p}(x) = g_{p}(x)f(x) = g_{p}(x) (x^{n} − r)

satisfies the assumptions of following result about Newton’s method.

Theorem 2.1. [2],[6],[17] Let p be an integer ≥ 2 and let F_{p}(x) be a regular function such that F_{p}(α) = 0, F_{p}^{(1)}(α) ≠ 0, F_{p}^{(j)}(α) = 0 for j = 2, …, p − 1, and F_{p}^{(p)}(α) ≠ 0. Then the Newton’s method applied to the equation F_{p}(x) = 0 generates a sequence {x_{k}}_{k=0}^{+∞} where

x_{k+1} = Φ_{0,p}(x_{k}) = x_{k} − \frac{F_{p}(x_{k})}{F_{p}^{(1)}(x_{k})} (k = 0, 1, 2, …)

which converges to α for a given x_{0} sufficiently close to α. Moreover, the convergence is of order p, and the asymptotic constant is

K_{0,p}(α) = lim_{k→+∞} \frac{x_{k+1} − α}{(x_{k} − α)^{p}} = \frac{p − 1}{p!} \frac{F_{p}^{(p)}(α)}{F_{p}^{(1)}(α)}. □

One such function g_{p}(x) suggested in [3] is

(2.1)  g_{p}(x) = ∑_{i=1}^{p−1} a_{i}(x^{n} − r)^{i−1} = ∑_{i=1}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) \frac{(x^{n} − r)^{i−1}}{r^{i}} .

where

(2.2)  (\begin{matrix}1/n \\ i \end{matrix}) = \{ \begin{matrix}1 & for & i = 0, \\ \frac{\frac{1}{n}(\frac{1}{n} −1)···(\frac{1}{n} −(i−1))}{i!} & for & i ≥ 1. \end{matrix}

We have the following result.

Theorem 2.2. [3] Let n be an integer ≥ 2, p be an integer ≥ 2, and

(2.3)  F_{p}(x) = ∑_{i=1}^{p−1} a_{i}(x^{n} − r)^{i}

where a_{i} = \frac{1}{r^{i}} (\begin{matrix}1/n \\ i \end{matrix}) for i = 1, ..., p − 1. Then

(2.4)  F_{p}(r^{1/n}) = 0,
(2.5)  F_{p}^{(1)}(r^{1/n}) = r^{−1/n},
(2.6) F_{p}^{(j)}(r^{1/n}) = 0 for j = 2, …, p − 1,
(2.7)  F_{p}^{(p)}(r^{1/n}) = −n^{p}p! (\begin{matrix}1/n \\ p \end{matrix}) r^{− \frac{p}{n}} ,
(2.8)  F_{p}^{(p+1)}(r^{1/n}) = (p + 2 − np)\frac{p − 1}{2}n^{p}p! (\begin{matrix}1/n \\ p \end{matrix}) r^{− \frac{p+1}{n}} .

Proof. We use the identity

(2.9)  Q_{p}(y) = F_{p}((y + r)^{1/n}) = ∑_{i=1}^{p−1} a_{i}y^{i}

to find F_{p}^{(j)}(r^{1/n}) for j = 0, ..., p + 1. It is clear that F_{p}(r^{1/n}) = 0. For j ≥ 1, we have

F_{p}^{(j)}((y + r)^{1/n}) = ∑_{k=1}^{j} F_{p}^{(k)}((y + r)^{1/n})G_{k,j}(y),

where the G_{k,j}(y) are regular functions of y near 0. More precisely, we have

G_{1,j}(y) = \frac{d^{j}}{dy^{j}} (y + r)^{1/n},
G_{j−1,j}(y) = γ_{j}[\frac{d}{dy} (y + r)^{1/n}]^{j−2} \frac{d^{2}}{dy^{2}} (y + r)^{1/n},
G_{j,j}(y) = [\frac{d}{dy} (y + r)^{1/n}]^{j},

where γ_{1} = 0 and γ_{j+1} = γ_{j} + j = \frac{j(j+1)}{2} for j ≥ 2. Since

Q_{p}^{(j)}(y) = \{ \begin{matrix}∑_{i=j}^{p−1} a_{i} \frac{i!}{(i−j)!}y^{i−j} & for j = 1, ..., p − 1 \\ 0 & for j ≥ p, \end{matrix}

We obtain the result by setting y = 0 recursively for j = 1, ..., p + 1. □

It follows that the sequence {x_{k}}_{k=0}^{+∞} generated by : x_{0} given sufficiently close to r^{1/n}, and

(2.10)  x_{k+1} = Φ_{0,p}(x_{k})
(2.11)  = x_{k} − \frac{F_{p}(x_{k})}{F_{p}^{(1)}(x_{k})}
(2.12)  = x_{k} − \frac{(x_{k}^{n} − r) ∑_{i=1}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) (\frac{x_{k}^{n}−r}{r} )^{i−1}}{nx_{k}^{n−1} ∑_{i=1}^{p−1} i (\begin{matrix}1/n \\ i \end{matrix}) (\frac{x_{k}^{n}−r}{r} )^{i−1}}

for k = 0, 1, 2, …, converges to r^{1/n}. Moreover, the convergence is of order p, and the asymptotic constant is

(2.13)  K_{0,p}(r^{1/n}) = lim_{k→+∞} \frac{x_{k+1} − r^{1/n}}{(x_{k} − r^{1/n})^{p}} = −(p − 1)n^{p} (\begin{matrix}1/n \\ p \end{matrix}) r^{− \frac{p−1}{n}} .

3. Modified step size for the Newton’s method applied on f(x).

To get high order method for finding r^{1/n}, we try to find a function G(x) such that the modified Newton’s method given by

x_{k+1} = x_{k} − G(x_{k})\frac{f(x_{k})}{f^{(1)}(x_{k})}

satisfies the assumptions of following result about fixed-point method.

Theorem 3.1. [13], [16] Let p be an integer ≥ 2 and let Φ(x) be a regular function such that Φ(α) = α, Φ^{(j)}(α) = 0 for j = 1, …, p − 1, and Φ^{(p)}(α) ≠ 0. Then the sequence {x_{k}}_{k=0}^{+∞} generated by x_{k+1} = Φ(x_{k}) for k = 0, 1, 2, …, converges to α for a given x_{0} sufficiently close to α. Moreover, the convergence is of order p, and the asymptotic constant is

K_{p}(α) = lim_{k→+∞} \frac{x_{k+1} − α}{(x_{k} − α)^{p}} = \frac{Φ^{(p)}(α)}{p!}. □

To determine G(x) we start from the Taylor’s expansion of f(x) = x^{n} −r around x evaluated at r^{1/n}

(3.1)  0 = f(r^{1/n}) = f(x) + ∑_{i=1}^{n} \frac{f^{(i)}(x)}{i!}(r^{1/n} − x)^{i}.

For any x we look for a correction Δx such that x + Δx = r^{1/n} of the form

(3.2)  Δx = r^{1/n} − x = −G(x)\frac{f(x)}{f^{(1)}(x)}.

Using (3.1) and (3.2), we get

0 = f(x) + ∑_{i=1}^{n} (\begin{matrix}n \\ i \end{matrix}) x^{n−i}( − G(x)\frac{f(x)}{f^{(1)}(x)})^{i}

because

f^{(i)}(x) = \frac{n!}{(n − i)!}x^{n−i}

for i = 1, 2, …, n. Following [5], we define the two functions

(3.3)  u(x) = \frac{f(x)}{f^{(1)}(x)}

and

(3.4)  t(x) = \frac{f(x)f^{(2)}(x)}{(f^{(1)}(x))^{2}}.

These functions verify u^{(1)}(x) = 1 − t(x). Also because the special form of f(x), we also have

(3.5)  u(x) = \frac{x}{n − 1}t(x),

(3.6)  t(x) = \frac{n − 1}{n}(1 − \frac{r}{x^{n}} ),

and

(3.7)  t^{(1)}(x) = \frac{n − 1}{x}(1 − \frac{n}{n − 1}t(x)).

Using (3.5), we get

0 = −r + x^{n} ∑_{i=0}^{n} (\begin{matrix}n \\ i \end{matrix}) ( − G(x)\frac{t(x)}{n − 1})^{i}.
0 = −r + x^{n}(1 − G(x)\frac{t(x)}{n − 1})^{n}.

It follows from (3.6) that

(1 − G(x)\frac{t(x)}{n − 1})^{n} = \frac{r}{x^{n}} = 1 − \frac{n}{n − 1}t(x),

and

G(x) = \frac{1 − (1 − \frac{n}{n−1}t(x))^{1/n}}{\frac{1}{n−1}t(x)} .

Obviously it is a theoretical result because it requires the computation of the n-th root of (1 − \frac{n}{n−1}t(x)). We can verify that with this G(x), if we start with any x value we get α in one step because

x − G(x)u(x) = x − \frac{1 − (1 − \frac{n}{n−1}t(x))^{1/n}}{\frac{1}{n−1}t(x)} u(x)
= x − x(1 − (1 − \frac{n}{n − 1}t(x))^{1/n})
= x(1 − \frac{n}{n − 1}t(x))^{1/n}
= x(\frac{r}{x^{n}} )^{1/n}
= r^{1/n}.

To obtain a numerical method we use the MacLaurin’s expansion of (1 + x)^{1/n}

(1 + x)^{1/n} = ∑_{i=0}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) x^{i} + (\begin{matrix}1/n \\ p \end{matrix}) (1 + θ(x)x)^{\frac{1}{n} −p}x^{p}

where θ(x) ∈ (0, 1). For p ≥ 2 we take

(3.8)  G_{p}(x) = \frac{1 − ∑_{i=0}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) ( − \frac{n}{n−1}t(x))^{i}}{\frac{1}{n−1}t(x)} ,

and define

(3.9)  Φ_{1,p}(x) = x − G_{p}(x)u(x) = x − G_{p}(x)\frac{x}{n − 1}t(x).

Then we have the following result.

Theorem 3.2. Let f(x) and t(x) given by (1.1) and (3.4). Let n be an integer ≥ 2, p be an integer ≥ 2, and let Φ_{1,p}(x) be defined by

(3.10)  Φ_{1,p}(x) = x ∑_{i=0}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) ( − \frac{n}{n − 1}t(x))^{i}.

Then

(3.11)  Φ_{1,p}(r^{1/n}) = r^{1/n},
(3.12)  Φ_{1,p}^{(j)}(r^{1/n}) = 0  for j = 1, ..., p − 1,
(3.13)  Φ_{1,p}^{(p)}(r^{1/n}) = (−1)^{p}n^{p}p! (\begin{matrix}1/n \\ p \end{matrix}) r^{− \frac{p−1}{n}} ,
(3.14)  Φ_{1,p+1}^{(p+1)}(r^{1/n}) = (−1)^{p} \frac{p(p − 1)}{2}n^{p}(n + 1)p! (\begin{matrix}1/n \\ p \end{matrix}) r^{−p/n}.

Proof. Since t(r^{1/n}) = 0, we have Φ_{1,p}(r^{1/n}) = r^{1/n}. Also, using (3.7) and the identity

(3.15)  (\begin{matrix}1/n \\ i + 1 \end{matrix}) = (\begin{matrix}1/n \\ i \end{matrix}) \frac{\frac{1}{n} − i}{i + 1},

we get

Φ_{1,p}^{(1)}(x) = ∑_{i=0}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) ( − \frac{n}{n − 1}t(x))^{i}

+x ∑_{i=1}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) i( − \frac{n}{n − 1}t(x))^{i−1}( − \frac{n}{n − 1}t^{(1)}(x))

= ∑_{i=1}^{p−2} [ (\begin{matrix}1/n \\ i \end{matrix}) (1 − ni) − (\begin{matrix}1/n \\ i + 1 \end{matrix}) n(i + 1)]( − \frac{n}{n − 1}t(x))^{i}

+ (\begin{matrix}1/n \\ p − 1 \end{matrix}) (1 − n(p − 1))( − \frac{n}{n − 1}t(x))^{p−1}

= np (\begin{matrix}1/n \\ p \end{matrix}) ( − \frac{n}{n − 1}t(x))^{p−1}.

Hence, because t(r^{1/n}) = 0 and p ≥ 2, it follows that Φ_{1,p}^{(1)}(r^{1/n}) = 0. For j = 2, ..., p, we have

(3.16)  Φ_{1,p}^{(j)}(x) = (t(x))^{p−(j−2)}g_{j}(x)

+ (−1)^{p−1} \frac{(j − 1)(j − 2)}{2} \frac{n^{p}}{(n − 1)^{p−1}} \frac{p!}{(p − (j − 1))!} (\begin{matrix}1/n \\ p \end{matrix}) (t(x))^{p−(j−1)}(t^{(1)}(x))^{j−3}t^{(2)}(x)

+ (−1)^{p−1} \frac{n^{p}}{(n − 1)^{p−1}} \frac{p!}{(p − j)!} (\begin{matrix}1/n \\ p \end{matrix}) (t(x))^{p−j}(t^{(1)}(x))^{j−1}

where the g_{j}(x) are regular functions of x near r^{1/n}. It follows that Φ_{1p}^{(j)}(r^{1/n}) = 0 for j = 2, ..., p − 1, and

(3.17)  Φ_{1,p}^{(p)}(r^{1/n}) = (−1)^{p−1}n^{p}p! (\begin{matrix}1/n \\ p \end{matrix}) r^{− \frac{p−1}{n}} .

Finally, taking the derivative of (3.16) for j = p, we obtain

Φ_{1,p}^{(p+1)}(x) = t(x)g_{p+1}(x)+(−1)^{p−1} \frac{p(p − 1)}{2} \frac{n^{p}}{(n − 1)^{p−1}} p! (\begin{matrix}1/n \\ p \end{matrix}) (t^{(1)}(x))^{p−2}t^{(2)}(x)

where the g_{p+1}(x) is regular functions of x near r^{1/n}. The result follows for Φ_{1,p}^{(p+1)}(r^{1/n}) because t^{(1)}(r^{1/n}) = (n − 1)r^{−1/n} and t^{(2)}(r^{1/n}) = −(n − 1)(n + 1)r^{−2/n}. □

Then the sequence {x_{k}}_{k=0}^{+∞} generated by : x_{0} given sufficiently close to r^{1/n}, and

(3.18)  x_{k+1} = Φ_{1,p}(x_{k})
(3.19)  = x_{k} ∑_{i=0}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) ( − \frac{n}{n − 1}t(x_{k}))^{i}

for k = 0, 1, 2, …, converges to r^{1/n}. Moreover, the convergence is of order p, and the asymptotic constant is

(3.20)  K_{1,p}(r^{1/n}) = \frac{Φ_{1,p}^{(p)}(α)}{p!} = (−1)^{p−1}n^{p} (\begin{matrix}1/n \\ p \end{matrix}) r^{− \frac{p−1}{n}} .

Moreover if x_{k} > r^{1/n} we have

x_{k+1} − r^{1/n} = Φ_{1,p}(x_{k}) − Φ_{1p}(r^{1/n})
= Φ_{1,p}^{(1)}(ξ)
= (−1)^{p−1} \frac{n^{p}}{(n − 1)^{p−1}} (\begin{matrix}1/n \\ p \end{matrix}) (t(ξ))^{p−1}
> 0,

since ξ ∈ (r^{1/n}, x_{k}), t(ξ) = \frac{n−1}{ξ}u(ξ) > 0 and (−1)^{p−1} (\begin{matrix}1/n \\ p \end{matrix}) > 0. Also

x_{k+1} − x_{k} = x_{k} ∑_{i=1}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) ( − \frac{n}{n − 1}t(x_{k}))^{i}

= x_{k} ∑_{i=1}^{p−1}(−1)^{i}(\frac{n}{n − 1})^{i} (\begin{matrix}1/n \\ i \end{matrix}) (t(x_{k}))^{i}
< 0,

since t(x_{k}) = \frac{n−1}{x_{k}}u(x_{k}) > 0 and (−1)^{i} (\begin{matrix}1/n \\ i \end{matrix}) < 0. Then for any x_{0} > r^{1/n}, the

sequence {x_{k}}_{k=0}^{+∞} monotonically decreases and converges to r^{1/n}.

4. Higher order methods.

In the preceding two sections we have obtained two families of methods for the computation of r^{1/n}. In this section we combine the two families to get new higher order methods.

We start with two p-order methods

x_{k+1} = Φ_{0,p}(x_{k}) = x_{k} − \frac{(x_{k}^{n} − r) ∑_{i=1}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) (\frac{x_{k}^{n}−r}{r} )^{i−1}}{nx_{k}^{n−1} ∑_{i=1}^{p−1} i (\begin{matrix}1/n \\ i \end{matrix}) (\frac{x_{k}^{n}−r}{r} )^{i−1}} ,

and

x_{k+1} = Φ_{1,p}(x_{k}) = x_{k} ∑_{i=0}^{p−1} (\begin{matrix}1/n \\ i \end{matrix}) ( − \frac{n}{n − 1}t(x_{k}))^{i},

and consider an affine combination

Φ_{λ,p}(x) = (1 − λ)Φ_{0,p}(x) + λΦ_{1,p}(x).

This method converges to r^{1/n} if x_{0} is given sufficiently close to r^{1/n} because Φ_{λ,p}(r^{1/n}) = r^{1/n} and

Φ_{λ,p}^{(1)}(r^{1/n}) = (1 − λ)Φ_{0,p}^{(1)}(r^{1/n}) + λΦ_{1,p}^{(1)}(r^{1/n}) = 0.

We obtain a method of order p with an asymptotic constant given by

K_{λ,p}(r^{1/n}) = (1 − λ)K_{0,p}(r^{1/n}) + λK_{1,p}(r^{1/n}).

From (2.13) and (3.20), we get

K_{λ,p}(r^{1/n}) = [(−1)^{p}(p − 1) + λ(1 − (−1)^{p}(p − 1))](−1)^{p−1}n^{p} (\begin{matrix}1/n \\ p − 1 \end{matrix}) r^{− \frac{p−1}{n}} .

This asymptotic constant can be made arbitrary small for p > 2, and is 0 for

λ = λ_{p} = \frac{(−1)^{p+1}(p − 1)}{1 + (−1)^{p+1}(p − 1)}.

Using Taylor expansions for F_{p}(x_{k+1}), F_{p}^{(1)}(x_{k+1}), and Φ_{1,p}^{(1)}(x_{k+1}) around r^{1/n}, we have

x_{k+1} − r^{1/n} = Φ_{λ,p}(x_{k}) − Φ_{λ,p}(r^{1/n})
= (1 − λ)[(x_{k} − r^{1/n}) − \frac{F_{p}(x_{k})}{F_{p}^{(1)}(x_{k})}] + λ[Φ_{1,p}(x_{k}) − Φ_{1,p}(r^{1/n})]

= [(1 − λ)\frac{p − 1}{p!} \frac{F_{p}^{(p)}(r^{1/n})}{F_{p}^{(1)}(r^{1/n})} + λ\frac{Φ_{1,p}^{(p)}(r^{1/n})}{p!}](x_{k} − r^{1/n})^{p}

+(1 − λ)F_{p}^{(p)}(r^{1/n})\frac{p − 1}{p!}[\frac{1}{F_{p}^{(1)}(x_{k})} − \frac{1}{F_{p}^{(1)}(r^{1/n})}](x_{k} − r^{1/n})^{p}

+[(1 − λ)\frac{(p + 1)F_{p}^{(p+1)}(ξ′) − F_{p}^{(p+1)}(ξ′′)}{(p + 1)!F_{p}^{(1)}(x_{k})} + λ\frac{Φ_{1,p}^{(p+1)}(ξ)}{(p + 1)!}](x_{k} − r^{1/n})^{p+1}

= [(1 − λ)K_{0,p}(r^{1/n}) + λK_{1,p}(r^{1/n})](x_{k} − r^{1/n})^{p}

+(1 − λ)F_{p}^{(p)}(r^{1/n})\frac{p − 1}{p!}[\frac{1}{F_{p}^{(1)}(x_{k})} − \frac{1}{F_{p}^{(1)}(r^{1/n})}](x_{k} − r^{1/n})^{p}

+[(1 − λ)\frac{(p + 1)F_{p}^{(p+1)}(ξ′) − F_{p}^{(p+1)}(ξ′′)}{(p + 1)!F_{p}^{(1)}(x_{k})} + λ\frac{Φ_{1,p}^{(p+1)}(ξ)}{(p + 1)!}](x_{k} − r^{1/n})^{p+1}

where ξ, ξ′ and ξ′′ are between x_{k} and r^{1/n}.

For λ = λ_{p}, it follows that the method is of order p + 1 and its asymptotic constant is

K_{λ_{p},p+1}(r^{1/n}) = [(1 − λ_{p})\frac{pF_{p}^{(p+1)}(r^{1/n})}{(p + 1)!F_{p}^{(1)}(r^{1/n})} + λ_{p} \frac{Φ_{1,p}^{(p+1)}(r^{1/n})}{(p + 1)!}].

From (2.5), (2.8) and (3.14), we obtain

K_{λ_{p},p+1}(r^{1/n}) = [\frac{(3 + n − 2np)}{1 + (−1)^{p+1}(p − 1)}]\frac{p(p − 1)}{2(p + 1)}n^{p} (\begin{matrix}1/n \\ p \end{matrix}) r^{−p/n}.

5. Acknowledgement

This work has been financially supported by an individual discovery grant from NSERC (Natural Sciences and Engineering Research Council of Canada).

References

[1] D.F. Bateman, A historical survey of solution by functional iteration, Math. Mag., 62 (1989), 155-166.

[2] J.E. Dennis and R.B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, N.J., 1983.

[3] F. Dubeau, Algorithms for n-th root approximation, Computing, 57 (1996), 365-369.

[4] W.F. Ford and J.A. Pennline, Accelerated convergence in Newton’s method, SIAM Review, 38 (1996), 658-659.

[5] W. Gander, On Halley’s iteration method, Amer. Math. Month., 92 (1985), 131-134.

[6] J. Gerlach, Accelerated convergence in Newton’s method, SIAM Review, 36 (1994), 272-276.

[7] A.A. Goldstein, Constructive Real Analysis, Harper and Row, N.Y., 1967.

[8] J.M. Gutierrez, M.A. Hernandez, and M.A. Solanova, Calculus of nth roots and third order iterative methods, Nonlinear Analysis, 47 (2001), 2875-2880.

[9] M.A. Hernandez and N. Romero, Accelerated convergence in Newton’s method for approximating square roots, Journal of Computational and Applied Mathematics, 177 (2005), 225-229.

[10] K.R. Johnson, An iterative method for approximating square roots, Math. Mag., 62 (1989), 253-259.

[11] B. Kalantari, On the order of convergence of determinantal family of root-finding methods, BIT, 39 (1999), 96-109.

[12] B. Kalantari and I. Kalantari, High order methods for approximating square roots, BIT, 36 (1996), 395-399.

[13] D. Kincaid and W. Cheney, Numerical Analysis, Brooks/Cole Pub. Co., California, 1991.

[14] R.J. Knill, A modified Babylonian algorithm, Amer. Math. Month., 99 (1992), 734-737.

[15] A.Y.Özban, New methods for approximating square roots, Applied mathematics and Computation, 175 (2006), 532-540.

[16] J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, 2nd Ed., Springer-Verlag, N.Y., 1993.

[17] J.F. Traub, Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, N.J., 1964.

[18] A.K. Yeyios, On two sequences of algorithms for approximating square roots, Journal of Computational and Applied Mathematics, 40 (1992), 63-72.