Evaluations of Parameters for the Optimization of S.S.O.R. and A.D.I. Preconditioning

The main goal of this paper is to give two ways to estimate the needed parameters in order to obtain the condition number of S.S.O.R. preconditioned matrices, namely, the algebraic matricial formulation of convexity Riesz theorem and the tridiagonal Fourier analysis. The improvement with respect to Axelsson's approach is explicitly given. Estimations of the condition number in the case of A.D.I. preconditioning is also considered.     

HSS METHOD WITH A COMPLEX PARAMETER FOR THE SOLUTION OF COMPLEX LINEAR SYSTEM

In this paper, a complex parameter is employed in the Hermitian and skew-Hermitian splitting (HSS) method (Bai, Golub and Ng: SIAM J. Matrix Anal. Appl., 24(2003), 603-626) for solving the complex linear system $Ax=f$. The convergence of the resulting method is proved when the spectrum of the matrix $A$ lie in the right upper (or lower) part of the complex plane. We also derive an upper bound of the spectral radius of the HSS iteration matrix, and an estimated optimal parameter $α$(denoted by $α_{est}$) of this upper bound is presented. Numerical experiments on two modified model problems show that the HSS method with $α_{est}$has a smaller spectral radius than that with the real parameter which minimizes the corresponding upper bound. In particular, for the 'dominant' imaginary part of the matrix $A$, this improvement is considerable. We also test the GMRES method preconditioned by the HSS preconditioning matrix with our parameter $α_{est}$.     

On the spectral radius of the Jacobi iteration matrix for a rectangular region with two different media

The spectral radius of the Jacobi iteration matrix plays an important role to estimate the optimum relaxation factor, when the successive overrelaxation (SOR) method is used for solving a linear system. The specific systems are finite difference forms of the Laplace equation satisfied on a rectanglar region with two different media. Though the potential function for the inhomogeneous closed region is continuous, the first order derivative is not continuous. So this requires internal boundary conditions or interface conditions. In this paper, the spectral radius of the Jacobi iteration matrix for the inhomogeneous rectangular region is formulated and the approximation for the explicit formula, suitable for the computation of the spectral radius, is deduced. It is also found by the proposed formula that the spectral radius and the optimum relaxation factor rigorously depend on the inhomogeneity or the internal boundary conditions in the closed region, and especially vary with the position of the internal boundary. These findings are also confirmed by the numerical results of the power method.The stationary iterative method using the proposed formula for calculating estimates of the spectral radius of the Jacobi iteration matrix is compared with Carré's method, Kulstrud's method and the stationary iterative method using Frankel's theoretical formula, all for the case of some numerical models with two different media. According to the results our stationary iterative method gives the best results ffor the estimate of the spectral radius of the Jacobi iteration matrix, for the required number of iterations to calculate solutions, and for the accuracy of the solutions.As a numerical example the microstrip transmission line is taken, the propating mode of which can be approximated by a TEM mode. The cross section includes inhomogeneous media and a strip conductor. Upper and lower bounds of the spectral radius of the Jacobi iteration matrix are estimated. Our method using these estimates is also compared with the other methods. The upper bound of the spectral radius of the Jacobi iteration matrix for more general closed regions with two different media might be given by the proposed formula.     

A generalisation of systematic relaxation methods for consistently ordered matrices

Summary A systematic relaxation method is analysed for consistently ordered matrices as defined by Broyden (1964). The method is a generalisation of successive over-relaxation (S.O.R.). A relation is derived between the eigenvalues of the iteration matrix of the method and the eigenvalues of the Jacobi iteration matrix. Forp-cyclic matrices, the method corresponds to using a special type of diagonal matrix instead of a single relaxation factor. For certain choices of this diagonal matrix, the method has a better asymptotic rate of convergence than S.O.R. and requires less calculations and computer store.     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

迭代矩阵谱半径的上界估计

该文对一类广义对角占优矩阵Ｍ,给出了迭代矩阵Ｍ－１Ｎ 的谱半径的上界．特别,当Ｍ是严格对角占优时,证明了所得到的估计值总比通常用作谱半径的估计值要好．     

Acceleration of Convergence of Static and Dynamic Iterations

A new technique for acceleration of convergence of static and dynamic iterations for systems of linear equations and systems of linear differential equations is proposed. This technique is based on splitting the matrix of the system in such a way that the resulting iteration matrix has a minimal spectral radius for linear systems and a minimal spectral radius for some value of a parameter in Laplace transform domain for linear differential systems.This revised version was published online in October 2005 with corrections to the Cover Date.     

并行多分裂AOR迭代法的收敛定理

对解非奇异线性方程组的并行多分裂ＡＯＲ方法,本文给出了该方法的收敛性定理,同时也给出了该方法的迭代矩阵的谱半径的上界估计式。     

Poisson方程差分格式迭代解法中一些最优参数的有理拟合方法(英文)

