Directional Secant-Type Methods for Solving Equations

A semilocal convergence analysis for directional Secant-type methods in multidimensional space is provided. Using weaker hypotheses than the ones exploited by An and Bai, we provide a semilocal convergence analysis with the following advantages: weaker convergence conditions, larger convergence domain, finer error estimates on the distances involved, and more precise information on the location of the solution. A numerical example, where our results apply to solve an equation but not the ones of An and Bai, is also provided. In a second example, we show how to implement the method.     

Convergence conditions for secant-type methods

We provide new sufficient convergence conditions for the convergence of the secant-type methods to a locally unique solution of a nonlinear equation in a Banach space. Our new idea uses recurrent functions, and Lipschitz-type and center-Lipschitz-type instead of just Lipschitz-type conditions on the divided difference of the operator involved. It turns out that this way our error bounds are more precise than earlier ones and under our convergence hypotheses we can cover cases where earlier conditions are violated. Numerical examples are also provided.     

On the local convergence of inexact Newton-type methods under residual control-type conditions

A local convergence analysis of inexact Newton-type methods using a new type of residual control was recently presented by C. Li and W. Shen. Here, we introduce the center-Hölder condition on the operator involved, and use it in combination with the Hölder condition to provide a new local convergence analysis with the following advantages: larger radius of convergence, and tighter error bounds on the distances involved. These results are obtained under the same hypotheses and computational cost. Numerical examples further validating the theoretical results are also provided in this study.     

Spectral analysis of parallel incomplete factorizations with implicit pseudo‐overlap

Two general parallel incomplete factorization strategies are investigated. The techniques may be interpreted as generalized domain decomposition methods. In contrast to classical domain decomposition methods, adjacent subdomains exchange data during the construction of the incomplete factorization matrix, as well as during each local forward elimination and each local backward elimination involved in the application of the preconditioner. Local renumberings of nodes are combined with suitable global fill‐in strategy in an (successful) attempt to overcome the well‐known trade‐off between high parallelism (locality) and fast convergence (globality). From an algebraic viewpoint, our techniques may be implemented as global renumbering strategies. Theoretical spectral analysis is provided, which displays that the convergence rate weakly depends on the number of subdomains. Numerical results obtained on a 16‐processor SGI Origin 2000 are reported, showing the efficiency of our parallel preconditionings. Copyright © 2001 John Wiley & Sons, Ltd.     

A unifying local-semilocal convergence analysis and applications for two-point Newton-like methods in Banach space

We provide a local as well as a semilocal convergence analysis for two-point Newton-like methods in a Banach space setting under very general Lipschitz type conditions. Our equation contains a Fréchet differentiable operator F and another operator G whose differentiability is not assumed. Using more precise majorizing sequences than before we provide sufficient convergence conditions for Newton-like methods to a locally unique solution of equation F(x)+G(x)=0. In the semilocal case we show under weaker conditions that our error estimates on the distances involved are finer and the information on the location of the solution at least as precise as in earlier results. In the local case a larger radius of convergence is obtained. Several numerical examples are provided to show that our results compare favorably with earlier ones. As a special case we show that the famous Newton-Kantorovich hypothesis is weakened under the same hypotheses as the ones contained in the Newton-Kantorovich theorem.     

P_0函数非线性互补问题的一步非内点连续方法的收敛性

本文对于Ｐ０函数非线性互补问题提出了一个基于Ｋａｎｚｏｗ光滑函数的一步非内点连续方法,在适当的假设条件下,证明了方法的全局线性及局部二次收敛性．特别,在方法的全局线性收敛性的分析中,不需要假定非线性互补问题的函数的Ｊａｃｏｂｉ阵是Ｌｉｐｓｃｈｉｔｚ连续的．文献中为了得到非内点连续方法的全局线性收敛性,这一假定是被广泛使用的．本文提出的方法在每一次迭代只须解一个线性方程式组．     

Optimal Rates of Linear Convergence of Relaxed Alternating Projections and Generalized Douglas-Rachford Methods for Two Subspaces

We systematically study the optimal linear convergence rates for several relaxed alternating projection methods and the generalized Douglas-Rachford splitting methods for finding the projection on the intersection of two subspaces. Our analysis is based on a study on the linear convergence rates of the powers of matrices. We show that the optimal linear convergence rate of powers of matrices is attained if and only if all subdominant eigenvalues of the matrix are semisimple. For the convenience of computation, a nonlinear approach to the partially relaxed alternating projection method with at least the same optimal convergence rate is also provided. Numerical experiments validate our convergence analysis     

