WIREs Computational Statistic -1 with A=A∈Rmx" s that GF c tem A)At the start of the th st we have converted the origl systm twhere ops,where a k-1#-k+1 nop denotes a f T e is n A肉= k-1 「A A图 difficulty in generalizing the LU factorization to rect 知-k+10 A (1) angular matrices,though by far its most common use is for r with A upper triangular.The kth stage of the elimi- form nation the elements below the pivot element al in the kth column of A according to the operations that this happens submatrix f Thm.9.1).We define a+=a-mai=k+1:% (2a b+山=b-mb,1=k+1:n(2b) ngular for where the quantities =1:n-1.f Ak is singular for some1≤k≤n-1 then the factorization may exist,but if so it is not m达=a州/a你，i=k+1:n The the theorem are e in general matrices they can be shown always to hold;see the Back the p section'Structured Matrices' triangular system Ux=b is the recurrence The interpretation of GE as an LU f very impor ed tha paradigm for thinking and computings.In particular. 4=(b-∑4)/4，k=n-1-1:1 =k+1 Le give severa and Ux:thus x is Much insight into ge is obtained by obtained by solving two triangular systems.If we need to solve for another right-hand side b2 we where the Gauss transformation M=I-mge with m=[0,...,0m..Overall, can just carry e LU correspon ing trian that iss if w ork MR-1Mn-2…M1A=Am=:U. with the equations(2)that mix up operations on A and b the fact thatMit easy to Similarly,solving Ay=c redu to solving the 三2us1n A=...M-U the computation of the sca r yA-.which =(1+m1e)1+m2e…1+mm-1e1)U ny or x)and s oagain requires just two triangula =(+∑m加 then 「1 m211 l =eTU-len eTU-IL-len =eTA-len=bam U=:LU 1 Volume 3.Mayuune 2011 2011 John wiley sons.Inc 231WIREs Computational Statistics Gaussian elimination are n − 1 stages, beginning with A(1) = A ∈ Rn×n, b(1) = b, and finishing with the upper triangular sys￾tem A(n) x = b(n) . At the start of the kth stage we have converted the original system to A(k) x = b(k) , where k − 1 n − k + 1 A(k) = k − 1 A(k) 11 A(k) 12 n − k + 1 0 A(k) 22 (1) with A(k) 11 upper triangular. The kth stage of the elimi￾nation zeros the elements below the pivot element a (k) kk in the kth column of A(k) according to the operations a (k+1) ij = a (k) ij − mika (k) kj , i, j = k + 1: n, (2a) b(k+1) i = b(k) i − mikb(k) k , i = k + 1: n, (2b) where the quantities mik = a (k) ik /a (k) kk , i = k + 1: n are called the multipliers and a (k) kk is called the pivot. At the end of the (n − 1)st stage, we have the upper triangular system Ux ≡ A(n) x = b(n) , which is solved by back substitution. Back substitution for the upper triangular system Ux = b is the recurrence xn = bn/unn, xk =  bk − n j=k+1 ukjxj ukk, k = n − 1 : −1:1. Much insight into GE is obtained by expressing it in matrix notation. We can write A(k+1) = MkA(k) , where the Gauss transformation Mk = I − mkeT k with mk = [0, ... , 0, mk+1,k, ... , mn,k] T. Overall, Mn−1Mn−2 ··· M1A = A(n) =: U. By using the fact that M−1 k = I + mkeT k it is easy to show that A = M−1 1 M−1 2 ··· M−1 n−1U = (I + m1eT 1 )(I + m2eT 2 ) ···(I + mn−1eT n−1)U =  I +n−1 i=1 mieT i  U =        1 m21 1 . . . m32 ... . . . . . . ... mn1 mn2 ... mn,n−1 1        U =: LU. The upshot is that GE computes an LU factorization A = LU (also called an LU decomposition), where L is unit lower triangular and U is upper triangu￾lar. The cost of the computation is (2/3)n3 + O(n2) flops, where a flop denotes a floating point addition, subtraction, multiplication, or division. There is no difficulty in generalizing the LU factorization to rect￾angular matrices, though by far its most common use is for square matrices. GE may fail with a division by zero dur￾ing formation of the multipliers. The following theorem shows that this happens precisely when A has a singular leading principal submatrix of dimension less than n (Ref 5, Thm. 9.1). We define Ak = A(1: k,1: k). Theorem 1 There exists a unique LU factorization of A ∈ Rn×n if and only if Ak is nonsingular for k = 1: n − 1. If Ak is singular for some 1 ≤ k ≤ n − 1 then the factorization may exist, but if so it is not unique. The conditions of the theorem are in general difficult to check, but for some classes of structured matrices they can be shown always to hold; see the section ‘Structured Matrices’. The interpretation of GE as an LU factorization is very important, because it is well established that the matrix factorization viewpoint is a powerful paradigm for thinking and computing6,7. In particular, separating the computation of LU factorization from its application is beneficial. We give several examples. First, note that given A = LU, we can write Ax = b1 as LUx = b1, or Lz = b1 and Ux = z; thus x is obtained by solving two triangular systems. If we need to solve for another right-hand side b2 we can just carry out the corresponding triangular solves, re-using the LU factorization—something that is not so obvious if we work with the GE equations (2) that mix up operations on A and b. Similarly, solving ATy = c reduces to solving the triangular systems UTz = c and LTy = z using the available factors L and U. Another example is the computation of the scalar α = yTA−1x, which can be rewritten α = yTU−1 · L−1x (or α = yT · U−1L−1x) and so again requires just two triangular solves and avoids the need to invert a matrix explicitly. Finally, note that if A = LU and A−1 = (bij) then u−1 nn = eT nU−1en = eT nU−1L−1en = eT nA−1en = bnn. Thus the reciprocal of unn is an element of A−1, and so we have the lower bound A−1≥|u−1 nn |, for all the standard matrix norms. Volume 3, May/June 2011  2011 John Wiley & Son s, In c. 231