Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 02, 1996, pp. 48–54. Submitted: August 11, 1996. Published: October 15, 1996.

WEAK CONDITIONS FOR THE CONVERGENCE

OF ITERATIONS TO SOLUTIONS OF EQUATIONS

ON PARTIALLY ORDERED TOPOLOGICAL SPACES

Ioannis K. Argyros

Abstract. We provide sufficient conditions for the monotone convergence of Newton like methods to solutions of nonlinear operator equations on partially ordered topological spaces. We assume conditions weaker than standard Lipschitz-like conditions to produce two iterations, one increasing and one decreasing, that enclose and converge to a solution of an equation. Finally examples are given to show that our results apply where previous ones fail.

1991 A.M.S. (MOS) Subject Classification Codes. 65J15, 47H17, 49D15.

Key Words and Phrases. Partially ordered topological space, monotone convergence, fixed point, Newton-like methods.

I. INTRODUCTION

In this study we are concerned with approximating a solution of the nonlinear operator equation

(1)  F (x) = 0,

where F is an operator defined on a subset of partially ordered linear space E_{1} = (E_{1}, ≤) (POL-space) with values in a POL-space E_{2} [1], [2], [5]–[8].

We suggest Newton-like iterations of the form

(2)  F (x_{n}) + A^{1}(x_{n−1}, x_{n})(x_{n+1} − x_{n}) = 0

(3)  F (y_{n}) + A^{1}(y_{n}, y_{n−1})(y_{n+1} − y_{n}) = 0

for [x_{−1}, y_{−1}] ⊆ D, x_{−1} ≤ x_{0}, y_{0} ≤ y_{−1} and A^{1}, A^{2}: D^{2} → L(E_{1}, E_{2}) [2], [6]. Sufficient conditions for the monotone convergence of the sequences {x_{n}}, {y_{n}}

Typeset by AMS-TEX

Cameron University, Lawton, Oklahoma

E-mail Address: ioannisa@cameron.edu

\begin{matrix}c \\ ◯ \end{matrix}1996 Cameron University

(n ≥ 1) generated by (2) and (3) respectively to a solution of equation (1) have been given by various authors based mainly on the condition

(4)  F (y) − F (x) ≤ A(w, z)(y − x) for x ≤ y ≤ w ≤ z,

[x, z] ⊆ D and A: D → L(E_{1}, E_{2}) being linear operator having continuous nonsingular nonnegative left subinverse (see [2], [5], [6] and the references there). There are examples even in the scalar case (see the example after Theorem 1) where iterations {x_{n}}, {y_{n}} converge to a solution of equation (1) but the sufficient conditions for the convergence fail to apply. That is why it is important to try to find weaker conditions under which these iterations converge to a solution. This is what we have done in this study.

Finally we note that for A^{1}(x, y) = A^{2}(x, y) = F′(x) for all x, y ∈ D, where F′(x) is the Fréchet-derivative of F we obtain Newton’s method [3], [4], whereas for A^{1}(x, y) = A^{2}(x, y) = [x, y; F] for all x, y ∈ D, where [x, y; F] is the divided difference of order one of F at the points x, y ∈ D we obtain the secant method [3], [4]. Several other choices for the operators A^{1} and A^{2} are also possible [2].

Theorem 1. Consider an operator F: D ⊆ E_{1} → E_{2} where E_{1} is a regular POTL-space, E_{2} is a POTL-space and D is an open convex subset of E_{1}. Let x_{−1}, x_{0}, y_{−1}, y_{0} be points of D such that

(5)  x_{−1} ≤ x_{0} ≤ y_{0} ≤ y_{−1}, [x_{−1}, y_{−1}] ⊆ D.

Assume:

(a) there exists points z_{1}, z_{2} ∈ [x_{0}, y_{0}] such that

z_{1} ≤ z_{2} and F (z_{1}) = F (z_{2}) = 0.

(b) F (x) ≤ 0 for all x ∈ [x_{0}, z_{1}] and F (x) ≥ 0 for all x ∈ [z_{2}, y_{0}].

