On a two-step iterative process under generalized Lipschitz conditions for first-order divided differences

We study the convergence of the inexact chord method and Steffensen method for the solution of systems of nonlinear equations under the generalized Lipschitz conditions for first-order divided differences. We consider methods with a check of the relative discrepancy. The results obtained easily provide an estimate of the convergence sphere for inexact methods. For special cases, these results coincide with the known ones.     

Analysis of the cell boundary element methods for convection dominated convection-diffusion equations

We introduce two kinds of the cell boundary element (CBE) methods for convection dominated convection-diffusion equations: one is the CBE method with the exact bubble function and the other with inexact bubble functions. The main focus of this paper is on inexact bubble CBE methods. For inexact bubble CBE methods we introduce a family of numerical methods depending on two parameters, one for control of interior layers and the other for outflow boundary layers. Stability and convergence analysis are provided and numerical tests for inexact bubble CBEs with various choices of parameters are presented.     

A generalization of parameterized inexact Uzawa method for generalized saddle point problems

Recently, a class of parameterized inexact Uzawa methods has been proposed for generalized saddle point problems by Bai and Wang [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900–2932], and a generalization of the inexact parameterized Uzawa method has been studied for augmented linear systems by Chen and Jiang [F. Chen, Y.-L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput. (2008)]. This paper is concerned about a generalization of the parameterized inexact Uzawa method for solving the generalized saddle point problems with nonzero (2, 2) blocks. Some new iterative methods are presented and their convergence are studied in depth. By choosing different parameter matrices, we derive a series of existing and new iterative methods, including the preconditioned Uzawa method, the inexact Uzawa method, the SOR-like method, the GSOR method, the GIAOR method, the PIU method, the APIU method and so on. Numerical experiments are used to demonstrate the feasibility and effectiveness of the generalized parameterized inexact Uzawa methods.     

Smale's α-theory for inexact Newton methods under the γ-condition

The present paper is concerned with the convergence problem of inexact Newton methods. Assuming that the nonlinear operator satisfies the γ-condition, a convergence criterion for inexact Newton methods is established which includes Smale's type convergence criterion. The concept of an approximate zero for inexact Newton methods is proposed in this paper and the criterion for judging an initial point being an approximate zero is established. Consequently, Smale's α-theory is generalized to inexact Newton methods. Furthermore, a numerical example is presented to illustrate the applicability of our main results.     

The convergence analysis of inexact Gauss–Newton methods for nonlinear problems

In this paper, inexact Gauss–Newton methods for nonlinear least squares problems are studied. Under the hypothesis that derivative satisfies some kinds of weak Lipschitz conditions, the local convergence properties of inexact Gauss–Newton and inexact Gauss–Newton like methods for nonlinear problems are established with the modified relative residual control. The obtained results can provide an estimate of convergence ball for inexact Gauss–Newton methods.     

On the order optimality of the regularization via inexact Newton iterations

Inexact Newton regularization methods have been proposed by Hanke and Rieder for solving nonlinear ill-posed inverse problems. Every such a method consists of two components: an outer Newton iteration and an inner scheme providing increments by regularizing local linearized equations. The method is terminated by a discrepancy principle. In this paper we consider the inexact Newton regularization methods with the inner scheme defined by Landweber iteration, the implicit iteration, the asymptotic regularization and Tikhonov regularization. Under certain conditions we obtain the order optimal convergence rate result which improves the suboptimal one of Rieder. We in fact obtain a more general order optimality result by considering these inexact Newton methods in Hilbert scales.     

Certain methods for linear problems with inexact initial data

Linear problems with inexact initial data are examined. The stopping rules for certain iterative methods designed for solving linear equations and a linear elimination problem are proposed and analysed. In particular, these methods are applicable to ill-conditioned and ill-posed problems. Numerical results are presented that demonstrate the efficiency of these methods.     

Globally and superlinearly convergent inexact Newton–Krylov algorithms for solving nonsmooth equations

This paper presents some variants of the inexact Newton method for solving systems of nonlinear equations defined by locally Lipschitzian functions. These methods use variants of Newton's iteration in association with Krylov subspace methods for solving the Jacobian linear systems. Global convergence of the proposed algorithms is established under a nonmonotonic backtracking strategy. The local convergence based on the assumptions of semismoothness and BD‐regularity at the solution is characterized, and the way to choose an inexact forcing sequence that preserves the rapid convergence of the proposed methods is also indicated. Numerical examples are given to show the practical viability of these approaches. Copyright © 2009 John Wiley & Sons, Ltd.     

A new criterion for the inexact logarithmic-quadratic proximal method and its derived hybrid methods

To solve nonlinear complementarity problems, the inexact logarithmic-quadratic proximal (LQP) method solves a system of nonlinear equations (LQP system) approximately at each iteration. Therefore, the efficiencies of inexact-type LQP methods depend greatly on the involved inexact criteria used to solve the LQP systems. This paper relaxes inexact criteria of existing inexact-type LQP methods and thus makes it easier to solve the LQP system approximately. Based on the approximate solutions of the LQP systems, a descent method, and a prediction–correction method are presented. Convergence of the new methods are proved under mild assumptions. Numerical experiments for solving traffic equilibrium problems demonstrate that the new methods are more efficient than some existing methods and thus verify that the new inexact criterion is attractive in practice.     

