Finite iterative solutions to coupled Sylvester-conjugate matrix equations

This paper is concerned with solutions to the so-called coupled Sylveter-conjugate matrix equations, which include the generalized Sylvester matrix equation and coupled Lyapunov matrix equation as special cases. An iterative algorithm is constructed to solve this kind of matrix equations. By using the proposed algorithm, the existence of a solution to a coupled Sylvester-conjugate matrix equation can be determined automatically. When the considered matrix equation is consistent, it is proven by using a real inner product in complex matrix spaces as a tool that a solution can be obtained within finite iteration steps for any initial values in the absence of round-off errors. Another feature of the proposed algorithm is that it can be implemented by using original coefficient matrices, and does not require to transform the coefficient matrices into any canonical forms. The algorithm is also generalized to solve a more general case. Two numerical examples are given to illustrate the effectiveness of the proposed methods.     

Finite iterative method for solving coupled Sylvester-transpose matrix equations

This paper is concerned with solutions to the so-called coupled Sylvester-transpose matrix equations, which include the generalized Sylvester matrix equation and Lyapunov matrix equation as special cases. By extending the idea of conjugate gradient method, an iterative algorithm is constructed to solve this kind of coupled matrix equations. When the considered matrix equations are consistent, for any initial matrix group, a solution group can be obtained within finite iteration steps in the absence of roundoff errors. The least Frobenius norm solution group of the coupled Sylvester-transpose matrix equations can be derived when a suitable initial matrix group is chosen. By applying the proposed algorithm, the optimal approximation solution group to a given matrix group can be obtained by finding the least Frobenius norm solution group of new general coupled matrix equations. Finally, a numerical example is given to illustrate that the algorithm is effective.     

Iterative algorithms for solving a class of complex conjugate and transpose matrix equations

This paper is concerned with iterative solutions to a class of complex matrix equations, which include some previously investigated matrix equations as special cases. By applying the hierarchical identification principle, an iterative algorithm is constructed to solve this class of matrix equations. A sufficient condition is presented to guarantee that the proposed algorithm is convergent for an arbitrary initial matrix with a real representation of a complex matrix as tools. By using some properties of the real representation, a convergence condition that is easier to compute is also given in terms of original coefficient matrices. A numerical example is employed to illustrate the effectiveness of the proposed methods.     

基于梯度的Sylvester共轭矩阵方程的迭代解

本文提出了一种基于梯度的Sylvester共轭矩阵方程的迭代算法.通过引入一个松弛参数和采用递阶辨识原理,构造一个迭代算法求解Sylvester矩阵方程.通过应用复矩阵的实数表达以及实数表示的一些性质,收敛性分析表明在一定假设条件下,对于任意初始值,迭代方法均收敛到精确解,数值算例也表明了所给方法的有效性.     

On a relaxed SOR-method applied to nonsymmetric linear systems

Nonsymmetric linear systems are by far not as common as syemmtric ones but nevertheless systems with nonsymmetric matrices appear, e. g., in the numerical solution of the biharmonic equation, the computation of splines or the solution of some special integral equations. The SOR-method applied to linear systems X = BX + C with skew-symmetric matrix B is studied. Described is a region in the complex plane which contains the eigenvalues of the SOR-operator. Using this information a relaxed SOR-method is proposed; bounds for the spectral radius of the iteration operator are derived. The advantage is that the values of the corresponding iteration parameters can be directly calculated from the norm of the given matrix.     

Iterative solutions to the extended Sylvester-conjugate matrix equations

This paper is concerned with iterative solutions to a class of complex matrix equations. By applying the hierarchical identification principle, an iterative algorithm is constructed to solve this class of complex matrix equations. The range of the convergence factor is given to guarantee that the proposed algorithm is convergent for arbitrary initial matrix by applying a real representation of a complex matrix as a tool. By using some properties of the real representation, a sufficient convergence condition that is easier to compute is also given by original coefficient matrices. Two numerical examples are given to illustrate the effectiveness of the proposed methods.     

广义耦合Sylvester矩阵方程的对称-反对称最小二乘解