(c) there exist operators A^{1}, A^{2}: D^{2} → L(E_{1}, E_{2}) such that

(6)  F (z_{1}) − F (x) ≤ A^{1}(y, x)(z_{1} − x) for all y, x with x_{0} ≤ y ≤ x ≤ z_{1}

and

(7) F (v) − F (z_{2}) ≤ A^{2}(v, w)(v − z_{2}) for all v, w with z_{2} ≤ v ≤ w ≤ y_{0}.

(d) The linear operators A^{1}(y, x) and A^{2}(v, w) have continuous nonsingular

nonnegative left subinverses on [x_{−1}, y_{−1}]. Then there exist two sequences {x_{n}}, {y_{n}} generated by (2) and (3) respectively (n ≥ 1) and two points x^{∗}, y^{∗} of E_{1} such that for all n ≥ 0

(8)  F (x_{n}) ≤ 0 ≤ F (y_{n}),

(9)  x_{0} ≤ x_{1} ≤ ⋯ ≤ x_{n} ≤ x_{n+1} ≤ z_{1} ≤ z_{2} ≤ y_{n+1} ≤ y_{n} ≤ ⋯ ≤ y_{1} ≤ y_{0},

(10)  lim_{n→∞} x_{n} = x^{∗}, lim_{n→∞} y_{n} = y^{∗}, x^{∗} ≤ z_{1} ≤ z_{2} ≤ y^{∗},

and

(11)  x^{∗} = y^{∗} ⇒ x^{∗} = z_{1} = z_{2} = y^{∗}.

Moreover assume there exist operators A^{3}, A^{4}: D^{2} → L(E_{1}, E_{2}) with nonnegative left superinverses satisfying

(12)  F (z_{1}) − F (x) ≥ A^{3}(x, y)(z_{1} − x) for all x_{0} ≤ x ≤ y ≤ z_{1},

(13)  F (v) − F (z_{2}) ≥ A^{4}(w, v)(v − z_{2}) for all z_{2} ≤ w ≤ v ≤ y_{0},

F (x^{∗}) = F (z_{1}) and F (y^{∗}) = F (z_{2}).

Then we deduce

x^{∗} = z_{1} and y^{∗} = z_{2}.

Furthermore if z_{1} = z_{2} we get x^{∗} = y^{∗} = z_{1} = z_{2}.

Proof. Let B_{0}^{1} be a continuous nonsingular left subinverse of A_{0}^{1} = A^{1}(x_{−1}, x_{0}) and consider the operator P_{1}: [0, z_{1} − x_{0}] → E_{1} defined by

P_{1}(x) = x − B_{0}^{1}(F (x_{0}) + A_{0}^{1}(x)).

It is easy to see that P_{1} is isotone and continuous. We also have

P_{1}(0) = −B_{0}^{1}(F (x_{0})) ≥ 0
P_{1}(z_{1} − x_{0}) = z_{1} − x_{0} − B_{0}^{1}(F (z_{1})) + B_{0}(F (z_{1}) − F (x_{0}) − A_{0}^{1}(z, −x_{0}))
≤ z_{1} − x_{0} − B_{0}^{1}(F (z_{1})) ≤ z_{1} − x_{0}

by hypotheses (a), (b) and (c).

According to Kantorovich’s theorem on fixed points [2], [5], [8] the operator P_{1} has a fixed point q_{1} ∈ [0, z_{1} − x_{0}]. Set x_{1} = x_{0} + q_{1} then

F (x_{0}) + A_{0}^{1}(x_{1} − x_{0}) = 0, x_{0} ≤ x_{1} ≤ z_{1}.

By hypothesis (a) we also get

F (x_{1}) ≤ 0.

Define the operator P_{2}: [0, y_{0} − z_{2}] → E_{1} by

P_{2}(x) = x + B_{0}^{2}(F (y_{0}) − A_{0}^{2}(x))

