LIBRARY OF THE 
 
 UNIVERSITY OF ILLINOIS 
 
 AT URBANA-CHAMPAIGN 
 
 bi.0.%4 
 
Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/factorizationpro477diam 
 

If- 
 
 Report No. if 77 
 
 ~7?Ja^zL 
 
 A FACTORIZATION PROCEDURE THAT IS EQUIVALENT 
 TO SUCCESSIVE OVER RELAXATION 
 
 "by 
 
 Martin Diamond 
 
 September, 1971 
 
 NOV 9 1972 
 
 UNIVERSITY OF ILLINOIS 
 AT URBANA-CHAMPAIGN 
 
 DEPARTMENT OF COMPUTER SCIENCE 
 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 
 
 URBANA, ILLi 
 
Report No. 1^77 
 
 A FACTORIZATION PROCEDURE THAT IS EQUIVALENT 
 TO SUCCESSIVE OVER RELAXATION* 
 
 "by 
 
 Martin Diamond 
 
 September 7, 1971 
 
 Department of Computer Science 
 
 University of Illinois at Urbana-Champaign 
 
 Urbana, Illinois 61801 
 
 *This work was supported in part by the National Science Foundation under 
 Grant No. GJ812. 
 
1. INTRODUCTION 
 
 The solution of a system of equations AX = q by factorization 
 techniques can he separated into two segments. The first step is the 
 definition of an auxiliary matrix, B, which is chosen so that A + B = LU 
 where L and U are sparse lower and upper triangular matrices respectively. 
 In practical computer programs the elements of B are not computed; instead 
 the elements of L and U are computed. Then by using the factors L and U, 
 systems of equations whose matrix of coefficients is A+B can be easily 
 solved. 
 
 The second part of the method consists of an algorithm which 
 uses an iteration of the form 
 
 (A+B)X n+] _ = (A+B)X n - (AX n -q), n = 0, 1, 2, 
 
 to generate a sequence of vectors {X } which converges to the solution of 
 
 AX = q. The convergence of the iteration is dependent upon the definition 
 of the auxiliary matrix (through the definition of L and U) and a sequence 
 of parameters. 
 
 One of two types of parameters is employed in the iteration. 
 The first type multiplies the term (AX -q) in the iteration as follows, 
 
 (A+B)X n+1 = (A+B)X n - T n (AX n -q). (l.l) 
 
 an analysis of this parameter and an algorithm based on the iteration (l.l) 
 can be found in Diamond [1]. 
 
 The second set of parameters may be used to alter the auxiliary 
 matrix for each n, producing the iteration 
 
 (A+B )X ,. = (A+B )X - (AX -q). (1.2) 
 
 n y n+1 n' n n 
 
 In this paper we show that if the matrix A is positive definite 
 then the well-known Successive -Over -Relaxation method (SOR) can be written 
 as a factorization. That is, we can define the auxiliary matrix B in such 
 
 (JO 
 
 a way that the sequence of vectors calculated using the iteration 
 
(A+B )X . = (A+B )X - (AX -q) 
 v oo n+1 v oo ' n v n u/ 
 
 is exactly the sequence that would be computed if SOR with relaxation 
 factor od were used. This suggests that SOR can he generalized by intro- 
 ducing the additional parameter t as in (l. 1). However, we show that in 
 
 general no improvement can be gained by introducing this new parameter. 
 
2. WRITING SUCCESSIVE OVER RELAXATION AS A FACTORIZATION 
 
 We shall begin by giving a precise definition of SOR. Let 
 
 A = (a. . ) be an n X n matrix and q be an n-component vector. The 
 i* J 
 
 solution of AX = q using SOR is computed by selecting an initial vector 
 X = (x , . . . x ) and calculating succeeding approximations from 
 
 m+1 m ,~ m+1 
 
 X. = X. ■+ 00 fx. 
 
 -. n <- -I 
 
 m, /-, n m ~ m+1 
 x. } = (1-tojx. + cnx. , 
 1 ' l l ' 
 
 where 
 
 x. 
 
 m+1 
 
 1 
 
 a. 
 
 i,i 
 
 i-1 
 
 m+1 
 Z a. .x. + z a. .x . 
 
 j=l 1,J 3 j=i+l 1,J D 
 
 n 
 E 
 
 m 
 
 - ^ 
 
 The quantity oo is called the relaxation factor. It has been 
 shown (see for example Ostrowski [2]) that if A is positive definite then 
 SOR is convergent for < oo < 2. Furthermore ifA-I-E-E, where I 
 is the identity matrix, E is strictly lower triangular and the asterisk 
 denotes the conjugate transpose, then the error vector, e = x - x , is 
 multiplied by 
 
 X = (1-^oE)" 1 [ (lio)l + E*] 
 
 CO 
 
 (2.1) 
 
 on each iteration. 
 
 We are now prepared to present the results of this paper. 
 In the following theorem we show that an auxiliary matrix B can 
 be defined in such a way that the sequence of vectors {x } computed using 
 
 (l.l) is the same as the sequence {x } computed using SOR. 
 
Theorem 1 ; 
 
 Let A = I - E - E where I is the identity and E is strictly- 
 lower triangular. Let B = -A + — I - E, < 03 < 2. Then the iteration 
 
 (A+B)x n+1 = (A+B)x n - T n (Ax n -q.) (2.2) 
 
 is equivalent to SOR when t = 1. 
 
 Proof: 
 
 First note that with B = -A + -I -E, A + B=-I -E. Thus 
 
 00 U3 
 
 each step of the iteration (2.2) is easily performed. 
 
 12 
 
 Suppose X is selected and X , X , ... are computed using SOR to solve 
 
 AX = q. Now suppose X = X ... are computed using (2.2). On the (n+l) 
 
 iteration the error e = X - X is multiplied by 
 
 n n 
 
 I - T (A+B) _1 A = I - t (~ I-E) _1 A 
 n n oj 
 
 I - T o)(l-o)E) A 
 n 
 
 = I - T (i^nE)" 1 (l-I-toI-<BE-cuE*) 
 n 
 
 I - T (I-d-oiE)" 1 [ (l-0))lW*]) 
 
 = (1-t )I+T (I-^W)" 1 [(l^)l-toE*]. (2.3) 
 n n . 
 
 When t si, (2.3) is exactly (2.1). Thus if £ , = e " then e = e . 
 n ' a n-1 n 
 
 This completes the proof. 
 
