对称不定矩阵三对角化约化方法的新讨论
对称不定矩阵三对角化约化方法的新讨论 作者:苏尔
来源:《上海师范大学学报·自然科学版》2013年第06期
摘要:对称不定矩阵实现三对角分解PAPT=LTLT的关键问题是如何从Tk-1约化到Tk进行递推计算,直接计算的工作量很大.用构造兼证明方法实现对称三对角阵Tk-1矩阵表示的递进约化,在利用Gauss变换的乘积性质容易确定单位下三角阵的递推基础上,建立一个与Tk-1关系密切的临时矩阵Hk-1为纽带,以矩阵关系确定的元素关系运算操作为推进依据,以矩阵表示的待定元素为直接运算结果,确定Tk-1矩阵表示的递进过程,逐步约化得最终的矩阵三对角化结果T,从而代替矩阵本身繁琐的直接运算.
关键词:Gauss变换; 三对角化; 矩阵表示; 待定元素; 递进约化
中图分类号:O 241.6文献标识码:A文章编号:10005137(2013)06058411
对于对称正定矩阵,用Cholesky分解法求解[1]是已知最佳方法,运算量仅是Gauss消去法的一半.而对称不定矩阵,是否可利用其对称性给出与Cholesky分解法运算量相同的数值解法,很多文献资料都有关于这方面的题材讨论,但详述不够.本文作者将对称不定矩阵三对角分解的一个较好方法作进一步讨论,对其约化方法进行着重阐述.
给定对称矩阵A,类似于LU分解的实现过程,利用稳定的Gauss变换[2]将A逐步约化为对称三对角阵而得到分解式子PAPT=LTLT,其中L=[lij]为|lij|≤1的单位下三角阵,P是排列方阵,T是对称三对角阵.说明如下:逐步求得n-2个排列方程P1,…,Pn-2和n-2个Gauss变换M1,…,Mn-2,使得Mn-2Pn-2…M1P1APT1MT1…PTn-2MTn-2=Tn-2为所求,这样,从T0=A出发经过n-2步递推可把A最终约化为对称三对角矩阵Tn-2,记L=(Mn-2Pn-
2…M1P2P3…Pn-2)-1,P=Pn-2…P2P1,T=Tn-2,那么PAPT=LTLT[3-4].实现这个分解式关键是求出第k步的Pk,Mk时如何解决递推过程从Tk-1约化到Tk的问题,如果直接计算式子MkPkTk-1PTkMTk=Tk,工作量非常大而且每步都有不须要的计算量,本文作者用构造兼证明方法实现对Tk-1矩阵表示的递进约化,在利用Gauss变换的乘积性质容易确定单位下三角阵的递推基础上,建立一个与Tk-1关系密切的临时矩阵Hk-1为纽带,以矩阵关系确定的元素关系运算操作为推进依据,以矩阵表示的待定元素为直接运算结果,确定Tk-1矩阵表示的递进过程,从而代替Tk-1进行直接计算,逐步约化得最终结果T.
2基本思路
求Tk-1之前,不妨设已经求出M1,…,Mk-1;P1,…,Pk-1,现在构造一个临时矩阵:Hk-1=Mk-1Pk-1,…,M1P1AP1,…,Pk-1.记临时符号P=Pk-1,…,P1,M=Mk-1Pk-1,…,M1P1,L-1=MPT,而Tk-1=Mk-1Pk-1,…,M1P1APT1MT1,…,PTk-1MTk-1=Mk-1Pk-1,…,
M1P1AP1,…,Pk-1(Mk-1Pk-1,…,M2P2M1P2P3,…,Pk-1)T,由排列矩阵的性质PTi=P-1i=Pi不难得到以下的矩阵关系式:Tk-1=Hk-1L-T及Hk-1=MAPT,从构造矩阵Hk-1的定义看出因为其左右不对称形成乘积,在因子乘积计算时用它代替Tk-1的乘积相对容易得多,所以选择Hk-1作为临时矩阵搭桥是有效的,每一步不去实质求出Hk-1矩阵本身只要给出它的矩阵表示,那2个矩阵关系式又有利地确定了矩阵表示Tk-1与Hk-1的待定元素及Hk-1的一些待定元素与A(矩阵行列变换后)元素的运算关系,这些是递进约化的主要依据所在.实际上由Gauss变换的乘积性质得知,L-1=MPT是单位下三角阵,而且容易由每个Gauss向量直接确定(其中Gauss向量的每个分量lj,i+1≤1,i=1…n-2;j=i+2,…n),使得递进约化实现简洁.设想每一步计算在Hk-1矩阵表示的协助下,先得到L-1=MPT的已知结果,利用Hk-1与Tk-1以及A和Hk-1之间的关系,通过Tk-1已知主对角和次对角元素和A(矩阵行列变换后)的某些元素,得Hk-1矩阵表示的一些待定元素,然后再借已知的Hk-1元素去计算Tk-1矩阵表示的未知待定元素,逐步以Tk-1的矩阵表示为递进计算结果,最后累加得到Tn-2.通俗说就是由已经求得的M和P,由矩阵关系式推导的相对简单的矩阵元素运算关系,得到一些Tk-1与Hk-1的待定元素的运算结果,将元素所求结果对应到Tk-1的矩阵表示中,从而代替矩阵直接的繁琐运算.
上海师范大学学报(自然科学版)2013年第6期苏尔:对称不定矩阵三对角化约化方法的新讨论3具体实现
下面展开逐步递推计算的约化过程.首先从k-1=0开始,先做准备,记
H0=A=a11a12……a1n
及第一个主对角元完全等同,而且Tk-1和Hk-1第k列的后面n-k个分量vk+1,…,vn也是完全相同的,这一步中,除了Hk-1表示中有未知待定元素h2,…,hk;vk+1,…,vn,Tk-1表示中还有一个明显的未知待定元素αk,以及一个隐含的未知待定元素βk+1,这个主对角元αk和下一个次对角元βk+1在递推计算的过程显然要求这一步Tk-1中求得,同时其前面的主对角元和次对角元都在第k-1步之前的步骤中已陆续求出,且这些已知递推元素继续出现在Tk参考文献:
[1]苏尔.正定矩阵平方根分解性质讨论及正定矩阵某个特征的证明[J].吉林师范大学学报:自然科学版,2012,33(1):54-58.
[2]G W 斯图尔特.矩阵计算引论[M].王国荣,译.上海:上海科学技术出版社,1980.
[3]徐树方.矩阵计算的理论与方法[M].北京:北京大学出版社,2001.
[4]G H 格罗布.矩阵计算[M].廉庆荣,译.大连:大连理工大学出版社,1988.
Abstract:The key problem of achieving PAPT=LTLT for tridiagonalizing symmetric indefinite matrices is how to design the recurrence calculations from Tk-1 to Tk. Direct calculations would lead to a heavy workload. With construction and proof, this paper studies the progressive reduction.
Using the multiplication property of the Gauss transform, we can easily determine the recursion of unit lower triangular matrices. Thus, we establish a temporary matrix Hk-1 which is closely related to Tk-1. Element relations reflect the operation process and pending elements will provide the result. Then, with Tk-1, the progressive process is determined, and gradual reductions lead to the resultant tridiagonal matrix T. Thus, heavy and tedious matrix correction calculations are avoided. Key words:Gauss transform; tridiagonal reduction; matrix representation; pending element; progressive calculation
(责任编辑:冯珍珍)