Note on the improvement of Newton’s method for system of nonlinear equations.docx

Note on the improvement of Newtons method for system of nonlinear equationsNote on the improvement of Newtons methodfor system of nonlinear equationsXinyuan WuState Key Laboratory for Novel Software Technology at Nanjing University,Nanjing 210093,PR ChinaDepartment of Mathematics,Nanjing University,Nanjing 210093,PR ChinaAbstractIn this note,we are concerned with the further study for a signi?cant improvement on Newtons iterative method pro-posed by Wu Xinyuan Wu,A new continuation Newton-like method and its deformation,http:/www.wendangku.net/doc/75fd8cbfee06eff9aef807c6.htmlput.112(2000)7578.We present a natural extension and development of the improvement on Newtons method for system of nonlinear equation.The convergence is presented and the numerical results are given to show the e?ciency of the extended method for system of nonlinear equations.2006Elsevier Inc.All rights reserved.Keywords:System of nonlinear equations;Newton-like methods;Local convergence;Iterative method1.IntroductionMany relationships in nature are inherently nonlinear in that e?ects are not in direct proportion to their cause.Accordingly,solving nonlinear equations occurs frequently in scienti?c work.Suppose that f be a con-tinuously di?erentiable function of a single variable x .Consider the nonlinear equation:f ex T?0:e1TIt is well known that,Newtons method is one of the most powerful numerical method.However,if the deriv-ative of the function f ex Tat an iterate is singular or almost singular,namely j f 0ex k Tj %0,the iteration can be aborted due to the over?ow or lead to divergence.For dealing with the problem,Wu et al.14have inves-tigated the revisions of Newtons method and one of them is given byAlgorithm 1.Suppose that an initial point x 0is given,then the iterative sequence x k is produced by the following formulax k t1:?x k f ex k Tv k f ex k Ttf 0ex k T;k ?0;1;2;.;e2T0096-3003/$-see front matter 2006Elsevier Inc.All rights reserved.doi:10.1016/j.amc.2006.12.035E-mail address:xywuhttp:/www.wendangku.net/doc/75fd8cbfee06eff9aef807c6.htmlApplied Mathematics and Computation 189(2007)14761479http:/www.wendangku.net/doc/75fd8cbfee06eff9aef807c6.html/locate/amcX.Wu/Applied Mathematics and Computation189(2007)147614791477 where v k has the same sign as that of f0ex kTfex kTwithj v k j?vWe observe that the choice of v k 0in(2)reduces to the classical Newtons method for the nonlinear equa-tions in one variable.If v?0,then the denominator of the formula(2)will never be zero,provided the approximate x k has not been accepted,even if f0ex kT?0occurs.It turns out that the formula(2)of the algo-rithm1has two remarkable advantages over the classical Newton method.The?rst one is thatx kis well de?ned,even if f0ex kT?0happens.The second one is that the absolute value of the denominator in the for-mula(2)of the algorithm1is always greater than j f0ex kTj if x k cannot be accepted as an approximation of x*, and this means that the numerical stability of formula(2)is better than the classical Newton method. Although Kou et al.5extend the formula(2)to system of nonlinear equations FexT?0and the correspond-ing convergence is considered in5,the assumptions of convergence imposed on FexTcontains the strong con-ditions,which are,FexTis su?ciently smooth and diagev i f iexTTtDFexTis nonsingular in some neighborhood of the solution x*of FexT.In this note,we will replace the strong conditions imposed on FexTwith the mild and reasonable conditions.Numerical examples will be further considered to show the new algorithm is more e?ec-tive and practicable than the classical Newtons method.2.Extension to system of nonlinear equationsConsider system of nonlinear equationsFexT?0;e3TwhereFexT?ef1exT;f2exT;.;f mexTTT;x?ex1;x2;.;x mTT:Assume that F:D&R m!R m is Gdi?erentiable on an open neighborhood U0&D of a point x?2D for which Fex?T?0.LetGexT?ee v1x1f1exT;e v2x2f2exT;.;e v m x m f mexTTT;e4Twhere v i,i=1,2,.,m are parameters withj v i j6vand chosen such that the Jacobin matrix of GexTis nonsingular.The Jacobin matrix of GexTis given by DGexT?diagee v i x iTediagev i f iexTTtDFexTT;where,DFexTexpresses the Jacobin matrix of FexT.It is easy to see that the solution of(3)is equivalent to that of the following system GexT?0;e5Twhere GexTis de?ned by(4).Moreover,the di?erential property of F and G is in the same.Now,applying Newton method to the system of nonlinear Eq.(5)yieldsxekt1T?xekTeDGexekTTT1GexekTT?xekTediagev i f iexekTTTtDFexekTTT1FexekTT;that is,xekt1T?xekTediagev i f iexekTTTtDFexekTTT1FexekTT:e6TSince Newton iterative method converges quadratically,so does the iterative formula(6).We state the convergence theorem as follows.Theorem 2.1.Suppose that x *is a solution of (3),F :D &R m !R mis twice differentiable on an openneighborhood U 0&D of x ?2D and o 2f i ex To x j o x k6M ,i ?1;2;.;m ;j ?1;2;.;m ;k ?1;2;.;m ,for some constant M,the matrixA ex ?T?diag ev i f i ex ?TTtDF ex ?Tis nonsingular,then there exists a closed ball U ex ?T&U 0with a suf?ciently small radius,such that the formula (6)is well de?ned and converges quadratically to the solution x *,provided that x e0T2 Uex ?T:Proof.It follows immediately from applying the Newton attraction theorem 6to the function G ex Tde?nedby (4).Next,we state the NewtonKantorovich theorem for iterative formula (6).h Theorem 2.2.Suppose that G :D &D &R n !R n is Fdifferentiable on a convex set U 0&D andk DG ex TDG ey Tk 6c k x y k ;8x ;y 2U 0holds.Assume that there exists an x e0T2U 0with k DG ex e0TTk 6b and a ?bcg 61;where g P k DG ex e0TT1G ex e0TTk .Let s 1?ebc T1?1e12a T12 ;s 2?ebc T1?1te12a T12 ;and assume that the ball S ex e0T;s 1T&U 0.Then the iterative formula (6)is well de?ned,x ek T;k ?1;2;.,generated by (6),remain in S ex e0T;s 1T,and converge to a solution x *of G ex T?0,namely,F(x)=0,which is unique in S ex e0T;s 2TU 0.Moreover,the error estimate of x ?x ek Tsatis?esk x ?x ek Tk 6ebc 2k T1e2a T2k;k ?0;1;.:Proof.Applying the well-known NewtonKantorovich theorem to the function G ex Tde?ned by (4)yields the results of the theorem.h 3.Numerical examplesHere we give some numerical results for the test problems in a preassigned region D .We apply the iterativeformula (6)with the choice of j v i j ?1for convenience and v i f i ex ek TThave the signs as o f io x iex ek TTto the test prob-lems.The stopping criterion is given by k F ex ek TTk Problem 1:x 21x 2t1?0;x 1cos ep x 2T?0;(D ?fex 1;x 2Tj 1e X?2p 1:5!:The numerical results are shown in Table 1.It should be pointed out that for the problem 1,the numerical solution e12TTgiven by Newton method after 35iterative steps is not in the preassigned region D .Problem 2:3x 1tx 22?0;x 1x 2e1tx 2T?0;D ?fex 1;x 2Tj 1e X ?00:1478X.Wu /Applied Mathematics and Computation 189(2007)14761479The numerical results are listed in Table 2.4.ConclusionAs stated above,a natural extension and development of the improvement on Newtons method for system of nonlinear equation is further considered.The convergence theorems for the extended formula (6)are http:/www.wendangku.net/doc/75fd8cbfee06eff9aef807c6.htmlpared with Kous theorem 5,the strong assumptions of convergence imposed on F ex Tnamely,F ex Tis su?ciently smooth and diag ev i f i ex TTtDF ex Tis nonsingular in some neighborhood of the solution x *of F ex Tare removed.Replace the strong conditions imposed on F ex Twith the mild and reasonable conditions.And the numerical results are given to show the e?ciency of the extended method.References1Xinyuan Wu,A new continuation Newton-like method and its deformation,http:/www.wendangku.net/doc/75fd8cbfee06eff9aef807c6.htmlput.112(2000)7578.2Xinyuan Wu,Hongwei Wu,On a class of quadratic convergence iteration formulae without derivatives,http:/www.wendangku.net/doc/75fd8cbfee06eff9aef807c6.htmlput.107(2000)7780.3Xinyuan Wu,Dongsheng Fu,New high order iteration methods without employing derivatives for solving nonlinear equations,Comput.Math.Appl.41(2001)489495.4Xinyuan Wu,A signi?cant improvement on Newtons iterative method,Appl.Math.Mech.-Engl.20(8)(1999)924927.5J.Kou,Y.Li,X.Wang,E?cient continuation Newton-like method for solving system of nonlinear equations 174(2006)846853.6J.M.Ortega,W.C.Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables,Academic Press,New York and London,1970.Table 2The numerical results for problem 2X 0New formulaNewtons method e0:150:75TTN 7FailsX N e00TT Error e00TT e0:140:75TTN 7FailsX N e00TT Error e00TT e0:120:74TTN 711X N e00TT e00TT Errore00TTe00TTTable 1The numerical results for problem 1X 0New formulaNewtons method e1p1TTN 6FailsX N e0:707106781186551:5TT Error e00TTe0:3181:5TTN 6FailsX N e0:707106781186551:5TT Error e00TTe0:321TTN 635X N e0:707106781186551:5!TT e12TT Errore00TTe00TTX.Wu /Applied Mathematics and Computation 189(2007)147614791479