Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1997, pp. 18–22. Submitted: February 7, 1997. Published: July 23, 1997.

GENERAL WAYS OF CONSTRUCTING

ACCELERATING NEWTON-LIKE ITERATIONS ON

PARTIALLY ORDERED TOPOLOGICAL SPACES

Ioannis K. Argyros

Abstract. In this study, we examine the monotone convergence of Newton-like methods to a solution of an equation on a partially ordered topological space setting. In particular we provide sufficient conditions for the construction of accelerating sequences. This way the solution is obtained faster than in earlier results.

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

Key Words and Phrases. Partially ordered topological space, accelerating iteration, nonlinear equation.

I. INTRODUCTION

In this study, we are concerned with the problem of approximating a solution z of the equation

(1)  F_{1}(x) = 0

where F_{1} is a continuous operator defined on a closed convex subset D of a partially ordered topological space (POTL-space) E_{1} with values in a POTL-space E_{2} [3], [4], [8].

Sufficient conditions for the monotone convergence of Newton-like methods to z have been found by several authors (see [1]–[4], [7], [8] and the references there). Here we first transform (1) into a fixed point problem of the form

(2)  x = G_{1}(x)

and then consider iterations, of the form

(3)  x_{n+1} = G_{1}(x_{n}) (n ≥ 0),
(4)  ȳ_{n+1} = G_{2}(x_{n}) (n ≥ 0),

Typeset by AMS-TEX

Department of Mathematics, Cameron University, Lawton, OK 73505, U.S.A.

E-mail Address: ioannisa@cua.cameron.edu

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

and

(5)  y_{n+1} = G_{2}(y_{n}) (n ≥ 0)

for some continuous operators G_{1}, G_{2}: D → E_{2} with G_{1}(z) = G_{2}(z) whenever F_{1}(z) = 0. Under the conditions in the above-mentioned papers iteration {x_{n}} (n ≥ 0) converges to z. We then provide sufficient conditions that show that iterations {ȳ_{n}}, {y_{n}} (n ≥ 0) are accelerating sequences to z, in the sense that

(6)  y_{n} ≤ ȳ_{n} ≤ x_{n} (n ≥ 0) and lim_{n→∞} x_{n} = lim_{n→∞} = lim_{n→∞} ȳ_{n} = z.

Moreover in the case when E_{1} = E_{2} = R our results can be reduced to weaker versions of the corresponding ones in [5].

Finally we provide an example to justify (6).

II. MONOTONE CONVERGENCE

We state and prove the following main result on the monotone convergence of Newton-like methods on partially ordered topological spaces.

Theorem. Let F_{1}, F_{2} be continuous operators defined on a closed convex subset D of a partially ordered topological space E_{1} = (E_{1}, ≤) (POTL-space) with values in a POTL-space E_{2} = (E_{2}, ≤). Assume:

(a) there exists points a, z, b of D such that a ≤ z ≤ b, [a, b] ⊆ D and z is the only point in [a, b] such that

(7)  F_{1}(z) = F_{2}(z) = 0.

(b) There exists operators A_{1}(x), A_{2}(x) ∈ L(E_{2}, E_{1}) (x ∈ D) such that the Newton-like iterations

(8)  x_{n+1} = x_{n} − A_{1}(x_{n})F_{1}(x_{n}) (n ≥ 0)
(9)  y_{n+1} = y_{n} − A_{2}(y_{n})F_{2}(y_{n}) (n ≥ 0)

are decreasing and converging to z for some starting points x_{0}, y_{0} with x_{0} = y_{0} ≠ z and z ≤ x_{0} ≤ b.

(c) For all points x ∈ [a, b] there exists an operator L ∈ L(E_{1}, E_{2}) depending on F_{1}, F_{2}, z and x such that

(10)  0 ≤ L(x − z) = (G_{1} − G_{2})(x) − (G_{1} − G_{2})(z)

where

(11)  G_{1}(x) = x − A_{1}(x)F_{1}(x) and G_{2}(x) = x − A_{2}(x)F_{2}(x).

