Analysis of the nonlinear Uzawa algorithm for symmetric saddle point problems

In this paper we discuss the convergence behaviour of the nonlinear Uzawa algorithm for solving saddle point problems presented in a recent paper of Cao [Z.H. Cao, Fast Uzawa algorithm for generalized saddle point problems, Appl. Numer. Math. 46 (2003), pp. 157–171]. For a general case, the results on the convergence of the algorithm are given.     

Optimization of a parameterized inexact Uzawa method for saddle point problems

For large sparse saddle point problems, Cao et al. studied a modified generalized parameterized inexact Uzawa (MGPIU) method (see [Y. Cao, M.Q. Jiang, L.Q. Yao, New choices of preconditioning matrices for generalized inexact parameterized iterative methods, J. Comput. Appl. Math. 235 (1) (2010) 263–269]). For iterative methods of this type, the choice of the relaxation parameter is crucial for the methods to achieve their best performance. In this paper, for an example of 2D Stokes equations, we derive the optimal relaxation parameter for the continuous version of the MGPIU method, by minimizing the corresponding convergence factor that is obtained using Fourier analysis. In addition, we find that the MGPIU method is mesh parameter independent, however, it depends asymptotically linearly on the viscosity ν, which suggests that the numerical methods for Stokes equations should be investigated with the presence of the viscosity ν, though it can be scaled out from the equations in advance. We use numerical experiments to validate our theoretical findings.     

Some new preconditioned generalized AOR methods for generalized least-squares problems

Some new preconditioned GAOR methods for solving generalized least-squares problems and their comparison results are given. Comparison results show that the convergence rates of the new preconditioned GAOR methods are better than those of the preconditioned GAOR methods presented by Shen et al. [Preconditioned iterative methods for solving weighted linear least squares problems, Appl. Math. Mech. – Engl. Ed. 33(3) (2012), pp. 375–384] whenever these methods are convergent. Lastly, numerical experiments are provided to confirm the theoretical results.     

Comparison results on the preconditioned GAOR method for generalized least squares problems

Recently, Zhou et al. [Preconditioned GAOR methods for solving weighted linear least squares problems, J. Comput. Appl. Math. 224 (2009), pp. 242–249] have proposed the preconditioned generalized accelerated over relaxation (GAOR) methods for solving generalized least squares problems and studied their convergence rates. In this paper, we propose a new type of preconditioners and study the convergence rates of the new preconditioned GAOR methods for solving generalized least squares problems. Comparison results show that the convergence rates of the new preconditioned GAOR methods are better than those of the preconditioned GAOR methods presented by Zhou et al. whenever these methods are convergent. Lastly, numerical experiments are provided in order to confirm the theoretical results studied in this paper.     

An acceleration of preconditioned generalized accelerated over relaxation methods for systems of linear equations

In this paper, a new type of preconditioners are proposed to accelerate the preconditioned generalized accelerated over relaxation methods presented by Zhou et al. [Preconditioned GAOR methods for solving weighted linear least squares problems, J. Comput. Appl. Math. 224 (2009), pp. 242–249] for the linear system of the generalized least-squares problem. The convergence and comparison results are obtained. The comparison results show that the convergence rates of the proposed methods are better than those of the original methods. Finally, numerical experiments are provided to confirm the results obtained in this paper.     

On SSOR-like preconditioner for saddle point problems with dominant skew-Hermitian part

ABSTRACT

Based on the SSOR-like iteration method proposed by Bai [Numer. Linear Algebra Appl. 23 (2016), pp. 37–60], we present an SSOR-like preconditioner for the saddle point problems whose coefficient matrix has strongly dominant skew-Hermitian part. The spectral properties, including the bounds on the eigenvalues of the preconditioned matrix, are discussed in this work. Numerical experiments are presented to illustrate the effectiveness of the new preconditioner for saddle point problems.     

An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems

This paper describes an accelerated HPE-type method based on general Bregman distances for solving convex–concave saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Math. Oper. Res. 25(2) (2000), pp. 214–230] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented in He and Monteiro [An accelerated HPE-type algorithm for a class of composite convex–concave saddle-point problems, SIAM J. Optim. 26 (2016), pp. 29–56] in two ways, namely: (a) it deals with general monotone SP problems instead of bilinear structured SPs and (b) it is based on general Bregman distances instead of the Euclidean one. Similar to the algorithm of He and Monteiro [An accelerated HPE-type algorithm for a class of composite convex–concave saddle-point problems, SIAM J. Optim. 26 (2016), pp. 29–56], it has the advantage that it works for any constant choice of proximal stepsize. Moreover, a suitable choice of the stepsize yields a method with the best known iteration-complexity for solving monotone SP problems. Computational results show that the new method is superior to Nesterov's [Smooth minimization of non-smooth functions, Math. Program. 103(1) (2005), pp. 127–152] smoothing scheme.     