Modified modulus‐based matrix splitting iteration methods for linear complementarity problems

For solving the large sparse linear complementarity problems, we establish modified modulus‐based matrix splitting iteration methods and present the convergence analysis when the system matrices are H₊‐matrices. The optima of parameters involved under some scopes are also analyzed. Numerical results show that in computing efficiency, our new methods are superior to classical modulus‐based matrix splitting iteration methods under suitable conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

Convergence rate analysis of iteractive algorithms for solving variational inequality problems

 We present a unified convergence rate analysis of iterative methods for solving the variational inequality problem. Our results are based on certain error bounds; they subsume and extend the linear and sublinear rates of convergence established in several previous studies. We also derive a new error bound for $\gamma$-strictly monotone variational inequalities. The class of algorithms covered by our analysis in fairly broad. It includes some classical methods for variational inequalities, e.g., the extragradient, matrix splitting, and proximal point methods. For these methods, our analysis gives estimates not only for linear convergence (which had been studied extensively), but also sublinear, depending on the properties of the solution. In addition, our framework includes a number of algorithms to which previous studies are not applicable, such as the infeasible projection methods, a separation-projection method, (inexact) hybrid proximal point methods, and some splitting techniques. Finally, our analysis covers certain feasible descent methods of optimization, for which similar convergence rate estimates have been recently obtained by Luo [14]. Received: April 17, 2001 / Accepted: December 10, 2002 Published online: April 10, 2003 RID="⋆" ID="⋆" Research of the author is partially supported by CNPq Grant 200734/95–6, by PRONEX-Optimization, and by FAPERJ. Key Words. Variational inequality – error bound – rate of convergence Mathematics Subject Classification (2000): 90C30, 90C33, 65K05     

Local linear convergence analysis of Primal–Dual splitting methods

In this paper, we study the local linear convergence properties of a versatile class of Primal–Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework, we first show that (i) the sequences generated by Primal–Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal–Dual splitting can be specialized to cover existing ones on Forward–Backward splitting and Douglas–Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning. The demonstration not only verifies the local linear convergence behaviour of Primal–Dual splitting methods, but also the insights on how to accelerate them in practice.     

Asynchronous multisplitting two-stage iterations for systems of weakly nonlinear equations

For the large sparse systems of weakly nonlinear equations arising in the discretizations of many classical differential and integral equations, this paper presents a class of asynchronous parallel multisplitting two-stage iteration methods for getting their solutions by the high-speed multiprocessor systems. Under suitable assumptions, we study the global convergence properties of these asynchronous multisplitting two-stage iteration methods. Moreover, for this class of new methods, we establish their local convergence theories, and precisely estimate their asymptotic convergence factors under some reasonable assumptions when the involved nonlinear mapping is only assumed to be directionally differentiable. Numerical computations show that our new methods are feasible and efficient for parallely solving the system of weakly nonlinear equations.     

On a family of high-order iterative methods under gamma conditions with applications in denoising

We study a class of at least third order iterative methods for nonlinear equations on Banach spaces. A characterization of the convergence under Gamma-type conditions is presented. Though, in general, these methods are not very extended due to their computational costs, we can find examples in which they are competitive and even cheaper than other simpler methods. Indeed, we propose a new nonlinear mathematical model for the denoising of digital images, where the best method in the family has fourth order of convergence. Moreover, our family includes two-step Newton type methods with good numerical behavior in general. We center our analysis in both, analytic and computational, aspects.     

Regularized Nonconvex Mixed Variational Inequalities: Auxiliary Principle Technique and Iterative Methods

In this paper, we turn our attention to formulating and studying a new class of variational inequalities in a nonconvex setting, called regularized nonconvex mixed variational inequalities. By using the auxiliary principle technique, some new predictor corrector methods for solving such class of regularized nonconvex mixed variational inequalities are suggested and analyzed. The study of convergence analysis of the proposed iterative algorithms requires either pseudomonotonicity or partially mixed relaxed and strong monotonicity of the operator involved in regularized nonconvex mixed variational inequalities. As a consequence of our main results, we provide the correct versions of the algorithms and results presented in the literature.     

Staggered discontinuous Galerkin methods for the incompressible Navier–Stokes equations: Spectral analysis and computational results