本文主要研究极小残差问题‖(A1XB1+C1YD1A2XB2+C2YD2)-(M1M2)‖=min关于X对称-Y反对称解的迭代算法.本文首先给出等价于极小残差问题的规范方程,然后,提出求解此规范方程的对称-反对称解的迭代算法.在不考虑舍入误差的情况下,任取一个初始的对称-反对称矩阵对(X0,Y0),该算法都可以在有限步内求得该极小残差问题的对称-反对称解.最后讨论该问题的极小范数对称-反对称解.     

Solving a large dense linear system by adaptive cross approximation

An efficient algorithm for the direct solution of a linear system associated with the discretization of boundary integral equations (in two dimensions) is described without having to compute the complete matrix of the linear system. This algorithm is based on the unitary-weight representation, for which a new construction based on adaptive cross approximation is proposed. This low rank approximation uses only a small part of the entries to construct the adaptive cross representation, and therefore the linear system can be solved efficiently.     

解不等式约束优化的新的序列线性方程组方法

提出一种新的序列线性方程组(SSLE)算法解非线性不等式约束优化问题.在算法的每步迭代,子问题只需解四个简化的有相同的系数矩阵的线性方程组.证明算法是可行的,并且不需假定聚点的孤立性、严格互补条件和积极约束函数的梯度的线性独立性得到算法的全局收敛性.在一定条件下,证明算法的超线性收敛率.     

Iterative solutions to coupled Sylvester-transpose matrix equations

This note studies the iterative solutions to the coupled Sylvester-transpose matrix equation with a unique solution. By using the hierarchical identification principle, an iterative algorithm is presented for solving this class of coupled matrix equations. It is proved that the iterative solution consistently converges to the exact solution for any initial values. Meanwhile, sufficient conditions are derived to guarantee that the iterative solutions given by the proposed algorithm converge to the exact solution for any initial matrices. Finally, a numerical example is given to illustrate the efficiency of the proposed approach.     

连续Sylvester矩阵方程求解的分裂迭代算法

有效求解连续的Sylvester矩阵方程对于科学和工程计算有着重要的应用价值,因此该文提出了一种可行的分裂迭代算法.该算法的核心思想是外迭代将连续Sylvester矩阵方程的系数矩阵分裂为对称矩阵和反对称矩阵,内迭代求解复对称矩阵方程.相较于传统的分裂算法,该文所提出的分裂迭代算法有效地避免了最优迭代参数的选取,并利用了复对称方程组高效求解的特点,进而提高了算法的易实现性、易操作性.此外,从理论层面进一步证明了该分裂迭代算法的收敛性.最后,通过数值算例表明分裂迭代算法具有良好的收敛性和鲁棒性,同时也证实了分裂迭代算法的收敛性很大程度依赖于内迭代格式的选取.     

The Inverse Problem Method on the Half-Line and a Nested System of Riccati Equations

A mixed problem for the nonlinear Bogoyavlenskii system on the half-line is studied by the inverse problem method. The solution of the mixed problem is reduced to the solution of the inverse spectral problem of recovering a forth-order differential operator on the half-line from the Weyl matrix. We derive evolution equations for the elements of the Weyl matrix and give an algorithm for the solution of the mixed problem. Evolution equations of the elements of the Weyl matrix are nonlinear. It is shown that they can be reduced to a nested system of three successively solvable matrix Riccati equations.     

矩阵最小二乘问题的迭代求解及其在机器翻译中的应用

研究一类线性矩阵方程最小二乘问题的迭代法求解,利用目标函数与矩阵迹之间的关系构造了矩阵形式的"梯度"下降法迭代格式,推广了向量形式的经典"梯度"下降法,并引入了两个矩阵之间的弱正交性来刻画迭代修正量的特点.作为本文算法的应用,给出了机器翻译优化问题的一种迭代求解格式.     

A shift-splitting hierarchical identification method for solving Lyapunov matrix equations

In the present paper, we propose a hierarchical identification method (SSHI) for solving Lyapunov matrix equations, which is based on the symmetry and skew-symmetry splitting of the coefficient matrix. We prove that the iterative algorithm consistently converges to the true solution for any initial values with some conditions, and illustrate that the rate of convergence of the iterative solution can be enhanced by choosing the convergence factors appropriately. Furthermore, we show that the method adopted can be easily extended to study iterative solutions of other matrix equations, such as Sylvester matrix equations. Finally, we test the algorithms and show their effectiveness using numerical examples.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Iterative solutions to the Kalman-Yakubovich-conjugate matrix equation

