外文翻译word版

  • 格式:doc
  • 大小:268.00 KB
  • 文档页数:7

RICHARD W.COTTLE斯坦福大学对于矩阵schur 补的表现性质(基于1974年11月12日的会议)摘要在本文中,笔者关注的是Schur 补可以在数值线性代数中使用的一些方法。

首先概述的是变量消除和块枢转:商属性是为了下一个用于测试的矩阵的前主子式是否是非零的特定标志。

另一个有用的应用是在计算实对称矩阵的惯性:惯性有助于检查这种矩阵正(半)定性。

这可以在以数学规划问题被利用检查非凸二次函数的准凸(拟凸)的非负定限。

1.-介绍在1917年,I.schur[18] 发表了带有Schur 引理的论文,这篇论文后来被称为Schur 的行列式公式,它讲的是,如果M 是一个方阵,并且A 是非奇异的M 的主子阵, 然后A B M C D ⎛⎫= ⎪⎝⎭, 则 (1) 1det det det(D CA B)M A -=-。

最近,E.Haynsworth 和其他人已经引入术语Schur 补作为一个矩阵名称,比如1D CA B --,它出现在(1)中。

参见[12]。

更确切的说, 当A B M C D ⎛⎫= ⎪⎝⎭,det 0A ≠时,就把1D CA B --称作在M 中A 的schur 补。

习惯的写成 (2) 1(M/A):D CA B -=-之所以这种表示法吸引人,是因为(1),则(3) det(M/A)det /det M A =。

在某些不参考这些性质是公知的或在数学科学的其他分支被使用的情况下,有一些论文中已经出现了对Schur 补的两个主要理论特性的开发。

本说明的目的是回顾schur 补的产生以及如何它们的属性可以在数值线性代数被利用的方式。

这个问题的更广泛的理解可以在作者的论文中找到[8]。

2.-一般定理大家在解线性方程组的过程中,消去一个或多个变量都遇到了schur 补。

比如,思考Mz=0这个线性方程组,A B M C D ⎛⎫= ⎪⎝⎭ x z y ⎛⎫= ⎪⎝⎭因此(4) 0Ax By +=(5) 0Cx Dy +=如果 d e t 0A ≠,则消除变量x 可得出下式(6) 1()0D CA B y --=另一个常见的例子是在块旋转中,有这样一个系统(在均一的情况下)(7) u Ax By =+(8) v Cx Dy =+其中det 0A ≠,则11x A u A By --=-11(D A B)y v CA u --=+-这样的操作被称为一个块主体枢[21],[17],[23],或回转[10]。

在上面的两个例子中,M 必须是方阵。

当M 是方阵且它的主子阵A 和D 是可逆矩阵时, 11111111111(A BD C)(D CA B)C(A BD C)(D CA B)A B M D -----------⎛⎫---= ⎪---⎝⎭在这种情况下,(M/A)和(M/D)的逆在公式中扮演了一个突出的角色。

Schur 补被Carlson,,Hayns-worth,,和Markham 在摩尔 - 彭罗斯逆中推广,W. N. Anderson, Jr 开展了另一种类型的发展,使用在短路操作代替Schur 补方面,如想深入了解电路网络中的短路操作理论可参考[3],[4],[11]。

3.-商属性已知M ,A 和E 为方阵,且A B M C D ⎛⎫= ⎪⎝⎭ E F A G H ⎛⎫= ⎪⎝⎭d e t d e t 0A E = 则矩阵Schur 补的商属性可描述为:(10) (M/A)((M/E)/(A/E))=Crabtree 和 Haynsworth [9]提出了商公式(10),接着Ostrowski[16]对它提出了质疑,但是它早已在数理统计(在计算多元条件正态分布的协方差矩阵)和数学规划关键代数中所熟知。

见[1]。

商属性有一个好的应用是:判断一个矩阵的主子式是否为奇异的。