A non-monotone inexact regularized smoothing Newton method for solving nonlinear complementarity problems

In the paper [S.P. Rui and C.X. Xu, A smoothing inexact Newton method for nonlinear complementarity problems, J. Comput. Appl. Math. 233 (2010), pp. 2332–2338], the authors proposed an inexact smoothing Newton method for nonlinear complementarity problems (NCP) with the assumption that F is a uniform P function. In this paper, we present a non-monotone inexact regularized smoothing Newton method for solving the NCP which is based on Fischer–Burmeister smoothing function. We show that the proposed algorithm is globally convergent and has a locally superlinear convergence rate under the weaker condition that F is a P ₀ function and the solution of NCP is non-empty and bounded. Numerical results are also reported for the test problems, which show the effectiveness of the proposed algorithm.     

A symmetric positive definite preconditioner for saddle-point problems

For the classical saddle-point problem, we present precisely two intervals containing the positive and the negative eigenvalues of the preconditioned matrix, respectively, when the inexact version of the symmetric positive definite preconditioner introduced in Section 2.1 of Gill et al. [Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl. 13 (1992), pp. 292–311] is employed. The model of Stokes problem is used to test the effectiveness of the presented bounds as well as the quality of the symmetric positive definite preconditioner.     

Spline collocation method with four parameters for solving a system of fourth-order boundary-value problems

In this paper, a spline collocation method is applied to solve a system of fourth-order boundary-value problems associated with obstacle, unilateral and contact problems. The presented method is dependent on four collocation points to be satisfied by four parameters θ _j ∈(0, 1], j=1(1) 4 in each subinterval. It turns out that the proposed method when applied to the concerned system is a fourth-order convergent method and gives numerical results which are better than those produced by other spline methods [E.A. Al-Said and M.A. Noor, Finite difference method for solving fourth-order obstacle problems, Int. J. Comput. Math. 81(6) (2004), pp. 741–748; F. Geng and Y. Lin, Numerical solution of a system of fourth order boundary value problems using variational iteration method, Appl. Math. Comput. 200 (2008), pp. 231–241; J. Rashidinia, R. Mohammadi, R. Jalilian, and M. Ghasemi, Convergence of cubic-spline approach to the solution of a system of boundary-value problems, Appl. Math. Comput. 192 (2007), pp. 319–331; S.S. Siddiqi and G. Akram, Solution of the system of fourth order boundary value problems using non polynomial spline technique, Appl. Math. Comput. 185 (2007), pp. 128–135; S.S. Siddiqi and G. Akram, Numerical solution of a system of fourth order boundary value problems using cubic non-polynomial spline method, Appl. Math. Comput. 190(1) (2007), pp. 652–661; S.S. Siddiqi and G. Akram, Solution of the system of fourth order boundary value problems using cubic spline, Appl. Math. Comput. 187(2) (2007), pp. 1219–1227; Siraj-ul-Islam, I.A. Tirmizi, F. Haq, and S.K. Taseer, Family of numerical methods based on non-polynomial splines for solution of contact problems, Commun. Nonlinear Sci. Numer. Simul. 13 (2008), pp. 1448–1460]. Moreover, the absolute stability properties appear that the method is A-stable. Two numerical examples (one for each case of boundary conditions) are given to illustrate practical usefulness of the method developed.     

Using reproducing kernel for solving a class of singular weakly nonlinear boundary value problems

Cui et al. [M. Cui and F. Geng, Solving singular two point boundary value problems in reproducing kernel space, J. Comput. Appl. Math. 205 (2007), pp. 6–15; H. Yao and M. Cui, A new algorithm for a class of singular boundary value problems, Appl. Math. Comput. 186 (2007), pp. 1183–1191] presents an algorithm to solve a class of singular linear boundary value problems in the reproducing kernel space. In this paper, we will present three new algorithms to solve a class of singular weakly nonlinear boundary value problems in reproducing kernel space. The algorithms are efficiently applied to solving some model problems. It is demonstrated by the numerical examples that those algorithms are highly accurate.     

The Bruck's ergodic iteration method for the Ky Fan inequality over the fixed point set

We introduce a new iteration algorithm for solving the Ky Fan inequality over the fixed point set of a nonexpansive mapping, where the cost bifunction is monotone without Lipschitz-type continuity. The algorithm is based on the idea of the ergodic iteration method for solving multi-valued variational inequality which is proposed by Bruck [On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space, J. Math. Anal. Appl. 61 (1977), pp. 159–164] and the auxiliary problem principle for equilibrium problems P.N. Anh, T.N. Hai, and P.M. Tuan. [On ergodic algorithms for equilibrium problems, J. Glob. Optim. 64 (2016), pp. 179–195]. By choosing suitable regularization parameters, we also present the convergence analysis in detail for the algorithm and give some illustrative examples.     

