# A Method to Accelerate the Convergence of the Secant Algorithm

Authors: M. J. P. Nijmeijer
Journal: Advances in Numerical Analysis
 (2014)

---

## Abstract

We present an acceleration technique for the Secant method. The Secant method is a root-searching algorithm for a general functionf. We exploit the fact that the combination of two Secant steps leads to an improved, so-called first-order approximant of the root. The original Secant algorithm can be modified to a first-order accelerated algorithm which generates a sequence of first-order approximants. This process can be repeated: two nth order approximants can be combined in a (
n
+
1
)th order approximant and the algorithm can be modified to an (
n
+
1
)th order accelerated algorithm which generates a sequence of such approximants. We show that the sequence of nth order approximants converges to the root with the same order as methods using polynomial fits of f of degree n.


---

## Body

## 1. Introduction

The Secant algorithm is a textbook algorithm to find a numerical approximation of the root of a functionf
(
x
). A root α is a solution of the equation f
(
x
)
=
0. Other such algorithms are, for example, the bisection algorithm, inverse quadratic interpolation, the regula-falsi algorithm, Muller’s method, the Newton-Raphson algorithm, Steffensen’s method, the Brent algorithm, and many more. These methods are discussed in many books and articles; see, for example, [1–11]. All the algorithms mentioned are intended for a general function f. They all take one, two, or more initial estimates of α as input and iteratively generate a sequence {
x
n
} of approximants of α. The sequence converges to the root α for suitably chosen initial estimates and a function f meeting particular regularity requirements at and around α. The exact requirements differ from method to method. Root-finding plays a role in many problems, also when this is not immediately apparent. An example is the problem of solving a set of linear equations [12].The Secant algorithm has the characteristics that (a) it is “derivative-free;” that is, it does not require the evaluation of a derivative off and (b) it requires only one evaluation of f per iteration. The generated sequence {
x
n
} converges superlinearly with order ψ
0
=
(
1
+
5
)
/
2
≈
1.6180 for a large class of functions f.It is important to stress that only one evaluation off per iteration is needed. Situations which require an efficient root-finding algorithm are typically situations in which the execution time of the algorithm is dominated by the time needed to calculate the value of f. In these situations it is important that as few evaluations of f as possible are needed to estimate the root with a certain accuracy. An algorithm which requires m evaluations of f per iteration is therefore only competitive with the Secant algorithm if one iteration produces a better estimate than m subsequent Secant iterations. In other words, it must converge with an order larger than ψ
0
m. To the best of our knowledge, there are no derivative-free algorithms which achieve this, except for the generalizations of the Secant algorithm discussed below.In this paper we derive a generalization of the Secant method with the following properties: (a) it is derivative-free, (b) it requires one evaluation off per iteration, and (c) it achieves an order of convergence arbitrarily close to 2 for analytic functions f. The first two properties are the same as for the Secant algorithm. The last property shows that the method presented here will converge faster than the Secant method if f is sufficiently regular.Other generalizations of the Secant algorithm with the same three properties are the method of inverse interpolation [2] and Sidi’s method [13]. These two methods are based on polynomial fits to either the inverse of f (in the case of the method of inverse interpolation) or to f itself (in the case of Sidi’s method). Whereas the Secant method is based on straight-line fits to f, the polynomial fits of these methods can be of an arbitrary degree n. The resulting order of convergence is ψ
n
-
1 for both methods. Hence the order is ψ
0 for the Secant method and ψ
1
≈
1.8393 when a polynomial of degree 2 is used. By taking the order of the fitting polynomial large enough, the order of convergence becomes asymptotically quadratic if the function is sufficiently regular.Another method which satisfies the three properties is the method of direct interpolation [2]. However this method requires that the root(s) of a polynomial of degree n are calculated in every iteration. This is not an attractive scheme except possibly for the case n
=
2 which is known as Muller’s method [1].Our method is not based on polynomial fits. It was noted in [14, 15] that the results of two Secant steps can be combined into a better approximant of the root α in a way reminiscent of Aitken’s delta-squared method [16] or Shank’s transformation [17]. We take this idea further. We show that the process of combining approximants can be repeated. If we call the result of a Secant step an approximant of order zero, we demonstrate that two approximants of order n can be combined into an approximant of order n
+
1. We devise an algorithm which generates these approximants. The nth order version of the algorithm generates a sequence of nth order approximants. We show that this sequence converges with order ψ
n to the root α if f is sufficiently regular.Although our algorithm offers no specific advantage over the method of inverse interpolation or Sidi’s method (all are derivative-free, require one evaluation off per iteration, and achieve orders of convergence ψ
n), we think it is noteworthy that the Secant method can be sped up to higher orders of convergence without the use of polynomial fits. We suspect that the same acceleration technique can be applied to a broader set of iterative algorithms. We also see a possibility that our technique can lead to a parallel root-solving algorithm. These venues are however not explored in this paper.The paper is organized as follows. We discuss preliminaries and recall the basic properties of the Secant sequence in Sections2 and 3. We introduce the approximants in Section 4. The algorithm which generates these approximants is given in Section 5 and its convergence properties are derived in Section 6. We end with conclusions in Section 7.


## 2. Preliminaries

### 2.1. Order of Convergence

When a sequence{
x
n
} converges to a limit α and the sequence has the property
(1)
lim
⁡
n
→
∞
x
n
-
α
x
n
-
1
-
α
ψ
=
A
with A
≠
0, then ψ is called the “order of convergence” or “order” of the sequence. The condition A
≠
0 is necessary to define the order of convergence uniquely. A is called the “asymptotic error constant” [2, 18, 19]. The larger the order of convergence, the faster the sequence converges.


### 2.2. Divided Differences

Throughout this paper we use “divided differences.” We remind the reader of their definition and two important properties.LetI be an open interval of real values and let f be a function f
:
I
→
R. Let x
1
,
…
,
x
n
∈
I with x
i
≠
x
j if i
≠
j. The “nth divided difference” f
[
x
1
,
…
,
x
n
] of f is defined recursively as
(2)
f
x
1
,
…
,
x
n
=
f
x
1
,
…
,
x
n
-
1
-
f
x
2
,
…
,
x
n
x
1
-
x
n
with
(3)
f
x
=
f
x
to terminate the recursion.We use the following two properties of divided differences.(i) Iff
∈
C
n
-
2
(
I
) and the (
n
-
2
)th derivative f
(
n
-
2
) is Lipschitz continuous on I, then f
[
x
1
,
…
,
x
n
] is bounded on I
n.
This follows from the property that there exist aζ
1
,
ζ
2
∈
[
min
⁡
(
x
1
,
…
,
x
n
)
,
max
⁡
(
x
1
,
…
,
x
n
)
] such that
(4)
f
x
1
,
…
,
x
n
=
1
n
-
1
!
f
n
-
2
ζ
1
-
f
n
-
2
ζ
2
ζ
1
-
ζ
2
iff
∈
C
n
-
2
(
I
).
(ii) Iff
∈
C
n
-
1
(
I
) and α
∈
I then f
[
x
1
,
…
,
x
n
] is continuous in the point (
x
1
,
…
,
x
n
)
=
(
α
,
…
,
α
) with
(5)
lim
⁡
x
1
,
…
,
x
n
→
α
f
x
1
,
…
,
x
n
=
f
n
-
1
α
n
-
1
!
.
This property is cited in many text books [2, 5, 18, 20]. It follows, for example, from the previous property in combination with the mean value theorem.


## 2.1. Order of Convergence

When a sequence{
x
n
} converges to a limit α and the sequence has the property
(1)
lim
⁡
n
→
∞
x
n
-
α
x
n
-
1
-
α
ψ
=
A
with A
≠
0, then ψ is called the “order of convergence” or “order” of the sequence. The condition A
≠
0 is necessary to define the order of convergence uniquely. A is called the “asymptotic error constant” [2, 18, 19]. The larger the order of convergence, the faster the sequence converges.


## 2.2. Divided Differences

Throughout this paper we use “divided differences.” We remind the reader of their definition and two important properties.LetI be an open interval of real values and let f be a function f
:
I
→
R. Let x
1
,
…
,
x
n
∈
I with x
i
≠
x
j if i
≠
j. The “nth divided difference” f
[
x
1
,
…
,
x
n
] of f is defined recursively as
(2)
f
x
1
,
…
,
x
n
=
f
x
1
,
…
,
x
n
-
1
-
f
x
2
,
…
,
x
n
x
1
-
x
n
with
(3)
f
x
=
f
x
to terminate the recursion.We use the following two properties of divided differences.(i) Iff
∈
C
n
-
2
(
I
) and the (
n
-
2
)th derivative f
(
n
-
2
) is Lipschitz continuous on I, then f
[
x
1
,
…
,
x
n
] is bounded on I
n.
This follows from the property that there exist aζ
1
,
ζ
2
∈
[
min
⁡
(
x
1
,
…
,
x
n
)
,
max
⁡
(
x
1
,
…
,
x
n
)
] such that
(4)
f
x
1
,
…
,
x
n
=
1
n
-
1
!
f
n
-
2
ζ
1
-
f
n
-
2
ζ
2
ζ
1
-
ζ
2
iff
∈
C
n
-
2
(
I
).
(ii) Iff
∈
C
n
-
1
(
I
) and α
∈
I then f
[
x
1
,
…
,
x
n
] is continuous in the point (
x
1
,
…
,
x
n
)
=
(
α
,
…
,
α
) with
(5)
lim
⁡
x
1
,
…
,
x
n
→
α
f
x
1
,
…
,
x
n
=
f
n
-
1
α
n
-
1
!
.
This property is cited in many text books [2, 5, 18, 20]. It follows, for example, from the previous property in combination with the mean value theorem.


