计算部分奇异值分解的隐式重新启动的双对角化Lanczos方法和精化的双对角化Lanczos方法

The singular value decomposition problem is mathematically equivalent to the eigenproblem of an argumented matrix. Golub et al. give a bidiagonalization Lanczos method for computing a number of largest or smallest singular values and corresponding singular vertors, but the method may encounter some convergence problems. In this paper we analyse the convergence of the method and show why it may fail to converge. To correct this possible nonconvergence, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique to it, and we then present an implicitly restarted bidiagonalization Lanczos algorithm(IRBL) and an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). A new implicitly restarting scheme and a reliable and efficient algorithm for computing refined shifts are developed for this special structure eigenproblem.Theoretical analysis and numerical experiments show that IRRBL performs much better than IRBL.     

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

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

隐式重新启动的Lanczos算法在模型降阶中的应用

主要研究了一种隐式重新启动的L anczos算法在模型降阶中的应用.分析了由这个算法得到的降价后的模型的一些性质,对于一个n阶稳定的线性时不变系统,模型降阶的思想是寻找一个m阶转换函数来近似原系统的n阶转换函数H(s),其中n m.传统的kry lov子空间方法仅仅产生一个不稳定的实现,并且在低频处的误差较大,本文所考虑的隐式重新启动的L anczos方法,能较好的解决上述两个问题.     

求解大规模非对称矩阵特征问题的精化双正交Lanczos算法

We combine Lanczos algorithm with the thought of the refined projection method using QR factorization and propose the refined biothogonalization Lanczos method for computing the desired eigenvalues of large unsymmetric matrix. With low cost of work space and flops the algorithm cures the disease that the Ritz vectors may not converge when the Ritz values converge usingthe Lanczos method. Numerical experiments show our algorithm is considerably more stable and efficient than its counterpart.     

两类线性隐式方法

众所周知,在Stiff常微分方程组初值问题的数值解法中,向后微分公式(即Gear方法)是目前最通用的方法之一(见[1]).但是,Gear方法是一类隐式方法,在数值解的过程中,一般说来,每向前积分一步,需要解一个非线性方程组,它的求解是采用Newton-Raphson迭代方法,因此需要给出适当精度的预估值和计算右函数f(t,y)的Jacobi阵以     

传统隐式Runge-Kutta方法的转换方法

多级隐式Runge-Kutta(RK)方法簇中,除Gauss类方法是s级2s阶的辛方法以外,Radau类方法和Lobatto类方法既不是s级2s阶的方法也不是辛方法.基于隐式RK方法是一类转换RK方法这一特征,利用V-变换和Pade对角逼近,提出了构造高阶RK方法的转换定理.依据转换定理,导出了s级2s阶的Radau方法和s级2s阶的Lobatto方法.利用V-变换和待定系数法,导出了辛Radau方法和辛Lobatto方法.在此基础上,发现并证明了辛Radau方法是s级2s阶的方法.     

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

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

无约束优化问题的Lanczos路径方法

1 引言本文研究无约束的非线性优化问题其中f:Rn→R是光滑的非线性函数,且f(x)在Rn上是连续可微的. 目标函数第k次迭代的二次近似模型为:     

计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法

1.引言 在科学工程计算中经常需要计算大规模矩阵的少数最大或最小的奇异值及其所对应的奇异子空间。例如图像处理中要计算矩阵端部奇异值之比作为图像的分辨率,诸如此类的问题还存在于最小二乘问题、控制理论、量子化学中等等。然而大多实际问题中的矩阵是大型稀疏矩阵,且需要的是矩阵的部分奇异对。如果计算A的完全奇异值分解(SVD),则运算量和存储量极大,甚至不可能。因此必须寻求其它有效可靠的算法。 假设A的SVD为     

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

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

一类比式和问题的全局优化方法

对于一类比式和问题(P)给出一全局优化算法.首先利用线性约束的特征推导出问题(P)的等价问题(P1),然后利用新的线性松弛方法建立了问题(P1)的松弛线性规划(RLP),通过对目标函数可行域线性松弛的连续细分以及求解一系列线性规划,提出的分枝定界算法收敛到问题(P)的全局最优解.最终数值实验结果表明了该算法的可行性和高效性.     

延迟微分方程隐式Euler方法的收敛性

本文讨论了用隐式Euler方法求解一类延迟量满足Lipschitz条件且Lipschitz常数小于1的非线性变延迟微分方程初值问题的收敛性.获得了带线性插值的隐式Euler方法的收敛性结果.     

一类块隐式混合单步并行计算方法

本文讨论了一类解常微分方程初值问题的块隐式混合单步并行算法，这种算法的块数为K，精度阶为2d＋2，可在S台处理机上进行并行计算，其中K＝S·d．本文讨论了方法的一般性质，给出了方法的稳定性定理，最后给出了一个数值例子．     

两类半隐式随机Runge-Kutta方法

本文针对一般的Ito随机微分方程,应用彩色树理论构造了两类稳定性较好的强1阶半隐式Runge-Kutta(RK)方法,数值实验证明了所得方法的精度和有效性.     

显式及对角隐式Runge-Kutta方法的非线性稳定性

1.引言 过去,stiff常微分方程初值问题数值方法的稳定性研究,主要集中于讨论方法的稳定区域,目标是针对线性自治系统的.最近十年,直接针对非线性非自治系统的理论研究,所谓非线性稳定性分析,才逐渐发展起来.     

求解单侧障碍问题的隐式投影方法

利用不动点原理,得到了求解一类障碍问题的隐式投影算法.采用中心差分格式将障碍问题离散为一个线性互补问题,从而得到了基于投影形式的隐式算法.该方法的每一步迭代只需要求解一个线性方程组.用投影性质很容易证明算法收敛性.给出了具体的算法过程,数值算例结果和理论分析是一致的.     

一种四级半隐式随机Runge-Kutta方法

1引言对于大多数的工程实际问题,一般都是采用确定性微分方程来描述和研究的.然而在工程实际中,含有随机因素是不可避免的.如果仍然采用确定性微分方程来研究,那么只有对相应的微分方程进行摄动,或者其它的近似方法来分析.要想更加准确地研究含随机现象的工程实际问题,还是要对建立的确定性模型引入随机项,进而建立相应的随机微分方程,并进行求解.但是除了极少数类型的线性方程可以得到解析解.绝大多数的随机微     

广义sine-Gordon方程高精度隐式紧致差分方法

本文研究一类二维非线性的广义sine-Gordon(简称SG)方程的有限差分格式.首先构造三层时间的紧致交替方向隐式差分格式,并用能量分析法证明格式具有二阶时间精度和四阶空间精度.然后应用改进的Richardson外推算法将时间精度提高到四阶.最后,数值算例证实改进后的算法在空间和时间上均达到四阶精度.     

非线性波动方程的弱隐式与显式差分方法

广泛出现于物理、化学、机械动力学、生物、几何学等领域的非线性波动方程已经有很多的研究工作,Sine-Gordon方程和非线性受迫振动方程就是典型的例子.周毓麟教授在[1]中研究了非线性波动方程组     

关于Lanczos方法解对称方程组的一个判据

设A是n×n实对称非定矩阵,b是n维列向量,考虑方程组 Ax=b的求解问题。因为A是非定的,因此不能使用共轭斜量法,对于大型稀疏矩阵A的求解,文[1]和[2]提出使用Lanczos算法:取初始近似向量x_0,r_0=b—Ax_0,β_0=||r_0||z,令 q_1=r_0/β_0,逐次构造Lancoz序列q_1,q_2,…,q_(j 1),即