Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1997, pp. 30–36. Submitted: March 4, 1997. Published: July 31, 1997.

A LOCAL CONVERGENCE THEOREM FOR THE

INEXACT NEWTON METHOD AT SINGULAR POINTS

Ioannis K. Argyros

Abstract. If Newton’s method is used to find a solution of an equation on a Banach space, and the Fréchet-derivative is singular at the solution, the convergence of Newton iterates to the solution is linear rather than quadratic. In this study we employ the inexact Newton method to restore quadratic convergence, especially in cases when Newton’s or the corrected Newton’s method cannot achieve this or cannot even be used.

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

Key Words and Phrases. Banach space, Newton method, singular points, quadratic convergence.

I. INTRODUCTION

In this study we are concerned with the problem of approximating a solution x^{∗} of the equation

(1)  F (x) = 0

where F is an operator defined on a closed convex subset D of a Banach space E_{1} with values on a Banach space E_{2}.

Newton’s method

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

is the most popular way of generating a sequence {y_{n}} (n ≥ 0) converging to x^{∗}. According to the well-known Newton-Kantorovich theorem [3], [5], [7] method (2) converges quadratically to x^{∗} provided ∥x_{0} −x^{∗}∥ is small and the Fréchet derivative F′(x^{∗}) is an invertible operator. The solution x^{∗} is called isolated in this case. A solution x^{∗} at which F′(x^{∗}) is not invertible is called singular. Method (2) converges to x^{∗}, only linearly in this case [3], [5], [7].

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

In [6] and the references there the convergence behavior of method (2) has been studied. Roughly speaking the Banach space E_{1} is written as a direct, N ⊕ E, sum of the null space N of F′(x^{∗}) and an appropriate complementing space E. Then, when the iterates converge, the components of the iterate error in N converges linearly, while the E-component of the error converges with asymptotic order 2. This technique is considered rather complicated, and most importantly it is assumed that the iterates can be computed exactly. However this is not the case most of the time. That is why we propose the study of the inexact Newton method of the form

(3)  x_{n+1} = x_{n} − P′(x_{n})^{−1}F (x_{n}) − z_{n},

where

(4)  F (x) = P (x) + Q(x) (x ∈ D),

F (x^{∗}) = 0, P′(x^{∗}) is invertible and P, Q: D → E_{2} are Fréchet-differentiable operators on D.

The importance of studying the inexact Newton method (3) comes from the fact that many commonly used variants of Newton’s method can be considered procedures of this type. Indeed approximation (3) characterizes any iterative process in which corrections are taken as approximate solutions of Newton equations. If for example an equation on the real line is solved, F (x_{n}) ≥ 0 (n ≥ 0), and P′(x_{n})^{−1} (n ≥ 0) overestimates the derivative, y_{n} is always larger than the corresponding Newton iterate. In such cases, a positive z_{n} (n ≥ 0) correction term is appropriate. Points z_{n} ∈ D (n ≥ 0) are determined in such a way that iteration {x_{n}} (n ≥ 0) converges to a solution x^{∗} of equation (1). Sufficient conditions for the convergence of method (3) to x^{∗} have been given in [1]–[4], [7] under various assumptions. Here as in [6] and the references there we will assume that x^{∗} exists but we will not construct N and E which are very expensive to produce in general. A local convergence theorem is given an special choices of the points z_{n} (n ≥ 0) that restore quadratic convergence in some cases will be given.

Finally a numerical example is also provided to show that quadratic convergence can be restored in the case when Newton’s method or the corrected Newton’s method cannot even be used.

II. CONVERGENCE ANALYSIS

Let F, Q be Fréchet-differentiable on D ⊆ E_{1}, x^{∗} ∈ D with F (x^{∗}) = 0, P′(x^{∗}) invertible on D, a, b, c, c_{n} (n ≥ 0) nondecreasing functions on the nonnegative axis, R ≥ 0 such that:

(5) ∥(F′(x^{∗}) − Q′(x^{∗}))^{−1}[F′(x + t(x^{∗} − x)) − F′(x)]∥ ≤ a(∥x^{∗} − x∥)∥x^{∗} − x∥t,

(6)  ∥(F′(x^{∗}) − Q′(x^{∗}))^{−1}(Q′(x^{∗}) − Q′(x))∥ ≤ b(∥x − x^{∗}∥),

and

