基于Lanczos方法的结构动力学灵敏度分析

利用数学理论得到结构动力学重特征值的灵敏度表达式,从而解决了奇异性问题.然后,为降低计算工作量,基于Lanczos方法得到降阶的结构系统,从而得到降阶的灵敏度分析近似解.用一个算例证明的方法正确性.     

代数数极小多项式的近似重构

给出了代数数极小多项式近似重构的误差控制条件,进而基于同步整数关系探测算法SIRD,得到一个从代数数近似值重构其准确极小多项式的完备的新算法,从而将“采用近似计算获得准确值”这一思想的适用范围从有理数扩展到代数数.     

三阶微分方程边值问题的高效数值算法

基于再生核空间法提出了一个高效的数值算法来解决三阶微分方程的边值问题.利用再生性以及正交基的构造,得到了模型精确解的级数表示形式,并通过截断级数获得了其近似解.通过数值算例说明了此方法的有效性.     

计算最小奇异组的一个精化调和 Lanczos双对角化方法

在很多实际应用中需要计算大规模矩阵的若干个最小奇异组.调和投影方法是计算内部特征对的常用方法,其原理可用于求解大规模奇异值分解问题.本文证明了,当投影空间足够好时,该方法得到的近似奇异值收敛,但近似奇异向量可能收敛很慢甚至不收敛.根据第二作者近年来提出的精化投影方法的原理,本文提出一种精化的调和Lanczos双对角化方法,证明了它的收敛性.然后将该方法与Sorensen提出的隐式重新启动技术相结合,开发出隐式重新启动的调和Lanczos双对角化算法(IRHLB)和隐式重新启动的精化调和Lanczos双对角化算法(IRRHLB).位移的合理选取是算法成功的关键之一,本文对精化算法提出了一种新的位移策略,称之为"精化调和位移".理论分析表明,精化调和位移比IRHLB中所用的调和位移要好,且可以廉价可靠地计算出来.数值实验表明,IRRHLB比IRHLB要显著优越,而且比目前常用的隐式重新启动的Lanczos双对角化方法(IRLB)和精化算法IRRLB更有效.     

一类Lyapunov矩阵方程的双反对称解的迭代算法

基于求线性代数方程组的共轭梯度法的思想,建立一种求Lyapunov矩阵方程的双反对称解的迭代算法,对任意给定的初始双反对称矩阵,算法能够在有限步迭代计算后得到矩阵方程的极小范数双反对称解,同时在上述解集中也可得出指定矩阵的最佳逼近双反称矩阵.数值算例表明,迭代算法是有效的.     

一种新的逼近精确罚函数的罚函数及性质

针对可微非线性规划问题提出了一个新的逼近精确罚函数的罚函数形式,给出了近似逼近算法与渐进算法,并证明了近似算法所得序列若有聚点,则必为原问题最优解. 在较弱的假设条件下,证明了算法所得的极小点列有界,且其聚点均为原问题的最优解,并得到在Mangasarian-Fromovitz约束条件下,经过有限次迭代所得的极小点为可行点.     

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

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

求解病态线性方程组的收缩Lanczos方法

Lanczos方法是求解大型线性方程组的常用方法.遗憾的是,在Lanczos过程中通常会发生算法中断或数值不稳定的情况.将给出求解大型对称线性方程组的收缩Lanczos方法,即DLanczos方法.新算法将采用增广子空间技术,在Lanczos过程中向Krylov子空间加入少量绝对值较小的特征值所对应的特征向量进行收缩.数值实验表明,新算法比Lanczos方法收敛速度更快,并且适合求解病态对称线性方程组.     

求解大规模Hamilton矩阵特征问题的辛Lanczos算法的误差分析

对求解大规模稀疏Hamilton矩阵特征问题的辛Lanczos算法给出了舍入误差分析.分析表明辛Lanczos算法在无中断时,保Hamilton结构的限制没有破坏非对称Lanczos算法的本质特性.本文还讨论了辛Lanczos算法计算出的辛Lanczos向量的J一正交性的损失与Ritz值收敛的关系.结论正如所料,当某些Ritz值开始收敛时.计算出的辛Lanczos向量的J-正交性损失是必然的.以上结果对辛Lanczos算法的改进具有理论指导意义.     

