• Nu S-Au Găsit Rezultate

View of Generalized Newton’s method for solving nonlinear and nondifferentiable algebraic systems

N/A
N/A
Protected

Academic year: 2022

Share "View of Generalized Newton’s method for solving nonlinear and nondifferentiable algebraic systems"

Copied!
7
0
0

Text complet

(1)

J. Numer. Anal. Approx. Theory, vol. 44 (2015) no. 1, pp. 93–99 ictp.acad.ro/jnaat

GENERALIZED NEWTON’S METHOD

FOR SOLVING NONLINEAR AND NONDIFFERENTIABLE ALGEBRAIC SYSTEMS

NICOLAE POP

Dedicated to prof. I. P˘av˘aloiu on the occasion of his 75th anniversary

Abstract. In this paper a model based on non-smooth equations is proposed for solving a non-linear and non-differential equation obtained by discretization of a quasi-variational inequality that models the frictional contact problem. The main aim of this paper is to show that the Newton method based on the ple- nary hull of the Clarke generalized Jacobians (the non-smooth damped Newton method) can be implemented for solving Lipschitz non-smooth equation.

MSC 2010. 90C30, 90C56, 90C53, 49J52.

Keywords. nonlinear programming, generalized derivatives, quasi-Newton methods, nonsmoots analysis.

1. INTRODUCTION

The solving of nonlinear equations is based on the concept of approxi- mation. Perhaps the best known and used approximation method is the one of successive approximations, due to Emile Picard [14]. In the case of nonlinear equation systems, the most commonly used method is Newton- Raphson’s method. I. V. Kantorovici [7], [8], proves the convergence conditions of Newton-Raphson’s method.

First we recall two important results on the Newton-Raphson method, which consist in weakening the assumptions. Thus, on one hand Barthle’s result [5], shows that we can apply Newton-Raphson’s method, without imposing conditions on the second order derivative, and on the other hand, Altman [3], solves the problem, in certain conditions without imposing the existence of the inverse of the first order derivative in the initial point.

I. K. Argyros and S. George [4], introduce a family of iterative methods that does not use derivatives, for solving the nonlinear and nondifferentiable system F(x) = 0. Specifically, the authors use the classical Secant method

Institute of Solid Mechanics of the Romanian Academy, C-tin Mille str. Nr. 15, Bucharest and Department of Mathematics and Computer Science, Faculty of Sciences, North University Center at Baia Mare, Technical University of Cluj-Napoca, e-mail:

[email protected].

(2)

and approximates the first derivative of F from a divided difference of first order:F0(xn) w [xn−1, xn;F], where, [x, y;F] is a divided difference of firs order for F at the pointx, y. In the paper specified, the authors introduce the Chebyshev-Kurchakov-type method:

yn=xn−[2xnxn−1, xn−1;F]−1F(xn), zn=xn+a(ynxn),

xn+1=xn−[2xnxn−1, xn−1;F]−1(bF(xn) +cF(zn)), n=0,

where x−1, x0 are given and a, b, c are non-negative parameters to be chosen so that the sequence xn is convergent.

I. Pavaloiu [11]–[12], introduces and studies the convergence of Aitken- Steffensen-type methods for nonsmooth and nonlinear equations.

In recent years, Newton-Raphson method has been generalized to solve problems in mathematical programming. A treatment of such wide general- izations was made by S. M. Robinson in [18] and [19].

The nonlinear systems from the discretization of contact problems are in- cluded in the category of problems with nondifferentiable terms. In this class lies the work of Pang [10], who refers to Newton’s method for B-differential equations. The notion of B-differentiability (B from Buligand) is similar to the one of directional differentiability and it was introduced by Robinson [20].

In general, a B-differentiable function is not F-differentiable, but can be approximated by a simplified function in the same way as a F-differentiable function by its F-derivative.

Pang showed that, for this type of equations, Newton’s method is quadratic convergent, if the pointwise solution is pointwise differentiable. Using a search technique through linear steps, one can prove also the global convergence.

A convergence theorem under the condition of semismoothness, was been given by L. Qi in [17], for solving the nonlinear systems with Newton’s method.

As in [15] we will emphasize the equivalence between the proof of the gen- eralized Newton method, for nonlinear and nondifferentiable equations, using theB-differentiability notion with the proof which involves the notion of gen- eralized Jacobian.

2. PROPERTIES OF THE B-DIFFERENTIABLE FUNCTIONS AND THE GENERALIZED NEWTON METHOD

