1. Introduction
The fixed-point theorem is one of the most powerful mathematical tools that have been
widely applied in various fields, not only in pure mathematics, but also in the areas
of engineering. For over a century, many researchers have demonstrated the existence
and the properties of fixed point theory through analysis, topology, geometry, and
numerical analysis. After Banach proved that a contraction mapping in the field of
complete metric space possesses a unique point in 1922
(1), the contractive mapping was developed by many researchers as fixed point theory
(2,3). In recent decades, the various numerical methods including the fixed point theory
have been employed in fixed point theory to approximate the roots of polynomials and
to demonstrate the convergence property
(4,5).
In this research, a new numerical method is proposed to find the real roots of the
nonlinear systems by constructing a scheme that builds a converging sequence to a
root of a function even in the case that the conventional fixed point theorem (CFPT)
does not guarantee the convergence.
The CFPT is defined as follows. Let f(x) be a real-valued function with an initial
point x
0 in the domain of f(x). Then the fixed point iterations x
n+1=f(x
n), n∈N, the natural numbers, build a sequence {x
n} that may converge to a point x
r. If f(x) is continuous, then the obtained x
r is a fixed point of f(x) such as f(x)=x. Analytically, for a complete metric space
(X, d) with f:X→X, if f is continuous and satisfies d(f(x)), f(x
0)
λd(x,x
0) with x,x
0∈X, 0
λ
1 then f has a unique fixed point x
r in X
(7).
In this paper, an extended fixed point iterative method finds the real-valued roots
of a polynomial by relaxing the constraint 0
λ
1 of CFPT, such that the regions of convergence to a root may be expanded. The metric
defined by the proposed method converges to a fixed point, a root of f(x), without
the constraint 0
λ
1. The proposed iterative method provides the various good properties compared to
CFPT besides relaxing the constraint. However, further research on the extended contractive
iterative method (ECIM) is needed.
On the extended contractive iterative method on the extended contractive iteration
method (ECIM) for the applications in various fields, such as the linear and nonlinear
system analysis in discrete and continuous control theory.
The remainder of this paper is organized as follows. In Section 2, the problems involved
in CFPT are discussed. Section 3 presents the ECIM and the extended fixed point theorem
(EFPT) with proofs. In Section 4, some numerical simulations are presented to demonstrate
the advantages of the proposed method. Finally, Section 5 draws the conclusions of
the present study.
2. Problems Involved in CFPT
Let f:X →X be a mapping from a set X to itself. We call a point x ∈ X a fixed point
of f when f(x)=x. We will discuss here the most basic fixed-point theorem in analysis
to relax the constraints on it. Let (X,d) be a complete metric space and f:X→X be
a map, such that d(f(x), f(x
0))
λd(x, x
0) for some 0
λ
1 and all x, x
0∈X. Then f has a unique fixed point x_r in X. Moreover, for any x
0∈X, the sequence x
0, f(x
0), f(f(x
0))··· converges to a fixed point x
r∈X
(4,6,7). A function f(x) is called a contraction that shrinks the metric by a uniform factor
λ for all pairs of points, where the contraction does not hold for some λ
1.
The first problem to be considered is that it is not easy to choose a proper form
of g(x) with convergence property for a given function f(x)=g(x)-x=0. Secondly, even
the several different forms of g(x) converge to the same fixed point, the convergence
regions of different forms of g(x) may differ one from another due to the convergence
constraint |g'(x
0)|
1.0, which we call the convergence region problems.
For example, suppose that a polynomial f(x)=x
2-x-1=0 is given in a form of f(x)=g(x)-x=0. Several different forms of g(x) maybe
obtained as shown in
Table 1, such as g
a(x)=1+x
-1, g
b(x)=(1+x)
-1, g
c(x)=x
2-1 and
. The functions, g
a(x), g
b(x) and g
c(x) have the different regions of convergence (ROC) which satisfy the constraint |g'(x
0)|
1.0 x, x
0∈X, while the function g
d(x) is not in the proper form of convergence as presented in
Table 1.
Table 1. An example: f(x)=x2-x-1 where f(x)=g(x)-x=0, x1=-0.61803, x2=1.6180
|
|
g(x)
|
|
ROC
|
The roots of f(x)=0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Improper form
|
|
|
As shown in
Table 1, a function f(x) may be expressed in several different forms of g(x)'s each of which
has its own ROC, while g
d(x) is in improper form for finding a root using the fixed point iterations. The example
f(x) in
Table 1 has the two roots, x
1and x
2, but none of the forms presents the two contractive fixed points as the roots of
f(x) simultaneously.
The function g
a(x) has only x
2 as a fixed point and g
b(x) constructs a contractive iterations converging to only x
1 while the sequence generated by the iterations of g
c(x) converges to -1 and 0 alternatively not to the roots, x
1, x
2 since x
1= -0.6183 and x
2=1.6180 are not in the region of ROC (-0.5, 0.5) as shown in
Table 1. Based on the observations described, it is possible that those two roots of f(x)
can be obtained algebraically, which is not true in general for a higher order polynomial.
However, the contractive iterations which converge to the roots may not be obtained
by employing the fixed point theorem only. Those roots which are in ROC, where the
area of ROC is derived by the constraint |g'(x
0)|
1.0, are obtained through the contractive property of fixed point theorem. Otherwise
the contractive property cannot be kept if the roots are outside of ROC. Convergence
to a fixed point requires that the root of a function must be inside of ROC which
is derived from |g'(x
0)|
1.0 where x
0 is a point in the domain of the function g(x).
From the above observations, we may conclude two facts. Firstly it is not easy to
choose a proper form of g(x) with the convergence property for a given function f(x)=g(x)-x=0
from all possible forms g(x)'s since we do not have any information on g(x) in advance.
Secondly, choosing the proper initial value in the domain of g(x) for the fixed point
iteration is not easy because the choice of g(x) constructs the region of convergence
differently. However, it is not necessary for the initial values to be in the ROC
when ECIM is used. It is true that if a root of a function f(x) is in ROC, then the
iterative sequence converges to a root of f(x). In addition to this, in order to find
the roots in ROC, the initial value also needs to be in ROC for the contraction property.
When we choose an initial value outside of ROC, the iterations may and may not converge
to the roots of a function f(x). Even we choose an initial value in ROC, if a root
of f(x) locates in the outside of ROC, the generated contractive sequence does not
converge to a root. Therefore we may conclude that the form of g(x) determines the
property of contractive convergence.
In this work, we propose a new contractive iteration method to relax the constraint
of convergence, |g'(x
0)|
1.0 by constructing a scheme that enhances the possibility of convergence to the roots
of a function. The proposed method simplifies not only the conventional fixed point
iteration but also the algorithm that generates a converging sequence instead of diverging
sequence. Consequently, the proposed method simplifies the searching process for a
unique form of g(x) and expanding ROC by constructing the proposed scheme that transforms
a diverging sequence to a converging sequence.
3. 본론
Practically, the fixed point theorem in a continuous interval is constrained to satisfy
|g'(x_0 )|
1.0 to find the roots of the function, such that a sequence of points
for k∈N where N is the natural number, converges to a fixed point x
r∈X. The fixed point is a root of a given polynomial f(x)=0 when the constraint |g'(x_0
)|
1.0 is satisfied, where g(x) is obtained from the relationship f(x)=g(x)-x=0. Otherwise,
the sequence g
k(g
k-1( ··· (g
0 (x
0)))) diverges for k∈N the natural number
(6). In the proposed scheme, for a given arbitrary function f(x), a unique g(x) is generated
by setting g(x)=f(x)+x, we present a new method of generating a sequence which converges
to a root of a function whether the constraint of CFPT is satisfied or not. At the
same time, the problem of finding a proper g(x) has been relaxed simultaneously.
The choice of initial value is set to be free in the proposed method since the sequence
built by an arbitrary initial value is set to converge to roots or may diverge, which
implies that the choice of initial value does not need to be in ROC for finding the
roots of polynomial in the proposed scheme. However, a root of f(x) needs to be in
ROC if the fixed point generated by CFPT is set to be a root of the given polynomial.
The proposed method expands the CFPT by generating a sequence of metrics defined in
the opposite direction of divergence as described in
Fig. 1. The sequence of metrics obtained by the proposed scheme is set to converge to a
real-valued root of a function. For a chosen initial point x
0, the corresponding function value g(x
0) is determined, such that a metric is defined as shown in
Eq. (1)(6). Since a point Q(x
0, x
0) is on a line p(x)=x, a metric can be generated between Q(x
0, x
0) and P(x
0, g(x
0)) in the form of l
2-norm such as
Fig. 1. A scheme of finding the root of a function using ECIM
A new point x
n in the domain of a function g(x) is generated by
Eq. (2)
The parameter c is defined c=sign*dif as presented in
Table 2 with two functions sign and dif in
Eq. (3),
Table 2. A method of finding the next following point in the domain of function g(x)
|
sign
|
dif
|
c=sign*dif
|
xn = x0 -c*d
|
|
+1
|
+1
|
+1
|
xn =x0 -d
|
|
+1
|
-1
|
-1
|
xn =x0 +d
|
|
-1
|
-1
|
+1
|
xn =x0 -d
|
|
-1
|
+1
|
-1
|
xn =x0 +d
|
The variable sign is 1.0 when g'(x
0)
1.0} and -1 when g'(x
0)
-1.0, while the variable dif becomes 1.0 when g(x_0 )-x
00.0}} and -1 when g(x
0)-x
00.0. The parameter c=sign*dif presents the four cases as shown in
Table 2. A sequence is generated by the selecting a value in the domain of g(x) using x
n=x
0-c*d. As it is shown in
Table 2, when g'(x
0)
1.0, we need to determine whether g(x) locates above or below the line p(x)=x and
set the direction of sampling process in the domain of g(x), such that the sequence
converges to a root of a polynomial. Roots of polynomial locate at the points of intersections
between g(x) and p(x)=x.
Suppose that x
0 and g(x
0)} are the present sampled value and its corresponding g(x) to x
0. Then, both the sampled value obtained from the next sampling process x
n=x
0-c*d and its corresponding g(x
n) need to be in the same side with respect to p(x)=x until the sequence converges
to a root. Then we check whether g(x
0) and g(x
n) are in the same side with respect to p(x)=x by the following expression, where *
denotes multiplication
If they are in the same side with respect to p(x)=x, τ
n0.0, otherwise, τ
n0.0. When τ
n0.0, we reduce the sampling step size by a shrinking parameter β∈(0, 1), such that
a new metric
is revised recursively until τ
n0.0. The next sampling point is determined by x
n= x
0-c*d. The sequence sampling process is repeated until
where the predetermined criteria ε
obj is set as an allowed error. When the constraint, |g'(x
0)|
1.0, is not fulfilled, the sequence from the domain of g(x) does not converge to
a root f(x)=0 in CFPT as we have found. However, the diverging sequence extracted
from CFPT may be switched to a converging metric sequence via the proposed scheme.
The sequence of points { x
k } for k∈N is designed to be generated through the recursive iterations, x
k+1= x
k-β(g(x
k)-x
k) where β∈[0,1) and k∈N the natural number. The variable β∈[0,1) affects the speed
of convergence to a fixed point.
Theorem 1. [Extended Contractive Iteration Theorem]
Let (X,d) be a complete metric space and f:X→X be a map, such that
for some λ
1.0 and all x, x
0∈X. Then f has a unique fixed point x
r∈X for any x
0∈X, where the sequence of iterations generated by x
k+1=x
k-β(g(x
k)-x
k) for β∈(0,1), such that { x
k} converges to a fixed point x
r∈X of f for k∈N the natural number,
.
[Proof] From the constraint, d(f(x),f(x
0))
λd(x,x
0) where λ
1.0 implies that the absolute value of derivative is greater than 1.0 at each point
x
0∈X, such that f'(x
0)
λ
1.0. Let β = λ
-1∈(0,1) and k=0, then we define the value x
1=x
0-β(f(x
0-x
0) and d
0=x
0-x
1.
Since f'(x
0)
λ
1, f(x
0)-f(x
1)
x
0-x
1 becomes f(x
0)-x
0f(x
1)-x
1, such that f(x
1)-x
1= β (f(x
0)-x
0) for β∈(0,1) where x
1x
0. Using the obtained x
1, we set the value x
2, such that x
2x
1, x
1-x
2=β(f(x
1)-x
1). Then x
1-x
2=β(f(x
1)-x
1)=β(β(f(x
0)-x
0))=β
2(f(x
0)-x
0) and the distance between x
1 and x
2 becomes d
1=β
2(f(x
0)-x
0)
d
0.
For the obtained values x
1, x
2, we can determine x
3, d
2=x
2-x
3=β(f(x
2)-x
2)=β (β
2(f(x
0)-x
0))= β
3(f(x
0)-x
0) such that d
2 d
1 d
0 for β∈(0,1). Then for an arbitrary k, we obtain d
k=x
k-x
k+1= β
k+1(f(x
0)-x
0)
d
k-1and x
kx
k-1 for all k∈N, d
k= x
k-x
k+1=β
k+1(f(x
0)-x
0)
d
k-1 such that
. Thus for any x
0∈X the iterations x
k+1=x
k-β(g(x
k)-x
k) for k∈Z, where Z = { 0, 1,2, ··· }, 0
β
1, generates the sequence { x
k } where x
k converges to the fixed point x
r∈X of f,
.
Now, for an arbitrary function f(x)=g(x)-x, if it has a real root, then the root locates
at the point where g(x) crosses p(x)=x whether the constraints in CFPT is satisfied
or not, since for a root x
r∈X, the root searching iteration converges to from an initial value x
0 by using both CFPT and ECIM. Hence, whenever g(x) crosses p(x)=x, a real valued root
can be obtained by the contractive iterations. It turns out to be sufficient to get
the conclusion of the contraction mapping theorem for the functions with the real-valued
roots by the following Theorem 2.
Theorem 2. [Extended Fixed Point Theorem (EFPT)]
Let (X,d) be a complete metric space and f: X→X be a map, such that
for some λ≠1.0 and all x, x
0∈X. Then f has a unique fixed point x
r in X whenever F has a real valued root using the iteration method.
[Proof] Firstly, for f(x) with λ∈(0,1) and any x
0∈X, the sequence obtained from iterations x
0, g(x
0), g(g(x
0)), g(g(g(x
0))),···, converges to a unique fixed point of f(x)=g(x)-x=0 for x
r, x
0∈X if d(f(x),f(x
0))
λ d(x,x
0) by CFPT. Secondly, for λ
1, the sequence extracted with 0
β
1.0
converges to x
r,
, k∈N the natural number by the Theorem 1. Therefore, the statements in Theorem 2
hold.
4. Numerical Simulations
For a given function f(x), the proposed method ECIM is applied to find the roots of
the function f(x)=x
2-x-1 whose roots cannot be obtained using the fixed points of the conventional fixed
point theorem. In order to use the proposed scheme, a unique polynomial g(x) is obtained
by the relation f(x)=g(x)-x=0. As it is shown in
Table 1, for g(x)=x
2-1, the conventional fixed point iterations do not converge to the roots of f(x) when
the roots of f(x) are not in ROC (-0.5, 0.5) obtained from the constraints |g'(x)|
1. However, the proposed scheme builds a sequence of contractive iterations, where
a fixed point becomes a root of the function f(x).
Figure. 2,
Figure. 3,
Figure. 4,
Figure. 5 illustrate the behaviors of contractive iterations f(x) which converge to the roots,
the fixed points, with initial values -0.01, -1.0, 0.0, 3.0 respectively.
Table 3 presents the results of numerical simulations using the proposed scheme with variable
β=0.25, which is chosen as a constant for convenience. The variable β needs to be
studied further since it affects the speed of convergence to a fixed point. The numerical
simulation results present the contractive property of the proposed method by Theorem
1. The chosen sequences obtained by Theorem 1 converge to the roots of the polynomial
while the sequences may diverge in CFPT.
Fig. 2. Function f(x)=x2-x-1 with g(x)=f(x)+x, the number of iterations 22, a fixed point xr=-0.618033970, error=-6.8738122e-08, the initial value x0=-0.01
Fig. 3. Function f(x)=x2-x-1 with g(x)=f(x)+x, the number of iterations 20 , a fixed point xr=-0.618034008, error=7.713588e-8, the initial value x0=-1.0
Fig. 4. Function f(x)=x2-x-1 with g(x)=f(x)+x, the number of iterations 26, a fixed point xr=1.618033976, error=-7.699750e-8, the initial value x0=0.0
Fig. 5. Function f(x)=x2-x-1 with g(x)=f(x)+x, the number of iterations 21, a fixed point xr=1.618033997, error=, the initial value x0=3.0
Table 3. Experimental results for a function f(x)=x2-x-1 using the proposed scheme
|
Fig.
|
Initial point: x0
|
Num. of iter.: N
|
Converging point: xr
|
Error: εN
|
|
Figure. 2
|
-0.01
|
22
|
-0.61803397
|
-6.873922e-8
|
|
Figure. 3
|
-1.0
|
20
|
-0.61803400
|
7.713588e-8
|
|
Figure. 4
|
0.0
|
26
|
1.61803397
|
-7.699750e-8
|
|
Figure. 5
|
3.0
|
21
|
1.61803399
|
5.669268e-8
|
|
Figure. 6
|
4.0
|
23
|
1.61803399
|
-5.200781e-8
|
|
Figure. 7
|
-2.5
|
19
|
-0.61803396
|
-8.889898e-8
|
Figure. 6 and
Figure. 7 represent two cases where the sequences converge to the fixed points in the proposed
iterations with alternating with respect to the fixed points. In both cases, the metric
d
1 is greater than the distance to an adjacent root from the initial value. Even though
there are some swings around a root, the sequence eventually converges to the root
which attracts the iterations to a fixed point.
Fig. 6. Function f(x)=x2-x-1 with g(x)=f(x)+x, the number of iterations 23, a fixed point xr=1.618033997, error=-5.2007811e-8, the initial value x0=4.0
Fig. 7. Function f(x)=x2-x-1 with g(x)=f(x)+x, the number of iterations 19, a fixed point xr=-0.618033965, error=-8.88989890e-8, the initial value x0=-2.50
The method of generating a convergence sequence is demonstrated in
Figure. 8,
Figure. 9 using the proposed scheme for the cases that |g'(x)|
1.0 for all x∈X, the domain of g(x).
Figure. 8,
Figure. 9 describe graphically the function g(x) obtained from f(x) using g(x)=f(x)+x where
g(x)=x
3+1.5x
2+1.95x+1.0 as they are illustrated in
Table 4. The experimental results demonstrate the property of contractive iterations to the
roots of the polynomial f(x)=x
3+1.5x
2+0.95x+1.0 with variable β=0.25 chosen as a constant for convenience. The variable
β affects the speed of convergence to the fixed point.
Fig. 8. Convergence of {xk} where k∈N to the fixed point xr=-1.34612960, with the initial value x0=1.5, error=6.4729788e-8, the number of iterations=23, and β = 0.25
Fig. 9. With the initial value x0=-2.5, the sequence {xk} where k∈N converges to the fixed point xr = -1.34612960, error=6.831943188e-8, the number of iterations=24, and β = 0.25
Table 4. A case of g(x)=f(x)+x where g(x)=x3+1.5x2+1.95x+1.0 with |g '(x)|
1.0 for all x∈X, the domain of g(x)
|
Fig.
|
Initial point: x0
|
Number of iter.: N
|
Converging point: xr
|
Error: εN
|
|
Figure. 8
|
1.5
|
23
|
-1.3461239
|
6.4729278e-8
|
|
Figure. 9
|
-2.5
|
20
|
-1.3461239
|
6.8319431e-8
|
With the function, g(x)=f(x)+x, we check the derivation of g(x) at a chosen initial
point. If the slope at the chosen point is less than 1.0, we use the conventional
fixed point iteration method using CFPT. When the absolute slope is greater than 1.0
at the chosen point such as, we apply the specified sequence generation process using
ECIM.
In
Figure. 8,
Figure. 9, for f(x)=x
3+1.5x
2+0.95x+1.0, a unique function g(x) is generated. The function f(x) crosses the horizontal
axis at the points where the roots of the function f(x) locate while g(x) crosses
a line p(x)=x at the locations of roots of f(x). The sequences of metrics in
Figure. 8,
Figure. 9 illustrate the convergence to the two roots for the initial value x_0 = 1.5 and the
initial value x_0 = -2.5 respectively.
As illustrated in
Figure. 2-
Figure. 9, the experimental results show that a sequence of metrics { d
k } converges to a fixed point even the absolute value of the slope of g(x
0), |g'(x
0)|, is greater than 1.0. As shown in Figures, a set of metrics { d
k } is generated by connecting the points of g
x and the corresponding points of p(x)=x at each chosen point of the domain of a function
g(x). In
Figure. 8, the converging metric sequence { d
k } to the fixed point x
r=-1.34612960} is illustrated for the initial value x
0 = 1.5 with the number of iterations yields 23, the error 6.47292788e-08, and the
parameter β=0.25.
Figure. 9 shows the case of the initial value x
0 = -2.5 where a sequence { x
k }, which is a set of the chosen domain values of a function f(x), converges to the
fixed point x
r=-1.34612960 with error 6.83194318895e-08. The number of iterations with the given
conditions yields 24 with the process x
k+1=x
k-β(g(x
k)-x
k) where the variable β=0.25 affects the speed of convergence to a fixed point. In
experiments, we have demonstrated the convergence for the case and using Theorems
1 and 2. Further reaches is expected to take advantage of the good properties of the
proposed method in various fields.
5. Conclusions
In this paper, EFPT is proposed using the metric constructed by an extended fixed
point iterative method ECIM, such that any real-valued roots of a nonlinear system
may be obtained. The proposed method relaxes the constraints on the numerical fixed
point iteration method for finding the roots of a nonlinear systems with the two good
properties.
Firstly, EFPT lets an initial value for a system converge to a real-valued root via
the relaxation on the constraint by minimizing the constraint from |g'(x)|
1.0 to |g'(x)|≠1.0. Secondly, a unique form of g(x) from f(x)=g(x)-x=0 is able to
be determined without the efforts for finding a proper form of g(x) with trial and
error. In the conventional fixed point theorem, CFPT, it is necessary to check several
forms of g(x)'s' for f(x) since a chosen g(x) may diverge or converge depending on
the form of g(x) with the various regions of convergence. However, the proposed method,
EFPT, improves the convergence to the real roots of a nonlinear system by expanding
ROC with the relaxation on the constraints of g(x).
The proposed method is useful to establish the local existence and uniqueness of solutions
of the ordinary differential equations. As some practical applications, the contraction
mappings are useful to develop the simple numerical methods for solving nonlinear
equations, such as the fuzzy logic programming. For example, the proposed fixed point
theory may be applied for finding equilibrium points in the area of nuclear reactor
analysis. In general, the applications of the fixed point theory can be focused on
any kind of differential equations related to stability of dynamic systems of continuous-time,
discrete-time, hybrid of both of them. Further researches are expected to be carried
out for taking advantage of the good properties of EFPT for various applications in
science and engineering fields.