近似函数高阶导数的高精度积分逼近方法

主要研究稳定计算近似函数的高阶导数的积分逼近方法,方法因由Lanczos提出故也称为Lanczos算法.利用Legendre多项式的正交性,提出了一类逼近近似函数高阶导数的高精度积分方法,即构造出一系列积分算子Dn,h(m)去逼近噪声函数的高阶导数,且这些积分算子具有O(δ(2n+2)/(2n+m+2))的收敛速度,其中δ为近似函数的噪声水平.数值模拟结果表明提出的方法是稳定而有效的.     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling

Recently, Freund and Nachtigal proposed the quasi-minimal residual algorithm (QMR) for solving general nonsingular non-Hermitian linear systems. The method is based on the Lanczos process, and thus it involves matrix—vector products with both the coefficient matrix of the linear system and its transpose. Freund developed a variant of QMR, the transpose-free QMR algorithm (TFQMR), that only requires products with the coefficient matrix. In this paper, the use of QMR and TFQMR for solving singular systems is explored. First, a convergence result for the general class of Krylov-subspace methods applied to singular systems is presented. Then, it is shown that QMR and TFQMR both converge for consistent singular linear systems with coefficient matrices of index 1. Singular systems of this type arise in Markov chain modeling. For this particular application, numerical experiments are reported.     

QMR: a quasi-minimal residual method for non-Hermitian linear systems

Summary The biconjugate gradient (BCG) method is the natural generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. In this paper, we present a novel BCG-like approach, the quasi-minimal residual (QMR) method, which overcomes the problems of BCG. An implementation of QMR based on a look-ahead version of the nonsymmetric Lanczos algorithm is proposed. It is shown how BCG iterates can be recovered stably from the QMR process. Some further properties of the QMR approach are given and an error bound is presented. Finally, numerical experiments are reported.This work was supported in part by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).     

A linear system solver based on a modified Krylov subspace method for breakdown recovery

Despite its usefulness in solving eigenvalue problems and linear systems of equations, the nonsymmetric Lanczos method is known to suffer from a potential breakdown problem. Previous and recent approaches for handling the Lanczos exact and near-breakdowns include, for example, the look-ahead schemes by Parlett-Taylor-Liu [23], Freund-Gutknecht-Nachtigal [9], and Brezinski-Redivo Zaglia-Sadok [4]; the combined look-ahead and restart scheme by Joubert [18]; and the low-rank modified Lanczos scheme by Huckle [17]. In this paper, we present yet another scheme based on a modified Krylov subspace approach for the solution of nonsymmetric linear systems. When a breakdown occurs, our approach seeks a modified dual Krylov subspace, which is the sum of the original subspace and a new Krylov subspaceK _m (w _j ,A ^T ) wherew _j is a newstart vector (this approach has been studied by Ye [26] for eigenvalue computations). Based on this strategy, we have developed a practical algorithm for linear systems called the MLAN/QM algorithm, which also incorporates the residual quasi-minimization as proposed in [12]. We present a few convergence bounds for the method as well as numerical results to show its effectiveness.Research supported by Natural Sciences and Engineering Research Council of Canada.     

Iterative methods for solvingAx=b,GMRES/FOM versus QMR/BiCG