## 3. The Secant Algorithm

Suppose we have an open intervalI of real values and a function f
:
I
→
R. Suppose α
∈
I and f
(
α
)
=
0. A Secant step S is defined as
(6)
S
x
1
,
x
2
=
x
1
-
f
x
1
x
1
-
x
2
f
x
1
-
f
x
2
=
-
f
x
2
x
1
+
f
x
1
x
2
f
x
1
-
f
x
2
.
The Secant algorithm generates a sequence {
x
n
}
n
=
-
1
∞ which starts with two initial values x
-
1, x
0
∈
I and develops as
(7)
x
n
=
S
x
n
-
1
,
x
n
-
2
.
We can develop the sequence as long as x
n
∈
I. It can be shown [2, 5] that
(8)
x
n
-
α
=
x
n
-
1
-
α
x
n
-
2
-
α
f
α
,
x
n
-
1
,
x
n
-
2
f
x
n
-
1
,
x
n
-
2
.
It can also be shown [2, 5] that if f
∈
C
2
(
I
), the first derivative f
(
1
)
(
α
) and second derivative f
(
2
)
(
α
) are not equal to zero, and the start values x
-
1 and x
0 are chosen close enough to α, then the Secant sequence {
x
n
}
n
=
-
1
∞ converges to α with
(9)
lim
⁡
n
→
∞
x
n
-
α
x
n
-
1
-
α
ψ
0
=
f
2
α
2
f
1
α
ψ
0
-
1
,
where ψ
0
=
(
1
+
5
)
/
2.This means that the sequence converges with orderψ
0 under the conditions stated. It can be expected [10] that the sequence converges with a higher order if f
(
2
)
(
α
)
=
0. In case f
(
1
)
(
α
)
=
0 the sequence still converges but no longer superlinearly [21].


## 4. General Order Approximant

We define what we call an approximant of general order of the rootα of a function f in this section. This definition is recursive. To study this approximant, we express the approximant directly in terms of f in Section 4.1. Two expressions are obtained: one involving f and polynomials in Section 4.1.1 and one involving divided differences in Section 4.1.2. These forms allows us to cast the approximant in a form which exposes its properties when we are close to α in Lemmas 3 and 4.We define annth order approximant S
n as follows.Definition 1.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R. Define the nth order approximant S
n for n
=
1,2
,
3
,
… as
(10)
S
n
x
1
,
…
,
x
n
+
2
=
S
n
-
1
x
1
,
…
,
x
n
+
1
x
n
+
2
-
x
1
S
n
-
1
x
2
,
…
,
x
n
+
2
S
n
-
1
x
1
,
…
,
x
n
+
1
+
x
n
+
2
-
x
1
-
S
n
-
1
x
2
,
…
,
x
n
+
2
for all values x
1
,
…
,
x
n
+
2
∈
I for which S
n
-
1
(
x
1
,
…
,
x
n
+
1
) and S
n
-
1
(
x
2
,
…
,
x
n
+
2
) are defined and for which the denominator is unequal to zero. S
0
(
x
1
,
x
2
) is the Secant step S
(
x
1
,
x
2
) defined in (6).The reason why we call this an approximant will become clear shortly.


### 4.1. The Approximant in Terms of the Functionf

#### 4.1.1. First Form

From (6) we can write S
0 as
(11)
S
0
x
1
,
x
2
=
-
x
1
/
f
x
1
+
x
2
/
f
x
2
-
1
/
f
x
1
+
1
/
f
x
2
for f
(
x
1
)
,
f
(
x
2
)
≠
0 and f
(
x
1
)
≠
f
(
x
2
). Working out S
1 with our recursive definition for S
n we obtain
(12)
S
1
x
1
,
x
2
,
x
3
=
-
x
1
f
x
1
x
2
-
x
3
+
x
2
f
x
2
x
1
-
x
3
h
h
h
h
h
-
x
3
f
x
3
x
1
-
x
2
·
-
1
f
x
1
x
2
-
x
3
+
1
f
x
2
x
1
-
x
3
h
h
h
h
h
-
1
f
x
3
x
1
-
x
2
-
1
for f
(
x
1
)
,
f
(
x
2
)
,
f
(
x
3
)
≠
0 and the denominator not equal to zero.We show in AppendixA that the general form of (11) and (12) is
(13)
S
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
x
i
/
f
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
∑
i
=
1
n
+
2
1
/
f
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
for f
(
x
1
)
,
…
,
f
(
x
n
+
2
)
≠
0 and the denominator not equal to zero. The a
n
,
i are polynomials and are given by
(14)
a
n
,
i
x
1
,
…
,
x
n
+
2
=
-
1
i
∏
j
=
1
j
≠
i
n
+
2
∏
k
=
j
+
1
k
≠
i
n
+
2
x
j
-
x
k
for n
=
0,1
,
2
,
…  and i
=
1
,
…
,
n
+
2. Throughout the paper we follow the convention that ∏
i
=
j
k
‍
(
⋯
)
=
1 for k
<
j.The conditionf
(
x
i
)
≠
0 for all i must be imposed for the form (13) but can be lifted by multiplying both numerator and denominator with the product ∏
i
=
1
n
+
2
‍
f
(
x
i
).Examples ofa
n
,
i for n
=
0,1
,
2 are
(15)
a
0,1
x
1
,
x
2
=
-
1
,
a
0,2
x
1
,
x
2
=
1
,
a
1,1
x
1
,
x
2
,
x
3
=
-
x
2
-
x
3
,
a
1,2
x
1
,
x
2
,
x
3
=
x
1
-
x
3
,
a
1,3
x
1
,
x
2
,
x
3
=
-
x
1
-
x
2
,
a
2,1
x
1
,
x
2
,
x
3
,
x
4
=
-
x
2
-
x
3
x
2
-
x
4
x
3
-
x
4
,
a
2,2
x
1
,
x
2
,
x
3
,
x
4
=
x
1
-
x
3
x
1
-
x
4
x
3
-
x
4
,
a
2,3
x
1
,
x
2
,
x
3
,
x
4
=
-
x
1
-
x
2
x
1
-
x
4
x
2
-
x
4
,
a
2,3
x
1
,
x
2
,
x
3
,
x
4
⋮


#### 4.1.2. Second Form

We derive a second expression forS
n with the help of the lemma below.Lemma 2.
LetS
n be defined as
(16)
S
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
g
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
for some function g
(
x
). Then
(17)
S
n
x
1
,
…
,
x
n
+
2
=
-
∏
i
=
1
n
+
2
∏
j
=
i
+
1
n
+
2
x
i
-
x
j
g
x
1
,
…
,
x
n
+
2
.Proof.
The proof can be obtained by elementary manipulations if we remember [18] that
(18)
g
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
g
x
i
∏
j
=
1
j
≠
i
n
+
2
x
i
-
x
j
.Application of Lemma2 to (13) with g
(
x
)
=
x
/
f
(
x
) for the numerator and g
(
x
)
=
1
/
f
(
x
) for the denominator of (13) brings S
n in the form
(19)
S
n
x
1
,
…
,
x
n
+
2
=
x
/
f
x
1
,
…
,
x
n
+
2
1
/
f
x
1
,
…
,
x
n
+
2
provided that f
(
x
i
)
≠
0 for all i
=
1
,
…
,
n
+
2 and that the denominator is not equal to zero. The numerator (
x
/
f
)
[
x
1
,
…
,
x
n
+
2
] in (19) is the (
n
+
2
)th divided difference of the function x
/
f
(
x
). The denominator (
1
/
f
)
[
x
1
,
…
,
x
n
+
2
] is (
n
+
2
)th divided difference of the function 1
/
f
(
x
).


### 4.2. The Approximant Near the Root

