Variant of Greedy Randomized Gauss-Seidel Method for Ridge Regression

The variants of randomized Kaczmarz and randomized Gauss-Seidel algorithms are two effective stochastic iterative methods for solving ridge regression problems. For solving ordinary least squares regression problems, the greedy randomized Gauss-Seidel (GRGS) algorithm always performs better than the randomized Gauss-Seidel algorithm (RGS) when the system is overdetermined. In this paper, inspired by the greedy modification technique of the GRGS algorithm, we extend the variant of the randomized Gauss-Seidel algorithm, obtaining a variant of greedy randomized Gauss-Seidel (VGRGS) algorithm for solving ridge regression problems. In addition, we propose a relaxed VGRGS algorithm and the corresponding convergence theorem is established. Numerical experiments show that our algorithms outperform the VRK-type and the VRGS algorithms when $m > n$.     

An iterative method based on equation decomposition for the fourth‐order singular perturbation problem

In this article, we propose an iterative method based on the equation decomposition technique ( 1 ) for the numerical solution of a singular perturbation problem of fourth‐order elliptic equation. At each step of the given method, we only need to solve a boundary value problem of second‐order elliptic equation and a second‐order singular perturbation problem. We prove that our approximate solution converges to the exact solution when the domain is a disc. Our numerical examples show the efficiency and accuracy of our method. Our iterative method works very well for singular perturbation problems, that is, the case of 0 < ε ? 1, and the convergence rate is very fast. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Block s‐step Krylov iterative methods

Block (including s‐step) iterative methods for (non)symmetric linear systems have been studied and implemented in the past. In this article we present a (combined) block s‐step Krylov iterative method for nonsymmetric linear systems. We then consider the problem of applying any block iterative method to solve a linear system with one right‐hand side using many linearly independent initial residual vectors. We present a new algorithm which combines the many solutions obtained (by any block iterative method) into a single solution to the linear system. This approach of using block methods in order to increase the parallelism of Krylov methods is very useful in parallel systems. We implemented the new method on a parallel computer and we ran tests to validate the accuracy and the performance of the proposed methods. It is expected that the block s‐step methods performance will scale well on other parallel systems because of their efficient use of memory hierarchies and their reduction of the number of global communication operations over the standard methods. Copyright © 2009 John Wiley & Sons, Ltd.     

混合边界条件下的三维定常 旋转Navier-Stokes方程的原始变量有限元计算

本文利用原始变量有限元法求解混合边界条件下的三维定常旋转Navier-Stokes方程,证明了离散问题解的存在唯一性,得到了有限元解的最优误差估计.给出了求解原始变量有限元逼近解的简单迭代算法,并证明了算法的收敛性.针对三维情况下计算资源的限制,采用压缩的行存储格式存储刚度矩阵的非零元素,并利用不完全的LU分解作预处理的GMRES方法求解线性方程组.最后分析了简单迭代和牛顿迭代的优劣对比,数值算例表明在同样精度下简单迭代更节约计算时间.     

矩阵方程AX＋XB=C的双对称解及其最佳逼近

提出一种求解线性矩阵方程AX＋XB=C双对称解的迭代法.该算法能够自动地判断解的情况,并在方程相容时得到方程的双对称解,在方程不相容时得到方程的最小二乘双对称解.对任意的初始矩阵,在没有舍入误差的情况下,经过有限步迭代得到问题的一个双对称解.若取特殊的初始矩阵,则可以得到问题的极小范数双对称解,从而巧妙地解决了对给定矩...     

On the convergence of nonstationary column-oriented version of algebraic iterative methods

Recently, Elfving, Hansen, and Nikazad introduced a successful nonstationary block-column iterative method for solving linear system of equations based on flagging idea (called BCI-F). Their numerical tests show that the column-action method provides a basis for saving computational work using flagging technique in BCI algorithm. However, they did not present a general convergence analysis. In this paper, we give a convergence analysis of BCI-F. Furthermore, we consider a fully flexible version of block-column iterative method (FBCI), in which the relaxation parameters and weight matrices can be updated in each iteration and the column partitioning of coefficient matrix is allowed to update in each cycle. We also provide the convergence analysis of algorithm FBCI under mild conditions.     

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.     