3. ADDING THE PARAMETER t 
 
 It seems possible now to increase the rate of convergence of (2.2) 
 by selecting a sequence of t • However, we will show that in general no 
 
 increase can he made. We will need the following theorem due to Zarantonello 
 (see Varga [3] ) • 
 
 Theorem 2 : 
 
 Let S he the set of all n degree polynomials q such that q (l) = 1. 
 
 For all r such that < r < 1, 
 
 min { MAX |g (z) |} = r 
 
 g e S I z I < r 
 °n n ii— 
 
 n 
 
 for all positive integers n. 
 We can now prove 
 
 Theorem 3 "• 
 
 -* 
 Let A = I - E - E and let B hy the auxiliary matrix defined in 
 
 Theorem 1. The best sequence of t 's to use In iteration (2.2), assuming 
 only the eigenvalues K of the Successive-Over-Relaxation method satisfy 
 
 \\\ < P < !> is T n = !• 
 
 Proof: 
 
 th 
 From Theorem 1 we have that on the (n+l) iteration with (2.2' 
 
 the error vector e = X - X is multiplied by 
 n n ^ 
 
 '1-T n )l + T n (l-^E) _1 [(l-w)l + WE*] 
 
 = (l-T )I + t *S V 
 
 n n u> 
 
 where ^ is given by (2.1). Therefore 
 
That is 
 
 n-1 
 
 e = n [(1-t.)I + t. <# n ]e n - 
 n . _ i ! o) J 
 
 i=0 
 
 e = P (06 ) e n 
 
 n n v or 
 
 n-1 
 
 where P (z) = n [(l-T.) +t.z]. 
 
 i=0 
 
 Since P (l) = 1 and the eigenvalues of <j& satisfy K| < p < 1, Theorem 2 
 can he applied implying the "best sequence of f's is such that 
 
 P (z) = z n . 
 n 
 
 Thus T ^ 1 and the proof is complete. 
 
LIST OF REFEEENCES 
 
 [l] M. A. Diamond, "An Economical Algorithm for the Solution of 
 Elliptic Difference Equations Independent of User-Supplied 
 Parameters," Ph.D. Thesis, Department of Computer Science, 
 University of Illinois at Urbana-Champaign, Urhana, Illinois, 
 to be printed. 
 
 [2] A. M. Ostrowski, "On the Linear Iteration Procedure for 
 
 Symmetric Matrices," pendiconti di Matematica e delle sue 
 Applicazioni , Vol. Ik, 195^- 
 
 [3] R. S. Varga, "A Comparison of the Successive Over-relaxation 
 
 Method and Semi -Iterative Methods Using Chebychev Polynomials," 
 J. Soc. Indust. Appl. Math. , Vol. 5, June 1957- 
 
\ 
 
 &1