1. Introduction and Preliminaries
Let
be a normed field and
be an arbitrary function. It is well known that one of the most commonly used tools for finding the zeros of
f is the Picard iteration
where
is some iteration function (see, e.g., Traub [
1]). Although the Picard iteration is an old method, it still draws strong interest as a powerful tool for solving a wide range of mathematical problems (see e.g., [
2,
3,
4] and references therein). Nowadays, there are a plethora of convergence results about the iterative methods of the type (
1) but the proofs are often based on Taylor’s expansions or other methods that require the existence of higher-order derivatives of
f and ensure only asymptotic error constants where available. Moreover, the most of the existing convergence theorems do not provide exact information about the sets of initial approximations that guarantee the convergence of the iteration (
1) (see e.g., [
5,
6,
7] and the references therein).
In the last decade, a general convergence theory of the Picard iteration (
1) in cone metric spaces and in
n-dimensional vector spaces has been developed by Proinov [
8,
9,
10,
11]. The main role in this theory is played by a real-valued function called function of initial conditions of the iteration function
T. Following the ideas of Proinov [
11], in this paper we make two contributions. First, in
Section 2, using two different functions of initial conditions we prove two general local convergence theorems (Theorem 1 and Theorem 2) that provide domains of initial approximations (convergence domains) to guarantee the convergence of the Picard iteration (
1) with a priori and a posteriori error estimates right from the first step. In this manner, we reduce the convergence analysis of (
1) up to studying of some simple properties of the iteration function
T. Second, applying this general approach, in
Section 3 we obtain two new local convergence theorems with error estimates (Theorem 3 and Theorem 4) about the Super-Halley method for approximation of polynomial zeros with known multiplicity
m. The obtained theorems are new even in the case of simple zeros (
).
In the remainder of this section, we recall some definitions and theorems of Proinov [
9,
12] which are crucial for the proof of the upcoming results.
Furthermore,
J always denotes an interval on
containing 0 and we assume that
. Also, we denote by
the sum of the first
k terms of geometric sequence
, i.e., for all
, we have
In the case
, we set
.
Definition 1 ([
9] Definition 2.1).
A function is called quasi-homogeneous of degree if it is such that for all and . Recall some simple but useful properties of the quasi-homogeneous functions.
- (P1)
A function f is quasi-homogeneous of degree on some interval J if and only if f is nondecreasing on J;
- (P2)
If a function f is quasi-homogeneous of degree p on J, then there exists a nondecreasing function such that ;
- (P3)
If g and h are quasi-homogeneous of degree and on J, then is quasi-homogeneous of degree on J.
Definition 2 ([
9] Definition 2.4).
A function is said to be a gauge function
of order on J if it satisfies the following conditions:- (i)
φ is a quasi-homogeneous function of degree p on J;
- (ii)
for all .
A gauge function φ of order p on J is said to be a strict gauge function if the inequality (ii) holds strictly whenever .
Definition 3 ([
9] Definition 3.1).
Let be a map on an arbitrary set X. A function is said to be a function of initial conditions of T (with gauge function φ on an interval J) if there exists a function such that Definition 4 ([
9] Definition 3.2).
Let be a map on an arbitrary set X. Suppose is a function of initial conditions of T (with gauge function on an interval J). Then a point is said to be an initial point
of T if and all of the iterates are well defined and belong to D. The next theorem provides a sufficient condition for initial points.
Proposition 1 ([
9] Proposition 4.1).
Let be a map on a set X, and let be a function of initial conditions of T with a gauge function φ on J. Suppose thatThen every point such that is an initial point of T. Proposition 2 ([
12] Lemma 3.6).
For every initial point of T and every , we haveIn addition, if φ is a gauge function of order , thenwhere and ϕ is a non-negative and nondecreasing function on J such that for all . 2. General Local Convergence Theorems
Let
be an arbitrary iteration function. In this section, we present two general theorems about the local convergence of the Picard iteration (
1). The first one (Theorem 1) is a case of Theorem 3.1 of Proinov [
11] but provides an extra error estimate that ensures the
Q-order of convergence of the Picard iteration (
1) (see, e.g., [
13]). The second theorem (Theorem 2) is of bit more practical importance than Theorem 1 since there is less unknown information involved into the initial conditions and error estimates.
Let
be an arbitrary function which has at least one zero in
. For two points
, we define the functions
and
by
where
d denotes the distance between
and the nearest zero of
f and
is the radius of a disk with center
x that not contains zeros of
f. If
is a zero of
f and it is unique, then we set
. In this case, we assume that
. Also, we observe that the domain of
is the set
We have to note that usually
is a zero of
f but we do not assume this in Theorem 1 and Theorem 2.
The following theorem is our first main result.
Theorem 1. Let be an iteration function, and be defined by (2). Suppose is a quasi-homogeneous function of degree such that for each with , the following two conditions are satisfied: - (a)
- (b)
.
Also, let be an initial approximation such thatthen the following statements hold: - (i)
The Picard iteration (1) is well defined and converges to ξ with order . - (ii)
For all , we have the following error estimates: where .
- (iii)
The Picard iteration (1) converges to ξ with Q-order and with the following error estimate: where R is the minimal solution of the equation in the interval .
Proof. The claims (i) and (ii) follow from Theorem 3.1 of Proinov [
11] in the one dimensional case. So, it remains to prove the estimate (iii).
By (i) and (ii), for all
we have
, where
Since,
is a quasi-homogeneous function of degree
, then by (P2) it follows that there exists a nondecreasing function
such that
. This together with
implies that
. Hence, from conditions (a) and (b), for all
we get
Now, setting
and
in the last inequality, we get the estimate of (iii) which implies that the Picard iteration (
1) converges to
with
Q-order
and completes the proof. □
In what follows, for a nondecreasing function
, we define the function
by
If the function
is positive, then we can define the function
by
The second main result of this paper is represented by the following theorem:
Theorem 2. Let be an iteration function, and be defined by (2). Suppose is a nonzero quasi-homogeneous function of degree and for each with , the following two conditions are satisfied: - (a)
;
- (b)
.
Let also, be an initial guess such thatwhere the function ψ is defined by (4). Then the Picard iteration (1) is well defined and converges to ξ with the following error estimates:where and with ϕ and ψ defined by (5) and (4), respectively. In addition, if the second inequality in (6) is strict, then the order of convergence of Picard iteration (1) is at least . Proof. The initial condition (
6) can be written in the form
, where
. It is not hard to verify that for all
, the following inequalities hold (see, e.g., ([
11] Lemma 7.3)):
According to the first of these inequalities and the fact that
, we get
Indeed, if
is a zero of
, then by the triangle inequality, the definition of
and the condition (b), we obtain
This implies (
9) which in turn means that
. So, dividing both sides of (b) by
, we reach the inequality
where
with
defined by (
5). Since the inequality (
10) implies that
, then we have both
which according to (a) means that
. This, together with (
10) purports that
is a function of initial conditions of
T with gauge function
on the interval
(see Definition 3).
Now let
U be the set
. Then the condition (
6) implies that
. On the other hand (
10) and (
11) imply that
which means that starting from
the Picard iteration (
1) is well defined and remains in the set
U. The convergence to
follows from the second estimate of (
7). So, it remains to prove the estimates (
7). Since
is an initial point of
T with respect to
, and
is a gauge function of order
, then from Proposition 2 it follows that
where
. From this, taking into account that
is quasi-homogeneous function of degree
, and that
, we get
From this and condition (b) applied to
, we obtain the first estimate in (
7). From the first estimate in (
7) one can easily obtain the second one which in turn implies the convergence of the Picard iteration (
1) due to
and
. □
3. Local Convergence of the Super-Halley Method for Multiple Polynomial Zeros
In 2008, Osada [
5] derived a modification of the Chebyshev–Halley family of iterative methods for computation of multiple zeros of known multiplicity
m. The most famous iterative methods, namely Newton’s, Halley’s and Chebyshev’s methods for multiple zeros are members of this family. A detailed local convergence analysis of these illustrious methods applied to multiple polynomial zeros can be found in the papers [
8,
14,
15,
16]. Another member of the Chebyshev–Halley family that has been rarely studied is the so called Super-Halley method for multiple zeros, which can be defined by the following iteration (see, e.g., [
17,
18] and references therein):
where the iteration function
is defined by
with
and
defined as follows
It is seen that the domain of the function (
13) is the set
In this section, we implement Theorem 1 and Theorem 2 to the Super-Halley method (
12) applied for computation of polynomial zeros of known multiplicity
m. Thus, we obtain two new local convergence theorems (Theorem 3 and Theorem 4) that provide sufficient conditions to guarantee the cubic convergence of the method (
12) right from the first step. A priory and a posteriori error estimates at any iteration are also provided. The obtained results are new even in the case of simple zeros. Note that in this case, i.e., when
the Super-Halley method (
12) was presented in 1992 by Hernández-Verón [
19] and later investigated in [
20,
21], etc.
Before proceeding further, we give two useful technical lemmas.
Lemma 1. Let K be an arbitrary field, and let be polynomial of degree which splits over K. Suppose that are all distinct zeros of f with multiplicities , respectively.
- (i)
If is not a zero of f, then for any we have - (ii)
If is not a zero of both f and , then for any we have
Proof. (i) Using a well known identity (see, e.g., ([
15] Lemma 4.2(i))), we obtain
which proves the first claim.
The second claim follows from (i) and the following identities (see, e.g., ([
15] Lemma 4.2(ii)) and ([
14] Equation (
15))):
□
Lemma 2. Let and be all zeros of f which are not equal to ξ, then for any the following inequality holds:where is defined by (2). Proof. Since
for all
, then by the triangle inequality in
, we get
□
3.1. Local Convergence of the First Type
From now on
denotes the ring of polynomials over the normed field
. Let
be a polynomial of degree
. We shall study the convergence of the Super-Halley method (
12) with respect to the function of initial conditions
defined by (
2).
Onwards, for
, we define the real functions
g and
h by
Obviously, the function
g is positive and quasi-homogeneous of second degree on the interval
and the function
h is decreasing and positive on the interval
, where
Hence, we can define the function
by
Note that the function
is quasi-homogeneous of second degree on the interval
owing to the properties (P1) and (P3).
The next lemma shows that the function
defined by (
19) satisfies the conditions (a) and (b) of Theorem 1 with the Super-Halley iteration function and the function
E defined by (
2).
Lemma 3. Let be a polynomial of degree which splits over , and let be a zero of f with multiplicity m. Let be such thatwhere the function E is defined by (2) and τ is the number (18). Then: - (i)
x belongs to the set D defined by (15). - (ii)
, where the function ϕ is defined by (19).
Proof. Let
satisfy (
20). If
or
, then
and the statements of the lemma hold. Let
and
. Let also
be all distinct zeros of
f with respective multiplicities
and the quantities
and
be defined as in Lemma 1. Put
and
for some
.
(i) According to (
15), we have to prove that
implies
, where
is defined by (
14). From
and Lemma 2, we get
for each
which means that
. Then, from (
14) and Lemma 1 (i), we get
Now, from the triangle inequality and (
21), we obtain the following estimate:
From this, using the triangle inequality and
, we get
Hence,
which implies
. Then, from Lemma 1 (ii), we have
Now, from (
14), (
22) and (
25), we obtain
Further, by means of the triangle inequality, (
21) and
, we reach the estimates (see e.g., ([
14] Equation (
11)))
The last estimate implies that
and so
.
(ii) From the definition of the Super-Halley iteration function (
13), (
22) and (
25), we easily get
where
Hence, to complete the proof it is sufficient to estimate
from above. With this aim, using the estimates (
23), (
24) and (
26), we get
This completes the proof of the lemma. □
The following theorem is the first convergence result about the Super-Halley method (
12).
Theorem 3. Let be a polynomial of degree which splits over , and let be a zero of f with multiplicity m. Suppose is an initial approximation satisfyingwhere the function E is defined by (2). Then the Super-Halley iteration (12) is well defined and converges cubically to ξ with the following error estimates for all :where and the function ϕ is defined by (19). Besides, the iteration (12) converges Q-cubically to ξ with the following error estimate Proof. It is easy to verify that
, where
is defined by (
18) and
for all
. Hence, the initial condition (
29) is equivalent to (
3) with
and
defined by (
19). Therefore, the proof follows from Lemma 3 and Theorem 1. □
Remark 1. It is interesting to note that in the case , Theorem 3 gives larger convergence domain and better error estimates for the Super-Halley method (12) than Theorem 4.5 of [15] for the Halley’s method. 3.2. Local Convergence of the Second Type
Here, we study the convergence of the Super-Halley method (
12) with respect to the function of initial conditions
defined by (
2).
For
, we define the real function
by
Apparently,
is a quasi-homogeneous function of second degree on
.
The role played by the following lemma is the same as the one of Lemma 3.
Lemma 4. Let be a polynomial of degree which splits over , and let be a zero of f with multiplicity m. Let be such thatwhere the function is defined by (2). Then: - (i)
, where D is the set (15). - (ii)
, where the function β is defined by (32).
Proof. The proof is the same as those of Lemma 3. One just should use the estimate
instead of (
21). □
Now we can state the second main result of this section.
Theorem 4. Let be a polynomial of degree which splits over , and let be a zero of f with multiplicity m. Suppose an element satisfies the following initial conditionswhere the function is defined by (2) and the real functions β and ψ are defined by (32) and (4), respectively. Then the Super-Halley iteration (12) is well defined and converges to ξ with error estimateswhere and . In addition, if the second inequality in (34) is strict, then the iteration (12) converges at least cubically to ξ. Proof. The proof follows immediately from Lemma 4 and Theorem 2. □
4. Conclusions
Two general theorems (Theorem 1 and Theorem 2) that give an easy algorithm for investigating the local convergence of Picard-type iterative processes in arbitrary normed fields are proven in this paper. Any of the presented theorems is supplied with a priori and a posteriori error estimates. Moreover, the initial conditions of Theorem 1 guarantee the Q-order convergence of the Picard iteration right from the first step. Furthermore, the presented general theorems are applied to study the local convergence of the Super-Halley method for multiple polynomial zeros. Thus, two types of local convergence theorems (Theorem 3 and Theorem 4) with error estimates for this method are proven. The obtained theorems are new even in the case of simple zeros.
Finally, the ideas of this paper can be further developed to obtain general convergence theorems with computationally verifiable initial conditions and error estimates that are of significant practical importance.