View of Local convergence of some Newton-type methods for nonlinear systems

Rev. Anal. Num´er. Th´eor. Approx., vol. 33 (2004) no. 2, pp. 209–213 ictp.acad.ro/jnaat

LOCAL CONVERGENCE OF SOME NEWTON-TYPE METHODS FOR NONLINEAR SYSTEMS^∗

ION P ˘AV ˘ALOIU^†

Dedicated to Professor Elena Popoviciu on the occasion of her 80th birthday.

Abstract. In order to approximate the solutions of nonlinear systems F(x) = 0,

withF :D⊆Rⁿ→Rⁿ,n∈N, we consider the method xk+1=xk−AkF(xk)

Ak+1=Ak(2I−F⁰(xk+1)Ak), k= 0,1, ..., A0∈Mn(R), x0∈D, and we study its local convergence.

MSC 2000. 65H10.

Keywords. Nonlinear systems of equations.

1. INTRODUCTION

Most of the problems regarding the methods of approximating the solutions of nonlinear equations in abstract spaces lead, as is well known, to solving of linear systems in Rⁿ, n ∈ N. From here, the importance of the study of the methods of approximating the solutions of linear and nonlinear problems in Rⁿ.

For the linear systems there have been studied several methods which offer very good results for some relatively large classes of problems. In the case of the nonlinear systems, the number of the methods is limited and the possibility of their applications differs from system to system.

One of the most used methods is the Newton method. The application of this method to nonlinear systems requires at each step the approximate solution of a linear system. It is well known that the matrix of this linear system is given by the Jacobian of the nonlinear system.

The approximate computation of the elements of the matrix may introduce not only truncation errors, but also rounding errors, and therefore the resulted

∗This work has been supported by the Romanian Academy under grant GAR 16/2004.

†“T. Popoviciu” Institute of Numerical Analysis, O.P 1, C.P. 68, Cluj-Napoca, and North University Baia Mare, Romania, e-mail: [email protected].

linear system at each iteration step is a perturbed one. Further errors may appear from the algorithm used for solving the linear system.

A method which can overcome a part of the above mentioned difficulties seems to be the one which at each iteration step uses an approximation for the inverse of the Jacobian.

More precisely, letF :D⊆Rⁿ→Rⁿ and the equation

(1) F(x) = 0.

We denote byM_n(R) the set of the square matrices of ordern, having real elements.

Letx0 ∈D and A0 ∈Mn(R).Consider the sequences (x_k)_k≥0 and (A_k)_k≥0 given by

xk+1=xk−AkF(xk) (2)

A_k+1=A_k(2I−F⁰(x_k+1)A_k), k= 0,1, ...

whereI is the unity matrix.

The matrices A_k approximate, as we shall see, the inverse of the Jacobian matrix.

In this note we show that locally, the r-convergence order of the sequence (x_k)_k≥0 is the same as for the sequence given by the Newton method, i.e., 2.

This result completes those obtained in [1]–[7].

2. LOCAL CONVERGENCE

The following results have maybe a smaller practical importance, but they prove that, theoretically, the Newton method and method (2) offer the same results regarding the local convergence. Method (2) presents the advantage that eliminates the algorithm errors mentioned above. However, the trun- cation and the rounding errors cannot be avoided by this algorithm. This algorithm may be easily programmed.

Regarding the function F we make the following assumptions:

a) system (1) has a solutionx^∗ ∈D;

b) F is of classC¹ onD;

c) there exists F⁰(x^∗)⁻¹.

Lemma 1. If F verifies assumptions a)−c) and there exists r > 0 such that:

i. S={x∈Rⁿ:kx−x^∗k ≤r} ⊆D

ii. mcr=q <1,where m= sup_x∈DkF⁰⁰(x)k andc=F⁰(x^∗)⁻¹, then for any x∈S there exists F⁰(x)⁻¹ and

(3) F⁰(x)⁻¹≤ _1−q^c . Proof. Letx∈D and consider the difference

(4) ∆(x) =F⁰(x^∗)−F⁰(x) =F⁰(x^∗)I−F⁰(x^∗)⁻¹F⁰(x).

It follows that

(5) I−F⁰(x^∗)⁻¹F⁰(x)=F⁰(x^∗)⁻¹∆(x).

The finite increment formula [5] leads to relation

k∆(x)k=F⁰(x^∗)−F⁰(x)≤mkx^∗−xk ≤mr, from which, by (5) we get

I −F⁰(x^∗)⁻¹F⁰(x)≤cmr=q <1.

It follows by the Banach lemma thatF⁰(x^∗)⁻¹F⁰(x) is invertible and F⁰(x^∗)⁻¹F⁰(x)⁻¹=I−F⁰(x^∗)⁻¹∆x⁻¹.

Further,

F⁰(x)⁻¹=I−F⁰(x^∗)⁻¹∆x⁻¹F⁰(x^∗)⁻¹,

whence, by taking norms we obtain (3).

Regarding the convergence of the iteration (2) we obtain the following result.