We study the convergence of the GMRES/FOM and QMR/BiCG methods for solving nonsymmetric systems of equationsAx=b. We prove, in exact arithmetic, that any type of residual norm convergence obtained using BiCG can also be obtained using FOM but on a different system of equations. We consider practical comparisons of these procedures when they are applied to the same matrices. We use a unitary invariance shared by both methods, to construct test matrices where we can vary the nonnormality of the test matrix by variations in simplified eigenvector matrices. We used these test problems in two sets of numerical experiments. The first set of experiments was designed to study effects of increasing nonnormality on the convergence of GMRES and QMR. The second set of experiments was designed to track effects of the eigenvalue distribution on the convergence of QMR. In these tests the GMRES residual norms decreased significantly more rapidly than the QMR residual norms but without corresponding decreases in the error norms. Furthermore, as the nonnormality ofA was increased, the GMRES residual norms decreased more rapidly. This led to premature termination of the GMRES procedure on highly nonnormal problems. On the nonnormal test problems the QMR residual norms exhibited less sensitivity to changes in the nonnormality. The convergence of either type of procedure, as measured by the error norms, was delayed by the presence of large or small outliers and affected by the type of eigenvalues, real or complex, in the eigenvalue distribution ofA. For GMRES this effect can be seen only in the error norm plots.In honor of the 70th birthday of Ted RivlinThis work was supported by NSF grant GER-9450081.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

New results on the convergence of the conjugate gradient method

This paper is concerned with proving theoretical results related to the convergence of the conjugate gradient (CG) method for solving positive definite symmetric linear systems. Considering the inverse of the projection of the inverse of the matrix, new relations for ratios of the A‐norm of the error and the norm of the residual are provided, starting from some earlier results of Sadok (Numer. Algorithms 2005; 40 :201–216). The proofs of our results rely on the well‐known correspondence between the CG method and the Lanczos algorithm. Copyright © 2008 John Wiley & Sons, Ltd.     

Preserving geometric properties of the exponential matrix by block Krylov subspace methods

Given a large square real matrix A and a rectangular tall matrix Q, many application problems require the approximation of the operation . Under certain hypotheses on A, the matrix preserves the orthogonality characteristics of Q; this property is particularly attractive when the associated application problem requires some geometric constraints to be satisfied. For small size problems numerical methods have been devised to approximate while maintaining the structure properties. On the other hand, no algorithm for large A has been derived with similar preservation properties. In this paper we show that an appropriate use of the block Lanczos method allows one to obtain a structure preserving approximation to when A is skew-symmetric or skew-symmetric and Hamiltonian. Moreover, for A Hamiltonian we derive a new variant of the block Lanczos method that again preserves the geometric properties of the exact scheme. Numerical results are reported to support our theoretical findings, with particular attention to the numerical solution of linear dynamical systems by means of structure preserving integrators. AMS subject classification (2000) 65F10, 65F30, 65D30     

Inverse subspace problems with applications

Given a square matrix A, the inverse subspace problem is concerned with determining a closest matrix to A with a prescribed invariant subspace. When A is Hermitian, the closest matrix may be required to be Hermitian. We measure distance in the Frobenius norm and discuss applications to Krylov subspace methods for the solution of large‐scale linear systems of equations and eigenvalue problems as well as to the construction of blurring matrices. Extensions that allow the matrix A to be rectangular and applications to Lanczos bidiagonalization, as well as to the recently proposed subspace‐restricted SVD method for the solution of linear discrete ill‐posed problems, also are considered.Copyright © 2013 John Wiley & Sons, Ltd.     

Lanczos,Householder transformations,and implicit deflation for fast and reliable dominant singular subspace computation

Many applications, such as subspace‐based models in information retrieval and signal processing, require the computation of singular subspaces associated with the k dominant, or largest, singular values of an m×n data matrix A, where k?min(m,n). Frequently, A is sparse or structured, which usually means matrix–vector multiplications involving A and its transpose can be done with much less than ??(mn) flops, and A and its transpose can be stored with much less than ??(mn) storage locations. Many Lanczos‐based algorithms have been proposed through the years because the underlying Lanczos method only accesses A and its transpose through matrix–vector multiplications. We implement a new algorithm, called KSVD, in the Matlab environment for computing approximations to the singular subspaces associated with the k dominant singular values of a real or complex matrix A. KSVD is based upon the Lanczos tridiagonalization method, the WY representation for storing products of Householder transformations, implicit deflation, and the QR factorization. Our Matlab simulations suggest it is a fast and reliable strategy for handling troublesome singular‐value spectra. Copyright © 2001 John Wiley & Sons, Ltd.