Suppose the functionf in the definition of S
n has a root at α
∈
I: f
(
α
)
=
0. We study S
n in the case that all its arguments x
1
,
…
,
x
n
+
2 are in the neighbourhood of α. We write x
=
α
+
y and f
Y
(
y
)
=
f
(
α
+
y
). The function f
Y is the function f in the coordinate frame Y. The root is at y
=
0 in this coordinate frame: f
Y
(
0
)
=
0. We can express f
(
x
) in the second divided difference of f
Y as f
(
x
)
=
y
f
Y
[
0
,
y
].Substitutingx
i
=
α
+
y
i in (13) we have
(20)
S
n
α
+
y
1
,
…
,
α
+
y
n
+
2
=
α
+
∏
i
=
1
n
+
2
y
i
K
Y
n
y
1
,
…
,
y
n
+
2
with
(21)
K
Y
n
y
1
,
…
,
y
n
+
2
=
∑
i
=
1
n
+
2
1
/
f
Y
0
,
y
i
a
n
,
i
y
1
,
…
,
y
n
+
2
∑
i
=
1
n
+
2
∏
j
=
1
,
j
≠
i
n
+
2
y
j
/
f
Y
0
,
y
i
a
n
,
i
y
1
,
…
,
y
n
+
2
.
K
Y
n is defined in the coordinate frame Y. The corresponding K
n in the original coordinate frame is
(22)
K
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
1
/
f
α
,
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
∑
i
=
1
n
+
2
∏
j
=
1
,
j
≠
i
n
+
2
x
j
-
α
/
f
α
,
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
.If we can show thatK
Y
n is bounded for small values of the y
i, we see from (20) that S
n is a good approximation of α. Establishing the boundedness of K
Y
n is therefore the major task of the remainder of this section.Application of Lemma2 with g
(
y
)
=
1
/
f
Y
[
0
,
y
] in the numerator and g
(
y
)
=
(
∏
i
=
1
n
+
2
‍
y
i
)
/
(
y
f
Y
[
0
,
y
]
) in the denominator of (21) brings K
Y
n in the form
(23)
K
Y
n
y
1
,
…
,
y
n
+
2
=
1
/
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
∏
i
=
1
n
+
2
y
i
1
/
y
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
.The numerator is a divided difference of1
/
f
[
0
,
y
]. The denominator contains a divided difference of 1
/
(
y
f
[
0
,
y
]
). Call the denominator D. We express the divided difference of 1
/
(
y
f
[
0
,
y
]
) in divided differences of 1
/
f
[
0
,
y
] with the use of Leibniz rule for divided differences [22–24]
(24)
D
y
1
,
…
,
y
n
+
2
=
∏
i
=
1
n
+
2
y
i
1
y
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
=
∏
i
=
1
n
+
2
y
i
∑
i
=
1
n
+
2
1
y
y
1
,
…
,
y
i
1
f
Y
0
,
y
y
i
,
…
,
y
n
+
2
.
Using
(25)
1
y
y
1
,
…
,
y
i
=
-
1
i
+
1
∏
j
=
1
i
1
y
j
,
we arrive at
(26)
D
y
1
,
…
,
y
n
+
2
=
∑
i
=
1
n
+
2
-
1
i
+
1
∏
j
=
i
+
1
n
+
2
y
j
1
f
Y
0
,
y
y
i
,
…
,
y
n
+
2
.We are now in a position to establish the properties ofK
n in the following two lemmas.Lemma 3.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
1
(
I
). Let f
(
n
+
1
) be Lipschitz continuous on I. Let α
∈
I, f
(
α
)
=
0, and f
(
1
)
(
α
)
≠
0. Then the nth order approximant S
n takes the form
(27)
S
n
x
1
,
…
,
x
n
+
2
=
α
+
∏
i
=
1
n
+
2
x
j
-
α
K
n
x
1
,
…
,
x
n
+
2
,
where there exists an ϵ
>
0 such that K
n is bounded if  |
x
i
-
α
|
<
ϵ for all i
=
1
,
…
,
n
+
2.Proof.
We have already shown the form ofS
n in (20). All that remains to be done is to show that K
Y
n is bounded in an (
n
+
2
)-dimensional hypercube around the point (
y
1
,
…
,
y
n
+
2
)
=
(
0
,
…
,
0
). Denote this point by 0
→.
From the properties of divided differences we know that the numerator in (23) is bounded in a hypercube around 0
→ if the function 1
/
(
f
Y
[
0
,
y
]
) is n-times continuously differentiable around y
=
0 and the nth derivative is Lipschitz continuous.
This is also a sufficient condition for all divided differences that appear in (26) to be bounded. Therefore all terms in (26) can be made arbitrarily small by choosing the y
i small enough, except for the last term. The last term has a limiting value (
-
1
)
n
+
3
/
f
Y
(
1
)
(
0
)
≠
0 if all y
i become equal to zero; compare or confer (35). This shows that there is a lower bound D
_ such that 0
<
D
_
<
|
D
| on a hypercube around 0
→. Combining this with the bound on the numerator proves that K
Y
n is bounded.
It remains to be shown that1
/
(
f
Y
[
0
,
y
]
) is n-times continuously differentiable with the nth order derivative Lipschitz continuous around y
=
0.
LetJ be the interval around y
=
0 corresponding to the interval I around x
=
α: J
=
{
y
∈
R
∣
y
+
α
∈
I
}. Because f
∈
C
n
+
1
(
I
) and f
(
n
+
1
) is Lipschitz continuous on I we have f
Y
∈
C
n
+
1
(
J
) and f
Y
(
n
+
1
) is Lipschitz continuous on J.
Becausef
(
1
)
(
α
)
≠
0 there is an finite open interval J
′
⊂
J with 0
∈
J
′ such that inf
⁡
{
|
f
Y
[
0
,
y
]
|
∣
y
∈
J
′
}
>
0. Because f
Y
(
n
+
1
) is Lipschitz continuous on J
′ and J
′ is finite, f
Y
(
n
+
1
) is bounded on J
′. Because f
Y
(
n
+
1
) is bounded on J
′, all lower-order derivatives f
Y
(
k
) (k
=
1
,
…
,
n) and f
Y itself will be bounded on J
′.
First we show that1
/
(
f
Y
[
0
,
y
]
) is n-times continuously differentiable on J
′. We use [18]
(28)
∂
∂
y
f
Y
0
,
y
,
…
,
y
︸
k
times
=
k
f
Y
0
,
y
,
…
,
y
︸
k
+
1
times
which is defined if f
Y is k-times differentiable in the point y and y
≠
0. If we allow y
=
0 as well then f
Y must be (
k
+
1
)-times differentiable in y. Hence we find
(29)
∂
∂
y
1
f
Y
0
,
y
=
-
f
Y
0
,
y
,
y
f
Y
0
,
y
2
if y
∈
J
′ (which includes y
=
0) and f
Y
∈
C
2
(
J
′
), and
(30)
∂
2
∂
y
2
1
f
Y
0
,
y
=
2
-
f
Y
0
,
y
,
y
,
y
f
Y
0
,
y
+
f
Y
0
,
y
,
y
2
f
Y
0
,
y
3
.
if y
∈
J
′ and f
Y
∈
C
3
(
J
′
). Continuing the differentiation we easily see that 1
/
(
f
Y
[
0
,
y
]
)
∈
C
n
(
J
′
) if f
Y
∈
C
n
+
1
(
J
′
).
Next we show that thenth derivative to y of 1
/
(
f
Y
[
0
,
y
]
) is Lipschitz continuous on J
′. As we see from examples (29) and (30), the derivative can be expressed as a nonlinear combination of f
Y
[
0
,
y
,
…
,
y
︸
k
times
] for k
=
1
,
…
,
n
+
1. Combine the following to see that the derivative is Lipschitz continuous on J
′.(i)
f
Y
[
0
,
y
,
…
,
y
︸
k
times
] is Lipschitz continuous on J
′ for k
=
1
,
…
,
n
+
1. To show this take y
1
,
y
2
∈
J
′ and consider the difference of the divided difference between the two points:
(31)
f
Y
0
,
y
1
,
…
,
y
1
︸
k
times
-
f
Y
0
,
y
2
,
…
,
y
2
︸
k
times
=
1
k
-
1
!
·
∂
k
-
1
∂
y
k
-
1
f
Y
0
,
y
y
=
y
1
-
∂
k
-
1
∂
y
k
-
1
f
Y
0
,
y
y
=
y
2
=
1
k
-
1
!
y
1
-
y
2
∂
k
∂
y
k
f
Y
0
,
y
y
=
ζ
=
k
y
1
-
y
2
f
Y
0
,
ζ
,
…
,
ζ
︸
k
+
1
times
for some ζ
∈
(
min
⁡
(
y
1
,
y
2
)
,
max
⁡
(
y
1
,
y
2
)
). Since f
Y
∈
C
n
+
1
(
J
′
) and f
Y
(
n
+
1
) Lipschitz continuous on J
′,f
Y
[
0
,
ζ
,
…
,
ζ
︸
(
k
+
1
)
times
] is bounded on J
′ for k
=
1
,
…
,
n
+
1.
(ii)
Becausef
Y
[
0
,
y
] is Lipschitz continuous on J
′ and the infimum of its absolute value on J
′ is larger than zero, 1
/
(
f
Y
[
0
,
y
]
) is Lipschitz continuous on J
′.
(iii)
If two functionsf
1 and f
2 are Lipschitz continuous and bounded on J
′, then f
1
+
f
2 and f
1
f
2 are also Lipschitz continuous on J
′. This is easy to see for the sum of the two functions. For the product we have
(32)
f
1
y
1
f
2
y
1
-
f
1
y
2
f
2
y
2
=
f
1
y
1
-
f
1
y
2
f
2
y
1
-
f
1
y
2
f
2
y
2
-
f
2
y
1
≤
f
2
y
1
f
1
y
1
-
f
1
y
2
+
f
1
y
2
f
2
y
1
-
f
2
y
2
≤
M
L
1
+
L
2
y
1
-
y
2
,
where M is the maximum of the suprema of f
1 and f
2 on J
′ and L
i is the Lipschitz constant of f
i on J
′.
This concludes the proof.Lemma 4.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
2
(
I
). Let α
∈
I, f
(
α
)
=
0, and f
(
1
)
(
α
)
≠
0. Then K
n
(
x
1
,
…
,
x
n
) as defined in Lemma 3 is continuous in (
x
1
,
…
,
x
n
+
2
)
=
(
α
,
…
,
α
) with
(33)
lim
⁡
x
1
,
…
,
x
n
+
2
→
α
K
n
x
1
,
…
,
x
n
+
2
=
-
1
n
+
1
n
+
1
!
f
1
α
∂
n
+
1
∂
x
n
+
1
1
f
α
,
x
x
=
α
.Proof.
Taking the limit for the numerator of (23) we find
(34)
lim
⁡
y
1
,
…
,
y
n
+
2
→
0
1
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
=
1
n
+
1
!
∂
n
+
1
∂
y
n
+
1
1
f
Y
0
,
y
y
=
0
=
1
n
+
1
!
∂
n
+
1
∂
x
n
+
1
1
f
α
,
x
x
=
α
.
Taking the limit for the denominator D in (26) we obtain
(35)
lim
⁡
y
1
,
…
,
y
n
+
2
→
0
D
y
1
,
…
,
y
n
+
2
=
-
1
n
+
1
f
Y
0,0
=
-
1
n
+
1
f
1
α
.
Dividing the result for numerator by the result for the denominator yields the proof.


