求解大规模矩阵内部特征值问题的精化与修正的精化调和块Arnoldi算法

格式：pdf
大小：306.99 KB
文档页数：6

下载文档原格式

/ 6

基于Krylov-Schur重启技术的Arnoldi模型降阶方法

基于Krylov-Schur重启技术的Arnoldi模型降阶方法徐康丽;杨志霞;蒋耀林【摘要】Krylov子空间模型降阶方法是模型降阶中的典型方法之一，Arnoldi模型降阶方法是这类方法中的一类基本方法。

运用重正交化的Arnoldi算法得到r步Arnoldi分解；执行Krylov-Schur重启过程，导出基于Krylov-Schur重启技术的Arnoldi模型降阶方法。

运用此方法对大规模线性时不变系统进行降阶，得到具有较高近似精度的稳定的降阶系统，从而改善了Krylov子空间降阶方法不能保持降阶系统稳定性的不足。

数值算例验证了此方法是行之有效的。

%Krylov subspace method is one of the typical model reduction methods, in which Arnoldi model reduction method is the basic method. Re-orthogonalizational Arnoldi algorithm is proposed to obtain r step Arnoldi decomposition. Next, this paper restarts Krylov-Schur process and drives Arnoldi model reduction method based on implicitly restarted Krylov-Schur technology to reduce the large scale linearly time invariant systems. By this method, it can obtain a stable order-reduced system with higher accuracy, which can improve the drawback of Krylov subspace methods. Finally, simula-tions of a linearly time invariant system will be conducted to illustrate the effectiveness of the proposed method.【期刊名称】《计算机工程与应用》【年(卷),期】2016(052)012【总页数】5页(P251-255)【关键词】模型降阶;Krylov子空间方法;重正交化;Krylov-Schur重启技术【作者】徐康丽;杨志霞;蒋耀林【作者单位】新疆大学数学与系统科学学院，乌鲁木齐 830046;新疆大学数学与系统科学学院，乌鲁木齐 830046;西安交通大学数学与统计学院，西安 710049【正文语种】中文【中图分类】TP39XU Kangli,YANG Zhixia,JIANG Yaolin.Computer Engineering andApplications,2016,52（12）：251-255.在众多工程技术领域，随着问题复杂性的提高，系统也变得越来越庞大，如：电力系统、流体机械系统、超大规模集成电路系统等，都涉及大型或复杂动力系统的计算机设计、仿真、优化与控制。

数值分析—矩阵特征值问题的数值计算

( vk +1 )i vk = α1 x1 , lim = λ1 . k k →∞ λ k →∞ ( v ) k i 1
lim
可见，当 k 充分大时， vk 近似于主特征向量（相差一个常数倍）， vk +1 与 vk 的对应非零分量的比值近似于主特征值。在实际计算中，需要对计算结果进行规范化。因为当 λ1 <1 时， vk 趋于零；当 λ1 >1 时， vk 的非零分量趋于无穷，从而计算时会出现下溢或上溢。为此，对向量
λ1 ≥ λ2 ≥ L ≥ λn ,
∑x y
i =1 i
n
i
为向量 x 和 y 的内积。
定理 8.3 设 A 为 n 阶实对称矩阵，其特征值都为实数，排列为对应的特征向量 x1 , x2 ,L , xn 组成正交向量组，则有 1) 对任何非零向量 x ∈ R n ，有 λn ≤ R( x) ≤ λ1 ， 2) λ1 = max R ( x) = R( x1 ) ，
Ζ = ( z1 , z2 ,L, zn )T ∈ R n ，记 max( Ζ) = zi ，其中 zi = Ζ ∞ ，这样，我们有如下乘幂法的实用
的计算公式：任取 v0 = u0 ≠ 0 ，对于 k = 1, 2,L 分别计算 vk = Auk −1 , uk = vk / max(vk ). 求出对应矩阵的主特征向量和特征值的近似值，有下面的定理。定理 8.4
m1 0 M = 0 0 0
称为质量矩阵，而
0 m2 0 0 0
0 0 m3 0 0
0 0 0 m4 0
0 0 0 0 m5 0 0 −k4 k 4 + k5 − k5 0 0 0 − k5 k5

