Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 02, 1996, pp. 55–59. Submitted: September 23, 1996. Published: November 7, 1996.

ON THE MONOTONE CONVERGENCE

OF IMPLICIT NEWTON-LIKE METHODS

Ioannis K. Argyros

Abstract. In this study, we examine the convergence of implicit Newton-like methods to a solution of a nonlinear equation on a partially ordered topological space. We generate two sequences, one increasing and one decreasing that enclose a solution of the nonlinear equation. Finally, we provide an example that shows that our method converges whereas the standard explicit Newton-like method does not.

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

Key Words and Phrases. Newton-like method, monotone convergence, partially ordered topological space.

I. INTRODUCTION

In this study, we are concerned with the problem of approximating a solution z^{∗} of the nonlinear operator equation

(1)  F (x) = 0

where F is a continuous nonlinear operator defined on a subset D of a partially ordered topological space (POTL-space) E_{1} with values in a POTL-space E_{2} [2], [3], [5].

We introduce implicit Newton-like methods of the form

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

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

to monotonically enclose z^{∗}. Here operators A^{1}, A^{2}: D^{2} → L(E_{1}, E_{2}) are satisfying certain convexity type conditions.

Typeset by AMS-TEX

Cameron University, Lawton, Oklahoma

E-mail Address: ioannisa@cameron.edu

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

So far explicit Newton-like methods of the form

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

(5)  F (y_{n}) + A^{2}(y_{n}, y_{n−1})(y_{n+1} − y_{n}) = 0 (n ≥ 0)

as well as various explicit configurations of them have been extensively examined [1]–[5] under the natural hypothesis

(6)  F (y) − F (x) ≤ A(w, z)(y − x)

for all x_{0} ≤ x ≤ y ≤ w ≤ z ≤ y_{0} where [x_{0}, y_{0}] ⊆ D.

One can provide examples where iterations (2) and (3) converge to a solution z^{∗} of equation (1) whereas iterations (4) and (5) do not. (See the example at the end of this study.) On the other hand the convergence results developed so far for (4) and (5) provide no information about the behavior of iterations (2) and (3).

Sufficient convergence conditions are provided for monotonically enclosing a solution z^{∗} of equation (1) as well as some applications. In particular we provide an example that shows that our results apply where the earlier ones fail.

II. MONOTONE CONVERGENCE

The main result of our study is contained in the following theorem:

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

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

Assume there exist nonnegative operators A^{1}, A^{2}: D^{2} → L(E_{1}, E_{2}) with continuous nonsingular nonnegative left subinverses B^{1} and B^{2} respectively such that

(8)  B(v, w)(F (y) − F (x)) ≤ (I − B(v, w)A(v, w))(y − x)

where (B, A) is (B^{1}, A^{1}) or (B^{2}, A^{2}) for all v, w, x, y ∈ D with x_{0} ≤ v ≤ w ≤ x ≤ y ≤ y_{0}.

Then there exist two iterations {x_{n}} (n ≥ 1), {y_{n}} (n ≥ 1) and two points x^{∗}, y^{∗} of D such that for all n ≥ 0 approximations (2) and (3) are solvable,

(9)  F (x_{n}) ≤ 0 ≤ F (y_{n})

(10)  x_{0} ≤ x_{1} ≤ ⋯ ≤ x_{n} ≤ x_{n+1} ≤ y_{n+1} ≤ y_{n} ≤ ⋯ ≤ y_{1} ≤ y_{0},

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

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

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

Clearly H is continuous and for x ≤ y we deduce that H is isotone. Indeed from (8) we get

B_{0}^{1}(F (y) − F (x)) ≤ (I − B_{0}^{1}A_{0}^{1})(y − x) ⇒

x − B_{0}^{1}(F (x)) − B_{0}^{1}A_{0}^{1}(x − x_{0}) ≤ y − B_{0}^{1}(F (y)) − B_{0}^{1}A_{0}^{1}(y − x_{0})
⇒ H(x) ≤ H(y).

We also have

