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.     

Mesh‐independent convergence of the modified inexact Newton method for a second order non‐linear problem

In this paper, we consider an inexact Newton method applied to a second order non‐linear problem with higher order non‐linearities. We provide conditions under which the method has a mesh‐independent rate of convergence. To do this, we are required, first, to set up the problem on a scale of Hilbert spaces and second, to devise a special iterative technique which converges in a higher than first order Sobolev norm. We show that the linear (Jacobian) system solved in Newton's method can be replaced with one iterative step provided that the initial non‐linear iterate is accurate enough. The closeness criteria can be taken independent of the mesh size. Finally, the results of numerical experiments are given to support the theory. Published in 2005 by John Wiley & Sons, Ltd.     

Modified Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive‐definite linear systems

To further study the Hermitian and non‐Hermitian splitting methods for a non‐Hermitian and positive‐definite matrix, we introduce a so‐called lopsided Hermitian and skew‐Hermitian splitting and then establish a class of lopsided Hermitian/skew‐Hermitian (LHSS) methods to solve the non‐Hermitian and positive‐definite systems of linear equations. These methods include a two‐step LHSS iteration and its inexact version, the inexact Hermitian/skew‐Hermitian (ILHSS) iteration, which employs some Krylov subspace methods as its inner process. We theoretically prove that the LHSS method converges to the unique solution of the linear system for a loose restriction on the parameter α. Moreover, the contraction factor of the LHSS iteration is derived. The presented numerical examples illustrate the effectiveness of both LHSS and ILHSS iterations. Copyright © 2007 John Wiley & Sons, Ltd.     

Semilocal and global convergence of the Newton‐HSS method for systems of nonlinear equations

Newton‐HSS methods, which are variants of inexact Newton methods different from the Newton–Krylov methods, have been shown to be competitive methods for solving large sparse systems of nonlinear equations with positive‐definite Jacobian matrices (J. Comp. Math. 2010; 28 :235–260). In that paper, only local convergence was proved. In this paper, we prove a Kantorovich‐type semilocal convergence. Then we introduce Newton‐HSS methods with a backtracking strategy and analyse their global convergence. Finally, these globally convergent Newton‐HSS methods are shown to work well on several typical examples using different forcing terms to stop the inner iterations. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

Computational experience with numerical methods for nonnegative least‐squares problems

We discuss the solution of large‐scale box‐constrained linear least‐squares problems by two recent affine‐scaling methods: a cyclic Barzilai–Borwein strategy and an Inexact Newton‐like method where a preconditioning technique allows for an efficient computation of the steps. A robust globally and fast locally convergent method based on the combination of the two procedures is presented along with extensive numerical results. Copyright © 2010 John Wiley & Sons, Ltd.     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.     

Two‐grid mixed finite‐element methods for nonlinear Schrödinger equations

Two‐grid mixed finite element schemes are developed for solving both steady state and unsteady state nonlinear Schrödinger equations. The schemes use discretizations based on a mixed finite‐element method. The two‐grid approach yields iterative procedures for solving the nonlinear discrete equations. The idea is to relegate all of the Newton‐like iterations to grids much coarser than the final one, with no loss in order of accuracy. Numerical tests are performed. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 63‐73, 2012     

A choice of forcing terms in inexact Newton method

Inexact Newton method is one of the effective tools for solving systems of nonlinear equations. In each iteration step of the method, a forcing term, which is used to control the accuracy when solving the Newton equations, is required. The choice of the forcing terms is of great importance due to their strong influence on the behavior of the inexact Newton method, including its convergence, efficiency, and even robustness. To improve the efficiency and robustness of the inexact Newton method, a new strategy to determine the forcing terms is given in this paper. With the new forcing terms, the inexact Newton method is locally Q-superlinearly convergent. Numerical results are presented to support the effectiveness of the new forcing terms.     

Two‐level Newton iterative method for the 2D/3D steady Navier‐Stokes equations

A combination method of the Newton iteration and two‐level finite element algorithm is applied for solving numerically the steady Navier‐Stokes equations under the strong uniqueness condition. This algorithm is motivated by applying the m Newton iterations for solving the Navier‐Stokes problem on a coarse grid and computing the Stokes problem on a fine grid. Then, the uniform stability and convergence with respect to ν of the two‐level Newton iterative solution are analyzed for the large m and small H and h << H. Finally, some numerical tests are made to demonstrate the effectiveness of the method. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2012     

A two‐grid method for mixed finite‐element solution of reaction‐diffusion equations