## 4.1. The Approximant in Terms of the Functionf

### 4.1.1. First Form

From (6) we can write S
0 as
(11)
S
0
x
1
,
x
2
=
-
x
1
/
f
x
1
+
x
2
/
f
x
2
-
1
/
f
x
1
+
1
/
f
x
2
for f
(
x
1
)
,
f
(
x
2
)
≠
0 and f
(
x
1
)
≠
f
(
x
2
). Working out S
1 with our recursive definition for S
n we obtain
(12)
S
1
x
1
,
x
2
,
x
3
=
-
x
1
f
x
1
x
2
-
x
3
+
x
2
f
x
2
x
1
-
x
3
h
h
h
h
h
-
x
3
f
x
3
x
1
-
x
2
·
-
1
f
x
1
x
2
-
x
3
+
1
f
x
2
x
1
-
x
3
h
h
h
h
h
-
1
f
x
3
x
1
-
x
2
-
1
for f
(
x
1
)
,
f
(
x
2
)
,
f
(
x
3
)
≠
0 and the denominator not equal to zero.We show in AppendixA that the general form of (11) and (12) is
(13)
S
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
x
i
/
f
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
∑
i
=
1
n
+
2
1
/
f
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
for f
(
x
1
)
,
…
,
f
(
x
n
+
2
)
≠
0 and the denominator not equal to zero. The a
n
,
i are polynomials and are given by
(14)
a
n
,
i
x
1
,
…
,
x
n
+
2
=
-
1
i
∏
j
=
1
j
≠
i
n
+
2
∏
k
=
j
+
1
k
≠
i
n
+
2
x
j
-
x
k
for n
=
0,1
,
2
,
…  and i
=
1
,
…
,
n
+
2. Throughout the paper we follow the convention that ∏
i
=
j
k
‍
(
⋯
)
=
1 for k
<
j.The conditionf
(
x
i
)
≠
0 for all i must be imposed for the form (13) but can be lifted by multiplying both numerator and denominator with the product ∏
i
=
1
n
+
2
‍
f
(
x
i
).Examples ofa
n
,
i for n
=
0,1
,
2 are
(15)
a
0,1
x
1
,
x
2
=
-
1
,
a
0,2
x
1
,
x
2
=
1
,
a
1,1
x
1
,
x
2
,
x
3
=
-
x
2
-
x
3
,
a
1,2
x
1
,
x
2
,
x
3
=
x
1
-
x
3
,
a
1,3
x
1
,
x
2
,
x
3
=
-
x
1
-
x
2
,
a
2,1
x
1
,
x
2
,
x
3
,
x
4
=
-
x
2
-
x
3
x
2
-
x
4
x
3
-
x
4
,
a
2,2
x
1
,
x
2
,
x
3
,
x
4
=
x
1
-
x
3
x
1
-
x
4
x
3
-
x
4
,
a
2,3
x
1
,
x
2
,
x
3
,
x
4
=
-
x
1
-
x
2
x
1
-
x
4
x
2
-
x
4
,
a
2,3
x
1
,
x
2
,
x
3
,
x
4
⋮


### 4.1.2. Second Form

We derive a second expression forS
n with the help of the lemma below.Lemma 2.
LetS
n be defined as
(16)
S
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
g
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
for some function g
(
x
). Then
(17)
S
n
x
1
,
…
,
x
n
+
2
=
-
∏
i
=
1
n
+
2
∏
j
=
i
+
1
n
+
2
x
i
-
x
j
g
x
1
,
…
,
x
n
+
2
.Proof.
The proof can be obtained by elementary manipulations if we remember [18] that
(18)
g
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
g
x
i
∏
j
=
1
j
≠
i
n
+
2
x
i
-
x
j
.Application of Lemma2 to (13) with g
(
x
)
=
x
/
f
(
x
) for the numerator and g
(
x
)
=
1
/
f
(
x
) for the denominator of (13) brings S
n in the form
(19)
S
n
x
1
,
…
,
x
n
+
2
=
x
/
f
x
1
,
…
,
x
n
+
2
1
/
f
x
1
,
…
,
x
n
+
2
provided that f
(
x
i
)
≠
0 for all i
=
1
,
…
,
n
+
2 and that the denominator is not equal to zero. The numerator (
x
/
f
)
[
x
1
,
…
,
x
n
+
2
] in (19) is the (
n
+
2
)th divided difference of the function x
/
f
(
x
). The denominator (
1
/
f
)
[
x
1
,
…
,
x
n
+
2
] is (
n
+
2
)th divided difference of the function 1
/
f
(
x
).


## 4.1.1. First Form

From (6) we can write S
0 as
(11)
S
0
x
1
,
x
2
=
-
x
1
/
f
x
1
+
x
2
/
f
x
2
-
1
/
f
x
1
+
1
/
f
x
2
for f
(
x
1
)
,
f
(
x
2
)
≠
0 and f
(
x
1
)
≠
f
(
x
2
). Working out S
1 with our recursive definition for S
n we obtain
(12)
S
1
x
1
,
x
2
,
x
3
=
-
x
1
f
x
1
x
2
-
x
3
+
x
2
f
x
2
x
1
-
x
3
h
h
h
h
h
-
x
3
f
x
3
x
1
-
x
2
·
-
1
f
x
1
x
2
-
x
3
+
1
f
x
2
x
1
-
x
3
h
h
h
h
h
-
1
f
x
3
x
1
-
x
2
-
1
for f
(
x
1
)
,
f
(
x
2
)
,
f
(
x
3
)
≠
0 and the denominator not equal to zero.We show in AppendixA that the general form of (11) and (12) is
(13)
S
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
x
i
/
f
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
∑
i
=
1
n
+
2
1
/
f
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
for f
(
x
1
)
,
…
,
f
(
x
n
+
2
)
≠
0 and the denominator not equal to zero. The a
n
,
i are polynomials and are given by
(14)
a
n
,
i
x
1
,
…
,
x
n
+
2
=
-
1
i
∏
j
=
1
j
≠
i
n
+
2
∏
k
=
j
+
1
k
≠
i
n
+
2
x
j
-
x
k
for n
=
0,1
,
2
,
…  and i
=
1
,
…
,
n
+
2. Throughout the paper we follow the convention that ∏
i
=
j
k
‍
(
⋯
)
=
1 for k
<
j.The conditionf
(
x
i
)
≠
0 for all i must be imposed for the form (13) but can be lifted by multiplying both numerator and denominator with the product ∏
i
=
1
n
+
2
‍
f
(
x
i
).Examples ofa
n
,
i for n
=
0,1
,
2 are
(15)
a
0,1
x
1
,
x
2
=
-
1
,
a
0,2
x
1
,
x
2
=
1
,
a
1,1
x
1
,
x
2
,
x
3
=
-
x
2
-
x
3
,
a
1,2
x
1
,
x
2
,
x
3
=
x
1
-
x
3
,
a
1,3
x
1
,
x
2
,
x
3
=
-
x
1
-
x
2
,
a
2,1
x
1
,
x
2
,
x
3
,
x
4
=
-
x
2
-
x
3
x
2
-
x
4
x
3
-
x
4
,
a
2,2
x
1
,
x
2
,
x
3
,
x
4
=
x
1
-
x
3
x
1
-
x
4
x
3
-
x
4
,
a
2,3
x
1
,
x
2
,
x
3
,
x
4
=
-
x
1
-
x
2
x
1
-
x
4
x
2
-
x
4
,
a
2,3
x
1
,
x
2
,
x
3
,
x
4
⋮


## 4.1.2. Second Form