一类非线性方程组的Newton-PSS迭代法

正定反Hermite分裂(PSS)方法是求解大型稀疏非Hermite正定线性代数方程组的一类无条件收敛的迭代算法.将其作为不精确Newton方法的内迭代求解器,我们构造了一类用于求解大型稀疏且具有非Hermite正定Jacobi矩阵的非线性方程组的不精确Newton-PSS方法,并对方法的局部收敛性和半局部收敛性进行了详细的分析.数值结果验证了该方法的可行性与有效性.     

一类Riccati方程组对称自反解的两种迭代算法

针对源于Markov跳变线性二次控制问题中的一类对偶代数Riccati方程组,分别采用修正共轭梯度算法和正交投影算法作为非精确Newton算法的内迭代方法,建立求其对称自反解的非精确Newton-MCG算法和非精确Newton-OGP算法.两种迭代算法仅要求Riccati方程组存在对称自反解,对系数矩阵等没有附加限定.数值算例表明,两种迭代算法是有效的.     

Uzawa methods for a class of block three‐by‐three saddle‐point problems

In this work, we consider numerical methods for solving a class of block three‐by‐three saddle‐point problems, which arise from finite element methods for solving time‐dependent Maxwell equations and some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

First-order methods of smooth convex optimization with inexact oracle

We introduce the notion of inexact first-order oracle and analyze the behavior of several first-order methods of smooth convex optimization used with such an oracle. This notion of inexact oracle naturally appears in the context of smoothing techniques, Moreau–Yosida regularization, Augmented Lagrangians and many other situations. We derive complexity estimates for primal, dual and fast gradient methods, and study in particular their dependence on the accuracy of the oracle and the desired accuracy of the objective function. We observe that the superiority of fast gradient methods over the classical ones is no longer absolute when an inexact oracle is used. We prove that, contrary to simple gradient schemes, fast gradient methods must necessarily suffer from error accumulation. Finally, we show that the notion of inexact oracle allows the application of first-order methods of smooth convex optimization to solve non-smooth or weakly smooth convex problems.     

Inexact GMRES for singular linear systems

Inexact Krylov subspace methods have been shown to be practical alternatives for the solution of certain linear systems of equations. In this paper, the solution of singular systems with inexact matrix-vector products is explored. Criteria are developed to prescribe how inexact the matrix-vector products can be, so that the computed residual remains close to the true residual, thus making the inexact method of practical applicability. Cases are identified for which the methods work well, and this is the case in particular for systems representing certain Markov chains. Numerical experiments illustrate the effectiveness of the inexact approach. AMS subject classification (2000)  65F10     

Tuned preconditioners for inexact two‐sided inverse and Rayleigh quotient iteration

Convergence results are provided for inexact two‐sided inverse and Rayleigh quotient iteration, which extend the previously established results to the generalized non‐Hermitian eigenproblem and inexact solves with a decreasing solve tolerance. Moreover, the simultaneous solution of the forward and adjoint problem arising in two‐sided methods is considered, and the successful tuning strategy for preconditioners is extended to two‐sided methods, creating a novel way of preconditioning two‐sided algorithms. Furthermore, it is shown that inexact two‐sided Rayleigh quotient iteration and the inexact two‐sided Jacobi‐Davidson method (without subspace expansion) applied to the generalized preconditioned eigenvalue problem are equivalent when a certain number of steps of a Petrov–Galerkin–Krylov method is used and when this specific tuning strategy is applied. Copyright © 2014 John Wiley & Sons, Ltd.     

Banach空间中半光滑算子方程的不精确牛顿法(英文)

本文主要解决Banach空间中抽象的半光滑算子方程的解法.提出了两种不精确牛顿法,它们的收敛性同时得到了证明.这两种方法可以看作是有限维空间中已存在的解半光滑算子方程的方法的延伸.     

Convergence behaviour of inexact Newton methods under weak Lipschitz condition

Under weak Lipschitz condition, local convergence properties of inexact Newton methods and Newton-like methods for systems of nonlinear equations are established in an arbitrary vector norm. Processes with modified relative residual control are considered; the results easily provide an estimate of convergence ball for inexact methods. For a special case, the results are affine invariant. Some applications are given.     

Gap Functions for Equilibrium Problems

The theory of gap functions, developed in the literature for variational inequalities, is extended to a general equilibrium problem. Descent methods, with exact an inexact line-search rules, are proposed. It is shown that these methods are a generalization of the gap function algorithms for variational inequalities and optimization problems.     

空间中半光滑算子方程的不精确牛顿法}

In this paper, we propose two inexact Newton methods forlocally Lipschitzian semismooth function and prove their local convergence results under some conditions. The present inexact Newton methods could be viewed asthe extensions of previous ones with same convergent results in finite-dimensional space.     

框式线性规划非精确不可行内点算法

本文为框式线性规划给出了一个非精确不可行内点算法．该算法使用的搜索方向仅需要达到一个相对的精度，这样的搜索方向可以通过Krylov子空间迭代法，比如CG或QMR得到，本文最后证明了算法的全局收敛性。