Then

(12)  (i)  the estimate y_{n} ≤ x_{n} holds for all n ≥ 0 such that x_{n} ≠ z.

(ii) x_{n−1} ≠ z and x_{n} = z imply y_{n} = z.

Proof: (i) We will show estimate (12) using mathematical induction on n ∈ N. For n = 0 estimate (12) is true as equality. Using (7)–(11) for n = 1 we obtain

0 ≤ L(x_{0} − z) = (G_{1} − G_{2})(x_{0}) − (G_{1} − G_{2})(z) = x_{1} − y_{1}

which shows (12) in this case. Assume that y_{k} ≤ x_{k} for k = 1, 2, …, n − 1. If x_{n} ≠ z then x_{n−1} ≠ z and from (7)–(11) we obtain

0 ≤ L(x_{n−1} − z) = (G_{1} − G_{2})(x_{n−1}) − (G_{1} − G_{2})(z) ≤ G_{1}(x_{n−1}) − G_{2}(y_{n−1})
= x_{n} − y_{n},

(since G_{2} is increasing in [z, b] and {y_{n}} ⊆ [z, b] (n ≥ 0)) which shows (12) for all n ≥ 0. Part (ii) follows easily by applying the arguments used in part (i).

That completes the proof of the Theorem.

Remark 1. It is easily seen that for E_{1} = E_{2} = R our theorem reduces to a weaker version of Theorem 1 in [5, p. 160] (see also [6]). A similar theorem can also be immediately stated for increasing sequences to z.

Remark 2. The condition that iteration {x_{n}} (n ≥ 0) is decreasing (similarly for iteration {y_{n}} (n ≥ 0)) can be replaced by: A_{1}(x) is a nonnegative linear operator and 0 ≤ F_{1}(x) for x ∈ [z, b].

Remark 3. Operator L appearing in (10) can be chosen as L = [z, x; G_{1} − G_{2}]. That is as a divided difference of order one on D at the points z, x for the operator G_{1} − G_{2} [3], [4], [7], [8].

Remark 4. Several sufficient conditions for the monotone convergence of iterations {x_{n}}, {y_{n}} (n ≥ 0) to z can be found in [3], [4], [7], [8] and the references there. In our theorem above we did not add such conditions to avoid repetitions and because we want to keep it as uncluttered and simple as possible.

Remark 5. Another choice for the operator L can be given by L = A_{2}(x)[z, x; F_{2}]− A_{1}(x)[z, x; F_{1}]. Indeed we can get from the identity

G_{1}(x) − G_{2}(x) = x − A_{1}(x)F_{1}(x) − x + A_{2}(x)F_{2}(x)
= A_{2}(x)(F_{2}(x) − F_{2}(z)) − A_{1}(x)(F_{1}(x) − F_{1}(z))
= (A_{2}(x)[z, x; F_{2}] − A_{1}(x)[z, x; F_{1}])(x − z)
= L(x − z),

which justifies the choice for L.

Remark 6. A reasonable choice for the operator F_{2} can be given by

F_{2}(x) = A_{3}(x)F_{1}(x) + F_{3}(x, z)

for some A_{3}(x) ∈ L(E_{1}, E_{2}) and F_{3}: D → E_{2} such that F_{2}(z) = 0 whenever F_{1}(z) = 0. Assume that [z, x; F_{1}] is a divided difference of order one on D at the points z, x ∈ D for the operator F_{1}. We can write

G_{1}(x) − G_{2}(x) = x − A_{1}(x)F_{1}(x) − x + A_{2}(x)F_{2}(x)
= A_{2}(x)(A_{3}(x)F_{1}(x) + F_{3}(x, z)) − A_{1}(x)F_{1}(x)
= (A_{2}(x)A_{3}(x) − A_{1}(x))(F_{2}(x) − F_{1}(z)) + A_{2}(x)F_{3}(x, z)
= (A_{2}(x)A_{3}(x) − A_{1}(x))[z, x; F_{1}](x − z) + A_{2}(x)F_{3}(x, z)