We derive a second expression forS
n with the help of the lemma below.Lemma 2.
LetS
n be defined as
(16)
S
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
g
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
for some function g
(
x
). Then
(17)
S
n
x
1
,
…
,
x
n
+
2
=
-
∏
i
=
1
n
+
2
∏
j
=
i
+
1
n
+
2
x
i
-
x
j
g
x
1
,
…
,
x
n
+
2
.Proof.
The proof can be obtained by elementary manipulations if we remember [18] that
(18)
g
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
g
x
i
∏
j
=
1
j
≠
i
n
+
2
x
i
-
x
j
.Application of Lemma2 to (13) with g
(
x
)
=
x
/
f
(
x
) for the numerator and g
(
x
)
=
1
/
f
(
x
) for the denominator of (13) brings S
n in the form
(19)
S
n
x
1
,
…
,
x
n
+
2
=
x
/
f
x
1
,
…
,
x
n
+
2
1
/
f
x
1
,
…
,
x
n
+
2
provided that f
(
x
i
)
≠
0 for all i
=
1
,
…
,
n
+
2 and that the denominator is not equal to zero. The numerator (
x
/
f
)
[
x
1
,
…
,
x
n
+
2
] in (19) is the (
n
+
2
)th divided difference of the function x
/
f
(
x
). The denominator (
1
/
f
)
[
x
1
,
…
,
x
n
+
2
] is (
n
+
2
)th divided difference of the function 1
/
f
(
x
).


## 4.2. The Approximant Near the Root

Suppose the functionf in the definition of S
n has a root at α
∈
I: f
(
α
)
=
0. We study S
n in the case that all its arguments x
1
,
…
,
x
n
+
2 are in the neighbourhood of α. We write x
=
α
+
y and f
Y
(
y
)
=
f
(
α
+
y
). The function f
Y is the function f in the coordinate frame Y. The root is at y
=
0 in this coordinate frame: f
Y
(
0
)
=
0. We can express f
(
x
) in the second divided difference of f
Y as f
(
x
)
=
y
f
Y
[
0
,
y
].Substitutingx
i
=
α
+
y
i in (13) we have
(20)
S
n
α
+
y
1
,
…
,
α
+
y
n
+
2
=
α
+
∏
i
=
1
n
+
2
y
i
K
Y
n
y
1
,
…
,
y
n
+
2
with
(21)
K
Y
n
y
1
,
…
,
y
n
+
2
=
∑
i
=
1
n
+
2
1
/
f
Y
0
,
y
i
a
n
,
i
y
1
,
…
,
y
n
+
2
∑
i
=
1
n
+
2
∏
j
=
1
,
j
≠
i
n
+
2
y
j
/
f
Y
0
,
y
i
a
n
,
i
y
1
,
…
,
y
n
+
2
.
K
Y
n is defined in the coordinate frame Y. The corresponding K
n in the original coordinate frame is
(22)
K
n
x
1
,
…
,
x
n
+
2
=
∑
i
=
1
n
+
2
1
/
f
α
,
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
∑
i
=
1
n
+
2
∏
j
=
1
,
j
≠
i
n
+
2
x
j
-
α
/
f
α
,
x
i
a
n
,
i
x
1
,
…
,
x
n
+
2
.If we can show thatK
Y
n is bounded for small values of the y
i, we see from (20) that S
n is a good approximation of α. Establishing the boundedness of K
Y
n is therefore the major task of the remainder of this section.Application of Lemma2 with g
(
y
)
=
1
/
f
Y
[
0
,
y
] in the numerator and g
(
y
)
=
(
∏
i
=
1
n
+
2
‍
y
i
)
/
(
y
f
Y
[
0
,
y
]
) in the denominator of (21) brings K
Y
n in the form
(23)
K
Y
n
y
1
,
…
,
y
n
+
2
=
1
/
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
∏
i
=
1
n
+
2
y
i
1
/
y
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
.The numerator is a divided difference of1
/
f
[
0
,
y
]. The denominator contains a divided difference of 1
/
(
y
f
[
0
,
y
]
). Call the denominator D. We express the divided difference of 1
/
(
y
f
[
0
,
y
]
) in divided differences of 1
/
f
[
0
,
y
] with the use of Leibniz rule for divided differences [22–24]
(24)
D
y
1
,
…
,
y
n
+
2
=
∏
i
=
1
n
+
2
y
i
1
y
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
=
∏
i
=
1
n
+
2
y
i
∑
i
=
1
n
+
2
1
y
y
1
,
…
,
y
i
1
f
Y
0
,
y
y
i
,
…
,
y
n
+
2
.
Using
(25)
1
y
y
1
,
…
,
y
i
=
-
1
i
+
1
∏
j
=
1
i
1
y
j
,
we arrive at
(26)
D
y
1
,
…
,
y
n
+
2
=
∑
i
=
1
n
+
2
-
1
i
+
1
∏
j
=
i
+
1
n
+
2
y
j
1
f
Y
0
,
y
y
i
,
…
,
y
n
+
2
.We are now in a position to establish the properties ofK
n in the following two lemmas.Lemma 3.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
1
(
I
). Let f
(
n
+
1
) be Lipschitz continuous on I. Let α
∈
I, f
(
α
)
=
0, and f
(
1
)
(
α
)
≠
0. Then the nth order approximant S
n takes the form
(27)
S
n
x
1
,
…
,
x
n
+
2
=
α
+
∏
i
=
1
n
+
2
x
j
-
α
K
n
x
1
,
…
,
x
n
+
2
,
where there exists an ϵ
>
0 such that K
n is bounded if  |
x
i
-
α
|
<
ϵ for all i
=
1
,
…
,
n
+
2.Proof.
We have already shown the form ofS
n in (20). All that remains to be done is to show that K
Y
n is bounded in an (
n
+
2
)-dimensional hypercube around the point (
y
1
,
…
,
y
n
+
2
)
=
(
0
,
…
,
0
). Denote this point by 0
→.
From the properties of divided differences we know that the numerator in (23) is bounded in a hypercube around 0
→ if the function 1
/
(
f
Y
[
0
,
y
]
) is n-times continuously differentiable around y
=
0 and the nth derivative is Lipschitz continuous.
This is also a sufficient condition for all divided differences that appear in (26) to be bounded. Therefore all terms in (26) can be made arbitrarily small by choosing the y
i small enough, except for the last term. The last term has a limiting value (
-
1
)
n
+
3
/
f
Y
(
1
)
(
0
)
≠
0 if all y
i become equal to zero; compare or confer (35). This shows that there is a lower bound D
_ such that 0
<
D
_
<
|
D
| on a hypercube around 0
→. Combining this with the bound on the numerator proves that K
Y
n is bounded.
It remains to be shown that1
/
(
f
Y
[
0
,
y
]
) is n-times continuously differentiable with the nth order derivative Lipschitz continuous around y
=
0.
LetJ be the interval around y
=
0 corresponding to the interval I around x
=
α: J
=
{
y
∈
R
∣
y
+
α
∈
I
}. Because f
∈
C
n
+
1
(
I
) and f
(
n
+
1
) is Lipschitz continuous on I we have f
Y
∈
C
n
+
1
(
J
) and f
Y
(
n
+
1
) is Lipschitz continuous on J.
Becausef
(
1
)
(
α
)
≠
0 there is an finite open interval J
′
⊂
J with 0
∈
J
′ such that inf
⁡
{
|
f
Y
[
0
,
y
]
|
∣
y
∈
J
′
}
>
0. Because f
Y
(
n
+
1
) is Lipschitz continuous on J
′ and J
′ is finite, f
Y
(
n
+
1
) is bounded on J
′. Because f
Y
(
n
+
1
) is bounded on J
′, all lower-order derivatives f
Y
(
k
) (k
=
1
,
…
,
n) and f
Y itself will be bounded on J
′.
First we show that1
/
(
f
Y
[
0
,
y
]
) is n-times continuously differentiable on J
′. We use [18]
(28)
∂
∂
y
f
Y
0
,
y
,
…
,
y
︸
k
times
=
k
f
Y
0
,
y
,
…
,
y
︸
k
+
1
times
which is defined if f
Y is k-times differentiable in the point y and y
≠
0. If we allow y
=
0 as well then f
Y must be (
k
+
1
)-times differentiable in y. Hence we find
(29)
∂
∂
y
1
f
Y
0
,
y
=
-
f
Y
0
,
y
,
y
f
Y
0
,
y
2
if y
∈
J
′ (which includes y
=
0) and f
Y
∈
C
2
(
J
′
), and
(30)
∂
2
∂
y
2
1
f
Y
0
,
y
=
2
-
f
Y
0
,
y
,
y
,
y
f
Y
0
,
y
+
f
Y
0
,
y
,
y
2
f
Y
0
,
y
3
.
if y
∈
J
′ and f
Y
∈
C
3
(
J
′
). Continuing the differentiation we easily see that 1
/
(
f
Y
[
0
,
y
]
)
∈
C
n
(
J
′
) if f
Y
∈
C
n
+
1
(
J
′
).
Next we show that thenth derivative to y of 1
/
(
f
Y
[
0
,
y
]
) is Lipschitz continuous on J
′. As we see from examples (29) and (30), the derivative can be expressed as a nonlinear combination of f
Y
[
0
,
y
,
…
,
y
︸
k
times
] for k
=
1
,
…
,
n
+
1. Combine the following to see that the derivative is Lipschitz continuous on J
′.(i)
f
Y
[
0
,
y
,
…
,
y
︸
k
times
] is Lipschitz continuous on J
′ for k
=
1
,
…
,
n
+
1. To show this take y
1
,
y
2
∈
J
′ and consider the difference of the divided difference between the two points:
(31)
f
Y
0
,
y
1
,
…
,
y
1
︸
k
times
-
f
Y
0
,
y
2
,
…
,
y
2
︸
k
times
=
1
k
-
1
!
·
∂
k
-
1
∂
y
k
-
1
f
Y
0
,
y
y
=
y
1
-
∂
k
-
1
∂
y
k
-
1
f
Y
0
,
y
y
=
y
2
=
1
k
-
1
!
y
1
-
y
2
∂
k
∂
y
k
f
Y
0
,
y
y
=
ζ
=
k
y
1
-
y
2
f
Y
0
,
ζ
,
…
,
ζ
︸
k
+
1
times
for some ζ
∈
(
min
⁡
(
y
1
,
y
2
)
,
max
⁡
(
y
1
,
y
2
)
). Since f
Y
∈
C
n
+
1
(
J
′
) and f
Y
(
n
+
1
) Lipschitz continuous on J
′,f
Y
[
0
,
ζ
,
…
,
ζ
︸
(
k
+
1
)
times
] is bounded on J
′ for k
=
1
,
…
,
n
+
1.
(ii)
Becausef
Y
[
0
,
y
] is Lipschitz continuous on J
′ and the infimum of its absolute value on J
′ is larger than zero, 1
/
(
f
Y
[
0
,
y
]
) is Lipschitz continuous on J
′.
(iii)
If two functionsf
1 and f
2 are Lipschitz continuous and bounded on J
′, then f
1
+
f
2 and f
1
f
2 are also Lipschitz continuous on J
′. This is easy to see for the sum of the two functions. For the product we have
(32)
f
1
y
1
f
2
y
1
-
f
1
y
2
f
2
y
2
=
f
1
y
1
-
f
1
y
2
f
2
y
1
-
f
1
y
2
f
2
y
2
-
f
2
y
1
≤
f
2
y
1
f
1
y
1
-
f
1
y
2
+
f
1
y
2
f
2
y
1
-
f
2
y
2
≤
M
L
1
+
L
2
y
1
-
y
2
,
where M is the maximum of the suprema of f
1 and f
2 on J
′ and L
i is the Lipschitz constant of f
i on J
′.
This concludes the proof.Lemma 4.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
2
(
I
). Let α
∈
I, f
(
α
)
=
0, and f
(
1
)
(
α
)
≠
0. Then K
n
(
x
1
,
…
,
x
n
) as defined in Lemma 3 is continuous in (
x
1
,
…
,
x
n
+
2
)
=
(
α
,
…
,
α
) with
(33)
lim
⁡
x
1
,
…
,
x
n
+
2
→
α
K
n
x
1
,
…
,
x
n
+
2
=
-
1
n
+
1
n
+
1
!
f
1
α
∂
n
+
1
∂
x
n
+
1
1
f
α
,
x
x
=
α
.Proof.
Taking the limit for the numerator of (23) we find
(34)
lim
⁡
y
1
,
…
,
y
n
+
2
→
0
1
f
Y
0
,
y
y
1
,
…
,
y
n
+
2
=
1
n
+
1
!
∂
n
+
1
∂
y
n
+
1
1
f
Y
0
,
y
y
=
0
=
1
n
+
1
!
∂
n
+
1
∂
x
n
+
1
1
f
α
,
x
x
=
α
.
Taking the limit for the denominator D in (26) we obtain
(35)
lim
⁡
y
1
,
…
,
y
n
+
2
→
0
D
y
1
,
…
,
y
n
+
2
=
-
1
n
+
1
f
Y
0,0
=
-
1
n
+
1
f
1
α
.
Dividing the result for numerator by the result for the denominator yields the proof.


