Eigenfactor solution of the matrix Riccati equation--A continuous square root algorithm

This paper introduces a new algorithm for solving the matrix Riccati equation. Differential equations for the eigenvalues and eigenvectors of the solution matrix are developed in which their derivatives are expressed in terms of the eigenvalues and eigenvectors themselves and not as functions of the solution matrix. The solution of these equations yields, then, the time behavior of the eigenvalues and eigenvectors of the solution matrix. A reconstruction of the matrix itself at any desired time is immediately obtained through a trivial similarity transformation. This algorithm serves two purposes. First, being a square root solution, it entails all the advantages of square root algorithms such as nonnegative definiteness and accuracy. Secondly, it furnishes the eigenvalues and eigenvectors of the solution matrix continuously without resorting to the complicated route of solving the equation directly and then decomposing the solution matrix into its eigenvalues and eigenvectors. The algorithm which handles cases of distinct as well as multiple eigenvalues is tested on several examples. Through these examples it is seen that the algorithm is indeed more accurate than the ordinary one. Moreover, it is seen that the algorithm works in cases where the ordinary algorithm fails and even in cases where the closed-form solution cannot be computed as a result of numerical difficulties.     

A vector-multiplication dominated parallel algorithm for the computation of real eigenvalue spectra

In order to exploit effectively the power of array and vector processors for the numerical solution of linear algebraic problems it is desirable to express algorithms principally in terms of vector and matrix operations. Algorithms which manipulate vectors and matrices at component level are best suited for execution on single processor hardware. Often, however, it is difficult, if not impossible, to construct efficient versions of such algorithms which are suitable foe execution on parallwl hardware. A method for computing the eigenvalues of real unsymmetric matrices with real eigenvalue spectra is presented. The method is an extension of the one described in ref. [1]. The algorithm makes heavy use of vector inner product evaluations. The manipulation of individual components of vectors and matrices is kept to a minimum. Essentially, the method involves the construction of a sequence of biorthogonal transformation matrices the combined effect of which is to diagonalise the matrix. The eigenvalues of the matrix are diagonal elements of the final diagonalised form. If the eigenvectors of the matrix are also required the algorithm may be extended in a straightforward way. The effectiveness of the algorithm is demonstrated by an application of sequential version to several small matrices and some comments are made about the time complexity of the parallel version.     

First- and second-order eigensensitivities of matrices with distinct eigenvalues

Formulae for computation of the first- and second-order sensitivity matrices of the eigenvalues and eigenvectors of a matrix with distinct eigenvalues are derived using matrix calculus and the algebra of Kronecker products. The sensitivities of eigenvalues and eigenvectors to all elements of the matrix can thus be expressed by concise matrix equations.     

关于r-循环矩阵的开平方运算

当r=1时(此时r可省略),A为通常的循环矩阵。当r=0时,为文[3]中的上三角形Toeplitz矩阵。当r=-1时,为通常的反循环矩阵。 r-循环矩阵是一类很重要的特殊矩阵,它在数字图象处理、线性预测、自回归滤波器设计、计算机时序分析及工程计算等领域有着广泛的应用,近年来,对其特性及有关快速算法     

A computer program for non-linear curve fitting

Recently several techniques for non-linear curve fitting have been developed. The implementation of a non-linear curve fitting procedure is treated for mathematical models in which the linear and the nonlinear parameters are separable. The technique of Golub and Pereyra is used so that a minimization algorithm only for the non-linear parameters is needed. The minimization algorithm of Marquardt has been completed with an eigenvalue analysis. In order to reduce the computation steps the inverses of matrices of the form A + λI are calculated with the eigenvalues and eigenvectors of the matrix A. Of particular interest is the obtained convergence speed and the ease with which the method can be applied.     

Parallel computation of the eigenvalues of symmetric Toeplitz matrices through iterative methods