Definition 2.1. A functionF :Rn→Rn, is called B-differentiable at z∈ Rn if there exists a function BF(z) : Rn → Rn, called the B-derivative of F atz, which is positive homogenous of first degree, i.e. BF(z)(λv) =λBF(z)v, for all v∈Rn andλ >0, such that

v→0lim

F(z+v)−F(z)−BF(z)v

kvk = 0.

If F isB-differentiable at each point of a certain setS ⊂Rn, then we say that F isB-differentiable onS.

(3)

In the original definition of theB-differentiability, Robinson [20], expressed the positive homogeneity of the B-derivative of the function F in terms of the cone of the graph of functionF.A fundamental distinction between a B- differentiable function and a F-differentiable one is that the B-derivative is nonlinear.

The main properties of a B-differentiable function are summarized in the following proposition.

Proposition 2.2. Let the function F :Rn→Rn be locally Lipschitz at z.

(i) If F is F-differentiable at the point z, then it is also B-differentiable and the expression of BF(z) is given by BF(z) = ∇F(z). Conversely, if F is B-differentiable at the point z and its B-derivative, BF(z)v is linear in v, thenF is F-differentiable at z;

(ii) If F is B-differentiable at z, then its B-derivative is unique. Further- more, BF(z) is Lipschitz and has the same modulus as F;

(iii) If F is B-differentiable at the pointz, thenF is directionally differen- tiable at z with respect to each direction dand Fd0(z) =BF(z)d.

In the paper [21], Shapiro showed that if F is locally Lipschitz at z, the converse of the third statement(iii), also holds. Namely, if F is directionally differentiable at the pointz, then F isB-differentiable.

LetF :Rn→Rnbe aB-differentiable function. Further on, our purpose is to solve the following nonlinear system

(2.1) F(z) = 0.

Extending Newton’s classical method for solving theF-differentiable systems, we will define an iterative method.

Let zk, be a given iteration, we intend to solve the following system with respect todk

(2.2) F(zk) +BF(zk)dk= 0

wherezk+1=zk+dk. The algorithm continues until the stopping conditions are satisfied. In general, (2.2) is a nonlinear equation system (because BF is nonlinear) and we call it generalized Newton system.

Definition 2.3. We say that F has a strong F-derivative, and we denote it by ∇F(z), if

lim

(x,y)→(z,z)

F(x)−F(y)−∇F(z)(x−y) kx−yk = 0.

It is natural to wonder wether (2.2) has a solution or not? Furthermore if this solution exists, is it unique or not? Is the sequence {zk} convergent to the solution of F?

In general, under the hypothesis that the starting point z0 is arbitrary chosen, it is difficult to suppose that the sequence {zk}is convergent. Hence, the global convergence is unlikely to happen. This dead end can be overcome

(4)

by introducing a norm function (called pseudo-potential), which provides the search direction of the solution, as shown in

Lemma 2.4. Let the function F : Rn → Rn be B-differentiable and let G:Rn→R be a function defined as

G(z) = (1/2)F(z)TF(z), then,G is also B-differentiable with

BG(z)d=F(z)TBF(z).

Furthermore, if (2.2)holds, then

(2.3) G0dk(zk) =−F(zk)TF(zk).

Proof. The proof results easily from G0d(z) = BG(z)d, because the relation (2.3) holds from the expression of theG0s B-derivative and from the relation (2.2).

An important consequence of the relation (2.3) is that if the iteration zk of F is not a solution of F, i.e. F(zk) 6= 0, then each solution zk, of the generalized Newton equation (2.2) provides a descent search direction (for the norm functionG). Thus, we can establish a linear search algorithm in order to find the next iteration (see ([10]), where we use (2.3)). The main convergence result is

Theorem 2.5. [10] Let F :Rn → Rn be a B-differentiable function at an arbitrary point z0 and G(z) = (1/2)F(z)TF(z).

We assume that the following statements hold:

a)The level set {z∈Rn|kF(z)k ≤ kF(z0)k} is bounded;

b) Each generalized Newton equation has a solution. Let {zk} be a general- ized sequence, using Newton’s method (following the pattern of the algorithm presented in [10]), and let also F(zk) 6= 0, then the below conclusions are fulfilled

(i) kF(zk+1)k<kF(zk)k;

(ii) The sequence {zk} is bounded;

(iii) If z is an accumulation point of the sequence {zk} such that, if the F-derivative ∇G(z) is strong and if there exists a neighborhood, V of z and a positive scalar c > 0, such that for each xV and for each v ∈ Rn the inequality kBF(x)vk ≥ckvk, is satisfied, then F(z) = 0;