(7) ∥(F′(x^{∗}) − Q′(x^{∗}))^{−1}B_{n}∥ ≤ c_{n}(∥x^{∗} − x_{n}∥)∥x_{n} − x^{∗}∥ ≤ c(∥x^{∗} − x_{n}∥)∥x_{n} − x^{∗}∥,

where

(8) B_{n} = (Q′(x_{n}) − F′(x_{n}))z_{n} − Q′(x_{n})(x_{n} − x^{∗}) (n ≥ 0) with x_{n} given by (3),

and for all x, x_{n} ∈ U(x^{∗}, r) = {x ∈ E_{1} | ∥x − x^{∗}∥ ≤ r} ⊆ U(x^{∗}, R) ⊆ D, t ∈ [0, 1]. It is convenient to define on the nonnegative axis the functions f_{1} and f_{2} by

(9)  f_{1}(r) = 1 − b(r) − a(r)r,

and

(10)  f_{2}(r) = 3a(r)r + 2c(r) + 2b(r) − 2.

We can now state and prove the following local convergence result concerning the inexact Newton method (3):

Theorem. Assume F, Q, P be Fréchet-differentiable operators defined on a closed convex subset D of a Banach space E_{1} with values in a Banach space E_{2}, x^{∗} ∈ D with F (x^{∗}) = 0, P′(x^{∗}) invertible on D, a, b, c, c_{n} (n ≥ 0) nondecreasing functions on the nonnegative axis and R ≥ 0 such that:

(a) conditions (5)–(7) are satisfied;

(b) there exists an interval [0, d], d < R such that

(11)  f_{1}(r) > 0,

and

(12)  f_{2}(r) < 0,

for all r ∈ [0, d].

(c) U(x_{0}, d) ⊆ D. Then the inexact Newton method {x_{n}} (n ≥ 0) generated by (3) is well defined remains in U(x^{∗}, d) for all n ≥ 0 and converges to x^{∗} provided that x_{0} ∈ U(x^{∗}, d). Moreover the following error bounds hold for all n ≥ 0

(13)  ∥x_{n+1} − x^{∗}∥ ≤ \frac{1}{1 − b(∥x_{n} − x^{∗}∥) − a(∥x_{n} − x^{∗}∥)∥x_{n} − x^{∗}∥}ε̄_{n}

≤ \frac{1}{1 − b(d) − a(d)d}ε_{n}, (14)

where

(15)  ε̄_{n} = [\frac{1}{2}a(∥x_{n} − x^{∗}∥) + c_{n}(∥x_{n} − x^{∗}∥)] ∥x_{n} − x^{∗}∥

and

(16)  ε_{n} = [\frac{1}{2}a(d) + c(d)] ∥x_{n} − x^{∗}∥.

Proof: By hypothesis the point x_{0} belongs in U(x^{∗}, d). Assume x_{k} ∈ U(x^{∗}, d) for k = 0, 1, 2, …, n. Then using (6), (7), the Banach Lemma on invertible operators [7], the approximation

F′(x_{k}) − Q′(x_{k}) = F′(x_{k}) − Q′(x_{k}) − (F′(x^{∗}) − Q′(x^{∗})) + (F′(x^{∗}) − Q′(x^{∗}))

and the estimate

∥(F′(x^{∗}) − Q′(x^{∗}))^{−1}[(F′(x_{k}) − F′(x^{∗})) − (Q′(x_{k}) − Q′(x^{∗}))]∥ ≤ a(∥x_{k} − x^{∗}∥)∥x_{k} − x^{∗}∥ + b(∥x_{k} − x^{∗}∥) ≤ a(d)d + b(d) < 1 (by (12)),

it follows that P′(x_{k})^{−1} exists and

∥P′(x_{k})^{−1}(F′(x^{∗}) − Q′(x^{∗}))∥ ≤ [1 − b(∥x_{k} − x^{∗}∥) − a(∥x_{k} − x^{∗}∥)∥x^{∗} − x_{k}∥]^{−1} (17)

≤ [1 − b(d) − a(d)d]^{−1}. (18)

Using (3) and (8) we obtain the approximation

x_{k+1} − x^{∗} = x_{k} − x^{∗} − P′(x_{k})^{−1}F (x_{k}) − z_{k}

= [F′(x_{k}) − Q′(x_{k})]^{−1}[F′(x^{∗}) − Q′(x^{∗})][F′(x^{∗}) − Q′(x^{∗})]^{−1}· (19)

· {∫_{0}^{1}[F′(x_{k} + t(x^{∗} − x_{k})) − F′(x_{k})](x^{∗} − x_{k})dt + B_{k}} .

