嵌套简单ILU分解代数预处理方法

In this paper, we propose a nested simple incomplete LU decomposition (NSILU) method for preconditioning iterative methods for solving largely scale and sparse ill-conditioned hnear systems. NSILU consists of some numerical techniques such as simple modification of Schur complement, compression of ill-condition structure by permutation, nested simple ILU, and inner-outer iteration. We give detailed error analysis of NSILU and estimations of condition number of the preconditioned coefficient matrix, together with numerical comparisons. We also show an analysis of inner accuracy strategies for the inner-outer iteration approach. Our new approach NSILU is very efficient for linear systems from a kind of two-dimensional nonlinear energy equations with three different temperature variables, where most of the calculations centered around solving large number of discretized and illconditioned linear systems in large scale. Many numerical experiments are given and compared in costs of flops, CPU times, and storages to show the efficiency and effectiveness of the NSILU preconditioning method. Numerical examples include middle-scale real matrices of size n = 3180 or n = 6360, a real apphcation of solving about 755418 linear systems of size n = 6360, and a simulation of order n=814080 with structures and properties similar as the real ones.     

数据缺损矩阵低秩分解的正则化方法

数据缺损下矩阵低秩逼近问题出现在许多数据处理分析与应用领域. 由于极高的元素缺损率,数据缺损下的矩阵低秩逼近呈现很大的不适定性, 因而寻求有效的数值算法是一个具有挑战性的课题. 本文系统完整地综述了作者近期在这方面的一些研究进展, 给出了基本模型问题的不适定性理论分析, 提出了两种新颖的正则化方法: 元素约束正则化和引导正则化, 分别适用于中等程度的数据缺损和高度元素缺损的矩阵低秩逼近. 本文同时也介绍了相应快速有效的数值算法. 在一些实际的大规模数值例子中, 这些新的正则化算法均表现出比现有其他方法都好的数值特性.     

正交非均衡Procrustes问题的持续投影算法

研究正交约束下的Procrustes问题：给定矩阵A∈R^n×n, B∈ ^n×k, n>k, 找一个Q∈R^n×k}, 使得在列单位正交约束Q^TQ=I_k下, 残量‖AQ-B‖_F达到最小. 给出了求解该问题的持续投影算法, 该算法的每一次扫描由求解k个二次约束下的最小二乘问题以及一个扩充后的均衡Procrustes问题组成; 也给出了详细的收敛性分析. 文中的数值例子表明新的迭代算法优于已有的其他方法.     

关于非亏损矩阵特征值的扰动

正规阵是非亏损矩阵的特殊情形.关于正规阵特征值的扰动,Hoffman和Wielandt在1957年提出了一个重要的定理:若N,A均为n×n正规阵,其特征值分别为{v_i}_i~n=1和{α_i}_i~n=1,则存在1,2,…,n的一个排列π(1),π(2),…,π(n),使得     

QL方法的一种位移

§1 引言 QL方法是求实对称三对角阵全部特征值的有效算法。为了提高算法的收敛速度,通常都要带特定的位移。自从QL方法被提出以来,先后提出了许多位移。其中较著名的是Rayleigh商位移和Wilkinson位移。此外,还有一些基于这两种位移的Newton型位移等,在这些位移中,有些具有较快的渐近收敛速度,但不能保证收敛。虽然人们普遍认为,Wilkinson位移应有三阶敛速,但至令尚未证明之。文[2]提出了一种称之为RW的位移,它结合了Rayleigh商位移与Wilkinson位移的一些特点,这是一个收敛且有三阶敛速的位移。     

对称约束平衡Procrustes问题的一个简单解法

本文提出一个非常简单的方法,解决对称约束的平衡Procrustes问题:给定两个同样大小的矩阵A,B∈R~m×n,求对称正交阵Q,使‖AQ—B‖_F达到最小.该方法同时具有较好的数值稳定性.     

线性低秩逼近与非线性降维

综合分析介绍了在线性与非线性数据约化两方面的最新工作: 对线性情形, 讨论了列分块矩阵奇异值分解的结构分析和稀疏低秩逼近方法与算法; 对非线性情形, 研究了非线性降维与流形学习的方法. 这些问题均为数据挖掘 与机器学习领域极受关注的研究课题.     

用简单反迭代法计算三对角矩阵的特征向量

与特征值计算的算法丰富多彩相比,在已知比较精确的特征值的情况下,求其相应的特征向量的算法却不多见,已有的算法有基本反迭代法[1][2][4][5]、交替法[3]等.到目前为止,计算特征向量的算法都是基于反迭代法的,衡量算法是否收敛都是以残量的大小为标准,本文的算法也不例外.本文的目的就是计算不可约实对称三对角矩阵T=[bj-1,aj,bj]的相应于某个特征值λi（已得到其近似λ）的特征向量.首先我们来看下面的例子:例1 我们取T为201阶的Wilkinson负矩阵,λ取计算的最大特征值,分别令迭代的初始向量是e1,e100,e201,e=（1,1,…,1）T.图1反映了反迭代的收敛速度.     

秩约束子集选择问题的分而治之解法

We consider the rank-constrained subset selection problem(RCSS):Given a matrix A and integer p≤rank(A),fing the largest submatrix A0 consisting of some colmns of A with rank(A0)=p.The RCSS problem is generally NP-hard.This paper focuses on a divide-and -conquer(DC)algorithm for solving the RCSS problem:Partition the matrix A into several small column blocks:A∏=[A1,…,Ak] with a certain column permutation ∏and decompose p to p1 p2 …pk such that solutions of the RCSS problems for smaller couples form a solution of the original RCSS problem.We show that the optimal solution of the RCSS problem can be found by DC algorithm for eachP≤rank (A),if and only if A is column-partitionable,i.e.,rank(A)=∑i=1^k rank(Ai),Based upon QR decomposition,a fast algorithm for determining the column partition is offered. Our divide-and-conquer algorithm is also quite efficient even A is approximately column-partitionable.