特征值解法——精选推荐

《结构动力学》大作业结构大型特征值问题的求解0810020035 吴亮秦1振动系统的特征值问题1.1实特征值问题n 自由度无阻尼线性振动系统的运动微分方程可表示为：[]{}[]{}(M u K u F t += （1.1）其中，{}u 是位移向量，[]M 和[]K 分别是系统的质量矩阵和刚度矩阵，都是n 阶正定矩阵，()F t 是激励向量。

此系统的自由振动微分方程为[]{}[]{}0M u K u += （1.2）设其主振型为： {}{}sin()u v t ωϕ=+ （1.3）其中，{}v 为振幅向量，ω为圆频率，ϕ为初相位。

将(1.3)代入自由振动微分方程(1.2)，得：[]{}[]{K v M v λ= （1.4）其中2λω=，(1.4)具有非零解的条件是()[][]d e t 0M K λ-= (1.5)式(1.4)称为系统的特征方程，由此可以确定方程的n 个正实根1{}n i i λ=，称为系统的特征值，1{}n i i ω=称为系统的固有频率，{}i v （i=1,2,…..n ）为对应于特征值的特征向量或称为系统的振型或模态。

因为[]M 矩阵正定，则[]M 有Cholesky 分解：[][][]TM L L = (1.6)其中，[]L 是下三角矩阵。

引入向量{}x 满足：{}[]{}T x L v =，则：1{}([]){}T v L x -= (1.7)代入(1.4)，得：([][]){}I P x λ-= (1.8) 其中，()11[][][][]TP L K L --=，式(1.8)称为标准实特征值问题。

1.2复特征值问题多自由度阻尼自由振动系统的运动方程为如下二阶常系数微分方程组：[]{()}[]{()}[]{(M x t C x t K x t ++= (1.9) 其中 []M ，[]C ，[]K 分别是n 阶的质量、阻尼和刚度矩阵，{()}q t 是n 维可微向量函数。

矩阵特征值问题的解法

x 0 x 2 1
n maxR( x ) max( Ax , , x )
x 0
由于 R(x ) R( x ) ，对于任意 x ，可以取，使得：||x ||2 1 . 证明: 假设 u1 , u2 ,, un 为 A 的规范正交特征向量组，则对任何向量 x R n ，有
eigenvalueofmarix.doc
3
特征值的估计与扰动问题
特征值的估计
Di ( A) { z c :| z aii | | aij | i }, i 1,2,, n
j i
称之为Gerschgorin圆盘（盖尔圆）. Gerschgorin 圆盘定理
设A (aij )nn为n阶实方阵,则 A 的任一特征值必落
18
例1 求矩阵A的按模最大的特征值
A 1 1 5 6 解取x(0)=(1,0)T ,计算x(k)=Ax(k-1), 结果如下
1 4 1 5
k
x1(k)
x2(k)
x1(k)/x1(k-1)
x2(k)/x2(k-1)
0
1
1
0.25
0
0.2
2
3 4
0.10250
0.042292 0.017451
x1 Ax0 a1 Av1 a2 Av2 an Avn a11v1 a22v2 annvn
x2 Ax1 A x0 a v a v a v
2 2 1 1 1 2 2 2 2 2 n n n
…………..
11
xk Axk 1 Ak x0 a11k v1 a22k v2 an nk vn
12
在实际计算时，须按规范法计算，每步先对向量xk进行“规范化”。迭代格式改为 xk zk xk

计算大规模矩阵部分奇异值分解的精化Lanczos型算法

大连理工大学博士学位论文计算大规模矩阵部分奇异值分解的精化Lanczos型算法姓名：牛大田申请学位级别：博士专业：计算数学指导教师：贾仲孝20030601摘要本文研究大规模矩阵奇异值问题的Ｌｍｎｃｚｏｓ类算法、算法的收敛性以及算法的重新启动等问题，全文共分六章．引言部分介绍大规模矩阵奇异值问题的来源、解决此类问题的基本方法以及本学科的发展状况，最后介绍本文的工作．第一章给出了投影类方法收敛性分析方面已有的重要结果，表明传统投影类方法存在着近似特征值收敛而近似奇异值可能不收敛的严重隐患，而贾提出的精化投影方法则可以克服这一隐患．只要近似特征值收敛，则对应的精化近似特征向量必然收敛。

第二章研究了增广矩阵在一类特殊子空间上Ｒｉｔｚ对的性质，证明投影后的特征问题町以通过计算阶数降低一半的小规模奇异值闻题来求解．这一性质可以用于双对角亿［．ａｎｃｚｏｓ疗法以及计算隐式重新启动的精化双对角化Ｌａｎｃｚｏｓ方法中的精化位移，从而显著地节省存储量和计算量。

第三章研究了计算部分最大（或最小）奇异组的隐式重新启动的下双对角化Ｌａｒｍｚｏｓ方法，分析了其收敛性，指出这一方法存在着近似奇异值收敛而近似奇异向量可能不收敛的隐患。

为克服这一隐患，借鉴贾的精化策略，本章做了两方面的工作：第一，用精化近似奇：异向量代替Ｒｉｔｚ近似奇异向量来作为待求奇异向量的近似，并证明，只要对应的近似奇异值收敛，则精化近似奇异向量必然收敛；第二，用可以廉价，可靠地得到的精化位移来代替准确位移，并从理论上证明精化位移要优于准确位移．理论和数值实验都表明，改进后的隐式重新启动的精化下双对角化Ｌａｎｃｚｏｓ方法要明显优予隐式重新启动的Ｆ双对角化Ｌａｎｃｚｏｓ方法。

第四章研究了计算部分奇异值分解的上双对角化Ｌａｎｃｚｏｓ方法，并给出了其精化版本，并做了收敛性分析，理论和数值实验都表明，精化版本明显优越，最后还就上双对角化Ｌａａｃｚｏｓ方法以及下双对角化Ｌａｎｃｚｏｓ方法做了初步的比较。

矩阵特征值问题

2
§1、特征值的估计
由于工程计算中求矩阵尤其是高阶矩阵的精确特征值通常比较困难，而许多情况下我们只需要知道特征值在什么范围内变化或者落在什么区域内，例如判断方阵的幂级数是否收敛只要看方阵的特征值的模或谱半径是否小于1，因此特征值的估计就显得尤其必要，这方面的理论在特征值问题中相当经典。
由于
实际上是的
一个
维子空间，因此我们希望将
搜索极值的空间放大到任意
维子空
间。而增大后的集合的极大值不会比原集
合的小，极小值也不会比原集合大。
58
设有则
，并假定
，即
59
并且当
时等号成立。因此
60
一般地，我们有
定理4 (Courant-Fischer)设
是
Hermite矩阵，其特征值为
，则
存在Hermite矩阵特征值的极值原理
48
一、 Rayleigh商
二次型
，如果存在
，那么
所以如果
，我们自然也希望
49
定义1 设
是Hermite矩阵，称
为矩阵的Rayleigh商。注意到
因此我们可以把对在单位球面
的极性的讨论限定上。
50
单位球面是闭集，又因为
是的连续
函数，因此根据多元函数的最值定理，
在上存在最大值和最小值。由于特征值与
对于广义特征值问题
，可以通过
适当选择位移(shift)或极点(pole) ，再通过求逆，将之转化为SEP：
这种方法的优点是特征向量不变，矩阵奇异时也可以使用，并且在求解邻近的特征值或绝对值很小的特征值时效率较高。缺点仍然是一般不是特殊矩阵。

第八章矩阵特征值问题的数值解法

k
(X (k))j ( X (k1) )
j
1
幂方法
k充
分
大
时
，( X (X(
(k) ) j k1) )
j
1
即1
x ( k 1) i x(k) i
,
i 1,2,...n
此式说明了什么？
当k充分大时，相邻两次迭代向量对应的非零
分量的比值近似等于主特征值。
解题步骤： (1)任给n维初始向量X (0) 0
雅克比方法的一般推广
如果a 0,取使得tan 2 2a /(a a ) ( / 4)则有
ij
ij
jj
ii
a(1) a(1) 0, 得到一个使A中非零的非对角元素a a
ij
ji
ij
ji
变成零的正交相似变换。
对A(1)重复上述过程 A(2) ，得到一个矩阵序列{A(k) }。
可证，虽然这种变换不一定能使矩阵中非对角元中零元素的个数增加，但是可以保证非对角元的平方和递减。
运行结果：
程序运行结果
预备知识：
E预ig备en知-ve识ctor
定义: 设A Rnn ,若存在数及非零向量x, 使得
Ax x
则称为A的特征值，x为A的属于的特征向量。
重要结论：
Eigen-value
(1) c 为cA的特征值（c为常数c 0）;
(2) k为Ak的特征值；
(3) 设A为非奇异阵，那么 0且 1 为A1特征值，
Print[“矩阵A的精确特征值及对应的特征向量为”]； Eigensystem[A]
运行结果：
8.3 反幂法运算及程序
原理：设A为非奇异阵，那么 0且 1 为A1特征值，

大型稀疏矩阵的LU分解及特征值求解-bestparallelsparsesolver

• 基本算法
利用稀疏矩阵的特性，得到一系列密集子阵（波前）。将LU分解转化为对这些波前的装配，消去，更新等操作。
• 多波前法的优点
波前是dense matrix ,可直接调用高性能库（BLAS等）密集子阵可以节省下标存储提高并行性
• 目前主要的求解器
UMFPACK,,GSS,MUMPS,PARDISO, WSMP,HSL MA41等
GSS1.2
15秒
2012
3.0G 4核
GSS 2.34秒ຫໍສະໝຸດ 2014i7 8核
GSS 2.4
1秒
• 硬件的发展 CPU，内存等
• 稀疏算法逐渐成熟
稀疏排序，密集子阵 multifrontal ,supernodal…
• 数学库
BLAS，LAPACK

稀疏LU分解算法的关键
稀疏LU分解（不考虑零元的）LU分解 1 零元是动态的概念，需要稀疏排序,减少注入元(fill-in)
• 直接法基于高斯消元法，即计算A的LU分解。A通常要经过一系列置换排序，可归并为左置换矩阵P，右置换矩阵Q。基本步骤如下： 1）符号分析：得到置换排序矩阵 P Q
2）数值分解：
3）前代回代：
I.S.Duff, A.M.Erisman, and J.K.Reid. Direct Methods for Sparse Matrices. London:Oxford Univ. Press,1986. J.J.Dongarra,I.S.Duff, ... Numerical Linear Algebra for High-Performance Computers. G.H.Golob, C.F.Van loan. Matrix Computations. The Johns Hopkins University Press. 1996

改进的精化Cayley_Arnoldi算法计算电力系统关键特征值

当采用 Cay ley 变换[ 8, 10] 时, 可结合幂法利用稀疏技术求解[ 11] , 但仍需不断改变参数, 经过多次 Cay ley 变换, 完成对整个搜索区域的求解。使用多
收稿日期: 2009 01 14; 修回日期: 2009 04 12。
重 Caylay 变换[ 12 13] 和同时迭代法, 解决了 Cay lay 变换的参数对收敛速度的影响, 但求解的特征值数目少且运算量大。
A RPA CK [ 18] 是实现隐式重启动 A rno ldi 算法
的 FORT RAN 77 子程序包, 用于求解大型稀疏矩
阵特征值问题。本文采用修改 ARP ACK 库程序实
现改进的隐式重启动精化 Ar no ldi 算法, 求解大型
电力系统小干扰稳定性分析关键特征值。仅以较为
复杂的最小阻尼比特征值的 Cay ley 变换为例介绍
本文将数学上提出的改进精化 A rno ldi 算法[ 14] 应用于电力系统关键特征值的计算。由精化 Ritz 向量形成精化 Rit z 值, 从而构成精化 Rit z 对, 并由其替代原 Rit z 对加速算法收敛。再结合 Cayley 变换, 只需 1 次变换, 就可以计算出大规模电力系统的小干扰稳定性分析的关键特征值, 且能保证关键特征值不被遗漏。
# 13 #
2009, 33( 15)
2. 1 实部最大特征值的 Cayley 变换
为了求解实部较大的特征值, 其变换式如下:
C( A) = ( A - 1 I) ( A - 2 I) - 1
( 2)
式中: A 为状态矩阵; 1 和 2 为复常数, 也可取实常
数; I 为单位矩阵; C( A) 为变换后的矩阵。

解大规模矩阵内部特征问题的简单调和Arnoldi方法

Ｈ一（）＋）．（１为上Ｈｅｓｎｅｇ矩阵．｝卅 × ｌｓｅｂｒ
假设ｒ为复平面上的一个定点，我们要计算矩阵
Ａ在ｒ附近的特征值．由式（）得１
１
（ — ｒ）Ａ１
一
，、ｆ ‘
（）３
为是解大规模矩阵内部特征问题最有效的方法之一．本文给出了调和Ａｒｏｄ方法的一种新的实现方ｎｌｉ
Ａｒｏｄ方法是求解大规模矩阵特征问题最流行ｎｌｉ
个小型的标准特征问题，且小问题的系数矩阵是一并个上Ｈｅｓｎｅｇ矩阵．ｓｅｂｒ因此运算十分简单．
１调和Ａｎｌｉ法ｒｏｄ方
考虑大规模矩阵特征问题
维数较小时。方法的优越性更明显．新
关键词：ｒｌ算法；Ａｎｄｏｉ调和Ａｎｌ算法；ｒｏｉｄ调和Ｒｔ对；和投影ｉｚ调
中图分类号：４．０２１６
文献标识码：Ａ
文章编号：４８４９２０）３３２５０３— ７（０７０— １— ０００
Ｍｏｇｎ¨，ｉ【等深人研究了这种方法求解内部特ｒａ［Ｊａ征问题的自身缺陷，时指出了其失败的原因．同Ｓｏｔ出的位移求逆的Ａｒｏｄ方法对于大规ｃｔ［提６ｎｌｉ模矩阵内部特征问题的求解是非常有效的，该方法能达到很快的收敛速度．由于计算过程中需要对大规但模矩阵进行分解，一方面会破坏原矩阵的稀疏结构，这增加存储量；一方面，另由于Ａｒｏｄ算法在迭代过程ｎｌｉ中对矩阵的扰动是非常敏感的［，７而求逆过程又很难］

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Ｖｏ．９。．１２Ｎｏ１
Ｍａｒ２Ｉ．，０１
Ｒｅｉｄａｏｆｅｅｉｄｈａｍｏｃｂｌｃｆｎｅｎｄｍｄｉｉｄｒｆｎｅｒｎｉｏｋ
Ａｒｌｌｏｉｈｍｓｆｒｌｒｅｉｅｉｒｅｇｎｐｒｂｌｍｓｎｏｄｉａｇｒｔｏａｇｎｔｒｏｉｅｏｅ
ｓｉｓｂｔｅｈｅｉｅｎｈｄｆｄｒｆｅａｍｏｉｔｅｔｒｒｓａｌｈｄｈｐｅｗｅｎｔｅｒｆｄａｄｔｅｍｏｉｅｅｉｄｈｒｎｃＲｉｖｃｏｓａｅｅｔｂｉｅ．Ｎｕｒａｅｕｔｈｗｈｎｉｎｚｓｍｅｉｌｓｌｓｏｔｅｃｒｓｅｆｉｎｙｏｕｅａｇｒｈ．ｆｉｅｃｆｏｒｎｗｌｏｉｍｓｃｔＫｅｏｄ：ｌｒｅｅｇｎｒｂｅ；Ａｒｏｄｒｃｓ；ｈｒｎｃＲｉａｕ；ｒｆｅａｍｏｉＲｉｅｔｒｙｗｒｓａｇｉｅｐｏｌｍｎｌｉｏｅｓａｍｏｉｐｔｖｌｅｅｉｄｈｒｎｃｔｖｃｏ；ｍｏｉｅｅｚｎｚｄｆｄｒ— ｉｆｅａｍｏｉｔｅｔｒｉｄｈｒｎｃＲｉｚｖｃｏｎＣＬｈｍｂｒＣｕｅ：０２１６４．Ｄｏｕｎｏｅｃｍｅｔｃｄ：ＡＡｒｉｌＤ：１０－５３２１）１０５－６ｔｅＩｃ０７６７（０１０ —０２０
ＳｎＪａｇｉｕｉｎｌ
（ｃｏｌｆＭａｈｍａｉａＳｉｎｅＸｕｈｕＮｏｍａｉｅｓｙ，ｚｏ２１Ｊａｇｕ，ｈｎ）Ｓｈｏｔｅｔｃｌｃｅｃ，ｚｏｒｌＵｎｖｒｉＸｕｈｕ２１ｉｎｓＣｉａｏｔ１６，
第２９卷第１期２１０１年３月
Hale Waihona Puke 徐州师范大学学报（自然科学版）
ＪｕｎｌｆＸｕｈｕＮｏｍａｉｅｓｔ（ｔｒｌｃｅｃｉｉｎｏｒａｚｏｒｌｏＵｎｖｒｉＮａｕａＳｉｎｅＥｄｔ）ｙｏ
ｃｒｕｖｅｔｔｓｄｉｆｃｔｉｃｍｎｈｉｆｉｕｌｙ．ｗｅｐｒｏｓｅｉｅｎｄｍｏｄｆｅｅｉｅａｍｏｃｂｏｋＡｒｏｌｅｈｓＳｏｅｒｌｔｏｎｏｐｅｒｆｎｄａｉｉｄｒｆｎｄｈｒｎｉｌｃｎｄｉｍｔｏｄ．ｍｅａｉ —
量和精化调和Ｒｔｉｚ向量之间的关系．值实验结果表明了新算法的有效性．数
关键词：规模特征值问题；ｎｌｉ程；和Ｒｔ值；化调和Ｒｔ大Ａｒｏｄ过调ｉｚ精ｉｚ向量；正的精化调和Ｒｔ向量修ｉｚ
部特征值及其相应的特征向量．而，论分析表明，求得调和Ｒｔ向量可能收敛非常缓慢，至不收敛．避免然理所ｉｚ甚为
这种情况，出了精化调和块Ａｒｏｄ及修正的精化调和块Ａｒｏｄ方法．此外，给出了修正的精化调和Ｒｔ给ｎｌｉｎｌｉ还ｉｚ向
Ａｂｔａｔｓｒｃ：ＴｈａｍｏｉｌｃｎｌｉｔｏａｅｕｅｏｆｎｎｅｉｒｅｇｎａｒｆｌｒｅｍａｒｃｓＦｒａｇｖｎｅｈｒｎｃｂｏｋＡｒｏｄｍｅｈｄｃｎｂｓｄｔｉｄｉｔｒｉｅｐｉｓｏａｇｔｉ．ｏｉｅｏｅｔｒｅｏｎｒｓｉｔ，ｕｉｇｔｉｍｅｈｄｗｅｃｕｄｆｄｔｅｉｔｒｏｉｅｖｌｅｎｈｓｏｉｔｄｅｇｎｅｔｒｌｓａｇｔｐｉｔｏｈｆｒｓｎｈｓｔｅｏｌｉｈｎｅｉｒｅｇｎａｕｓａｄｔｅａｓｃａｅｉｅｖｃｏｓｃｏｅｎｔ．ＨｏｖｒｔｈｓｂｅｈｗｎｔａｈａｍｏｉＲｉｅｔｒｙｃｎｅｇｒａｉａｌｎｖｎｆｉｔｏｓ．Ｔｏｏｚ－ｗｅｅ，ｉａｅｎｓｏｈｔｔｅｈｒｎｃｔｖｃｏｓｍａｏｖｒｅｅｒｔｌａｄｅｅａｌｏｄｏｚｃｙ
求解大规模矩阵内部特征值问题的精化与修正的精化调和块Ａｎｌｉ法ｒｏｄ算
孙江丽
（州师范大学数学科学学院，苏徐州２１１）徐江２１６
摘要：和块Ａｒｏｄ方法可以用于求解大规模矩阵的内部特征对，定一个位移点ｒ以用该方法求接近ｒ的内调ｎｌｉ给可