where B_{0}^{2} is a continuous nonsingular nonnegative left subinverse of A_{0}^{2} = A^{2}(y_{0}, y_{−1}). P_{2} is clearly continuous, isotone with

P_{2}(0) = B_{0}^{2}(F (y_{0})) ≥ 0,

and

\begin{aligned}P_{2}(y_{0} − z_{2}) & = y_{0} − z_{2} + B_{0}^{2}(F (z_{2})) + B_{0}^{2}(F (y_{0}) − F (z_{2}) − A_{0}^{2}(y_{0} − z_{2})) \\ & ≤ y_{0} − z_{2} + B_{0}^{2}(F (z_{2})) ≤ y_{0} − z_{2} \end{aligned}

by hypotheses (a), (b) and (c).

As above we define the existence of a point q_{2} ∈ [0, y_{0}−z_{2}] such that P_{2}(q_{2}) = q_{2}. Let y_{1} = y_{0} − q_{2}. It follows that

F (y_{0}) + A_{0}^{2}(y_{1} − y_{0}) = 0, z_{2} ≤ y_{1} ≤ y_{0}.

By hypothesis (b) we also have

F (y_{1}) ≤ 0.

Using induction on n ≥ 0 we can show that there exists two sequences {x_{n}}, {y_{n}} (n ≥ 0) satisfying (2), (3), (8), (9). Since E_{1} is regular from (9) it follows that there exist x^{∗}, y^{∗} ∈ E_{1} such that x^{∗} = lim_{n→∞} x_{n} and y^{∗} = lim_{n→∞} y_{n}. We obviously also have x^{∗} ≤ z_{1} ≤ z_{2} ≤ y^{∗}.

Denote by A^{5}(x^{∗}, z_{1}) a nonnegative left superinverse of A^{3}(x^{∗}, z_{1}). Then by (12) we obtain

0 ≤ z_{1} − x^{∗} ≤ A^{5}(x^{∗}, z_{1})A^{3}(x^{∗}, z_{1})(z_{1} − x^{∗}) ≤ A^{5}(x^{∗}, z_{1})(F (z_{1}) − F (x^{∗})) = 0

which implies x^{∗} = z_{1}. Similarly by (13) we obtain y^{∗} = z_{2}. By z_{1} = z_{2} we deduce x^{∗} = y^{∗}. Finally if x^{∗} = y^{∗}, (10) gives z_{1} = z_{2}.

That completes the proof of the theorem.

Example. Let E_{1} = E_{2} = R, choose any x_{−1} ≤ 0 and y_{−1} ≥ 0 and set D = [x_{−1}, y_{−1}]. Define the function F on D by