## 5. The Algorithm

We construct an algorithm which generates a sequence ofnth order approximants S
n. The algorithm starts with two initial approximants x
-
1 and x
0 of the root α. In the first iteration we simply carry out a Secant step:
(36)
x
-
1
x
0
x
1,0
=
S
x
0
,
x
-
1
.
The second iteration also starts with a Secant step:
(37)
x
-
1
x
0
x
1,0
=
S
x
0
,
x
-
1
x
2,0
=
S
x
1,0
,
x
0
,
but next we combine the two Secant steps in a first-order approximant using the iterative definition of the nth order approximants:
(38)
x
-
1
x
0
x
1,0
=
S
x
0
,
x
-
1
x
2,0
=
S
x
1,0
,
x
0
x
2,1
=
S
1
x
1,0
,
x
0
,
x
-
1
.
The third iteration first carries out a Secant step x
3,0, then combines this Secant step with the previous step x
2,0 in a first-order approximant x
3,1, and finally combines x
2,1 and x
3,1 in a second-order approximant x
3,2:(39)
x
-
1
x
0
x
1,0
=
S
x
0
,
x
-
1
x
2,0
=
S
x
1,0
,
x
0
x
2,1
=
S
1
x
1,0
,
x
0
,
x
-
1
x
3,0
=
S
x
2,1
,
x
1,0
x
3,1
=
S
1
x
2,1
,
x
1,0
,
x
0
x
3,2
=
S
2
x
2,1
,
x
1,0
,
x
0
,
x
-
1
.We continue this way with the fourth and the following iterations and generate a scheme which looks like(40)
x
-
1
x
0
x
1,0
x
2,0
x
2,1
x
3,0
x
3,1
x
3,2
x
4,0
x
4,1
x
4,2
x
4,3
⋮
⋮
⋮
⋮
⋱
x
n
,
0
x
n
,
1
⋯
⋯
⋯
x
n
,
n
-
1
x
n
+
1,0
x
n
+
1,1
⋯
⋯
⋯
x
n
+
1
,
n
-
1
x
n
+
1
,
n
x
n
+
2,0
x
n
+
2,1
⋯
⋯
⋯
x
n
+
2
,
n
-
1
x
n
+
2
,
n
⋮
⋮
⋮
⋮
⋮
⋮
⋮Since we aim at generating a sequence ofnth order approximants, we calculate at most n
+
1 columns in an iteration. The first iteration in which we calculate all n
+
1 columns is the (
n
+
1
)th iteration.If we parametrizex
-
1 as x
-
1,0 and x
0 as x
0,0 we have parametrized all values in our scheme as x
p
,
i with p running over the values p
=
-
1,0
,
1
,
…  and i running over the values i
=
0
,
…
,
i
max
⁡
(
p
) with
(41)
i
max
⁡
p
=
0
,
p
=
-
1,0
,
p
-
1
,
p
=
1
,
…
,
n
,
n
,
p
>
n
.
For simplicity we will denote x
p
,
i
max
⁡
(
p
) by x
p
,
i
max
⁡. This means that, for example, x
p
-
1
,
i
max
⁡ must be read as x
p
-
1
,
i
max
⁡
(
p
-
1
).The choice ofn in (41) sets the order of the algorithm. Choosing n
=
0 results in the Secant algorithm, choosing n
=
1 results in the first-order accelerated Secant algorithm, n
=
2 results in the second-order accelerated Secant algorithm, and so forth. An nth order accelerated Secant algorithm generates a sequence of nth order approximants.The algorithm described above can be formulated as(42)
x
p
,
i
=
S
x
p
-
1
,
i
max
⁡
,
x
p
-
2
,
i
max
⁡
,
i
=
0
,
x
p
-
1
,
i
-
1
x
p
-
1
,
i
max
⁡
-
x
p
,
i
-
1
x
p
-
i
-
2
,
i
max
⁡
x
p
-
1
,
i
-
1
+
x
p
-
1
,
i
max
⁡
-
x
p
,
i
-
1
-
x
p
-
i
-
2
,
i
max
⁡
i
=
1
,
…
,
i
max
⁡
p
,
with start values x
-
1,0 and x
0,0.Note that withx
p
,
0
=
S
(
x
p
-
1
,
i
max
⁡
,
x
p
-
2
,
i
max
⁡
) we have
(43)
x
p
,
1
=
x
p
-
1,0
x
p
-
1
,
i
max
⁡
-
x
p
,
0
x
p
-
3
,
i
max
⁡
x
p
-
1,0
+
x
p
-
1
,
i
max
⁡
-
x
p
,
0
-
x
p
-
3
,
i
max
⁡
=
S
1
x
p
-
1
,
i
max
⁡
,
x
p
-
2
,
i
max
⁡
,
x
p
-
3
,
i
max
⁡
,
and by recursion we easily show that
(44)
x
p
,
i
=
S
i
x
p
-
1
,
i
max
⁡
,
…
,
x
p
-
i
-
2
,
i
max
⁡
for i
=
2
,
…
,
i
max
⁡
(
p
).Each Secant stepS after the first Secant step x
1,0
=
S
(
x
0
,
x
-
1
) requires exactly one evaluation of f. Namely, the calculation of x
p
,
0 requires the calculation f
(
x
p
-
1
,
i
max
⁡
) while f
(
x
p
-
2
,
i
max
⁡
) has already been calculated when we evaluated x
p
-
1,0. The calculation of x
p
,
i for i
>
0 does not require a calculation of f. Hence one iteration of the algorithm requires one evaluation of f, except for the first iteration which requires the evaluation of f
(
x
-
1
) and f
(
x
0
).According to Brezinski and Zaglia [16] it is recommended to calculate the second line in (42) in the following form. It is mathematically equivalent to the second line in (42) but less susceptible to round-off errors according to [16]:
(45)
x
p
,
i
=
x
p
,
i
-
1
+
x
p
-
1
,
i
max
⁡
-
x
p
,
i
-
1
x
p
-
1
,
i
-
1
-
x
p
,
i
-
1
x
p
-
1
,
i
-
1
+
x
p
-
1
,
i
max
⁡
-
x
p
,
i
-
1
-
x
p
-
i
-
2
,
i
max
⁡
for i
=
1
,
…
,
i
max
⁡
(
p
). Alternative forms in which the leading term is x
p
-
1
,
i
-
1, x
p
-
1
,
i
max
⁡, or x
p
-
i
-
2
,
i
max
⁡ are also readily derived.A pseudocode for the accelerated Secant algorithm is provided in AppendixB. Examples of sequences generated by this algorithm are given in the tables in Appendix C.


