Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Stone’s original and symmetric factorization procedure : contrasts and comparisons Kusiak, Robert A. 1974

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

Item Metadata

Download

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

Full Text

S T O N E ' S O R I G I N A L AND S Y M M E T R I C F A C T O R I Z A T I O N P R O C E D U R E : C O N T R A S T S AND C O M P A R I S O N S b y R o b e r t A . K u s i a k B . S c , Q u e e n ' s U n i v e r s i t y a t K i n g s t o n , 1 9 7 1 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T OF T H E R E Q U I R E M E N T S F O R THE D E G R E E OF M A S T E R OF S C I E N C E i n t h e D e p a r t m e n t o f M a t h e m a t i c s We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d s t a n d a r d T H E U N I V E R S I T Y OF B R I T I S H A p r i l , 1 9 7 4 C O L U M B I A 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 o f t h e r e q u i r e m e n t s f o r a n a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l m a k e 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 a n d s t u d y . I f u r t h e r a g r e e 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 p u r p o s e s may b e g r a n t e d b y t h e H e a d o f my D e p a r t m e n t o r b y h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f 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 n o t b e 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 . D e p a r t m e n t T h e U n i v e r s i t y o f B r i t i s h C o l u m b i a V a n c o u v e r 8, C a n a d a A B S T R A C T T h e n u m e r i c a l s o l u t i o n o f e l l i p t i c b o u n d a r y v a l u e p r o b l e m s o n r e c t a n g u l a r r e g i o n s w i t h D i r i c h l e t b o u n d a r y c o n d i t i o n s i s c o n s i d e r e d . T h e w e l l - k n o w n f i n i t e d i f f e r e n c e s c h e m e i s u s e d t o d i s c r e t i z e t h e c o n t i n u o u s p r o b l e m . T h e s o l u t i o n i s n o w e x p r e s s e d a s t h e u n k n o w n v e c t o r i n a h i g h o r d e r m a t r i x e q u a t i o n . I n g e n e r a l , e f f i c i e n t d i r e c t m e t h o d s f o r o b t a i n i n g t h e s o l u t i o n o f t h e m a t r i x e q u a t i o n a r e n o t k n o w n . T h e r e a r e s e v e r a l w e l l - k n o w n i t e r a t i o n s c h e m e s c o m m o n l y u s e d t o s o l v e s u c h p r o b l e m s . T h e m a i n d i s a d v a n t a g e o f t h e s e m e t h o d s i s t h a t t h e n u m b e r o f c o m p u t a t i o n s w h i c h a r e r e q u i r e d t o s o l v e t h e m a t r i x e q u a t i o n i n c r e a s e s i n a n o n -l i n e a r w a y w i t h t h e n u m b e r o f e q u a t i o n s t o b e s o l v e d . S t o n e ' s o r i g i n a l a n d s y m m e t r i c s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e a r e c o n s i d e r e d . T h e k n o w n r e s u l t s c o n c e r n i n g t h e c o n v e r g e n c e p r o p e r t i e s o f e a c h i t e r a t i o n a r e p r e s e n t e d . A n e w r e s u l t c o n c e r n i n g t h e s y m m e t r i c f a c t o r i z a t i o n i s p r e s e n t e d a n d t h e r e s u l t s o f n u m e r i c a l i n v e s t i g a t i o n s a r e p r e s e n t e d . ( i ) T A B L E O F C O N T E N T S A B S T R A C T T A B L E OF C O N T E N T S L I S T OF T A B L E S L I S T OF F I G U R E S A C K N O W L E D G M E N T S I N T R O D U C T I O N C H A P T E R I C H A P T E R I I C H A P T E R I I I 3.1 3.2 3.3 C H A P T E R I V C H A P T E R V B I B L I O G R A P H Y C i ) ( i i ) ( i i i ) ( v ) ( v i ) 1 D E S C R I P T I O N OF T H E P R O B L E M 6 COMMONLY U S E D METHODS OF S O L V I N G S P A R S E L I N E A R S Y S T E M S 2 4 D E S C R I P T I O N OF THE S T R O N G L Y I M P L I C I T M E T H O D 2 8 M o t i v a t i o n o f t h e S t r o n g l y I m p l i c i t M e t h o d 2 8 M e t h o d o f R e s i d u a l C o r r e c t i o n 3 7 S t o n e ' s I t e r a t i o n P r o c e d u r e 4 1 T H E S Y M M E T R I C F A C T O R I Z A T I O N 4 4 R E S U L T S OF N U M E R I C A L E X P E R I M E N T S 6 1 8 1 ( i i ) L I S T OF T A B L E S T A B L E I R e s u l t s f o r V a r i o u s o t . 1 s w h e n S o l v i n g P r o b l e m O n e o n 1 1 x 1 1 M e s h T A B L E I I R e s u l t s f o r V a r i o u s oL 's w h e n S o l v i n g P r o b l e m O n e o n 2 1 x 2 1 M e s h T A B L E I I I R e s u l t s f o r V a r i o u s 0 ^ 1 s w h e n S o l v i n g P r o b l e m O n e o n 3 1 x 3 1 M e s h T A B L E I V R e s u l t s f o r V a r i o u s <* 's w h e n S o l v i n g P r o b l e m O n e o n 4 1 x 4 1 M e s h T A B L E V S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m O n e w i t h B r a c h a - B a r a k a n d S a y l o r ' s V a l u e o f f a n d V a r i o u s oJs T A B L E V I S t o n e ' s O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m O n e T A B L E V I I S t o n e ' s O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m Two T A B L E V I I I S t o n e ' s S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m O n e T A B L E I X S t o n e ' s S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m Two T A B L E X S t o n e ' s O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m T h r e e T A B L E X I S t o n e ' s S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m T h r e e T A B L E X I I E r r o r A f t e r O n e I t e r a t i o n o f O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m F o u r T A B L E X I I I R e s u l t s o f A p p l y i n g S u c c e s s i v e L i n e O v e r R e l a x a t i o n t o P r o b l e m s O n e , Two a n d T h r e e ( i i i ) ( i v ) T A B L E X I V N u m e r i c a l V a l u e s o f L o w e r B o u n d f o r A m i n LT~ (A + W A ) O b t a i n e d b y B r a c h a - B a r a k a n d S a y l o r 7 9 L I S T OF F I G U R E S F I G U R E 1 F I G U R E 2 F I G U R E 3 F I G U R E 4 T h e D o m a i n «_T2_ C o v e r e d w i t h t h e U n i f o r m M e s h 7 S t r u c t u r e o f t h e M a t r i x A 17 T h e S t r u c t u r e o f t h e M a t r i c e s L. a n d U 3 0 , 3 1 S t e n c i l D i a g r a m f o r A l t e r e d E q u a t i o n a t ( j , V; ) M e s h P o i n t 3 3 ( v ) A C K N O W L E D G M E N T S I w i s h t o t h a n k my s u p e r v i s o r , P r o f e s s o r J a m e s M. V a r f o r h i s e x p e r t g u i d a n c e a n d u n e n d i n g e n t h u s i a s m o f f e r e d d u r i n g t h e p r e p a r a t i o n o f t h i s t h e s i s . I a l s o w i s h t o t h a n k t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a M a t h e m a t i c s D e p a r t m e n t f o r t h e f i n a n c i a l a s s i s t a n c e r e c e i v e d d u r i n g t h e p r e p a r a t i o n o f t h i s t h e s i s . I a l s o w i s h t o e x p r e s s my t h a n k s t o M r s . B e v e r l y M i l i n a z z o f o r e f f i c i e n t l y t y p i n g t h e m a n u s c r i p t . ( v i ) I N T R O D U C T I O N I n t h i s t h e s i s we c o n s i d e r a n u m e r i c a l m e t h o d w h i c h c a n b e u s e d t o c a l c u l a t e t h e s o l u t i o n o f a n e l l i p t i c b o u n d a r y v a l u e p r o b l e m . I n p a r t i c u l a r , we w i s h t o c a l c u l a t e t h e v a l u e o f t h e f u n c t i o n m C x , ^ ) a t s e v e r a l p o i n t s w h e r e u . i s t h e s o l u t i o n o f t h e f o l l o w i n g p a r t i a l d i f f e r e n t i a l e q u a t i o n w h e r e |<x a n d a r e t w o g i v e n , s t r i c t l y p o s i t i v e r e a l v a l u e d f u n c t i o n s d e f i n e d o n Si- , & s u f f i c i e n t l y s m o o t h b o u n d e d d o m a i n i n [J? ; w h e r e T i s a i g i v e n r e a l v a l u e d f u n c t i o n a l s o d e f i n e d o n SL a n d U. , t h e s o l u t i o n i s a l s o d e f i n e d o n Si-I n o r d e r t o m a k e t h e s o l u t i o n o f t h i s p r o b l e m u n i q u e t h e v a l u e s o f {j. o n t h e b o u n d a r y o f SL. m u s t b e s p e c i f i e d [ 4 ] . I n s p a r t i c u l a r we m u s t b e g i v e n a f u n c t i o n g d e f i n e d o n t h e b o u n d a r y o f s u c h t h a t T h e s o l u t i o n o f t h e a b o v e p r o b l e m d e s c r i b e s t h e s t e a d y - 1 -- 2 -s t a t e t e m p e r a t u r e d i s t r i b u t i o n i n a t h i n f l a t ^ p l a t e w h e r e f ( * i i s t h e h e a t f l u x a t t h e p o i n t ( x , y ) a n d < j ( v - , t j ) i s t h e t e m p e r a t u r e d i s t r i b u t i o n o n t h e b o u n d a r y o f t h e t h i n p l a t e £ l l j H e r e t h e f u n c t i o n s k x a n d k y r e p r e s e n t t h e c o n d u c t i v i t i e s o f t h e p l a t e i n t h e X a n d y d i r e c t i o n s r e s p e c t i v e l y . We a d m i t t h e p o s s i b i l i t y t h a t t h e c o n d u c t i v i t i e s m a y b e f u n c t i o n s o f t h e l o c a t i o n o n t h e p l a t e a n d m a y n o t b e e q u a l a t a n y p o i n t o n t h e p l a t e . I n C h a p t e r I we d e s c r i b e t h e u s u a l f i n i t e d i f f e r e n c e a p p r o a c h u s e d t o s o l v e e l l i p t i c b o u n d a r y v a l u e p r o b l e m s . T h e d o m a i n J~l_ i s c o v e r e d b y a r e c t a n g u l a r m e s h a n d a t p o i n t s o f i n t e r s e c t i o n o f t h e l i n e s o f t h e m e s h t h e d e r i v a t i v e s i n t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n a r e r e p l a c e d b y t h e u s u a l d i f f e r e n c e q u o t i e n t a p p r o x i m a t i o n s . H e n c e , a t e a c h m e s h p o i n t t h e o r i g i n a l c o n t i n u o u s p r o b l e m i s r e p l a c e d b y a d i s c r e t e p r o b l e m . N a m e l y , a t e a c h m e s h p o i n t we r e p l a c e t h e p a r t i a l d i f f e r e n t i a l e q u a t i o n b y a l i n e a r e q u a t i o n a n d o b t a i n a s e t o f l i n e a r e q u a t i o n s t o s o l v e . I n p r a c t i c e , t h e m e s h m a y b e v e r y f i n e s o t h a t t h e r e a r e a l a r g e n u m b e r o f e q u a t i o n s t o s o l v e . T h e f i n e m e s h i s u s e d i n o r d e r t o o b t a i n m o r e a c c u r a t e a p p r o x i m a t i o n s t o t h e s o l u t i o n o f o u r o r i g i n a l p r o b l e m . - 3 -T h e l a r g e n u m b e r o f e q u a t i o n s t o b e s o l v e d p r e c l u d e s t h e u s e o f t h e w e l l - k n o w n G a u s s i a n E l i m i n a t i o n m e t h o d s i n c e t h e t i m e r e q u i r e d m a y b e o f t h e o r d e r o f d a y s . F o r t h i s r e a s o n , a n i t e r a t i o n t e c h n i q u e i s u s u a l l y u s e d . I n g e n e r a l , a n i t e r a t i o n t e c h n i q u e g e n e r a t e s a s e q u e n c e o f a p p r o x i m a t e s o l u t i o n s , c o n v e r g i n g t o t h e s o l u t i o n o f o u r l i n e a r s e t o f e q u a t i o n s . T h e s e q u e n c e i s fce'r.m.Mated w h e n t h e a c c u r a c y o f t h e a p p r o x i m a t i o n i s s u f f i c i e n t l y s m a l l . I n C h a p t e r I I w e r e p o r t t h e e s t i m a t e s o f t h e n u m b e r o f c a l c u l a t i o n s r e q u i r e d t o r e d u c e t h e e r r o r b y a g i v e n a m o u n t f o r a v a r i e t y o f w e l l - k n o w n i t e r a t i o n t e c h n i q u e s . I n C h a p t e r I I I w e c o n s i d e r S t o n e ' s s t r o n g l y i m p l i c i t f a c t o r i z a t i o n t e c h n i q u e £ l l ] . T h i s i s a n e f f i c i e n t a l g o r i t h m f o r s o l v i n g t h e l a r g e s e t s o f l i n e a r e q u a t i o n s w h i c h a r i s e f r o m d i s c r e t i z i n g a n e l l i p t i c b o u n d a r y v a l u e p r o b l e m . T h e m e t h o d i s m o t i v a t e d b y t h e f a c t t h a t t h e G a u s s i a n E l i m i n a t i o n p r o c e d u r e i s e q u i v a l e n t t o f a c t o r i n g t h e m a t r i x t o b e s o l v e d i n t o t h e p r o d u c t o f a l o w e r a n d u p p e r t r i a n g u l a r m a t r i x ^ 9 ^ . I f t h e n t w o m a t r i c e s c a n b e f o u n d e x p l i c i t l y t h e n t h e s o l u t i o n o f t h e m a t r i x e q u a t i o n i s e a s i l y o b t a i n e d b y f o r w a r d a n d b a c k w a r d s u b s t i t u t i o n . I n o u r c a s e , t h e m a t r i x t o b e s o l v e d h a s o n l y a v e r y f e w n o n - z e r o e n t r i e s w h i l e t h e l o w e r a n d u p p e r t r i a n g u l a r m a t r i c e s w i l l - 4 -h a v e a l a r g e n u m b e r o f n o n - z e r o e n t r i e s . S t o n e a t t e m p t e d t o f i n d l o w e r a n d u p p e r t r i a n g u l a r m a t r i c e s w i t h o n l y a a s m a l l n u m b e r o f n o n - z e r o e n t r i e s . T h e m a t r i x p r o d u c t o f t h e s e t w o t r i a n g u l a r m a t r i c e s i s t h e e x a c t f a c t o r i z a t i o n f o r a m a t r i x c l o s e t o t h e o r i g i n a l m a t r i x we w i s h t o s o l v e . I n o r d e r t o f u r t h e r i m p r o v e t h e a c c u r a c y o f t h e s o l u t i o n , S t o n e u s e d t h e w e l l - k n o w n m e t h o d o f r e s i d u a l c o r r e c t i o n , [ 9 ] a s t h e b a s i s o f a n i t e r a t i o n s c h e m e . T h e v i r t u e o f S t o n e ' s m e t h o d i s t h a t f o r s o m e p r o b l e m s , t h e n u m b e r o f i t e r a t i o n s r e q u i r e d t o o b t a i n a n a p p r o x i m a t e s o l u t i o n s u f f i c i e n t l y c l o s e t o t h e d e s i r e d s o l u t i o n i s i n d e p e n d e n t o f t h e n u m b e r o f e q u a t i o n s t o b e s o l v e d . T h i s i s i n s h a r p c o n t r a s t t o t h e u s u a l i t e r a t i o n t e c h n i q u e s f o r w h i c h t h e n u m b e r o f i t e r a t i o n s r e q u i r e d t o s o l v e t h e m a t r i x e q u a t i o n s i n c r e a s e s s h a r p l y w i t h t h e o r d e r o f t h e m a t r i x e q u a t i o n . [^ 6 T h e c o n v e r g e n c e p r o p e r t i e s o f t h e i t e r a t i o n a r e n o t w e l l - u n d e r s t o o d a n d a n a l y s i s i s m a d e d i f f i c u l t b y t h e l a c k o f s y m m e t r y i n t h e p e r t u r b e d m a t r i x . S u b s e q u e n t l y , S t o n e i n t r o d u c e d t h e s y m m e t r i c f a c t o r i z a t i o n | ~ l j w h i c h i s c o m p a r a b l e t o t h e o r i g i n a l u n s y m m e t r i c f a c t o r i z a t i o n a n d h a s t h e v i r t u e o f b e i n g m o r e e a s i l y a n a l y z e d . I n C h a p t e r I V w e p r e s e n t t h e s y m m e t r i c p r o c e d u r e a n d d i s c u s s o n e a t t e m p t t o a n a l y z e t h e c o n v e r g e n c e p r o p e r t i e s o f a n i t e r a t i o n s c h e m e u s i n g t h e s y m m e t r i c f a c t o r i z a t i o n . - 5 -We a l s o p r e s e n t s o m e r e s u l t s w h i c h w i l l b e n e e d e d i n a p r o o f o f t h e c o n v e r g e n c e p r o p e r t i e s o f t h e s y m m e t r i c f a c t o r i z a t i o n p r o c e d u r e . T h e p r o o f o f t h e c o n v e r g e n c e p r o p e r t i e s o f t h e s y m m e t r i c f a c t o r i z a t i o n p r o c e d u r e i s n o t a v a i l a b l e a l t h o u g h s o m e p a r t i a l r e s u l t s d u e t o D i a m o n d a r e a v a i l a b l e . I n C h a p t e r V we p r e s e n t a . d e t a i l e d n u m e r i c a l i n v e s t i g a t i o n s a n d c o m p a r i s o n s o f t h e t w o f a c t o r i z a t i o n p r o c e d u r e s . We a l s o c o m p a r e t h e e f f e c t i v e n e s s o f t h e f a c t o r i z a t i o n p r o c e d u r e s w i t h o n e s t a n d a r d a n d w e l l - u n d e r s t o o d i t e r a t i o n p r o c e d u r e . I n e a c h c a s e c o n s i d e r e d t h e s u p e r i o r i t y o f t h e s t r o n g l y i m p l i c i t p r o c e d u r e i s c l e a r l y d e m o n s t r a t e d . C H A P T E R I D E S C R I P T I O N O F T H E P R O B L E M L e t SL b e a n o p e n b o u n d e d r e g i o n i n I R . L e t k x a n d k*f b e t w o r e a l v a l u e d , s t r i c t l y p o s i t i v e d i f f e r e n t i a b l e f u n c t i o n s d e f i n e d o n J l . L e t b e a r e a l v a l u e d f u n c t i o n d e f i n e d o n - J L , a n d l e t 9 b e a r e a l v a l u e d f u n c t i o n d e f i n e d o n t h e b o u n d a r y o f -S2. . We w i s h t o f i n d a r e a l - v a l u e d f u n c t i o n d d e f i n e d o n w h i c h s a t i s f i e s t h e f o l l o w i n g c o n d i t i o n s . ( kxcx,«_)u x(x._))jt + ( k y c x . w ) 8 5 T-CX.IJ) , I f o r ( x , y ) £ - J L . a n d , F o r k x a n d k y b o t h s t r i c t l y p o s i t i v e a n d f o r a s u f f i c i e n t l y s m o o t h b o u n d a r y i t i s w e l l k n o w n t h a t t h e r e i s a u n i q u e s o l u t i o n t o ( 1 . 1 ) . [ ^ ] . I n m a n y c a s e s , t h e n u m e r i c a l v a l u e s o f U ( J C i " _ ) a r e d e s i r e d a t s e v e r a l p o i n t s i n s i d e SK . We b e g i n b y c o v e r i n g .51-w i t h a u n i f o r m r e c t a n g u l a r m e s h . L e t A X b e t h e d i s t a n c e b e t w e e n v e r t i c a l l i n e s o f t h e m e s h a n d l e t & y b e t h e d i s t a n c e b e t w e e n - 6 -- 7 -h o r i z o n t a l m e s h l i n e s . T h e u n i f o r m r e c t a n g u l a r m e s h i s s h o w n i n F i g u r e 1 . y Si-Fig. 1 T h e D o m a i n _ f L . C o v e r e d w i t h t h e U n i f o r m M e s h T h e p o i n t o f i n t e r s e c t i o n o f t w o m e s h l i n e s i s c a l l e d a m e s h p o i n t . We w i s h t o f i n d t h e v a l u e o f t h e s p l u t i o n t o ( 1 . 1 ) a t t h e m e s h p o i n t s l y i n g i n s i d e Si- . F o r e a c h m e s h p o i n t l y i n g i n s i d e Si. a n d h a v i n g e a c h o f i t s f o u r n e a r e s t m e s h p o i n t s a l s o l y i n g i n J l . w e c a n a p p r o x i m a t e t h e p a r t i a l d e r i v a t i v e s o f U . £' **! 3 < T h e a p p r o x i m a t i o n , c a l l e d a d i f f e r e n c e q u o t i e n t , e x p r e s s e s t h e p a r t i a l d e r i v a t i v e i n t e r m s o f a l i n e a r c o m b i n a t i o n o f t h e v a l u e s o f t h e f u n c t i o n a t t h e m e s h p o i n t a n d a t t h e f o u r n e a r e s t - 8 -n e i g h b o u r i n g m e s h p o i n t s . T h e a p p r o x i m a t i o n i s f o u n d b y u s i n g a T a y l o r S e r i e s e x p a n s i o n o f t h e f u n c t i o n a b o u t t h e m e s h p o i n t . We b e g i n b y d e r i v i n g t h e d i f f e r e n c e q u o t i e n t a p p r o x i m a t i o n t o a n a r b i t r a r y r e a l v a l u e d f u n c t i o n \jr , w h i c h h a s b o u n d e d f o u r t h d e r i v a t i v e s . U s i n g T a y l o r S e r i e s we o b t a i n t h e f o l l o w i n g e x p r e s s i o n . v r ( x * A x , y ) = u -u .y ) + I v r u.u) A X +- lAx ) * . T " vi*,*) ax 3 T " Jy* B y a n o b v i o u s s i m p l i f i c a t i o n w e h a v e t h a t H e n c e , i f u~ h a s b o u n d e d f o u r - t H d e r i v a t i v e s t h e n S i m i l a r l y w e c a n s h o w t h a t t h e f o l l o w i n g e q u a t i o n h o l d s . - 9 b a x 3 Z4- <Jx* S u b t r a c t i n g ( 1 . 5 ) f r o m ( 1 . 3 ) w e o b t a i n a s e c o n d o r d e r d i f f e r e n c e q u o t i e n t f o r t h e f i r s t p a r t i a l o f \T i n t h e X d i r e c t i o n . t/-fx+AX,H) - vr(x-Ax,4) - L ^ l * . * ) *<___U*s__jr(x. _,) Z AX t i X 3 ( I t ) I f V h a s b o u n d e d f o u r t h d e r i v a t i v e s t h e n u- (. x-t-AX.M - ir(x-&*\M) i » r ( y , . ) + 0((Ax)**j 2. A X C^X L e t U x ( * ' _ t ' ) - I T ( X + A X , «j ) - ^  f X, _)) A X L e t tr- .x.^ - trfx,4) - tr.X-AX,*,) A X L e t I T * .X. 1,) = LT (X-4-AX.M) - t r / X - A - X , t _ ) We c a l l VT y , ^ a n d i r ~ t h e f o r w a r d , b a c k w a r d a n d c e n t r e d d i f f e r e n c e q u o t i e n t s o f \r i n t h e X d i r e c t i o n . We c a n a l s o o b t a i n d i f f e r e n c e q u o t i e n t s w h i c h a p p r o x i m a t e - 1 0 -t h e s e c o n d p a r t i a l d e r i v a t i v e o f IT i n t h e X d i r e c t i o n a t t h e m e s h p o i n t <X*y) . B y a d d i n g ( 1 . 3 ) a n d ( 1 . 5 ) we o b t a i n t h e f o l l o w i n g e x p r e s s i o n . ir(x»AX,q) -2u-(x,«j) + ^ -fx-ax,y) _ 4ZIU-(X.H) -t- (&xl IT (v-t- e» »x, H ) I^|<1 -.£|.7) I f VT h a s b o u n d e d f o u r t h ' d e r i v a t i v e s t h e n t h e e x p r e s s i o n o n t h e l e f t o f ( 1 . 7 ) i s a s e c o n d o r d e r d i f f e r e n c e q u o t i e n t a p p r o x i m a t i o n t o t h e s e c o n d p a r t i a l o f IT a t t h e p o i n t (n,«j) i n t h e X d i r e c t i o n . We c a n a l s o o b t a i n t h i s d i f f e r e n c e q u o t i e n t i n a n o t h e r w a y b y u s i n g t h e f o r w a r d a n d b a c k w a r d d i f f e r e n c e q u o t i e n t s . l^xx (x.vj) = / u - f x ^ ) - V (x-fcx, ^)\ I &X 'X. - u~(x-n>x,tj \ — z i r ( X c ^ ) + ir|x+-&x, ^  ) C A X ) 2 -I t i s c l e a r t h a t t h e d i f f e r e n c e q u o t i e n t s f o r t h e p a r t i a l d e r i v a t i v e s o f y i n t h e y d i r e c t i o n a r e f o u n d i n t h e s a m e m a n n e r a s t h o s e i n t h e X d i r e c t i o n . We n o w d e r i v e b o t h t h e d i f f e r e n c e q u o t i e n t a p p r o x i m a t i o n t o ( 1 . 1 ) a n d t h e l o c a l t r u n c a t i o n e s t i m a t e . - 1 1 -B e f o r e w e b e g i n , t h e f o l l o w i n g r e s u l t w i l l p r o v e u s e f u l . U s i n g T a y l o r S e r i e s w e c a n w r i t e kx(x+-^r,y) * kx<x.f) •*- **kx x(x.y) +• IAXJ* kx X K (x + e5 *x,y) (l-8) w h e r e I G5I < '/Z , a n d we c a n w r i t e k x ( x - ^ . y ) - kx(x^) - £ x k x x (x,y) -4- l&xj • kxXJt(x*etAx,yJ fi-*J 2. 8 w h e r e | © b | < . A d d i n g ( 1 . 8 ) a n d ( 1 . 9 ) g i v e s u s t h e f o l l o w i n g r e s u l t kx(x*-^,^|) -H Vrx(x- ^ = 2 k x ( x . « j ) + ^ f k x x x ( x + - © 7 A x , y J « 4 w h e r e We c a n n o w o b t a i n t h e u s u a l d i f f e r e n c e q u o t i e n t a p p r o x i m a t i o n f o r t h e d e r i v a t i v e s i n ( 1 . 1 ) . (kx(x,^)u x(x, v))x - I kx( x + % , y ) - r fc»(x-^»y) - (AX)* kx^w-T. \ 24. / \ 2 A X G / - 1 2 -u ( X T - A x , y ) - 2 u u } y ) +- UU-AX.S ) _ (Axf"uXx(**-1VAx,y) IA*)2- 12. "(AXJ1" ( i kxx(x,v) UxxxCx+fr-WCV) + - i - K x x ^ + r ' ^ ' Y ^ U*(W) + u UxK^Ax.vflkxlx,^) + 8 kx x x (x+r3^ ,v)uxx ^vv;) + (9 l(Axf) - CAX) (kx(x^ iyjlu(xi-&x/v)-u(x,y)) U^(X-^ /)(U(X-AX,V)- UM)) - (Axf (t bx(x,v,)uAx^  o - 13 -w h e r e | %\ ^ 1 , t = 1,2,?, t . We o b t a i n t h e 6 t e r m i f t h e s o l u t i o n t o ( 1 . 1 ) h a s b o u n d e d f o u r t h p a r t i a l s w i t h r e s p e c t t o X a n d h a s b o u n d e d s e c o n d p a r t i a l s w i t h r e s p e c t t o X S i m i l a r l y we c a n o b t a i n t h a t (lOj(x,Y)ciy(xfl))y " (Av)"x(kv(x,v+^K^^+ )^ -a(^ y)) k y ( x , w - * i ) ( u ( M - * y ) -«(*//)) - (*y)"(~t kyv ( u V Y v (*> v + + A k iv/xi*Mi£>y<x.yJ H e n c e a t e a c h m e s h p o i n t w h i c h l i e s o n _£?_ a n d h a s i t s f o u r n e a r e s t n e i g h b o u r i n g m e s h p o i n t s l y i n g i n s i d e , we r e p l a c e ( 1 . 1 ) b y t h e f o l l o w i n g l i n e a r e q u a t i o n . ^ T(X ( N) •^••2.) I f t h e m e s h p o i n t (x,y) h a s o n e o r m o r e o f i t s f o u r n e a r e s t n e i g h b o u r i n g m e s h p o i n t s l y i n g o u t s i d e t h e b o u n d a r y o f - / L , - 1 4 -t h e n t h e a b o v e a p p r o x i m a t i o n m u s t b e m o d i f i e d s o t h a t t h e f u n c t i o n U i s e v a l u a t e d o n l y a t p o i n t s l y i n g i n ~SL . [ ^ ] . I n o r d e r t o a v o i d t h i s p r o b l e m , w e w i l l c o n s i d e r o n l y r e c t a n g u l a r d o m a i n s o f l e n g t h q a n d w i d t h b I f t h e m e s h p o i n t h a s a n e a r e s t n e i g h b o u r i n g m e s h p o i n t l y i n g o n t h e b o u n d a r y o f , t h e n t h e v a l u e o f u i s k n o w n a t t h a t p o i n t a n d t h e n u m b e r o f u n k n o w n v a r i a b l e s i n t h a t e q u a t i o n i s r e d u c e d b y o n e . I n t h e c a s e o f a r e c t a n g u l a r d o m a i n , w e w i l l p u t n m e s h l i n e s i n t h e X d i r e c t i o n a n d n m e s h l i n e s i n t h e *y Q t d i r e c t i o n s o t h a t A X = " f v f l a n c^ ~ rn-1 • We u s e t h e u s u a l c o n v e n t i o n t o l a b e l t h e g r i d p o i n t s : w e u s e (j, k ) t o i n d i c a t e t h e m e s h p o i n t ( j A X , , k A y ) I n o r d e r t o f u r t h e r s i m p l i f y t h e w r i t i n g o f ( 1 . 1 2 ) w e m a k e t h e f o l l o w i n g d e f i n i t i o n s . D e f i n i t i o n s : L e t L e t L e t L e t B j , K = ky(j AX, ( k - t ) A y ) , j , k ^ ' . * > - - . , n EJ.K = i^ (kx((o+^ Ax^ y) r k x ( ( j - i ) A x ; k A y ) +- T£J (ky (j AX, (k*iO ^ ) + kv / ( . jl*., (k-iVy)), - 15 -M u l t i p l y i n g e q u a t i o n ( 1 . 1 2 ) t h r o u g h b y — APCAy a n d u s i n g t h e p r e v i o u s d e f i n i t i o n s we h a v e t h e f o l l o w i n g s e t o f l i n e a r e q u a t i o n s . T h e n o t a t i o n U_,_k. •*-s b e i n g u s e d t o i n d i c a t e U C j > ^^V^j t h e s o l u t i o n o f o u r d i s c r e t e p r o b l e m a t t h e m e s h p o i n t ( j . > k ) . + "Bj.v^ U j ) t e + , = <^ i , k i j , k - u , . . . . n • ( l | 3 ) T h e b o u n d a r y t e r m s a r e n o w f i t t e d t o t h e s e t o f e q u a t i o n s i n ( 1 . 1 3 ) . I f J s 1 , t h e n k. l i e s o n t t h e b o u n d a r y l i n e X—Q a n d we h a v e t h a t U j _ j ^  =• ^ • H e n c e , w e s e t "D(,ic=0 a n d a d d ^ ( O j k a ^ ) kx.((j-_J&X. t o t h e r i g h t h a n d s i d e o f t h e e q u a t i o n . S i m i l a r p r o c e d u r e s a r e u s e d o n t h e t h r e e o t h e r b o u n d a r y z l i n e s o f t h e r e c t a n g l e . We a r e n o w l e f t w i t h H e q u a t i o n s o f t h e •L t y p e i n ( 1 . 1 3 ) a n d we w i s h t o f i n d t h e s o l u t i o n t o ( 1 . 1 ) a t t h e Y\ m e s h p o i n t s l y i n g i n s i d e A f t e r f i t t i n g t h e b o u n d a r y t e r m s t o t h e s e t o f l i n e a r e q u a t i o n s we n o t e t h e f o l l o w i n g p r o p e r t i e s o f t h e c o e f f i c i e n t s i n ( 1 . 1 3 ) - 1 6 -k4 /, k+ n+l ; j = I.Xi • ,n k= i , k. - n-+-<j j i i . i , . . . , n We u s e t h e u s u a l o r d e r i n g o f t h e e q u a t i o n s b y r o w s . T h e e q u a t i o n s a s s o c i a t e d w i t h t h e m e s h p o i n t ^ j ' J ^ ' " ) p r e c e d e s t h e e q u a t i o n a s s o c i a t e d w i t h t h e m e s h p o i n t ^ j i . ) k*-) i f e i t h e r k < k__ o r k j . = kz. a n d j , < j i • F i g u r e 1 p r e s e n t s t h e m a t r i x o f c o e f f i c i e n t s /\ , w i t h t h e a b o v e o r d e r i n g . F r o m n o w o n , w e w i l l r e f e r t o e n t r i e s i n t h e m a t r i x b y s p e c i f y i n g t h e c o o r d i n a t e s o f t h e m e s h p o i n t t o w h i c h t h e r o w i n t h e m a t r i x c o r r e s p o n d s . L e mma 1 . 1 ; W i t h t h e a b o v e o r d e r i n g o f t h e l i n e a r e q u a t i o n s , A i s a s y m m e t r i c a n d p o s i t i v e d e f i n i t e . F i g . 2 S t r u c t u r e o f t h e M a t r i x A P r o o f : To s e e t h e s y m m e t r y o f A , s e e F i g u r e 2. T o s h o w t h a t A i s p o s i t i v e d e f i n i t e we m u s t s h o w t h a t f o r a n y X IJ\ , X+Op XTAx?0. A t y p i c a l e n t r y i n Ax i s : M u l t i p l y i n g o n t h e l e f t b y ^( g i v e s t h a t - 1 8 -R e c a l l i n g t h e p r o p e r t i e s o f t h e e n t r i e s i n t h e m a t r i x J\ a n d c h a n g i n g t h e i n d e x o f s u m m a t i o n i n t h e s e c o n d a n d t h i r d s u m m a t i o n s i n ( 1 . 1 4 ) g i v e s u s t h e f o l l o w i n g e x p r e s s i o n f o r x rAx. X r Ax * 21 7Z ESMx]x + z 2 T £ : B i l k 4 , x i . i c X , w , "*-|^f'|Ei.w.Xi'ivc+ ^ i B i ^ C x ^ t x ^ ) + ? ^ k ^ ( x ^ ^ / ) - 1 9 -R e c a l l i n g t h e d e f i n i t i o n s o f "Bj.Vc'j ^S,lc anc^ w e n a v e t n e f o l l o w i n g e x p r e s s i o n f o r t h e l a s t t h r e e s u m m a t i o n s i n ( 1 . 1 5 ) . J : l t=| J-I **•' H e n c e we h a v e t h a t xTAx = t . [ f . ^ tafrjtt ( X i H . i t - X i j c r - t - f t Iwi.kX^c AX I t i s w e l l k n o w n t h a t t h e q u a n t i t y i n t h e c u r l y b r a c k e t s i s t h e e x p r e s s i o n f o r X^A^X w h e r e Aj) i s t h e d i s c r e t e 2 0 -L a p l a c e o p e r a t o r a n d t h a t Z(tv»D ) xTx [ <f ]. H e n c e f o r X ^ O , we h a v e t h a t J t V c i - i t ) O.E.-D. We d e n o t e t h e r i g h t h a n d s i d e o f t h e e q u a t i o n s i n ( 1 . 1 3 ) b y . We c a n w r i t e t h e m a t r i x e q u a t i o n a s A U - C[ 0-17) S i n c e /\ i s p o s i t i v e d e f i n i t e , A ' e x i s t s a n d t h e r e i s a u n i q u e s o l u t i o n t o ( 1 . 1 7 ) . S u p p o s e t h a t we c a n f i n d t h e U w h i c h s o l v e s ( 1 . 1 7 ) e x a c t l y . I s t h e v a l u e o f t h e s o l u t i o n t o ( 1 . 1 ) a t t h e m e s h p o i n t J^(k) ? I n g e n e r a l , t h e a n s w e r i s n o . E x c e p t i n t h e c a s e w h e r e t h e s o l u t i o n t o ( 1 . 1 ) i s a l i n e a r f u n c t i o n o f X a n d y , t h e v a l u e o f t h e s o l u t i o n o f ( 1 . 1 ) a t £j,lc) a n d t h e v a l u e Uj ^ , t h e s o l u t i o n o f ( 1 . 1 7 ) a t (j,k) w i l l d i f f e r b y & ( & X +A^ | . We c a n u s e ( 1 . 1 0 ) , ( 1 . 1 1 ) a n d ( 1 . 1 6 ) t o s h o w t h i s r e s u l t . We u s e t h e u s u a l m e t h o d \_ °\ ] o f o b t a i n i n g t h e u p p e r b o u n d o n \\ U - LK l| ^ . We b e g i n b y d e f i n i n g (, ^ U ^>y)J t o b e t h e l o c a l t r u n c a t i o n e r r o r a t t h e m e s h p o i n t - 2 1 -w h e r e U i s t h e e x a c t s o l u t i o n o f ( 1 . 1 ) . N o t e t h a t AX-Z^ M A X A y L e t b e t h e v e c t o r o f l o c a l t r u n c a t i o n e r r o r s , t h e n we c a n w r i t e V - A ( a-u) AX Ay a n d h e n c e u - u =. A X Ay. A 1 T T a k i n g $ x n o r m s , we h a v e t h a t Hu-Ti% i Ax-AvllA-'II^ JITlt^  We k n o w t h a t (I A" II * - — _ F r o m e q u a t i o n s ( 1 . 1 0 ) a n d ( 1 . 1 1 ) we h a v e t h a t + fe«vy(x,yM¥Ay)kY(x,Y)^ ifkyvv(x,Y+*J *y)u„M] H e n c e [ 7 \  u l*H ?j| — ( A X) + ( ^ V J Z ^ i WUA*( ( k y y U Y V Y | ) + ^  K > u ^ C | k y Y y 6 < v O 4- 7a>m».x(|u V y kMl) 4- i? max f|k W y y u Vy 1^4- (5'((^x;++CA4)^) a n d (IT||^ i n ( i i x f jimax(|kxKuXxl)+^ rw»A(|fcxAJtJ f«A|) • -+ n^( lWVwU Y |) + fe HwxOu V v ty!)+-^m(xxOk«yyy«yy/)| H e n c e r e c a l l i n g t h a t flX = q a n d A w - b . we h a v e t h a t - 23 -+ ^  r V O x ( ( k 4 y H U M |) +- rVUX^ClUy^kv/l) +• £ r>«*X C l ^ v < M «Vv< ' a l o•(;2TT • ^ - J " ' ( ^ i ^ ( | : ^ ; ^ ^ ^ ) ) " , H e n c e a s KI—•>•© we h a v e t h a t C i j . k ? U j ( f c ; . N o t e t h e n , t h a t t h e s o l u t i o n t o ( 1 . 1 7 ) d i f f e r s f r o m t h a t o f ( 1 . 1 ) b y t e r m s o f a n d h e n c e t h e c a l c u l a t i o n o f t h e e x a c t s o l u t i o n t o ( 1 . 1 7 ) i s w a s t e f u l . W i t h t h i s i n m i n d , we c o n s i d e r s e v e r a l m e a n s o f " c a l c u l a t i n g " t h e s o l u t i o n t o ( 1 . 1 7 ) . C H A P T E R I I COMMONLY U S E D METHODS OF S O L V I N G S P A R S E L I N E A R S Y S T E M S G a u s s i a n e l i m i n a t i o n i s o n e w e l l k n o w n m e t h o d o f s o l v i n g s y s t e m s o f l i n e a r e q u a t i o n s . I f t h e b a n d e d s t r u c t u r e o f o u r /\ i n ( 1 . 1 7 ) i s t a k e n i n t o a c c o u n t , t h e n G a u s s i a n e l i m i n a t i o n r e q u i r e s OCfl^) o p e r a t i o n s t o s o l v e ft* l i n e a r e q u a t i o n s . F o r o u r m a t r i x e q u a t i o n w i t h n = l i O O O t h e s o l u t i o n r e q u i r e s 0(10**) o p e r a t i o n s o r 0(lOb) s e c o n d s o n t h e I B M 3 6 0 - 6 7 a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a . T h i s l a r g e a m o u n t o f c o m p u t a t i o n a l e f f o r t i s w a s t e d s i n c e t h e e x a c t s o l u t i o n t o ( 1 J 1 7 ) s t i l l d o e s n o t g i v e t h e e x a c t s o l u t i o n t o ( 1 . 1 ) a t e a c h m e s h p o i n t . H e n c e , a n i t e r a t i o n t e c h n i q u e w h i c h g e n e r a t e s a s e q u e n c e o f a p p r o x i m a t i o n s c o n v e r g i n g t o t h e s o l u t i o n o f ( 1 . 1 7 ) i s s u p e r i o r t o G a u s s i a n e l i m i n a t i o n i f t h e n u m b e r o f o p e r a t i o n s p e r i t e r a t i o n i s s m a l l a n d t h e c o n v e r g e n c e i s r a p i d . T h e i t e r a t i o n c a n b e h a l t e d w h e n t h e e r r o r b e t w e e n t h e i t e r a t e a n d t h e t r u e s o l u t i o n i s - 25 -o f t h e s a m e o r d e r a s t h e e r r o r i n t r o d u c e d b y u s i n g d i f f e r e n c e q u o t i e n t s . O n e w e l l k n o w n i t e r a t i o n t e c h n i q u e i s s u c c e s s i v e - o v e r -r e l a x a t i o n , o r SOR. f ^ ] • T h i s i t e r a t i o n t e c h n i q u e i s e f f i c i e n t i f t h e r e q u i r e d e r r o r r e d u c t i o n i s s m a l l ; i t h a s t h e a d v a n t a g e s o f b e i n g w e l l u n d e r s t o o d a n d e a s y t o a p p l y . M o r e o v e r , i t c a n b e u s e d o n i r r e g u l a r l y s h a p e d d o m a i n s . To r e d u c e t h e i n i t i a l e r r o r b y a f a c t o r o f fl "^ r e q u i r e s o p e r a t i o n s w h e n s o l v i n g t h e L a p l a c e e q u a t i o n . £ ] • A n o t h e r w e l l k n o w n i t e r a t i o n t e c h n i q u e i s t h e P e a c e m a n - R a c h f o r d a l t e r n a t i n g d i r e c t i o n s i m p l i c i t i t e r a t i o n ( A . D . I ) [ cf ] . A g a i n A D I i s w e l l u n d e r s t o o d b u t a m e t h o d f o r c h o o s i n g t h e r e q u i r e d s e q u e n c e o f o p t i m a l p a r a m e t e r s i s n o t k n o w n f o r p r o b l e m s o t h e r t h a n t h e d i s c r e t e L a p l a c e e q u a t i o n . T h i s m e t h o d o f f e r s s u b s t a n t i a l i m p r o v e m e n t o v e r S O R i n t h a t i t r e q u i r e s (5 ( n ( l o ^ n ) ) o p e r a t i o n s t o r e d u c e t h e i n i t i a l -Z e r r o r b y a f a c t o r o f • t\ w h e n s o l v i n g t h e d i s c r e t e L a p l a c e e q u a t i o n , \_ & ] . T h e r e a r e a v a r i e t y o f d i r e c t m e t h o d s u s e d t o s o l v e t h e d i s c r e t e L a p l a c e e q u a t i o n o n r e c t a n g u l a r r e g i o n s . £ 3 J« T h e y r e l y h e a v i l y o n t h e r e g u l a r r e p e t i t i o n o f t h e s a m e b l o c k s u b -m a t r i c e s w i t h i n t h e d i s c r e t e L a p l a c e o p e r a t o r . O n e s u c h m e t h o d - 26 -d u e t o B u n e m a n £ 2. ] y i e l d s t h e e x a c t s o l u t i o n t o t h e d i s c r e t e L a p l a c e e q u a t i o n a f t e r o p e r a t i o n s . T h e m e t h o d f a i l s t o g e n e r a l i z e t o m o r e g e n e r a l e l l i p t i c p r o b l e m s o r t o n o n -r e c t a n g u l a r d o m a i n s . T h e h o p e d f o r o b j e c t i v e i s t o d e v e l o p a n a l g o r i t h m w h i c h w i l l s o l v e t h e d i s c r e t e e l l i p t i c p r o b l e m i n o p e r a t i o n s . I n t h i s c a s e t h e e r r o r r e d u c t i o n f r o m o n e i t e r a t i o n t o t h e n e x t w o u l d b e i n d e p e n d e n t o f t h e n u m b e r o f e q u a t i o n s t o b e s o l v e d a n d t h e n u m b e r o f o p e r a t i o n s n e e d e d t o r e d u c e t h e i n i t i a l e r r o r -Z b y a f a c t o r o f n w o u l d d e p e n d l i n e a r l y u p o n t h e n u m b e r o f e q u a t i o n s t o b e s o l v e d . C o n c u s a n d G o l u b [ 3 ] c l a i m t h a t a n i t e r a t i o n b a s e d o n t h e B u n e m a n a l g o r i t h m s a t i s f i e s t h i s g o a l w h e n t h e c o e f f i c i e n t f u n c t i o n s Kx a n d ky i n ( 1 . 1 ) a r e s m o o t h . T h e i t e r a t i o n s c h e m e i s g i v e n b e l o w . L e t AN b e t h e d i s c r e t e L a p l a c e o p e r a t o r . U s i n g t h e n o t a t i o n o f C h a p t e r I , t h e i t e r a t i o n i s g i v e n a s w h e r e (. i s a s u i t a b l y c h o s e n a c c e l e r a t i o n p a r a m e t e r , X a n d tK+t) 1^ + X a r e t h e k a n d |<+| a p p r o x i m a t i o n s t o X , a n d w h e r e we a r e s o l v i n g o u r m a t r i x e q u a t i o n ( 1 . 1 : 7 ) . A t e a c h s t e p o f t h e i t e r a t i o n t h e B u n e m a n a l g o r i t h m i s u s e d t o s o l v e f o r t h e n e x t a p p r o x i m a t i o n , X , t o t h e s o l u t i o n o f ( 1 . 1 7 ) . - 2 7 -C o n c u s a n d G o l u b c l a i m t h a t t h e u s e o f a s u i t a b l e s h i f t c o n s t a n t ft a n d t h e s c a l i n g o f /\ f u r t h e r r e d u c e t h e n u m b e r o f o p e r a t i o n s r e q u i r e d t o s o l v e ( 1 . 1 7 ) . I f t h i s i s d o n e , t h e i t e r a t i o n b e c o m e s -(A„ + K l ) x ' " , ) = - ^ n + K I ) x ( t ) - T ( A x " > - ? ) is. /V. w h e r e /\ a n d *f a r e t h e s e a l e d v e r s i o n s o f A a n d {-r e s p e c t i v e l y a n d J_ i s t h e fl X H i d e n t i t y m a t r i x . T h e B u n e m a n a l g o r i t h m c a n s t i l l b e u s e d t o s o l v e w h e r e t = " ( / i n + K i ) - T ( * X ^  - Y ) T h e s t r o n g l y i m p l i c i t m e t h o d o f S t o n e a p p e a r s t o b e a n o t h e r m e t h o d w h i c h r e a c h e s t h e d e s i r e d g o a l ; s e e t h e n u m e r i c a l r e s u l t s i n C h a p t e r V . C H A P T E R I I I D E S C R I P T I O N O F THE S T R O N G L Y I M P L I C I T METHOD S e c t i o n 3.1 M o t i v a t i o n o f t h e S t r o n g l y I m p l i c i t M e t h o d We b e g i n t h e d e s c r i p t i o n o f t h e s t r o n g l y i m p l i c i t m e t h o d b y r e - c o n s i d e r i n g G a u s s i a n e l i m i n a t i o n . T h e t e c h n i q u e o f G a u s s i a n e l i m i n a t i o n i s e q u i v a l e n t t o f a c t o r i n g o u r m a t r i x i n t o t h e m a t r i x p r o d u c t o f t w o s q u a r e m a t r i c e s L a n d W w h e r e L i s a l o w e r t r i a n g u l a r m a t r i x a n d U i s a n u p p e r t r i a n g u l a r m a t r i x [ ^ ] . We c a n d e f i n e t h e m a t r i x L m o r e p r e c i s e l y . L i t * b e a n f) X 1 r e a l m a t r i x . L e t Xi'tj b e t h e e n t r y i n t h e i"** 1 r o w a n d t h e j** 1 c o l u m n o f L . T h e n us W w h e r e CUjj i s t h e (ijj)*** e n t r y i n w h e r e A*' i s t h e m a t r i x o b t a i n e d b y ?row r e d u c i n g t h e f i r s t (j- •) c o l u m n s o f W i t h t h i s d e f i n i t i o n o f L , we c a n d e f i n e Ll t o b e ' - 2 8 -- 2 9 -f\ , i . e . t h e m a t r i x o b t a i n e d b y r o w - r e d u c i n g r\ t o a n u p p e r t r i a n g u l a r m a t r i x . I f w e h a v e L a n d U e x p l i c i t l y , t h e n we c a n s o l v e o u r m a t r i x e q u a t i o n b y t h e t e c h n i q u e o f b a c k w a r d a n d f o r w a r d s u b s t i t u t i o n . We c a n w r i t e o u r m a t r i x e q u a t i o n a s L U x = b T o s o l v e t h i s , l e t y = U x a n d s o l v e L y = b f o r y . T h i s i s e a s i l y d o n e s i n c e L i s l o w e r t r i a n g u l a r . T h e n , s o l v e f o r X . F o r o u r m a t r i x A i t i s n o t t o o d i f f i c u l t t o s e e t h a t L_ a n d t| w i l l b e q u i t g f u l l . T h e f i r s t r o w o f L. w i l l c o n t a i n t w o n o n - z e r o e l e m e n t s s i n c e t h e r e a r e t w o n o n z e r o e l e m e n t s t o b e e l i m i n a t e d i n t h e f i r s t c o l u m n o f A . S e e F i g u r e 2 . T h e r o w r e d u c t i o n p r o c e s s u s e d t o e l i m i n a t e t h e s e t w o e l e m e n t s w i l l a d d a n o t h e r n o n - z e r o e l e m e n t t o t h e s e c o n d c o l u m n o f " . H e n c e AU) t h e r e a r e t h r e e r o w - r e d u c t i o n s t o c a r r y o u t i n g o i n g f r o m A t o A 13) r\ . T h e s e t h r e e r o w r e d u c t i o n s a d d t w o m o r e n o n - z e r o e l e m e n t s A ( 3 ) t o t h e t h i r d c o l u m n o f f\ . H e n c e t h e r e a r e f o u r n o n - z e r o e l e m e n t s t o e l i m i n a t e i n n . I n g e n e r a l , g o i n g f r o m n t o J\ Lnt+t) " i n c r e a s e s t h e n u m b e r o f e l e m e n t s t o b e e l i m i n a t e d b y o n e . H e n c e , t h e c o l u m n s o f L. f i l l u p a s t h e r o w r e d u c t i o n c o n t i n u e s . - 3 0 -S i m i l a r l y t h e n u m b e r o f n o n - z e r o e l e m e n t s i n ( j ( i n c r e a s e w h e n A im) >>(m-»<) . . . t o n a n d L a n d U b e c o m e m o r e d e n s e a s t h e c o l u m n o r r o w n u m b e r s r e s p e c t i v e l y i n c r e a s e . S i n c e o u r m a t r i x A h a s o n l y f i v e b a n d s we s h o u l d , h o p e f u l l y , b e a b l e t o f i n d a n L a n d U e a c h h a v i n g t h r e e b a n d s a n d f o r w h i c h L U i s i n s o m e s e n s e c l o s e t o /\ S t o n e s u g g e s t s t r y i n g t o f i n d a n |_ a n d U o f t h e f o l l o w i n g f o r m . ( L u ) J | k - b j . K l ^ v ; - , + C J > U j . , i K I" djV U j , K (3l) S e e F i g u r e 3 . L = f e w - 3 1 o-w** column F i g . 3 T h e S t r u c t u r e o f t h e M a t r i c e s L. a n d U I f we n o w p r e m u l t i p l y CI by. | a n d e q u a t e t h e r e s u l t we h a v e t h e f o l l o w i n g s e t o f e q u a t i o n s t o s a t i s f y f o r j,k=l ( 3 . 3 - t,) ( 3-3- t-tl) - 3 2 -A t e a c h m e s h p o i n t t h e r e a r e s e v e n e q u a t i o n s t o s a t i s f y a n d o n l y f i v e f r e e v a r i a b l e s t o c h o o s e . C l e a r l y , t h e r e i s n o s e t o f b j | K , C j , * , d j l K t C;^ , f j K w h i c h s a t i s f y a l l t h e e q u a t i o n s i n ( 3 . 3 ) . S t o n e [ l ^ ] , s u g g e s t s t h e f o l l o w i n g w a y o f o v e r c o m i n g t h i s d i f f i c u l t y . D e f i n e ^J tK = c J i K ^ j - l . K a n d G j ' ) K — b j . K Cj,K-l • T h e f a c t o r i z a t i o n i s e x a c t t h e n f o r e q u a t i o n s o f t h e f o r m ^ j * UJ»K-I "** C J . K Mj+I.K-I + DJ.K U j - , ( K +V E4> We n o w a a t t e m p t t o r e w r i t e e a c h o f t h e o r i g i n a l e q u a t i o n s t o b e s o l v e d i n t h e f o r m o f ( 3 . 4 ) a n d i n s u c h a w a y s o t h a t t h e s o l u t i o n o f t h i s a l t e r e d s e t o f e q u a t i o n s w i l l b e c l o s e t o t h e s o l u t i o n o f o u r o r i g i n a l m a t r i x e q u a t i o n ( 1 . 1 7 ) . I f we u s e a s t e n c i l d i a g r a m t o i n d i c a t e w h i c h m e s h p o i n t s a r e u s e d i n e a c h e q u a t i o n i n t h e o r i g i n a l s e t o f l i n e a r e q u a t i o n s , w e c a n s e e h o w t h e e q u a t i o n i n ( 3 . 4 ) d i f f e r s f r o m t h a t i n ( 1 . 8 ) . - 3 3 -F i g . 4 k - l ( \ 3 s V. \ J J s \ \ ? ^ / \ f r \ • • — •• -? J J-A S t e n c i l D i a g r a m f o r A l t e r e d E q u a t i o n a t ( j i k ) M e s h P o i n t I n t h e o r i g i n a l s e t o f e q u a t i o n s , t h e e q u a t i o n a s s o c i a t e d w i t h t h e m e s h p o i n t c o n t a i n s n o n - z e r o c o e f f i c i e n t s f o r t h e s o l u t i o n a t t h e m e s h p o i n t s m a r k e d b y a n i n t h e s t e n c i l d i a g r a m a b o v e . I n t h e a l t e r e d s e t o f e q u a t i o n s , t h e e q u a t i o n a s s o c i a t e d w i t h t h e m e s h p o i n t a l s o i n c l u d e s n o n - z e r o c o e f f i c i e n t s f o r t h e s o l u t i o n a t t h e m e s h p o i n t s m a r k e d b y o p e n c i r c l e s i n t h e s t e n c i l d i a g r a m . We n o w s h o w h o w t o a l t e r e a c h e q u a t i o n i n ( 1 . 8 ) . U s i n g T a y l o r ' s S e r i e s , S t o n e o b t a i n e d t h e f o l l o w i n g s e t o f s e c o n d o r d e r a p p r o x i m a t i o n s . - 3 4 -Uj-itK*\ = UJ.K. - A X U X + ay uy + t f A y ) l u Y y + iUxKlxx^AXAyu,^ ~ U i - i . tc ^ - a3,K *- *x - i C A x j \ i x x A d d i n g t h e t h r e e a p p r o x i m a t i o n s g i v e s t h e f o l l o w i n g r e s u l t . U 4-1. M i = - Uj .K + U j ) V c + 1 + U j . , i K - A X ^ ^ U x v B y i g n o r i n g t h e c r o s s p r o d u c t t e r m we g e t t h e f o l l o w i n g a p p r o x i m a t i o n . U j - , , f e t , = - U j . K •»- U i , K * i +• H$-M=-T h e f o l l o w i n g a p p r o x i m a t i o n i s o b t a i n e d s i m i l a r l y . S t o n e s u g g e s t e d t h a t t h e a p p r o x i m a t i o n s i n ( 3 . 5 ) a n d ( 3 . 6 ) c a n b e i m p r o v e d b y m u l t i p l y i n g t h e r i g h t h a n d s i d e s b y a c o n s t a n t f a c t o r o f d\ , w h e r e O ^ oL *^ 1_ # X f t h i s i s d o n e w e o b t a i n t h e f o l l o w i n g t w o a p p r o x i m a t i o n s t o t h e s o l u t i o n a t a n d ( j - l . f c + l ) . - 35 -I f w e m u l t i p l y ( 3 . 7 ) b y C j ^ a n d m u l t i p l y ( 3 . 8 ) b y 1 a n d a d d t h e r e s u l t i n g t w o a p p r o x i m a t i o n s t o ( 1 . 8 ) w e o b t a i n t h e f o l l o w i n g a p p r o x i m a t i o n . JK. K f l T h i s e q u a t i o n i s o f t h e s a m e f o r m a s t h a t i n ( 3 . 4 ) a n d t h e r e s u l t i n g m a t r i x e q u a t i o n d e n o t e d b y (A + B) u « cj C"5-/o; m a y b e s o l v e d u s i n g t h e L U f a c t o r i z a t i o n p r o c e d u r e a s d e f i n e d b y ( 3 . 1 ) a n d ( 3 . 2 ) . T h e s o l u t i o n U o f t h i s p e r t u r b e d p r o b l e m w i l l h o p e f u l l y b e c l o s e t o t h e s o l u t i o n LA o f ( 1 . 1 7 ) s i n c e t h e p e r t u r b a t i o n w a s o b t a i n e d b y a d d i n g a s e t o f e q u a t i o n s w h i c h h a v e a p p r o x i m a t e l y t h e s a m e s o l u t i o n a s ( 1 . 1 7 ) . C o m p a r i n g t h e e n t r i e s i n w i t h t h o s e i n LU - 3 6 -we o b t a i n t h e f o l l o w i n g d e f i n i t i o n s f o r t h e e l e m e n t s o f L a n d " i ' u. c J t c = Dj | K/(H - d ^j-f.ic) (3/1.Ci) - C j c e j - , . i c ( 3 / i c u ) *3.|c - C BJ.ISH - okCj i f r Hi.K-J/dj.ic ( 3 - l l - l / J We n o w h a v e a n a l g o r i t h m f o r c a l c u l a t i n g t h e s o l u t i o n o f m a t r i x e q u a t i o n s o f t h e t y p e i n ( 3 . 1 0 ) . T h e r e a r e n e q u a t i o n s t o b e s o l v e d a n d t h e c a l c u l a t i o n o f L a n d (J r e q u i r e s a t o t a l o f (9(l| n X ) o p e r a t i o n s . A n o p e r a t i o n i s e i t h e r a m u l t i p l i c a t i o n o r a d i v i s i o n . We d o n o t c o u n t a d d i t i o n s a s t h e t i m e r e q u i r e d t o do a n a d d i t i o n i s s i g n i f i c a n t l y s m a l l e r t h a n t h e t i m e r e q u i r e d t o d o a m u l t i p l i c a t i o n o r d i v i s i o n . T h e b a c k w a r d a n d f o r w a r d s u b s t i t u t i o n r e q u i r e s a t o t a l o f o p e r a t i o n s . H e n c e t h e s o l u t i o n t o ( 3 . 1 0 ) c a n b e a t t a i n e d a f t e r o p e r a t i o n s . R e c a l l , h o w e v e r t h a t w e w i s h t o f i n d [A , t h e s o l u t i o n t o ( 1 . 1 7 ) . T h e s o l u t i o n U o f ( 3 . 1 0 ) s h o u l d b e c l o s e t o LL , t h e a c t u a l s o l u t i o n o f ( 1 . 1 7 ) . We n o w r e q u i r e a m e t h o d w h i c h w i l l f u r t h e r r e d u c e t h e d i f f e r e n c e b e t w e e n U. a n d IA- . T h e m e t h o d o f r e s i d u a l , c o r r e c t i o n [ ] , [ & ] i s j u s t s u c h a m e t h o d a n d w i l l f o r m t h e - 37 -b a s i s o f t h e s t r o n g l y i m p l i c i t i t e r a t i o n s c h e m e . S e c t i o n 3.2 M e t h o d o f R e s i d u a l C o r r e c t i o n C o n s i d e r t h e f o l l o w i n g p r o b l e m . L e t f*1 b e a r e a l , n o n - s i n g u l a r , H X10 m a t r i x . L e t X a n d b €. (R* . We w i s h t o f i n d X s o t h a t M X = t ( 3 . 1 2 ) S u p p o s e t h a t we h a v e 3- , a r e a l OXfl l o w e r t r i a n g u l a r m a t r i x a n d IX. , a r e a l flXH u p p e r t r i a n g u l a r m a t r i x a n d s u p p o s e t h a t <£ll i s a n a p p r o x i m a t e t r i a n g u l a r f a c t o r i z a t i o n o f We c a n e a s i l y s o l v e ( 3 . 1 3 ) f o r X."^ , t h e f i r s t a p p r o x i m a t i o n t o X eCU Xl° = b ( 3 . 1 3 ) We d e f i n e t h e r e s i d u a l v e c t o r V""^ b y a n d t h e e r r o r v e c t o r e. t l^ b y N o t e t h e f o l l o w i n g r e s u l t . M e " ) M x - Mx°> I n o t h e r w o r d s , 6^'^ i s t h e s o l u t i o n o f ( 3 . 1 4 ) ,v,ea) c rco (3*1+) 3 8 -ti) I f w e c o u l d s o l v e ( 3 . 1 4 ) f o r C? t h e n s i n c e X=X11"*" we w o u l d h a v e t h e s o l u t i o n t o ( 3 . 1 1 ) . We c a n n o t CO s o l v e f o r 6 , h o w e v e r s i n c e i f w e c o u l d t h e n w e c o u l d s o l v e ( 3 . 1 1 ) f o r X . B u t w e c a n u s e t h e *ClL a p p r o x i m a t e f a c t o r i z a t i o n o f [*\ t o g e t a n a p p r o x i m a t i o n t o X . To g e t t h e s e c o n d a p p r o x i m a t i o n t o X , s o l v e aClL^^ — f1^ f o r etl^ a n d l e t X < X' =• X ( % C ° ; • H o p e f u l l y , X t , J w i l l b e a b e t t e r a p p r o x i m a t i o n t o X t h a n X*'^ . I n g e n e r a l , i f w e h a v e x'1^ , t h e L^ 1 a p p r o x i m a t i o n t o X , we c o m p u t e r U * = b - M X*' ' a n d s o l v e "ZU - r U i f o r C . We d e f i n e t h e IW**, a p p r o x i m a t i o n b y N o t e t h a t w e n o w h a v e a n i t e r a t i o n t e c h n i q u e f o r g e n e r a t i n g a s e q u e n c e \ X , X ^ . . . } X o f a p p r o x i m a t i o n s t o X . T h e c o n v e r g e n c e p r o p e r t i e s o f t h i s i t e r a t i o n m e t h o d a r e d i s c u s s e d l a t e r . N o t e a l s o t h a t w e n o w h a v e a n e q u a t i o n w h i c h r e l a t e s X" '" ' t o x" ' ' . = x ' ! ) +- teWf' (b-Plx"" ' ) - 3 9 -M u l t i p l y i n g o n b o t h s i d e s b y w e h a v e ^ U x ' " " =• ^ t i x " J - ( / v t x ^ . - l > ) (3-/0 T h i s i s t h e u s u a l f o r m i n w h i c h t h e i t e r a t i o n i s p r e s e n t e d ! ] , [ / ] • C o m p a r e s a l s o t h i s i t e r a t i o n s c h e m e w i t h t h e o n e i n ( 2 . 1 ) . T h e r e a r e s e v e r a l v a r i a t i o n s o f t h e i t e r a t i o n s c h e m e i n ( 3 . 1 5 ) . O n e i t e r a t i o n m e t h o d u s e s t h e s a m e f a c t o r i z a t i o n a t e a c h s t e p o f t h e i t e r a t i o n . T h e c o n v e r g e n c e p r o p e r t i e s o f t h i s i t e r a t i o n a r e d i s c u s s e d b y - I s a a c s o n a n d K e l l e r £ ^ ] , a n d b y Y o u n g a n d G r e g o r y . [ 8 ]• T h e o r e m 3 . 2 . 1 [ 8 ], [ ] L e t ^ X** ' , X * * ' ; . .. , X , ... ^  b e t h e s e q u e n c e o f v e c t o r s g e n e r a t e d b y t h e i t e r a t i o n i n ( 3 . 1 5 ) . L e t X - ~ ^ t> T h e n X > X a s I * °° , i f f o r s o m e m a t r i x n o r m « - ///> F u r t h e r m o r e , i f t h e n f o r t h e v e c t o r n o r m J| "~Hp w h i c h i n d u c e s t h e m a t r i x \\ - |y , we h a v e || X^ » A * ffx//^ • n o r m - 4 0 -P r o o f : see [ 8 ] or [ °J ]. The second v a r i a t i o n of the i t e r a t i o n procedure (3.15) i s to change the matrices °*- and at each step of the i t e r a t i o n . The i t e r a t i o n can be w r i t t e n as The t h i r d v a r i a t i o n uses the same «^ and at each step of the i t e r a t i o n and a c c e l e r a t e s the r e s i d u a l by a f a c t o r of C . The i t e r a t i o n can be w r i t t e n as: x " v , ) - ^ x l l ' ' - T ( ^ x ( i ) - l . ) ( V 1 7 J Theorem 3.2.2 Let p and P be the extreme eigenvalues of ( lit ctt i X 7 X , . . . , X )•-•/ d e f i n e d by (3.17) converges to X ~ 1^ b i f and only i f O < T < JL. P The value of f~ which minimizes the s p e c t r a l r a d i u s of I S P r o o f : See [ # ] , [ °l ]. - 4 1 -S e c t i o n 3.3 S t o n e ' s I t e r a t i o n P r o c e d u r e We u s e ( 3 . 1 ) , ( 3 . 2 ) a n d ( 3 . 1 0 ) t o d e f i n e LU , t h e a p p r o x i m a t e f a c t o r i z a t i o n o f o u r m a t r i x A a n d we u s e ( 3 . 1 5 ) a s t h e b a s i s o f o u r i t e r a t i o n p r o c e d u r e . S t o n e h a s f o u n d t h a t t h e c o n v e r g e n c e p r o p e r t i e s o f ( 3 . 1 6 ) d e p e n d s t r o n g l y u p o n t h e v a l u e o f ©C . F o r = o , t h e c o n v e r g e n c e i s s l o w ; f o r 0^=1 , t h e i t e r a t i o n may n o t c o n v e r g e . S t o n e h a s f o u n d t h a t t h e f o l l o w i n g v a l u e o f g i v e s a g o o d r a t e o f c o n v e r g e n c e w h e n t h e f u n c t i o n s \<X a n d l e y i n ( 1 . 1 ) a r e c o n s t a n t s . I n o r d e r t o f u r t h e r i m p r o v e t h e r a t e o f c o n v e r g e n c e , S t o n e h a s u s e d a s e q u e n c e o f T o^'s d e f i n e d b y ott = 1 - Cl -* )^ -t = o,.,2,...,T-| E a c h o f t h e «*fc's i s u s e d f o r t w o s u c c e s s i v e i t e r a t i o n s . F o r e v e n n u m b e r e d i t e r a t i o n s S t o n e r e o r d e r s t h e m e s h p o i n t s a n d h e n c e t h e o r d e r i n g o f t h e e q u a t i o n s . T h e m e s h p o i n t (j^ki) p r e c e d e s t h e m e s h p o i n t ( j a , kr) i f j t < J % o r i f j , - j x a n d -7 ^ . T h e LIA f a c t o r i z a t i o n i s d i f f e r e n t f o r t h e e v e n n u m b e r e d i t e r a t i o n s s i n c e a t e a c h m e s h p o i n t t h e m o d i f i e d e q u a t i o n s - 4 2 -n o w c o n t a i n s a n o n - z e r o c o e f f i c i e n t f o r t h e s o l u t i o n a t U j L j a n d U j + i . l c + l S t o n e a l s o p r e s e n t e d t h e f o l l o w i n g E o u r i e r e r r o r a n a l y s i s o f t h e i t e r a t i o n f o r t h e c a s e o f c o n s t a n t c o e f f i c i e n t f u n c t i o n s k x a n d k*-j . L e t l c ~ u i i K - — K),* w h e r e U j , ^ . i s t h e s o l u t i o n /• i \ C i ) o f ( 1 . 1 7 ) a t t h e m e s h p o i n t ( j i M a n d e j , K . i s t h e e r r o r a t t h e m e s h p o i n t Cj.k) a f t e r L a p p l i c a t i o n s o f t h e i t e r a t i o n s c h e m e . A s s u m e t h a t t h e e r r o r i s o f t h e f o l l o w i n g f o r m . € ? j K — T A<to,p C to,p= -eft T h e n t h e f o l l o w i n g e x p r e s s i o n f o r t h e d e c a y f a c t o r i s o b t a i n e d . t ^ T i e d - * ) 3-+ C*A:T -tyc^R2-w h e r e ft = 2 ^ ( J i L ^ L ) * ^ ( . Z 2 L £ L ) T = C<SS ( U/TT A.*) COS (p TTfcv/J w h e r e Djtc=- ^  A N D J^,fc = *B a n d C i s t h e a s y m p t o t i c v a l u e w h i c h C^ i K_ a p p r o a c h e s a s j a n d k g r o w l a r g e . - 4 3 -D u p o n t K e n d a l l a n d R a c h f o r d [] "7 ] h a v e s h o w n t h a t f o r a d i f f e r e n t d e f i n i t i o n o f L a n d (J a n d t h e i t e r a t i o n i n ( 3 . 1 7 ) t h e n u m b e r o f c o m p u t a t i o n s r e q u i r e d t o r e d u c e t h e A n o r m t h e e r r o r b y a f a c t o r o f n""2" i s 0 ( 2 f l 3 ^ o c | - a . l ^ ) • T h i s w o r k e s t i m a t e i s n o b e t t e r t h a n t h a t o f SOR a n d d o e s n o t r e f l e c t t h e p o w e r o f S t o n e ' s S t r o n g l y I m p l i c i t F a c t o r i z a t i o n . C H A P T E R I V THE S Y M M E T R I C F A C T O R I Z A T I O N R e c e n t l y , S t o n e h a s p r o p o s e d a n LU f a c t o r i z a t i o n f o r w h i c h t h e m o d i f i e d m a t r i x i s s y m m e t r i c . T h e n e w f a c t o r i z a t i o n c a n n o t b e j u s t i f i e d a s t h e o r i g i n a l f a c t o r i z a t i o n ( 3 . 1 1 ) b u t n u m e r i c a l e x p e r i e m e n t s s u g g e s t t h a t t h e s y m m e t r i c f a c t o r i z a t i o n i s c o m p a r a b l e t o t h e o r i g i n a l a l g o r i t h m . S e e C h a p t e r V . A g a i n L a n d U h a v e t h e f o r m g i v e n i n ( 3 . 1 ) a n d ( 3 . 2 ) . T h e d e f i n i t i o n s o f t h e e l e m e n t s o f L a n d U a r e g i v e n b e l o w . C\%x. = D^ .ic - * bj-uc e j - L t - i (4-1-ii) - HJC f y c - i - co*ic € H , i c (4:1• at) Hie - (Bj.tc-n - < * c j , i c 4 i - i 1 K J / ^ L K (4-1-i/J B y i n c r e a s i n g t h e j i n d e x b y 1 i n ( 4 . 1 . i i ) w e h a v e : - 4 4 -- 4 5 -B y i n c r e a s i n g t h e K i n d e x b y 1 i n ( 4 . 1 . i ) w e h a v e : T h e s e r e l a t i o n s h o l d a t a l l g r i d p o i n t s . H e n c e , a s a r e s u l t we h a v e t h e f o l l o w i n g r e l a t i o n s h i p a m o n g t h e e n t r i e s i n L a n d U . W e i , tc- i = di.ic-i ^ K - I •= Cj^.iw f i x - i A c o n s e q u e n c e o f ( 4 . 2 ) i s t h a t t h e p r o d u c t LU i s a s y m m e t r i c m a t r i x . T h e f o l l o w i n g l e m m a i s d u e t o B r a c h a - B a r a k a n d S a y l o r \_ 1 J j w h o h a v e c o n s i d e r e d t h e s y m m e t r i c f a c t o r i z a t i o n . L e m m a 1 A s s u m e t h a t Bj (fc - f D j x\d<0 f o r a l l Cj.lc) . L e t 0 1^ i 1 . I t f o l l o w s t h a t t h e q u a n t i t i e s d e f i n e d i n ( 4 . 1 ) e x i s t a n d s a t i s f y t h e f o l l o w i n g i n e q u a l i t i e s . d^K, "7 O (4-B t i t ) - I < e3,,< ^ .O U-3 - lV ) - I< t,>$0 U 31/) - 4 6 -T h e p r o o f u s e s i n d u c t i o n a n d i s f o u n d i n £ J[ ]. We a r e a b l e t o e x t e n d t h e s e r e s u l t s i n t h e f o l l o w i n g 1 e mma. L e m m a 2 U n d e r t h e s a m e a s s u m p t i o n s a s i n L e m m a 1 t h e q u a n t i t i e s i n ( 4 . 2 ) s a t i s f y t h e f o l l o w i n g c o n d i t i o n s . EO,K+ Bj^-v-Dj,^ < d i r . < 2 max (E 4> + Dj f l t +-Bj>) > B j , K - £ +-D,\,t f£o, K) CJ,K > PJ,H. ~ * maj (EJ.K+DJ.K+BJ.K) fj.ic < Bu+i/(Znjw(Ej i l c +p 5 . K i -Q. l c)) P r o o f : F r o m ( 4 . 1 . i i i ) w e h a v e U s i n g t h e r e l a t i o n s i n ( 4 . 2 ) we c a n s u b s t i t u t e f o r fc\)ilC a n d Q l " , | C t o g e t t h a t < ^ = Ei .K-t-Bj.tc-t- Dj.yc - djjic-llj.it-l 0 + fj.K-i) - 4 7 -F r o m L e m m a 1 we h a v e t h a t a n d t h a t - d . i - l . i c e i - i . i c C ! + e , - - u i c ) 7 0 H e n c e , <^ j|d > ^ j t * "B j jc +- D J <. To g e t t h e u p p e r b o u n d o n ^J^yC w e n o t e t h a t i s a q u a d r a t i c d e f i n e d o n t h e i n t e r v a l a n d h e n c e h a s a m a x i m u m o f £ a t ^ " i . l C ~ l ~ • S i m i l a r l y ~ 6 j - ^ ( c C l +• S ' i - i jc ) h a s a m a x i m u m o f £ a t C j - M C ^ "51 S i n c e cfjic'^k f o r a l l Cl.fc-) we h a v e t h a t H e n c e a n d t h e r e s u l t f o l l o w s . I n o r d e r t o s e e t h e s e c o n d t w o r e s u l t s w e r e w r i t e t h e d e f i n i t i o n s o f fc>i,K a n d Q , ( C . U s i n g ( 4 . 2 ) a g a i n , we s e e t h a t - 4 8 -a n d t h a t c i , i c - ^LK ~ <* C IM.IM ej-i.ic-i 4)-i.)c-» U s i n g t h e w e l l k n o w n i n e q u a l i t y c o n c e r n i n g t h e a r i t h m e t i c a n d g e o m e t r i c m e a n s , w e o b t a i n t h a t f o r a l l ^ J t V-) 2. U s i n g ( 4 . 3 . v i ) w e h a v e t h a t a z S q u a r i n g b o t h s i d e s o f t h e e x p r e s s i o n g i v e s u s t h a t H e n c e , 4-a n d 4-U s i n g t h e u p p e r b o u n d o n ^J,|c w e o b t a i n t h e d e s i r e d r e s u l t . I n o r d e r t o s e e t h e t h i r d r e s u l t w e u s e ( 4 . 2 . i ) t o w r i t e d ^ i c ^ i IC • U s i n g ( 4 . 3 . i i ) w e h a v e t h a t 4 9 -U s i n g t h e u p p e r b o u n d o n ^ j ^ w e h a v e t h a t O^.K, ^ o . i c . y 2 Gi.K max (.Ei.tc + B j . c + j.k. P u t t i n g t h e p r e v i o u s t w o i n e q u a l i t i e s t o g e t h e r g i v e s u s t h a t J.IC S i n c e I71C>X ( Ej.K. t* Dj .ic+BjK^othe r e s u l t f o l l o w s . S i m i l a r l y , we h a v e t h e r e s u l t t h a t -fi^ c < Bi .fct-i 2. max (Eo.* +- B o t + "D; K") 3 ic ' Q . E . D . N o t e t h a t L e m m a 1 t o g e t h e r w i t h L e m m a 2 i m p l y t h a t t h e c o e f f i c i e n t s i n L a n d (jt s t a y b o u n d e d i n d e p e n d e n t l y o f t h e s i z e o f t h e m a t r i c e s L a n d U a n d s o i n d e p e n d e n t l y o f %Vt&* t h e m e s h s p a c i n g . I n o r d e r f o r t h e i t e r a t i o n t o m a k e s e n s e , we m u s t s h o w t h a t t h e p r o d u c t LU i s n o n - s i n g u l a r . T h e f o l l o w i n g r e s u l t i s d u e t o D i a m o n d £ S ]. L e m m a 3 W i t h L a n d Li d e f i n e d b y 4 . 1 , we h a v e t h a t LU i s p o s i t i v e d e f i n i t e . P r o o f : N o t e t h a t w h e r e U i s t h e d i a g o n a l m a t r i x w i t h - 5 0 -e n t r i e s c/j.K , j ^ C - U l j — O . S i n c e b y L e m m a 1 , C ^ o . l c ^ O , we h a v e t h a t *^  e x i s t s . H e n c e L U =1 U T D U =• ( D ^ ) T ( ^ U ) >, o We c a n r e m o v e t h e p o s s i b i l i t y o f e q u a l i t y b y n o t i n g t h a t d c t (LU) - cUrt lO-ckfr lbO - <J] da.c) • l > o H e n c e LU i s p o s i t i v e d e f i n i t e a n d t h e r e s u l t i s p r o v e d . We n o w e x a m i n e t h e c o n v e r g e n c e p r o p e r t i e s o f t h e i t e r a t i o n ( 3 . 1 5 ) u s i n g t h e s y m m e t r i c v e r s i o n o f LU . S i n c e t h e p r o d u c t LU i s n o n - s i n g u l a r we c a n w r i t e U4"0 = UC0 - ILU)"M(U(0- U)) L e t 6 - U ~ U > w h e r e LX = / \ . I n o t h e r w o r d s Q. i s t h e e r r o r v e c t o r a f t e r (Cfl) a p p l i c a t i o n s o f t h e i t e r a t i o n . S u b t r a c t i n g U f r o m b o t h s i d e s o f ( 4 . 4 ) u s i n g t h e d e f i n i t i o n o f 6 we h a v e e 1 ' * ' - ( l - ( L u r W 5 1 -© «-» w h e r e G i s t h e e r r o r b e t w e e n L/C — n ^ a n d t h e i n i t i a l (o) g u e s s (J, _ _ (O I t i s w e l l k n o w n [ ^ J t h a t ^ — 9 0 a s <•»—J 0 0 i f a n d i f o n l y f o r e a c h e i g e n v a l u e o f , d e n o t e d b y A m ( l - (LU)-'A) , - 1 < I A r n C l " ILU) HA)I * 1 R e c a l l i n g t h a t A+-^  , we h a v e t h a t T - (LuVA = x - (A-h^ r1 A - I - ( 1 + A - - B ) " ' H e n c e , i t f o l l o w s t h a t f o r e a c h e i g e n v a l u e o f A m ( l - ( L U r ' A ) - 1 - 1 H-\m(A-'B) H e n c e t h e i t e r a t i o n ( 3 . 1 5 ) c o n v e r g e s t o UL ~ A °[ i f a n d o n l y i f f o r e a c h m, A m i s r e a l a n d ~ t < Xw.lA-'B) < ^ B r a c h a - B a r a k a n d S a y l o r [ 3L ]> h a v e s h o w n t h a t t h e e i g e n v a l u e s o f a r e r e a l . S i n c e M i s a r e a l s y m m e t r i c p o s i t i v e d e f i n i t e m a t r i x , t h e r e e x i s t s A 2 " , t h e r e a l , s y m m e t r i c p o s i t i v e d e f i n i t e s q u a r e r o o t o f A . S i n c e i s s i m i l a r t o A*f A+"b) A 1 " > a r e a l s y m m e t r i c m a t r i x , t h e 5 2 -e i g e n v a l u e s o f (A+-B) A a r e r e a l . S i n c e X m {((\t&)'A) - } + *Jffr&) we h a v e t h a t t h e e i g e n v a l u e s o f A'B> a r e r e a l , S i n c e A a n d B a r e b o t h r e a l s y m m e t r i c m a t r i c e s a n d A i s p o s i t i v e d e f i n i t e w e h a v e b y a w e l l k n o w n r e s u l t £ ^ ^ ] » t h a t a n d /^Ytxin t h e e x t r e m e e i g e n v a l o f A ' B> a r e g i v e n b y t h e e x t r e m e v a l u e s o f t h e R a y l e i g h u e s Qu o t i e n t .A max (A"B) — max { X B X I x^-o [ x r A X/ Ar».vi (A"'e>) - m m / x r B x I n o r d e r t o s h o w t h a t t h e i t e r a t e s c o n v e r g e t o t h e s o l u t i o n o f ( 1 . 1 7 ) w e m u s t s h o w t h a t m<xx / x T "Bx \ < ' (4>'5-; x*o \ x r Ax a n d t h a t m i * / x T ft* \ ^ - L (^-6^ x*o l x T A x J F r o m b e f o r e w e h a v e t h a t f o r X 5 ^ , X €.7R° , ff^/^.J^minf^kw, ^ k x ) x T x X r A X - 5 3 -I n o r d e r t o f i n d a b o u n d f o r X T & X > w e m u s t h a v e t h e i n n e r p r o d u c t }C Bx. • B r a c h a - B a r a k a n d S a y l o r [ I ]> h a v e s h o w n t h a t X TBX = I I (* c o\fcW ^ X j.k4 | - X j , W ) ^ + ( i - * K K W x j ; , c ) ^ M ^ ^ , k e j ( k . , (x^,,ic- xj,k):u+-(«-<=')bj,kei,ic-l x£ t ) - j ^ L C 3 i K$j-,.k. ( x K U , - x^lJ" O'S) F r o m Lemma 1 we h a v e t h a t c j , k ^ - t ^ l c ? / ° a n d ^ j . k ^ j . k - l ° f o r a l l ^ ( | c ) . F o r 0 S od 1 1 we h a v e t h a t t h e f i r s t t w o s u m s i n ( 4 . 8 ) a r e n o n - n e g a t i v e . We c a n g e t a n u p p e r b o u n d o n t h e f i r s t t w o s u m s . A r\-i N o t e t h a t b y ( 4 . 2 ) c o , k W - ^ ^ , . ^ 1 : = b i - i > V * i €J-Kk. - 5 4 -H e n c e m(KY (.C J,,C$J-MC~) ~ U\(KX ( b j . K - ^ ^ l c - i ) . R e c a l l i n g t h e d e f i n i t i o n o f XTIS* X w h e r e A M i s t h e d i s c r e t e L a p l a c e o p e r a t o r , we h a v e t h a t t h e f i r s t t w o s u m s i n ( 4 . 8 ) a r e b o u n d e d b y S i n c e t h e t h i r d s u m i n ( 4 . 8 ) i s n e g a t i v e w e h a v e t h a t f o r l a r g e n , a n d b y u s i n g L emma 2 , X T B x < WTA*(doK«iV^ie) * T X < moot (Ej/ K + B j , K + t>3,,c) C 1 + "3<*) x r X H e n c e f o r l a r g e D , we h a v e t h a t T h e r e s u l t i n ( 4 . 6 ) i s n o t : e a s y t o o b t a i n . We c a n e x a m i n e t h e c o n v e r g e n c e p r o p e r t i e s o f t h e i t e r a t i o n b y l o o k i n g a t t h e p r o b l e m i n a n e w w a y . We a r e a b l e t o p r o v e t h e f o l l o w i n g t h e o r e m . T h e o r e m 4 .1 W i t h o u r /\ , a n d L(X d e f i n e d u s i n g t h e s y m m e t r i c S t o n e 1 - II D * -U A ^ i r £ (*•&) 1 - II C D ^ U A - r i \ ^ (t*) f a c t o r i z a t i o n , we h a v e t h a t - 5 5 -P r o o f : A r m V , (X- (Ai&V'A) ~ 1 - Amw< ( M+RV'A) R e c a l l i n g t h a t A a n d A+~^> a r e b o t h p o s i t i v e d e f i n i t e a n d s y m m e t r i c , we h a v e t h a t f o r e a c h e i g e n v a l u e o f (A+B>)/1 > X ™ (fti-ar'A) « Am ^ A * ) w h e r e c = A - 6 ^ B ) -H e n c e A max (CA-tbr 'A) = H c c T l l i z . - II A - ( A ^ y i l l ^ a n d , ^  2. R e c a l l t h e d e f i n i t i o n o f t h e i n d u c e d m a t r i x a n d t h a t (fob) ~- L U U T D U , w h e r e L/ i s t h e d i a g o n a l m a t r i x w i t h p o s i t i v e e n t r i e s ^lj,|C n o r m - 5 6 -- A*,** ( A ~ - ( A ^ ) A ^ ) H e n c e A p?, n ((A* %)~'A) = II ( D VU A"-) ||£ S i m i l a r l y , = X^x(At(A+6)" 'A-) = IIAi(Diu ) - , | l^ H e n c e R e c a l l t h a t t o s h o w c o n v e r g e n c e , we n e e d t o s h o w t h a t . F r o m (4.9) w e i m m e d i a t e l y o b t a i n t h a t A max ( I - (WA)<i. I n o r d e r t o s h o w t h a t ~'^^min i t i s t e m p t i n g t o p r o c e e d a s f o l l o w s . - 57 -B y d e f i n i t i o n , L e t « d y - u T ' x t h e n i(p*-urf I f w e c a n f i n d a p s u c h t h a t II D y |( «, |«> J|y|(«> f o r a l l y , t h e n we h a v e t h a t P F o r , p i c k C j , | c ) s o t h a t l c j ] l K | = / </,'j | T h e n f o r t h a t Qik) , we h a v e |2? = W « J d ^ c ( l + e $ > K + - ? j \ | t ) J a n d we h a v e t h a t H e n c e - 5 8 -cO S i m i l a r l y i do^ mi a n d h e n c e , N u m e r i c a l e x p e r i m e n t s s h o w h o w e v e r , t h a t f o r t h e c a s e o f t h e d i s c r e t e L a p l a c e o p e r a t o r , o u r l o w e r b o u n d f o r c a n t a k e o n v a l u e s o f t h e o r d e r o f •2. -CX/O . N u m e r i c a l e x p e r i e m e n t s ( s e e C h a p t e r V ) s h o w t h a t t h e s y m m e t r i c f a c t o r i z a t i o n w i l l c o n v e r g e t o t h e s o l u t i o n o f t h e d i s c r e t e L a p l a c e e q u a t i o n , s o t h a t t h e e i g e n v a l u e s o f CX" (A+Q) 'A ) m u s t l i e i n t h e i n t e r v a l £-1,1) . I t a p p e a r s t h a t t h e m a t r i x i n e q u a l i t y u s e d i n ( 4 . 1 0 ) g a v e t o o m u c h a w a y s o t h a t a g o o d e s t i m a t e o f t h e >(~ n o r m o f t h e p r o d u c t i s n o t a v a i l a b l e . H o w e v e r , a b e t t e r a l t h o u g h s t i l l n o t u s e f u l e s t i m a t e o f t h e m i n i m u m e i g e n v a l u e o f (X— (A+B)"' A ) i s d u e t o B r a c h a -B a r a k a n d S a y l o r [ 1 ] . T h e y h a v e s h o w n t h a t A W m ( l ~ (A+bj'AJy^r w h e r e Q •=- Wu/yv. I H } . S e e C h a p t e r V f o r t h e r e s u l t i n g " c),ic) \ « J < ^ $i)L I b o u n d o n Am?*( X - CA^y'/l) . - 5 9 -D i a m o n d [ 5 J, h a s s h o w n t h a t f o r t h e c a s e o f t h e L a p l a c e o p e r a t o r , w i t h o^ .~ 1_ , a n d t h a t a s A"X —9 O . H e h a s a l s o s h o w n t h a t i f HO;K= H> , a c o n s t a n t , a n d t > ^ j c = n> a c o n s t a n t , t h e n f o r o l = 3_ liYn X ^ , ( W * B ) " A ) ) -1 1 I n t h i s c h a p t e r we h a v e p r e s e n t e d S t o n e ' s s y m m e t r i c s t r o n g l y i m p l i c i t p r o c e d u r e a n d s h o w n t h a t t h e p e r t u r b e d m a t r i x i s n o n - s i n g u l a r . We h a v e a l s o s h o w n t h a t t h e e n t r i e s t h e n u m b e r o f e q u a t i o n s t o b e s o l v e d . We h a v e a l s o p r e s e n t e d n e c e s s a r y a n d s u f f i c i e n t c o n d i t i o n s w h i c h g u a r a n t e e c o n v e r g e n c e o f t h e i t e r a t i o n s c h e m e . U n f o r t u n a t e l y w e a r e u n a b l e t o s h o w t h a t t h e s y m m e t r i c f a c t o r i z a t i o n p r o c e d u r e s a t i s f i e s t h e s e c o n d i t i o n s . We r e f o r m u l a t e t h e c o n d i t i o n s n e c e s s a r y f o r c o n v e r g e n c e i n t e r m s o f a m a t r i x n o r m a n d q u o t e t h e r e s u l t s o b t a i n e d b y B r a c h a - B a r a k a n d S a y l o r , a n d D i a m o n d . I n t h e n e x t c h a p t e r we i n c l u d e n u m e r i c a l e x a m p l e s o f t h e b o u n d s o b t a i n e d r e m a i n b o u n d e d i n d e p e n d e n t l y o f H , - 60 -f o r t h e c r u c i a l e i g e n v a l u e ; X^. C JL-fA+lZi)1 A) C H A P T E R V R E S U L T S OF N U M E R I C A L E X P E R I M E N T S I n t h i s c h a p t e r we c o n s i d e r s e v e r a l a s p e c t s o f t h e o r i g i n a l a n d s y m m e t r i c s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e a n d a l s o c o m p a r e t h e i r e f f e c t i v e n e s s w i t h t h e w e l l - k n o w n s u c c e s s i v e l i n e o v e r r e l a x a t i o n p r o c e d u r e [ ] 8 j , ^ 9 j . I n p a r t i c u l a r , we w i s h t o s t u d y t h e r e l a t i o n s h i p b e t w e e n t h e v a l u e o f o(. u s e d i n t h e f a c t o r i z a t i o n s ( 3 . 1 1 ) a n d ( 4 . 1 ) a n d t h e r a t e a t w h i c h t h e e r r o r i s r e d u c e d i n e a c h i t e r a t i o n . We a l s o w i s h t o i n v e s t i g a t e t h e e f f e c t o f r e o r d e r i n g t h e m e s h p o i n t s i n t h e m a n n e r s u g g e s t e d b y S t o n e [ l l j . We a l s o c o n s i d e r t h e c l a i m t h a t S t o n e ' s o r i g i n a l f a c t o r i z a t i o n p r o c e d u r e i s e x a c t f o r p r o b l e m s w h i c h h a v e a l i n e a r s o l u t i o n . F o r i n t e r e s t ' s s a k e , we a l s o i n c l u d e t h e r e s u l t s o f a p p l y i n g t h e m e t h o d s u g g e s t e d b y B r a c h a - B a r a k a n d S a y l o r [ l ] . B e f o r e p r e s e n t i n g t h e r e s u l t s o f t h e n u m e r i c a l i n v e s t i g a t i o n s , we m u s t d e f i n e a m e a s u r e o f t h e e r r o r v e c t o r . We u s e t h e s a m e m e a s u r e o f t h e e r r o r a s t h a t u s e d b y S t o n e [ l l ] . - 6 1 -- 6 2 -R e c a l l t h a t we d e f i n e t h e e r r o r v e c t o r a t t h e I ~" s t e p o f t h e i t e r a t i o n t o b e <0 _ it) e = IA - u w h e r e U s o l v e s o u r m a t r i x e q u a t i o n ( 1 . 1 7 ) a n d U < 1 ^ i s t h e L~ a p p r o x i m a t i o n t o U . M u l t i p l y i n g t h i s e x p r e s s i o n f o r S b y o u r m a t r i x A , we o b t a i n A e 1 0 = A (TX- Y A u ( 0 w h e r e <^ i s t h e r i g h t h a n d s i d e o f o u r m a t r i x e q u a t i o n ( 1 . 1 7 ) . We m e a s u r e t h e e r r o r a t t h e I s t e p o f t h e i t e r a t i o n i n t e r m s o f t h e f l f - A l l 1 ||«, j JL | CJ^ |C  . We u s e t h e f o l l o w i n g f o u r p r o b l e m s a s t e s t c a s e s . I n e a c h c a s e JL i s t h e i n t e r i o r o f t h e u n i t s q u a r e . P r o b l e m O n e : A u = - 1 ^ * ^ ) £ -JL. u - o tx,«j) £ ^si. P r o b l e m T w o : loo u x x + u -- 6 3 -P r o b l e m T h r e e ( x , y ) e Jz-w h e r e kx = J / o o i k ^ = | l o o o- oo ooo / I 4 = J b o o ooo I -5 U o n d 1 - ^ t ^ 3 ofti'er UJ i s •c, • 5 ^ I'O ohd o t^j t . SI ot^er urt.se O -o 5" - A £= O'lS and o - o s t y to i s " O R t X t f l ^ f one*, o ? { , t Y t o < ? f 1 - o o. 5 I 83 - o -27 6 P r o b l e m F o u r A U ~ O Oc«-)~)£ J\_ ^ - 3 X + 4 ^ 6c. *V) 6 ^  J V We b e g i n b y c o n s i d e r i n g t h e r e l a t i o n s h i p b e t w e e n t h e v a l u e o f a n d t h e e r r o r r e d u c t i o n a c h i e v e d a f t e r t e n a p p l i c a t i o n s - 6 4 -o f b o t h t h e o r i g i n a l a n d s y m m e t r i c s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e s , w h e n u s e d t o s o l v e p r o b l e m o n e . F o r b o t h f a c t o r i z a t i o n s we r e p o r t t h e r e s u l t s o b t a i n e d w h e n t h e m e s h p o i n t s a r e r e o r d e r e d o n a l t e r n a t e i t e r a t i o n s a n d w h e n t h e o r d e r i n g o f t h e m e s h p o i n t s i s k e p t t h e s a m e f o r e a c h s t e p o f t h e i t e r a t i o n . We p e r f o r m t h e a b o v e a n d f o l l o w i n g i n v e s t i g a t i o n s u p o n f o u r d i f f e r e n t u n i f o r m m e s h e s . T h e f i r s t m e s h h a s 1 1 e q u a l l y s p a c e d m e s h p o i n t s i n b o t h t h e X a n d "y* d i r e c t i o n s , t h e s e c o n d m e s h h a s 2 1 e q u a l l y s p a c e d m e s h p o i n t s i n e a c h d i r e c t i o n , t h e t h i r d h a s 3 1 e q u a l l y s p a c e d m e s h p o i n t s a n d t h e f o u r t h h a s 4 1 e q u a l l y s p a c e d m e s h p o i n t s . I n a l l c a s e s s i n g l e p r e c i s i o n a r i t h m e t i c i s u s e d . On t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a ' s I B M 3 7 0 - 1 6 8 t h i s m e a n s t h a t a b ' o u d i s e v e n a d ' i g i i t j s d a r e u s e d i n a l l c a l c u l a t i o n s . T a b l e s I t o I V i n c l u d e t h e r e s u l t s o f t h e a b o v e i n v e s t i g a t i o n ? . We n o t e t h a t t h e v a l u e s o f <x c l o s e t o b u t n o t e q u a l t o o n e p r o v i d e t h e g r e a t e s t r e d u c t i o n i n t h e e r r o r a n d t h a t t h e e f f e c t o f r e o r d e r i n g t h e m e s h p o i n t s i s n o t i c e a b l e o n l y f o r v a l u e s o f c l o s e t o o n e . I n e a c h c a s e we n o t e t h a t fche^o.riginal s t r o n g l y i m p l i c i t f a c t o r i z a t i o n d o e s b e t t e r t h a n t h e s y m m e t r i c s t r o n g l y i m p l i c i t f a c t o r i z a t i o n . - 65 -F o r i n t e r e s t ' s s a k e we n o w p r e s e n t t h e r e s u l t s o f a p p l y i n g t e n i t e r a t i o n s o f t h e s c h e m e s u g g e s t e d b y B r a c h a - B a r a k ? a n d S a y l o r f l ] . T h e i r s c h e m e u s e s i t e r a t i o n ( 3 . 1 7 ) . S Y M M E T R I C F A C T O R I Z A T I O N * O R I G I N A L F A C T O R I Z A T I O N * I n i t i a l E r r o r : 8.2 x 1 0 " 3 R e o r d e r N o R e o r d e r i n g R e o r d e r i n g No R e o r d e r i n s 0. 1.4 - 3 1.4 - 3 1.4 - 3 1.4 - 3 .1 1.2 - 3 1.2 - 3 1.2 -3 1.2 - 3 .2 1.1 - 3 1.1 - 3 1.1 -3 1.1 -3 .3 9.2 -4 9.5 -4 9.2 -4 9.5 -4 .4 7.4 -4 7.7 -4 7.4 -4 7.7r -4 .5 5.5 -4 5.8 -4 5.5 -4 5.8 -4 .6 3.6 -4 0 3.9 -4 3.6 -4 3.9 -4 .7 1.8 -4 2.1 -4 1.9 -4 2.2 -4 .8 5.5 -5 7.9 -5 5.7 -4 7.9 -5 .9 2.8 -6 9.6 -6 2.2 -6 9.1 -6 .95 3.7 -6 2.4 -5 1.3 -6 5 . 4 -6 . 9 9 5.8 -5 2.4 - 3 8.3 -6 3.7 -4 1 . 0 0 1.1 -4 1.1 -2 2.7 -5 6.0 - 3 T A B L E I R e s u l t s f o r V a r i o u s o l ' s w h e n S o l v i n g P r o b l e m O n e o n 1 1 x 1 1 M e s h * F i n a l e r r o r a f t e r t e n i t e r a t i o n s . - 6 6 -- - S Y M M E T R I C F A C T O R I Z A T I O N * O R I G I N A L F A C T O R I Z A T I O N * I n i t i a l E r r o r : 2.2 - 3 R e o r d e r N o R e o r d e r i n g R e o r d e r i n g R e o r d e r i n g N o R e o r d e r i n g 0. 1.7 - 3 1.7 - 3 1.7 - 3 1.7 " 3 .1 1.7 - 3 1.7 - 3 1.7 - 3 1.7 " 3 .2 1.6 - 3 1.6 - 3 1.6 - 3 1.6 " 3 .3 1.5 - 3 1.5 - 3 1.5 - 3 1.5 " 3 .4 1.4 - 3 1.4 - 3 1.4 - 3 1.4 " 3 .5 1.3 - 3 1.3 - 3 1.3 - 3 1.3 " 3 .6 1.1 - 3 1.1 - 3 1.1 - 3 1 . 1 " 3 .7 9.4 -4 9.4 -4 9.4 -4 9.4 " 4 .8 6.2 -4 6.3 -4 6.2 -4 _ A 6.3 1 4 .9 2 . 0 -4 2.2 -4 2.5 4 2 . 2 -* . 9 5 2.8 -5 7.5 -5 2.8 -5 6.0 " 3 .99 3 . 4 -4 1.7 1.6 -4 6.4 " 2 1 . 0 0 3.7 - 3 1 5 . 0 1.4 - 3 4.7 T A B L E I I R e s u l t s f o r V a r i o u s 's w h e n S o l v i n g P r o b l e m O n e o n 2 1 x 2 1 M e s h * F i n a l e r r o r a f t e r t e n i t e r a t i o n s . - 67 -SYMMETRIC FACTORIZATION* ORIGINAL FACTORIZATION* I n i t i a l E r r o r : 1.0 -3 Reo rder No Reordering Reordering No Reordering 0. 1.0 -3 1.0 -3 1.0 -3 1.0 -3 .1 1.0 -3 1.0 :3 1.0 -3 1.0 -3 .2 9.9 -4 9.9 -3 9.9 -4 9.9 -4 .3 9.8 -4 9.8 -3 9.8 -4 9.8 -4 .4 9.6 -4 9.6 -4 9.6 -4 9.6 -4 .5 9.3 -4 9.3 -4 9.3 -4 9.3 -4 .6 8.9 -4 8.9 -4 8.9 -4 8.9 .7 8.2 -4 8.2 -4 8.2 -4 8.2 -4 .8 6.9 -4 6.9 -4 6.9 -4 6.9 -4 .9 4.0 -4 4.1 -4 4.0 -4 4.1 -4 .99 2.1 -4 1.6 -4 1.3 -4 115 1.00 1.8 -2 6.1 -3 8.3 -3 2.5 -2 TABLE I I I Resu l t s f o r Various d,'s when S o l v i n g Problem One on 31 x 31 Mesh * F i n a l e r r o r a f t e r ten i t e r a t i o n s . - 68 -S Y M M E T R I C F A C T O R I Z A T I O N * O R I G I N A L F A C T O R I Z A T I O N * I n i t i a l E r r o r : 5.9 -4 R e o r d e r N N o R e o r d e r i n g R e o r d e r M g g N o R e o r d e r i n g 0. 5 . 9 -4 5 . 9 -4 5.9 -4 5.9 " 4 .1 5 . 9 -4 5.9 -4 5.9 -4 5.9 -* .2 5.9 -4 5.9 -4 5.9 -4 5.9 "* .3 5 . 9 -4 5.9 -4 5.9 -4 5.9 .4 5.8 -4 5.8 -4 5.8 -4 5.8 " 4 .5 5.8 -5 5.8 -4 5.8 -4 5.8 " 4 .6 5.7 -4 5.7 -4 5.7 -4 5.7 " 4 .7 5.6 -4 5.6 -4 5.6 -4 5 . 6 " 4 .8 5.2 -4 5.2 -4 5.2 -4 5 . 2 " 4 .9 4.0 -4 4.0 -4 4 . 0 -4 4 . 0 " 4 . 9 5 2.2 -4 2.3 -4 2.2 -4 2 . 3 " 4 .99 9.2 -5 1.9 -1 6.4 -5 . 1 3 1 . 0 0 4.9 - 2 . 9.7 -4 2.5 -2 3.5 " 3 T A B L E I V R e s u l t s f o r V a r i o u s OC 1 s w h e n S o l v i n g P r o b l e m O n e o n 4 1 x 4 1 M e s h * F i n a l e r r o r a f t e r t e n i t e r a t i o n s . - 6 9 -1 1 x 1 1 G r i d 2 1 x 2 1 G r i d 3 1 x 3 1 G r i d 4 1 x 4 1 G r i d E r r o r T E r r o r T E r r o r T E r r o r 0. 2 . r 3 . 8 2 3 1.9" 3 . 8 2 6 i . o " 3 . 8 2 7 5 . 9 " 4 . 8 2 7 .1 2 . r 3 . 7 9 8 K 8 " 3 . 8 0 1 i . o " 3 . 8 0 2 5 . 9 " 4 . 8 0 2 .2 2 . 0 " 3 . 7 7 0 1.8" 3 . 7 7 3 i . o " 3 . 7 7 4 5 . 9 " 4 . 7 7 4 .3 1.9" 3 . 7 3 9 1.8" 3 . 7 4 2 i . o " 3 . 7 4 2 5 . 9 " 4 . 7 4 3 .4 X . 9 " 3 . 7 0 4 1.8" 3 . 7 0 6 i . o " 3 . 7 0 7 5 . 9 " 4 . 7 0 7 .5 1.8" 3 . 6 6 3 i . r 3 . 6 6 5 i . o " 3 . 6 6 6 5 . 9 " 4 . 6 6 0 .6 1 . 7 " 3 . 6 1 5 1.7" 3 . 6 1 7 9 . 9 " 4 . 6 1 7 5 . 9 " 4 . 6 1 7 .7 1 . 5 " 3 . 5 5 6 1.6"3 . 5 5 7 9 . 7 " 4 . 5 5 7 5 . 8 " 4 . 5 5 8 .8 1 . 3 " 3 . 4 7 9 1 . 5 " 3 . 4 8 0 9 . 4 " 4 . 4 5 0 5 . 8 " 4 . 4 8 0 .9 i . r 3 . 3 6 4 1 . 2 " 3 . 3 6 5 8 . 7 " 4 . 3 6 5 5 . 6 " 4 . 3 6 5 .95 i . r 3 . 2 7 3 i . o " 3 . 2 7 2 7 . 8 " 4 . 2 7 3 5 . 3 " 4 . 2 7 3 .99 2 . 9 " 3 . 1 5 4 i . o " 3 . 1 3 3 5 . 3 " 4 . 1 3 2 4 . 0 " 4 . 1 3 2 1 . 0 0 4 . 2 " 3 . 1 0 9 1.9" 3 . 0 5 4 9 . 8 " 4 . 0 3 5 5 . 8 " 4 . 0 2 6 T A B L E V S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m O n e w i t h B r a c h a - B a r a k a n d S a y l o r ' s V a l u e o f T* a n d V a r i o u s 0 oc/s  - 70 -H e r e t h e v a l u e o f ( X i s s e t e q u a l t o o n e a n d t h e v a l u e o f i s e s t i m a t e d f r o m t h e e n t r i e s i n t h e m a t r i x N o t e t h a t t h i s s c h e m e i s n o t a s e f f e c t i v e a s e i t h e r t h e s y m m e t r i c o r o r i g i n a l s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e . M o r e o v e r t h e s u c c e s s i v e l i n e o v e r r e l a x a t i o n t e c h n i q u e d o e s m u c h b e t t e r t h a n t h e B r a c h a - B a r a k a n d S a y l o r s c h e m e . A l t h o u g h m a n y a n a l y z e t h e s t r o n g l y i m p l i c i t f a c t o r i z a t i o n t e c h n i q u e u s i n g t h e a p p r o a c h o f B r a c h a - B a r a k a n d S a y l o r £ 7 ] , £ l ] i t a p p e a r s t h a t t h e p r o p e r c h o i c e o f (X a n d s e t t i n g C =1.0 g i v e f a r b e t t e r r e s u l t s . We n e x t c o n s i d e r t h e r e s u l t s o b t a i n e d b y a p p l y i n g S t o n e ' s o r i g i n a l s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e t o p r o b l e m s o n e a n d t w o . H e r e t h e m e s h p o i n t s a r e r e o r d e r e d o n a l t e r n a t e s t e p s o f t h e i t e r a t i o n a n d a s e q u e n c e o f oi J a r e u s e d . We u s e t h e m e t h o d s u g g e s t e d b y S t o n e t o o b t a i n a s e q u e n c e o f oc's w h i c h a r e a p p l i e d c y c l i c a l l y . We u s e (3.18) t o d e f i n e Os. a n d t h e n u s e (3.19) t o d e f i n e oi-^ , t. = o,T-| . We u s e T- S a n d a p p l y t h e o t s i n t h e o r d e r s u g g e s t e d b y S t o n e , n a m e l y ( o C g , °< s ; <* ^  , ^ 7 ; 4. , «< 1 ;ot(,,<*.2,c(a) . E a c h v a l u e o f tf. t i s u s e d t w i c e i n s u c c e s s i o n . I t i s u s e d o n c e w h e n t h e u s u a l o r d e r i n g o f t h e m e s h p o i n t s i s u s e d a n d o n c e i n t h e f o l l o w i n g s t e p o f t h e i t e r a t i o n w h e n t h e m e s h p o i n t s a r e r e o r d e r e d . - 71 -G r i d . I n i t i a l E r r o r F i n a l E r r o r N o . o f I t n ' s T i m e 1 1 x 1 1 8.2 " 3 1.7 -7 1 2 . 1 8 0 2 1 x 2 1 2 . 2 " 3 8.7 -7 1 4 . 7 7 0 3 1 x 3 1 1.0 " 3 7.9 -7 1 8 2 . 1 0 6 4 1 x 4 1 5.9 " 4 3.0 -7 3 0 6 . 2 7 0 T A B L E V I S t o n e ' s O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m O n e  G r i d I n i t i a l E r r o r F i n a l E r r o r N o . o f I t n ' s T i m e 1 1 x 1 1 8.2 " 3 1.4 -7 6 . 0 9 0 2 1 x 2 1 2.2 " 3 1.8 -7 6 . 3 2 4 3 1 x 3 1 1.0 " 3 2 . 8 -7 6 . 7 0 8 4 1 x 4 1 5.7 -7 6 1 . 2 4 8 T A B L E V I I S t o n e ' s O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m Two  - 7 2 -A f t e r 1 8 s t e p s o f t h e i t e r a t i o n , t h e s a m e s e q u e n c e o f i s u s e d a g a i n . T a b l e V I c o n t a i n s t h e r e s u l t s o b t a i n e d f o r p r o b l e m o n e a n d T a b l e V I I c o n t a i n s t h e r e s u l t s o b t a i n e d f o r p r o b l e m t w o . T a b l e V I I i l l u s t r a t e s t h e w e a k d e p e n d e n c e o f t h e r a t e o f c o n v e r g e n c e u p o n t h e s i z e o f t h e m a t r i x e q u a t i o n t o b e s o l v e d ; f o r e a c h o f t h e f o u r m e s h e s o n l y s i x i t e r a t i o n s w e r e r e q u i r e d t o r e d u c e t h e e r r o r b y a f a c t o r o f & ( 1 0 ^ ) . T a b l e s V I I I a n d I X c o n t a i n t h e a n a l a g o u s r e s u l t s o b t a i n e d b y u s i n g t h e s y m m e t r i c s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e t o s o l v e p r o b l e m s o n e a n d t w o . N o t e t h a t a l t h o u g h t h e o r i g i n a l f a c t o r i z a t i o n d o e s b e t t e r , t h e s y m m e t r i c a n d o r i g i n a l f a c t o r i z a t i o n s a r e c o m p a r a b l e i n t h e i r e f f e c t i v e n e s s . N o t e t h a t i n p r o b l e m s o n e a n d t w o t h e c o e f f i c i e n t f u n c t i o n s a n d i n e q u a t i o n ( 1 . 1 ) h a v e b e e n c o n s t a n t o v e r t h e d o m a i n . We n o w c o n s i d e r a p r o b l e m f o r w h i c h t h e c o e f f i c i e n t f u n c t i o n s a n d k-*i v a r y c o n s i d e r a b l y o v e r t h e d o m a i n .52- . A n i n t e r e s t i n g p r o b l e m p r e s e n t s i t s e l f w h e n a t t e m p t i n g t o c h o o s e a n <X w h i c h w i l l g i v e a r a p i d r a t e o f Li) r -j c o n v e r g e n c e o f t h e i t e r a t e s U . S t o n e [_''J, s u g g e s t s t h a t we u s e ( 3 . 1 8 ) t o d e f i n e <*. a t e a c h g r i d p o i n t a n d t h e n t a k e t h e a r i t h m e t i c a v e r a g e o f t h e s e v a l u e s t o o b t a i n a s i n g l e v a l u e . We c a n u s e t h i s c o n s t a n t v a l u e o f <X t o g e n e r a t e t h e s e q u e n c e 5 - 7 3 -t — O , / ~ l . A s e c o n d m e t h o d c a l c u l a t e s t h e ot 5 a t e a c h g r i d p o i n t a c c o r d i n g t o ( 3 . 1 8 ) a n d t h e n t a k e s t h e m i n i m u m o f t h e s e o L S o v e r a l l m e s h p o i n t s a n d u s e s t h e r e s u l t i n g v a l u e t o g e n e r a t e t h e s e q u e n c e <A-fc , -fc = o , T ~ l . T h e r e i s , h o w e v e r , n o o b v i o u s r e a s o n w h y t h e s a m e v a l u e o f ot s h o u l d b e u s e d a t e a c h m e s h p o i n t . R e c a l l i n g ( 3 . 7 ) a n d ( 3 . 8 ) , i t s e e m s m o r e a p p r o p r i a t e t h a t t h e v a l u e o f d e p e n d u p o n t h e m e s h p o i n t . H e n c e , a t h i r d m e t h o d s u g g e s t s i t e s e l f : u s e ( 3 . 1 8 ) t o d e f i n e °^-j,K a t e a c h m e s h p o i n t a n d t h e n u s e ( 3 . 1 9 ) t o g e n e r a t e t h e s e q u e n c e o f ^J.IC'5 f ° r e a c h m e s h p o i n t . We p r e s e n t r e s u l t s f o r a l l t h r e e m e t h o d s o f c h o o s i n g OC a n d c o m p a r e t h e i r r e l a t i v e e f f e c t i v e n e s s i n T a b l e X . We n o t e t h a t i n a l l c a s e s t h e u s e o f a c o n s t a n t oL f o r e a c h g r i d p o i n t i s b e t t e r t h a n u s i n g a n w h i c h d e p e n d s u p o n t h e m e s h p o i n t a n d t h a t t h e ot. o b t a i n e d b y t h e f i r s t m e t h o d ( s u g g e s t e d b y S t o n e i s s u p e r i o r t o t h e l a t t e r t w o m e t h o d s . T a b l e X I c o n t a i n s a n a l a g o u s r e s u l t s o b t a i n e d b y a p p l y i n g t h e s y m m e t r i c f a c t o r i z a t i o n t o p r o b l e m t h r e e . A g a i n e a c h o f t h e t h r e e m e t h o d s i s u s e d t o g e n e r a t e a s e q u e n c e 01 ^ } fc ~ O, .. .T-| . I n t h i s c a s e t h e r e i s a g r e a t d e a l o f s i m i l a r i t y b e t w e e n t h e r e s u l t s o b t a i n e d b y t h e f i r s t a n d s e c o n d me-tihb'dfs.. T h e y b o t h d o e q u a l l y w e l l . T h e t h i r d i d m e t h o d o f - 7 4 -G r i d I n i t i a l E r r o r F i n a l E r r o r N o . o f I t n ' s T i m e 1 1 x 11 8.2 " 3 2.3 -7 1 2 . 2 2 1 2 1 x 2 1 2.2 ' 3 3.0 -7 1 6 1 . 5 0 0 3 1 x 3 1 1.0 " 3 2.5 -7 2 4 3 . 1 4 4 4 1 x 4 1 5.9 " 4 3.6 -4 4 0 8 . 8 2 2 T A B L E V I I I S t o n e ' s S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m O n e  G r i d I n i t i a l E r r o r F i n a l E r r o r N o . o f I t n ' s T i m e 1 1 x 1 1 8.2 " 3 3.2 -7 4 . 0 7 4 2 1 x 2 1 2.2 " 3 3.9 -7 5 . 3 1 3 3 1 x 3 1 1.0 " 3 4 . 6 -7 6 . 7 8 6 4 1 x 4 1 5.9 " 4 2.6 -7 8 1 . 8 8 T A B L E I X S t o n e ' s S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m Two  - 75 -G r i d I n i t i a l E r r o r F i n a l E r r o r M i n o v e r a l l G r i d P t * M i n a t r e a c h G r i d ' • A r i t h M e a n * T i m e 1 1 x 1 1 . 6 4 6 4.9 3.6 ' 6 3.3 " 6 1 2 3 0 1 1 . 2 0 0 . 4 6 8 . 1 7 8 2 1 x 2 1 . 1 0 1 3.5 •<> 4.2 " 6 2 2 D i v e r g e s 1 6 1 . 2 1 1 . 8 9 9 3 1 x 3 1 . 0 5 6 4 . 6 " 6 3.6 - 6 3 0 D i v e r g e s 1 7 3 . 5 5 3 2 . 0 0 4 4 1 x 4 1 . 0 2 9 1.0 " 4 3.3 " 6 4 0 D i v e r g e s 2 9 3 . 1 7 9 5 . 9 3 5 T A B L E X S t o n e ' s O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m T h r e e * N u m b e r o f i t e r a t i o n s r e q u i r e d t o r e a c h i n d i c a t e d f i n a l e r r o r . - 76 -G r i d I n i t i a l E r r o r F i n a l E r r o r M i n a t E a c h G r i d P t * M i n O v e r A l l G r i d P t s * A r i t h M e a n * T i m e 1 1 x 1 1 . 6 4 6 3.1 " 6 3.5 " 6 2.6 " 6 1 1 1 1 1 1 . 3 1 3 . 3 1 7 . 3 1 3 2 1 x 2 1 . 1 0 1 1.7 " 6 3.9 " 6 2 . 3 " 6 1 7 2 2 17 1 . 5 5 8 2 . 0 5 8 1 . 5 6 4 3 1 x 3 1 . 0 5 6 4 . 1 " 6 4 . 4 " 6 4.2 " 6 1 7 35 1 8 3 . 3 1 2 6 . 6 8 2 3 . 6 7 8 4 1 x 4 1 . 0 2 9 3 . 3 " 6 3.5 " 2 4.8 -35 4 0 35 1 1 . 6 4 5 1 3 . 4 7 7 1 1 . 6 9 1 T A B L E X I S t o n e ' s S y m m e t r i c F a c t o r i z a t i o n A p p l i e d t o P r o b l e m T h r e e  * N u m b e r o f i t e r a t i o n s r e q u i r e d t o r e a c h i n d i c a t e d f i n a l e r r o r . - 77 -c h o o s i n g t h e s e q u e n c e ck^ d o e s n o t d o a s w e l l a s t h e f i r s t a n d s e c o n d -methbd'si F o r i n t e r e s t s s a k e we p r e s e n t t h e r e s u l t s o b t a i n e d b y d o i n g o n e i t e r a t i o n o f S t o n e ' s o r i g i n a l f a c t o r i z a t i o n p r o c e d u r e a p p l i e d t o p r o b l e m f o u r . S e e T a b l e X I I . A l t h o u g h t h e e r r o r r e d u c t i o n i s l a r g e we d o n o t o b t a i n t h e e x a c t s o l u t i o n t o o u r m a t r i x e q u a t i o n i n o n e i t e r a t i o n a s c l a i m e d b y B r a c h a - B a r a k a n d S a y l o r £ l ] . We h a v e n o t d i s c u s s e d t h e e f f e c t s o f r o u n d - o f f e r r o r i n o u r c a l c u l a t i o n s ; we h a v e p r o c e e d e d a s i f o u r c a l c u l a t i o n s w e r e d o n e e x a c t l y b y t h e c o m p u t e r w h i l e i n f a c t o n l y a s i x d i g i t a p p r o x i m a t i o n i s u s e d . T h e e r r o r i n t r o d u c e d b y t h i s a p p r o x i m a t i o n m a y b e r e a s o n t h a t S t o n e ' s m e t h o d f a i l s t o g i v e t h e e x a c t s o l u t i o n t o p r o b l e m s w h o s e s o l u t i o n s a r e l i n e a r . I n o r d e r t o c o m p a r e t h e e f f e c t i v e n e s s o f t h e s t r o n g l y i m p l i c i t f a c t o r i z a t i o n , we p r e s e n t i n T a b l e X I I I t h e r e s u l t s o b t a i n e d b y u s i n g s u c c e s s i v e l i n e o v e r r e l a x a t i o n t o s o l v e e a c h o f o u r t h r e e p r o b l e m s . F o r p r o b l e m o n e t h e r e i s a s m a l l a d v a n t a g e i n u s i n g t h e s t r o n g l y i m p l i c i t f a c t o r i z a t i o n . F o r t h e m o r e d i f f i c u l t p r o b l e m s , e i t h e r o f t h e s t r o n g l y i m p l i c i t f a c t o r i z a t i o n s r e a l i z e a s u b s t a n t i a l s a v i n g i n c o m p u t a t i o n a l e f f o r t . B r a c h a - B a r a k a n d S a y l o r h a v e o b t a i n e d a l o w e r b o u n d - 7 8 -G r i d I n i t i a l E r r o r E r r o r A f t e r O n e I t e r a t i o n T i m e 1 1 x 1 1 8.4 " 2 3.8 " 4 . 0 1 3 S e e s . 2 1 x 2 1 4.4 " 2 2 . 1 " 4 . 0 4 1 3 1 x 3 1 3.0 " 2 1.4 " 4 . 0 8 5 4 1 x 4 1 1.1 " 4 . 1 4 8 T A B L E X I I E r r o r A f t e r O n e I t e r a t i o n o f O r i g i n a l F a c t o r i z a t i o n A p p l i e d t o P r o b l e m F o u r P r o b l e m G r i d N o . o f I t n ' s F i n a l E r r o r T i m e O n e 1 1 X 1 1 2 6 4.9 -7 . 2 9 6 2 1 X 2 1 4 4 7.9 -7 1 . 0 7 1 3 1 X 3 1 6 2 9.5 -7 4 . 4 6 8 4 1 X 4 1 8 1 1.8 -6 1 0 . 8 4 9 Two 1 1 X 1 1 3 5 3 3 8 8 -7 . 3 8 3 2 1 X 2 1 8 1 9.5 -7 2 . 8 6 8 3 1 X 31 8 1 1.2 -6 6 . 1 6 2 4 1 X 4 1 8 1 1.8 -5 1 0 . 7 4 0 T h r e e 1 1 X 1 1 5 0 7.3 -6 . 5 1 5 2 1 X 2 1 6 8 9.2 -6 2 . 3 8 0 3 1 X 3 1 1 0 1 4.9 -4 7.6 4 1 X 4 1 1 0 1 2.5 - 3 1 3 . 2 6 T A B L E X I I I R e s u l t s o f A p p l y i n g S u c c e s s i v e L i n e O v e r R e l a x a t i o n t- rt P - r n V t l omc O n o T i . 7 n an A T l i r o o - 79 -L o w e r B o u n d f o r ^ ( l G r i d 1 1 x 1 1 2 1 x 2 1 3 1 x 3 1 4 1 x 4 1 0 - 1.4 - 1.4 - 1.4 - 1.4 .1 - 1.4 - 1.4 - 1.4 - 1.4 .2 - 1.5 - 1.5 - 1.5 - 1.5 .3 - 1.6 - 1.6 - 1.6 .4 - 1.8 - 1.8 - 1.8 - 1.8 .5 - 2.0 - 2 . 0 - 2.0 - 2.0 .6 - 2.2 - 2 . 2 - 2.2 - 2.2 .7 - 2.5 - 2.5 - 2.5 - 2.3 .8 - 3.1 - 3.1 - 3.1 " 3.1 .9 - 4.4 - 4.4 - 4.4 - 4.4 1.0 - 1 7 . 3 - 3 6 . 0 - 5 4 . 9 - 7 4 . 0 T A B L E X I V I N u m e r i c a l V a l u e s o f L o w e r B o u n d f o r X m i * (Z- (A+W4) O b t a i n e d b y B r a c h a - B a r a k a n d S a y l o r  - 8 0 -f o r t h e s m a l l e s t e i g e n v a l u e o f I"" ^ A ^ ) A . £ l ] . I n T a b l e X I V I we p r e s e n t t h e n u m e r i c a l v a l u e o f t h i s l o w e r b o u n d f o r v a r i o u s v a l u e s o f ok. w h e n t h e s y m m e t r i c f a c t o r i z a t i o n i s a p p l i e d t o p r o b l e m o n e . I n e a c h c a s e t h e l o w e r b o u n d i s s m a l l e r t h a n -1, t h e s m a l l e s t v a l u e w h i c h i s n e c e s s a r y f o r c o n v e r g e n c e o f t h e s y m m e t r i c f a c t o r i z a t i o n p r o c e d u r e . I n c o n c l u s i o n we h a v e s h o w n t h a t t h e s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e o f f e r s c l e a r a d v a n t a g e s w h e n u s e d t o s o l v e m o r e d i f f i c u l t e l l i p t i c b o u n d a r y v a l u e p r o b l e m s . We h a v e i n v e s t i g a t e d t h e r e l a t i o n s h i p b e t w e e n OC a n d t h e r a t e o f c o n v e r g e n c e o f t h e s t r o n g l y i m p l i c i t f a c t o r i z a t i o n p r o c e d u r e . We f o u n d t h a t f o r b o t h t h e s y m m e t r i c a n d o r i g i n a l f a c t o r i z a t i o n s t h e c h o i c e o f a n 0C c l o s e t o b u t n o t e q u a l t o o n e , p r o v i d e s t h e m o s t r a p i d r a t e o f c o n v e r g e n c e . We h a v e f o u n d t h a t t h e r e o r d e r i n g o f g r i d p o i n t s i n a l t e r n a t e i t e r a t i o n s i s a d v a n t a g e o u s o n l y f(o:r v a l u e s o f ot c l o s e t o o n e . We i n v e s t i g a t e d t h e p r o c e d u r e s u g g e s t e d b y B r a c h a -B a r a k a n d S a y l o r a n d f o u n d t h a t i t i s n o t a s e f f e c t i v e a s S L O R . H e n c e we h a v e d e m o n s t r a t e d t h e n e e d f o r a c a r e f u l a n a l y t i c i n v e s t i g a t i o n o f t h e r e l a t i o n s h i p b e t w e e n o*«. a n d t h e e x t r e m e e i g e n v a l u e s o f t h e i t e r a t i o n m a t r i x o f t h e s y m m e t r i c s t r o n g l y i m p l i c i t f a c t o r i z a t i o n . B I B L I O G R A P H Y B r a c h a - B a r a k , A m n o n ; S a y l o r , P a u l E . ; A S y m m e t r i c F a c t o r i z a t i o n P r o c S c u r e f o r t h e S o l u t i o n o f E l l i p t i c B o u n d a r y V a l u e P r o b l e m s ; S I A M J . o f Num. A n a l . ; V o l . 1 0 , N o . 1 , p p . 1 9 0 - 2 0 6 ; M a r c h , 1 9 7 0 . B u z b e e , B . L . ; G o l u b , G.H.; N i e l s o n , C .W.; O n D i r e c t M e t h o d s f o r S o l v i n g P o i s s o n ' s E q u a t i o n ; S I A M J . o f Num. A n a l . ; V o l . 7, N o . 4, p p . 6 2 7 - 6 5 6 ; D e c e m b e r , 1 9 7 0 . C o n c u s , P a u l ; G o l u b , G e n e H.; U s e o f F a s t D i r e c t M e t h o d s f o r t h e E f f i c i e n t N u m e r i c a l S o l u t i o n o f N o n - S e p a r a b l e E l l i p t i c E q u a t i o n s ; S I A M J . o f Num. A n a l . ; V o l . 1 0 , N o . 6, p p . 1 1 0 3 - 1 1 2 0 ; D e c e m b e r , 1 9 7 3 . C o u r a n t , R. ; H i l b e r t , D.; M e t h o d s o f M a t h e m a t i c a l P h y s i c s ; I n t e r s c i e n c e P u b l i s h e r s I n c . ; N e w Y o r k ; 1 9 7 0 . D i a m o n d , M a r t i n ; A n E c o n o m i c a l A l g o r i t h m f o r t h e S o l u t i o n o f E l l i p t i c D i f f e r e n c e E q u a t i o n s I n d e p e n d e n t o f U s e r S u p p l i e d P a r a m e t e r s ; D o c t o r a l T h e s i s ; U n i v e r s i t y o f I l l i n o i s a t U r b a n a - C h a m p a i g n U r b a n a , I l l i n o i s ; D e c e m b e r , 1 9 7 1 . D o r r , F r e d W.; T h e D i r e c t S o l u t i o n o f t h e D i s c r e t e P o i s s o n E q u a t i o n o n a R e c t a n g l e , S I A M R e v i e w , V o l . 1 2 , N o . 2 , p p . 2 4 8 T 2 6 3 ; A p r i l , 1 9 7 0 . D u p o n t , T o d d ; K e n d a l l , R i c h a r d P.; R a c h f o r d J r . , H.H.; A n A p p r o x i m a t e F a c t o r i z a t i o n P r o c e d u r e f o r S o l v i n g S e l f - A d j o i n t E l l i p t i c D i f f e r e n c e E q u a t i o n s ; S I A M J o f Num. A n a l . , V o l . 5 , N o . 3 , p p . 5 5 9 - 5 7 3 ; S e p t e m b e r , 1 9 6 8 . G r e g o r y , R o b e r t T o d d ; Y o u n g , D a v i d M.; A S u r v e y o f N u m e r i c a l M a t h e m a t i c s ; A d d i s o n W e s l e y P u b l i s h i n g C o . ; R e a d i n g , M a s s . ; 1 9 7 3 . - 8 1 -- 8 2 -I s a a c s o n , E u g e n e ; K e l l e r , H e r b e r t B i s h o p ; A n a l y s i s o f N u m e r i c a l M e t h o d s ; J o h n W i l e y & S o n s , I n c . ; N e w Y o r k ; 1 9 6 6 . L a n c a s t e r , P e t e r ; T h e o r y o f M a t r i c e s ; A c a d e m i c P r e s s ; N e w Y o r k ; 1 9 6 9 . S t o n e , H e r b e r t , L . ; I t e r a t i v e S o l u t i o n o f I m p l i c i t A p p r o x i m a t i o n o f M u l t i - D i m e n s i o n a l P a r t i a l D i f f e r e n t i a l E q u a t i o n s ; S I A M J . o f Num. A n a l . ; V o l . 5 , N o . 3 , p p . 5 3 0 - 5 5 8 ; S e p t e m b e r , 1 9 6 8 . W a c h s p r a s s , E u g e n e L . ; I t e r a t i v e S o l u t i o n o f E l l i p t i c S y s t e m s a n d A p p l i c a t i o n t o t h e N e u t r o n D i f f u s i o n E q u a t i o n s o f R e a c t o r P h y s i c s ; P r e n t i c e H a l l , I n c . E n g l e w o o d C l i f f s , N e w J e r s e y ; 1 9 6 6 . 

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-0079503/manifest

Comment

Related Items