The goal of this paper is to create a fruitful bridge between the numerical methods for approximating PDEs in fluid dynamics and the (iterative) numerical methods for dealing with the resulting large linear systems. Among the main objectives are the design of new, efficient iterative solvers and a rigorous analysis of their convergence speed. The link we have in mind is either the structure or the hidden structure that the involved coefficient matrices inherit, both from the continuous PDE and from the approximation scheme; in turn, the resulting structure is used for deducing spectral information, crucial for the conditioning and convergence analysis and for the design of more efficient solvers. As a specific problem, we consider the incompressible Navier–Stokes equations; as a numerical technique, we consider a novel family of high‐order, accurate discontinuous Galerkin methods on staggered meshes, and as tools, we use the theory of Toeplitz matrices generated by a function (in the most general block, the multilevel form) and the more recent theory of generalized locally Toeplitz matrix sequences. We arrive at a somehow complete picture of the spectral features of the underlying matrices, and this information is employed for giving a forecast of the convergence history of the conjugate gradient method, together with a discussion on new and more advanced techniques (involving preconditioning, multigrid, multi‐iterative solvers). Several numerical tests are provided and critically illustrated in order to show the validity and the potential of our analysis.     

A Stirling-like method with Hölder continuous first derivative in Banach spaces

In this paper, the convergence of a Stirling-like method used for finding a solution for a nonlinear operator in a Banach space is examined under the relaxed assumption that the first Fréchet derivative of the involved operator satisfies the Hölder continuity condition. Many results exist already in the literature to cover the stronger case when the second Fréchet derivative of the involved operator satisfies the Lipschitz/Hölder continuity condition. Our convergence analysis is done by using recurrence relations. The error bounds and the existence and uniqueness regions for the solution are obtained. Finally, two numerical examples are worked out to show that our convergence analysis leads to better error bounds and existence and uniqueness regions for the fixed points.     

High order splitting methods for analytic semigroups exist

In this paper, we are concerned with the construction and analysis of high order exponential splitting methods for the time integration of abstract evolution equations which are evolved by analytic semigroups. We derive a new class of splitting methods of orders three to fourteen based on complex coefficients. An optimal convergence analysis is presented for the methods when applied to equations on Banach spaces with unbounded vector fields. These results resolve the open question whether there exist splitting schemes with convergence rates greater then two in the context of semigroups. As a concrete application we consider parabolic equations and their dimension splittings. The sharpness of our theoretical error bounds is further illustrated by numerical experiments.     

Extension of the Hybrid Steepest Descent Method to a Class of Variational Inequalities and Fixed Point Problems with Nonself-Mappings

In this paper, we discuss the strong convergence of the hybrid steepest descent method relative to the case when the involved operators belong to a wide class of possibly nonself-mappings. Our convergence results cover previous ones, and the techniques of analysis used are simple and can be adapted to many other fixed point methods.     

On the convergence and application of Newton-like methods for analytic operators

We provide local and semilocal theorems for the convergence of Newton-like methods to a locally unique solution of an equation in a Banach space. The analytic property of the operator involved replaces the usual domain condition for Newton-like methods. In the case of the local results we show that the radius of convergence can be enlarged. A numerical example is given to justify our claim. This observation is important and finds applications in steplength selection in predictor-corrector continuation procedures.     

Affine invariant local convergence theorems for inexact Newton-like methods

Affine invariant sufficient conditions are given for two local convergence theorems involving inexact Newton-like methods. The first uses conditions on the first Fréchet-derivative whereas the second theorem employs hypotheses on the second. Radius of convergence as well as rate of convergence results are derived. Results involving superlinear convergence and known to be true for inexact Newton methods are extended here. Moreover, we show that under hypotheses on the second Fréchet-derivative our radius of convergence is larger than the corresponding one in [10]. This allows a wider choice for the initial guess. A numerical example is also provided to show that our radius of convergence is larger than the one in [10].     

On the semilocal convergence of the Halley method using recurrent functions

We provide new semilocal convergence results for the Halley method in order to approximate a locally unique solution of a nonlinear equation in a Banach space setting. Our sufficient convergence conditions can be weaker than before, where as the error bounds on the distances involved are finer. Our first approach uses a Kantorovich-type analysis. The second approach uses our new idea of recurrent functions. A comparison between the two approaches is also given. A numerical example further validating the theoretical results is also provided in this study.