## 6. Convergence Properties

### 6.1. Basic Convergence

The following lemma establishes sufficient conditions under which the algorithm generates a convergent sequence.Lemma 5.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
1
(
I
). Let f
(
n
+
1
) be Lipschitz continuous on I. Let α
∈
I, f
(
α
)
=
0 and f
(
1
)
(
α
)
≠
0. Then there exists an ϵ
>
0 such that the sequence {
x
p
,
n
}
p
=
n
+
1
∞ generated by the nth order accelerated Secant algorithm converges to α if the start values x
-
1 and x
0 are within a distance ϵ of α.Proof.
We develop our proof in the coordinate frameY. With y
p
,
i
=
x
p
,
i
-
α  (44) reads in the coordinate frame Y:
(46)
y
p
,
i
=
S
Y
i
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
i
-
2
,
i
max
⁡
with
(47)
S
Y
i
y
1
,
…
,
y
i
+
2
=
S
i
α
+
y
1
,
…
,
α
+
y
i
+
2
-
α
.
We have to prove that the sequence {
y
p
,
n
}
p
=
n
+
1
∞ converges to zero if y
-
1 and y
0 are chosen close enough to zero.
Puttingi
=
i
max
⁡ in (46) we obtain a closed recursion for y
p
,
i
max
⁡:
(48)
y
p
,
i
max
⁡
=
S
Y
i
max
⁡
p
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
i
-
2
,
i
max
⁡
.
For p
≥
n
+
1 we have i
max
⁡
(
p
)
=
n and hence
(49)
y
p
,
i
max
⁡
=
S
Y
n
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
n
-
2
,
i
max
⁡
=
∏
j
=
1
n
+
2
y
p
-
j
,
i
max
⁡
K
Y
n
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
n
-
2
,
i
max
⁡
.
Starting at p
=
n
+
1  (49) generates a sequence {
y
p
,
n
}
p
=
n
+
1
∞ from a set of start values V
=
{
y
-
1,0
,
y
0,0
,
y
1,0
,
y
2,1
,
y
3,2
,
…
,
y
n
,
n
-
1
}
=
{
y
p
,
i
max
⁡
∣
p
=
-
1
,
…
,
n
}. It must first be noted that all values in the set can be made arbitrarily small by choosing y
-
1
=
y
-
1,0 and y
0
=
y
0,0 close enough to zero. We can see this for y
1,0 because y
1,0
=
y
-
1
y
0
K
Y
1
(
y
-
1
,
y
0
) and |
K
Y
1
| is bounded in a 2-dimension volume around (
0,0
) according to Lemma 3. In the same way we can see this for y
2,1 because y
2,1
=
y
-
1
y
0
y
1,0
K
Y
2
(
y
-
1
,
y
0
,
y
1,0
) and |
K
Y
2
| is bounded in a 3-dimension volume around (
0,0
,
0
). Continuing the argument we find that all values in the set V can be made arbitrarily small.
Lemma3 states that there is an ϵ
>
0 such that
(50)
K
Y
n
y
1
,
…
,
y
n
+
2
<
K
¯
if |
y
j
|
<
ϵ for all j
=
1
,
…
,
n
+
2. Define the interval J
=
{
y
∈
R
∣
|
y
|
<
min
⁡
(
ϵ
,
K
¯
-
1
/
(
n
+
1
)
)
}. Choose y
-
1 and y
0 small enough such that y
p
,
i
max
⁡
∈
J for all y
p
,
i
max
⁡
∈
V.
From (49) with p
=
n
+
1 we see
(51)
y
n
+
1
,
n
=
∏
j
=
1
n
+
2
y
n
+
1
-
j
,
i
max
⁡
K
Y
n
y
n
,
i
max
⁡
,
…
,
y
-
1
,
i
max
⁡
<
∏
j
=
1
n
+
2
y
n
+
1
-
j
,
i
max
⁡
K
¯
<
y
n
,
i
max
⁡
∏
j
=
2
n
+
2
K
¯
-
1
/
n
+
1
K
¯
=
y
n
,
i
max
⁡
=
y
n
,
n
-
1
.
Since y
n
,
n
-
1
∈
J this guarantees that also y
n
+
1
,
n
∈
J. Repeating the argument recursively we see that |
y
p
+
1
,
n
|
<
|
y
p
,
n
| for all p
≥
n
+
1. This means that the sequence {
|
y
p
,
n
|
}
p
=
n
+
1
∞ is monotonically decreasing. Since it is bounded from below it must converge.
It remains to show that the sequence converges to zero. Suppose|
y
p
,
n
|
→
a
>
0 for p
→
∞. Since |
y
p
,
n
|
∈
J and the sequence is decreasing we must have a
∈
J. From (49) we see |
K
Y
n
(
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
n
-
2
,
i
max
⁡
)
|
≡
K
p
→
a
-
(
n
+
1
) for p
→
∞. However K
p
<
K
¯
<
a
-
(
n
+
1
) where the last inequality follows from the fact a
∈
J. This is a contradiction with K
p
→
a
-
(
n
+
1
) and therefore we must have a
=
0.


### 6.2. Order of Convergence

Our main result regarding the convergence of the sequence generated by the algorithm is the following theorem.Theorem 6.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
2
(
I
). Let α
∈
I, f
(
α
)
=
0, and f
(
1
)
(
α
)
≠
0. Define
(52)
K
∞
n
=
-
1
n
+
1
n
+
1
!
f
1
α
∂
n
+
1
∂
x
n
+
1
1
f
α
,
x
x
=
α
and let K
∞
n
≠
0. Then there is an ϵ
>
0 such that the sequence {
x
p
,
n
}
p
=
n
+
1
∞ generated by the nth order accelerated Secant algorithm converges to α if the start values x
-
1 and x
0 are within a distance ϵ of α. The sequence converges with order ψ
n:
(53)
lim
⁡
p
→
∞
x
p
,
n
-
α
x
p
-
1
,
n
-
α
ψ
n
=
K
∞
n
ψ
n
-
1
/
n
+
1
,
where ψ
n is the real, positive solution of t
n
+
2
-
∑
i
=
0
n
+
1
‍
t
i
=
0.Proof.
First of all note that iff
∈
C
n
+
2
(
I
) then f
∈
C
n
+
1
(
J
) with f
(
n
+
1
) Lipschitz continuous on J for any finite interval J
⊂
I. Convergence of the sequence {
x
p
,
n
}
p
=
n
+
1
∞ is therefore guaranteed by Lemma 5.
Reverting to the coordinate frameY, we see from (49) that
(54)
y
p
,
n
=
∏
j
=
1
n
+
2
y
p
-
j
,
n
K
p
,
n
with
(55)
K
p
,
n
=
K
Y
n
y
p
-
1
,
n
,
…
,
y
p
-
n
-
2
,
n
for p
≥
2
n
+
3. Since lim
⁡
p
→
∞
y
p
,
n
=
0 we have from Lemma 4 that lim
⁡
p
→
∞
K
p
,
n
=
K
∞
n. Therefore we satisfy the conditions of Theorem 3
-
3 in [2]. This theorem proves the result for the order of convergence and the asymptotic error term.Note that the theorem encompasses the convergence property (9) of the Secant sequence for n
=
0.The sequence{
ψ
n
}
n
=
0
∞ is monotonically increasing and converges to 2 [2, 13]. As examples we have ψ
0
=
(
1
+
5
)
/
2
≈
1.6180, ψ
1
≈
1.8393, ψ
2
≈
1.9276, and ψ
3
≈
1.9659.If we define(56)
C
n
=
f
n
α
n
!
f
1
α
we have as examples for K
∞
n
(57)
K
∞
0
=
C
2
,
K
∞
1
=
-
C
3
+
C
2
2
,
K
∞
2
=
C
4
-
2
C
2
C
3
+
C
2
3
.


## 6.1. Basic Convergence

