analyse nume
TRANSCRIPT
-
7/28/2019 Analyse Nume
1/42
I n t r o d u c t i o n t o N u m e r i c a l A n a l y s i s
a n d C o m p u t i n g w i t h F o r t r a n
M . A . W o n g s a m
R . W . C h a n t r e l l
S c h o o l o f E l e c t r o n i c E n g i n e e r i n g a n d C o m p u t e r S y s t e m s
U n i v e r s i t y o f W a l e s
D e a n S t r e e t , B a n g o r , G w y n e d d , L L 5 7 1 U T
1
-
7/28/2019 Analyse Nume
2/42
C o n t e n t s
1 O u t l i n e o f t h e C o u r s e 4
2 L e c t u r e 1 - C o m p u t i n g w i t h n u m b e r s 5
2 . 1 T h e c o m p u t e r r e p r e s e n t a t i o n o f n u m b e r s : : : : : : : : : : : : : : 5
2 . 2 E r r o r s d u e t o t h e c o m p u t e r r e p r e s e n t a t i o n o f n u m b e r s : : : : : : : 6
3 L e c t u r e 2 - E r r o r s a r i s i n g f r o m a r i t h m e t i c a l o p e r a t i o n s 8
3 . 1 S u m m a r y f r o m l e c t u r e 1 : : : : : : : : : : : : : : : : : : : : : : : 8
3 . 2 E r r o r a c c u m u l a t i o n : : : : : : : : : : : : : : : : : : : : : : : : : : 9
3 . 3 L o s s o f s i g n i c a n c e : : : : : : : : : : : : : : : : : : : : : : : : : : 1 0
4 L e c t u r e 3 - S o l v i n g N o n - L i n e a r E q u a t i o n s 1 1
4 . 1 F i x e d - p o i n t i t e r a t i o n : : : : : : : : : : : : : : : : : : : : : : : : : 1 1
4 . 2 c r i t e r i a f o r c o n v e r g e n c e : : : : : : : : : : : : : : : : : : : : : : : : 1 2
4 . 3 T h e N e w t o n - R a p h s o n m e t h o d : : : : : : : : : : : : : : : : : : : : 1 3
5 L e c t u r e 6 - S y s t e m s o f l i n e a r e q u a t i o n s ( 1 ) 1 4
5 . 1 I n t r o d u c t i o n : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 4
5 . 1 . 1 S o l v a b i l i t y o f s y s t e m s o f l i n e a r e q u a t i o n s : : : : : : : : : : 1 4
5 . 2 D i r e c t m e t h o d s : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 6
5 . 2 . 1 D e n i t i o n s : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 6
5 . 2 . 2 T h e b a c k s u b s t i t u t i o n a l g o r i t h m : : : : : : : : : : : : : : : 1 6
5 . 3 G a u s s i a n e l i m i n a t i o n : : : : : : : : : : : : : : : : : : : : : : : : : 1 7
5 . 3 . 1 T h e r e d u c t i o n a l g o r i t h m : : : : : : : : : : : : : : : : : : : 1 7
5 . 3 . 2 F a i l u r e o f t h e r e d u c t i o n m e t h o d : : : : : : : : : : : : : : : 1 8
5 . 4 I t e r a t i v e m e t h o d s : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1
5 . 4 . 1 J a c o b i ' s m e t h o d : : : : : : : : : : : : : : : : : : : : : : : : 2 1
5 . 4 . 2 T h e G a u s s - S e i d e l m e t h o d : : : : : : : : : : : : : : : : : : 2 1
6 L e c t u r e 7 - S y s t e m s o f l i n e a r e q u a t i o n s ( 2 ) 2 4
6 . 1 T h e A l g e b r a i c e i g e n v a l u e p r o b l e m : : : : : : : : : : : : : : : : : : 2 4
6 . 2 T h e p o w e r m e t h o d : : : : : : : : : : : : : : : : : : : : : : : : : : 2 4
6 . 3 S i m i l a r i t y a n d t h e Q R m e t h o d : : : : : : : : : : : : : : : : : : : : 2 5
6 . 3 . 1 H o u s e h o l d e r t r i d i a g o n a l i s a t i o n : : : : : : : : : : : : : : : : 2 5
6 . 3 . 2 Q R F a c t o r i s a t i o n : : : : : : : : : : : : : : : : : : : : : : : 2 7
7 L e c t u r e 1 0 - O r d i n a r y D i e r e n t i a l E q u a t i o n s , P a r t ( 1 ) 3 0
7 . 1 I n t r o d u c t i o n : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 0
7 . 2 S i n g l e - s t e p m e t h o d s : : : : : : : : : : : : : : : : : : : : : : : : : : 3 1
7 . 2 . 1 T h e E u l e r m e t h o d : : : : : : : : : : : : : : : : : : : : : : 3 1
7 . 2 . 2 T h e i m p r o v e d E u l e r ( p r e d i c t o r - c o r r e c t o r ) m e t h o d : : : : : 3 2
7 . 2 . 3 R u n g e - K u t t a m e t h o d s : : : : : : : : : : : : : : : : : : : : 3 2
7 . 2 . 4 4 - t h o r d e r R u n g e - K u t t a a l g o r i t h m : : : : : : : : : : : : : : 3 3
8 L e c t u r e 1 1 - O r d i n a r y D i e r e n t i a l E q u a t i o n s , P a r t ( 2 ) 3 5
8 . 1 M u l t i - s t e p m e t h o d s : : : : : : : : : : : : : : : : : : : : : : : : : : 3 5
8 . 1 . 1 I m p l i c i t f o r m u l a s : : : : : : : : : : : : : : : : : : : : : : : 3 5
8 . 1 . 2 E x p l i c i t f o r m u l a s : : : : : : : : : : : : : : : : : : : : : : : 3 6
-
7/28/2019 Analyse Nume
3/42
8 . 2 T h e A d a m s - M o u l t o n p r e d i c t o r - c o r r e c t o r m e t h o d : : : : : : : : : : 3 7
8 . 2 . 1 T h e A d a m s - B a s h f o r d m e t h o d : : : : : : : : : : : : : : : : 3 7
8 . 2 . 2 T h e A d a m s - M o u l t o n m e t h o d : : : : : : : : : : : : : : : : 3 8
9 P r o b l e m s 3 9
1 0 A n s w e r s t o P r o b l e m s 3 9
1 1 L e c t u r e p r o g r a m m e 4 2
-
7/28/2019 Analyse Nume
4/42
1 O u t l i n e o f t h e C o u r s e
T h e s e n o t e s h a v e b e e n p r e p a r e d a s a c o m p a n i o n t o a p a r t o f a n M S c . d e g r e e r u n
a t S E E C S , U W B i n t h e s p r i n g o f 1 9 9 8 . I t i s i n t e n d e d f o r g r a d u a t e e n g i n e e r s , a n d
a s s u m e s a g r a d u a t e l e v e l k n o w l e d g e o f a p p l i e d m a t h e m a t i c s i n c l u d i n g c a l c u l u s ,
r e a l a n d c o m p l e x a n a l y s i s a n d l i n e a r a l g e b r a . F o r i n s t a n c e , i n s e c t i o n 4 r e f e r e n c e
i s m a d e t o t h e m e a n v a l u e t h e o r e m a n d i n t e r m e d i a t e v a l u e t h e o r e m f r o m c a l c u -
l u s . T h e i n t e n t i o n i s t o p r o v i d e a g r o u n d i n g i n s o m e o f t h e m o s t u s e f u l a r e a s
o f n u m e r i c a l a n a l y s i s f o r p h y s i c a l s c i e n t i s t s a n d e n g i n e e r s , t o g e t h e r w i t h s o m e
e x p e r i e n c e o f w r i t i n g i m p l e m e n t a t i o n s o f t h e a l g o r i t h m s u s i n g F o r t r a n 9 0 / 9 5 . N o
p r e v i o u s k n o w l e d g e o f F o r t r a n p r o g r a m m i n g i s a s s u m e d .
T h e c o u r s e c o m p r i s e s 2 4 s e s s i o n s i n c l u d i n g p r o g r a m m i n g w o r k s h o p s , a n d
c o v e r s t h e s o l u t i o n o f s y s t e m s o f n o n - l i n e a r e q u a t i o n s , l i n e a r a l g e b r a , i n t e r p o l a -
t i o n , n u m e r i c a l q u a d r a t u r e , a n d t h e i n t e g r a t i o n o f o r d i n a r y a n d p a r t i a l d i e r e n t i a l
e q u a t i o n s . T h e p r o g r a m m e f o r t h e 1 9 9 7 / 9 8 p r e s e n t a t i o n i s g i v e n i n T a b l e 1 i n
s e c t i o n 1 1 .
A l s o , a s p a r t o f t h e a s s e s s m e n t i s i n c l u d e d t w o p r a c t i c a l p r o j e c t s w h i c h e n a b l e
s t u d e n t s t o d e m o n s t r a t e t h e i r g r a s p a n d a b i l i t y t o a p p l y c e r t a i n t o p i c s w i t h i n t h e
c o u r s e . I n t h e t h e 1 9 9 7 / 9 8 p r e s e n t a t i o n , t h e a s s i g n m e n t s a r e : -
( 1 ) T h e c a l c u l a t i o n o f s w i t c h i n g s p e e d s i n h a r d d i s c r e c o r d i n g . T h i s a s s i g n -
m e n t i n v o l v e s t h e i n t e g r a t i o n o f a s y s t e m o f c o u p l e d o r d i n a r y d i e r e n t i a l
e q u a t i o n s ( T h e L a n d a u - L i f s h i t z e q u a t i o n ) , a n d w i l l i n c l u d e a s u b s t a n t i a l
p r o g r a m m i n g e l e m e n t .
( 2 ) t h e m e a s u r e m e n t o f c o e r c i v e f o r c e d i s t r i b u t i o n s f o r c h a r a c t e r i s a t i o n o f r e c o r d -
i n g m e d i a . T h i s a s s i g n m e n t i n v o l v e s t h e n u m e r i c a l d i e r e n t i a t i o n o f e x p e r -
i m e n t a l d a t a , w h i c h w i l l b e t a k e n f r o m a n a c t u a l l a b o r a t o r y e x p e r i m e n t .
R e c o m m e n d e d r e a d i n g f o r t h e c o u r s e i s : -
N u m e r i c a l M e t h o d s f o r M a t h e m a t i c s , S c i e n c e a n d E n g i n e e r i n g
J o h n H . M a t h e w s , P r e n t i c e - H a l l I n t e r n a t i o n a l I n c .
I S B N 0 - 1 3 - 6 2 5 0 4 7 - 5
A p o s t s c r i p t c o p y o f t h e s e n o t e s i s a v a i l i b l e f o r d o w n l o a d i n g f r o m t h e w o r l d
w i d e w e b a t U R L h t t p : / / w w w . m i k e w o n g . d e m o n . c o . u k / i n d e x . h t m l .
A n o t e o n s y m b o l s W e u s e t h e f o l l o w i n g s p e c i a l s y m b o l s : -
s y m b o l m e a n i n g
9 t h e r e e x i s t s . . . s u c h t h a t
8 f o r a l l . . . w e h a v e
2 i s a m e m b e r o f t h e s e t
i s a s u b s e t o f
= ) i m p l i e s t h a t
Z t h e s e t o f n o n - n e g a t i v e i n t e g e r s
R t h e s e t o f a l l r e a l n u m b e r s
-
7/28/2019 Analyse Nume
5/42
2 L e c t u r e 1 - C o m p u t i n g w i t h n u m b e r s
I n m a t h e m a t i c a l m o d e l l i n g , a n a l y t i c a l s o l u t i o n s w i l l b e a v a i l i b l e i n o n l y a s m a l l
c l a s s o f p r o b l e m s . T h e s e i n c l u d e p r o b l e m s w h i c h a r e h i g h l y s y m m e t r i c , w h e r e
c l a s s i c a l f u n c t i o n s a r e a b l e t o d e s c r i b e t h e b e h a v i o u r o f t h e s o l u t i o n s , a n d w h e r e
t h e n u m b e r o f d e g r e e s o f f r e e d o m a r e s u c h t h a t t h e p r o b l e m i s t r a c t a b l e f r o m
t h e p r a c t i c a l s t a n d p o i n t . W h e r e , t h e r e i s a l o w e r d e g r e e o f s y m m e t r y , a n d m a n y
d e g r e e s o f f r e e d o m , o n e g e n e r a l l y h a s t o r e s o r t t o a n u m e r i c a l s o l u t i o n .
T h e u s e o f n u m e r i c a l m a t h e m a t i c s i s n o t l i m i t e d t o m a t h e m a t i c a l m o d e l l i n g
p r o b l e m s . E x p e r i m e n t a l d a t a i s o f t e n a n a l y s e d u s i n g s o p h i s t i c a t e d n u m e r i c a l
t e c h n i q u e s . W e i n t e n d t o i l l u s t r a t e t h e u s e o f c o m p u t i n g t e c h n i q u e s b o t h i n
m o d e l l i n g a n d i n t h e t r e a t m e n t o f e x p e r i m e n a t l d a t a i n t w o p r a c t i c a l a s s i g n m e n t s
( 1 ) t h e c a l c u l a t i o n o f s w i t c h i n g s p e e d s i n h a r d d i s c r e c o r d i n g
( 2 ) t h e m e a s u r e m e n t o f c o e r c i v e f o r c e d i s t r i b u t i o n s f o r c h a r a c t e r i s a t i o n o f r e c o r d -
i n g m e d i a .
W h e r e v e r n u m e r i c a l m a t h e m a t i c s i s t o b e u s e d , o n e e n c o u n t e r s p r o b l e m s o f
t h e r e p r e s e n t a t i o n o f n u m b e r s , w h i c h i s t h e s u b j e c t o f l e c t u r e 1 .
2 . 1 T h e c o m p u t e r r e p r e s e n t a t i o n o f n u m b e r s
I n t e g e r s : M a n y r e a l n u m b e r s c a n b e r e p r e s e n t e d b y n i t e s t r i n g s o f d i g i t s , b u t
m o s t r e a l n u m b e r s r e q u i r e i n n i t e s t r i n g s o f d i g i t s . S i n c e f o r p r a c t i c a l c o m p u -
t a t i o n s o n l y n i t e s t r i n g s o f d i g i t s m u s t b e u s e d , a t r a u n c a t i o n e r r o r i s e n t a i l e d
w h e n r e a l n u m b e r s a r e r e p r e s e n t e d i n c a l c u l a t i o n s . F o r e x a m p l e , m o s t c o m p u t e r
s u b r o u t i n e s f o r e v a l u a t i n g s i n , c o s , e t c . r s t s u b t r a c t o r a d d 2 f r o m t h e a r g u -
m e n t i n o r d e r t o o b t a i n a n a r g u m e n t i n t h e r a n g e
; + . B u t s i n c e r e q u i r e s
a n i n n i t e n u m b e r o f d i g i t s f o r i t s r e p r e s e n t a t i o n , t h e s u b t r a c t i o n e n t a i l s a n e r r o r
w h i c h c h a n g e s t h e r e s u l t .
A n o n - n e g a t i v e i n t e g e r N w i t h n d i g i t s m a y b e r e p r e s e n t e d a c c o r d i n g t o t h e
f o l l o w i n g p o l y n o m i a l s c h e m e
N =
n ; 1
X
i = 0
a
n ; i ; 1
1 0
n ; i ; 1
0 f a
k
2 Z g 9
s o t h a t t h e n u m b e r 2 5 7 i n t h i s d e n a r y r e p r e s e n t a t i o n i s
2 5 7 = 2 1 0
2
+ 5 1 0
1
+ 7 1 0
0
S i n c e c o m p u t e r s s t o r e n u m b e r s a s s t a t e s o f e l e c t r o n i c c o m p o n e n t s , t h e y o f t e n
u s e a b i n a r y r e p r e s e n t a t i o n , s o t h a t a n o n - n e g a t i v e i n t e g e r w i t h n d i g i t s m a y b e
r e p r e s e n t e d a c c o r d i n g t o
N =
n ; 1
X
i = 0
a
n ; i ; 1
2
n ; i ; 1
0 f a
k
2 Z g 1
F o r e x a m p l e , t h e b i n a r y r e p r e s e n t a t i o n o f t h e d e n a r y n u m b e r 1 3 i s ( 1 1 0 1 ) w h i c h
h a s p o l y n o m i a l r e p r e s e n t a t i o n
1 1 0 1 = 1 2
3
+ 1 2
2
+ 0 2
1
+ 1 2
0
-
7/28/2019 Analyse Nume
6/42
F r a c t i o n s : A n o n - n e g a t i v e r e a l n u m b e r x i n d e n a r y r e p r e s e n t a t i o n h a s a n i n t e -
g r a l p a r t x
I
w h i c h i s t h e l a r g e s t i n t e g e r l e s s t h a n o r e q u a l t o x , w h i l e i t s f r a c t i o n a l
p a r t x
F
= x ; x
I
. x
F
c a n h a v e p o l y n o m i a l d e n a r y r e p r e s e n t a t i o n
x
F
=
1
X
i = 1
b
i
1 0
; i
0 f b
k
2 Z g 9
I f k i 2 Z , t h e n t h e f r a c t i o n x
F
i s s a i d t o t e r m i n a t e i f a n d o n l y i f i t i s t r u e t h a t
9 k 8 k + i ] b
k + i
= 0 . I f n o s u c h k e x i s t s , t h e n x
F
r e q u i r e s a n i n n i t e n u m b e r o f
d i g i t s t o r e p r e s e n t i t e x a c t l y . N o w , i f x
I
= ( a
n
a
n ; 1
: : : a
0
) a n d x
F
= ( b
1
b
2
: : : ) t h e w e
c a n w r i t e x = ( a
n
a
n ; 1
: : : a
0
: b
1
b
2
: : : ) w h e r e t h e d e c i m a l p o i n t s e p a r a t e s t h e a
k
f r o m
t h e b
k
.
I n t h e b i n a r y p o l y n o m i a l r e p r e s e n t a t i o n
x
F
=
1
X
i = 1
b
i
2
; i
0 f b
k
2 Z g 1
a n d i n a g e n e r a l n u m b e r b a s e , t h e p o l y n o m i a l r e p r e s e n t a t i o n w i l l b e
x
F
=
1
X
i = 1
b
i
; i
0 f b
k
2 Z g ; 1
W h e n w e u s e c o m p u t e r s f o r n u m e r i c a l c a l c u l a t i o n s w e h a v e t o c o n v e r t b e t w e e n
t h e d e n a r y a n d r e p r e s e n t a t i o n s o f n u m b e r s . I t s o h a p p e n s t h a t n o t e v e r y
n u m b e r w h i c h i s t e r m i n a t i n g i n d e n a r y r e p r e s e n t a t i o n i s a l s o t e r m i n a t i n g i n b i n a r y
r e p r e s e n t a t i o n . T h e r e f o r e , e v e n w h e n a f r a c t i o n c a n b e e x a c t l y r e p r e s e n t e d b y a
n i t e n u m b e r o f d i g i t s i n d e n a r y r e p r e s e n t a t i o n , i t m a y s t i l l e n t a i l a t r u n c a t i o n
e r r o r w h e n c o n v e r t e d t o b i n a r y .
2 . 2 E r r o r s d u e t o t h e c o m p u t e r r e p r e s e n t a t i o n o f n u m b e r s
C o m p u t e r s u s e a n o r m a l i s e d o a t i n g p o i n t t - d i g i t r e p r e s e n t a t i o n
x = ( : b
1
b
2
: : : b
t
)
e
w h e r e ( : b
1
b
2
: : : b
t
) i s c a l l e d t h e m a n t i s s a a n d e i s c a l l e d t h e e x p o n e n t . T h e p r e c i s i o n
o f t h e m a n t i s s a i s d e t e r m i n e d b y t h e w o r d l e n g t h o f t h e c o m p u t e r , a n d t h e e x p o -
n e n t i s b o u n d e d w i t h i n s o m e r a n g e m e M w h e r e m i s a n e g a t i v e i n t e g e r a n d
M i s s o m e p o s i t i v e i n t e g e r . T h e r e f o r e , a l l t h e n u m b e r s w h i c h c a n b e s t o r e d i n
a c o m p u t e r a n d u s e d i n c a l c u l a t i o n s a r e c o n t a i n e d w i t h i n t h e s e t F ( t m M ) .
A n y n u m b e r x t h a t w e u s e i n a c o m p u t e r c o m p u t a t i o n t h a t i s n o t i n t h i s s e t ,
m u s t b e a p p r o x i m a t e d b y a n u m b e r w h i c h i s a m e m b e r o f t h e s e t , i e .
x f l ( x ) 2 F ( t m M )
A n u m b e r x i s c o n v e r t e d t o n o r m a l i s e d o a t i n g p o i n t r e p r e s e n t a t i o n f l ( x ) b y
c h o o s i n g t h e n e a r e s t n o r m a l i s e d o a t i n g p o i n t n u m b e r t o x , a n d a p p l y i n g s o m e
r u l e i n t h e c a s e o f a t i e , s u c h a s r o u n d i n g ( c h o o s i n g t h e n e a r e s t o a t i n g p o i n t
n u m b e r t o x a n d u s i n g a r u l e l i k e r o u n d i n g u p i n t h e c a s e o f a t i e ) o r c h o p p i n g
( c h o o s i n g t h e n e a r e s t o a t i n g p o i n t n u m b e r s m a l l e r i n m a g n i t u d e t h a t x ) , a s l o n g
a s e l i e s w i t h i n t h e r a n g e m e M
1
. T h e d i e r e n c e j x ; f l ( x ) j i s c a l l e d t h e
a b s o l u t e e r r o r .
1
I f e < m o n e h a s a n u n d e r o w c o n d i t i o n , a n d i f e > M o n e h a s a n o v e r o w c o n d i t i o n .
-
7/28/2019 Analyse Nume
7/42
T h e d i s t r i b u t i o n o f o a t i n g p o i n t n u m b e r s i s v e r y u n e v e n
2
s o t h a t f l ( x )
d e p e n d s s t r o n g l y o n x . I t i s a l w a y s p o s s i b l e t o w r i t e a n y n o n z e r o d e c i m a l n u m b e r
x i n t h e f o r m
x = u 1 0
e
+ v 1 0
e ; t
1
1 0
j u j
-
7/28/2019 Analyse Nume
8/42
3 L e c t u r e 2 - E r r o r s a r i s i n g f r o m a r i t h m e t i c a l
o p e r a t i o n s
I n t h e p r e v i o u s l e c t u r e w e i n d i c a t e d s o m e o f t h e e r r o r s a s s o c i a t e d w i t h u s i n g c o m -
p u t e r s t o r e p r e s e n t n u m b e r s . N o d i s c u s s i o n w a s e n t e r e d i n t o a b o u t p e r f o r m i n g
a c t u a l c a l c u l a t i o n s w i t h t h e s e n u m b e r s . I n t h e p r e s e n t l e c t u r e , w e w i l l b e c o n -
c e r n e d w i t h e r r o r s a r i s i n g f r o m d o i n g n u m e r i c a l c a l c u l a t i o n s . I n p a r t i c u l a r , w e a r e
c o n c e r n e d w i t h t h e p r o p a g a t i o n o f e r r o r s a s s o c i a t e d w i t h n u m b e r r e p r e s e n t a t i o n ,
a n d c e r t a i n a v o i d a b l e e r r o r s t h a t c a n o c c u r d u e t o t h e f o r m o f t h e c a l c u l a t i o n
b e i n g p e r f o r m e d .
W e d o n o t c o v e r i s s u e s s u c h a s t h e s t a b i l i t y o f a l g o r i t h m s
3
. T o b e u s e f u l
f o r d o i n g a p a r t i c u l a r c a l c u l a t i o n , a n a l g o r i t h m m u s t b e s t a b l e t h a t i s t o s a y ,
s m a l l c h a n g e s i n t h e i n i t i a l d a t a s h o u l d p r o d u c e s m a l l c h a n g e s i n t h e n a l r e s u l t s .
I f s m a l l c h a n g e s i n t h e i n i t i a l d a t a p r o d u c e l a r g e c h a n g e s i n t h e r e s u l t s , t h e
a l g o r i t h m i s s a i d t o u n s t a b l e
4
.
3 . 1 S u m m a r y f r o m l e c t u r e 1
I n l e c t u r e 1 , i t w a s d e m o n s t r a t e d t h a t
1 c o m p u t e r s c a n n o t s t o r e a l l r e a l n u m b e r s x 2 R , b u t o n l y a d i s c r e t e s u b s e t
o f t h e r e a l n u m b e r s w h i c h w e h a v e d e n o t e d b y F ( t m M ) R
2 t h e d e n s i t y o f y 2 F ( t m M ) i s h i g h l y n o n - u n i f o r m i n R
3 w h e n a n u m b e r x 2 R i s t o b e u s e d i n a c o m p u t e r c a l c u l a t i o n , i t i s r s t a p -
p r o x i m a t e d b y a n u m b e r y = f l ( x ) 2 F ( t m M ) a n d s t o r e d i n n o r m a l i s e d
t - d i g i t o a t i n g p o i n t - r e p r e s e n t a t i o n
4 i n s u c h r e p r e s e n t a t i o n , f l ( x ) h a s t h e f o r m f l ( x ) = ( : b
1
b
2
: : : b
t
)
e
w h e r e
t i s d e t e r m i n e d b y t h e w o r d l e n g t h o f t h e c o m p u t e r , i s t h e n u m b e r - b a s e
s y s t e m u s e d , a n d m e M
T h e i m p l i c a t i o n s o f t h e a b o v e a r e t h a t n u m b e r s s t o r e d i n c o m p u t e r s e n t a i l
e r r o r s e v e n b e f o r e c a l c u l a t i o n s h a v e b e e n p e r f o r m e d . I n p a r t i c u l a r , t h e i m p l i c a t i o n
o f p o i n t 2 a b o v e i s t h a t t h e e r r o r e n t a i l e d i n s t o r i n g t h e n u m b e r x d e p e n d s s e n -
s i t i v e l y o n x . F r o m p o i n t s 3 a n d 4 , i t i s c l e a r t h a t t h e e r r o r a l s o d e p e n d s o n t h e
w o r d l e n g t h o f t h e c o m p u t e r , a n d t h e t h e m a g n i t u d e o f t h e n u m b e r s i t i s p o s s i b l e
t o s t o r e i s b o u n d e d a b o v e a n d b e l o w .
A l s o , t h e r e l a t i v e e r r o r
C
( x ) ,
R
( x ) f o r c o m p u t e r s w h i c h u t i l i s e c h o p p i n g
o r r o u n d i n g r u l e s o f a p p r o x i m a t i o n a r e r e s p e c t i v e l y g i v e n b y
C
( x ) =
1 ; t
a n d
R
( x ) =
1 ; t
= 2 , E q s . 1 a n d 2 r e s p e c t i v e l y . W e n o w w a n t t o s e e w h a t f u r t h e r
e r r o r s a r e e n t a i l e d w h e n s o m e a r i t h m e t i c i s d o n e .
3
A n a l g o r i t h m i s a n i t e s e q u e n c e o f r u l e s f o r p e r f o r m i n g a c e r t a i n c a l c u l a t i o n s u c h t h a t , a t
e a c h s t e p , t h e r u l e s d e t e r m i n e e x c t l y w h a t i s t o b e d o n e i n t h e f o l l o w i n g s t e p .
4
T h i s n u m e r i c a l i n s t a b i l i t y i s n o t t o b e c o n f u s e d w i t h t h e m a t h e m a t i c a l i n s t a b i l i t y o f a p r o b -
l e m , w h i c h i s c a l l e d i l l - c o n d i t i o n i n g . I f a p r o b l e m i s i l l - c o n d i t i o n e d , t h e n n o m a t t e r h o w g o o d
t h e a l g o r i t h m i s , t h e r e s u l t s w i l l b e e x t r e m e l y s e n s i t i v e t o s m a l l c h a n g e s i n t h e i n i t i a l d a t a .
-
7/28/2019 Analyse Nume
9/42
3 . 2 E r r o r a c c u m u l a t i o n
L e t d e n o t e a n y o f t h e b i n a r y a r i t h m e t i c a l o p e r a t i o n s ( + ; ) . A l s o , l e t
x y
2F ( t m M ) a n d d e n o t e b y f l x
y ]
2F ( t m M ) t h e c o m p u t e d o a t i n g
p o i n t v a l u e o f x y u s i n g t h e s y s t e m F ( t m M )
5
. T h e n
C
= ( x
C
; x ) = x a l l o w s
o n e t o w r i t e x
C
= x ( 1 +
C
) a s a r e l a t i o n b e t w e e n t h e e x a c t a n d c h o p p e d v a l u e s ,
w h e r e
C
f r o m E q . 1 , a n d w h e r e a s i m i l a r r e l a t i o n h o l d s f o r x
R
i n t e r m s o f
R
. T h e n , o n e h a s
f l x y ] = ( x y ) ( 1 + ) ( 3 )
A c c u m u l a t i o n o f e r r o r s C o n s i d e r t h e s u m
s = x
1
+ x
2
+ x
3
+ x
4
+ x
5
( 4 )
A d d i n g f r o m t h e l e f t , t h e c o m p u t e d o a t i n g p o i n t s u m i s
f l ( s ) = f l f l f l f l x
1
+ x
2
] + x
3
] + x
4
] + x
5
] ( 5 )
O n u s i n g E q . 3 w i t h + f o r
f l x
1
+ x
2
] = x
1
( 1 +
1
) + x
2
( 1 +
2
)
f l f l x
1
+ x
2
] + x
3
] = f l ( x
1
( 1 +
1
) + x
2
( 1 +
2
) ) + x
3
]
= ( x
1
( 1 +
1
) + x
2
( 1 +
2
) ) ( 1 +
3
) + x
3
( 1 +
4
)
= x
1
( 1 +
1
) ( 1 +
3
) + x
2
( 1 +
2
) ( 1 +
3
) + x
3
( 1 +
4
)
e t c . , s o t h a t
f l ( s ) = x
1
( 1 +
1
) + x
2
( 1 +
2
) + x
3
( 1 +
3
) + x
4
( 1 +
4
) + x
5
( 1 +
5
)
= x
1
+ x
2
+ x
3
+ x
4
+ x
5
+ x
1
1
+ x
2
2
+ x
3
3
+ x
4
4
+ x
5
5
= s + x
1
1
+ x
2
2
+ x
3
3
+ x
4
4
+ x
5
5
( 6 )
w h e r e E q . 4 h a s b e e n u s e d i n t h e n a l s t e p , a n d w h e r e
1 +
1
= ( 1 +
1
) ( 1 +
3
) ( 1 +
5
) ( 1 +
7
)
1 +
2
= ( 1 +
2
) ( 1 +
3
) ( 1 +
5
) ( 1 +
7
)
1 +
3
= ( 1 +
4
) ( 1 +
5
) ( 1 +
7
)
1 +
4
= ( 1 +
6
) ( 1 +
7
)
1 +
5
= ( 1 +
8
)
U s i n g E q . 6 o n e t h e n a r i v e s a t a n e x p r e s s i o n f o r t h e b o u n d o n t h e e r r o r f o r t h e
c o m p u t e d s u m
j f l ( s ) ; s j x
1
1
+ x
2
2
+ x
3
3
+ x
4
4
+ x
5
5
5
N o t e t h a t y 6= 0 i f r e p r e s e n t s .
-
7/28/2019 Analyse Nume
10/42
3 . 3 L o s s o f s i g n i c a n c e
T h e e r r o r s d i s c u s s d s o f a r a r i s e a s a r e s u l t o f t h e m a c h i n e r e p r e s e n t a t i o n o f n u m -
b e r s , a n d t h e c o n s e q u e n c i e s w h i c h f o l l o w w h e n a r i t h m e t i c a l o p e r a t i o n s a r e c a r r i e d .
T h e y a r e p r e s e n t i n n u m e r i c a l c a l c u l a t i o n s b e c a u s e m a c h i n e s t o r a g e o f n u m b e r s
i s d i s c r e t e , w h e r e a s t h e n u m b e r s w e w a n t t o u s e a r e p a r t o f a c o n t i n u u m . G i v e n
a p a r t i c u l a r m a c h i n e e n v i r o n m e n t , t h e r e i s n o t h i n g t h a t w e c a n d o t o a v o i d s u c h
e r r o r s . H o w e v e r , t h e r e a r e e r r o r s w h i c h o c c u r w h e n c a r r y i n g o u t a r i t h m e t i c o p -
e r a t i o n s w h i c h c a n b e a v o i d e d .
C o n s i d e r t h e o a t i n g p o i n t s u b t r a c t i o n i n t h e r e p r e s e n t a t i o n F ( t m M )
o f t w o n u m b e r s w h i c h a r e v e r y c l o s e i n n u m e r i c a l v a l u e . W e c a n n o t s p e c i f y t h e
n u m b e r s t o m o r e t h a n t - d i g i t a c c u r a c y , w h i c h m a y b e i n e r r o r b y 0 : 5
1 ; t
. I f
t h e r e s u l t o f t h e s u b t r a c t i o n i s o f t h e s a m e o r d e r a s t h e t - t h d i g i t s i n t h e o r i g i n a l
n u m b e r s , t h e e r r o r i n t h e r e s u l t w i l l b e o f t h e s a m e o r d e r a s t h e r e s u l t i t s e l f . F o r
i n s t a n c e , c o n s i d e r
f ( x ) = 1
;c o s x
n e a r t o x = 0 . F r o m E q . 2 t h e b o u n d o n t h e e r r o r i n c a l c u l a t i n g c o s x c l o s e
t o x = 0 i s
1
2
1 ; t
j c o s x j
1
2
1 ; t
w h i c h m a y b e a s l a r g e o r l a r g e r t h a n f ( x ) .
W h e n e v e r s u c h a c o n d i t i o n c o u l d a p p e a r , o n e c a n c i r c u m v e n t t h e p r o b l e m b y a
j u d i c i o u s c h o i c e o f a l t e r n a t i v e e x p r e s s i o n
6
6
S e e p r o b l e m 3 .
-
7/28/2019 Analyse Nume
11/42
4 L e c t u r e 3 - S o l v i n g N o n - L i n e a r E q u a t i o n s
I t o f t e n h a p p e n s t h a t w e h a v e t o s o l v e a n o n - l i n e a r e q u a t i o n f o r e i t h e r o n e o r m o r e
t h a n o n e o f i t s r o o t s . F o r a g e n e r a l q u a d r a t i c , c u b i c o r q u a r t i c e q u a t i o n t h e r e
a r e s t a n d a r d f o r m u l a s . T h e r e f o r e , i f t h e p r o b l e m i n v o l v e s a n e x p l i c i t e q u a t i o n o f
q u a d r a t i c , c u b i c o r q u a r t i c d e g r e e , t h e n t h e r e a r e n o r e a l d i c u l t i e s
7
. H o w e v e r ,
o n e d o e s n o t a l w a y s k n o w e x p l i c i t l y t h e f o r m o f t h e e q u a t i o n
8
, a n d w h e v e r o n e
d o e s e x p l i c i t l y k n o w , t h i s , p r o b l e m s o f d e g r e e g r e a t e r t h a n 4 w h i c h a r e n o n -
f a c t o r a b l e r e q u i r e n u m e r i c a l c a l c u l a t i o n t o n d a n a p p r o x i m a t e s o l u t i o n . A s s u c h ,
a l l t h e s o u r c e s o f e r r o r d i s c u s s e d i n l e c t u r e s 1 a n d 2 a p p l y
9
.
T h e p r o b l e m t o b e s t u d i e d h e r e i s t o n d a s o l u t i o n x o f t h e n o n l i n e a r
e q u a t i o n
f ( x ) = 0 ( 7 )
W e a l s o h e r e i n t r o d u c e t h e c o n c e p t o f i t e r a t i o n , w h i c h i s e x t e n s i v e l y u s e d i n
n u m e r i c a l c a l c u l a t i o n s . T h i s c o n s i s t s i n g e n e r a t i n g a s e q u e n c e x
0
x
1
: : : x
k
s u c h
t h a t
l i m
k ! 1
x
k
= x
S i n c e i n p r a c t i c a l c a l c u l a t i o n s o n l y a n i t e n u m b e r o f i t e r a t i o n s c a n b e c o m p u t e d ,
w e c a n o n l y a p p r o x i m a t e x t o a g i v e n a c c u r a c y . T h e n , o n e m u s t b e c o n c e r n e d
w i t h i m p o s i n g c e r t a i n t e r m i n a t i n g c o n d i t i o n s o n t h e c a l c u l a t i o n s s u c h t h a t , w h e n
t h e s e a r e s a t i s e d a t a c e r t a i n k , t h e n t h e s o l u t i o n i s d e e m e d t o h a v e b e e n f o u n d .
4 . 1 F i x e d - p o i n t i t e r a t i o n
M a n y o f t h e c o m m o n l y u s e d i t e r a t i v e m e t h o d s t a k e t h e f o r m o f s u c c e s s i v e s u b s t i -
t u t i o n
x
k + 1
= g ( x
k
) ( 8 )
w h e r e g ( x ) i s c a l l e d t h e i t e r a t i o n f u n c t i o n . I f i t i s t h e c a s e t h a t
l i m
k ! 1
x
k
= ~x = g ( ~x )
t h e n ~ x i s c a l l e d a x e d p o i n t o f g . T h u s , t h e p r o b l e m o f n d i n g a z e r o p o i n t o f f
c a n o f t e n b e s o l v e d b y n d i n g a x e d p o i n t o f g .
O n e c a n t h e n p u t t h e p r o b l e m 7 i n t h e f o r m 8 b y w r i t i n g g ( x ) = f ( x ) + x .
H o w e v e r , t h e r e w i l l b e m a n y w a y s o f p u t t i n g 7 i n t h e f o r m 8 . C o n s i d e r t h e
f u n c t i o n
7
O n e s t i l l h a s t o t a k e c a r e w i t h r e g a r d t o p r o b l e m s s u c h a s l o s s o f s i g n i c a n c e .
8
T h e p r o b l e m m a y p r e s e n t i t s e l f a s t h e s o l u t i o n o f a d i e r e n t i a l e q u a t i o n w h i c h d e p e n d s
u p o n t h e i n i t i a l c o n d i t i o n , s o t h a t o n e h a s a r u l e f o r e v a l u a t i n g f ( x ) f o r a n y a r g u m e n t - i e . ,
s o l v e t h e d i e r e n t i a l e q u a t i o n - w h e r e a s t h e e x p l i c i t f o r m o f f ( x ) i s n o t k n o w n .
9
F o r i n s t a n c e , t h e p o l y n o m i a l P
6
( x ) = ( 1 ; x )
6
h a s t h e s i n g l e s o l u t i o n x = 1 . H o w e v e r , i f
o n e w e r e t o u s e t h e u n f a c t o r e d f o r m
P
6
( x ) = 1 ; 6 x + 1 5 x
2
; 2 0 x
3
+ 1 5 x
4
; 6 x
5
+ x
6
e v a l u a t e i t u s i n g a h i g h p r e c i s i o n ( l o n g w o r d l e n g t h ) c o m p u t e r , a n d p l o t i t b e t w e e n 0 . 9 a n d 1 . 1 ,
o n e w o u l d n d t h a t t h e r e a r e m a n y a p p a r e n t z e r o ' s r a n g i n g b e t w e e n a b o u t 0 . 9 9 4 a n d 1 . 0 0 6 .
T h u s , u s e o f t h e e x p a n d e d f o r m o f P
6
( x ) l e a d s t o a p p a r e n t l y a c c e p t a b l e e s t i m a t e s o f t h e r o o t
w h i c h a r e c o r r e c t o n l y t o 2 d e c i m a l d i g i t s . T h e r e a s o n f o r t h i s b e h a v i o u r l i e s s o l e l y i n r o u n d - o
e r r o r , l o s s s i g n i c a n c e , e t c .
-
7/28/2019 Analyse Nume
12/42
f ( x ) = x
2
; x ; 2 ( 9 )
O n e c a n u s e a g ( x ) i n a n y o f t h e f o r m s
( 1 ) g ( x ) = x
2
; 2
( 2 ) g ( x ) =
p
2 + x
( 3 ) g ( x ) = 1 +
2
x
( 4 ) g ( x ) = x ;
x
2
; x ; 2
m
8 m 2 Z
O n e t h e n s t a r t s t h e c a l c u l a t i o n w i t h a n i n i t i a l v a l u e x
0
w h i c h i s i n t u i t i v e 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 , a n d u s e s E q . 8 t o g e n e r a t e t h e i t e r a t i o n s e q u e n c e .
4 . 2 c r i t e r i a f o r c o n v e r g e n c e
I t s o m e t i m e s h a p p e n s t h a t n o t a l l i t e r a t i o n s e q u e n c e s c o n v e r g e
1 0
. A l s o , t h e f u n c -
t i o n g h a s t o b e c h o s e n s u c h t h a t i t i s p o s s i b l e t o g e n e r a t e t h e i t e r a t i o n s e q u e n c e .
F o r e x a m p l e , w i t h g ( x ) = ;
p
x , x
0
n e c e s s a r i l y h a s t o b e p o s i t i v e , b u t t h e n t h a t
w o u l d n e c e s s a r i l y m a k e x
1
= g ( x
0
) n e g a t i v e . T h e r e f o r e , x
2
c a n n o t b e c a l c u l a t e d .
H o w e v e r , i f i t i s t h e c a s e t h a t
9 I = a b ] 2 R 8 x
0
2 I g ( x ) 2 I
a n d t h a t g ( x ) i s c o n t i n u o u s i n I , t h e n i t i s g u a r a n t e e d t h a t t h e r e i s a x e d p o i n t
o f g i n I . T h i s i s s o b e c a u s e g ( a ) a a n d g ( b ) b . T h e r e f o r e i f h ( x ) = g ( x ) ; x
s a t i s e s h ( a ) 0 a n d h ( b ) 0 . I f g ( x ) i s c o n t i n u o u s i n I t h e n s o i s h ( x ) , a n d s o
h ( x ) v a n i s h e s s o m e w h e r e i n I b y t h e i n t e r m e d i a t e v a l u e t h e o r e m . T h i s z e r o o f h
i s a x e d p o i n t o f g .
I n g e n e r a l , t h e x e d p o i n t ~ x i s l o c a t e d a t t h e i n t e r s e c t i o n o f t h e c u r v e s y = x
a n d y = g ( x ) . N o w , s u p p o s e t h a t
9 K > 0 8 x 2 I j g
0
( x ) j K ( 1 0 )
a n d l e t e
n
= ~x ; x
n
. T h e n
e
n
= ~x ; x
n
= g ( ~x ) ; g ( x
n ; 1
)
= g
0
(
n
) e
n ; 1
w h e r e E q . 8 h a s b e e n u s e d i n t h e s e c o n d s t e p a n d t h e m e a n - v a l u e t h e o r e m i n t h e
t h i r d s t e p . T h e n , o n u s i n g E q . 1 0 w e h a v e
je
n
j K
je
n ; 1
j
G e n e r a l i s i n g t h e a b o v e r e s u l t
j e
n
j K j e
n ; 1
j K
2
j e
n ; 2
j : : : K
n
j e
0
j ( 1 1 )
1 0
S e e p r o b l e m 4 .
-
7/28/2019 Analyse Nume
13/42
a n d s i n c e f o r 0 K 1 = 2 , g
0
( x ) > 1 w h e r e a s , i f w e c h o o s e g ( x ) =
p
2 + x a s i t e r a t i o n f u n c t i o n
0 g
0
( x ) 1 =
p
8 .
4 . 3 T h e N e w t o n - R a p h s o n m e t h o d
E q . 1 1 s h o w s t h a t i t e r a t i o n f u n c t i o n s w i t h d e r i v a t i v e s w i t h s m a l l e r a b s o l u t e v a l u e
c o n v e r g e f a s t e r t h a n t h o s e w i t h l a r g e r d e r i v a t i v e s . F o r f a s t c o n v e r g e n c e t h e r e f o r e ,
w e s h o u l d c h o o s e a f o r m o f t h e i t e r a t i o n f u n c t i o n w h i c h i s m i n i m i s e d a t ~ x . I f f
i s d i e r e n t i a b l e t h e n a x e d p o i n t f o r m w i t h t h e d e s i r a b l e f e a t u r e s i s d e r i v e d b y
e x p a n d i n g f i n a T a y l o r s e r i e s a n d r e t a i n i n g o n l y t h e l i n e a r t e r m , t h a t i s
f ( x + h ) = f ( x ) + f
0
( x ) h
a n d s o l v i n g t h i s l i n e a r i s e d e q u a t i o n , t h a t i s s o l v i n g f ( x + h ) = 0 w i t h f ( x + h ) i n
t h e a b o v e l i n e a r a p p r o x i m a t i o n , i n s t e a d o f f ( x ) = 0 w i t h a l l t e r m s p r e s e n t . T h i s
a m o u n t s t o r e p l a c i n g f ( x ) b y a l i n e a r f u n c t i o n l ( x ) t a n g e n t t o f ( x
0
) , t h a t i s
l ( x ) = f ( x
0
) + f
0
( x
0
) ( x ; x
0
) ( 1 2 )
a n d s o l v i n g l ( x ) = 0 , t h a t i s
x = x
0
; f ( x
0
) = f
0
( x
0
)
I n o t h e r w o r d s , w e h a v e a x e d p o i n t i t e r a t i o n w i t h i t e r a t i o n f u n c t i o n
g ( x ) = x ; f ( x ) = f
0
( x ) ( 1 3 )
O n e n o w n d s t h a t
g
0
( ~x ) = 1 ;
( f
0
( ~x ) )
2
; f ( ~x ) f
0 0
( ~x )
( f
0
( ~x ) )
2
w h i c h i s z e r o s i n c e f ( ~x ) = 0 . T h e m e t h o d w h i c h u s e s t h e i t e r a t i o n f u n c t i o n
a c c o r d i n g t o E q . 1 3 i s c a l l e d t h e N e w t o n - R a p h s o n m e t h o d . I t s h o u l d b e n o t e d
t h a t a s o l u t i o n d e p e n d s u p o n t h e c o n d i t i o n f
0
( x ) 6= 0 . I f f
0
( x ) i s v e r y s m a l l i n
t h e n e i g h b o u r h o o d o f a s o l u t i o n , t h e n t h e s o l u t i o n d e t e r m i n e d b y t h e N e w t o n -
R a p s h o n m e t h o d w i l l b e v e r y s e n s i t i v e t o c h a n g e s i n t h e i n i t i a l d a t a . F o r i n s t a n c e ,
i f f ( x ) = x
5
+ 1 0
; 4
x = 0 , t h e n ~ x = 0 i s a s o l u t i o n . H o w e v e r , f
0
( 0 ) = 1 0
; 4
w h i c h
i s s m a l l . A t x = 0 : 1 , w e h a v e f ( 0 : 1 ) = 2 1 0
; 5
. T h e r e f o r e , i f t h e p r e c i s i o n
w i t h w h i c h w e d e t e r m i n e t h a t a s o l u t i o n h a s b e e n f o u n d a c c o r d i n g t o f ( x ) = 0
i s o f t h i s o r d e r , w e c a n g e t a s o l u t i o n o f x = 0 : 1 e v e n t h o u g h t h e p r e c i s i o n o f t h e
s o l u t i o n k x ; ~x k = 0 : 1 i s a b o u t 5 0 0 0 t i m e s l a r g e r t h a n t h e p r e c i s i o n o f f . S u c h a
p r o b l e m i s s a i d t o b e i l l - c o n d i t i o n e d .
-
7/28/2019 Analyse Nume
14/42
5 L e c t u r e 6 - S y s t e m s o f l i n e a r e q u a t i o n s ( 1 )
5 . 1 I n t r o d u c t i o n
A s y s t e m o f m l i n e a r e q u a t i o n s i n n u n k n o w n s i s u s u a l l y e x p r e s s e d i n t h e f o l l o w i n g
f o r m
a
1 1
x
1
+ a
1 2
x
2
+ : : : + a
1 n
x
n
= b
1
a
2 1
x
1
+ a
2 2
x
2
+ : : : + a
2 n
x
n
= b
2
:
:
:
a
m 1
x
1
+ a
m 2
x
2
+ : : : + a
m n
x
n
= b
m
w h e r e t h e a
i j
a n d b
i
a r e g i v e n o a t i n g p o i n t n u m b e r s a n d t h e x
i
a r e t o b e d e -
t e r m i n e d s o a s t o s a t i s f y t h e s y s t e m . I t i s c o n v e n i e n t t o e x p r e s s t h e s y s t e m i n
m a t r i x f o r m
A x = b ( 1 4 )
w h e r e A i s t h e m n m a t r i x
A =
0
B
B
B
B
B
B
B
B
@
a
1 1
a
1 2
: : : a
1 n
a
2 1
a
2 2
: : : a
2 n
:
:
:
a
m 1
a
m 2
: : : a
m n
1
C
C
C
C
C
C
C
C
A
( 1 5 )
a n d x a n d b a r e t h e c o l u m n v e c t o r s
x =
0
B
B
B
B
B
B
B
B
@
x
1
x
2
:
:
:
x
n
1
C
C
C
C
C
C
C
C
A
b =
0
B
B
B
B
B
B
B
B
@
b
1
b
2
:
:
:
b
n
1
C
C
C
C
C
C
C
C
A
( 1 6 )
M a t r i c e s a s s o c i a t e d w i t h l i n e a r s y s t e m s c a n b e c l a s s i e d a s e i t h e r d e n s e
o r s p a r s e . D e n s e m a t r i c e s h a v e v e r y f e w z e r o v a l u e d e l e m n e t s , a n d t e n d t o b e
r e l a t i v e l y s m a l l , w h e r e a s s p a r s e m a t r i c e s h a v e v e r y f e w n o n z e r o v a l u e d e l e m e n t s ,
a n d t e n d t o b e r e l a t i v e l y l a r g e . S p a r s e m a t r i c e s u s u a l l y a r i s e f r o m a t t e m p t s t o
s o l v e d i e r e n t i a l e q u a t i o n s b y n i t e d i e r e n c e o r n i t e e l e m e n t m e t h o d s .
5 . 1 . 1 S o l v a b i l i t y o f s y s t e m s o f l i n e a r e q u a t i o n s
E q . 1 4 f a l l s i n t o o n e o f t h r e e c a t e g o r i e s : -
1 i f t h e s y s t e m h a s n o s o l u t i o n , t h e e q u a t i o n s a r e s a i d t o b e i n c o n s i s t e n t , a s
f o r e x a m p l e
2 x
1
+ 3 x
2
= 5
4 x
1
+ 6 x
2
= 1
-
7/28/2019 Analyse Nume
15/42
2 i f t h e s y s t e m h a s m a n y s o l u t i o n s , t h e s y s t e m i s s a i d t o b e d e p e n d e n t , a s f o r
e x a m p l e
2 x
1
+ 3 x
2
= 5
4 x
1
+ 6 x
2
= 1 0
3 i f t h e s y s t e m h a s e x a c t l y o n e s o l u t i o n f o r e v e r y b , i t i s s a i d t o b e n o n -
s i n g u l a r . I n t h i s c a s e w e u s u a l l y s p e a k o f t h e n o n - s i n g u l a r i t y o f t h e c o e -
c i e n t m a t r i x A . I f t h i s i s t h e c a s e , t h e n t h e h o m o g e n e o u s e q u a t i o n A x = 0
h a s o n l y t h e t r i v i a l s o l u t i o n
1 1
x = 0 .
H e r e , w e w i l l b e c o n c e r n e d o n l y w i t h p r o b l e m s w h i c h f a l l i n t o t h e t h i r d
c a t e g o r y { n o n s i n g u l a r s y s t e m s . F o r s u c h s y s t e m s , i t i s n e c e s s a r y t h a t
t h e n u m b e r o f e q u a t i o n s e q u a l s t h e n u m b e r s o f u n k n o w n s , i e . , i n E q . 1 5
m = n , s o t h a t A i s a n n n s q u a r e m a t r i x
A i s i n v e r t i b l e .
A f r e q u e n t l y q u o t e d t e s t f o r i n v e r t i b i l i t y i s b a s e d u o p n w h e t h e r d e t ( A ) 6= 0 . I f
t h i s i s c a s e
1 2
, t h e n i t i s p o s s i b l e t o e x p r e s s t h e s o l u t i o n i n t e r m s o f d e t e r m i n a n t s
b y u s i n g C r a m e r ' s r u l e
1 3
. H o w e v e r , f o r p r o b l e m s i n w h i c h n i s l a r g e C r a m e r ' s
r u l e i s n o t o f p r a c t i c a l i n t e r e s t s i n c e t h e c a l c u l a t i o n o f d e t e r m i n a n t s i s i n g e n e r a l
o f t h e s a m e o r d e r o f d i c u l t y a s s o l v i n g a l i n e a r s y s t e m i t s e l f .
N u m e r i c a l m e t h o d s f o r s o l v i n g l i n e a r s y s t e m s m a y b e d i v i d e d i n t o t w o c a t -
e g o r i e s ,
d i r e c t : t h e s e y i e l d t h e e x a c t s o l u t i o n i n a n i t e n u m b e r o f e l e m e n t a r y a r i t h -
m e t i c o p e r a t i o n s s u b j e c t t o r o u n d - o a n d o t h e r e r r o r s
1 4
i t e r a t i v e : t h e s e s t a r t w i t h a n i n i t i a l a p p r o x i m a t i o n , a n d b y a p p l y i n g a s u i t -
a b l e a l g o r i t h m , s u c c e s s i v e l y b e t t e r a p p r o x i m a t i o n s a r e g e n e r a t e d .
D i r e c t m e t h o d s a r e u s u a l l y b e t t e r s u i t e d t o h a n d l i n g p r o b l e m s c h a r a c t e r i s e d b y
d e n s e c o e c i e n t m a t r i c e s , w h e r e a s i t e r a t i v e m e t h o d s a r e m o r e s u i t a b l e f o r d e a l i n g
w i t h p r o b l e m s c h a r a c t e r i s e d b y s p a r s e c o e c i e n t m a t r i c e s .
1 1
T h i s w i l l b e i m p o r t a n t l a t e r w h e n t h e a l g e b r a i c e i g e n v a l u e p r o b l e m i s d i s c u s s e d i n s e c t i o n
6 . 1
1 2
I f d e t ( A ) i s s m a l l , i e . i f t h e p r o b l e m i s n e a r l y s i n g u l a r , t h e n o n e h a s a n i l l - c o n d i t i o n e d
p r o b l e m . F o r e x a m p l e , t h e e q u a t i o n s x ; y = 1 a n d x ; 1 : 0 0 0 1 y = 0 h a v e s o l u t i o n x = 1 0 0 0 1 ,
y = 1 0 0 0 0 . H o w e v e r , t h e e q u a t i o n s x ; y = 1 a n d x ; 0 : 9 9 9 9 y = 0 h a v e s o l u t i o n x = ; 9 9 9 9 ,
y = ; 1 0 0 0 0 ! ! ! Y e t , t h e c o e c i e n t s i n t h e t w o s e t s d i e r b y a t m o s t t w o u n i t s i n t h e f o u r t h
d e c i m a l p l a c e .
1 3
C r a m e r ' s r u l e s t a t e s t h a t t h e s o l u t i o n t o a n n n l i n e a r s y s t e m c a n b e w r i t t e n d o w n i n
t e r m s o f t h e d e t e r m i n a n t s D , D
1
, D
2
, e t c . , w h e r e D = d e t ( A ) , a n d t h e D
i
a r e d e n e d a s t h e
d e t e r m i n a n t s o f t h e m a t r i c e s o b t a i n e d b y r e p l a c i n g t h e i - t h c o l u m n o f A b y t h e c o l u m n v e c t o r
b .
1 4
I n p r a c t i c e , b e c a u s e c o m p u t e r s u s e n i t e l e n g t h o a t i n g p o i n t r e p r e s e n t a t i o n s , e x t r e m e l y
p o o r r e s u l t s c a n b e o b t a i n e d .
-
7/28/2019 Analyse Nume
16/42
5 . 2 D i r e c t m e t h o d s
5 . 2 . 1 D e n i t i o n s
T h e m a t r i x e l e m e n t s o f A f a l l i n t o t h e f o l l o w i n g c a t e g o r i e s : -
1 t h o s e f o r m i n g t h e s e t
fa
i i
1
i
n
ga r e c a l l e d t h e d i a g o n a l e l e m e n t s o f A
2 t h e e l e m e n t s f a
i j
i 6= j g a r e t h e o - d i a g o n a l e l e m e n t s .
2 a O f t h e s e , t h e s u b s e t
fa
i j
i < j
ga r e c a l l e d t h e s u p e r d i a g o n a l e l e m e n t s ,
2 b t h e e l e m e n t s f a
i j
i > j g a r e t h e s u b d i a g o n a l e l e m e n t s .
N o w , i f a l l e l e m e n t s i n c a t e g o r y 2 , i e . a l l o - d i a g o n a l e l e m e n t s a r e z e r o , A i s s a i d
t o b e a d i a g o n a l m a t r i x . I f a l l e l e m e n t s i n c a t e g o r y 2 b a r e z e r o w h i l e t h o s e i n
2 a a r e n o t a l l z e r o , t h e n A i s c a l l e d a n u p p e r - t r i a n g u l a r m a t r i x , w h i l e i f a l l t h o s e
e l e m e n t s i n c a t e g o r y 2 a a r e z e r o a n d t h o s e i n c a t e g o r y 2 b a r e n o t a l l z e r o , A i s
c a l l e d a l o w e r - t r i a n g u a l r m a t r i x .
5 . 2 . 2 T h e b a c k s u b s t i t u t i o n a l g o r i t h m
I f t h e c o e c i e n t m a t r i x A i n E q . 1 4 i s d i a g o n a l t h e n t h e s o l u t i o n c a n b e s i m p l e
w r i t t e n d o w n a s
x
1
=
b
1
a
1 1
x
2
=
b
2
a
2 2
: : : : x
n
=
b
n
a
n n
i f a l l o f t h e a
i i
a r e n o n z e r o .
A s l i g h t l y m o r e g e n e r a l f o r m c o n s i s t s i n A b e i n g u p p e r - t r i a n g u l a r . T h e n , t h e
s y s t e m o f e q u a t i o n s a r e
a
1 1
x
1
+ a
1 2
x
2
+ : : : + a
1 n
x
n
= b
1
a
2 2
x
2
+ : : : + a
2 n
x
n
= b
2
:
:
:
a
n ; 1 n ; 1
x
n ; 1
+ a
n ; 1 n
x
n
= b
n ; 1
a
n n
x
n
= b
n
( 1 7 )
F r o m t h e l a s t , o r n - t h r o w ,
x
n
=
b
n
a
n n
( 1 8 )
T h e p e n n u l t i m a t e , o r ( n - 1 ) - t h r o w i s
b
n ; 1
= a
n ; 1 n ; 1
x
n ; 1
+ a
n ; 1 n
x
n
= ) x
n ; 1
=
b
n ; 1
; a
n ; 1 n
x
n
a
n ; 1 n ; 1
w h e r e x
n
o n t h e r i g h t h a n d s i d e i s k n o w n f r o m E q . 1 8 . N o w x
n
a n d x
n ; 1
w h i c h
a r e n o w k n o w n , c a n b e u s e d i n t h e ( n - 2 ) - t h r o w t o d e t e r m i n e x
n ; 2
, e t c . T h i s
p r o c e d u r e f o r s o l v i n g a n u p p e r t r i a n g u l a r s y s t e m o f l i n e a r e q u a t i o n s i s c a l l e d t h e
b a c k s u b s t i t u t i o n a l g o r i t h m .
-
7/28/2019 Analyse Nume
17/42
5 . 3 G a u s s i a n e l i m i n a t i o n
M o s t o f t h e p r o b l e m s e n c o u n t e r e d i n 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 d o n o t
p r e s e n t t h e m s e l v e s i n t h e u p p e r t r a i n g u l a r f o r m . I f t h e r e i s a w a y o f t r a n s f o r m i n g
a g e n e r a l s q u a r e m a t r i x i n t o t h e u p p e r t r i a n g u l a r f o r m , t h e n u p o n u s i n g t h i s o n e
i s t h e n i n a p o s i t i o n t o i m p l e m e n t t h e b a c k s u b s t i t u t i o n a l g o r i t h m a n d s o l v e t h e
p r o b l e m . T h e m o s t f r e q u e n t l y u s e d m e t h o d i s G a u s s i a n e l i m i n a t i o n . W e r s t
n o t e t h a t t h e s o l u t i o n t o t h e s y s t e m o f l i n e a r e q u a t i o n s i s i n v a r i a n t w i t h r e s p e c t
t o t h e e l e m e n t a r y r o w o p e r a t i o n s : -
1 m u l t i p l i c a t i o n o f o n e o f t h e e q u a t i o n s b y a n o n - z e r o c o n s t a n t
2 r e p l a c i n g a n e q u a t i o n b y t h e s u m o f t h e e q u a t i o n a n y o t h e r e q u a t i o n i n t h e
s y s t e m
3 i n t e r c h a n g i n g a n y t w o e q u a t i o n s
4 a c o m b i n a t i o n o f 1 a n d 2 a b o v e .
5 . 3 . 1 T h e r e d u c t i o n a l g o r i t h m
O n e c a n n o w s e e t h a t r e p e a t e d a p p l i c a t i o n o f e l e m e n t a r y r o w o p e r a t i o n s , u n d e r
w h i c h t h e s o l u t i o n o f t h e s y s t e m i s i n v a r i a n t , c a n t r a n s f o r m t h e o r i g i n a l s y s t e m
i n t o u p p e r - t r i a n g u l a r f o r m . T h i s i s a c h i e v e d i n t h e w a y o u t l i n e b e l o w .
F i r s t r e d u c t i o n s t e p : W e r s t e l i m i n a t e a l l c o e c i e n t s o f x
1
a p a r t f r o m t h a t
o c c u r r i n g i n t h e r s t r o w b y
1 . 1 m o v e t o e a c h r o w i n t u r n s t a r t i n g f r o m r o w 2
1 . 2 a t r o w i a d d t h e c o n s t a n t m
i 1
=
;a
i 1
= a
1 1
m u l t i p l i e d b y t h e c o r r e s p o n d i n g
c o e c i e n t o f e q u a t i o n 1
1 . 3 d o t h e s a m e t o t h e r i g h t h a n d s i d e o f r o w i
1 5
.
A f t e r a p p l i c a t i o n o f t h e a b o v e p r o c e d u r e , t h e s y s t e m o f e q u a t i o n s l o o k s l i k e
a
1 1
x
1
+ a
1 2
x
2
+ a
1 3
x
3
+ : : : + a
1 n
x
n
= b
1
a
2 2
x
2
+ a
2 3
x
3
+ : : : + a
2 n
x
n
= b
2
a
3 2
x
2
+ a
3 3
x
3
+ : : : + a
3 n
x
n
= b
3
:
:
:
a
n 2
x
2
+ a
n 3
x
3
+ : : : + a
n n
x
n
= b
n
w h e r e o f c o u r s e , t h e c o e c i e n t s i n r o w s 2 { n a r e l i n e a r c o m b i n a t i o n s o f t h e
o r i g i n a l c o e c i e n t s .
1 5
T h e e e c t o f 1 . 2 a n d 1 . 3 t o g e t h e r i s t o m u l t i p l y t h e w h o l e r o w 1 b y m
i 1
a n d a d d i t t o
e q u a t i o n i , i e . , e l e m e n t a r y r o w o p e r a t i o n 4 a b o v e , b u t w i t h t h e e e c t o f e l i m i n a t i n g a
i 1
.
-
7/28/2019 Analyse Nume
18/42
S e c o n d r e d u c t i o n s t e p : N o w , w e e l i m i n a t e a l l c o e c i e n t s o f x
2
i n r o w s 3 { n
b y
2 . 1 m o v e t o e a c h r o w i n t u r n s t a r t i n g f r o m r o w 3
2 . 2 a t r o w i a d d t h e c o n s t a n t m
i 2
= ; a
i 2
= a
2
m u l t i p l i e d b y t h e c o r r e s p o n d i n g
c o e c i e n t o f e q u a t i o n 2
2 . 3 d o t h e s a m e t o t h e r i g h t h a n d s i d e o f r o w i .
A f t e r a p p l i c a t i o n o f t h e a b o v e p r o c e d u r e , t h e s y s t e m o f e q u a t i o n s l o o k s l i k e
a
1 1
x
1
+ a
1 2
x
2
+ a
1 3
x
3
+ : : : + a
1 n
x
n
= b
1
a
2 2
x
2
+ a
2 3
x
3
+ : : : + a
2 n
x
n
= b
2
a
3 3
x
3
+ : : : + a
3 n
x
n
= b
3
:
:
:
a
n 3
x
3
+ : : : + a
n n
x
n
= b
n
w h e r e a g a i n , t h e c o e c i e n t s i n r o w s 3 { n a r e l i n e a r c o m b i n a t i o n s o f t h e c o e -
c i e n t s r e s u l t i n g a f t e r a p p l i c a t i o n o f t h e r s t r e d u c t i o n s t e p .
T h i s p r o c e d u r e i s n o w r e p e a t e d f o r t h i r d , f o u r t h , e t c . r e d u c t i o n s t e p s ,
u n t i l a f t e r n s t e p s , t h e r e s u l t i n g c o e c i e n t m a t r i x i s i n u p p e r - t r i a n g u l a r f o r m .
T h r o u g h o u t , o n l y e l e m e n t a r y r o w o p e r a t i o n s h a v e b e e n p e r f o r m e d , u n d e r w h i c h
t h e s o l u t i o n r e m a i n s i n v a r i a n t . T h e r u l e s i n v o l v e d i n t h e k ; t h r e d u c t i o n s t e p
c a n b e i l l u s t r a t e d b y t h e o w d i a g r a m i n F i g . 1
A n a l g o r i t h m f o r r e d u c t i o n t o u p p e r t r i a n g u l a r f o r m b y G a u s s i a n e l i m i n a t i o n
c o n s i s t s i n a s e r i e s o f s u c h r e d u c t i o n s t e p s f r o m k = 1 t o k = n ; 1 , a f t e r w h i c h
t h e c o n t i n u a l l y u p d a t e d c o e c i e n t s w i l l b e i n t h e r e q u i r e d f o r m . T h i s f o r m c a n
t h e n b e u s e d a s t h e i n p u t t o t h e b a c k s u b s t i t u t i o n a l g o r i t h m . A o w d i a g r a m f o r
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 a s o u t l i n e i n F i g . 2
5 . 3 . 2 F a i l u r e o f t h e r e d u c t i o n m e t h o d
E x a m i n a t i o n o f S t a g e 2 o f t h e a l g o r i t h m f o r p e r f o r m i n g t h e k - t h r e d u c t i o n s t e p
i n F i g . 1 r e q u i r e s t h a t a
k k
6= 0 . W h e n e v e r t h i s o c c u r s , t h e r e a r e t w o p o s s i b i l i t i e s : -
1 9 l > k a
l k
6= 0 , i e . t h e r e i s a r o w w h i c h h a s n o t y e t b e e n v i s i t e d t h a t h a s
a n o n - z e r o c o e c i e n t f o r x
k
2 8 l > k a
l k
= 0 , i e . a l l s u c c e e d i n g c o e c i e n t s o f x
k
a r e z e r o .
I f t h e r s t p o s s i b i l i t y i s t h e c a s e , t h e n o n e c a n s i m p l y i n t e r c h a n g e r o w k a n d r o w
l , s i n c e r o w i n t e r c h a n g e i s o n e o f t h e e l e m e n t a r y r o w o p e r a t i o n s u n d e r w h i c h t h e
s o l u t i o n i s i n v a r i a n t . I f t h i s c a n b e d o n e w h e n e v e r t h e r e i s a a
k k
= 0 i n t h e k - t h
r e d u c t i o n s t e p , t h e n t h e s y s t e m i s s i n g u l a r . I f t h e s e c o n d p o s s i b i l i t y i s t h e c a s e ,
t h e n t h e s y s t e m w i l l b e o v e r d e t e r m i n e d , a n d e i t h e r t h e r e a r e a n i n n i t e n u m b e r
o f p o s s i b l e s o l u t i o n s ( t h e s y s t e m i s d e p e n d e n t , s e e s e c t i o n 5 . 1 . 1 ) , o r t h e r e i s n o
s o l u t i o n ( t h e s y s t e m i s i n c o n s i s t e n t ) . I f t h i s i s t h e c a s e , t h e s y s t e m i s d e n i t e l y
n o n - s i n g u l a r .
-
7/28/2019 Analyse Nume
19/42
F l o w D i a g r a m f o r t h e k - t h R e d u c t i o n S t e p
d o i = k + 1 n
l o o p o v e r r o w s > k
?
m
i k
=
;a
i k
= a
k k
f o r m t h e m u l t i p l i e r
?
d o j = k n
l o o p o v e r c o l u m n s k i n r o w i
?
a
i j
= a
i j
+ m
i k
a
k j
u p d a t e t h e c o e c i e n t s
?
e n d d o
-
6
?
b
i
= b
i
+ m
i k
b
k
u p d a t e t h e r i g h t h a n d s i d e s
?
e n d d o
-
6
?
s t o p
F i g u r e 1 : T h e s e q u e n c e o f o p e r a t i o n s i n m a k i n g t h e k - t h r e d u c t i o n s t e p t o u p p e r -
t r i a n g u l a r f o r m . N o t i c e t h a t i n s t a g e 2 a b o v e , i t i s n e c e s s a r y t h a t a
k k
6= 0 . S e e
s e c t i o n 5 . 3 . 2
-
7/28/2019 Analyse Nume
20/42
R e d u c t i o n t o U p p e r T r i a n g u l a r F o r m
b y G a u s s i a n E l i m i n a t i o n
s t a r t p r o c e d u r e : s u p p l y i n i t i a l d a t a
I n p u t f n a
i j
b
i
g
?
d o k = 1 n ; 1
l o o p o v e r r o w s < n
?
k - t h r e d u c t i o n
p e r f o r m t h e k - t h r e d u c t i o n p r o c e d u r e
a s o u t l i n e i n F i g . 1
?
e n d d o
-
6
?
O u t p u t f n a
i j
b
i
g
?
o u t p u t t h e n e w c o e c i e n t s a n d r i g h t - h a n d
s i d e s t o t h e b a c k s u b s t i t u t i o n a l g o r i t h m t o
o b t a i n t h e n a l r e s u l t
F i g u r e 2 : F l o w d i a g r a m f o r r e d u c t i o n o f a s q u a r e n n m a t r i x t o u p p e r t r i a n g u l a r
f o r m u s 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 p r o c e d u r e o u t p u t s t h e t r a n s f o r m e d a
i j
a n d
b
i
, w h i c h c a n b e c o m e t h e i n p u t f o r t h e b a c k s u b s t i t u t i o n a l g o r i t h m .
-
7/28/2019 Analyse Nume
21/42
5 . 4 I t e r a t i v e m e t h o d s
T h e l a s t s e c t i o n d i s c u s s e d t h e G a u s s i a n e l i m i n a t i o n a l g o r i t h m , w h i c h i s u s e f u l f o r
m o d e r a t e l y s i z e d s y s t e m s o f l i n e a r e q u a t i o n s . T h i s i s w h a t w a s c a l l e d a d i r e c t
m e t h o d , w h i c h i n p r i n c i p l e y i e l d s a n e x a c t r e s u l t , n o t w i t h s t a n d i n g e r r o r s d u e t o
r o u n d o a n d c o m p u t e r a r i t h m e t i c . C e r t a i n p r o b l e m s h o w e v e r i n v o l v e t h e i n v e r -
s i o n o f v e r y l a r g e m a t r i c e s . S i n c e m a t r i x i n v e r s i o n i n v o l v e s n
3
o a t i n g p o i n t
o p e r a t i o n s , w h e r e n i s t h e d i m e n s i o n o f t h e m a t r i x , t h e i n v e r s i o n o f s y s t e m s o f
d i m e n s i o n 1 0
4
w o u l d r e q u i r e 1 0
1 2
o a t i n g p o i n t o p e r a t i o n s . S i n c e s u c h p r o b -
l e m s u s u a l l y a r i s e f r o m t h e s o l u t i o n o f d i e r e n t i a l e q u a t i o n s , t h e s o l u t i o n u s u a l l y
h a s t o b e m a r c h e d a c r o s s s o m e p a r a m e t e r s u b s p a c e
1 6
. I n s u c h c i r c u m s t a n c e ,
o n e t h e n a p p l i e s a p p r o x i m a t e m e t h o d s f o r n d i n g t h e s o l u t i o n . T h e s e i n v a r i a b l y
i n v o l v e s o m e i t e r a t i v e p r o c e d u r e .
5 . 4 . 1 J a c o b i ' s m e t h o d
A s w i t h a l l i t e r a t i v e p r o c e d u r e s , o n e s t a r t s w i t h a n a s s u m e d t r i a l s o l u t i o n x
( 0 )
.
T h e n , t h e s i m p l e s t a l g o r i t h m p r o c e e d s b y s o l v i n g f o r x
1
i n t e r m s o f b
1
a n d t h e
t r i a l s o l u t i o n x
( 0 )
i 6= 1
s o l v i n g f o r x
2
i n t e r m s o f b
2
a n d t h e t r i a l s o l u t i o n x
( 0 )
i 6= 2
e t c .
T h e o b t a i n e d s o l u t i o n t h e n b e c o m e s t h e r s t a p p r o x i m a t i o n 8 i x
i
= x
( 1 )
i
. T h e n
a f t e r t h e k - t h i t e r a t i o n t h e i - t h e q u a t i o n t a k e s t h e f o r m
1 7
x
( k )
i
=
1
a
i i
h
b
i
; a
i 1
x
( k ; 1 )
1
; a
i 2
x
( k ; 1 )
2
; : : :
; a
i i ; 1
x
( k ; 1 )
i ; 1
; a
i i + 1
x
( k ; 1 )
i + 1
; : : : ; a
i n
x
( k ; 1 )
n
i
( 1 9 )
I n a n a p p l i c a t i o n f o r w h i c h t h e a r e m a n y z e r o ' s ( i e . , t h e c o e c i e n t m a t r i x i s
s p a r s e ) w h i c h o c c u r i n r e g u l a r p a t t e r n s , t h i s c a n b e u t i l i s e d i n o r d e r t o a v o i d
m a k i n g s e v e r a l n e e d l e s s m u l t i p l i c a t i o n s a
i j
x
( k )
j
w h e r e a
i j
= 0 . S u c h a s t r a t e g y
t h e n r e d u c e s t h e n u m b e r o f o a t i n g p o i n t o p e r a t i o n s w h i c h h a v e t o b e p e r f o r m e d ,
a n d h e n c e a l s o t h e a c c u m u l a t e d e r r o r ( r e c a l l l e c t u r e 2 ) . T h e p r o c e d u r e o u t l i n e d
a b o v e i s k n o w n a s t h e J a c o b i a l g o r i t h m , a n d i s r e p r e s e n t e d i n o w d i a g r a m f o r m
i n F i g . 3
5 . 4 . 2 T h e G a u s s - S e i d e l m e t h o d
I n e v a l u a t i n g x
( k )
i
i n E q . 1 9 i t c a n b e n o t i c e d t h a t a l l x
( k )
j < i
h a v e p r e v i o u s l y b e e n
d e t e r m i n e d . A f a s t e r c o n v e r g e n c e c a n b e o b t a i n e d i f t h e s e v a l u e s a r e u s e d i n t h e
r i g h t h a n d s i d e o f E q . 1 9 i n s t e a d o f t h e o l d v a l u e s x
( k ; 1 )
j < i
. T h i s i s t h e b a s i s o f t h e
G a u s s - S e i d e l m e t h o d , a n d t h e e v a l u a t i o n s t a g e i s g i v e n b y t h e e q u a t i o n
x
( k )
i
=
1
a
i i
h
b
i
; a
i 1
x
( k )
1
; a
i 2
x
( k )
2
; : : :
; a
i i ; 1
x
( k )
i ; 1
; a
i i + 1
x
( k ; 1 )
i + 1
; : : : ; a
i n
x
( k ; 1 )
n
i
( 2 0 )
1 6
F o r i n s t a n c e , i n t h e s o l u t i o n o f t h e L a n d a u - L i f s h i t z e q u a t i o n ( s e e a s s i g n m e n t 2 ) f o r m a n y
d e g r e e o f f r e e d o m s y s t e m s , t h e s o l u t i o n h a s t o b e d e t e r m i n e d o v e r a g i v e n r a n g e o f t i m e a n d
e x t e r n a l c o n t r o l e l d . I f t h e t i m e a n d c o n t r o l e l d p a r a m e t e r s a r e d i s c r e t i s e d i n t o s a y N
t i m e s t e p s a n d M e l d s t e p s , t h e n t h e i n v e r s i o n h a s t o b e d o n e N M t i m e s . T h e r e f o r e , t h e
e n t i r e s i m u l a t i o n w o u l d t a k e n
3
N M o a t i n g p o i n t o p e r a t i o n s !
1 7
O b v i o u s l y , a
i i
m u s t b e n o n - z e r o . F o r a n o n - s i n g u l a r s y s t e m , o n e c a n a l w a y s a c h i e v t h i s
b y i n t e r c h a n g i n g r o w s , w h i c h i s a n e l e m e n t a r y r o w o p e r a t i o n u n d e r w h i c h t h e s o l u t i o n r e m a i n s
i n v a r i a n t .
-
7/28/2019 Analyse Nume
22/42
T h e J a c o b i A l g o r i t h m
s t a r t p r o c e d u r e : s u p p l y i n i t i a l d a t a
I n p u t
n
N
m a x
n a
i j
b
i
x
( 0 )
i
o
?
d o k = 1 N
m a x
m a i n i t e r a t i o n l o o p
?
g e n e r a t e x
( k )
i
a p p l y e q u a t i o n 1 9
?
t e s t f o r c o n v e r g e n c e
y e s
?
x
( k ; 1 )
x
( k )
t h e u p d a t e d s o l u t i o n b e c o m e s
t h e o l d s o l u t i o n
? n o
-
6
?
n o c o n v e r g e n c e
O u t p u t
n
x
( k )
i
o
t h e a l g o r i t h m h a s f a i l e d t o c o n v e r g e
E R R O R
t e r m i n a t e a n d o u t p u t t h e s o l u t i o n
F i g u r e 3 : F l o w d i a g r a m f o r t h e s o l u t i o n o f a s y s t e m o f l i n e a r e q u a t i o n s u s i n g
t h e J a c o b i a l g o r i t h m . N
m a x
i s t h e m a x i m u m n u m b e r o f i t e r a t i o n s a f t e r w h i c h
i t i s d e e m e d t h a t t h e s o l u t i o n h a s n o t c o n v e r g e d . A t t h e s t a g e w h e r e t h e x
( k )
i
a r e g e n e r a t e d f r o m t h e x
( k ; 1 )
i
, t h e o c c u r r e n c e o f z e r o ' s i n d e n i t e p a t t e r n s i n t h e
m a t r i x o f c o e c i e n t s s h o u l d b e u s e d t o a v o i d u n n e c e s s a r y m u l t i p l i c a t i o n s .
-
7/28/2019 Analyse Nume
23/42
A n a l g o r i t h m f o r t h e i m p l e m e n t a t i o n o f t h e G a u s s - S e i d e l m e t h o d w i l l b e v i r t u a l l y
i d e n t i c a l t o t h e J a c o b i m e t h o d , e x c e p t t h a t E q . 2 0 w i l l b e u s e d i n p l a c e o f E q . 1 9
-
7/28/2019 Analyse Nume
24/42
6 L e c t u r e 7 - S y s t e m s o f l i n e a r e q u a t i o n s ( 2 )
6 . 1 T h e A l g e b r a i c e i g e n v a l u e p r o b l e m
E i g e n v a l u e s a r e o f g r e a t i m p o r t a n c e i n m a n y p h y s i c a l p r o b l e m s a n d s o i t i s n e c -
e s s a r y t o h a v e a t h a n d r o b u s t w a y s o f s y s t e m m a t i c a l l y c o m p u t i n g e i g e n v a l u e s
a n d t h e i r a s s o c i a t e d e i g e n v e c t o r s . T h e a l g e b r a i c e i g e n v a l u e p r o b l e m i s a v a s t a n d
i m p o r t a n t s u b j e c t , a n d a s s u c h , m a n y m e t h o d s h a v e b e e n d e v e l o p e d t o o b t a i n
s o l u t i o n s u n d e r a v a r i e t y o f c o n d i t i o n s . T h e s e l e c t i o n o f m e t h o d d e p e n d s o n w h a t
t y p e o f m a t r i x i s i n v o l v e d , a n d w h a t i n f o r m a t i o n i s r e q u i r e d . H e r e , w e d e s c r i b e
p r o b a b l y t h e s i m p l e s t m e t h o d o f l o c a t i n g a g i v e n e i g e n v a l u e b y a n i t e r a t i v e p r o -
c e d u r e | t h e s o c a l l e d p o w e r m e t h o d . L a t e r , w e d e s c r i b e a l g o r i t h m w h i c h i s u s e d
t o c o m p u t e a l l e i g e n v a l u e s a n d e i g e n v e c t o r s o f a r e a l s y m m e t r i c m a t r i x | t h e
m e t h o d o f H o u s e h o l d e r t r i d i a g o n a l i s a t i o n a n d Q R f a c t o r i s a t i o n .
M a t h e m a t i c a l l y , t h e a l g e b r a i c e i g e n v a l u e p r o b l e m a r i s e s w h e n e v e r t h e r i g h t
h a n d s i d e o f t h e s y s t e m o f l i n e a r e q u a t i o n s , E q . 1 4 i s a m u l t i p l e o f t h e v e c t o r o f
u n k n o w n s , t h a t i s w h e n e v e r b = x , s o t h a t
( A ; I ) x = 0 ( 2 1 )
w h e r e I i s t h e u n i t n n m a t r i x a n d i s a s c a l a r q u a n t i t y . B u t f r o m t h e d i s c u s s i o n
o f n o n - s i n g u l a r m a t r i c e s i n s e c t i o n 5 . 1 . 1 , i f t h e m a t r i x A ; I i s n o n - s i n g u l a r , o n l y
t h e t r i v i a l s o l u t i o n x = 0 e x i s t s . T h e r e f o r e , f o r n o n - t r i v i a l s o l u t i o n s t o E q . 2 1 t o
e x i s t , t h e m a t r i x A ; I m u s t b e s i n g u l a r , i e . n o n - i n v e r t i b l e .
6 . 2 T h e p o w e r m e t h o d
O n e s t a r t s w i t h a n t r i a l e i g e n v e c t o r x
0
a n d c o m p u t e t h e s e q u e n c e
x
1
= A x
0
x
2
= A x
1
: : : x
k
= A x
k ; 1
N o w d e n e
m
0
= x
T
k ; 1
x
k ; 1
m
1
= x
T
k ; 1
x
k
m
2
= x
T
k
x
k
T h e n , t h e R a y l e i g h q u o t i e n t
q =
m
1
m
0
( 2 2 )
i s a n a p p r o x i m a t i o n f o r a n e i g e n v a l u e o f A . M o r e o v e r , i f w e d e n e q =
; s o
t h a t i s t h e e r r o r o f q , t h e n
j j =
s
m
2
m
0
; q
2
( 2 3 )
T o p r o v e t h i s , c o n s i d e r t h e i n n e r p r o d u c t
( x
k
; q x
k ; 1
)
T
( x
k
; q x
k ; 1
) = m
2
; 2 q m
1
+ q
2
m
0
= m
2
; 2 q ( q m
0
) + q
2
m
0
= m
2
; q
2
m
0
= j j
2
m
0
( 2 4 )
-
7/28/2019 Analyse Nume
25/42
w h e r e E q . 2 2 h a s b e e n u s e d i n t h e s e c o n d s t e p a n d E q . 2 3 h a s b e e n u s e d i n t h e
n a l s t e p .
N o w , t h e n o r m a l i s e d e i g e n v e c t o r s z
i
i = 1 n o f t h e r e a l s y m m e t r i c m a -
t r i x A f o r m a c o m p l e t e o r t h o n o r m a l s e t w h i c h s p a n t h e v e c t o r s p a c e V
n
=
f y = ( y
1
y
2
: : : y
n
) g s o t h a t w e c a n w r i t e
x
k ; 1
=
n
X
i = 1
c
i
z
i
m
0
=
n
X
i = 1
c
2
i
x
k
= A x
k ; 1
=
n
X
i = 1
c
i
A z
i
=
n
X
i = 1
c
i
i
z
i
( 2 5 )
f r o m w h i c h w e o b t a i n
x
k
; q x
k ; 1
=
n
X
i = 1
c
i
(
i
; q ) z
i
U s i n g t h i s r e s u l t i n E q . 2 4
j
j
2
m
0
=
n
X
i = 1
c
2
i
(
i
;q )
2
N o w , i f q i s c l o s e s t t o a p a r t i c u l a r
c
, t h e n r e p l a c i n g e a c h
i
b y
c
j j
2
m
0
(
c
; q )
2
n
X
i = 1
c
2
i
= (
c
; q )
2
m
0
w h e r e t h e s e c o n d o f E q . 2 5 h a s b e e n u s e d . D i v i d i n g t h r o u g h o u t b y m
0
w e a r r i v e
a t E q . 2 3 .
6 . 3 S i m i l a r i t y a n d t h e Q R m e t h o d
W e n o w t u r n t o t h e p r o b l e m o f n d i n g a l l t h e e i g e n v a l u e s a n d a s s o c i a t e d e i g e n -
v e c t o r s f o r a g i v e n r e a l s y m m e t r i c m a t r i x , t h a t i s a m a t r i x w h i c h h a s A = A
T
.
T w o m a t r i c e s
A a n d A a r e s a i d t o b e s i m i l a r i f
A = T
; 1
A T ( 2 6 )
f o r s o m e n o n - s i n g u l a r n n m a t r i x T . E q . 2 6 i s c a l l e d a s i m i l a r i t y t r a n s f o r m a t i o n .
T h e s e a r e i m p o r t a n t b e c a u s e t h e y p r e s e r v e e i g e n v a l u e s | t h e e i g e n v a l u e s o f A
a n d
A a r e t h e s a m e . M o r e o v e r , i f x i s a n e i g e n v e c t o r o f A , t h e n
x = T
; 1
x i s a n
e i g e n v e c t o r o f
A b e l o n g i n g t o t h e s a m e e i g e n v a l u e s i n c e f r o m E q . 2 1 w e h a v e
A x = x = ) T
; 1
A x = T
; 1
x
= T
; 1
A I x
= T
; 1
A T T
; 1
x
=
A
T
; 1
x
w h e r e E q . 2 6 h a s b e e n u s e d i n t h e t h i r d s t e p .
6 . 3 . 1 H o u s e h o l d e r t r i d i a g o n a l i s a t i o n
S i n c e a p p l i c a t i o n o f a s i m i l a r i t y t r a n s f o r m a t i o n p r e s e r v e s e i g e n v a l u e s , a n d r e a d i l y
g i v e s t h e e i g e n v e c t o r s , o n e c a n e x p l o i t t h i s f a c t i n o r d e r t o r e d u c e a g i v e n r e a l
s y m m e t r i c m a t r i x t o a s i m p l e r f o r m . A v e r y w i d e l y u s e d m e t h o d w h i c h e m p l o y s
-
7/28/2019 Analyse Nume
26/42
t h i s s t r a t e g y i s H o u s e h o l d e r ' s m e t h o d . T h i s e m p l o y s n ; 2 s u c c e s s i v e s i m i l a r i t y
t r a n s f o r m a t i o n s i n o r d e r t o r e d u c e A t o t r i d i a g o n a l f o r m
1 8
. T h e m a t r i c e s u n d e r
w h i c h t h e s e s i m i l a r i t y t r a n f o r m a t i o n s a r e c a r r i e d o u t , d e n o t e d b y P
1
, P
2
, . . . , P
n ; 2
a r e o r t h o g o n a l a n d s y m m e t r i c , a n d h e n c e
1 9
P
; 1
i
= P
T
i
= P
i
. T h e s e s i m i l a r i t y
t r a n s f o r m a t i o n s g e n e r a t e a s e q u e n c e o f m a t r i c e s A
0
= A , A
1
, A
2
, . . . , A
n ; 3
g i v e n b y
A
1
= P
1
A
0
P
1
A
2
= P
2
A
1
P
2
:
:
:
A = P
n ; 2
A
n ; 3
P
n ; 2
( 2 7 )
T h e i d e a i s t h a t t h e s e t r a n f o r m a t i o n s c r e a t e t h e n e c e s s a r y z e r o ' s i n r o w 1 c o l u m n
1 i n t h r r s t s t e p , r o w 2 c o l u m n 2 i n t h e s e c o n d s t e p , e t c . T h e s e s t e p s a r e
i l l u s t r a t e d f o r a 5 5 m a t r i x i n F i g . 4 . T h e r e s u l t i s t h a t
A i s t r i d i a g o n a l .
F i r s t s t e p
A
1
= P
1
A
0
P
1
S e c o n d s t e p
A
2
= P
2
A
1
P
2
T h i r d s t e p
A
3
= P
3
A
2
P
3
F i g u r e 4 : I l l u s t r a t i o n o f H o u s e h o l d e r ' s m e t h o d f o r a 5 5 m a t r i x . T h e p o s i t i o n s
l e f t b l a n k a r e t h e z e r o ' s c r e a t e d b y t h e t r a n s f o r m a t i o n s .
1 8
A t r i d i a g o n a l m a t r i x h a s n o n - z e r o e l e m e n t s i n t h e d i a g o n a l , s u p e r d i a g o n a l a n d s u b d i a g o n a l
o n l y , t h a t i s t o s a y , o n l y e l e m e n t s a
i j
, a
i + 1 j
a n d a
i j + 1
c a n b e d i e r e n t f r o m z e r o .
1 9
R e c a l l t h a t a n o r t h o g o n a l m a t r i x i s a r e a l n n m a t r i x w h i c h h a s c o l u m n v e c t o r s e
i
t h a t
f o r m a n o r t h o n o r m a l s y s t e m s o t h a t e
i
e
j
e
T
i
e
j
=
i j
w h e r e
i j
i s t h e K r o n e c k e r d e l t a
e q u a l t o 1 w h e n i = j a n d 0 w h e n i 6= j . T h i s m e a n s t h a t , i f E i s a n o r t h o g o n a l m a t r i x w i t h
c o l u m n v e c t o r s e
i
, E
T
E , w h i c h h a s e l e m e n t s e
T
i
e
j
i s e q u a l t o t h e u n i t m a t r i x , w h i c h i m p l i e s
t h a t E
T
= E
; 1
.
-
7/28/2019 Analyse Nume
27/42
T h e q u e s t i o n n o w i s , h o w t o d e t e r m i n e t h e P
k
? F i r s t , w r i t e
2 0
P
k
= I ; 2 v
k
v
T
k
( 2 8 )
w h e r e v
k
i s a u n i t v e c t o r w i t h i t s r s t k c o m p o n e n t s e q u a l t o 0 , i e .
2 1
v
1
=
0
B
B
B
B
B
B
B
B
B
B
B
@
0
:
:
:
1
C
C
C
C
C
C
C
C
C
C
C
A
v
2
=
0
B
B
B
B
B
B
B
B
B
B
B
@
0
0
:
:
:
1
C
C
C
C
C
C
C
C
C
C
C
A
: : : v
n ; 2
=
0
B
B
B
B
B
B
B
B
B
B
B
@
0
0
0
:
:
1
C
C
C
C
C
C
C
C
C
C
C
A
T h e s e q u e n c e o f c a l c u l a t i o n s t h a t g i v e r i s e t o t h e v
k
a r e d e p i c t e d i n F i g . 5
6 . 3 . 2 Q R F a c t o r i s a t i o n
H a v i n g t r a n s f o r m e d t h e o r i g i n a l m a t r i x A i n t o t r i d i a g o n a l f o r m u s i n g s u c c e s s i v e
H o u s e h o l d e r t r a n s f o r m a t i o n s u n d e r w h i c h t h e e i g e n v a l u e s a r e i n v a r i a n t , w e n o w
h a v e t o s o l v e t h e e i g e n v a l u e p r o b l e m f o r t h e t r a n s f o r m e d m a t r i x B
0
= A
n ; 2
. T h i s
i s a c c o m p l i s h e d b y t h e s o c a l l e d Q R m e t h o d a s f o l l o w s .
1 F a c t o r
B
0
= Q
0
R
0
w h e r e Q
0
i s o r t h o g o n a l a n d R
0
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 . T h e n c o m p u t e
B
1
= R
0
Q
0
2 F a c t o r
B
1
= Q
1
R
1
t h e n c o m p u t e
B
1
= R
0
Q
0
2 0
P
k
i n t h i s f o r m i s a u t o m m a t i c a l l y s y m m e t r i c
P
T
k
=
;
I ; 2 v
k
v
T
k
T
= I
T
; 2
;
v
k
v
T
k
T
= I ; 2 v
k
v
T
k
a n d o r t h o g o n a l , s i n c e
P
k
P
T
k
=
;
I ; 2 v
k
v
T
k
2
= I ; 4 v
k
v
T
k
+ 4 v
k
v
T
k
v
k
v
T
k
= I ; 4 v
k
v
T
k
+ 4 v
k
v
T
k
= I
w h e r e t h e f a c t t h a t v
T
k
v
k
= 1 h a s b e e n u s e d i n t h e p e n n u l t i m a t e s t e p .
2 1
T h e a s t e r i s k s d e n o t e c o m p o n e n t s o t h e r t h a n z e r o ' s
-
7/28/2019 Analyse Nume
28/42
v
1 1
= 0
v
2 1
=
r
1
2
j a
2 1
j
S
1
v
j 1
=
a
j 1
s g n ( a
2 1
)
2 v
2 1
S
1
3 j n
w h e r e
S
1
=
q
a
2
2 1
+ a
2
3 1
+ : : : + a
2
n 1
v
1 2
= v
2 2
= 0
v
3 2
=
s
1
2
j a
( 1 )
3 2
j
S
2
v
j 2
=
a
( 1 )
j 2
s g n ( a
( 1 )
3 2
)
2 v
2 1
S
2
4 j n
w h e r e
S
2
=
r
a
( 1 )
2 1
2
+
a
( 1 )
3 1
2
+ : : : +
a
( 1 )
n 1
2
F i r s t s t e p
S e c o n d s t e p
F i g u r e 5 : D e n i t i o n o f t h e u n i t v e c t o r s v
k
s h o w i n g e x p l i c i t l y t h e r s t ( v
1
) a n d
s e c o n d ( v
2
) s t e p s . T h e c o m p o n e n t s v
i j
r e f e r t o t h e i - t h c o m p o n e n t o f u n i t v e c t o r
v
j
. a
( k )
i j
r e f e r s t o e l e m e n t s o f A
k
, a n d a
i j
a r e t h e e l e m e n t s o f t h e o r i g i n a l m a t r i x A .
I n t h e k - t h s t e p , s g n ( a
( k ; 1 )
k + 1 k
) = + 1 w h e n a
( k ; 1 )
k + 1 k
0 a n d s g n ( a
( k ; 1 )
k + 1 k
) = ; 1 w h e n
a
( k ; 1 )
k + 1 k
-
7/28/2019 Analyse Nume
29/42
T h e f a c t o r i s a t i o n i t s e l f i s o b t a i n e d i n t h e f o l l o w i n g w a y . T h e t r i d i a g o n a l m a t r i x B
0
h a s n ; 1 g e n e r a l l y n o n - z e r o e l e m e n t s b
2 1
b
3 2
: : : b
n n ; 1
b e l o w t h e m a i n d i a g o n a l .
S u p p o s e t h a t B
0
i s m u l t i p l i e d o n t h e l e f t b y a m a t r i x C
2
s u c h t h a t t h e r e s u l t C
2
B
0
h a s b
2 1
= 0 . T h e n , t h e r e s u l t i s m u l t i p l i e d o n t h e l e f t b y a m a t r i x C
3
s u c h t h a t
C
3
C
2
B
0
h a s b
3 2
= 0 , e t c . A f t e r n ; 1 s u c h m u l t i p l i c a t i o n s o n e i s l e f t w i t h a n u p p e r
t r i a n g u l a r m a t r i x R
0
= C
n
C
n ; 1
: : : C
3
C
2
B
0
. T h e C
j
a r e o r t h o g o n a l p l a n e r o t a t i o n s ,
t h a t i s , t h e y c o n t a i n t h e 2 2 s u b m a t r i x
c o s
j
s i n
j
; s i n
j
c o s
j
!
i n r o w s j ; 1 , j a n d c o l u m n s j ; 1 , j , w i t h 1 ' s o n a l l o t h e r m a i n d i a g o n a l e l e m e n t s
a n d z e r o ' s e v e r y w h e r e e l s e . S i n c e t h e C
j
a r e o r t h o g n a l , s o i s t h e i r p r o d u c t , a n d
s o i s i t s i n v e r s e | t h i s i s Q
0
= C
n
C
n ; 1
: : : C
3
C
2
]
; 1
. T h e r e f o r e , a c c o r d i n g t o t h e
s c h e m e
2 4
B
1
= R
0
Q
0
= R
0
C
T
2
C
T
3
: : : C
T
n ; 1
C
T
n
N o w , i n t h e r s t o p e r a t i o n C
2
B
0
, o n e h a s
0
B
B
B
@
c o s
2
s i n
2
0 : : :
; s i n
2
c o s
2
0 : : :
: : : : : :
: : : : : :
1
C
C
C
A
0
B
B
B
@
b
1 1
b
1 2
: : :
b
2 1
b
2 2
: : :
: : : : :
: : : : :
1
C
C
C
A
a n d
2
i s d e t e r m i n e d b y t h e c o n d i t i o n
b
2 1