A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

Convergence of an adaptive Ka?anov FEM for quasi-linear problems

We design an adaptive finite element method to approximate the solutions of quasi-linear elliptic problems. The algorithm is based on a Ka?anov iteration and a mesh adaptation step is performed after each linear solve. The method is thus inexact because we do not solve the discrete nonlinear problems exactly, but rather perform one iteration of a fixed point method (Ka?anov), using the approximation of the previous mesh as an initial guess. The convergence of the method is proved for any reasonable marking strategy and starting from any initial mesh. We conclude with some numerical experiments that illustrate the theory.     

The semi-convergence properties of MHSS method for a class of complex nonsymmetric singular linear systems

We use the modified Hermitian and skew-Hermitian splitting (MHSS) iteration method to solve a class of complex nonsymmetric singular linear systems. The semi-convergence properties of the MHSS method are studied by analyzing the spectrum of the iteration matrix. Moreover, after investigating the semi-convergence factor and estimating its upper bound for the MHSS iteration method, an optimal iteration parameter that minimizes the upper bound of the semi-convergence factor is obtained. Numerical experiments are used to illustrate the theoretical results and examine the effectiveness of the MHSS method served both as a preconditioner for GMRES method and as a solver.     

A new algorithm for total variation based image denoising

We propose a new algorithm for the total variation based on image denoising problem. The split Bregman method is used to convert an unconstrained minimization denoising problem to a linear system in the outer iteration. An algebraic multi-grid method is applied to solve the linear system in the inner iteration. Furthermore, Krylov subspace acceleration is adopted to improve convergence in the outer iteration. Numerical experiments demonstrate that this algorithm is efficient even for images with large signal-to-noise ratio.     

The Monte-Carlo algorithm for the solving of systems of linear algebraic equations by the Seidel method

The iteration algorithm is used to solve systems of linear algebraic equations by the Monte-Carlo method. Each next iteration is simulated as a random vector such that its expectation coincides with the Seidel approximation of the iteration process. We deduce a system of linear equations such that mutual correlations of components of the limit vector and correlations of two iterations satisfy them. We prove that limit dispersions of the random vector of solutions of the system exist and are finite.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

一类四阶微积分方程的Legendre-Galerkin谱逼近

针对研究吊桥模型而建立的四阶微积分方程, 提出Legendre谱逼近法进行求解.构造迭代算法来求解得到的线性系统, 证明了迭代格式的收敛性, 对问题进行了误差分析.数值算例验证了迭代的收敛性和方法的高精度.     

A new class of polynomial primal–dual methods for linear and semidefinite optimization

We propose a new class of primal–dual methods for linear optimization (LO). By using some new analysis tools, we prove that the large-update method for LO based on the new search direction has a polynomial complexity of O(n^4/(4+ρ)log(n/ε)) iterations, where ρ∈[0,2] is a parameter used in the system defining the search direction. If ρ=0, our results reproduce the well-known complexity of the standard primal–dual Newton method for LO. At each iteration, our algorithm needs only to solve a linear equation system. An extension of the algorithms to semidefinite optimization is also presented.     

Reconstruction of biologic tissue conductivity from noisy magnetic field by integral equation method

Magnetic resonance electrical impedance tomography (MREIT) is a new technique to recover the conductivity of biologic tissue from the induced magnetic flux density. This paper proposes an inversion scheme for recovering the conductivity from one component of the magnetic field based on the nonlinear integral equation method. To apply magnetic fields corresponding to two incoherent injected currents, an alternative iteration scheme is proposed to update the conductivity. For each magnetic field, the regularizing technique on the finite dimensional space is applied to solve an ill-posed linear system. Compared with the well-developed harmonic B_z method, the advantage of this inversion scheme is its stability, since no differential operation is required on the noisy magnetic field. Numerical implementations are given to show the convergence of the iteration and its validity for noisy input data.     

Multigrid preconditioning for time-periodic Navier–Stokes problems

We propose to solve time-periodic Navier–Stokes problems by a discrete Fourier transform in time. Truncating the Fourier series yields a nonlinear system of equations for the unknown Fourier coefficients. Its solution by Picard iteration requires to solve a sequence of linear systems of equations. The focus of this work is on an efficient method to solve these linear systems. We employ GMRES, complemented by an optimal block triangular preconditioner. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A single-step HSS method for non-Hermitian positive definite linear systems

In this paper, based on the Hermitian and skew-Hermitian splitting (HSS) iteration method, a single-step HSS (SHSS) iteration method is introduced to solve the non-Hermitian positive definite linear systems. Theoretical analysis shows that, under a loose restriction on the iteration parameter, the SHSS method is convergent to the unique solution of the linear system. Furthermore, we derive an upper bound for the spectral radius of the SHSS iteration matrix, and the quasi-optimal parameter is obtained to minimize the above upper bound. Numerical experiments are reported to the efficiency of the SHSS method; numerical comparisons show that the proposed SHSS method is superior to the HSS method under certain conditions.     

离散空间分数阶非线性薛定谔方程的MHSS型迭代方法