(iv)If lim

k→∞infαk >0, then each accumulation point of{zk}is a zero ofF, where αk is given by zk+1 =zk+αkdk.

The proof can be found in [10].

Remarks 2.6. 1. The hypothesis a) is equivalent with the property that F is coercive, i.e. lim

kzk→∞kF(z)k=∞.

2. The third statement, iii) requires a strong F-propriety at the accumu- lation point on the norm function G but not on F. In general, if F has an

(5)

F-derivative atz, then so doesG. The converse result is not true, F(z) =|z|

is a contraexample.

3. From the above theorem we can not conclude that the generalized Newton equation (2.2) has a unique solution (in [10] it is shown that the local solution is unique becauseBF is injective).

3. THE GENERALIZED JACOBIAN FOR SOLVING THE NONLINEAR AND NONDIFFERENTIABLE SYSTEMS

In the idea of weakening the notion of differentiability, Clarke [6], defines the generalized Jacobian following the subdifferentiability model.

Definition 3.1. Let F :Rn→Rn be a continuous, Lipschitz application.

Then the generalized Jacobian atx, denoted by∂F(x), is defined as the convex coverage of all matrices obtained as a limit of the sequencesJ F(xi), forxix and xi 6∈ΩF, whereF is the set of points where F is nondifferentiable, and J F(xi) is the Jacobian matrix ofF,i.e.

∂F(x) =co{limJ F(xi);xix, xi 6∈ΩF}.

Remark 3.2. The condition that F is Lipschitz is important, because it ensures that measure of ΩF is not void and therefore the limit has sense.

The following result [1] leads us to a sufficient condition for the existence of solutions of a nonlinear and nondifferentiable algebraic system, solutions obtained with the generalized Newton method (using the notion of generalized gradient). This result is easily applicable for the contact problems.

Theorem 3.3. If the application F : Rn → Rn is continuous, Lipschitz, and affine on a finite number of open cones, pointed at x0 and if detM 6= 0, for all M∂F(x0), then F is a global homeomorphism from Rn into Rn.

Proof. The proof can be found in [1]. Due to this theorem one can easily verify the lack of injectivity of the application F.

Further on we shall apply Newton’s method in terms of the generalized Jacobian for the following nonlinear and non differential algebraic system

(3.1) Ku+F(u) =Q,

where u is the vector unknowns, K is the matrix coefficients (differentiable components),Qis the free term, and finallyF(u) is the undifferentiable com- ponents of the system.

Thus the generalized Newton algorithm is given by

Mk∆uk=QK(uk)−F(uk), MkK+∂F(uk), k= 0,1, . . . (3.2)

uk−1=ukM−1G(uk), M ∈∂G(uk), k= 0,1, . . .

Next, we will verify the conditions of Theorem 3.3 for the equation (3.1).

So, we denote byH(u)Ku+F(u)−Q. Because ofF(u),H does not follows

(6)

from a potential. This is the reason why, it is necessary for us to introduce a

“pseudo-potential” (norm function) G(u) = (1/2)H(u)TH(u).

Using the above notations, Newton’s method is similarly to Gauss-Newton’s method and the equationH(u) = 0 is equivalent with (2.1).

Proposition3.4. IfH :Rn→Rn isB-differentiable at an arbitrary point, z0, andG(u) = (1/2)H(u)TH(u) and the above hypotheses hold then Theorem 2.5 is equivalent with Theorem 3.3.

The generalized Newton method for solving nonlinear and nondifferentiable systems which uses the notion of B-differentiability is equivalent with the generalized Newton method which uses the notion of generalized gradient.

Now, let us see under what conditions a discrete concrete problem of elastic contact in two dimensions, is included in the assumptions of Theorem 3.3, which ensures the uniqueness of solution with Newton-Raphson’s method (see [16]).

Remarks 3.5. 1. Theorem 3.3 can be easily applied in practice and is equivalent with Theorem 2.5.

2. The pseudopotential, G(u) = 12(Ku+F(u)−Q)T(Ku+F(u)−Q), which appears in the algorithm (3.2), corresponds to the norm function

G(z) = 12F(z)T ·F(z), from Theorem 3.3.

3. The condition detM 6= 0, with M∂F(x0), from Theorem 3.3 is equivalent with the fact that the level set {z ∈ Rn|kF(z)k ≤ kF(z0)k} is bounded.

REFERENCES

[1] Alar, P. and Curnier, A.,A generalized Newton method for contact problems with friction, J. Theor. Appl. Mech.,7(1) (1988), pp. 67–82.