本文针对二维Poisson方程五点和九点差分格式,导出了求解这些格式的SOR方法中最优松弛因子与区域剖分数的有理拟合公式,给出了Jacobi结合Chebyshev加速方法中Jacobi迭代矩阵谱半径的有理拟合公式.实际计算表明这些公式计算效果良好.     

Convergences of splitting iterative methods for symmetric indefinite linear systems

In this paper, we generalize the saddle point problem to general symmetric indefinite systems, we also present a kind of convergent splitting iterative methods for the symmetric indefinite systems. A special divergent splitting is introduced. The sufficient condition is discussed that the eigenvalues of the iteration matrix are real. The spectral radius of the iteration matrix is discussed in detail, the convergence theories of the splitting iterative methods for the symmetric indefinite systems are obtained. Finally, we present a preconditioner and discuss the eigenvalues of preconditioned matrix.     

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.     

关于ρ(L_(r,w))、ρ(J_w)的最小值

本文证明了当线性方程组系数矩阵 A之 Jacobi迭代矩阵 B=L+ U≥ 0 ,ρ( B) <1时 Gauss-Seidel法之迭代矩阵 G=L1,1的谱半径 ρ( G) =ρ( L1,1)是 ρ( Lr,w) ( 0≤ r≤w≤ 1 ,w>0 )中的最小值 ,即此时 Gauss-Seidel迭代是 AOR法中收敛最快的迭代法 .并且对 JOR法 (谱半径为 ρ( Jw) )和 SAOR法也作了相应的论述 .     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

基于分数阶扩散方程的离散线性代数方程组迭代方法研究

本文构建一类双参数拟Toeplitz分裂（TQTS）迭代方法求解变系数非定常空间分数阶扩散方程.TQTS迭代法是基于QTS迭代法引入双参技术建立而成,通过选取适当的参数使迭代矩阵谱半径变得更小,从而有效提升收敛的速度.然后对TQTS迭代法进行收敛性分析,获得相应的收敛区域,并对迭代法中涉及的参数进行讨论,获得使迭代矩阵谱半径上界达到最小的最优参数的表达式.最后通过数值仿真实验验证TQTS迭代法的有效性,实验结果表明TQTS迭代法改进效果十分突出,在迭代时间和步数上均有明显的减小.     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations

In this paper, we present a preconditioned variant of the generalized successive overrelaxation (GSOR) iterative method for solving a broad class of complex symmetric linear systems. We study conditions under which the spectral radius of the iteration matrix of the preconditioned GSOR method is smaller than that of the GSOR method and determine the optimal values of iteration parameters. Numerical experiments are given to verify the validity of the presented theoretical results and the effectiveness of the preconditioned GSOR method. Copyright © 2015 John Wiley & Sons, Ltd.     

AN A.D.I.GALERKIN METHOD FOR NONLINEAR PARABOLIC INTEGRO-DIFFERENTIAL EQUATION USING PATCH APPROXIMATION

An A. D. I. Galerkin scheme for three-dimensional nonlinear parabolic integro-differen-tial equation is studied. By using alternating-direction, the three-dimensional problem is reduced to a family of single space variable problems, the calculation is simplified; by using a local approxima-tion of the coefficients based on patches of finite elements, the coefficient matrix is updated at each time step; by using Ritz-Volterra projection, integration by part and other techniques, the influence coming from the integral term is treated; by using inductive hypothesis reasoning, the difficulty coming from the nonlinearity is treated. For both Galerkin and A. D. I. Galerkin schemes the con-vergence properties are rigorously demonstrated, the optimal H~1-norm and L~2-norm estimates are obtained.     

A geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.     

Adaptive sequencing of primal,dual, and design steps in simulation based optimization

Many researchers have used Oneshot optimization methods based on user-specified primal state iterations, the corresponding adjoint iterations, and appropriately preconditioned design steps. Our goal here is to develop heuristics for sequencing these three subtasks, in order to optimize the convergence rate of the resulting coupled iteration cycle. A key ingredient is the preconditioning in the design step by a BFGS approximation of the projected Hessian. We provide a hard bound on the spectral radius of the coupled iteration cycle at local minima satisfying second order sufficiency conditions. Finally, we show how certain problem specific parameters can be estimated by local samples and be used to steer the whole process adaptively. We present limited numerical results that confirm the theoretical analysis.     

A special Hermitian and skew-Hermitian splitting method for image restoration

In this paper, we consider an ill-posed image restoration problem with a noise contaminated observation, and a known convolution kernel. A special Hermitian and skew-Hermitian splitting (HSS) iterative method is established for solving the linear systems from image restoration. Our approach is based on an augmented system formulation. The convergence and operation cost of the special HSS iterative method for image restoration problems are discussed. The optimal parameter minimizing the spectral radius of the iteration matrix is derived. We present a detailed algorithm for image restoration problems. Numerical examples are given to demonstrate the performance of the presented method. Finally, the SOR acceleration scheme for the special HSS iterative method is discussed.