(14)  F (x) = \{ \begin{matrix}x & x ≤ 0 \\ 2x, & x ≥ 0. \end{matrix}

The only solution z of equation F (x) = 0 is z = 0. Let z_{1} = z_{2} = z. Choose also A^{1} = 2 and A^{2} = 3. Then hypotheses (a)–(d) of Theorem 1 are satisfied and iterations (2) and (3) give respectively

(15)  x_{n+1} = (\frac{1}{2})^{n+1} x_{0}

and

(16)  y_{n+1} = (\frac{1}{3})^{n+1} y_{0} (n ≥ 0)

which converge to 0 as n → ∞ for any x_{0} ≤ 0 and y_{0} ≥ 0. However theorems on the convergence of Newton’s method fail to apply since F′(0) does not exist [2], [3], [4]. We note though that Newton’s method converges to 0 since x_{1} = 0 for any x_{0}. Similar observations can be made for the secant method by setting A^{1}(y, x) = \frac{F (x)−F (y)}{x−y} and A^{2}(v, w) = \frac{F (w)−F (v)}{w−v}. By (14), approximations (2) and (3) become (15) and (16) respectively in this case which converge to 0. But theorems on the convergence of the Secant method require that F′(0) exists [2], [3], [4], [6], [8]. It is also simple calculus to show that condition (4) is not satisfied for both Newton’s and the Secant method.

Remark 1. We note that condition (4) implies (6) and (7) but not vice versa. (See the above example.) That is (6) and (7) are weaker conditions than (4).

The regularity of the space E_{1} is a rather restrictive condition. It was used to prove that sequences {x_{n}}, {y_{n}} (n ≥ 0) are well defined and convergent. To avoid this regularity condition we consider the explicit version of it:

(17)  x_{n+1} = x_{n} − B_{n}^{1}(F (x_{n})) (n ≥ 0)

(18)  y_{n+1} = y_{n} − B_{n}^{2}(F (y_{n})) (n ≥ 0)

where B_{n}^{1}, B_{n}^{2} are nonnegative subinverses of A_{n}^{1} and A_{n}^{2} respectively.

We can now state and prove the following result:

Theorem 2. Let F: D ⊆ E_{1} → E_{2} be an operator between two POL-spaces and D be an open convex subset of E_{1}. Let x_{−1}, x_{0}, y_{−1}, y_{0} be points of D satisfying (5). Assume that hypotheses (a)–(c) of Theorem 1 are true and linear operators A^{1}(y, x) and A^{2}(v, w) have nonnegative subinverses on [x_{−1}, y_{−1}].

Then approximations (17) and (18) where B_{n}^{1} and B_{n}^{2} are nonnegative subinverses of A_{n}^{1} and A_{n}^{2} respectively define two sequences {x_{n}}, {y_{n}} (n ≥ 0) having the properties (8) and (9).

Moreover if lim_{n→∞} x_{n} = x^{∗} = y^{∗} = lim_{n→∞} y_{n} then the following are true

x^{∗} = z_{1} = z_{2} = y^{∗} and F (x^{∗}) = F (y^{∗}) = 0.

Furthermore, if F is continuous at x^{∗} and y^{∗} and F (x^{∗}) = F (y^{∗}) we deduce F (x^{∗}) = F (y^{∗}) = 0.

Proof. For n = 0 we obtain in turn from approximations (17) and (18)

x_{1} − x_{0} = −B_{0}^{1}(F (x_{0})) ≥ 0,
z_{1} − x_{1} = z_{1} − x_{0} + B_{0}^{1}F (x_{0}) = (z_{1} − x_{0}) − B_{0}^{1}(F (z_{1}) − F (x_{0})) ≥ 0 by (6)

and

F (x_{1}) ≤ 0 by (b),
y_{0} − y_{1} = B_{0}^{2}(F (y_{0})) ≥ 0
y_{1} − z_{2} = y_{0} − B_{0}^{2}(F (y_{0})) − z_{2} = y_{0} − z_{2} − B_{0}^{2}(F (y_{0}) − F (z_{2})) ≥ 0 by (7)

and

F (y_{1}) ≥ 0 by (6).

Thus, we have proved x_{0} ≤ x_{1} ≤ z_{1} ≤ z_{2} ≤ y_{1} ≤ y_{0}. Proceeding by induction on n ≥ 0 we obtain (8) and (9). If x^{∗} = lim_{n→∞} x_{n}, y^{∗} = lim_{n→∞} y_{n} and x^{∗} = y^{∗} it follows that x^{∗} = z_{1} = z_{2} = y^{∗} and since F (z_{1}) = F (z_{2}) = 0 we get F (x^{∗}) = F (y^{∗}) = 0.

Finally if F is continuous at x^{∗} and y^{∗} by letting n → ∞ in (8) we get F (x^{∗}) ≤ 0 ≤ F (y^{∗}) and since F (x^{∗}) = F (y^{∗}) we deduce F (x^{∗}) = F (y^{∗}) = 0.

That completes the proof of the theorem.

Remark 2. Several natural conditions (other than the ones in Theorems 1 and 2) under which x^{∗} and y^{∗} are solutions of equation (1) as well as other variations of approximations (2)–(3) and (17)–(18) can be found in [2, Ch. 6].

Remark 3. The conclusions of Theorems 1 and 2 remain true if estimates (6), (7),

(12) and (13) are valid on [x_{0}, y_{0}], since x_{n} ≤ z_{1} and z_{2} ≤ y_{n} (n ≥ 0).

The following theorem is also available on fixed points.

Theorem 3. Let P: D ⊆ E_{1} → E_{1} where E_{1} is a regular POTL-space and D is a subset of E_{1}. Define the iterations

x_{n+1} = P (x_{n}) (n ≥ 0)

and

y_{n+1} = P (y_{n}) (n ≥ 0)

for some [x_{0}, y_{0}] ∈ D. Assume:

(a) there exists z ∈ D such that

x_{0} ≤ P (x_{0}) ≤ z ≤ P (y_{0}) ≤ y_{0};

(b) P (x) ≤ z for x ≤ z, x ∈ D and P (x) ≥ z for x ≥ z, x ∈ D;

(c) P (x) ≤ P (y) for x ≤ y, x, y ∈ D and P (x) ≥ P (y). Then there exist two points x^{∗}, y^{∗} ∈ D such that

(18) x_{0} ≤ x_{1} ≤ ⋯ ≤ x_{n} ≤ x_{n+1} ≤ x^{∗} ≤ z ≤ y^{∗} ≤ y_{n+1} ≤ y_{n} ≤ ⋯ ≤ y_{1} ≤ y_{0},

(19)  lim_{n→∞} x_{n} = x^{∗} and lim_{n→∞} y_{n} = y^{∗}.

Proof. By hypothesis x_{0} ≤ x_{1} = P (x_{0}) ≤ z, y_{−1} ≥ y_{1} = P (y_{0}) ≥ z. Assume x_{k−1} ≤ x_{k} ≤ z and y_{n−1} ≥ y_{k} ≥ z for k = 1, 2, …, n. Then x_{k+1} = P (x_{k}) ≤ z, y_{k+1} = P (y_{k}) ≥ z, x_{k+1} − x_{k} = P (x_{k}) − P (x_{k−1}) ≥ 0 and y_{k+1} − y_{k} = P (y_{k}) − P (y_{k−1}) ≤ 0. Moreover since E_{1} is regular there exist x^{∗}, y^{∗} such that (18) and (19) are satisfied.

That completes the proof of the Theorem.

Remark 4. (a) If x^{∗} = y^{∗} then x^{∗} = z = y^{∗}. Hence if z is a fixed point of P on [x_{0}, y_{0}] then P (x^{∗}) = x^{∗} = y^{∗} = P (y^{∗}).

(b) If z is the unique fixed point of P on [x_{0}, y_{0}] and P is continuous at x^{∗} and y^{∗} then since P (x^{∗}) = x^{∗} and P (y^{∗}) = y^{∗} we get x^{∗} = z = y^{∗}.

REFERENCES

[1] Argyros, I.K. and Szidarovszky, F. Convergence of general iteration schemes, J. Math. Anal. Appl. Vol. 168, No. 1 (1992), 42–62.

[2] Argyros, I.K. and Szidarovszky, F. The theory and applications of iteration methods, C.R.C. Press, Inc. Boca Raton, Florida, 1993.

[3] Demidovici, B.P. and Maron, A.I. Computational Mathematics, MIR Publ. Moscow, Russia, 1987.

[4] Kantorovich, L.V. and Akilov, G.P. Functional Analysis in Normed Spaces, Pergamon Press, New York, 1964.

[5] Krasnoleskii, M.A. Positive Solutions of Operator Equations, Noordhoff-Groningen Publ., 1964.

[6] Potra, F.A. Monotone iterative methods for nonlinear operator equations, Numer. Funct. Anal. Optimiz. Vol. 9, No. 7–8, (1987), 809–843.

[7] Slugin, S. Monotonic processes of bilateral approximation in a partially ordered convergence group, Soviet Math. 3 (1962), 1547–1551.

[8] Vandergraft, J.S. Newton’s method for convex operators in partially ordered spaces, SIAM J. Numer. Anal. 4 (1967), 406–432.