如果被测试的矩阵是M ,且它的主子式的矩阵顺序为[1,...,k]M ,则(M/[1,...,k ]M 的起始输入为(M[1,...,k 1]/M[1,...,k])+的起始输入,特别的有det [1,...,k 1]/detM[1,...,k]M +.如果11m 通过了测试,即它是非零的或者是所被要求的,那么(1)11(M/)M m =的起始输入是定义好的,它的起始输入(1)11m 可被作为(M[1,2]/M[1])或者det(M[1,2]/M[1])。

因此,可得到一个信息,关于det [1,2]M 从11m 到(1)11m ,如果(1)11m 通过了测试,然后可通过计算(2)(1)(1)11(M /m )M =得到(2)(1)(1)(1)(1)11(M [1,2]/M [1])det [1,2]/detM [1]m M ==但是通过商属性可得:(2)11(M[1,2,3])/M[1,2]det [1,2,3]/detM[1,2]m M ==所以可获得关于det [1,2,3]M 的一个信息,这个过程可一直重复知道M 的所有主子式被测试完或者找到一个未能拥有这种性质的主子式。

4.-惯性公式矩阵Schur 补的第二个性质是在惯性的概念上是有用的。

当前的讨论是对于实对称矩阵,比如,对于矩阵M 来说,它的惯性是一个三维的(M)((M),v(M),(M))In πδ=其中(M)π,v(M),(M)δ分别对应矩阵M 的正,负,和零特征值的数量,可包含多重的。

因此,对于一个阶为n 的矩阵来说(M)v(M)(M)n πδ++=这样,可得出关于秩(M)ρ和符号(M)σ之间的数量关系(M)(M)v(M)ρπ=+ (M )(M )v (M σπ=- 显然,从矩阵M 的秩,符号,和阶可算出矩阵M 的惯性。

给出分块矩阵 T AB M BC ⎛⎫= ⎪⎝⎭,其中A 是非退化的矩阵,易得出 (11) (M/A)InM InA In =+这种关系被叫做惯性公式,由Hayns-wortht [12]所证明。

这个公式被Haynsworth 和 Ostrowski 计算分块矩阵的惯性,对于这个分块矩阵的一个特殊形式是0T AB M B ⎛⎫= ⎪⎝⎭,其中A 是任意且对称的,B 是阶为k 的非退化的矩阵,Haynsworth 和Ostrowski 在前引中给出了结果的备用证明, 由于Carlson 和 Schneider [6]中所描述的那样(12) (k,k,0)InM = 在 [8] 中给出了 (12) 的归纳证明,先使用了1k =是公式的成立,然后使矩阵Schur 补M 中的一个2 X 2的矩阵8888,00rr r r r r a b C b b b ⎡⎤==≠⎢⎥⎣⎦得出了一个和M 有相同性质结构的矩阵。

5.-对于计算惯性的一个算法对于惯性公式(11)和特殊情况(12), k=1在 计算实对称矩阵M 的惯性中扮演了一个重要角色。

注意到M 的对角线上,如果M 的对角线上有一个非零的输入,如11m ,则通过(11) 可得 (13) 1111(M/m )InM Inm In =+其中 111111(1,0,0)m 0(0,1,0)0if Inm if m >⎧=⎨<⎩如果M 是非零的且在对角线上存在零元素,则存在非零输入,如12m ,并且1222100m M m ⎛⎫= ⎪⎝⎭,则有(14) 2(1,1,0)In(M/M )In M =+如果M 是一个阶为n 的零矩阵,则 (0,0,n )I n M =我们注意到当M 是对称矩阵时,(M/A)也是对称矩阵。

矩阵M 必定有下列性质之一:(P1) 0diag M ≠;(P2) 0diag M = , 0M ≠(P3) 0M =。

我们采用了下列公约,让Φ成为空矩阵并设置(0,0,0)In Φ=让(k)M 表示要计算的th k 的Schur 补,让k M 表示thk 枢纽(块),则 (0)M M = (M /M )=Φ0(M/)M,M Φ==Φ则一般地 (0)0In M In M In M =+算法的步骤仅仅对于(k)M ,它的阶从n —k. k 从0开始。

步骤 0 :到目前为止,我们有(15) (k)0k i i In M In M In M ==+∑ 如果(k)M 有性质(i P ),1,2,3i =,则到步骤i 。

步骤 1 :我们可以假设(k)110m =,让(k)111k M m +=1(k)1(M /M )k k M ++=然后 (k 1)0k i i In M In MIn M +==+∑如果(k 1)M +=Φ,则停止,否则返回到步骤0,并用k+1代替k 。

步骤 2 :我们可以假设(k)(k)12210m m =≠,让1k M +=Φ,(k)1222100k k m M m +⎛⎫= ⎪⎝⎭,(k 1)(k)(k)1(M /M )M k M++== (k 2)(k 1)2(M /M )k M +++=则 2(k 2)0k i i In M In MIn M ++==+∑如果(k 2)M +=Φ,则停止,否则返回到步骤0,并用k+2代替k 。

步骤 3 :在这种情况下,(k)0M=,因为它的阶是n —k ,我们有 0(0,0,n k)k i i In M In M==+-∑,停止,此时M 的惯性已被找到。

这个算法是基于确定的算术上的。

然而当在数字电路计算机中使用有限的准确性时,它缺少数字稳定性。

这个缺陷由Bunch 和 Parlett [5]所克服,对于获得一个分解,它给出了数字性地稳定对角线枢纽步骤。

T M LDL =其中L 为单位下三角,D 是1 X 1和2 X 2矩阵的直接总和,且1,1,00i i i i l if d ++=≠。

或许惯性概念最熟练的应用被发现是在测试实对称矩阵是否为正定(半)矩阵方面。

它在本质上是确定的(M)0v =的问题而不是一个寻找特征值本身,以便对发现他们是否是负的。

测试非凸二次函数()12T T Q x x Dx C x =+ 对于准凸(或伪凸)在n R 上的非负卦限是在二次规划中。

这可以通过进行两个试验来完成。

第一是验证 0T D C M C ⎡⎤=⎢⎥⎣⎦是一个非正矩阵,第二是查明(M)1v =。

如果当0k i i In M =∑的(15)中的第二成分超过1以上,上述用于计算M 的惯性算法可以总是被终止。

参考文献[1] ANDERSON T. W., An Introduction to Multivariate Statistical Analysis.Wiley,New York (1958).[2] ANDERSON W. N. Jr., Shorted operators. SIAM J. Appl. Math. 20 (1971),520-525.[3] ANDERSON W. N. Jr. and DUFFIN R. J., Series and parallel addition of matrices. J.Math. Anal. Appl. 26 (1969), 576-594.[4] ANDERSON W. N. Jr., DUFFIN R. J. and TRAPP G. E., Parallel subtraction ofmatrices. Proc. Nat. Acad. Sci. U.S.A. 69 (1972), 2530-2531.[5] BUNCH J. R. and PARLIYTT B. N., Direct method for solving symmetricindefinitesystems of linear equations. SIAM J. Numer. Anal. 8 (1971), 639-655.[6] CARLSON D. arid SCHNEIDER H., Inertia tlzeorems for matrices: the positivesemi-definite case. J. Math. Anal. Appl. 6 (1963), 430-446.[7] CARLSON D., HAYNSWORTH E. and MARKHAM T., A generalization of the Schurcomplement by means of the Moore-Penrose inverse. Submitted for publication in SIAM J. Appl. Math. (1972).[8] COTTLE R. W., Manifestation of the Schur complement. Lin. Alg, andAppl. 8 (1974), 189-211.[9] CRABTREE D. E. arid HAYNSWORTH E. V., An identity for the Sehur com-plementof a matrix. Proc. Amer. Math. Soc. 22 (1969), 364-366.[10] DUFFIN R. J., HAZONY D. and Morrrson N., Network synthesis through hybridmatrices. J. SIAM Appl. Math. 14 (1966), 390-413.[11] DUFFIN R. J. and TRAPP G. E.,Hybrid addition of matrices一network theoryconcept. Applicable Analysis 2 (1972), 241-254.[12] HAYNSWORTH E. V., Determination of the inertia of a partitioned Her-mitian matrix.Lin. Alg. and Appl. 1 (1968), 73-81.[13] HAYNSWORTH E. V. and OsTxowsxi A.M.,On the inertia of some classes ofpartioned matrices. Lin. Alg. and Appl. 1 (1968), 299-316.[14] HAYNSWORTH E. V., Reducti。