H(x_{0}) = x_{0} − B_{0}^{1}(F (x_{0}) + A_{0}^{1}(x_{0} − x_{0})) = x_{0} − B_{0}^{1}(F (x_{0})) ≥ x_{0}

by (7),

H(y_{0}) = y_{0} − B_{0}^{1}(F (y_{0}) + A_{0}^{1}(y_{0} − x_{0})) ≤ y_{0}

by (7) and the fact that A_{0}^{1} and B_{0}^{1} are nonnegative operators on D^{2}. It follows from the Kantorovich theorem on fixed points that H has a fixed point x_{1} ∈ [x_{0}, y_{0}]. That is H(x_{1}) = x_{1} which shows that x_{1} solves (2) for n = 0. It also follows from (2) for n = 0 that F (x_{1}) ≤ 0.

Let B_{0}^{2} be a continuous nonsingular nonnegative left subinverse of A_{0}^{2} = A^{2}(y_{0}, y_{−1}) and define the operator G: [x_{1}, y_{0}] → E_{1} by

G(x) = x − B_{0}^{2}(F (x) − A_{0}^{2}(y_{0} − x)).

Operator G is clearly continuous and exactly as above using (8) we can show that it is isotone.

Moreover we have

G(x_{1}) = x_{1} − B_{0}^{2}(F (x_{1}) − A_{0}^{2}(y_{0} − x_{1})) ≥ x_{1}

(since F (x_{1}) ≤ 0 and A_{0}^{2} is nonnegative),

G(y_{0}) = y_{0} − B_{0}^{2}(F (y_{0}) − A_{0}^{2}(y_{0} − x_{0})) ≤ y_{0}

(since F (y_{0}) ≥ 0). Hence there exists y_{1} ∈ [x_{1}, y_{0}] with G(y_{1}) = y_{1}. That is y_{1} solves approximation (3) for n = 0 and F (y_{1}) ≥ 0.

Proceeding by induction on n ≥ 0 we can show that there exist two iterations {x_{n}} (n ≥ 1), {y_{n}} (n ≥ 1) satisfying (2), (3), (9) and (10). Moreover since the space E_{1} is regular it follows that there exist x^{∗}, y^{∗} ∈ E_{1} satisfying (11).

That completes the proof of the Theorem.

In what follows we shall give some natural conditions under which the points x^{∗} and y^{∗} are solutions of the equation F (x) = 0.

Theorem 2. Under the hypotheses of Theorem 1 suppose that F is continuous at x^{∗} and y^{∗}. If one of the following conditions is satisfied:

(a) x^{∗} = y^{∗};

(b) operators A_{n}^{1}, A_{n}^{2} (n ≥ 0) are equicontinuous;

(c) E_{2} is normal and there exists an operator P: E_{1} → E_{2} (P (0) = 0) continuous on the origin and such that A_{n}^{1} ≤ S, A_{n}^{2} ≤ S for sufficiently large n;

(d) E_{1} is normal and there exists an operator Q: E_{1} → E_{2} (Q(0) = 0) which has an isotone inverse continuous at the origin and such that A_{n}^{1} ≤ Q, A_{n}^{2} ≤ Q for sufficiently large n.

Then we have

F (x^{∗}) = F (y^{∗}) = 0.

Proof. Using the continuity of F and (9) we get F (x^{∗}) ≤ 0 ≤ F (y^{∗}) by letting n → ∞. That is F (x^{∗}) = F (y^{∗}) = 0.

(b) By the equicontinuity of the operators A_{n}^{1}, A_{n}^{2} it follows that lim_{n→∞} A_{n}^{1}(x_{n}− x_{n+1}) = lim_{n→∞} A_{n}^{2}(y_{n} − y_{n+1}) = 0, and by (2) and (3), by letting n → ∞ and using the continuity of F at x^{∗} and y^{∗} we get F (x^{∗}) = F (y^{∗}) = 0.

(c) For sufficiently large n we get

0 ≥ F (x_{n+1}) ≥ P (x_{n} − x_{n+1}), 0 ≤ F (y_{n+1}) ≤ P (y_{n} − y_{n+1}).