On Convergence of the Arrow–Hurwicz Method for Saddle Point Problems

Journal of Mathematical Imaging and Vision - The Arrow–Hurwicz method is an inexact version of the Uzawa method; it has been widely applied to solve various saddle point problems in different...     

Modified alternating direction-implicit iteration method for linear systems from the incompressible Navier–Stokes equations

In order to solve the large sparse systems of linear equations arising from numerical solutions of two-dimensional steady incompressible viscous flow problems in primitive variable formulation, Ran and Yuan [On modified block SSOR iteration methods for linear systems from steady incompressible viscous flow problems, Appl. Math. Comput. 217 (2010), pp. 3050–3068] presented the block symmetric successive over-relaxation (BSSOR) and the modified BSSOR iteration methods based on the special structures of the coefficient matrices. In this study, we present the modified alternating direction-implicit (MADI) iteration method for solving the linear systems. Under suitable conditions, we establish convergence theorems for the MADI iteration method. In addition, the optimal parameter involved in the MADI iteration method is estimated in detail. Numerical experiments show that the MADI iteration method is a feasible and effective iterative solver.     

A new preconditioner for generalized saddle point matrices with highly singular(1,1) blocks

In this paper, based on the preconditioners presented by Cao [A note on spectrum analysis of augmentation block preconditioned generalized saddle point matrices, Journal of Computational and Applied Mathematics 238(15) (2013), pp. 109–115], we introduce and study a new augmentation block preconditioners for generalized saddle point matrices whose coefficient matrices have singular (1,1) blocks. Moreover, theoretical analysis gives the eigenvalue distribution, forms of the eigenvectors and its minimal polynomial. Finally, numerical examples show that the eigenvalue distribution with presented preconditioner has the same spectral clustering with preconditioners in the literature when choosing the optimal parameters and the preconditioner in this paper and in the literature improve the convergence of BICGSTAB and GMRES iteration efficiently when they are applied to the preconditioned BICGSTAB and GMRES to solve the Stokes equation and two-dimensional time-harmonic Maxwell equations by choosing different parameters.     

A new superconvergent method for systems of nonlinear singular boundary value problems

A new superconvergent method based on a sextic spline is described and analysed for the solution of systems of nonlinear singular two-point boundary value problems (BVPs). It is well known that the optimal orders of convergence could not be achieved using standard formulation of a sextic spline for the solution of BVPs. Based on the method used in our earlier research papers [J. Rashidinia and M. Ghasemi, B-spline collocation for solution of two-point boundary value problems, J. Comput. Appl. Math. 235 (2011), pp. 2325–2342; J. Rashidinia, M. Ghasemi, and R. Jalilian, An o(h ⁶) numerical solution of general nonlinear fifth-order two point boundary value problems, Numer. Algorithms 55(4) (2010), pp. 403–428], we construct a new O(h ⁸) locally superconvergent method for the solution of general nonlinear two-point BVPs up to order 6. The error bounds and the convergence properties of the method have been proved theoretically. Then, the method is extended to solve the system of nonlinear two-point BVPs. Some test problems are given to demonstrate the applicability and the superconvergent properties of the proposed method numerically. It is shown that the method is very efficient and applicable for stiff BVPs too.     

Efficient solution of a class of partial integro-differential equation in reproducing kernel space

In [Y.l. Wang, T. Chaolu, Z. Chen, Using reproducing kernel for solving a class of singular weakly nonlinear boundary value problems, Int. J. Comput. Math. 87(2) (2010), pp. 367–380], we present three algorithms to solve a class of ordinary differential equations boundary value problems in reproducing kernel space. It is worth noting that our methods can get the solution of partial integro-differential equation. In this note, we use method 2 [M. Dehghan, Solution of a partial integro-differential equation arising from viscoelasticity, Int. J. Comput. Math. 83(1) (2006), pp. 123–129] to solve a class of partial integro-differential equation in reproducing kernel space. Numerical example shows our method is effective and has high accuracy.     

On the convergence of iterative methods for stabilized saddle point problems

The convergence of the inexact Uzawa method for stabilized saddle point problems was analysed in a recent paper by Cao, Evans and Qin. We show that this method converges under conditions weaker than those stated in their paper.     

On the convergence of Newton-type methods using recurrent functions