The following lemma establishes sufficient conditions under which the algorithm generates a convergent sequence.Lemma 5.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
1
(
I
). Let f
(
n
+
1
) be Lipschitz continuous on I. Let α
∈
I, f
(
α
)
=
0 and f
(
1
)
(
α
)
≠
0. Then there exists an ϵ
>
0 such that the sequence {
x
p
,
n
}
p
=
n
+
1
∞ generated by the nth order accelerated Secant algorithm converges to α if the start values x
-
1 and x
0 are within a distance ϵ of α.Proof.
We develop our proof in the coordinate frameY. With y
p
,
i
=
x
p
,
i
-
α  (44) reads in the coordinate frame Y:
(46)
y
p
,
i
=
S
Y
i
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
i
-
2
,
i
max
⁡
with
(47)
S
Y
i
y
1
,
…
,
y
i
+
2
=
S
i
α
+
y
1
,
…
,
α
+
y
i
+
2
-
α
.
We have to prove that the sequence {
y
p
,
n
}
p
=
n
+
1
∞ converges to zero if y
-
1 and y
0 are chosen close enough to zero.
Puttingi
=
i
max
⁡ in (46) we obtain a closed recursion for y
p
,
i
max
⁡:
(48)
y
p
,
i
max
⁡
=
S
Y
i
max
⁡
p
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
i
-
2
,
i
max
⁡
.
For p
≥
n
+
1 we have i
max
⁡
(
p
)
=
n and hence
(49)
y
p
,
i
max
⁡
=
S
Y
n
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
n
-
2
,
i
max
⁡
=
∏
j
=
1
n
+
2
y
p
-
j
,
i
max
⁡
K
Y
n
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
n
-
2
,
i
max
⁡
.
Starting at p
=
n
+
1  (49) generates a sequence {
y
p
,
n
}
p
=
n
+
1
∞ from a set of start values V
=
{
y
-
1,0
,
y
0,0
,
y
1,0
,
y
2,1
,
y
3,2
,
…
,
y
n
,
n
-
1
}
=
{
y
p
,
i
max
⁡
∣
p
=
-
1
,
…
,
n
}. It must first be noted that all values in the set can be made arbitrarily small by choosing y
-
1
=
y
-
1,0 and y
0
=
y
0,0 close enough to zero. We can see this for y
1,0 because y
1,0
=
y
-
1
y
0
K
Y
1
(
y
-
1
,
y
0
) and |
K
Y
1
| is bounded in a 2-dimension volume around (
0,0
) according to Lemma 3. In the same way we can see this for y
2,1 because y
2,1
=
y
-
1
y
0
y
1,0
K
Y
2
(
y
-
1
,
y
0
,
y
1,0
) and |
K
Y
2
| is bounded in a 3-dimension volume around (
0,0
,
0
). Continuing the argument we find that all values in the set V can be made arbitrarily small.
Lemma3 states that there is an ϵ
>
0 such that
(50)
K
Y
n
y
1
,
…
,
y
n
+
2
<
K
¯
if |
y
j
|
<
ϵ for all j
=
1
,
…
,
n
+
2. Define the interval J
=
{
y
∈
R
∣
|
y
|
<
min
⁡
(
ϵ
,
K
¯
-
1
/
(
n
+
1
)
)
}. Choose y
-
1 and y
0 small enough such that y
p
,
i
max
⁡
∈
J for all y
p
,
i
max
⁡
∈
V.
From (49) with p
=
n
+
1 we see
(51)
y
n
+
1
,
n
=
∏
j
=
1
n
+
2
y
n
+
1
-
j
,
i
max
⁡
K
Y
n
y
n
,
i
max
⁡
,
…
,
y
-
1
,
i
max
⁡
<
∏
j
=
1
n
+
2
y
n
+
1
-
j
,
i
max
⁡
K
¯
<
y
n
,
i
max
⁡
∏
j
=
2
n
+
2
K
¯
-
1
/
n
+
1
K
¯
=
y
n
,
i
max
⁡
=
y
n
,
n
-
1
.
Since y
n
,
n
-
1
∈
J this guarantees that also y
n
+
1
,
n
∈
J. Repeating the argument recursively we see that |
y
p
+
1
,
n
|
<
|
y
p
,
n
| for all p
≥
n
+
1. This means that the sequence {
|
y
p
,
n
|
}
p
=
n
+
1
∞ is monotonically decreasing. Since it is bounded from below it must converge.
It remains to show that the sequence converges to zero. Suppose|
y
p
,
n
|
→
a
>
0 for p
→
∞. Since |
y
p
,
n
|
∈
J and the sequence is decreasing we must have a
∈
J. From (49) we see |
K
Y
n
(
y
p
-
1
,
i
max
⁡
,
…
,
y
p
-
n
-
2
,
i
max
⁡
)
|
≡
K
p
→
a
-
(
n
+
1
) for p
→
∞. However K
p
<
K
¯
<
a
-
(
n
+
1
) where the last inequality follows from the fact a
∈
J. This is a contradiction with K
p
→
a
-
(
n
+
1
) and therefore we must have a
=
0.


## 6.2. Order of Convergence

Our main result regarding the convergence of the sequence generated by the algorithm is the following theorem.Theorem 6.
LetI
⊂
R be an open interval of real values and f a function f
:
I
→
R with f
∈
C
n
+
2
(
I
). Let α
∈
I, f
(
α
)
=
0, and f
(
1
)
(
α
)
≠
0. Define
(52)
K
∞
n
=
-
1
n
+
1
n
+
1
!
f
1
α
∂
n
+
1
∂
x
n
+
1
1
f
α
,
x
x
=
α
and let K
∞
n
≠
0. Then there is an ϵ
>
0 such that the sequence {
x
p
,
n
}
p
=
n
+
1
∞ generated by the nth order accelerated Secant algorithm converges to α if the start values x
-
1 and x
0 are within a distance ϵ of α. The sequence converges with order ψ
n:
(53)
lim
⁡
p
→
∞
x
p
,
n
-
α
x
p
-
1
,
n
-
α
ψ
n
=
K
∞
n
ψ
n
-
1
/
n
+
1
,
where ψ
n is the real, positive solution of t
n
+
2
-
∑
i
=
0
n
+
1
‍
t
i
=
0.Proof.
First of all note that iff
∈
C
n
+
2
(
I
) then f
∈
C
n
+
1
(
J
) with f
(
n
+
1
) Lipschitz continuous on J for any finite interval J
⊂
I. Convergence of the sequence {
x
p
,
n
}
p
=
n
+
1
∞ is therefore guaranteed by Lemma 5.
Reverting to the coordinate frameY, we see from (49) that
(54)
y
p
,
n
=
∏
j
=
1
n
+
2
y
p
-
j
,
n
K
p
,
n
with
(55)
K
p
,
n
=
K
Y
n
y
p
-
1
,
n
,
…
,
y
p
-
n
-
2
,
n
for p
≥
2
n
+
3. Since lim
⁡
p
→
∞
y
p
,
n
=
0 we have from Lemma 4 that lim
⁡
p
→
∞
K
p
,
n
=
K
∞
n. Therefore we satisfy the conditions of Theorem 3
-
3 in [2]. This theorem proves the result for the order of convergence and the asymptotic error term.Note that the theorem encompasses the convergence property (9) of the Secant sequence for n
=
0.The sequence{
ψ
n
}
n
=
0
∞ is monotonically increasing and converges to 2 [2, 13]. As examples we have ψ
0
=
(
1
+
5
)
/
2
≈
1.6180, ψ
1
≈
1.8393, ψ
2
≈
1.9276, and ψ
3
≈
1.9659.If we define(56)
C
n
=
f
n
α
n
!
f
1
α
we have as examples for K
∞
n
(57)
K
∞
0
=
C
2
,
K
∞
1
=
-
C
3
+
C
2
2
,
K
∞
2
=
C
4
-
2
C
2
C
3
+
C
2
3
.


## 7. Conclusions

We have devised an accelerated Secant algorithm which requires one function evaluation per iteration, does not require the evaluation of a derivative, and can achieve an order of convergence arbitrarily close to two. As such the algorithm is an alternative for the method of inverse interpolation [2] or for Sidi’s method [13]. The accelerated algorithm is not much more complicated than the original Secant algorithm.The algorithm is formulated in (42) but can also be formulated as follows. Start with initial estimates x
-
1
,
…
,
x
n and generate the sequence as x
k
+
1
=
S
n
(
x
k
,
…
,
x
k
-
n
-
1
) with S
n calculated as in, for example, (13) or (19). This formulation shows that the algorithm is a “one-point iteration function with memory” in the classification of Traub [2]. The form (42) seems easier to implement though and requires only two initial estimates.It is possible that our approach can be applied to other algorithms than the Secant algorithm. We think in particular of algorithms generating a sequence{
x
n
} with the property (
x
n
-
α
)
=
K
n
∏
i
=
1
m
‍
(
x
n
-
i
-
α
).We also note that the our algorithm appears to lend itself for parallelization, which is not obvious for algorithms based on polynomial fits. Multiple evaluations off per iteration result in larger orders of convergence [2, 25–28]. It is not hard to see that our first-order algorithm can be modified into a faster converging algorithm in case where two calculation cores are available. It remains to be investigated what the order of convergence is (assuming an order is defined) and whether or not this can be generalized to an arbitrary number of cores.We have only studied the convergent behaviour of the subsequence{
x
p
,
n
}
p
=
n
+
1
∞ of the nth order algorithm. One may wonder about the subsequences {
x
p
,
i
}
p
=
i
+
1
∞ for i
<
n. A study of the first- and second-order accelerated versions of the algorithm [29] revealed that they converge with the same order as {
x
p
,
n
}
p
=
n
+
1
∞ but with a different asymptotic error term. This is likely the case for all orders of the algorithm.A different approach to judge the efficiency of the algorithm is to estimate the average computational cost of the algorithm by statistical means [30]. In this approach one averages the cost over a set of functions with a suitable probability measure. Although interesting, such a study is outside of the scope of the current article.



---

*Source: 321592-2014-11-19.xml*