矩阵方程X+A*X-nA=I的正定解

In this paper we give some sufficient conditions and some necessary conditions under which the matrix equation X A^*X^-nA=I has a positive definite solution. An iterative method which converges to a positive definite solution of this equation is constructed. And an error estimate formula on this iterative method is also derived.     

Multipole fast algorithm for the least‐squares approach of the method of fundamental solutions for three‐dimensional harmonic problems

In this article we describe an improvement in the speed of computation for the least‐squares method of fundamental solutions (MFS) by means of Greengard and Rokhlin's FMA. Iterative solution of the linear system of equations is performed for the equations given by the least‐squares formulation of the MFS. The results of applying the method to test problems from potential theory with a number of boundary points in the order of 80,000 show that the method can achieve fast solutions for the potential and its directional derivatives. The results show little loss of accuracy and a major reduction in the memory requirements compared to the direct solution method of the least squares problem with storage of the full MFS matrix. The method can be extended to the solution of overdetermined systems of equations arising from boundary integral methods with a large number of boundary integration points. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 828–845, 2003.     

求解带非线性边界条件的反应扩散方程数值解的组合迭代方法

1　引　　言我们首先考虑如下抛物型方程ｕｔ-ＤΔｕ =ｆ(ｘ ,ｔ ,ｕ) (ｔ∈ ( 0 ,Ｔ],ｘ∈Ω ) ｕ/ ν+ βｕ =ｇ(ｘ ,ｔ ,ｕ) (ｔ∈ ( 0 ,Ｔ],ｘ∈ Ω )ｕ(ｘ ,0 ) =ψ(ｘ) (ｘ∈Ω )( 1 .1 )其中Ｔ为正常数 ,Ω 是ＲＰ 空间的有界区域 记ＱＴ=Ω × ( 0 ,Ｔ],ＳＴ= Ω × ( 0 ,Ｔ],假设在ＱＴ上Ｄ≡ｄ(ｘ ,ｔ) >0 ,在ＳＴ 上β≡β(ｘ ,ｔ)≥ 0 又设 ｆ(ｘ ,ｔ,ｕ) ,ｇ(ｘ ,ｔ,ｕ)为关于ｕ的非线性函数 ,且对ｘ ,ｔ各参数满足Ｈ¨ｏｌｄｅｒ连续条件 将 ( 1 .1 )离散化之后我们得到相应的有限差分系统 ,当 ｇ(ｘ ,ｔ,ｕ)为ｕ的线性…     

A modified modulus method for symmetric positive‐definite linear complementarity problems

By reformulating the linear complementarity problem into a new equivalent fixed‐point equation, we deduce a modified modulus method, which is a generalization of the classical one. Convergence for this new method and the optima of the parameter involved are analyzed. Then, an inexact iteration process for this new method is presented, which adopts some kind of iterative methods for determining an approximate solution to each system of linear equations involved in the outer iteration. Global convergence for this inexact modulus method and two specific implementations for the inner iterations are discussed. Numerical results show that our new methods are more efficient than the classical one under suitable conditions. Copyright © 2008 John Wiley & Sons, Ltd.     

含高次逆幂的矩阵方程对称解的双迭代算法

本文研究了在控制理论和随机滤波等领域中遇到的一类含高次逆幂的矩阵方程的等价矩阵方程对称解的数值计算问题.采用牛顿算法求等价矩阵方程的对称解,并采用修正共轭梯度法求由牛顿算法每一步迭代计算导出的线性矩阵方程的对称解或者对称最小二乘解,建立了求这类矩阵方程对称解的双迭代算法,数值算例验证了双迭代算法是有效的.     