We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods. It turns out that our sufficient convergence conditions are weaker, and the error bounds are tighter than in earlier studies in many interesting cases [X. Chen, On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms, Ann. Inst. Statist. Math. 42 (1990), pp. 387–401; X. Chen and T. Yamamoto, Convergence domains of certain iterative methods for solving nonlinear equations, Numer. Funct. Anal. Optim. 10 (1989), pp. 37–48; Y. Chen and D. Cai, Inexact overlapped block Broyden methods for solving nonlinear equations, Appl. Math. Comput. 136 (2003), pp. 215–228; J.E. Dennis, Toward a unified convergence theory for Newton-like methods, in Nonlinear Functional Analysis and Applications, L.B. Rall, ed., Academic Press, New York, 1971, pp. 425–472; P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms, Springer Series in Computational Mathematics, Vol. 35, Springer-Verlag, Berlin, 2004; P. Deuflhard and G. Heindl, Affine invariant convergence theorems for Newton's method and extensions to related methods, SIAM J. Numer. Anal. 16 (1979), pp. 1–10; Z. Huang, A note of Kantorovich theorem for Newton iteration, J. Comput. Appl. Math. 47 (1993), pp. 211–217; L.V. Kantorovich and G.P. Akilov, Functional Analysis, Pergamon Press, Oxford, 1982; D. Li and M. Fukushima, Globally Convergent Broyden-like Methods for Semismooth Equations and Applications to VIP, NCP and MCP, Optimization and Numerical Algebra (Nanjing, 1999), Ann. Oper. Res. 103 (2001), pp. 71–97; C. Ma, A smoothing Broyden-like method for the mixed complementarity problems, Math. Comput. Modelling 41 (2005), pp. 523–538; G.J. Miel, Unified error analysis for Newton-type methods, Numer. Math. 33 (1979), pp. 391–396; G.J. Miel, Majorizing sequences and error bounds for iterative methods, Math. Comp. 34 (1980), pp. 185–202; I. Moret, A note on Newton type iterative methods, Computing 33 (1984), pp. 65–73; F.A. Potra, Sharp error bounds for a class of Newton-like methods, Libertas Math. 5 (1985), pp. 71–84; W.C. Rheinboldt, A unified convergence theory for a class of iterative processes, SIAM J. Numer. Anal. 5 (1968), pp. 42–63; T. Yamamoto, A convergence theorem for Newton-like methods in Banach spaces, Numer. Math. 51 (1987), pp. 545–557; P.P. Zabrejko and D.F. Nguen, The majorant method in the theory of Newton–Kantorovich approximations and the Pták error estimates, Numer. Funct. Anal. Optim. 9 (1987), pp. 671–684; A.I. Zin[cbreve]enko, Some approximate methods of solving equations with non-differentiable operators, (Ukrainian), Dopovidi Akad. Nauk Ukraïn. RSR (1963), pp. 156–161]. Applications and numerical examples, involving a nonlinear integral equation of Chandrasekhar-type, and a differential equation are also provided in this study.     

On local convergence of a Newton-type method in Banach space

In this study we are concerned with the local convergence of a Newton-type method introduced by us [I.K. Argyros and D. Chen, On the midpoint iterative method for solving nonlinear equations in Banach spaces, Appl. Math. Lett. 5 (1992), pp. 7–9.] for approximating a solution of a nonlinear equation in a Banach space setting. This method has also been studied by Homeier [H.H.H. Homeier, A modified Newton method for rootfinding with cubic convergence, J. Comput. Appl. Math. 157 (2003), pp. 227–230.] and Özban [A.Y. Özban, Some new variants of Newton's method, Appl. Math. Lett. 17 (2004), pp. 677–682.] in real or complex space. The benefits of using this method over other methods using the same information have been explained in [I.K. Argyros, Computational theory of iterative methods, in Studies in Computational Mathematics, Vol. 15, C.K. Chui and L. Wuytack, eds., Elsevier Science Inc., New York, USA, 2007.; I.K. Argyros and D. Chen, On the midpoint iterative method for solving nonlinear equations in Banach spaces, Appl. Math. Lett. 5 (1992), pp. 7–9.; H.H.H. Homeier, A modified Newton method for rootfinding with cubic convergence, J. Comput. Appl. Math. 157 (2003), pp. 227–230.; A.Y. Özban, Some new variants of Newton's method, Appl. Math. Lett. 17 (2004), pp. 677–682.]. Here, we give the convergence radii for this method under a type of weak Lipschitz conditions proven to be fruitful by Wang in the case of Newton's method [X. Wang, Convergence of Newton's method and inverse function in Banach space, Math. Comput. 68 (1999), pp. 169–186 and X. Wang, Convergence of Newton's method and uniqueness of the solution of equations in Banach space, IMA J. Numer. Anal. 20 (2000), pp. 123–134.]. Numerical examples are also provided.