Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the convergence of the Gauss-Seidel method applied to Dirichlet difference problems over various types… Teng, Koit 1963

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1963_A8 T3 O6.pdf [ 2.17MB ]
Metadata
JSON: 831-1.0302300.json
JSON-LD: 831-1.0302300-ld.json
RDF/XML (Pretty): 831-1.0302300-rdf.xml
RDF/JSON: 831-1.0302300-rdf.json
Turtle: 831-1.0302300-turtle.txt
N-Triples: 831-1.0302300-rdf-ntriples.txt
Original Record: 831-1.0302300-source.json
Full Text
831-1.0302300-fulltext.txt
Citation
831-1.0302300.ris

Full Text

ON THE CONVERGENCE OF THE GAUSS-SEIDEL METHOD APPLIED TO DIRICHLET DIFFERENCE PROBLEMS OVER VARIOUS TYPES OF REGIONS by KOIT. TENG 'B.A.Sc., The U n i v e r s i t y of B r i t i s h Columbia, 1961 . A' THESIS SUBMITTED 'IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR TIEE DEGREE OF MASTER OF: ARTS i n the Department of • MATHEMATICS We accept t h i s t h e s i s as conforming to the r e q u i r e standard THE UNIVERSITY OF BRITISH COLUMBIA September, 1963 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y of B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r -m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the Head of my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood t h a t copying, or p u b l i -c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department of The U n i v e r s i t y of B r i t i s h Columbia,. Vancouver 8, Canada. Date • 3 o ; i^i £>3 i A b s t r a c t The main problem considered i s the effect•due to changes i n the shape-of the r e g i o n on the•convergence r a t e of the Gauss-Seidel i t e r a t i v e method f o r s o l v i n g the D i r i c h l e t D i f f e r e n c e Problem. Ex p e r i m e n t a l l y , i t i s found t h a t as a r u l e the number of i t e r a t i o n s r e q u i r e d to a t t a i n convergence decreases as the perimeter of the region i s increased. The ensuing t h e o r e t i c a l i n v e s t i g a t i o n leads to the examination o f the corresponding i t e r a t i o n ..matrices and; a - q u a l i t a t i v e theory r e s u l t s which p r e d i c t s t h a t the number of i t e r a t i o n s should increase w i t h the number of non-zero of f -diagonal elements i n the m a t r i x .of the . l i n e a r ; s y s t e m . Further experiments i n d i c a t e t h a t "the l a t t e r r e l a t i o n s h i p i s - n o more p r e c i s e than the former; the l a c k of r i g o u r i n the theory i s undoubtedly t o blame. ; B e t t e r r e s u l t s , are obtained i n the sub-problem of e s t i m a t i n g the -number of i t e r a t i o n s necessary t o s a t i s f y / a - s u i t a b l e convergence c r i t e r i o n , given a good .estimate -of the s p e c t r a l r a d i u s of the i t e r a t i o n m a t r i x corresponding to the - region:under study. • We-accept t h i s a b s t r a c t as conforming to the r e q u i r e d standard \ i i Table of Contents Page 1. I n t r o d u c t i o n 1 2. Background f o r the Problem 2 3- The Problem to be I n v e s t i g a t e d 6 k. Convergence C r i t e r i a 8 5- E s t i m a t i o n of the Number of I t e r a t i o n s Required f o r .10 Convergence 6. P r e l i m i n a r y Experiments and R e s u l t i n g Theory 15 (a) / D e s c r i p t i o n o f the Experiments -^5 (b) R e s u l t s 17 (c) . I n t e r p r e t a t i o n of R e s u l t s 19 7- Experiment I I I 2k (a) D e s c r i p t i o n 2k (b) R e s u l t s 26 8- Conclusion 29 Appendix I - Methods of Determining the S p e c t r a l R a d i i of Gauss-Seidel I t e r a t i o n M a t r i c e s . ^ Appendix I I - M a t r i c e s A of AU=B f o r Experiment I I . 33 B i b l i o g r a p h y 37 Tables, Diagrams, Graphs Page F i g . l :. General Region f o r the D i r i c h t e l : P r o b l e m 2 F i g . 2 : P o s s i b l e Boundary C o n f i g u r a t i o n s 3 Fig. 3 : An Example Region for'Experiments . 3 Fig.!+ : Dependence of the Number of I t e r a t i o n s on •Spectral Radius ~' f o l l o w i n g page 11 Fig. 5 : Types of Regions Considered 1^  Fig.6. : Regions f o r Experiment I I l6 . Table I : Data,and R e s u l t s f o r Experiment I l 8 Table I I •: .Data and R e s u l t s f o r Experiment I I 19 F i g . 7 . : Number of I t e r a t i o n s vs. Perimeter 20 Table I I I : Ranking the Regions According t o Number of 21 Non-Zero Elements of A and S p e c t r a l R a d i i of H. Table IV :. R e s u l t s f o r Experiment I I I 27 F i g . 8 . : . Number of I t e r a t i o n s vs. Off-Diagonal Elements 28 i v Acknowledgement I wish to thank Dr. • T.E. Hull-and.Dr. • C h a r l o t t e Freese f o r • t h e i r encouragement and h e l p f u l suggestions towards t h e ' p r e p a r a t i o n of t h i s t h e s i s , the N a t i o n a l : Research'Council•of Canada f o r awarding me the Bursary•and Studentship under-which t h i s work was done, and the U n i v e r s i t y o f B r i t i s h Columbia Computing Centre - f o r making a v a i l a b l e the time f o r the numerical experiments on t h e i r IBM ;l620 computer. 1. I n t r o d u c t i o n The D i r i c h l e t d i f f e r e n c e boundary value problem f o r Laplace's equation i n the plane i s developed i n the next s e c t i o n and r e s t r i c t i o n s on the shape of the r e g i o n of s o l u t i o n .are' set up to f a c i l i t a t e the study of the main problem which i s posed I n s e c t i o n 3* To study the e f f e c t of the shape o f a re g i o n on .the number of i t e r a t i o n s r e q u i r e d t o s a t i s f y given convergence c r i t e r i a i n the numerical s o l u t i o n by the method of Gauss-Seidel. S e c t i o n k discusses the r e l a t i v e m e r i t s of' u s i n g any one of three c r i t e r i a for. determining convergence. In s e c t i o n 5 we de r i v e estimates o f the number of i t e r a t i o n s r e q u i r e d t o s a t i s f y two of these c r i t e r i a and see approximately.how t h i s number depends, on the s p e c t r a l r a d i u s o f the i t e r a t i o n matrix. We compare our r e s u l t s w i t h estimates d e r i v e d by K e l l e r ['6 ] • S e c t i o n 6 i s devoted t o p r e l i m i n a r y experiments which give us i n s i g h t i n t o the problem. In Experiment I we observe how the number of i t e r a t i o n s v a r i e s w i t h the perimeter o f a re g i o n ;and we examine the. v a l i d i t y o f a (k) convergence c r i t e r i o n depending on the displacement v e c t o r Y s ' ; i n Experiment I I we search f o r a fundamental c h a r a c t e r i s t i c o f a region which determines the corresponding convergence r a t e . This leads us t o a q u a l i t a t i v e theory regarding our problem which i s tested.by Experiment I I I - des c r i b e d i n s e c t i o n J. Concluding remarks sum up the t h e s i s and i n d i c a t e the d i r e c t i o n o f f u r t h e r research.' The major reference f o r the u n d e r l y i n g theory f o r t h i s t h e s i s i s the b o o k ' " F i n i t e - D i f f e r e n c e Methods f o r P a r t i a l D i f f e r e n t i a l Equations" by.Forsythe and-Wasow [U] . The same theory can a l s o be found i n the books by Fox [5] y. Todd [8] , or Varga [9] . 2. 2. Background for the Problem . The problem for which we seek an approximate solution i s the following: Find a function u(x,y) which s a t i s f i e s Laplace's equation \ 2 v 2 . ( 2 . 1 ) Au= + - o <)x2 i n an open, connected,> plane domain R, and the^Dirichlet boundary condition ( 2 . 2 ) u(x,y) = g(x,y) on the boundary S of R, where S i s composed.of piece-wise analytic arcs and g(x,y) i s a given function. 5. 1 R h t F i g . l General Region f o r the D i r i c h l e t Problem .In order to simplifyV •' the analysis we s h a l l consider only, regions, that can be covered with a square mesh of spacing h i n such a manner that the boundary S intersects the mesh l i n e s only/at nodes•• (points of intersection of mesh l i n e s ) . Figure 2 i l l u s t r a t e s the type of region :which i s allowed and which i s not. (*) Otherwise the Laplace difference approximation could be different f o r each point.-adjacent to the boundary and the-matrix of the resulting l i n e a r system would be more complicated. 3-f ) ^ I ' \ \ / c k O 5 5r x In ^ ' 'I ' *s ) / \ \ - ( s r — r % 5 > \ < (a) not allowed (b) .allowed F i g . 2 P o s s i b l e Boundary C o n f i g u r a t i o n s Let N, and M ;be the number of i n t e r v a l s , i n the x and y d i r e c t i o n s respect-i v e l y , r e q u i r e d t o cover a l l of R by the mesh. Label the l i n e s p a r a l l e l to the y - a x i s w i t h the index i , where i ,= 1,2,...,N+1 (as i n Figure 3 ) > a n d the l i n e s p a r a l l e l to the x - a x i s w i t h j : 3=1,2,...,M+1. F i g . 3 An Example Region.for Experiments Denote by R^  the set of a l l : n o d e s t h a t l i e i n R, and by a l l the nodes , s ] on S. Each node can be i d e n t i f i e d uniquely/by the index p a i r ( i , j ) belonging to the l i n e s t h a t i n t e r s e c t - a t t h a t node. At each p o i n t of R^  we can, under the above c o n d i t i o n s , apply the u s u a l f i v e - p o i n t d i f f e r e n c e approximation [U, P.192J t o the L a p l a c i a n , namely: (2.3) A h U = h " 2 [ u ( l - l , j ) , + U(i,j+1) :+ U ( i + l , j ) + U ( i , j - l ) - U u(i,j ) j w i t h t r u n c a t i o n e r r o r : (2.M A h u- A u = o(h 2) The d i s c r e t i z e d problem i s then to f i n d a f u n c t i o n U ( i , j ) s a t i s f y i n g at each p o i n t of R^  .: , (2.5) U(i,.j) = £ [ u ( i - l , j ) + U ( i + l , j ) + U ( i , j - l ) .+ u ( i , j + i ) ] : and at p o i n t s of : (2.6) U ( i , j ) = G ( i , j ) where G(±,i) ,is the d i s c r e t e e q u i v a l e n t of g ( x , y ) , d e f i n e d f o r p o i n t s of . Applying (2.5) at each p o i n t of R^  and (2.6) at each p o i n t of y i e l d s the f o l l o w i n g system of simultaneous l i n e a r equations : (2.7) AU = B where A i s a sparse ( f o r s u b s t a n t i a l problems) symmetric m a t r i x of order equal t o the number o f . p o i n t s of Rh , say n. U i s the r e q u i r e d n-dimensional s o l u t i o n v e c t o r and B i s a known v e c t o r c o n t a i n i n g the boundary values G ( i , j ) . We note t h a t system:(2 . 7 ).is i n v a r i a n t under any t r a n s f o r m a t i o n of S which does not v i o l a t e our r e s t r i c t i o n s on the shape of R and which introduces no new i n t e r i o r p o i n t s or d e l e t s p o i n t s already there. In other words the • 5 -system of d i f f e r e n c e equations does not correspond to a unique region. ...If.we f u r t h e r r e s t r i c t the regions R t o be such that, any two p o i n t s of R^ can be j o i n e d by l i n k s (see L i n Figure• 3),of the mesh connecting p o i n t s of R^ onl y , then the m a t r i x A becomes i r r e d u c i b l e ^ * ) [9> P-19] > and the f o l l o w i n g theory \k, Sec. 21.6 i s a p p l i c a b l e . (*) For then a l l . the p o i n t s o f R^ are mutually l i n k e d and consequently the f u n c t i o n value at any p o i n t depends e i t h e r d i r e c t l y . o r i n d i r e c t l y on the f u n c t i o n ' v a l u e s - a t ' a l l the other p o i n t s through elements o f the ma t r i x A. 3• The Problem to be • I n v e s t i g a t e d Let us p a r t i t i o n A,as f o l l o w s : (3.1) A = D + E.+ F where D. . = An- •• ±, 1 ±,± D = 0 f o r i. £ j E i , j = A i , j ^ > j ) i E i , j = ° ^ - J ) T T F = E where E i s the transpose of E •i.e. A = Then the Gauss-Seidel i t e r a t i v e method f o r s o l v i n g AU=B can be w r i t t e n : (3-2) ='HU^"1) + MB . k=l,2,. ... (o) where U i s a r b i t r a r y , and •M (3-3) H = -(D+E) - 1F ; M= (D+E)" 1 This d e f i n e s a sequence which converges f o r a r b i t r a r y TP"' to the s o l u t i o n U provided t h a t t h e - s p e c t r a l r a d i u s ^ ' , jO ( H j , of the i t e r a t i o n m a t r i x H i s l e s s than u n i t y . (k) We de f i n e the 'error v e c t o r at the k t h step, E , by (3.k) E ( k ) = U ( k ) - U = U ( k ) - A ^ B -.. I t f o l l o w s t h a t (3-5) E ( k ) = H E ( k - l } = H* E ( o )  (where E^°^ = - U i s the i n i t i a l e r r o r . (*) p (H) = max ' • i X.'(_) where X.(H) are eigenvalues of H. 1 1 7-In our numerical computations we choose a s u i t a b l e v e c t o r norm to monitor the s i z e of our e r r o r E ^ ) . We s h a l l use the maximum - component (Chebyshev) norm j~3, p.55J i n our experiments - i t has c e r t a i n computational advantages. We can now s t a t e our main problem as f o l l o w s : To observe the e f f e c t o f the shape of a r e g i o n on the-number of i t e r a t i o n s r e q u i r e d t o reduce the i n i t i a l e r r o r by a given f a c t o r . For comparison purposes we keep the number of i n t e r i o r p o i n t s constant i n (*) any one experiment. Without l o s s o f g e n e r a l i t y we need consider only regions whose boundary l i n e s make angles of n~^~" w i t h the p o s i t i v e x - a x i s (where n i s an i n t e g e r ) . . (*) ,Since the same l i n e a r system a r i s e s from regions w i t h the same c o n f i g u r a t i o n of i n t e r i o r p o i n t s , keeping i n mind our r e s t r i c t i o n s on R. 8 . k• Convergence C r i t e r i a Provided the s o l u t i o n v e c t o r U = A •^ B i s a v a i l a b l e to us we can use the e r r o r v e c t o r i n monitoring convergence. .We I t e r a t e u n t i l ,00 1 • tHM (k.i) | E w | _ t j | - v where tf i s a p r e s c r i b e d t o l e r a n c e and ||E ^ ^ J J i s our chosen v e c t o r norm. This procedure r e q u i r e s the storage of both the known s o l u t i o n U and the , c u r r e n t i t e r a t e throughout the i t e r a t i o n , which may be d i f f i c u l t i f U has a very l a r g e number of components and computer memory i s l i m i t e d . However, i f U ,1s not a v a i l a b l e ( t h i s i s the general c a s e ) , i t i s impossible (v) t o compute E V '• at any stage of the c a l c u l a t i o n . Therefore we seek a more u s e f u l convergence c r i t e r i o n . Define the r e s i d u a l at the k t h step (k.2) R ^ = B - A U ^ k= 0,l , 2 , . . . which i s the d i f f e r e n c e between ,the right-hand and l e f t - h a n d s i d e s of AU=B w i t h U r e p l a c e d by . Since R ^ •=. - A E ^ i t f o l l o w s t h a t i f E ^ — = • 0 then so does R ^ and we c o u l d conceivably use R ^ ^ t o monitor convergence, (k) •Let U I be the i t h component of the k t h , i t e r a t e . Then, i n the Gauss-(k) ( k - l ) . S e i d e l method, when we compute IL^ we have some o l d values' "and some (k) new values U N i n storage at any one time, except at the end of each i t e r a t i o n . Not u n t i l then'could we compute R V ' and t h i s would i n v o l v e j u s t as • (k) .much c a l c u l a t i o n i n i t s e l f as was i n v o l v e d i n computing U - ' . In. other words, computing R V ' i s e q u i v a l e n t i n time t o one complete i t e r a t i o n . We seek t o avoid t h i s e x t r a computation. Therefore, we l e t (U.3) y( k) = u W - u ^ " 1 ) k = l , 2 , . . . the displacement v e c t o r at the k t h i t e r a t i o n . I t .is r e l a t i v e l y simple to ( k ) onfl +.n k<=An t r a n k o f Y ^ ) •= mnv Y.'(^) max i as the i t e r a t i o n compute YV ' and t o keep t r a c k of proceeds. I t ..follows t h a t (k.k) = H Y ^ = H k " V 1 } i . e . Y^ k^ s a t i s f i e s the same i t e r a t i o n as E^ K^. ,Now i n the problems we s h a l l s o l v e , the m a t r i x A has diagonal dominance and i s i r r e d u c i b l e . Therefore, we are assured ^k, p.236j of the convergence of the Gauss-Seidel method and consequently a l l the eigenvalues of H.are l e s s than 1 i n modulus. Thus l i m H ,= 0 and hence 1 im Y ( K ) = 0 . k—v oo k-»-°o We have ( U . 5 ) Y ( L ) = ( H - l ) E ( O ) so t h a t (k.6) , Y ( K ) = H ^ C H - ^ E ^ ) From the l a s t r e l a t i o n and from (3-5) w e see tha t both E ^ K ^ and Y^ K^ f (o) ^ . depend on the same v a r i a b l e s , namely < H, E , k > . Thus f o r an e q u a l l y . v a l i d " b u t perhaps more u s e f u l convergence c r i t e r i o n we can take 0.7) ||YW|| _ iMo)\\ Now since U I s unknown E ^ ° ^ i s a l s o , but by the maximum p r i n c i p l e ^h, p.l7^J :ve do know upper bounds f o r ||E^°^||. Suppose | | ° ^ | ^  E . Then (k.f) becomes (U.8) ||- ( k ) || ^ t 2E . I f we use the same and E i n a l l our problems we can take (h,9) ||Y ( K )|| _ T as our c r i t e r i o n , where T - t 2 E. We note t h a t t h i s c r i t e r i o n i s the e a s i e s t to apply but since ||E^°)|| may be q u i t e d i f f e r e n t f o r problems w i t h the same.E, i t s use cannot be expected t o y i e l d as good r e s u l t s as.a more exact c r i t e r i o n . This f a c t i s borne out by. our experiments which w i l l be des c r i b e d i n l a t e r s e c t i o n s . 10. 5- E s t i m a t i o n of the •'Number of I t e r a t i o n s Required f o r Convergence We now proceed to d e r i v e approximate expressions f o r the number o f , i t e r a t i o n s r e q u i r e d t o s a t i s f y given convergence c r i t e r i a . The d e r i v a t i o n depends on ;approximate e q u a l i t i e s which become t r u e a s y m p t o t i c a l l y as k —»» oo (see Forsythe and Wasow [k.,. sec.2lj f o r d e t a i l s on these). R e s u l t s obtained from these expressions are compared against experimental r e s u l t s i n s e c t i o n s 6 and J. Let f> be the s p e c t r a l r a d i u s of H. For convergence, we know t h a t f> < 1, and assume t h i s to be t r u e . Then- ' ". . (5.1) .^k> - ^ E<kil> - ^k_<°> (5.2) E^" 1 ) _ From (5-1) ||-(K)|| — / 0 K ||E(°)|| . Therefore (5-3) 1 E O O 1 1 1 .Suppose our convergence c r i t e r i o n i s ||E0O|| _ i o - ||E(°)|| where s i s a small p o s i t i v e i n t e g e r (say 3 ° r k). Then we put ,.= 10"s i n (5-3) , 1 1 take logarithms^*) and o b t a i n k l o g fO — — s S p l v i n g f o r k, we get (5-i+) k ~ - s l o g ^ (*) a l l logarithms to the base 10 11. I f i n s t e a d we use-the displacement v e c t o r we get an estimate as f o l l o w s : (5-. 5). Y< k) = u ( k ^ - u ^ - ^ . E ^ - E ^ " 1 ) and u s i n g (5-l) and (5-2) . : Y ( k ) _ ^ _x) E ( o ) ,Taking-norms : . • I I Y W I I _ p^y-A . ||E<°>|| - ^ ( i - ^ ) ||«<?>|| ,Therefore (5.6) | | Y M I I r->TiF^i We use | | E ^ 0 ) | | £ E and j|Y^k^|| _ 10" s . E i n the above expression, take logarithms and o b t a i n ( k - l ) . l o g ^ c_ -s - l o g (l-f>) Hence ' (5-7) k ~ s + l o g (l-/o) . + 1 /-lOg/D . • ". As :our estimates we take the sma l l e s t i n t e g e r s > the r.h.s. of the above, expressions (5-U) -nd (5-7)- These expressions are p l o t t e d i n Figure k w i t h s •= 3 ;and demonstrate the approximate dependence of k on . Experimental points.are. a l s o shown on the graphs. The problem of e s t i m a t i n g the,number of i t e r a t i o n s - n e c e s s a r y to s a t i s f y a given c r i t e r i o n has a l s o been t a c k l e d hy K e l l e r ^6 Jwho d e r i v e s two lower bounds f o r -k under d i f f e r e n t assumptions. . F o l l o w i n g Forsythe and Wasow |\, p .2 l8J we define t h e , M r a t e o f convergence" : r = - l o g jo which can be i n t e r p r e t e d as "the asymptotic average number of d i g i t s by which the e r r o r i s decreased per i t e r a t i v e step". This agrees q u i t e w e l l w i t h our f i r s t estimate: 12. k ~ s = £ - log^o r where s represents the number of d i g i t s by which the e r r o r i s to be reduced. K e l l e r £-6 J proceeds along these l i n e s ; ( l ) Suppose the elementary d i v i s o r s of H.(see Faddeeva ^3 J f o r d e f i n i t i o n ) are simple. Tbep the n ,eigenvalues of H are d i s t i n c t and there e x i s t s a complete set Q f eigenvectors spanning the n-dimensional space. Therefore we can w r i t e (o) n E = 2 a^ e^ ( a. are constants) i = l and u s i n g i&> = H ^ E K ; ,-and, H e i = \.ei we o b t a i n , . „ i = l Suppose we r e q u i r e t h a t the most slo w l y decaying component i n ; E v ' be reduced by at l e a s t 10"s , where s > 0. This corresponds t o the one f o r = max|.Xj| .:•= ^ 1 > say and t h e r e f o r e ^ g k a]_ e^ £ 10 a^ e^ i . e . ^ 10 - s from which (5-8) k ^ , s = £ , since p < 1 -log/? r -• This would seem to i n d i c a t e t h a t our estimate (-5-U) , i s a lower bound but our b a s i s f o r the n-dimensional space c o n s i s t s o f u n i t v e c t o r s i n each of the n d i r e c t i o n s and hence the maximum component above does not correspond to I U ( k ) | I _ ( k ) | . . . E x = max E.V as we used i t . 11 1 i I l I 13-(2) ..If the elementary d i v i s o r s are not simple, by making the f o l l o w i n g assumptions: - t h a t the elementary d i v i s o r of l a r g e s t order corresponding' to^o= X-^  i s of order m+1 - t h a t k --m+1 - t h a t k - (m+l)^o + m that a l l other d i v i s o r s are simple, . K e l l e r [-6 ] obtains the f o l l o w i n g , approximate bound: (5-9) * - s ' / r . + m+ (m/2r)log [•(•s'l/r+m)s»/r] where- s' = s - log? m! ; r = - l o g p A s y m p t o t i c a l l y (as s —+ 00) , t h i s r e s u l t . i s e q uivalent to the previous one. However, t o use the lengthy expression (5-9) one would have t o know the order m+1 of the l a r g e s t elementary d i v i s o r corresponding to and,also the r e s t r i c t i v e c o n d i t i o n s used i n the d e r i v a t i o n would have t o be met. Thus i t s p r a c t i c a l use seems d o u b t f u l . 1444J4444444444444444/4444/,</•/ z: •N-L SI 14. •N a I///44444444444)4 14444444444444^ - N -'4444444444 4 44444^444 44 444 4 4 44 4 4 4 4, N /WW/l'//i'tflf 44" 4444, Y L -N a N-'44 44 44444*44 444444H 4 J44J 0 X if T , '444444, 4 44444, i N '444414444 3 -N , i 4*4+4-} N 9-The l e t t e r s R, L , • • • d e s i g n a t e the programs . /A U d i m e n s i o n s are i n u n i t s o"f K . L i n e i of s y m m e t r y . /////4444444 U = 1 on b o u n d a r y U= 0 on b dry g u r e 5 : Types of R e g i o n s C o n s i d e r e d 15-6. P r e l i m i n a r y Experiments and R e s u l t i n g Theory (a) -Description of-Experiments. In. the two experiments de s c r i b e d below,.the a c t u a l i t e r a t i o n was c a r r i e d out by using (6.1) ; U ( i , j ) , = £ [ u ( i - l , j ) + U ( i , j + l ) .+ U ( i + l , j ) + U ( i , j - l ) ] s u c c e s s i v e l y f o r each i n t e r i o r p o i n t ( i , j ) and sweeping through the p o i n t s i n a c o n s i s t e n t order p. 2U4-J during each i t e r a t i o n u n t i l (6.2) ||Y( k)|| ^ 10^ 'Experiment I Computer programs were w r i t t e n t o compute t h e . a c t u a l number of i t e r a t i o n s k a r e q u i r e d t o s a t i s f y the^above i n e q u a l i t y f o r the.types of regions i n Figure 5* The dimensions N, M, N a , M a were v a r i e d f o r each r e g i o n , keeping the number of i n t e r i o r p o i n t s at 36. " I n t u i t i v e l y , one would.expect t h a t i f the area of a region were kept constant and the perimeter increased, then the i n t e r i o r p o i n t s would be f o r c e d c l o s e r t o some boundary (on the average), the values of the f u n c t i o n would be more r e a d i l y determined, and the number of i t e r a t i o n s necessary should decrease. Thus'the obj e c t of t h i s experiment was to o b t a i n a p l o t of the number k a against the perimeter P and t o t e s t , the v a l i d i t y of the'convergence c r i t e r i o n ( J|_"^-)||_i .,''10 ; f o r comparison purposes. \ Experiment I I This experiment was c a r r i e d put on the regions shown i n Figure 6, each one c o n t a i n i n g 12 i n t e r i o r p o i n t s . Here we made s i m i l a r observations t o those of Experiment I but because the matrices were of such small order and hence convenient to work w i t h , we a l s o examined the matrices A, the r e s u l t i n g i t e r a t i o n R ,_X X X X 5 X X X X }ftittttHittittH4tfl IG. L H X X 9 x X 5 X X X x X X x WW / / / / / / / u I 0 X <, X 1/ x 5 x x x x ,X X X X I 0 X i ,x x X X X X X ii i ; Scale C"^ utai^s o"f k ) : L—• > 1 L-12 interior points ; L a b e l l e d , by x • Order 0/ solution i 5 mcdcateot • Figure £ f?egion.s "Tor Experiment H . •17-matrices H,.and the s p e c t r a l r a d i i of H which determine the rate o f convergence. The purpose, was to. f i n d , i f p o s s i b l e , a fundamental parameter, c h a r a c t e r i s t i c of the re g i o n i t s e l f , which i n f l u e n c e s t h i s r a t e the most. (b) R e s u l t s Data and r e s u l t s f o r Experiments I and I I are l i s t e d . i n Tables I and I I , r e s p e c t i v e l y . Key f o r headings i n Tables I and I I : - The program l e t t e r r e f e r s to the type of region under c o n s i d e r a t i o n . ( - N, \M, N a, M a are the dimensions i n Figure 5 :(in u n i t s of h). - A i s .the area ( i n u n i t s of h ) . ~ P i s the perimeter i n u n i t s of h. - i s the s p e c t r a l r a d i u s of H (computed i n one of s e v e r a l ways -see Appendix I ) . - kp i s the p r e d i c t e d number of i t e r a t i o n s , according t o (5»7)« - k a i s the a c t u a l number (found by experiment). 18. • Table I - Data and Res u l t s f o r Experiment I Prog: • .N •M ^ N a Mfl A . P k P k a R-2 •3 x9 57 UU • 5520 •16 10 -3 k ' 13 . '. . 5.2 3^ • 7039 • 2k 16 -k 5 :10 '50 3© • 77^1 32 23 -5 7 7 ' ^9 •28 .8127 38 •32 -6 10 5 50 30 .Tiki :32 30 -7 13 •U 52 •3k •7039 •2k • 2k -8 • 19 •3 57 kk •5520 16 ' 16 L-2 8 7 3 . ,2 '5.0 30 797^ 35 31 -3 9 7 ' U • 3 . 51 32 •7719 -31 28 -k 9 8 5 52 3^  .7321 26 2k -5 10 9 6 6 ,k 38 •6931 23 20 -6 11 l l ,8 8 57 •Mk .59UU 17 16; U-2 9 .6 •1 2 52 3k •7376 27 25 -3 . .9 ' 7 . 3 3' 5k 38 .70U5 • 2k 22 -M. -l l 7 5 57 •5991 :i8 16 0-2 8 7 .2 l 5U 36 6131 !18 •19 -3 10 6 2 2 56 ko 6333 20 20 -k ' 9 8 3 •u 6o kQ 5329 15 15 -5 ' 11 7 5 3 62 52 •5139 Ik 15 -6 11 11 ,7 7 72 72 ; .3372 10 10 1-2 9 7 3 1 57 :kk 63^1 20 •19 -3 7 8 5 .2 " 52 3k 7715 31 30 ._/+ 7 l l . .3 5 57 kk •5893 17 17 -5 . 5 13 3 5 55 ko 6385 20 19 -6 9 13 3 9 ., 63 56 5807 17 Ik X-2 9 6 1 l 50 30 8035 .36 • 38 -3 l l .7 ;3 .2 53 36 .7689 31 ' 30 -^  10 9 • 3 3 ' 3k 38 •7353 '27 2k -5 l l 11 57 kk .65^ 6 21 17 Tx-2 io 10 •50. •3k.Ik .77M1 32 •29 T2-2 Ik 7 h9 ' 33-80 7717 32 29 19-Table I I - Data and Re s u l t s f o r Experiment I I Prog; "N ,:M •Na :A , P k k a R - i 5- •k 20 18 .57^7 17 •15 L - l . 5 • 5 2 . -2 21 •20 .51^5 Ik 13 U-l 5 .5 1 2 23 2k . 1*512 12 12 0-1 5 5 . 1 1 2k 2k • .2500 8 10 i - r .5 5 3 1 23 2k .1+665 13 13 X-.I- 5 . .5 l ; '1 21 20 • 5623 16 :16 Tx-1 7- U 20 ' 19.66 • 5 ^ ' 15 Ik T 2 - l 9. 20.25 ::21.72 . 5181 Ik Ik (c) / I n t e r p r e t a t i o n of R e s u l t s . We note from Tables I and I I and Figure k(a) t h a t the p r e d i c t e d values kp and the a c t u a l values k a f o r the number of i t e r a t i o n s r e q u i r e d t o s a t i s f y (6.3) I I Y ^ H * io~k agree q u i t e c l o s e l y f o r both experiments, but p a r t i c u l a r l y f o r Experiment I I , where they d i f f e r / b y - a t most 2. This i n d i c a t e s t h a t i t i s p o s s i b l e to p r e d i c t reasonably w e l l , the r e q u i r e d number of i t e r a t i o n s provided t h a t the s p e c t r a l r a d i u s p> (H) i s known. Experiment I . In Figure 7 we have p l o t t e d the a c t u a l number of i t e r a t i o n s k a r e q u i r e d to satisfy'(6.3),vs. the perimeter P f o r each of the regions considered. I t can be seen from the graph t h a t a considerable amount of s c a t t e r i s i n v o l v e d , even f o r regions of the same type,.. although the general t r e n d i s towards l e s s i t e r a t i o n s as the perimeter i n c r e a s e s . In f a c t , f o r regions of type 0, at one p o i n t k a increases w i t h P, w h i l e f o r types R and I , regions w i t h the same perimeter have d i f f e r e n t values f o r k a. 0 <u 0 • —' L L <y —H 0 <U y Q_ tl X h o o M H crT O OCo X —I O M 00 © O O 0 20. 0^ o -t-> 'E CL J O LO o o - 4 - D _j or O CD* O o O rvl O CM 21. Experiment' I I To gain i n s i g h t i n t o the reason why convergence i s a t t a i n e d more r a p i d l y f o r some regions than f o r others we begin by examining the matrices A of the l i n e a r systems AU=B. .We compare the matrices f o r the other regions w i t h .the m a t r i x Ap f o r the re c t a n g l e f o r which the s p e c t r a l r a d i u s of the i t e r a t i o n m a t r i x i s well-known (see Appendix i ) . R e f e r r i n g to the matrices in'Appendix I I , we see th a t the A-matrices f o r the other regions d i f f e r from A^ by sparse symmetric matrices A,.which we compare as f o l l o w s : Since each element .of the A -matrices i s + 1 we enumerate i n column 2 (Table I I I ) how many.+ 1's o c c u r , . i n the next column how many -1's occur,.take the d i f f e r e n c e s , . r a n k these according to.descending order and compare t h i s order w i t h the descending order of the s p e c t r a l r a d i i p (H). Table I I I - Ranking the Regions According to Number of Non-Zero Elements of A and S p e c t r a l R a d i i of H. Region ..+ l ' s - l ' s ( + l ' s ) > Order Order P of A of A - ( - l ' s ) o f ( * ) Of jO* s R 0 1 .Tiki X 12 Ik -2 2-k 2 •5623 T l 12 Ik -2 2-k • 3 •5klk : 16 20 -k •5 k .5181 L •h 6 -2 2-k 5 • 5145 I . .12 18 -6 6-7 6 .1*665 .U 2. • 8 -6 6-7 7 .4512 0 k ,14 -10 8 8 .2500 From t h i s t a b l e we see th a t the two orderings agree q u i t e c l o s e l y w i t h the exception of regions T2^and L which have very n e a r l y equal yO(H). This i n d i c a t e s t h a t y 3 (H) decreases as the number o f • o f f - d i a g o n a l elements of A decreases. The l a t t e r i s due to an increase i n the number of p o i n t s adjacent t o a boundary, which i n t u r n may be caused by ah increased perimeiter. 22. Now we may ask why p> (H) decreases w i t h the number of o f f - d i a g o n a l elements of A? For a t e n t a t i v e answer we proceed as f o l l o w s : F i r s t we note t h a t f o r matrices w i t h Young's ^'Property A" [k, P.2U3J , the f o l l o w i n g r e s u l t holds [k, p.250] : : Theorem. I : The eigenvalues of the J a c o b i i t e r a t i o n ' ) m a t r i x H.= B "'"(E+F) are r e l a t e d to the eigenvalues of the Gauss-Seidel i t e r a t i o n m a t r i x "H = - (D+E) "'"F as i n d i c a t e d below: g • • x i ( H ] ) x i d v ) X, = 0 ± X i \ ± = 0 Thus, the. s p e c t r a l r a d i u s p (H g) = max | A^Hg) j , i s equal t o the square of the s p e c t r a l r a d i u s p (Hj) = max X^ (Hj ) | i.e. (6.k) ^ ( H g ) = / 0 2 ( H p and as one i n c r e a s e s , so does the other. Consequently i t w i l l s u f f i c e to examine the J a c o b i matrices corresponding t o our regions. This i s advantageous since the H-j are f a r e a s i e r to compute than the Hg. In f a c t the Hj can be obtained q u i t e e a s i l y from the A. We have H. = - i f 1 (E+F) 0 = i (E+F) . 2 5 " 0 .25 25 0 0 F E 0 (*) A l s o known as,the method of simultaneous displacements, wherein a l l the new'values Uj_^ k' are computed only from the o l d values U.(k-l) during each i t e r a t i o n . 23-So, we can get the Hj from the A-matrices i n Appendix I I hy simply r e p l a c i n g a l l the diagonal elements by zeros and the o f f - d i a g o n a l l ' s by 0 .25- The. o f f - d i a g o n a l zeros of course remain u n a l t e r e d . Therefore the Hj f o r non-re c t a n g u l a r regions d i f f e r from Hj f o r the rectan g l e i n e x a c t l y the same manner as the A d i f f e r e d from A^, w i t h the elements 1.0 r e p l a c e d by 0.25 throughout. We next s t a t e p a r t of a theorem due to Perron and Frobenius J9> P ' 3 o ] • Theorem I I : Let A ^ 0 ( a j L j - 0 ; a l l i , j ) be an i r r e d u c i b l e nxn matrix. Then, ( l ) A has a p o s i t i v e r e a l eigenvalue equal to i t s s p e c t r a l r a d i u s ( A ) . (2) p (A) ^increases when any entry of A increases. (3) /°. (A)-.,is a simple eigenvalue of A. Our J a c o b i matrices 'Hj. c e r t a i n l y s a t i s f y the c o n d i t i o n s o f the theorem. (*) I f f o r one Hj each element were J the corresponding element of some other H i , , then we cou l d use p a r t (2) of the theorem t o s t a t e t h a t the s p e c t r a l r a d i u s of the former i s grea t e r than t h a t of the l a t t e r . When comparing Hj f o r the r e c t a n g l e , t o the Hj f o r other regions ( f o r example), t h i s c o n d i t i o n i s not a c t u a l l y met, since i n pa s s i n g t o the • r e c t a n g u l a r region some ma t r i x elements decrease i n each case, although more elements do incr e a s e . Thus the theorem cannot s t r i c t l y be a p p l i e d t o our case. In summary we see t h a t as the shape of a re g i o n i s changed i n such a way -th a t the number of p o i n t s adjacent to the boundary i s increased, then the number of o f f - d i a g o n a l elements In "the A-matrix i s decreased. The same e f f e c t takes (*) at l e a s t one element s t r i c t l y >• 2k. p l a c e i n the J a c o b i i t e r a t i o n m a trices. Since these are non-negative, and i r r e d u c i b l e , t h i s o v e r a l l decrease i n the elements tends to decrease ^ o ' ( l t j ) . Therefore, (Hg) a l s o decreases, because p> (Hg) ,= f> (Hj) f o r matrices w i t h .Property A. Hence the r a t e of convergence r. = - log^o i n t u r n increases and consequently the number of i t e r a t i o n s t o a t t a i n convergence decreases.. T h i s i s a q u a l i t a t i v e and non-rigorous answer to our question and: i t seems th a t "a more s i g n i f i c a n t r e l a t i o n s h i p than Figure 7 shows should be obtained by p l o t t i n g the number o f i t e r a t i o n s r e q u i r e d to decrease the i n i t i a l e r r o r by a given f a c t o r vs. the number of o f f - d i a g o n a l elements i n the ma t r i x A. The l a t t e r q u a n t i t y i s easy t o compute since each p o i n t not adjacent to a boundary c o n t r i b u t e s h elements, each p o i n t i n a 90° corner 2 elements, and other p o i n t s anywhere from 1 - 3 elements, depending on t h e i r l o c a t i o n . The purpose of Experiment I I I was to-do j u s t t h i s . 7- Experiment I I I (a) D e s c r i p t i o n . ' . (k) Here we used an approximation to the e r r o r vector E f o r monitoring convergence, our d e s i r e d c r i t e r i o n b e i n g : (7.1)- |Mk)|| ^ r ( | | E ( 0 ) (k) (k) F i r s t , i t was necessary t o produce the s o l u t i o n U so t h a t E^ = IP - U could be computed. This was done u s i n g a method proposed by Diaz and Roberts ^2 J i n which we begin by choosing i n i t i a l values l/°) and v^0^ i n such a manner t h a t t\j(Q) ^ U ^ 'v(°) . We apply the Gauss-Seidel i t e r a t i o n t o u(°Vand V^ 0) . separ a t e l y and i n t h i s way co n s t r u c t sequences which approach the s o l u t i o n from above and from below r e s p e c t i v e l y . In f a c t we may take U^°) to be the maximum of the boundary values and V^°^ to be t h e i r 25-minimum. We i t e r a t e u n t i l ' (7-2) | | u ( k ) - V ( K )|| £ t3 where t$ i s a given t o l e r a n c e and then take f o r our s o l u t i o n (7-3) U = i (U(k)..+ V ( K ) ) - Then we know th a t (7>^ +) || U - uj| — ~k~^3 •> where we again use the Chebyshev norm. (k) We replaced our f i n a l values of U by the approximate s o l u t i o n and repeated the i t e r a t i o n w i t h the sequence For monitoring convergence we had t o be content w i t h u s i n g the approximate e r r o r vector : (7-5) -E^) = V<K> - U B y choosing the boundary values such t h a t the minimum of U was zero on •.the boundary, we cou l d take V^°^ = Q and then (7.6) l | S ( o ) l l II5 II Thus our a c t u a l convergence c r i t e r i o n was (7.7) ||i<*>|| ^ *Ji<°>| • D e f i n i n g (7.8) E ( k ) = v ( k ) - U I I E ^ H = ||v<k> - u + u - u ± || - U || + || U - U| 6 ||E( k)|| + i t 3 (from (7-U) and (7-5)) S i m i l a r l y , ||EW|| . | | * W - a > u . » | r ± l | v W - u | | + ||u-u|| * .-.-lis 26. Thus we have | | E W | | - ' j|i<k>|| * .n, I I E W I | - || E ( k ) |l > ^ so t h a t by choosing t-^ as small as we l i k e when compared t o t ^ we can make our c r i t e r i o n (7-7) as c l o s e to the d e s i r e d (7'l),as ve l i k e . -k -3 In the experiments we took t3 •= 10 > - t ^ = 10 , w i t h the same regions as i n Experiments I and I I . The graph of the number of i t e r a t i o n s r e q u i r e d to s a t i s f y (7-7) vs.' the number of non-zero o f f - d i a g o n a l e n t r i e s o f A i s p l o t t e d i n Figure 8. (b) R e s u l t s : Key t o .Table IV : - The regions are l a b e l l e d as i n Experiments I and I I . n .= number of non-zero o f f - d i a g o n a l elements i n the corresponding matrices A of AU=B. - kp i s the p r e d i c t e d no. of i t e r a t i o n s ( S 3/_log/° ) • •- k a i s the a c t u a l no. of i t e r a t i o n s observed. Table IV - R e s u l t s f o r Experiment I I I 'Region n k a R-2 10k 12 8 ' "-3 Ilk 20 • 1U .-k 118 27 21 -5 120 •35 30 -6 118 ' -27 27 -7 , • -Ilk 20 21 : -8 •IOU 12 ' 13 L-2 118 '31 28 . -3 116 27 25 : -k ••ilk 23 21 ' -5L 110 19 17 -6 . 1©U •Ik 13 U-2 Ilk 23 22 -3 110 . 20 19 -k 10k •Ik 13 0-2 108 15 15 -3 10U 16 •16 96 - :11 ' 12 -5 92 11 12 -6 . -72 7 7 "1-2 1©U 16 16 -3 ilk 27 27 .101+ , li+ • Ik - -5 ' 108 16 16 -6 92 13 12 X-2 118 32 3k -3 112 27 27 -U 110 23 22 -5 ioU 17 16 T±-2 112 •27 26 T2-2 • 110 27 •26 R - l 3^  13 13 L - l 32 11 l l U - l •28 9 . 9 - 0-1 2k 5 7 1-1 28 10 10 •X-l 32 13 ' ik T l-1 32 '12 12 T 2 - l 30 •11 • -11 28. .or 0 48 O o o 0 c ii < 0 L V N s : o O O OO OO o 00 O OO a: _1 OO 0£ A O T - H 0 . C a. o V O OJ ro — i o . -/ <u - Q O v_/ o O O O O Moo° M O 3 O OO-i o x M a: O o o <0 o 0_ o QJ 00 O o • —' QJ o o ro o rvj O O C/7 4-> QJ 5 QJ UJ o a o 09 > <0 C o •+J d QJ S-o -O 6 Z oo 29-8 . Conclusion As can be seen .from Figure 8 ( a ) , p l o t t i n g the r e q u i r e d number of i t e r a t i o n s . k a against the number of non-zero o f f - d i a g o n a l elements n i n the matrix A of AU=B,is not much of an improvement over p l o t t i n g k a against the perimeter P of the region. Although we have concluded t h a t the perimeter i s not r e a l l y the most s i g n i f i c a n t parameter, i t i s now .clear that f o r regions w i t h a regular-shape (such as the ones we: have considered), there i s very, l i t t l e to choose between usi n g P or n as the a b s c i s s a on,a graph. For r e g u l a r l y shaped regions an.increase i n P w i l l r e s u l t i n a decrease i n n .and v i c e versa. Furthermore our non-rigorous theory has considered only the s i z e ' (number) of the m a t r i x elements and not t h e i r p o s i t i o n i n the matrix. A moments r e f l e c t i o n w i l l i l l u m i n a t e the f a c t that the eigenvalues of a matrix depend not only on the s i z e of the m a t r i x elements but a l s o on t h e i r l o c a t i o n . Thus any,, f u r t h e r attempt at o b t a i n i n g a theory f o r our problem should take t h i s p o s i t i o n i n g of the m a t r i x elements i n t o account and should c o r r e l a t e t h i s w i t h the shape of the region. B e t t e r r e s u l t s have been obtained,.however,, i n the problem of e s t i m a t i n g the number of- i t e r a t i o n s k necessary to s a t i s f y a given convergence c r i t e r i o n , p rovided the s p e c t r a l r a d i u s of the i t e r a t i o n m a t r i x i s known reasonably c l o s e l y . For example i n Figure 4(b), the experimental p o i n t s f i t the curve q u i t e w e l l . The l e s s p r e c i s e r e s u l t • (using the displacement v e c t o r i n d e r i v i n g the expression) p l o t t e d i n Figure 4(a) s t i l l f u r n i s h e s an .approximate upper bound f o r kp i n most cases. This f a c t i s important • i n ' t h i s day of high-speed computing,.because i t a llows one t o estimate computing- time f a i r l y w e l l . F u rther research i n t o our problem should a l s o consider v a r i o u s other e l l i p t i c equations (such as Poissori* Er) and other d i f f e r e n c e approximations (such as the 9-point approximation f o r the L a p l a c i a n ) as w e l l as other 30. i t e r a t i v e methods. . A more c a r e f u l a n a l y s i s o f the i t e r a t i o n matrices might a l s o y i e l d f u r t h e r c l u e s i n the search f o r c h a r a c t e r i s t i c f e a t u r e s of a region which c o n t r o l the r a t e of convergence of an i t e r a t i v e s o l u t i o n . 31-Appendix I. Methods of Determining the S p e c t r a l R a d i i of Gauss-Seidel  I t e r a t i o n M a t r i c e s 1. For r e c t a n g u l a r regions of dimensions a x b, we know from a d e r i v a t i o n .analagous t o t h a t i n Forsythe-and Wasow [k, p.23C>J and the r e l a t i o n ^ ( H g ) = ^ 2 ( E i ) t h a t tn \ i ( TT b TT h v2 /3(H g) ,= u (COS + COS -^r—r ) and i f a = Nh , b = Mh ! , TT TT ,2 f>. = u: (cos — + c o s — ; where N .= number of i n t e r v a l s i n x - d i r e c t i o n M = number of i n t e r v a l s i n y - d i r e c t i o n 2. An approximate i t e r a t i v e method [uj i s t o use one of the f o l l o w i n g l i m i t i n g Y r a t i o s _ H E ( k ) l l , . For our estimate of we take the l a s t a v a i l a b l e r a t i o i n our i t e r a t i v e s o l u t i o n . We used the second r a t i o i n Experiments I and. I I - the obtained values agreed to 3 decimal p l a c e s w i t h other determinations of yD . Since we monitored ||E^^|| i n s t e a d of }|E^ |^| i n Experiment I I I , . t h e r e s u l t s obtained there w i t h the f i r s t r a t i o were somewhat l e s s accurate. The advantage of t h i s method i s t h a t f> i s obtained as a by-product of the i t e r a t i v e s o l u t i o n . The next 3 methods were used f o r Experiment I I only. 3'. A d i r e c t method. F i r s t l y , the Guass-Seidel i t e r a t i o n matrices were computed, w i t h the a i d of an i n v e r s i o n technique f o r t r i a n g u l a r matrices as described i n Bodewig [ 1 ] . Then the Danilevsky-method (see [3] ) was programmed to c a l c u l a t e the c o e f f i c i e n t s of the c h a r a c t e r i s t i c polynomials o f these matrices. 32. These c h a r a c t e r i s t i c polynomials were then,solved f o r . t h e eigenvalues ( r o o t s ) , b y - a U.B.C. Computing Centre l i b r a r y program u t i l i z i n g Bairstow's method (see [T] )• k. A v a r i a n t of method 3* The Danilevsky and Bairstow methods were used i n succession on the corresponding J a c o b i m a t r i c e s , y i e l d i n g eigenvalues of the l a t t e r . The s p e c t r a l r a d i i of. the Gauss-Seidel matrices were then computed from the r e l a t i o n - = This method e l i m i n a t e s the need to.compute the Hg ;.the Hj are very .easy.to w r i t e down, from the A-matrices. 5- Householder's method. Householder's method £7 ] was a p p l i e d to the-symmetric J a c o b i matrices Hj , and as b e f o r e , we used ^ ( H g ) = ( H j ) t o get the s p e c t r a l r a d i i of the Gauss-Seidel matrices. 33. A p p e n d i x I I : M a t r i c e s A o f A U = 8 - f o r E x p e r i m e n t T T R e g i o n - R M a t r i x A A = A - A , • 4 I 1 - 4 I I - 4 4 I I - 4 - 4 I -4 T h e m a t r i c e s b e l o w cLIt-•fer by t h e i n d i c a t e d a m t s . •from t h e A - m a t r i x f o r t h e r e c t a , n ^ u ( . e i r r e g i o n ^ A R . •4- I I -4 L 3 4 . u A A = A - A •4 I I 1 - 4 1 I I - 4 I I I - 4 I I - 4 1 I J 1 - 4 1 I 1 - 4 1 I I - 4 I - 4 I I - 4 - 4 I I - 4 -1 I -I I - I -/ I - I O •4 I I I - 4 I 1 - 4 1 I - 4 I I - 4 I 1 - 4 I I - 4 I I - 4 t I - 4 I / - 4 I I - 4 I I I - 4 - I I - I I - I - I I - I - I - I -I 35. A = A - A •4 I 1 - 4 1 I 1 - 4 1 I I - 4 I - 4 l I I 1 - 4 I / - 4 1 I I - 4 I - 4 I I - 4 I I 1 - 4 1 1 - 4 I -I -1 / -I -I I -I I -I X •4 I I I - 4 I - 4 1 I I 1-4 1 I 1 1 - 4 1 r I - 4 I < - 4 I I 1 - 4 1 I I t - 4 I I J 1 -4 I - 4 I I 1 - 4 -I I --I / I -i I r - i i / -1 - l I -I I I 3G. X A A - A - A -4 -4 I I -4 I -4 I I -4 - 4 I - 4 -4 - 4 - 4 I I - 4 I I - 4 I I -I I -I I I -I I -I I -I 4 I 1 - 4 1 I 1 - 4 1 I 1 - 4 1 | 1 - 4 1 I I - 4 I - 4 1 l 1-4 1 I \ j -4 i i I I - 4 I - 4 I I I -4 -I I I -I i I I - I I -I -I -I i - l -I -I i - l l I -I i - l i i l -I - l - l i -I -I I 37-• B i b l i o g r a p h y E. Bodewig, M a t r i x C a l c u l u s , I n t e r s c i e n c e , New York, 1956. J.B. Diaz and R.C Roberts,=Upper and Lower Bounds f o r the Numerical  S o l u t i o n of the D i r i c h l e t D i f f e r e n c e Boundary Value Problem, J . Math. Phys., vol.31 (1952), pp. .184-191. V.N. Faddeeya, Computational Methods of Lin e a r Algebra ( E n g l i s h t r a n s l a t i o n by CD. Be n s t e r ) , Dover, New York, 1959• G. E.. Forsythe and W.R. Wasow, F i n i t e - D i f f e r e n c e Methods f o r P a r t i a l D i f f e r e n t i a l Equations, Wiley, New York and London, i960. L. Fox ( e d i t o r ) , - Numerical S o l u t i o n of Ordinary•and P a r t i a l D i f f e r e n t i a l Equations, Addison-Wesley, Reading, Palo Alto,.and London, pp. 205-312, 1962. H. B. K e l l e r , On Some I t e r a t i v e Methods f o r S o l v i n g E l l i p t i c D i f f e r e n c e Equations,. Quart. Appl. Math.,. v o l . lto (1958), pp. 209-226. : Modern Computing Methods, Mathematics D i v i s i o n , N a t i o n a l P h y s i c a l Laboratory, H.M.S.O., London,.1961. J . Todd ( e d i t o r ) , - S u r v e y of Numerical!Analysis, McGraw-Hill, New York and San F r a n c i s c o , pp. 380-H-35, 1962. R.S. Varga, M a t r i x I t e r a t i v e A n a l y s i s , - P r e n t i c e ^ H a l l , Englewood C l i f f s , N.J., 1962. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0302300/manifest

Comment

Related Items