Using (5)–(7), (17) and (18) we obtain (13) and (14). Moreover by (12) and (14)

(20)  ∥x_{k+1} − x^{∗}∥ ≤ ε∥x_{k} − x^{∗}∥ ≤ ⋯ ≤ ε^{k+1}∥x_{0} − x^{∗}∥ ≤ ε^{k+1}d

for

(21)  ε = \frac{a(d) + 2c(d)}{2[1 − b(d) − a(d)d]} ∈ [0, 1).

It follows from (20) and (21) that

x_{k} ∈ U(x^{∗}, d) for all k ≥ 0 and lim_{k→∞} x_{k} = x^{∗}.

That completes the proof of the Theorem.

Remark 1. We note that in the proof of the Theorem we have not used (or assumed) that F′(x^{∗}) = 0.

Remark 2. Set z_{n} = 0 (n ≥ 0), E_{1} = E_{2} = R and assume x^{∗} is a zero of multiplicity m for F. Choose Q(x) = (1 − m)F (x) to obtain using (4) that P (x) = mF (x). In this case (3) reduces to the corrected Newton’s method which converges quadratically to x^{∗} [5], [7].

Remark 3. Choose z_{n} = P′(x_{n})^{−1}Q′(x_{n})(x^{∗} − x_{n}) (n ≥ 0) then by (7) we can choose c_{n} = c = 0 (n ≥ 0). Moreover if a(t) = qt, t ∈ [0, d] for some q ≥ 0 we obtain by (13) that the order of convergence of method (3) is quadratic.

Remark 4. Let z_{n} = L_{n}(x_{n} − x_{n−1}) (n ≥ 1), for some bounded linear operators L_{n}, z_{0} = 0, x_{0}, x_{1} ∈ U(x^{∗}, d), ∥L_{n}∥ ≤ ∥x_{n} − x^{∗}∥ (n ≥ 0) and c_{n} given by

c_{n}(∥x_{n} − x^{∗}∥) = s_{1}(∥x_{n} − x^{∗}∥)∥x_{n} − x^{∗}∥^{p_{1}} + s_{2}(∥x_{n} − x^{∗}∥)∥x_{n} − x_{n−1}∥^{p_{2}}

+ s_{3}(∥x_{n} − x^{∗}∥)∥x_{n} − x^{∗}∥^{p_{3}}∥x_{n} − x_{n−1}∥^{p_{4}} + s_{4}(∥x_{n} − x^{∗}∥),

for all n ≥ 1 where s_{1}, s_{2}, s_{3}, s_{4} are nondecreasing functions on [0, d] and p_{1}, p_{2}, p_{3} and p_{4} are nonnegative numbers. Moreover assume there exists h such that

∥(F′(x^{∗}) − Q′(x^{∗}))^{−1}Q′(z)∥ ≤ h for z = x^{∗} or x_{0}.

Furthermore assume F′(x^{∗}) = 0. Then from the approximation B_{n} = (Q′(x_{n}) − F′(x_{n}))L_{n}(x_{n} − x_{n−1}) − Q′(x_{n})(x_{n} − x^{∗}), we obtain

