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.     

Calculating the eigenvalues of the Sturm-Liouville problem with a fractal indefinite weight

An efficient method is proposed for calculating the eigenvalues of the boundary value problem ?y″ ? λρy = 0, y(0) = y(1) = 0, where ρ ? \(W_2^{^\circ - 1} \) [0, 1] is the generalized derivative of a self-similar function P ? L ₂[0, 1].     

Generating equations approach for quadratic matrix equations

We show how Van Loan's method for annulling the (2,1) block of skew‐Hamiltonian matrices by symplectic‐orthogonal similarity transformation generalizes to general matrices and provides a numerical algorithm for solving the general quadratic matrix equation: For skew‐Hamiltonian matrices we find their canonical form under a similarity transformation and find the class of all symplectic‐orthogonal similarity transformations for annulling the (2,1) block and simultaneously bringing the (1,1) block to Hessenberg form. We present a structure‐preserving algorithm for the solution of continuous‐time algebraic Riccati equation. Unlike other methods in the literature, the final transformed Hamiltonian matrix is not in Hamiltonian–Schur form. Three applications are presented: (a) for a special system of partial differential equations of second order for a single unknown function, we obtain the matrix of partial derivatives of second order of the unknown function by only algebraic operations and differentiation of functions; (b) for a similar transformation of a complex matrix into a symmetric (and three‐diagonal) one by applying only finite algebraic transformations; and (c) for finite‐step reduction of the eigenvalues–eigenvectors problem of a Hermitian matrix to the eigenvalues– eigenvectors problem of a real symmetric matrix of the same dimension. Copyright © 1999 John Wiley & Sons, Ltd.     

对称矩阵部分特征值之和的非光滑分析

本文研究n阶实对称矩阵A的前m项最大特征值之和fm（A）的非光滑分析问题．利用Ky－Fan的关于特征值之和的变分原理以及凸分析理论，得到了fm（A）的次梯度和方向导数的显式表达式．     

Solving symmetric indefinite systems in an interior-point method for linear programming

We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite augmented systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite normal equations that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.This work has been supported in part by National Science Foundation grants DDM-8908818 (Fourer) and CCR-8810107 (Mehrotra), and by a grant from GTE Laboratories (Mehrotra).     

Remarks on numerical ranges of operators in spaces with an indefinite metric

The numerical range of an operator on an indefinite inner product space (possibly infinite dimensional) is studied. In particular, operators having bounded numerical ranges are characterized, and the angle points of the numerical range and their connections with eigenvalues are described.

     

求解2×2块对称不定线性方程组迭代法的收敛性分析(英文)

本文研究求解系数矩阵为2×2块对称不定矩阵时的线性方程组,提出了一种新的分裂迭代法,并通过研究迭代矩阵的谱半径,详细讨论了新方法的收敛性.最后,我们也讨论了预条件矩阵特征根的几条性质.     

Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal

In this paper we describe an orthogonal similarity transformation for transforming arbitrary symmetric matrices into a diagonal-plus-semiseparable matrix, where we can freely choose the diagonal. Very recently an algorithm was proposed for transforming arbitrary symmetric matrices into similar semiseparable ones. This reduction is strongly connected to the reduction to tridiagonal form. The class of semiseparable matrices can be considered as a subclass of the diagonalplus- semiseparable matrices. Therefore we can interpret the proposed algorithm here as an extension of the reduction to semiseparable form. A numerical experiment is performed comparing thereby the accuracy of this reduction algorithm with respect to the accuracy of the traditional reduction to tridiagonal form, and the reduction to semiseparable form. The experiment indicates that all three reduction algorithms are equally accurate. Moreover it is shown in the experiments that asymptotically all the three approaches have the same complexity, i.e. that they have the same factor preceding the n³ term in the computational complexity. Finally we illustrate that special choices of the diagonal create a specific convergence behavior. The research was partially supported by the Research Council K.U.Leuven, project OT/05/40 (Large rank structured matrix computations), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors.     

Nonnegative rank of a matrix with one negative eigenvalue

We show that a rank-three symmetric matrix with exactly one negative eigenvalue can have arbitrarily large nonnegative rank.     

On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix

