On the convergence of subproper (multi)-splitting methods for solving rectangular linear systems

Abstract We give a convergence criterion for stationary iterative schemes based on subproper splittings for solving rectangular systems and show that, for special splittings, convergence and quotient convergence are equivalent. We also analyze the convergence of multisplitting algorithms for the solution of rectangular systems when the coefficient matrices have special properties and the linear systems are consistent. Keywords: Rectangular linear system, iterative method, proper splitting, subproper splitting, regularity, Hermitian positive semi-definite matrix, multi-splitting, quotient convergence AMS Subject Classification: 65F10, 65F15     

Convergence of P-regular splitting iterative methods for non-Hermitian positive semidefinite linear systems

In this paper, we study the convergence of P-regular splitting iterative methods for singular and non-singular non-Hermitian positive semidefinite linear systems, which generalize the known results. Some numerical experiments are performed to illustrate the convergence results.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

带控制时滞广义系统的PID型迭代学习算法

研究了一类线性时滞广义系统的迭代学习控制问题.针对广义系统的特点,引入选代学习控制方法,给出了线性时滞广义系统的PID型选代学习算法.结合矩阵广义逆理论,利用λ范数和Bellman引理,并从理论上给出了算法收敛性的完整证明.研究结果表明,只要充分利用广义系统的特点,寻找合适的收敛性分析方法,便可解决控制时滞广义系统的收敛性问题,对时滞广义系统速代学习控制问题的研究具有重要的理论意义与应用价值.     

Semiconvergence of P-regular splittings for solving singular linear systems

We investigate necessary and sufficient conditions for semiconvergence of a splitting for solving singular linear systems, where the coefficient matrix A is a singular EP matrix. When A is a singular Hermitian matrix, necessary and sufficient conditions for semiconvergence of P-regular splittings are given, which generalize known results. As applications, the necessary and sufficient conditions for semiconvergence of block AOR and SSOR iterative methods are derived. A numerical example is given to illustrate the theoretical results. The work is supported by the National Natural Science Foundation of China under grant 10371056, the Foundation for the Authors of the National Excellent Doctoral Thesis Award of China under grant 200720 and the Natural Science Foundation of Jiangsu Province of China under grant BK2006725.     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

An accelerated randomized Kaczmarz method via low-rank approximation

The Kaczmarz method for finding the solution to an overdetermined consistent system of linear equation Ax=b(A∈R^m×n) is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Recently, Strohmer and Vershynin proposed randomized Kaczmarz, and proved its exponential convergence. In this paper, motivated by idea of precondition, we present a modified version of the randomized Kaczmarz method where an orthogonal matrix was multiplied to both sides of the equation Ax=b, and the orthogonal matrix is obtained by low-rank approximation. Our approach fits the problem when m is huge and m?n. Theoretically, we improve the convergence rate of the randomized Kaczmarz method. The numerical results show that our approach is faster than the standard randomized Kaczmarz.     

Numerical performance of hyperplane constrained method and its hybrid method for singular value decomposition

The hyperplane constrained method has been proposed in Yadani et al. (Appl Math Comp 216:779–790, 2010) computing singular value decomposition (SVD) of matrix. In the method, the SVD is replaced with solving nonlinear systems whose solutions are constrained on hyperplane, and then their solutions are computed with the help of Newton’s iterative method. In this paper, we present a new convergence theorem concerning the hyperplane constrained method in finite arithmetic. We also clarify the numerical performance of the hyperplane constrained method. In numerical experiments, we first show that the computed singular values and singular vectors are with high accuracy, even if the target matrix of SVD has small singular values, almost the same singular values, not small condition number. Though the hyperplane constrained method requires not small amount of computations, it fastens by combining other fast singular value decomposition method. We next propose a hybrid method which adopts the singular vectors computed by other fast method as the initial guess of the Newton type iteration in order to decrease the iteration number. By numerical experiments, we can see that the hybrid method runs faster than the original hyperplane constrained method with almost same accuracy.     

Convergence of the interval and point TOR method

