# Polynomial and Rational Approximations and the Link between Schröder’s Processes of the First and Second Kind

Authors: François Dubeau
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We show that Schröder’s processes of the first kind and of the second kind to obtain a simple root of a nonlinear equation are related by polynomial and rational approximations.


---

## Body

## 1. Introduction

In [1, 2], Schröder proposed two fixed point processes to find a simple root α of a nonlinear equation f
(
x
)
=
0. These two processes have been reconsidered in Kalantari et al. [3] and Kalantari [4] from a modern point of view. Iteration functions (IF) of arbitrary order p
≥
2 associated with the two processes will be noted E
p
(
x
) for Schröder’s process of the first kind and S
p
(
x
) for Schröder’s process of the second kind.Order2 processes are
(1)
E
2
(
x
)
=
S
2
(
x
)
=
N
f
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
,
where N
f
(
x
) is the Newton's IF, and order p
>
2 processes can be expressed as
(2)
E
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
Λ
p
-
2
(
ξ
)
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
,
S
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
[
Γ
p
-
3
(
ξ
)
Γ
p
-
2
(
ξ
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
,
where Λ
q
(
ξ
) and Γ
q
(
ξ
) are polynomials of degree q
≥
0, such that Λ
q
(
0
)
=
1
=
Γ
q
(
0
).A question raised and discussed in [3–6] is to find and explain a possible link between the two processes. The main result of this paper is to show that E
p
(
x
) is a polynomial approximation of S
p
(
x
), and S
p
(
x
) is a rational approximation of E
p
(
x
). More precisely, we explain the relation between the polynomials Λ
p
-
2
(
ξ
), Γ
p
-
3
(
ξ
), and Γ
p
-
2
(
ξ
) in (2). This paper completes the work done previously in [3–6].Other links or comparisons could be established between these two families, for example, between their basins of attraction, their asymptotic constants, and their complexities. First results in these directions appeared in [7, 8], for example, but are not the object of the present paper.In the next section we present notations and definitions used in this paper. Sections3 and 4 present the two processes of Schröder and their corresponding polynomials Λ
q
(
ξ
) and Γ
q
(
ξ
). We prove the main result in the last section.


## 2. Preliminaries

Througout the paper we consider real valued functions which are regular enough to be differentiated sufficiently many times. Thelth derivative will be noted f
(
l
)
(
x
) for l
=
1,2
,
…. We will use the notation g
(
x
)
=
O
(
f
(
x
)
) (and g
(
x
)
=
o
(
f
(
x
)
)) for two functions f
(
x
) and g
(
x
) defined around x
=
α, when the following limit exists (and is finite):
(3)
lim
⁡
x
→
α
g
(
x
)
f
(
x
)
=
c
for c
≠
0 (for c
=
0, resp.).Letα be a fixed point of an IF Φ
(
x
), and let the sequence {
x
k
+
1
=
Φ
(
x
k
)
}
k
=
0
+
∞ converge to α. Let p be a positive integer such that the following limit exists (and is finite):
(4)
x
k
+
1
-
α
(
x
k
-
α
)
p
→
k
→
+
∞
K
p
(
α
;
Φ
)
.
We say that the convergence of the sequence to α is of (integer) order p if and only if K
p
(
α
;
Φ
)
≠
0. We also say that Φ
(
x
) is of order p.Letα be a simple root of f
(
x
), which means that f
(
α
)
=
0 and f
(
1
)
(
α
)
≠
0; then g
(
x
)
=
O
(
(
x
-
α
)
p
) is equivalent to g
(
x
)
=
O
(
f
p
(
x
)
) or g
(
x
)
=
O
(
(
f
/
f
(
1
)
)
p
(
x
)
). Moreover if α is a fixed point of an IF Φ
p
(
x
) of order p, then we can write [9]
(5)
Φ
p
(
x
)
=
α
+
O
(
(
x
-
α
)
p
)
=
α
+
O
(
f
p
(
x
)
)
=
α
+
O
(
(
f
f
(
1
)
)
p
(
x
)
)
.


## 3. Schröder’s Process of the First Kind

### 3.1. The Process

Schröder’s process of the first kind, proposed to increase the order of convergence of a fixed-point method [1–3, 9, 10], can be obtained by considering Taylor’s expansion of the inverse g
(
y
) of f
(
x
) around y
=
0 [9]. It is also associated with Chebyshev and Euler [11–13]. The IF E
p
(
x
) of order p is defined by the series
(6)
E
p
(
x
)
=
x
+
∑
l
=
1
p
-
1
‍
c
l
(
x
)
f
l
(
x
)
=
∑
l
=
0
p
-
1
‍
c
l
(
x
)
f
l
(
x
)
,
where c
0
(
x
)
=
x and
(7)
c
l
(
x
)
=
-
1
l
(
1
f
(
1
)
(
x
)
d
d
x
)
c
l
-
1
(
x
)
=
(
-
1
)
l
l
!
(
1
f
(
1
)
(
x
)
d
d
x
)
l
c
0
(
x
)
for l
=
1,2
,
….Relation (7) implies that c
l
(
x
) is a rational function of the form
(8)
c
l
(
x
)
=
(
1
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
)
(
x
)
polynomial
of
degree
l
-
1
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
)
(
x
)
)
×
(
[
f
(
1
)
(
x
)
]
2
l
-
1
)
-
1
.
Then we can write
(9)
E
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
Λ
p
-
2
(
ξ
)
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
,
where
(10)
Λ
p
-
2
(
ξ
)
=
∑
l
=
0
p
-
2
‍
λ
l
(
x
)
ξ
l
,
(11)
λ
l
(
x
)
=
{
1
for
l
=
0
,
-
[
f
(
1
)
(
x
)
]
l
l
+
1
d
d
x
(
λ
l
-
1
(
x
)
[
f
(
1
)
(
x
)
]
l
)
for
l
≥
1
.
Consequently
(12)
λ
l
(
x
)
=
(
(
[
f
(
1
)
(
x
)
]
l
)
-
1
{
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
polynomial
of
degree
l
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
}
×
(
[
f
(
1
)
(
x
)
]
l
)
-
1
)
.


### 3.2. Examples

The first4 IFs are given here. For(a)
p
=
2:
(13)
E
2
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
,
which corresponds to Newton’s IF of order 2;
(b)
p
=
3:
(14)
E
3
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
-
1
2
!
f
(
2
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
,
which corresponds to Chebyshev’s IF order 3 [11];
(c)
p
=
4:
(15)
E
4
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
-
1
2
!
f
(
2
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
-
1
3
!
[
3
[
f
(
2
)
(
x
)
]
2
-
f
(
1
)
(
x
)
f
(
3
)
(
x
)
[
f
(
1
)
(
x
)
]
2
]
×
[
f
(
x
)
f
(
1
)
(
x
)
]
3
;
(d)
p
=
5:
(16)
E
5
(
x
)
=
x
-
1
f
(
1
)
(
x
)
f
(
x
)
-
1
2
!
f
(
2
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
-
1
3
!
[
3
[
f
(
2
)
(
x
)
]
2
-
f
(
1
)
(
x
)
f
(
3
)
(
x
)
[
f
(
1
)
(
x
)
]
2
]
×
[
f
(
x
)
f
(
1
)
(
x
)
]
3
-
1
4
!
[
[
f
(
1
)
(
x
)
]
2
f
(
4
)
(
x
)
[
f
(
1
)
(
x
)
]
3
+
15
[
f
(
2
)
(
x
)
]
3
[
f
(
1
)
(
x
)
]
3
-
10
f
(
1
)
(
x
)
f
(
2
)
(
x
)
f
(
3
)
(
x
)
[
f
(
1
)
(
x
)
]
3
]
×
[
f
(
x
)
f
(
1
)
(
x
)
]
4
.


## 3.1. The Process

Schröder’s process of the first kind, proposed to increase the order of convergence of a fixed-point method [1–3, 9, 10], can be obtained by considering Taylor’s expansion of the inverse g
(
y
) of f
(
x
) around y
=
0 [9]. It is also associated with Chebyshev and Euler [11–13]. The IF E
p
(
x
) of order p is defined by the series
(6)
E
p
(
x
)
=
x
+
∑
l
=
1
p
-
1
‍
c
l
(
x
)
f
l
(
x
)
=
∑
l
=
0
p
-
1
‍
c
l
(
x
)
f
l
(
x
)
,
where c
0
(
x
)
=
x and
(7)
c
l
(
x
)
=
-
1
l
(
1
f
(
1
)
(
x
)
d
d
x
)
c
l
-
1
(
x
)
=
(
-
1
)
l
l
!
(
1
f
(
1
)
(
x
)
d
d
x
)
l
c
0
(
x
)
for l
=
1,2
,
….Relation (7) implies that c
l
(
x
) is a rational function of the form
(8)
c
l
(
x
)
=
(
1
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
)
(
x
)
polynomial
of
degree
l
-
1
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
)
(
x
)
)
×
(
[
f
(
1
)
(
x
)
]
2
l
-
1
)
-
1
.
Then we can write
(9)
E
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
Λ
p
-
2
(
ξ
)
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
,
where
(10)
Λ
p
-
2
(
ξ
)
=
∑
l
=
0
p
-
2
‍
λ
l
(
x
)
ξ
l
,
(11)
λ
l
(
x
)
=
{
1
for
l
=
0
,
-
[
f
(
1
)
(
x
)
]
l
l
+
1
d
d
x
(
λ
l
-
1
(
x
)
[
f
(
1
)
(
x
)
]
l
)
for
l
≥
1
.
Consequently
(12)
λ
l
(
x
)
=
(
(
[
f
(
1
)
(
x
)
]
l
)
-
1
{
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
polynomial
of
degree
l
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
}
×
(
[
f
(
1
)
(
x
)
]
l
)
-
1
)
.


## 3.2. Examples

The first4 IFs are given here. For(a)
p
=
2:
(13)
E
2
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
,
which corresponds to Newton’s IF of order 2;
(b)
p
=
3:
(14)
E
3
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
-
1
2
!
f
(
2
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
,
which corresponds to Chebyshev’s IF order 3 [11];
(c)
p
=
4:
(15)
E
4
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
-
1
2
!
f
(
2
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
-
1
3
!
[
3
[
f
(
2
)
(
x
)
]
2
-
f
(
1
)
(
x
)
f
(
3
)
(
x
)
[
f
(
1
)
(
x
)
]
2
]
×
[
f
(
x
)
f
(
1
)
(
x
)
]
3
;
(d)
p
=
5:
(16)
E
5
(
x
)
=
x
-
1
f
(
1
)
(
x
)
f
(
x
)
-
1
2
!
f
(
2
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
-
1
3
!
[
3
[
f
(
2
)
(
x
)
]
2
-
f
(
1
)
(
x
)
f
(
3
)
(
x
)
[
f
(
1
)
(
x
)
]
2
]
×
[
f
(
x
)
f
(
1
)
(
x
)
]
3
-
1
4
!
[
[
f
(
1
)
(
x
)
]
2
f
(
4
)
(
x
)
[
f
(
1
)
(
x
)
]
3
+
15
[
f
(
2
)
(
x
)
]
3
[
f
(
1
)
(
x
)
]
3
-
10
f
(
1
)
(
x
)
f
(
2
)
(
x
)
f
(
3
)
(
x
)
[
f
(
1
)
(
x
)
]
3
]
×
[
f
(
x
)
f
(
1
)
(
x
)
]
4
.


## 4. Schröder’s Process of the Second Kind

### 4.1. The Process

Different equivalent formulations exist for Schröder’s process of the second kind [4, 6, 13, 14]. One such form is based on a determinental identity. Let Δ
0
(
x
)
=
1 and for p
≥
1
(17)
Δ
p
(
x
)
=
|
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
⋯
⋯
⋯
f
(
p
)
(
x
)
p
!
f
(
x
)
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
⋯
⋯
f
(
p
-
1
)
(
x
)
(
p
-
1
)
!
0
f
(
x
)
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
⋯
f
(
p
-
2
)
(
x
)
(
p
-
2
)
!
⋮
⋱
⋱
⋱
⋱
⋮
0
⋯
0
f
(
x
)
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
0
⋯
⋯
0
f
(
x
)
f
(
1
)
(
x
)
|
.
Expanding this determinant along the first line, we obtain
(18)
Δ
p
(
x
)
=
∑
j
=
1
p
‍
(
-
1
)
j
+
1
f
(
j
)
(
x
)
j
!
f
j
-
1
(
x
)
Δ
p
-
j
(
x
)
for p
≥
1. Using R
p
(
x
)
=
Δ
p
(
x
)
/
f
p
+
1
(
x
), Schröder’s process of the second kind [1, 2] of order p is defined by
(19)
S
p
(
x
)
=
x
-
R
p
-
2
(
x
)
R
p
-
1
(
x
)
=
x
-
f
(
x
)
Δ
p
-
2
(
x
)
Δ
p
-
1
(
x
)
.We prove by mathematical induction that(20)
Δ
p
(
x
)
=
(
-
1
)
p
f
p
+
1
(
x
)
p
!
(
1
f
(
x
)
)
(
p
)
,
f
(
x
)
Δ
p
-
1
(
1
)
(
x
)
=
p
f
(
1
)
(
x
)
Δ
p
-
1
(
x
)
-
p
Δ
p
(
x
)
.Using(21)
(
1
f
(
x
)
)
(
p
)
=
∑
l
=
2
p
+
1
‍
d
p
,
l
(
x
)
(
1
f
(
x
)
)
l
,
then we have d
1,2
(
x
)
=
-
f
(
1
)
(
x
), and we can obtain recursively d
p
,
l
(
x
) for p
≥
2 by the formulae
(22)
d
p
,
l
(
x
)
=
{
d
p
-
1
,
l
(
1
)
(
x
)
for
l
=
2
,
d
p
-
1
,
l
(
1
)
(
x
)
-
(
l
-
1
)
d
p
-
1
,
l
-
1
(
x
)
f
(
1
)
(
x
)
for
l
=
3
,
…
,
p
,
-
p
d
p
-
1
,
p
(
x
)
f
(
1
)
(
x
)
for
l
=
p
+
1
.
Consequently
(23)
d
p
,
l
(
x
)
=
{
-
f
(
p
)
(
x
)
,
for
l
=
2
,
{
f
(
2
)
(
x
)
,
…
,
f
(
p
+
2
-
l
)
(
x
)
}
polynomial
of
degree
l
-
1
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
p
+
2
-
l
)
(
x
)
}
for
l
=
3
,
…
,
p
,
(
-
1
)
p
p
!
[
f
(
1
)
(
x
)
]
p
for
l
=
p
+
1
.
It follows that Δ
p
(
x
) is a polynomial of degree p
-
1 with respect to f
(
x
) and the term not depending on f
(
x
) is [
f
(
1
)
(
x
)
]
p. Hence
(24)
Δ
p
(
x
)
=
[
f
(
1
)
(
x
)
]
p
Γ
p
-
1
(
ξ
)
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
,
where Γ
p
-
1
(
ξ
) is a polynomial of degree p
-
1 such that Γ
p
-
1
(
0
)
=
1. Let us set
(25)
Γ
p
-
1
(
ξ
)
=
∑
l
=
0
p
-
1
‍
γ
p
-
1
,
l
(
x
)
ξ
l
,
where the coefficients γ
p
-
1
,
l
(
x
) are rational functions of the form
(26)
γ
p
-
1
,
l
(
x
)
=
(
-
1
)
p
d
p
,
p
+
1
-
l
(
x
)
p
!
[
f
(
1
)
(
x
)
]
p
-
l
(27)
=
(
(
[
f
(
1
)
(
x
)
]
p
-
l
)
-
1
{
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
polynomial
of
degree
p
-
l
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
}
×
(
[
f
(
1
)
(
x
)
]
p
-
l
)
-
1
)
.
Then we obtain
(28)
S
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
[
Γ
p
-
3
(
ξ
)
Γ
p
-
2
(
ξ
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
.


### 4.2. Examples

The first4 IFs are presented here. For(a)
p
=
2:
(29)
S
2
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
,
which corresponds to Newton’s IF of order 2;
(b)
p
=
3:
(30)
S
3
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
×
[
1
1
-
(
1
/
2
)
(
f
(
2
)
(
x
)
/
f
(
1
)
(
x
)
)
(
f
(
x
)
/
f
(
1
)
(
x
)
)
]
,
which is Halley’s IF of order 3 [15];
(c)
p
=
4:
(31)
S
4
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
×
[
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
-
1
(
1
-
1
2
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
)
×
(
[
f
(
x
)
f
(
1
)
(
x
)
]
2
1
-
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
-
1
]
;
(d)
p
=
5:
(32)
S
5
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
×
[
-
1
4
!
f
(
4
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
3
)
-
1
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
-
1
(
[
f
(
x
)
f
(
1
)
(
x
)
]
2
1
-
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
×
(
-
1
4
!
f
(
4
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
3
)
1
-
3
2
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
+
[
1
3
f
(
3
)
(
x
)
f
(
1
)
(
x
)
+
1
4
[
f
(
2
)
(
x
)
f
(
1
)
(
x
)
]
2
]
[
f
(
x
)
f
(
1
)
(
x
)
]
2
-
1
4
!
f
(
4
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
3
)
-
1
]
.


## 4.1. The Process

Different equivalent formulations exist for Schröder’s process of the second kind [4, 6, 13, 14]. One such form is based on a determinental identity. Let Δ
0
(
x
)
=
1 and for p
≥
1
(17)
Δ
p
(
x
)
=
|
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
⋯
⋯
⋯
f
(
p
)
(
x
)
p
!
f
(
x
)
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
⋯
⋯
f
(
p
-
1
)
(
x
)
(
p
-
1
)
!
0
f
(
x
)
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
⋯
f
(
p
-
2
)
(
x
)
(
p
-
2
)
!
⋮
⋱
⋱
⋱
⋱
⋮
0
⋯
0
f
(
x
)
f
(
1
)
(
x
)
f
(
2
)
(
x
)
2
!
0
⋯
⋯
0
f
(
x
)
f
(
1
)
(
x
)
|
.
Expanding this determinant along the first line, we obtain
(18)
Δ
p
(
x
)
=
∑
j
=
1
p
‍
(
-
1
)
j
+
1
f
(
j
)
(
x
)
j
!
f
j
-
1
(
x
)
Δ
p
-
j
(
x
)
for p
≥
1. Using R
p
(
x
)
=
Δ
p
(
x
)
/
f
p
+
1
(
x
), Schröder’s process of the second kind [1, 2] of order p is defined by
(19)
S
p
(
x
)
=
x
-
R
p
-
2
(
x
)
R
p
-
1
(
x
)
=
x
-
f
(
x
)
Δ
p
-
2
(
x
)
Δ
p
-
1
(
x
)
.We prove by mathematical induction that(20)
Δ
p
(
x
)
=
(
-
1
)
p
f
p
+
1
(
x
)
p
!
(
1
f
(
x
)
)
(
p
)
,
f
(
x
)
Δ
p
-
1
(
1
)
(
x
)
=
p
f
(
1
)
(
x
)
Δ
p
-
1
(
x
)
-
p
Δ
p
(
x
)
.Using(21)
(
1
f
(
x
)
)
(
p
)
=
∑
l
=
2
p
+
1
‍
d
p
,
l
(
x
)
(
1
f
(
x
)
)
l
,
then we have d
1,2
(
x
)
=
-
f
(
1
)
(
x
), and we can obtain recursively d
p
,
l
(
x
) for p
≥
2 by the formulae
(22)
d
p
,
l
(
x
)
=
{
d
p
-
1
,
l
(
1
)
(
x
)
for
l
=
2
,
d
p
-
1
,
l
(
1
)
(
x
)
-
(
l
-
1
)
d
p
-
1
,
l
-
1
(
x
)
f
(
1
)
(
x
)
for
l
=
3
,
…
,
p
,
-
p
d
p
-
1
,
p
(
x
)
f
(
1
)
(
x
)
for
l
=
p
+
1
.
Consequently
(23)
d
p
,
l
(
x
)
=
{
-
f
(
p
)
(
x
)
,
for
l
=
2
,
{
f
(
2
)
(
x
)
,
…
,
f
(
p
+
2
-
l
)
(
x
)
}
polynomial
of
degree
l
-
1
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
p
+
2
-
l
)
(
x
)
}
for
l
=
3
,
…
,
p
,
(
-
1
)
p
p
!
[
f
(
1
)
(
x
)
]
p
for
l
=
p
+
1
.
It follows that Δ
p
(
x
) is a polynomial of degree p
-
1 with respect to f
(
x
) and the term not depending on f
(
x
) is [
f
(
1
)
(
x
)
]
p. Hence
(24)
Δ
p
(
x
)
=
[
f
(
1
)
(
x
)
]
p
Γ
p
-
1
(
ξ
)
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
,
where Γ
p
-
1
(
ξ
) is a polynomial of degree p
-
1 such that Γ
p
-
1
(
0
)
=
1. Let us set
(25)
Γ
p
-
1
(
ξ
)
=
∑
l
=
0
p
-
1
‍
γ
p
-
1
,
l
(
x
)
ξ
l
,
where the coefficients γ
p
-
1
,
l
(
x
) are rational functions of the form
(26)
γ
p
-
1
,
l
(
x
)
=
(
-
1
)
p
d
p
,
p
+
1
-
l
(
x
)
p
!
[
f
(
1
)
(
x
)
]
p
-
l
(27)
=
(
(
[
f
(
1
)
(
x
)
]
p
-
l
)
-
1
{
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
polynomial
of
degree
p
-
l
w
.
r
.
t
.
f
(
1
)
(
x
)
,
f
(
2
)
(
x
)
,
…
,
f
(
l
+
1
)
(
x
)
}
×
(
[
f
(
1
)
(
x
)
]
p
-
l
)
-
1
)
.
Then we obtain
(28)
S
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
[
Γ
p
-
3
(
ξ
)
Γ
p
-
2
(
ξ
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
.


## 4.2. Examples

The first4 IFs are presented here. For(a)
p
=
2:
(29)
S
2
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
,
which corresponds to Newton’s IF of order 2;
(b)
p
=
3:
(30)
S
3
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
×
[
1
1
-
(
1
/
2
)
(
f
(
2
)
(
x
)
/
f
(
1
)
(
x
)
)
(
f
(
x
)
/
f
(
1
)
(
x
)
)
]
,
which is Halley’s IF of order 3 [15];
(c)
p
=
4:
(31)
S
4
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
×
[
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
-
1
(
1
-
1
2
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
)
×
(
[
f
(
x
)
f
(
1
)
(
x
)
]
2
1
-
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
-
1
]
;
(d)
p
=
5:
(32)
S
5
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
×
[
-
1
4
!
f
(
4
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
3
)
-
1
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
-
1
(
[
f
(
x
)
f
(
1
)
(
x
)
]
2
1
-
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
+
1
3
!
f
(
3
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
2
)
×
(
-
1
4
!
f
(
4
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
3
)
1
-
3
2
f
(
2
)
(
x
)
f
(
1
)
(
x
)
f
(
x
)
f
(
1
)
(
x
)
+
[
1
3
f
(
3
)
(
x
)
f
(
1
)
(
x
)
+
1
4
[
f
(
2
)
(
x
)
f
(
1
)
(
x
)
]
2
]
[
f
(
x
)
f
(
1
)
(
x
)
]
2
-
1
4
!
f
(
4
)
(
x
)
f
(
1
)
(
x
)
[
f
(
x
)
f
(
1
)
(
x
)
]
3
)
-
1
]
.


## 5. Proof of the Main Result

Since both processesE
p
(
x
) and S
p
(
x
) are of order p, following [9], the next result holds.Lemma 1.
Letα be a simple root of f
(
x
); then
(33)
E
p
(
x
)
-
S
p
(
x
)
=
O
(
f
p
(
x
)
)
=
O
(
(
f
(
x
)
f
(
1
)
(
x
)
)
p
)
.From this lemma(34)
f
(
x
)
f
(
1
)
(
x
)
[
Λ
p
-
2
(
ξ
)
-
Γ
p
-
3
(
ξ
)
Γ
p
-
2
(
ξ
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
=
O
(
(
f
(
x
)
f
(
1
)
(
x
)
)
p
)
,
and so
(35)
[
Λ
p
-
2
(
ξ
)
-
Γ
p
-
3
(
ξ
)
Γ
p
-
2
(
ξ
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
=
O
(
(
f
(
x
)
f
(
1
)
(
x
)
)
p
-
1
)
.The next step is to consider the following basic result about polynomial and rational approximations.Lemma 2.
Let us consider the expression(36)
Λ
p
(
ξ
)
=
Γ
p
-
1
(
ξ
)
Γ
p
(
ξ
)
+
O
(
ξ
p
+
1
)
,
where Λ
p
(
ξ
) and Γ
p
(
ξ
) are polynomials of degree p such that Λ
p
(
0
)
=
1
=
Γ
p
(
0
).(a)
IfΓ
p
-
1
(
ξ
) and Γ
p
(
ξ
) are given, there exists one and only one polynomial Λ
p
(
ξ
) such that (36) holds.
(b)
IfΓ
p
-
1
(
ξ
) and Λ
p
(
ξ
) are given, there exists one and only one polynomial Γ
p
(
ξ
) such that (36) holds.Proof.
This result is based on the following identity:(37)
Γ
p
-
1
(
ξ
)
Γ
p
(
ξ
)
=
Γ
p
-
1
(
ξ
)
1
-
(
1
-
Γ
p
(
ξ
)
)
=
Γ
p
-
1
(
ξ
)
∑
l
=
0
+
∞
‍
(
1
-
Γ
p
(
ξ
)
)
l
=
Γ
p
-
1
(
ξ
)
∑
l
=
0
p
‍
(
1
-
Γ
p
(
ξ
)
)
l
+
O
(
ξ
p
+
1
)
,
and we would like to have
(38)
Λ
p
(
ξ
)
=
Γ
p
-
1
(
ξ
)
∑
l
=
0
p
‍
(
1
-
Γ
p
(
ξ
)
)
l
+
O
(
ξ
p
+
1
)
.
We know that λ
0
=
γ
p
-
1,0
=
γ
p
,
0
=
1. Moreover the coefficient of ξ
l on the left-hand side is λ
l and on the right-hand side is
(39)
γ
p
,
l
+
an
expression
in
terms
of
{
γ
p
-
1
,
j
for
j
=
0
,
…
,
l
,
γ
p
,
j
for
j
=
0
,
…
,
l
-
1
for l
=
1
,
…
,
p. This expression shows that if the γ
p’s and the γ
p
-
1’s are given, we can obtain λ
p’s, and conversely if the λ
p’s and the γ
p
-
1’s are given, we can obtain the γ
p’s.In view of these two lemmas we obtain the main result of this paper.Theorem 3.
E
p
(
x
) and S
p
(
x
) are related as follows.(a)
ForS
p
(
x
) given by (28), one can obtain the form (9) of E
p
(
x
) by expanding the denominator in (28), multiplying, and truncating to keep powers of f
(
x
)
/
f
(
1
)
(
x
) up to p
-
1.
(b)
SinceS
2
(
x
)
=
E
2
(
x
)
=
N
f
(
x
), one can obtain recursively S
p
(
x
) given by (28) from E
p
(
x
) given by (9).Proof.
(a) Indeed, ifS
p
(
x
) is given, which means we know Γ
p
-
3
(
ξ
) and Γ
p
-
2
(
ξ
), we can write
(40)
S
p
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
[
Γ
p
-
3
(
ξ
)
Γ
p
-
2
(
ξ
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
[
Γ
p
-
3
(
ξ
)
1
-
(
1
-
Γ
p
-
2
(
ξ
)
)
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
[
Γ
p
-
3
(
ξ
)
∑
l
=
0
p
-
2
‍
(
1
-
Γ
p
-
2
(
ξ
)
)
l
+
O
(
ξ
p
-
1
)
Γ
p
-
3
(
ξ
)
∑
l
=
0
p
-
2
‍
(
1
-
Γ
p
-
2
(
ξ
)
)
l
]
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
=
x
-
f
(
x
)
f
(
1
)
(
x
)
Λ
p
-
2
(
ξ
)
|
ξ
=
f
(
x
)
/
f
(
1
)
(
x
)
+
O
(
f
p
(
x
)
)
=
E
p
(
x
)
+
O
(
f
p
(
x
)
)
,
which follows from part (a) of Lemma 1.
(b) As already observed,E
2
(
x
)
=
S
2
(
x
)
=
N
f
(
x
). If, for p
>
2, we have S
p
-
1
(
x
), and we know Γ
p
-
4
(
ξ
) and Γ
p
-
3
(
ξ
), and E
p
(
x
), and we know also Λ
p
-
2
(
ξ
), then we can determine Γ
p
-
2
(
ξ
) from part (b) of Lemma 1. Consequently we obtain S
p
(
x
).The computation of the polynomialsΛ
p
(
ξ
) and Γ
p
(
ξ
), and their coefficients λ
p’s and the γ
p’s, can be done explicitely using (11) for the λ
p’s and (22) and (26) for the γ
p’s. The verification of the link between the two Schröder’s processes has already been done using symbolic computation up to order 20 [5, 6].



---

*Source: 719846-2014-05-07.xml*