外文翻译---高斯消去法是稳定的反对角占优矩阵.doc

高斯消去法是稳定的反对角占优矩阵阿兰.乔治 和 KHAKIM D. IKRAMOV摘要: 假设 BMn (C) 是一个行对角占优矩阵, 即,当 01，i = 1,n, 且 =，我们的分析表明,当高斯消去法被应用于时，没有旋转是必要的。此外，增长因子A不会超过.同样的结果显示行对角优势的确会被列对角优势所取代.1. 引言我们开始了一个报价从N海厄姆的论文 1 ：当计算一LU因式分解时，主要有三类矩阵是已知的没有安全轴的：矩阵对角占优的行或列，厄米正定矩阵，和完全非负矩阵。”作者继续说道“确定另一类矩阵非常可取的属性：复杂对称矩阵的实部和虚部都是正定的。”本文我们扩展的矩阵具有此属性包括矩阵的逆矩阵对角占优的行或列，由此我们得出，生长因子等矩阵的。读者会在3节发现证明，在2节发现初步证明所需材料。2.初步证实令 AMn(C), 一套复杂的 nn 矩阵. 索引集 ,我们的主要矩阵表示A 位于行和列索引以及A() 并且与其互补的主矩阵为A().接下来最重要是引理 3。引理 1.令 AMn(C) 是一个非奇异矩阵, 并且 B =. 令 是的一个子集.不等式如下：(1) 一个积极的标量 反之，如果类似的不等式：(2) 则通过矩阵 B证明，不等式(2)只不过是不等式(1)的另外一种形式. 这可以由以下关系得出：,最后两个等式是一般情况下的在A和B之间的特别案例。(参见 2, 章1的(33).由此我们可以说 BMn(C)是一个(行)对角线占优矩阵 (矩阵证明略)如果：(3) 在 01, i = 1,n.的情况下，可以得到不等式：(4) =B将被称之为显性因素。引理 2. 令B是一个d.d.矩阵, 并且令= A = (aij ):然后，让 i = 1,n,(5)那么 Bi 是bii的余因子, 然后(6)之前的这两个引理都可以在不等式一书的3,节4, 6, 和 7.被发现(6) 由此我们可以说，每一列的逆矩阵元素的最大，而模数是主对角线。假设一个非奇异的nn的矩阵 A进行不旋转的高斯消去，当经过k步的排除完成之后, 我们会得到一个尚未处理的n-k矩阵。 这个矩阵有个另外的称呼-源矩阵(经过k步之后) 或者称之为Schur补. 在后一种情况下，它是指A/A();当(7) 引理 3.它认为(8) 当 B = :高斯消元法这是一的众所周知的联系(看, 举个例子4, Sec. 0.7.3).令 是Schur补的这项。,是指数集 (7). 不等式如下：(9) A被称为生长因子。d.d.矩阵的性质和高斯消去法是广为人知的。我们将会在第三节陈述以下我们需要的引理引理 4.令 BMn(C) 是一个d.d.矩阵且具有航优势因子(见 (3). 然后我们可以得出:(1) 高斯消去法在任何对角旋转规则下适用于B。(2) 对角占优矩阵具有积极的遗传属性。换句话说，每个Schur补B/B()同样是一个d.d.矩阵.此外,对每一个i来说，行优势因子. 是超越不了B/B()的。这个相应的因子 也是超越不了B的 (假设原始行指数B在行B/B()留下了”attached).3. 主要结果现在我们开始证明：定理 1. 令 AMn(C)是一个非奇异矩阵，比如说 B =是一个具有行优势因子(看 (4) 的d.d.矩阵。然后我们可以得出：(10) 证明：由引理 2可以得出， a11 是在第一列最大的模数记录。于是可以得出，a11可以作为最关键的第一步消除。设定=,我们可以从(8)看到A/A与d.d. 矩阵B()互逆. 因此我们可以得出,在A/A中和第一列最大的模数记录一致并且可以作为重要的第二步消去。重复上述步骤，我们可以得出以下结论在A中，没有有排列需要执行高斯消去法.而且高斯消去法应用于A时的旋转不完全和A的部分旋转相同。事实上, 关系 (6)的真正意思是在所有的矩阵A中，这项最大模数是主对角线. 这个结论在Schur补A/A中同样成立。由此可见，在之下我们不得不在对角项的排除过程中只检查这种行为。由此我们假定：在r = s = i; t = k的情况下实现。我们规定 然后得出(11) M =与A()互逆的是B/B.并且通过引理 4, B/B 是一个d.d.矩阵,并且这个矩阵的优势因子不会超过B 中相对应的优势因子。跟着得出不等式 (5)是一种对 B/B成立的不等式类型并且通过引理 1可以得出以下这个相似的不等式(12) 包含了 A():并且在联系了(11)和(12)的说明之后可以得出 这个定理是成立的证明：.由以上可以得出(10) 成立的条件，事实上, 这个精确的不等式,当 0 1时: 并且指出：那个同样是d.d.矩阵B =的增长因子的一个限制条件评论： 很明显，根据上面的论点可以得出列对角优势取代了行对角优势. 由此，我们有了下面的定理。定理 2. 令 AMn(C)是一个奇异矩阵就比如说 B = 是一个通过（列）优势因子成立的对角线占优矩阵。然后我们得到不等式：(13) 本文的研究结果可以推广到分块矩阵与块对角优势性(参见 9, 章12). 这将使我们起将发表的论文的主题.4. 感谢书首先，我们要感谢裁判，他们很仔细阅读文章和并且提出了许多有益的建议，说了很多有帮助的话。在这里特别指出，裁判很认真地指出了在论文中5的一些错误，获得了增长因子的逆矩阵的范围。把后一类包含矩阵添加到我们的论文中。无论如何, 这些矩阵, 在5 中的范围是和在 (10)和 (13)中的范围是不同的.一般来讲，当是一个 M-矩阵，他们是没有被我们所注意的例外情况，在这种情况下5的作者足以证明= 1紧接着5, 我们列出了一些应用在线性方程组上的Ax = b 和A 和M-matrix 的逆矩阵相遇的情况。6这是某些积分方程的解, 一种时间序列方法的数值微分7, 以及某些物理问题涉及的耦合振荡器8.参考书籍1. N.J. Higham, Factorizing complex symmetric matrices with positive de_nite real and imaginaryparts, Math. Comp. 67 (1998), 15911599. MR 99a:650492. F.R. Gantmacher, The Theory of Matrices, Chelsea, New York, 1959. MR 21:6372c3. A.M. Ostrowski, Note on bounds for determinants with dominant principal diagonal, Proc.Amer. Math. Soc. 3 (1952), 2630. MR 14:611c4. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985. MR87e:150015. M. Neumann and R.J. Plemmons, Backward error analysis for linear systems associated withinverses of H-matrices, BIT 24 (1984), 102112. MR 85f:650276. R.A. Willoughby, The inverse M-matrix problem, Linear Algebra Appl. 18 (1977), 7594. MR57:125617. R. Andersen and R. Bloom_eld, A time series approach to numerical di_erentiation, Technometrics16 (1974), 6975. MR 53:1889GAUSSIAN ELIMINATION 6578. H.S. Le_, Correlation inequalities for coupled oscillators, J. Math. Phys. 12 (1971), 569578.MR 43:83229. N.J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996. MR97a:65047School of Computer Science, University of Waterloo, Waterloo, Ontario, CanadaFaculty of Computational Mathematics and Cybernetics, Moscow State University,119992 Moscow, RussiaE-mail address: ikramovcs.msu.suLicenseGAUSSIAN ELIMINATION IS STABLEFOR THE INVERSEOF A DIAGONALLY DOMINANT MATRIXALAN GEORGE AND KHAKIM D. IKRAMOVAbstract. Let BMn (C) be a row diagonally dominant matrix, i.e.,where 01，i = 1,n, with =, We show that nopivoting is necessary when Gaussian elimination is applied to, Moreover,the growth factor for A does not exceed , The same results are truewith row diagonal dominance being replaced by column diagonal dominance.1. IntroductionWe begin with a quotation from N. Highams paper 1:”There are three main classes of matrix for which it is known to be safe not to pivot when computing an LUfactorization: matrices diagonally dominant by rows or columns, Hermitian positivedefinite matrices, and totally nonnegative matrices. Then the author proceeds to“identify another class of matrices with this highly desirable property:complexsymmetric matrices whose real and imaginary parts are both positive definite. Inthis short article we extend the set of matrices having this property to includematrices whose inverses are matrices diagonally dominant by rows or columns, andwe show that the growth factor for such matrices is bounded by two. The readerwill find the proof in Section 3, with preliminary material required for the proofcontained in Section 2.2. Preliminary factsLet AMn(C), the set of nn complex matrices. For an index set , we denote the principal submatrix of A that lies in the rows and columns indexed byas A() and its complementary principal submatrix as A().The following lemma is of crucial importance in Section 3.Received by the editor February 13, 2002 and, in revised form, August 1, 2002.2000 Mathematics Subject Classification. Primary 65F10.Key words and phrases. Gaussian elimination, growth factor, diagonally dominant matrices,Schur complement.This work was supported by Natural Sciences and Engineering Research Council of Canadagrant OGP0008111.Lemma 1. Let AMn(C) be a nonsingular matrix, and B =. Let be asubset of .The inequality(1) with a positive scalar holds if and only if the similar inequality(2) holds for the matrix B:Proof. Inequality (2) is just another form of (1). This can be seen from the relations,The last two equalities are particular cases of a general formula that connects minorsin B and A (see formula (33) in 2, Chapter1).We say that BMn(C) is a (row) diagonally dominant matrix (d.d. matrix, forshort) if(3) Where 01, i = 1,n. The quantity(4) =will be called the dominance factor of B.Lemma 2. Let B be a d.d. matrix, and let= A = (aij ): Then, for i = 1,n,(5)where Bi is the cofactor of bii, and(6)Both assertions of the lemma can be found in 3, Sections 4, 6, and 7. Inequality(6) says that, in each column of the inverse matrix A; the element with the largestmodulus is on the main diagonal.Suppose that a nonsingular n-by-n matrix A with nonvanishing leading principalminors undergoes Gaussian elimination with no pivoting. After k steps of theelimination have been completed, we have an order n-k matrix that has yet to beprocessed. This matrix is alternatively called the active submatrix (after the kthstep) or the Schur complement. In the latter case, it is denoted as A/A(); where(7) Lemma 3. It holds that(8) where B = :GAUSSIAN ELIMINATIONThis is a well-known relation (see, for example, 4, Sec. 0.7.3).Let be the entries of the Schur complement,being the index set in (7). The quantity(9) is called the growth factor for A.The properties of d.d. matrices related to Gaussian elimination are widely known.We state those we need in Section 3 in the lemma below.Lemma 4. Let BMn(C) be a d.d. matrix with the row dominance factors(see (3). Then:(1) Gaussian elimination is applicable to B under any diagonal pivoting order.(2) The diagonal dominance property is inherited by active submatrices. Inother words, each Schur complement B/B() is also a d.d. matrix. Moreover,for each i; the row dominance factor. for B/B() does not exceedthe corresponding factor for B (assuming that the original row indicesof B remain”attached to the rows in B/B().3. The main resultWe now proveTheorem 1. Let AMn(C) be a nonsingular matrix such that B =is a d.d.matrix with the dominance factor(see (4). Then(10)Proof. By Lemma 2, a11 is the entry with the largest modulus in the first column.Thus, a11 can be taken as the pivot for the first step of elimination. Setting=,we see from (8) that A/A has the d.d. matrix B() as its inverse. Hence,is the entry with the largest modulus in the first column of A/Aand can betaken as the pivot for the second step. Continuing in this way, we conclude that nopermutations are needed to perform Gaussian elimination (GE) for A. Moreover,GE with no pivoting as applied to A is the same as GE with partial pivoting.In fact, relation (6) means that the entry with the largest modulus in the entirematrix A belongs to the main diagonal. The same is true for all Schur complementsA/A. Hence, to bound , we have to examine only the behavior of thediagonal entries in the course of elimination. Assume thatis attained when r = s = i; t = k: Define Then(11) M =The inverse of A() is B/B.According to Lemma 4, B/B is a d.d. matrix,and its row dominance factors do not exceed the corresponding factorsfor B:It follows that an inequality of type (5) is valid for B/Band then, by Lemma1, the similar inequality(12) holds for A(): Relations (11) and (12) imply that The theorem is proved. Remark. It can be shown that bound (10) is, in fact, the strict inequality, when 0 1: Note thatis also a bound for the growth factor of thed.d. matrix B =.Remark. It is clear that, in the argument above, the row diagonal dominance couldbe replaced by the column diagonal dominance. Thus, we haveTheorem 2. Let AMn(C) be a nonsingular matrix such that B = isa matrix diagonally dominant by columns with the (column) dominance factor.Then(13) The results of this paper can be extended to block matrices with the blockdiagonal dominance property (see 9, Chapter 12). This will be the subject of ourforthcoming paper.4. AcknowledmentsWe wish to thank the referee for the very careful reading of the paper and manyhelpful remarks. In particular, the referee has pointed out paper 5, where boundswere obtained on the growth factor for inverses of H-matrices. The latter classcontains the matrices we consider in our paper. However, for these matrices, thebounds in 5 are different from our bounds (10) and (13). In general, they areweaker than ours with the notable exception of the case when is an M-matrix.In this case, the authors of 5 were able to show that= 1:Following 5, we list some applications where systems of linear equations Ax = b with A being the inverse of an M-matrix are encountered. These are the solutionof certain integral equations 6, a time series approach to numerical differentiation7, and certain physical problems involving coupled oscillators 8.References1. N.J. Higham, Factorizing complex symmetric matrices with positive de_nite real and imagina