By the normality of E_{2} and the continuity of F and P we get F (x^{∗}) = F (y^{∗}) = 0. (d) By (2), (3), (9) and (10) we get

0 ≥ F (x_{n+1}) = A_{n}^{1}(x_{n} − x_{n+1}) ≥ Q(x_{n} − x_{n+1}),
0 ≤ F (y_{n+1}) = A_{n}^{2}(y_{n} − y_{n+1}) ≤ Q(y_{n} − y_{n+1}).

Hence, we get

lim_{n→∞} Q^{−1}(F (x_{n+1})) = lim_{n→∞} Q^{−1}(F (y_{n+1})) = 0,

since E_{1} is normal and lim_{n→∞}(x_{n} − x_{n+1}) = lim_{n→∞}(y_{n} − y_{n+1}) = 0. That is by the continuity of F we finally get F (x^{∗}) = F (y^{∗}) = 0.

That completes the proof of the Theorem.

Example. Let D = E_{1} = E_{2} = R and F (x) = \frac{1}{2}x. Choose A^{1} = A^{2} = \frac{1}{4}, B^{1} = B^{2} = 1, x_{−1} = −2, x_{0} = −1, y_{0} = 1 and y_{−1} = 2. Then it can easily be seen that all hypotheses of Theorem 1 are satisfied and (2) becomes x_{n+1} = \frac{1}{3}x_{n} = (\frac{1}{3})^{n+1} x_{0} which converges to the unique solution z^{∗} = 0 of equation F (x) = 0. However condition (6) is not satisfied and iteration (4) becomes x_{n+1} = −x_{n} ↛ 0 for any x_{0} ≠ 0.

The uniqueness of the solution z^{∗} of the equation F (x) = 0 in [x_{0}, y_{0}] can be proved by assuming a condition complementary to (8). In particular we can show the following:

Theorem 3. Let E_{1} and E_{2} be two POL-spaces, F: D ⊆ E_{1} → E_{2} be a nonlinear operator and x_{0}, y_{0} ∈ D with x_{0} ≤ y_{0} and [x_{0}, y_{0}] ⊆ D. Assume:

(a) there exists an operator M: D^{2} → L(E_{1}, E_{2}) such that M(x, y) has a nonnegative left superinverse on D^{2} and

(12)  F (y) − F (x) ≥ M(x, y)(y − x)

for all (x, y) ∈ D^{2}.

(b) (x^{∗}, y^{∗}) ∈ D and F (x^{∗}) = F (y^{∗}).

Then we deduce

x^{∗} = y^{∗}.

Proof: Let M_{1}(x^{∗}, y^{∗}) be a nonnegative left superinverse of M(x^{∗}, y^{∗}). Then by (12) we get

0 ≤ y^{∗} − x^{∗} ≤ M_{1}(x^{∗}, y^{∗})M(x^{∗}, y^{∗})(y^{∗} − x^{∗})
≤ M_{1}(x^{∗}, y^{∗})(F (x^{∗}) − F (y^{∗})) = 0.

That is we deduce x^{∗} = y^{∗}.

That completes the proof of the Theorem.

Remark. Several configurations other than (2) and (3) can also be considered. See [1], [2], [4] for other configurations for explicit Newton-like methods. For example our results can apply to prove convergence for the implicit Newton-like method given by

F (x_{n+1}) + A(y_{n}, y_{n−1})(x_{n+1} − x_{n}) = 0 (n ≥ 0)
F (y_{n+1}) + A(y_{n}, y_{n−1})(y_{n+1} − y_{n}) = 0 (n ≥ 0)

where A: D^{2} → L(E_{1}, E_{2}).

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] Krasnoleskii, M.A. Positive Solutions of Operator Equations, Noordhoff-Groningen Publ., 1964.

[4] Potra, F.A. Newton-like methods with monotone convergence for solving nonlinear operator equations, Nonlinear Anal. Theory, Methods, Appl. Vol. 11, No. 6, (1987), 697–717.

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