Theorem 2. If F obeys the hypothesis of Lemma 1 and the initial approx- imations x0∈D andA0∈Mn(R) are taken such that

δ0 = ^am₂ kx^∗−x0k ≤αd, (6)

ρ₀ =I−F⁰(x₀)A₀≤βd, (7)

2αd am ≤r, (8)

where a= _1−q^c , d <1 and α, β >0 obey

α+βab <1 (9)

hβ+ 2ab(βd+ 1)²αⁱ< β (10)

where b= sup_x∈DkF⁰(x)k.

Then for all k∈N, we havexk∈S and kx_k−x^∗k ≤ _ma^2αd^2k, (11)

I−F⁰(x_k)A_k≤βd^2k, k= 0,1, ....

(12)

Proof. From (8) and (6) it followskx^∗−x0k ≤rand thereforex0 ∈S.From the identity

θ=F(x^∗) =F(x^∗)−F(x₀)−F⁰(x₀)(x^∗−x₀) +F⁰(x₀)(x^∗−x₀) +F(x₀), taking into account (2) for k= 0,we get

x₁−x^∗ =−F⁰(x₀)⁻¹F(x^∗)−F(x₀)−F⁰(x₀)(x^∗−x₀) (13)

+ (I−F⁰(x0)A0)F(x0).

From the Taylor formula [5], it follows

F(x^∗)−F(x₀)−F⁰(x₀)(x^∗−x₀)≤ ^m₂ kx^∗−x₀k², and (14)

kF(x₀)k=kF(x^∗)−F(x₀)k ≤bkx^∗−x₀k. (15)

By (14), (15), (3) and (13) it results

kx₁−x^∗k ≤ ^am₂ kx^∗−x₀k²+abI−F⁰(x₀)A₀kx^∗−x₀k.

From the above relation, denoting by δ₁ = ^am₂ kx₁−x^∗k and taking into ac- count (6), (7) and (9),

δ₁≤δ²₀+abδ₀ρ₀ ≤α²d²+abαβd² ≤αd².

Hence, by (8) it results thatx₁∈S and, moreover, (11) holds for k= 1.

The second relation in (2) fork= 0 implies that (16) I −F⁰(x1)A1

≤I−F⁰(x1)A0

2.

The finite increment formula and the first relation in (2) imply

F⁰(x₁)−F⁰(x₀)≤mkx₁−x₀k ≤mkA₀k kF(x₀)k. If we take into account (15) and the above relation, denoting

ρ₁ =I−F⁰(x₁)A₁ we are lead to

(17) ρ₁ ≤ρ₀+mbkA₀k²kx^∗−x₀k². Further, we have

kA₀k ≤F⁰(x0)⁻¹F⁰(x0)A0

≤a(ρ0+ 1)≤a(βd+ 1).

Using the above relation, by (17) and (10) it results ρ1≤^hρ0+ma²b(1 +βd)kx^∗−x0kⁱ²

≤[ρ0+ 2ab(1 +βd)δ0]²

≤βd², i.e., (12) for k= 1.

Assuming now that (11) and (12) are verified for k = i, i ≥ 1, then, pro- ceeding as above, one can show that these relations also hold for k=i+ 1.

From (11), taking into account that d < 1, it follows that limx_k = x^∗. Since we have admitted thatF⁰(x^∗) is continuous onD,by (12) it follows that

limA_k=F⁰(x^∗)⁻¹.

Relations (11) and (12) show us that convergence order of method (2) is at least 2, i.e., is not smaller than that of the Newton method.

REFERENCES

[1] C˘atinas¸, E. andP˘av˘aloiu, I.,On approximating the eigenvalues and eigenvectors of linear continuous operators, Rev. Anal. Num´er. Th´eor. Approx.,26, nos. 1–2, pp. 19–27, 1997.

[2] Diaconu, A., On the convergence of an iterative proceeding of Chebyshev type, Rev.

Anal. Num´er. Th´eor. Approx.,24, nos. 1–2, pp. 19–27, 1995.

[3] Diaconu, A. andP˘av˘aloiu, I.,Sur quelques m´ethodes it´eratives pour la r´esolution des equations op´erationelles, Rev. Anal. Num´er. Th´eor. Approx.,1, no. 1, pp. 45–61, 1972.

[4] Laz˘ar, I.,On a Newton type method, Rev. Anal. Num´er. Th´eor. Approx.,23, no. 2, pp.

167–174, 1994.

[5] P˘av˘aloiu, I.,Introduction in the Theory of Approximating the Solutions of Equations, Ed. Dacia, Cluj-Napoca, 1976 (in Romanian).

[6] Ulm, S., On the iterative method with simultaneous approximation of the inverse of the operator, Izv. Nauk. Estonskoi S.S.R.,16, no. 4, pp. 403–411, 1967.

[7] Zehnder, J. E.,A remark about Newton’s method, Comm. Pure Appl. Math.,37, pp.

361–366, 1974.

Received by the editors: January 21, 2004.