∥(F′(x^{∗}) − Q′(x^{∗}))^{−1}B_{n}∥ ≤ a(∥x_{n} − x^{∗}∥)∥L_{n}∥ ∥x_{n} − x^{∗}∥ · ∥x_{n} − x_{n−1}∥
+ (b(∥x_{n} − x^{∗}∥) + h)∥L_{n}∥ ∥x_{n} − x_{n−1}∥
+ (b(∥x_{n} − x^{∗}∥ + h)∥x_{n} − x^{∗}∥.

Hence we can take s_{1}(r) = 0, s_{2}(r) = b(r) + h, c_{3}(r) = a(r), c_{4}(r) = b(r) + h, r ∈ [0, d], p_{2} = p_{3} = p_{4} = 1 any p_{1} > 0, and

c(r) = max{c̄(r), h}, r ∈ [0, d]

where

c̄(r) = s_{1}(r)r^{p_{1}} + 2^{p_{2}}s_{2}(r)r^{p_{2}} + 2^{p_{4}}s_{3}(r)r^{p_{3}+p_{4}} + s_{4}(r), r ∈ [0, d].

Remark 5. Our Theorem can be used to solve autonomous differential equations satisfying

P′(x) = T (F (x))

for some continuous operator T. Since P′(x^{∗}) = T (F (x^{∗})) = T (0) the inverse of P′(x^{∗}) can be computed without knowing the solution x^{∗} [3], [7].

Remark 6. Our results can be extended to include a wider class of inexact Newton methods of the form

(22)  x_{n+1} = x_{n} − P_{1}(x_{n})^{−1}F (x_{n}) − z_{n} (n ≥ 0)

related to

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

where

A(x) = P_{1}(x) + Q_{1}(x) (x ∈ D)

and A(x), P_{1}(x), Q_{1}(x) ∈ L(E_{1}, E_{2}) (x ∈ D), with A(x) being an approximation to F′(x) (x ∈ D). The conclusions of the theorem will hold for method (22) assuming the following changes: In (5) replace F′(x^{∗}), Q′(x^{∗}) and F′(x) by A(x^{∗}), Q_{1}(x^{∗}) and A(x) respectively; in (6) replace F′(x^{∗}), Q′(x^{∗}) and Q′(x) by A(x^{∗}), Q_{1}(x^{∗}) and Q_{1}(x) respectively; in (7) replace F′(x^{∗}), Q′(x^{∗}) by A(x^{∗}) and Q_{1}(x^{∗}) respectively and in (8) replace Q′(x_{n}), F′(x_{n}) by Q_{1}(x_{n}) and A(x_{n}) (n ≥ 0) respectively. Then exactly as in the proof of the theorem using the approximation

x_{n+1} − x^{∗} = P_{1}(x_{n})^{−1}[F (x^{∗}) − F (x_{n}) − A(x_{n})(x^{∗} − x_{n}) + B_{n}]

we can show all the conclusions of the theorem. Comments similar to the ones made in Remarks 1–5 can also be made for method (22).

We will finish this study with an example related with Remark 3.

Example. Let E_{1} = E_{2} = R, x^{∗} = 0, R = d ∈ [0, \frac{1}{3}), U(x^{∗}, d) = D, consider the operator F on D given by

(23)  F (x) = x^{2}.

Choose

(24)  z_{n} = (1 − 2x_{n})^{−1}(x_{n} − x^{∗}) (n ≥ 0) for |x_{0}| ∈ U(0, d).

and

(25)  Q(x) = x (x ∈ D).

Using (5)–(10), (23), (24) and (25) we can choose a(r) = 2, b(r) = c(r) = 0 for all r ∈ [0, d]. Moreover we have B_{n} = 0 (n ≥ 0), f_{1}(r) = 1 − 2r > 0 and f_{2}(r) = 6r − 2 < 0 for all r ∈ [0, d]. Furthermore q = 0 in Remark 3. Hence all hypotheses of the Theorem are satisfied and (13) becomes

x_{n+1} − x^{∗} = (2x_{n} − 1)^{−1}(x_{n} − x^{∗})^{2} (n ≥ 0),

which shows quadratic convergence of sequence {x_{n}} (n ≥ 0) to x^{∗}. We also note that x^{∗} = 0 is a zero of multiplicity 2 for F given by (23).

We observe that as it can easily be seen Newton’s method cannot be used since F′(x_{n})^{−1} ≠ 0 (n ≥ 0) and y_{n+1} = y_{n} − F′(y_{n})^{−1}F (y_{n}) cannot be computed in any neighborhood of zero, for any starting point y_{0}. The corrected Newton’s method w_{n+1} = w_{n} − 2F′(w_{n})^{−1}F (w_{n}) (n ≥ 0) converges quadratically to x^{∗} [3], [5], [7], provided that z_{n} = 0 (n ≥ 0), which is not true in general.

REFERENCES

[1] Argyros, I.K. A convergence theorem for Newton-like methods under generalized Chen-Yamamoto type assumptions, Appl. Math. Comp. 61, 1, (1994), 25–37.

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

[3] Argyros, I.K. and Szidarovszky, F. The Theory and Applications of Iteration Methods, C.R.C. Press, Inc. Boca Raton, Florida, U.S.A., 1993.

[4] Argyros, I. K. and Szidarovszky, F. On the convergence of modified contractions. J. Comput. Appl. Math. 55, 2, (1994), 183–189.

[5] Atkinson, K. An Introduction to Numerical Analysis, Wiley Publ., New York, U.S.A., 1988.

[6] Decker, D.W., Keller, H.B. and Kelley, C.T. Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal. 20, 2, (1983), 296–314.

[7] Kantorovich, L.V. and Akilov, G.P. Functional Analysis, Pergamon Press, New York, U.S.A., 1982.