This paper presents a new procedure to compute many or all of the eigenvalues and eigenvectors of symmetric Toeplitz matrices. The key to this algorithm is the use of the “Shift–and–Invert” technique applied with iterative methods, which allows the computation of the eigenvalues close to a given real number (the “shift”). Given an interval containing all the desired eigenvalues, this large interval can be divided in small intervals. Then, the “Shift–and–Invert” version of an iterative method (Lanczos method, in this paper) can be applied to each subinterval. Since the extraction of the eigenvalues of each subinterval is independent from the other subintervals, this method is highly suitable for implementation in parallel computers. This technique has been adapted to symmetric Toeplitz problems, using the symmetry exploiting Lanczos process proposed by Voss [H. Voss, A symmetry exploiting Lanczos method for symmetric Toeplitz matrices, Numerical Algorithms 25 (2000) 377–385] and using fast solvers for the Toeplitz linear systems that must be solved in each Lanczos iteration. The method compares favourably with ScaLAPACK routines, specially when not all the spectrum must be computed.     

求解矩阵特征值和特征向量的PSO算法

提出一种基于粒子群优化算法的求解方法,将线性方程组的求解转化为无约束优化问题加以解决,采用粒子群优化算法求解矩阵特征值和特征向量。仿真实验结果表明,该方法求解精度高、收敛速度快,能够在10代左右收敛,可以有效获得任意矩阵的特征值和特征向量。     

Two algorithms for the parallel computation of eigenvalues and eigenvectors of large symmetric matrices using the ICL DAP

The implementation and evaluation of the performances on the ICL DAP of two algorithms for the parallel computation of eigenvalues and eigenvectors of moderately large real symmetric matrices of order N, where 64 < N 256, is reported. The first of the algorithms is a modified form of a Parallel Orthogonal Transformation algorithm proposed by Clint et al., which has already been implemented on the DAP for matrices of order N, where N < 65. The second, which has also been implemented on the DAP for matrices of order N, where N < 65, is Jacobi's algorithm, in the modified form proposed by Modi and Pryce. A comparison of the efficiency of the two algorithms for the solution of a variety of large matrices is given.     

极大代数意义下矩阵的特征值问题--一类离散事件动态系统运行周期的分析

在分析一类离散事件动态系统的运行周期及稳定性时,必须求解极大代数意义下矩阵的特征值及特征向量,这一直被认为是十分困难和繁复的工作.本文给出了求任一方阵特征值及特征向量的十分简单易行的方法以及有关的定理.     

基于二阶统计量的近场源四维参数联合估计

研究了一种基于二阶统计量的近场窄带信源频率、方位角、仰角和距离四维参数的联合估计算法。该算法利用中心对称的十字阵列,根据阵元输出构造二阶统计量矩阵,并结合这些矩阵的特点构造新矩阵,利用特征值和特征向量信息得到信源参数。该方法仅需计算6个二阶统计量矩阵就可以估计四维参数,此外参数自动配对。仿真结果表明该算法能准确地估计近场源参数。     

自洽场方法中广义本征值方程求解及其C++程序设计

本文研究自洽场方法中广义本征值方程求解的算法,并设计相应的C 程序来实现该算法。首先对重叠矩阵进行分解,并将广义本征值方程化为标准的本征值方程,再利用Householder变换将上一步变换所得的矩阵化为对称三对角矩阵,进而用QL方法求解这个三对角矩阵的本征值和本征矢量,从而得到自洽场方法中广义本征值方程的本征值和本征矢量。     

用神经网络计算矩阵特征值与特征向量

该文研究用神经网格求解一般实对称矩阵的全部特征向量的问题。详细讨论了网络的平均态度合的结构并建立了平衡态集合的构造定理。通过求解简单的一维微分方程求出了网络的解析表达式。这一表达式是由对称矩阵的特征值与特征向量表达的、因而非常清晰利用解的解析表达式分析了网络的解的全局渐近行为。提出了用一些单位向量作为网络初始值计算对称矩阵的全部特征值与特征向量的具体算法。     

Coupled principal component analysis

A framework for a class of coupled principal component learning rules is presented. In coupled rules, eigenvectors and eigenvalues of a covariance matrix are simultaneously estimated in coupled equations. Coupled rules can mitigate the stability-speed problem affecting noncoupled learning rules, since the convergence speed in all eigendirections of the Jacobian becomes widely independent of the eigenvalues of the covariance matrix. A number of coupled learning rule systems for principal component analysis, two of them new, is derived by applying Newton's method to an information criterion. The relations to other systems of this class, the adaptive learning algorithm (ALA), the robust recursive least squares algorithm (RRLSA), and a rule with explicit renormalization of the weight vector length, are established.     