Two operations are introduced for complex matrices. In terms of these two operations an infinite series expression is obtained for the unique solution of the Kalman-Yakubovich-conjugate matrix equation. Based on the obtained explicit solution, some iterative algorithms are given for solving this class of matrix equations. Convergence properties of the proposed algorithms are also analyzed by using some properties of the proposed operations for complex matrices.     

AN EFFECT ITERATION ALGORITHM FOR NUMERICAL SOLUTION OF DISCRETE HAMILTON-JACOBIBELLMAN EQUATIONS

§1Introduction ConsidertheHamilton-Jacobi-Bellmanequation max1≤v≤m[A(v)u(x)-f(v)(x)]=0,x∈Ω(1.1)withtheboundarycondition u(x)=0,x∈Ω(1.2)whereΩisabounded,smoothdomaininEuclideanspaceRd,d∈N;f(v)(x)aregiven functionsfromC2(Ω);A(v)aresecond-orderuniformlyellipticoperatorsoftheform A(v)=-d i,j=1a(v)ij2xixj+di=1b(v)ixi+c(v).(1.3)Intheaboveexpression(1.3)therearecoefficientsa(v)ij,b(v)i,c(v)∈C2(Ω)satisfying,forall1≤v≤m,a(v)ij(x)=a(v)ji(x),1≤i,j≤d,c(v)≥c0≥0,x∈Ω,a…     

Generalization of Exp-function and other standard function methods

Exp-function and other standard function methods for solving nonlinear differential equations are generalized in this paper. An analytical criterion determining if a solution can be expressed in a form comprising standard functions is derived. New computational algorithm for automatic identification of the structure of the solution is constructed. The algorithm provides information if the solution can be expressed as a sum of standard functions, a ratio of sums of standard functions, or even a more complex algebraic form involving standard functions. Several examples are used to illustrate the proposed concept.     

Weighted and deflated global GMRES algorithms for solving large Sylvester matrix equations

The solution of a large-scale Sylvester matrix equation plays an important role in control and large scientific computations. In this paper, we are interested in the large Sylvester matrix equation with large dimensionA and small dimension B, and a popular approach is to use the global Krylov subspace method. In this paper, we propose three new algorithms for this problem. We first consider the global GMRES algorithm with weighting strategy, which can be viewed as a precondition method. We present three new schemes to update the weighting matrix during iterations. Due to the growth of memory requirements and computational cost, it is necessary to restart the algorithm effectively. The deflation strategy is efficient for the solution of large linear systems and large eigenvalue problems; to the best of our knowledge, little work is done on applying deflation to the (weighted) global GMRES algorithm for large Sylvester matrix equations. We then consider how to combine the weighting strategy with deflated restarting, and propose a weighted global GMRES algorithm with deflation for solving large Sylvester matrix equations. In particular, we are interested in the global GMRES algorithm with deflation, which can be viewed as a special case when the weighted matrix is chosen as the identity. Theoretical analysis is given to show rationality of the new algorithms. Numerical experiments illustrate the numerical behavior of the proposed algorithms.

     

Truncated Newton method for sparse unconstrained optimization using automatic differentiation

When solving large complex optimization problems, the user is faced with three major problems. These are (i) the cost in human time in obtaining accurate expressions for the derivatives involved; (ii) the need to store second derivative information; and (iii), of lessening importance, the time taken to solve the problem on the computer. For many problems, a significant part of the latter can be attributed to solving Newton-like equations. In the algorithm described, the equations are solved using a conjugate direction method that only needs the Hessian at the current point when it is multiplied by a trial vector. In this paper, we present a method that finds this product using automatic differentiation while only requiring vector storage. The method takes advantage of any sparsity in the Hessian matrix and computes exact derivatives. It avoids the complexity of symbolic differentiation, the inaccuracy of numerical differentiation, the labor of finding analytic derivatives, and the need for matrix store. When far from a minimum, an accurate solution to the Newton equations is not justified, so an approximate solution is obtained by using a version of Dembo and Steihaug's truncated Newton algorithm (Ref. 1).This paper was presented at the SIAM National Meeting, Boston, Massachusetts, 1986.