In this paper, we present the interval version of the two parameter overrelaxation iterative (TOR) method and we obtain some convergence conditions when the matrix A of the linear system Ax?=?b belongs to some classes of matrice. Similar conditions were obtained for the point TOR method.

Some results for the accelerated overrelaxation interval and point iterative (AOR) method were also obtained, which coincides with those given by Martins in Ref. [7].     

On Accelerated Iterative Methods for the Solution of Systems of Linear Equations

In literature, it has been reported that the convergence of some preconditioned stationary iterative methods using certain type upper triangular matrices as preconditioners are faster than the basic iterative methods. In this paper, a new preconditioned iterative method for the numerical solution of linear systems has been introduced, and the convergence analysis of the proposed method and an existing one have been done. Some numerical examples have also been given, which show the effectiveness of both of the methods.     

Solving inverse eigenvalue problems by a projected Newton method

The inverse eigenvalue problem for symmetric matrices (IEP) can be formulated as a system of two matrix equations. For solving the system a variation of Newton's method is used which has been proposed by Fusco and Zecca [Calcolo XXIII (1986), pp. 285–303] for the simultaneous computation of eigenvalues and eigenvectors of a given symmetric matrix. An iteration step of this method consists of a Newton step followed by an orthonormalization with the consequence that each iterate satisfies one of the given equations. The method is proved to convergence locally quadratically to regular solutions. The algorithm and some numerical examples are presented. In addition, it is shown that the so-called Method III proposed by Friedland, Nocedal, and Overton [SIAM J. Numer. Anal., 24 (1987), pp. 634–667] for solving IEP may be constructed similarly to the method presented here.     

Convergence of Fixed Point Iteration for Modified Restoration Problems

The proof of the global and linear convergence of a fixed point iteration method for restoration, as well as an estimate for the rate of convergence have been discussed by many researchers. We present the global and linear convergence of a fixed point iteration method for a modified restoration problem. In addition, we show the equivalence among four different iterative methods: half-quadratic regularization, iteration based on the Bregman distance, inverse scale space method and generalized Weiszfeld’s method.

Regular matrix transformations and rates of convergence of positive linear operators

Abstract This paper investigates the effects of matrix summability methods on the A-statistical approximation of sequences of positive linear operators defined on the space of all 2π-periodic and continuous functions on the whole real axis. The two main tools used in this paper are A-statistical convergence and the modulus of continuity. Keywords: Regular infinite matrices, A-statistical convergence, rates of A-statistical convergence, positive linear operators, the Korovkin theorem, modulus of continuity. Mathematics Subject Classification (2000): 41A25, 41A36     

Efficient iterative algorithms for bounding the inverse of a matrix

In this paper we are considering iterative methods for bounding the inverse of a matrix, which make use of interval arithmetic. We present a class of methods as a combination of ordinary Schulz's methods for only approximating the inverse matrix (see [3]) and of well-known interval Schulz's methods (see [1]). Two convergence theorems are proved. Our methods are shown to be asymptotically of the same order of convergence as the ordinary Schulz's methods being part of them. Therefore we are getting considerably more efficient interval methods by our approach than by the classical interval Schulz's methods in [1] or [5]. A numerical example is given.     

Note To The Mixed-Type Splitting Iterative Method For The Positive Real Linear System

In [5] a new iterative method is given for the linear system of equations Au=b , where A is large, sparse and nonsymmetrical and A^{\rm T}+A is symmetric and positive definite (SPD) or equivalently A is positive real. The new iterative method is based on a mixed-type splitting of the matrix A and is called the mixed-type splitting iterative method. The iterative method contains an auxiliary matrix D_1 that is restricted to be symmetric. In this note, the auxiliary matrix is allowed to be more general and it is shown that by proper choice of D 1 , the new iterative method is still convergent. It is also shown that by special choice of D_{1} , the new iterative method becomes the well-known (point) accelerated overrelaxation (AOR) [1] method. Hence, it is shown that the (point) AOR method applied to the positive real system is convergent under the proper choice of the overrelaxation parameters y and .     

Solutions to the generalized Sylvester matrix equations by a singular value decomposition