[2] Alar, P.andCurnier, A.,A mixed formulation for frictional contact problems prone to Newton like solution methods, Comput. Meth. Appl. Mech. Engrg.,92(93) (1991), pp. 353–375.

[3] Altman, M.,Concerning approximate solutions of nonlinear functional equations, Bull.

Acad. Polon, Sci. Ser. Math., Astronom. Phys.,5, 1957.

[4] Argyros, I.K. andGeorge, S.,Chebyshev-Kurchatov-type methods for solving equa- tions with non-differentiable operators, Nonlinear Functional Analysis and Applications, 18, No. 3, (2013), pp. 421–432.

[5] Barthle, R. G.,Newton’s method inB-space, Proc. AMS.6(1955), pp. 27–31.

[6] Clarke, F. H.,Optimization and nonsmooth analysis, Wiley and Sons, 1983.

[7] Kantorovici, L. V.and Akilov, G. P.,Analiz˘a funct¸ional˘a, Ed. S¸tiint¸ific˘a ¸si Enci- clopedic˘a, 1986.

[8] Kantorovich, L. V.,Metoda Newton dlea functionalnˆıh uravnenii, D. A. N., C.C.C.R., 1948.

[9] Klarbring, A.,Contact problems in linear elasticity, Link¨oping Studies in Science and Technology, Disertation No. 133, Link¨oping University, 1985.

(7)

[10] Pang, J. S.,Newton’s method for B-diferentiable equations, Mathematics of Operations Research,15(2) (1980).

[11] av˘aloiu, I.,Aitken-Steffensen-type methods for nonsmooth functions (I), Rev. Anal.

Num´er. Th´eor. Approx.,31(2002), no. 1, pp. 111–116.

[12] av˘aloiu, I.,Aitken-Steffensen-type methods for nonsmooth functions (II), Rev. Anal.

Num´er. Th´eor. Approx.,31(2002), no. 2, pp. 191–196.

[13] Petrila, T. and Gheorghiu, C. I., Metode element finit ¸si aplicat¸ii, Editura Academiei, 1987.

[14] Picard, E.,Trait´e d’analyse, tom2, 1883.

[15] Pop, N., A generalized concept of a differentiability in Newton’s method for contact problems, Bul. St. Univ. Baia Mare, ser. B, Mat.-Inf.,16(2000), pp. 307–314.

[16] Pop, N., An algorithm for solving nonsmooth variational inequalities arising in fric- tional quasistatic contact problems, Carpathian J. Math.,24(2008) no. 2, 110–119.

[17] Qi, L. and SunJ.,A nonsmooth version of NewtonâĂŹs method, Mathematical Pro- gramming, 58 (1993), 353–367.

[18] Robinson, S. M., Generalized equations and their solutions, Part.1, Basic Theory, Math. Programming Study,10, 1979.

[19] Robinson, S. M.,Strongly regular generalized equations, Math. Oper. Res.,5, 1980.

[20] Robinson, S. M., Local structure of fiable sets in nonlinear programming, Part.3, Sta- bility and Sensitivity, Math. Programming Study, 1987.

[21] Shapiro, A.,On conceps of directional differentiability, Applied Mathematics and As- tronomy, 1988.

Received by the editors: March 23, 2015.

Referințe

DOCUMENTE SIMILARE

We extend the applicability of the Kantorovich theorem (KT) for solving nonlinear equations using Newton-Kantorovich method in a Banach space setting.. Under the same information

Later George and Nair [20] considered the adaptive selection of the parameter for choosing the regularization parame- ter in Newton-Lavrentiev regularization method for

Argyros, A unifying local–semilocal convergence analysis and applications for two-point Newton-like methods in Banach space, J.. Hilout , Numerical Methods for Equations and

From (20) we see that the inex- act Newton method with forcing term given by (20) is locally Q-superlinearly convergent, while IN with forcing term given by (23) converges

) instead of condition (3), leads to more precise majorizing sequences, which in turn are used to provide under the same hypotheses a finer semilocal convergence analysis with

Kantorovich theorem we show that the procedure suggested by Kung [6] is im- proved in the sense that the number of Newton-steps required to compute a good starting point can

In this paper we write the coupled problem as a root-finding problem which we solve with Broyden’s quasi-Newton method and an extension of this method in which two approximate

Using more precise majorizing sequences than before we show that under weaker conditions than before [1]–[3], [5], [6] we can obtain using Newton’s method (see (10)), finer error