改进的判别割及其在图像分割中的应用

谱聚类算法能在任意形状的样本空间上聚类且收敛于全局最优解,但判别割(Dcut)算法在计算正则化相似度矩阵及其特征向量时比较耗时,而基于子空间的Dcut(SDcut)算法则不稳定,为此,提出基于主成分分析(PCA)的Dcut算法(PCA-Dcut)。PCA-Dcut算法采用PCA算法计算相似度矩阵的前m个大的特征值对应的特征向量构造一个新的矩阵,然后采用构造的矩阵与相似度矩阵和拉普拉斯矩阵分别进行矩阵运算;接着通过计算获得一个m阶正则化相似度矩阵,并计算该矩阵的k个最大特征向量;最后使用构造的矩阵与这k个特征向量相乘获得最终用于分类的特征向量。PCA-Dcut算法能降低Dcut算法的计算复杂度。通过对人工合成数据集、UCI数据集和真实图像的仿真实验表明,PCA-Dcut算法的聚类准确率与Dcut等谱聚类算法相当,同时在分割图像时的运算速度约为Dcut的5.4倍,并具有比SDcut更快的速度和更好的性能。     

On the estimation of probability of error

This paper considers the problem of estimation of classification error in pattern recognition. A theorem is presented to obtain the changes in the eigenvalues and eigenvectors of matrices of the form S₂⁻¹ S₁, when there are changes of first order of smallness in the real symmetric matrices S_i, I = 1, 2. Based on this theory a computational algorithm is developed for the estimation of classification error of Fisher classifier, using leaving groups out method.     

最优二次型渐近设计法及其应用

本文探讨了用闭环系统预期特征值及特征向量确定加权阵,及依靠最优调节器的渐近特性确定Riccati代数方程迭代解起始阵的方法.据此提出了线性系统最优二次型渐近设计法,编写了设计程序,实验结果表明方法是可行的.     

Multivariate Polynomial System Solving Using Intersections of Eigenspaces

The solutions of a polynomial system can be computed using eigenvalues and eigenvectors of certain endomorphisms. There are two different approaches, one by using the (right) eigenvectors of the representation matrices, one by using the (right) eigenvectors of their transposed ones, i.e. their left eigenvectors. For both approaches, we describe the common eigenspaces and give an algorithm for computing the solution of the algebraic system. As a byproduct, we present a new method for computing radicals of zero-dimensional ideals.     

Partial solution of large symmetric generalized eigenvalue problems by nonlinear optimization of a modified Rayleigh quotient

A method is presented to solve numerically the lowest (or highest) eigenvalues and eigenvectors of the symmetric generalized eigenvalue problem. The technique proposed is iterative, does not transform the original matrices and yields eigencharacteristics in sequence, even for repeated eigenvalues. It is based on a nonlinear optimization of an unconstrained penalty function obtained from a generalization of the Rayleigh quotient. In addition, when the normality constraint is imposed, the eigenvectors are obtained by a sequence of solutions to linear equations, all with the same matrix. Examples demonstrate the validity of the method.     

求解矩阵特征值及特征向量的新方法

提出一种基于进化策略求解矩阵特征值及特征向量的新方法。该方法在进化过程中通过重组、突变、选择对个体进行训练学习,向最优解逼近。当达到预先给定的误差时,程序终止,得到最优解。实验结果表明,与传统方法相比,该方法的收敛速度较快,求解精度提高了10倍。该算法能够快速有效地获得任意矩阵对应的特征值及特征向量。     

基于融合邻域寻优与θ-PSO算法的矩阵特征值求解

提出一种融合邻域寻优与θ-PSO算法的矩阵特征值求解新方法,将矩阵特征值的求解问题转化为最优化问题。与需要多次运行程序分别求解不同范围的特征值算法相比,该方法可以一次性求出矩阵的全部特征根。仿真实验表明,该算法编程实现方便,对于不同类型的矩阵均可以应用,求解精度高,收敛速度快,大概在10~15代左右就可以收敛,完全可以满足工程实践运算中对精度和速度的要求。