In this paper,solutions to the generalized Sylvester matrix equations AX-XF=BY and MXN-X=TY with A,M∈Rn×n,B,T∈Rn×n,F,N∈Rp×p and the matrices N,F being in companion form,are established by a singular value decomposition of a matrix with dimensions n×(n pr).The algorithm proposed in this paper for the euqation AX-XF=BY does not require the controllability of matrix pair(A,B)andthe restriction that A,F do not have common eigenvalues.Since singular value decomposition is adopted,the algorithm is numerically stable and may provide great convenience to the computation of the solution to these equations,and can perform important functions in many design problems in control systems theory.     

A note on Wilkinson's iterative refinement of solution with automatic step-size control

In a more recent paper [X. Wu and Y.L. Fang, Wilkinson's iterative refinement of solution with automatic step-size control for linear system of equations, Appl. Math. Comput. 193 (2007), pp. 506–513], the authors proposed an iterative improvement of solution with automatic step-size control for a linear system of algebraic equations. The convergence analysis of the iterative procedure is shown for both stationary and non-stationary iterative formulas, based on the accurate coefficient matrix A and its inverse. However, in each iteration, A is approximated by the LU decomposition in floating-point arithmetic, and then its inverse is also approximated by a matrix B, although the role of B is realized by solving something like Az=r from the LU factorization of A. This point should be addressed that usually BA is not equal to an identity matrix I, in particular, when A is ill-conditioned. Therefore, in this paper, a supplementary convergence analysis is presented based on the approximation.     

The accelerated overrelaxation quadrant interlocking iterative method

In this paper we use a new splitting of the matrix A of the linear system A x = b introduced in [1] and we present a new version of the AOR method, more suitable for parallel processing, which involves explicit evaluation of 2 × 2 blocks.

We also obtain several convergence conditions for this new method, when the matrix A of (1.1) belongs to different classes of matrices. Some results, given in [1], are also improved and generalised.     

On the Solution of Boundary Value Problems by Using Fast Generalized Approximate Inverse Banded Matrix Techniques

A class of finite difference schemes in conjunction with approximate inverse banded matrix techniques based on the concept of LU-type factorization procedures is introduced for computing fast explicit approximate inverses. Explicit preconditioned iterative schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of banded linear systems. A theorem on the rate of convergence and estimates of the computational complexity required to reduce the L-norm of the error is presented. Applications of the method on linear and non-linear systems are discussed and numerical results are given.     

Root-finding by expansion with independent constraints

Elimination methods are highly effective for the solution of linear and nonlinear systems of equations, but reversal of the elimination principle can be beneficial as well: competent incorporation of additional independent constraints and variables or more generally immersion of the original computational problem into a larger task, defined by a larger number of independent constraints and variables can improve global convergence of iterative algorithms, that is their convergence from the start. A well known example is the dual linear and nonlinear programming, which enhances the power of optimization algorithms. We believe that this is just an ad hoc application of general Principle of Expansion with Independent Constraints; it should be explored systematically for devising iterative algorithms for the solution of equations and systems of equations and for optimization. At the end of this paper we comment on other applications and extensions of this principle.Presently we show it at work for the approximation of a single zero of a univariate polynomial p of a degree n. Empirical global convergence of the known algorithms for this task is much weaker than that of the algorithms for all n zeros, such as Weierstrass–Durand–Kerner’s root-finder, which reduces its root-finding task to Viète’s (Vieta’s) system of n polynomial equations with n unknowns. We adjust this root-finder to the approximation of a single zero of p, preserve its fast global convergence and decrease the number of arithmetic operations per iteration from quadratic to linear. Together with computing a zero of a polynomial p, the algorithm deflates this polynomial as by-product, and then could be reapplied to the quotient to approximate the next zero of p. Alternatively by using m processors that exchange no data, one can concurrently approximate up to m zeros of p. Our tests confirm the efficiency of the proposed algorithms.Technically our root-finding boils down to computations with structured matrices, polynomials and partial fraction decompositions. Our study of these links can be of independent interest; e.g., as by-product we express the inverse of a Sylvester matrix via its last column, thus extending the celebrated result of Gohberg and Sementsul (1972) [22] from Toeplitz to Sylvester matrix inverses.