We present a scheme for solving two‐dimensional, nonlinear reaction‐diffusion equations, using a mixed finite‐element method. To linearize the mixed‐method equations, we use a two grid scheme that relegates all the Newton‐like iterations to a grid Δ_H much coarser than the original one Δ_h, with no loss in order of accuracy so long as the mesh sizes obey . The use of a multigrid‐based solver for the indefinite linear systems that arise at each coarse‐grid iteration, as well as for the similar system that arises on the fine grid, allows for even greater efficiency. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 317–332, 1999     

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 two high‐order families of frozen Newton‐type methods

This paper is devoted to the study of two high‐order families of frozen Newton‐type methods. The methods are free of bilinear operators, which constitute the main limitation of the classical high‐order iterative schemes. Both families are natural generalizations of an efficient third‐order method. Although the methods are more demanding, a semilocal convergence analysis is presented using weaker conditions.     

Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

Theoretical Efficiency of an Inexact Newton Method

We propose a local algorithm for smooth unconstrained optimization problems with n variables. The algorithm is the optimal combination of an exact Newton step with Choleski factorization and several inexact Newton steps with preconditioned conjugate gradient subiterations. The preconditioner is taken as the inverse of the Choleski factorization in the previous exact Newton step. While the Newton method is converging precisely with Q-order 2, this algorithm is also precisely converging with Q-order 2. Theoretically, its average number of arithmetic operations per step is much less than the corresponding number of the Newton method for middle-scale and large-scale problems. For instance, when n=200, the ratio of these two numbers is less than 0.53. Furthermore, the ratio tends to zero approximately at a rate of log 2/logn when n approaches infinity.     

Shape reconstruction for the time‐dependent Navier‐Stokes flow

This article deals with the shape reconstruction of a bounded domain with a viscous incompressible fluid driven by the time‐dependent Navier‐Stokes equations. For the approximate solution of the ill‐posed and nonlinear problem we propose a regularized Newton method. A theoretical foundation for the Newton method is given by establishing the differentiability of the initial boundary value problem with respect to the interior boundary curve in the sense of the domain derivative. Numerical examples indicate the feasibility of our method. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2008     

Two‐grid methods for mixed finite‐element solution of coupled reaction‐diffusion systems

We develop 2‐grid schemes for solving nonlinear reaction‐diffusion systems: where p = (p, q) is an unknown vector‐valued function. The schemes use discretizations based on a mixed finite‐element method. The 2‐grid approach yields iterative procedures for solving the nonlinear discrete equations. The idea is to relegate all the Newton‐like iterations to grids much coarser than the final one, with no loss in order of accuracy. The iterative algorithms examined here extend a method developed earlier for single reaction‐diffusion equations. An application to prepattern formation in mathematical biology illustrates the method's effectiveness. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 589–604, 1999     

Regularization and preconditioning of KKT systems arising in nonnegative least‐squares problems

A regularized Newton‐like method for solving nonnegative least‐squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the interior‐point scaling matrix. Preliminary computational results confirm the effectiveness of the preconditioner and fast convergence of the iterative method established by the analysis performed in this paper. Copyright © 2008 John Wiley & Sons, Ltd.     

(Almost) matrix‐free solver for piecewise linear functions in abs‐normal form

The abs‐normal form (ANF) is a compact algebraic representation for piecewise linear functions. These functions can be used to approximate piecewise smooth functions and contain valuable information about the nonsmoothness of the investigated function. The information helps to define step directions within general Newton methods that obey the structure of the original function and typically yield better convergence. However, the computation of the generalized Newton directions requires the solution of a piecewise linear equation in ANF. It was observed that the ANF can become very large, even for simple functions. Hence, if a solver is based on the ANF and uses the (Schur‐complement) matrices of the explicit ANF representation, it has to be considered computationally expensive. In this paper, we will address this question and present the first (almost) matrix‐free versions of some solver for ANFs. The theoretical discussion is supported by some numerical run‐time experiments.     

First‐Order system least squares for generalized‐Newtonian coupled Stokes‐Darcy flow

The coupled problem for a generalized Newtonian Stokes flow in one domain and a generalized Newtonian Darcy flow in a porous medium is studied in this work. Both flows are treated as a first‐order system in a stress‐velocity formulation for the Stokes problem and a volumetric flux‐hydraulic potential formulation for the Darcy problem. The coupling along an interface is done using the well‐known Beavers–Joseph–Saffman interface condition. A least squares finite element method is used for the numerical approximation of the solution. It is shown that under some assumptions on the viscosity the error is bounded from above and below by the least squares functional. An adaptive refinement strategy is examined in several numerical examples where boundary singularities are present. Due to the nonlinearity of the problem a Gauss–Newton method is used to iteratively solve the problem. It is shown that the linear variational problems arising in the Gauss–Newton method are well posed. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1150–1173, 2015