Let $ \tilde \lambda Let be an approximate eigenvalue of multiplicity m _c = n − r of an n × n real symmetric tridiagonal matrix T having nonzero off-diagonal entries. A fast algorithm is proposed (and numerically tested) for deleting m _c rows of T− I so that the condition number of the r × n matrix B formed of the remaining r rows is as small as possible. A special basis of m _c vectors with local supports is constructed for the subspace kerB. These vectors are approximate eigenvectors of T corresponding to . Another method for deleting m _c rows of T− I is also proposed. This method uses a rank-revealing QR decomposition; however, it requires a considerably larger number of arithmetic operations. For the latter algorithm, the condition number of B is estimated, and orthogonality estimates for vectors of the special basis of kerB are derived. Original Russian Text ? S.K. Godunov, A.N. Malyshev, 2008, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2008, Vol. 48, No. 7, pp. 1156–1166.     

On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix

The upper bound of maximal entries in the principal eigenvector of a simple undirected connected graph is investigated in [Linear Algebra Appl. 310 (2000) 129]. We further investigate the maximal entry y^max_p in the principle eigenvector of symmetric nonnegative matrix with zero trace and obtain both sharp upper and lower bounds on the y^max_p. Particularly, this result answers the open question given in the above-mentioned reference     

Bezoutian矩阵的一致逼近形式

借助闭区间上的连续函数可以用Bernstein 多项式一致逼近这一事实,将多项式对所生成的经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵推广到C [0,1]上函数对所对应的情形,给出了 Bezoutian 矩阵一致逼近形式的定义,并且得到如下结论：给出了经典 Bezoutian 矩阵的 Barnett 型分解公式和三角分解公式的一致逼近形式;提供了经典Bezoutian 矩阵和Bernstein Bezoutian 矩阵的一致逼近形式的两类算法;得到了上述两种矩阵的一致逼近形式中元素间的两个恒等关系式。最后,利用数值实例对恒等关系式进行验证,结果表明两类算法是有效的。     

Computing the nearest diagonally dominant matrix

We solve the problem of minimizing the distance from a given matrix to the set of symmetric and diagonally dominant matrices. First, we characterize the projection onto the cone of diagonally dominant matrices with positive diagonal, and then we apply Dykstra's alternating projection algorithm on this cone and on the subspace of symmetric matrices to obtain the solution. We discuss implementation details and present encouraging preliminary numerical results. Copyright © 1999 John Wiley & Sons, Ltd.     

A method for separating nearly multiple eigenvalues for Hermitian matrix

In this paper, we propose a numerical method to verify for nearly multiple eigenvalues of a Hermitian matrix not being strictly multiple eigenvalues. From approximate eigenvalues computed, it seems to be difficult to distinguish whether they are strictly multiple eigenvalues or simple ones, and if they are very close each other, the verification method for simple eigenvalues may fail to enclose them separately, because of singularity of the system in the verification. There are several methods for enclosing multiple and nearly multiple eigenvalues (e.g., [Rump, Computational error bounds for multiple or nearly multiple eigenvalues, Linear Algebra Appl. 324 (2001) 209–226]), For such cases, there is no result to decide the enclosed eigenvalues are nearly multiple or strictly multiple, up to now. So, for enclosed eigenvalues, we propose a numerical method to separate nearly multiple eigenvalues.     

Stability analysis of time-varying switched systems via indefinite difference Lyapunov functions

Asymptotic stability of time-varying switched systems is investigated in this paper. The less conservative sufficient criteria for asymptotic stability of time-varying discrete-time switched systems are proposed via common indefinite difference Lyapunov functions and multiple indefinite difference Lyapunov functions introduced in this note, respectively. Common indefinite difference Lyapunov functions can be used to analyze stability of a switched system with asymptotic stable subsystems and arbitrary switching signal. Multiple indefinite difference Lyapunov functions can be used to investigate stability of a switched system with unstable subsystems and a given switching signal. The difference of the proposed Lyapunov function may be positive at some instants for an asymptotically stable subsystem. We compare these main results and illustrate the effectiveness of the obtained theorems by three numerical examples.     

Square indefinite LQ-problem: Existence of a unique solution

In this paper, we consider discrete-time systems. We study conditions under which there is a unique control that minimizes a general quadratic cost functional. The system considered is described by a linear time-invariant recurrence equation in which the number of inputs equals the number of states. The cost functional differs from the usual one considered in optimal control theory, in the sense that we do not assume that the weight matrices considered are semipositive definite. For both a finite planning horizon and an infinite horizon, necessary and sufficient solvability conditions are given. Furthermore, necessary and sufficient conditions are derived for the existence of a solution for an arbitrary finite planning horizon.The author dedicates this paper to the memory of his late grandfather Jacob Oosterwold.