A generalized LSQR algorithm

LSQR is a popular iterative method for the solution of large linear system of equations and least‐squares problems. This paper presents a generalization of LSQR that allows the choice of an arbitrary initial vector for the solution subspace. Computed examples illustrate the benefit of being able to choose this vector. Copyright © 2008 John Wiley & Sons, Ltd.     

A NOTE ON COMPARISON THEOREM OF TWO-STAGE ITERATIVE METHOD FOR HERMITIAN POSITIVE DEFINITE LINEAR SYSTEMS

We discuss two-stage iterative methods for the solution of linear system Ax = b, and give a new proof of the comparison theorems of two-stage iterative method for an Hermitian positive definite matrix. Meanwhile, we put forward two new versions of well known comparison theorem and apply them to some examples.     

Iterative methods for solving fourth- and sixth-order time-fractional Cahn-Hillard equation

This paper presents analytical-approximate solutions of the time-fractional Cahn-Hilliard (TFCH) equations of fourth and sixth order using the new iterative method (NIM) and q-homotopy analysis method (q-HAM). We obtained convergent series solutions using these two iterative methods. The simplicity and accuracy of these methods in solving strongly nonlinear fractional differential equations is displayed through the examples provided. In the case where exact solution exists, error estimates are also investigated.     

Existence and uniqueness of solutions of infinite systems of semilinear parabolic differential-functional equations in arbitrary domains in ordered banach spaces

We consider the Fourier first initial-boundary value problem for a weakly coupled infinite system of semilinear parabolic differential-functional equations of reaction-diffusion type in arbitrary (bounded or unbounded) domain. The right-hand sides of the system are functionals of unknown functions of the Volterra type. Differential-integral equations give examples of such equations. To prove the existence and uniqueness of the solutions, we apply the monotone iterative method. The underlying monotone iterative scheme can be used for the computation of numerical solution.     

Solving evolution equations using a new iterative method

In this article, we apply the new iterative method proposed by Daftardar‐Gejji and Jafari (J Math Anal Appl 316, (2006), 753–763) for solving various linear and nonlinear evolution equations. The results obtained are compared with the results by existing methods. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

A block monotone iterative method for numerical solutions of nonlinear elliptic boundary value problems

The aim of this article is to develop a new block monotone iterative method for the numerical solutions of a nonlinear elliptic boundary value problem. The boundary value problem is discretized into a system of nonlinear algebraic equations, and a block monotone iterative method is established for the system using an upper solution or a lower solution as the initial iteration. The sequence of iterations can be computed in a parallel fashion and converge monotonically to a maximal solution or a minimal solution of the system. Three theoretical comparison results are given for the sequences from the proposed method and the block Jacobi monotone iterative method. The comparison results show that the sequence from the proposed method converges faster than the corresponding sequence given by the block Jacobi monotone iterative method. A simple and easily verified condition is obtained to guarantee a geometric convergence of the block monotone iterations. The numerical results demonstrate advantages of this new approach. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Consistency of iterative operator‐splitting methods: Theory and applications

In this article, we describe a different operator‐splitting method for decoupling complex equations with multidimensional and multiphysical processes for applications for porous media and phase‐transitions. We introduce different operator‐splitting methods with respect to their usability and applicability in computer codes. The error‐analysis for the iterative operator‐splitting methods is discussed. Numerical examples are presented. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Numerical analysis for the quadratic matrix equations from a modification of fixed‐point type

In this paper, we study the quadratic matrix equations. To improve the application of iterative schemes, we use a transform of the quadratic matrix equation into an equivalent fixed‐point equation. Then, we consider an iterative process of Chebyshev‐type to solve this equation. We prove that this iterative scheme is more efficient than Newton's method. Moreover, we obtain a local convergence result for this iterative scheme. We finish showing, by an application to noisy Wiener‐Hopf problems, that the iterative process considered is computationally more efficient than Newton's method.