利用隐式守恒型差分格式来离散空间分数阶非线性薛定谔方程,可得到一个离散线性方程组.该离散线性方程组的系数矩阵为一个纯虚数复标量矩阵、一个对角矩阵与一个对称Toeplitz矩阵之和.基于此,本文提出了用一种\textit{修正的埃尔米特和反埃尔米特分裂}(MHSS)型迭代方法来求解此离散线性方程组.理论分析表明,MHSS型迭代方法是无条件收敛的.数值实验也说明了该方法是可行且有效的.     

A Dynamical Tikhonov Regularization for Solving Ill-posed Linear Algebraic Systems

The Tikhonov method is a famous technique for regularizing ill-posed linear problems, wherein a regularization parameter needs to be determined. This article, based on an invariant-manifold method, presents an adaptive Tikhonov method to solve ill-posed linear algebraic problems. The new method consists in building a numerical minimizing vector sequence that remains on an invariant manifold, and then the Tikhonov parameter can be optimally computed at each iteration by minimizing a proper merit function. In the optimal vector method (OVM) three concepts of optimal vector, slow manifold and Hopf bifurcation are introduced. Numerical illustrations on well known ill-posed linear problems point out the computational efficiency and accuracy of the present OVM as compared with classical ones.     

利用变分迭代法解二阶常微分方程组边值问题

将变分迭代法用于求解二阶常微分方程组边值问题,给出方法在两个具体实例中的应用,验证了变分迭代法对求解线性、非线性二阶常微分方程组边值问题是一种非常简便有效的方法.     

Numerical implementation of iteration processes applied in the study of nonlinear boundary value problems of the theory of elasticity and filtration

Nonlinear elastic problems for hardening media are solved by applying the universal iteration process proposed by A.I. Koshelev in his works on the regularity of solutions to quasilinear elliptic and parabolic systems. This requires numerically solving a linear elliptic system at each step of the iteration procedure. The method is numerically implemented in the MATLAB environment by using its PDE Toolbox. A modification of the finite-element procedure is suggested in order to solve a linear algebraic system at each iteration step. The computer model is tested on simple examples. The same nonlinear problems are also solved by the method of elastic solutions, which consists in replacing the Laplace operator in the universal iteration process by the Lamé operator of linear elasticity. As is known, this iteration process converges to a weak solution of the nonlinear problem, provided that the displacements are fixed on the boundary. The method is tested on examples with stresses on the boundary. The third part of the paper is devoted to the nonlinear filtration problem. General properties of the iteration process for nonlinear parabolic systems have been studied by A.I. Koshelev and V.M. Chistyakov. The numerical implementation is based on slightly modified PDE Toolbox procedures. The program is tested on simple examples.     

Several variants of the Hermitian and skew‐Hermitian splitting method for a class of complex symmetric linear systems

This paper is concerned with several variants of the Hermitian and skew‐Hermitian splitting iteration method to solve a class of complex symmetric linear systems. Theoretical analysis shows that several Hermitian and skew‐Hermitian splitting based iteration methods are unconditionally convergent. Numerical experiments from an n‐degree‐of‐freedom linear system are reported to illustrate the efficiency of the proposed methods. Copyright © 2014 John Wiley & Sons, Ltd.     

Lopsided PMHSS iteration method for a class of complex symmetric linear systems

Based on the preconditioned modified Hermitian and skew-Hermitian splitting (PMHSS) iteration method, we introduce a lopsided PMHSS (LPMHSS) iteration method for solving a broad class of complex symmetric linear systems. The convergence properties of the LPMHSS method are analyzed, which show that, under a loose restriction on parameter α, the iterative sequence produced by LPMHSS method is convergent to the unique solution of the linear system for any initial guess. Furthermore, we derive an upper bound for the spectral radius of the LPMHSS iteration matrix, and the quasi-optimal parameter α ^? which minimizes the above upper bound is also obtained. Both theoretical and numerical results indicate that the LPMHSS method outperforms the PMHSS method when the real part of the coefficient matrix is dominant.     

Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems

In order to solve large sparse linear complementarity problems on parallel multiprocessor systems, we construct modulus-based synchronous two-stage multisplitting iteration methods based on two-stage multisplittings of the system matrices. These iteration methods include the multisplitting relaxation methods such as Jacobi, Gauss–Seidel, SOR and AOR of the modulus type as special cases. We establish the convergence theory of these modulus-based synchronous two-stage multisplitting iteration methods and their relaxed variants when the system matrix is an H _?+?-matrix. Numerical results show that in terms of computing time the modulus-based synchronous two-stage multisplitting relaxation methods are more efficient than the modulus-based synchronous multisplitting relaxation methods in actual implementations.     

Two-Stage Multisplitting Iteration Methods Using Modulus-Based Matrix Splitting as Inner Iteration for Linear Complementarity Problems

The matrix multisplitting iteration method is an effective tool for solving large sparse linear complementarity problems. However, at each iteration step we have to solve a sequence of linear complementarity sub-problems exactly. In this paper, we present a two-stage multisplitting iteration method, in which the modulus-based matrix splitting iteration and its relaxed variants are employed as inner iterations to solve the linear complementarity sub-problems approximately. The convergence theorems of these two-stage multisplitting iteration methods are established. Numerical experiments show that the two-stage multisplitting relaxation methods are superior to the matrix multisplitting iteration methods in computing time, and can achieve a satisfactory parallel efficiency.