and for F_{3}(x, z) = F_{4}(x, z)(x − z), we get G_{1}(x) − G_{2}(x) = L(x, z) where

(13)  L = [A_{2}(x)A_{3}(x) − A_{1}(x)][z, x; F_{1}] + A_{2}(x)F_{4}(x, z).

Natural conditions can be imposed on the operators appearing in the above approximation (13) so that (10) is satisfied. In [5] for E_{1} = E_{2} = R operators A_{3} and F_{3} were chosen such that

A_{3}(x) = 1 and F_{3}(x, z) = −\frac{1}{2}F′′_{1}(z)(x − z)^{2}.

Since z is an unknown point it was replaced by x_{n−1} and a new iterative process involving the second derivative of order three was found. With the exception of some special cases this iterative process has no practical value since they require an evaluation of the second Fréchet-derivative at each step which means a number of function evaluations proportional with the cube of the dimension of the space. In [3], [4] discretized versions of F_{3} were considered on a POTL-space using divided differences of order one. Operator F_{3} is now defined by

F_{3}(x_{n}, x_{n−1}) = −([x_{n−1}, x_{n}] − [x_{n−1}, x_{n−1}])(x_{n−1} − x_{n}) (n ≥ 1).

Several other variations of the above discretized scheme are also possible [3], [4], [7], [8].

We now complete this study by providing an example for the last remark.

Example. Let E_{1} = E_{2} = R, [a, b] = [−\frac{1}{3}, \frac{1}{3}], F_{1}(x) = x^{2} and x_{0} = .2. Note that z = 0 is the only zero of equation F_{1}(x) = 0 on [a, b]. Consider iterations

x_{n+1} = x_{n} − x_{n}^{2}, ȳ_{n+1} = x_{n} − 2x_{n}^{2} and y_{n+1} = y_{n} − 2y_{n}^{2} (n ≥ 0).

Iterations {ȳ_{n}}, {y_{n}} (n ≥ 0) are accelerations of {x_{n}} (n ≥ 0) with y ≤ ȳ_{n} ≤ x_{n} (n ≥ 0) and lim_{n→∞} y_{n} = lim_{n→∞} ȳ_{n} = lim_{n→∞} x_{n} = z = 0, which justifies (6).

In what follows we tabulate the first seven iterates for each iteration for comparison:

x_{0} = .2, x_{1} = .16, x_{2} = .1344, x_{3} = .1163366, x_{4} = .1028024,
x_{5} = .0922341, x_{6} = .083727, x_{7} = .0767168,
ȳ_{0} = .2, ȳ_{1} = .12, ȳ_{2} = .1088, ȳ_{3} = .0982733, ȳ_{4} = .0892682,
ȳ_{5} = .0816657, ȳ_{6} = .0752198, ȳ_{7} = .0697066,
y_{0} = .2, y_{1} = .12, y_{2} = .0912, y_{3} = .0745651, y_{4} = .0634452,
y_{5} = .0553946, y_{6} = .0492575, y_{7} = .0444049.

REFERENCES

[1] Argyros, I.K. A unified approach for constructing fast two-step Newton-like methods, Monatshefte für Mathematik, 119 (1995), 1–22.

[2] Argyros, I.K. On the Super-Halley method using divided differences, Appl. Math. Letters (to appear).

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

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

[5] Hernandez, M.A. Newton-Raphson’s method and convexity, Zb. Rad. Prirod.-Mat. Fak. Ser. Mat., 22, 1, (1992), 159–166.

[6] Hernandez, M.A. and Salanova, M.A. A family of Newton-type iterative process, Inter. J. Computer Math. 51, (1994), 205–214.

[7] Potra, F.A. On an iterative algorithm of order 1.839 … for solving nonlinear operator equations, Numer. Funct. Anal. Optimiz. 7, (1), (1984–85), 75– 106.

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