M e t o d y n u m e r y c z n e
I n s t y t u t S t e r o w a n i a i S y s t e m w I n f o r m a t y c z n y c h
W y d z i a B E l e k t r o t e c h n i k i , I n f o r m a t y k i i T e l e k o m u n i k a c j i
U n i w e r s y t e t Z i e l o n o g r s k i
E l e k t r o t e c h n i k a s t a c j o n a r n e - d z i e n n e p i e r w s z e g o s t o p n i a z t y t . i n |y n i e r a
I n f o r m a t y k a s t a c j o n a r n e - d z i e n n e d r u g i e g o s t o p n i a z t y t . m a g i s t r a i n |y n i e r a
P r z y b l i |o n e m e t o d y r o z w i z y w a n i a r w n a D n i e l i n i o w y c h
L a b o r a t o r i u m , p r o w a d z c y : m g r i n |. B Ba |e j C i c h y
R o k a k a d e m i c k i 2 0 1 0 / 2 0 1 1
1 W s t p
C z s t o i s t n i e j e p o t r z e b a r o z w i z a n i a r w n a n i a p o s t a c i f ( x ) = 0 . D l a n i e k t r y c h f u n k c j i
( n p . f ( x ) = x 2 - 4 x + 1 ) z n a n e s s p o s o b y a n a l i t y c z n e g o w y z n a c z e n i a p i e r w i a s t k w t e g o
r w n a n i a . p r z y p a d k u w i k s z o [c i f u n k c j i r o z w i z a n i e a n a l i t y c z n e j e s t t r u d n e , c z a s o c h Bo n n e
l u b n a w e t n i e m o |l i w e . W w i e l u p r z y p a d k a c h z a d o w a l a j c e o k a z u j e s i u |y c i e s z y b s z y c h
m e t o d p r z y b l i |o n y c h . P i e r w i a s t e k r w n a n i a o d n a l e z i o n y p r z y i c h p o m o c y o b a r c z o n y j e s t
j e d n a k p e w n y m ( z r e g u By m o |l i w y m d o o s z a c o w a n i a ) b Bd e m .
I s t n i e j e w i e l e m e t o d p r z y b l i |o n e g o r o z w i z y w a n i a r w n a D n i e l i n i o w y c h . D o n a j p o p u -
l a r n i e j s z y c h n a l e | m e t o d y i t e r a c y j n e :
" b i s e k c j i ,
" s i e c z n y c h ( o p a r t e o r e g u B f a l s i ) ,
" s t y c z n y c h ( N e w t o n a ) ,
" p u n k t u s t a Be g o
1 . 1 M e t o d a b i s e k c j i
N i e c h f u n k c j a f ( x ) b d z i e f u n k c j c i g B w p r z e d z i a l e [ a , b ] i f ( a ) f ( b ) < 0 . O z n a c z a
t o , |e w a r t o [ f u n k c j i f z m i e n i a z n a k w t y m p r z e d z i a l e . P o n a d t o r w n a n i e f ( x ) = 0 m a w
p r z e d z i a l e [ a , b ] c o n a j m n i e j j e d n o r o z w i z a n i e . I d e a m e t o d y p o l e g a n a p o Bo w i e n i u p r z e -
d z i a Bu p o s z u k i w a D, z a k a |d y m r a z e m b i o r c t c z [ p r z e d z i a Bu , n a k t r e j w a r t o [ f u n k c j i
z m i e n i a z n a k . P o Bo w i e n i e t a k i e j e s t k o n t y n u o w a n e t a k d Bu g o , a | n i e z o s t a n i e o s i g n i t a
o k r e [l o n a d o k Ba d n o [ o b l i c z e D ( o z n a c z a n a z w y k l e l u b e p s ) . P r o w a d z i t o d o n a s t p u j c e g o
a l g o r y t m u , z n a n e g o j a k o m e t o d a b i s e k c j i l u b m e t o d a p o Bo w i e n i a :
1
P r z y b l i |o n e m e t o d y r o z w i z y w a n i a r w n a D n i e l i n i o w y c h 2
1 ) c : = ( a + b ) / 2
2 ) j e [ l i b - c < = e p s , t o
p r z y j m i j , |e p i e r w i a s t k i e m r w n a n i a f ( x ) = 0 j e s t
w a r t o [ c , a w i c f ( c ) = 0 i z a k o Dc z p r o g r a m .
3 ) j e [ l i z n a k ( f ( b ) ) " z n a k ( f ( c ) ) < = 0 t o
a : = c
w p r z e c i w n y m r a z i e
b : = c
4 ) s k o c z d o p u n k t u 1 .
F u n k c j a z n a k ( x ) z w r a c a w a r t o [ 1 j e [l i x > 0 , - 1 j e [l i x < 0 o r a z 0 d l a x = 0 . S z c z e g l n
z a l e t m e t o d y b i s e k c j i j e s t f a k t , i | j e s t o n a z a w s z e z b i e |n a d o r o z w i z a n i a . G B w n w a d
t e j m e t o d y j e s t w o l n a z b i e |n o [ d o r o z w i z a n i a .
1 . 1 . 1 O s z a c o w a n i e b Bd u
N i e c h a n , b n , c n o z n a c z a j n - t o b l i c z o n w a r t o [ o d p o w i e d n i o a , b i c . P o n a d t o n i e c h
o z n a c z a p r a w d z i w w a r t o [ p i e r w i a s t k a r w n a n i a f ( x ) = 0 . B Bd p o p e Bn i o n y w n - t y m
k r o k u w m e t o d z i e b i s e k c j i | - c n | j e s t o k r e [l o n y w z o r e m :
1
| - c n | d" ( b - a ) ( 1 )
2 n
1 . 2 M e t o d a N e w t o n a
M e t o d a N e w t o n a , z w a n a t e | m e t o d s t y c z n y c h , n a l e |y d o m e t o d i t e r a c y j n y c h . W
m e t o d z i e t e j k o r z y s t a s i z z a Bo |e n i a , |e f u n k c j a f p o s i a d a c i g B c o n a j m n i e j p i e r w s z
p o c h o d n ( o z n a c z o n f ) . P o n a d t o z a k Ba d a s i , |e z n a n e j e s t p i e r w s z e p r z y b l i |e n i e x 0
p i e r w i a s t k a r w n a n i a f ( x ) = 0 . W m e t o d z i e t e j i t e r a c y j n i e w y z n a c z a s i w a r t o [ w y r a |e -
n i a :
f ( x 0 )
x 1 = x 0 - ( 2 )
f ( x 0 )
w p i e r w s z y m k r o k u o r a z
f ( x n )
x n + 1 = x n - ( 3 )
f ( x n )
d l a n > 1 . P r o g r a m k o Dc z y s i , g d y b Bd m e t o d y j e s t z a d o w a l a j c o m a By : x n - x n - 1 d"
l u b w y k o n a n o z a d a n i l o [ i t e r a c j i n m a x . U w a g a : b Bd n y d o b r w a r t o [c i p o c z t k o w e j x 0
m o |e s p o w o d o w a b r a k z b i e |n o [c i m e t o d y .
1 . 2 . 1 O s z a c o w a n i e b Bd u
N i e c h p i e r w s z a ( f ) i d r u g a ( f ) p o c h o d n a f u n k c j i f b d z i e c i g Ba o r a z w a r t o [ p i e r w -
s z e j p o c h o d n e j f ( ) = 0 , g d z i e j e s t p i e r w i a s t k i e m r w n a n i a f ( x ) = 0 , t z n . f ( ) = 0 .
M o |n a w y k a z a , |e b Bd m e t o d y N e w t o n a w y n o s i
- x n H" x n + 1 - x n ( 4 )
P r z y b l i |o n e m e t o d y r o z w i z y w a n i a r w n a D n i e l i n i o w y c h 3
1 . 3 M e t o d a s i e c z n y c h
Z a k Ba d a j c , |e z n a n e s d w a p o c z t k o w e o s z a c o w a n i a ( x 0 o r a z x 1 ) w a r t o [c i p i e r w i a s t -
k a r w n a n i a f ( x ) = 0 . P r z y t a k i c h z a Bo |e n i a c h m o |l i w e j e s t u |y c i e m e t o d y s i e c z n y c h :
x n - x n - 1
x n + 1 = x n - f ( x n ) ( 5 )
f ( x n ) - f ( x n - 1 )
d l a n = 1 , 2 , 3 , n m a x . P r o g r a m k o Dc z y s i , g d y b Bd m e t o d y j e s t z a d o w a l a j c o m a By :
x n - x n - 1 d" l u b w y k o n a n o z a d a n i l o [ i t e r a c j i n m a x . M e t o d a s i e c z n y c h m o |e b y
u w a |a n a z a p r z y b l i |e n i e m e t o d y N e w t o n a b a z u j c e n a f a k c i e , i |
f ( x n ) - f ( x n - 1 )
f ( x n ) H"
x n - x n - 1
1 . 3 . 1 O s z a c o w a n i e b Bd u
O s z a c o w a n i e b Bd u w m e t o d z i e s i e c z n y c h o d b y w a s i p o d o b n i e d o m e t o d y N e w t o n a .
B Bd m e t o d y w y n o s i w p r z y b l i |e n i u
- x n - 1 H" x n - x n - 1 ( 6 )
1 . 4 P o r w n a n i e m e t o d y s i e c z n y c h i N e w t o n a
N a l e |y p o d k r e [l i , i | m e t o d a s i e c z n y c h w o g l n y m p r z y p a d k u w y m a g a b d z i e w i k s z e j
l i c z b y i t e r a c j i o d m e t o d y N e w t o n a . W s p Bc z y n n i k z b i e |n o [c i ( i n f o r m u j c y , j a k b Bd w
k r o k u n + 1 z a l e |y o d b Bd u w k r o k u n ) d l a m e t o d y s i e c z n y c h w y n o s i o k . 1 . 6 2 :
| - x n + 1 | H" c | - x n + 1 | 1 . 6 2
z a [ w m e t o d z i e N e w t o n a d o k Ba d n i e 2 :
- f ( c n )
- x n + 1 = ( - x n + 1 ) 2
2 f ( x n )
N i e n a l e |y j e d n a k z a p o m i n a , |e m e t o d a N e w t o n a w y m a g a w y l i c z e n i a z a r w n o w a r t o [c i
f u n k c j i , j a k i w a r t o [c i p o c h o d n e j t e j f u n k c j i . Z t e g o p o w o d u , p o m i m o m n i e j s z e j l i c z b y
i t e r a c j i , w p o r w n a n i u z m e t o d s i e c z n y c h , m o |e o n a w p r a k t y c e d z i a Ba w o l n i e j . Z a l e |y
t o o d t r u d n o [c i w w y z n a c z e n i u p o c h o d n e j f u n k c j i w p u n k c i e x n .
1 . 5 M e t o d y p u n k t u s t a Be g o
T e o r i a p u n k t u s t a Be g o s t a n o w i u o g l n i e n i e i t e r a c y j n y c h m e t o d w y m a g a j c y c h p o d a n i a
j e d n e g o p u n k t u s t a r t o w e g o . T e o r i a t a m o |e w i c z o s t a u |y t a d o a n a l i z y m e t o d y N e w t o n a .
W s z y s t k i e m e t o d y i t e r a c y j n e w y m a g a j c e p o d a n i a j e d n e g o p u n k t u s t a r t o w e g o m o |n a
z a p i s a j a k o :
x n + 1 = g ( x n ) ( 7 )
J e [l i
l i m x n + 1 = l i m g ( x n ) ( 8 )
n ! " n ! "
t o
= g ( ) ( 9 )
P r z y b l i |o n e m e t o d y r o z w i z y w a n i a r w n a D n i e l i n i o w y c h 4
S t d j e s t r o z w i z a n i e m r w n a n i a x = g ( x ) . W a r t o [ n a z y w a n a j e s t p u n k t e m s t a By m
f u n k c j i g .
M o |n a d o w i e [, |e m e t o d a i t e r a c y j n a o p a r t a n a w z o r z e ( 7 ) j e s t z b i e |n a , g d y
| g ( ) | < 1
J e [l i | g ( ) | = 1 , w t e d y z b i e |n o [ m e t o d y n a l e |y b a d a i n n y m i m e t o d a m i . G d y n a t o m i a s t
| g ( ) | > 1 , t o m e t o d a j e s t r o z b i e |n a .
2 Z e s t a w z a d a D I
P o n i |s z e z a d a n i e s p r z e z n a c z o n e d o w y k o n a n i a b e z u d z i a By m e t o d i m p l e m e n t o w a n y c h
w k o m p u t e r z e . M o |n a j e d n a k w y k o r z y s t a p r o g r a m M a t l a b w r o l i k a l k u l a t o r a .
1 . W y z n a c z y w z r n a m i n i m a l n l i c z b i t e r a c j i n w m e t o d z i e b i s e k c j i , k t r a z a p e w n i
b Bd o s z a c o w a n i a p i e r w i a s t k a r w n a n i a f ( x ) = 0 n i e w i k s z y , n i | z a Bo |o n a w a r t o [
. W s k a z w k a : s k o r z y s t a z w z o r u ( 1 ) .
"
2 . Z a p o m o c m e t o d y N e w t o n a w y z n a c z y p r z y b l i |o n w a r t o [: 2 , c z y l i p i e r w i a s t k a
r w n a n i a x 2 = 2 .
3 . W i a d o m o , |e r w n a n i e x 3 - x + 1 = 0 p o s i a d a t y l k o j e d e n p i e r w i a s t e k r z e c z y w i s t y
( w y j a [n i , d l a c z e g o t a k j e s t ? ) . Z n a l e z w p i e r w i a s t e k m e t o d b i s e k c j i ( p o Bo w i e n i a ) .
4 . M e t o d s i e c z n y c h z a s t o s o w a d o f u n k c j i f ( x ) = x 2 - 2 , g d z i e x 0 = 0 i x 1 = 1
o z n a c z a j k o l e j n e p r z y b l i |e n i a j e d n e g o z p i e r w i a s t k w r w n a n i a f ( x ) = 0 . W y l i c z y
w a r t o [ x 2 .
5 . S p r a w d z i , k t r e z p o n i |s z y c h w y r a |e D u |y t e w m e t o d z i e p u n k t u s t a Be g o g w a r a n t u j
z n a l e z i e n i e r o z w i z a n i a r w n a n i a : x 2 - 5 = 0 :
( a ) x n + 1 = 5 + x n - x 2
n
( b ) x n + 1 = 5 / x n
1
( c ) x n + 1 = 1 + x n - x 2
n
5
1 5
( d ) x n + 1 = x n +
2 x n
6 . K o r z y s t a j c z m e t o d y s i e c z n y c h o d s z u k a o b y d w a p i e r w i a s t k i p o n i |s z e g o r w n a n i a :
x 3 + x 2 - 3 x - 3 = 0
W s k a z w k a : p i e r w i a s t e k z n a j d u j e s i w p r z e d z i a l e ( 1 , 2 ) .
3 Z e s t a w z a d a D I I
W p o n i |s z y m z b i o r z e w y k o r z y s t u j e m y m e t o d y w b u d o w a n e w M a t l a b a , m e t o d y z p a -
k i e t u N C M 1 o r a z w Ba s n o r c z n i e n a p i s a n e f u n k c j e .
1 . N a p i s a f u n k c j e i m p l e m e n t u j c e n a s t p u j c e m e t o d y :
1
P a k i e t j e s t d o s t p n y p o d a d r e s e m : h t t p : / / w w w . m a t h w o r k s . c o m / m o l e r /
P r z y b l i |o n e m e t o d y r o z w i z y w a n i a r w n a D n i e l i n i o w y c h 5
( a ) b i s e k c j i
( b ) f a l s i
( c ) N e w t o n a
( d ) s i e c z n y c h
2 . R o z w i z a n a s t p u j c e r w n a n i e :
x 3 - 2 x - 5 = 0
z a p o m o c p a k i e t u S y m b o l i c T o o l s 2 , f u n k c j i r o o t s M a t l a b a a o r a z f u n k c j i f z e r o t x
z p a k i e t u N C M .
3 . S t o s u j c f u n k c j f z e r o g u i z p a k i e t u N C M o d s z u k a p i e r w i a s t k i p o n i |s z y c h r w n a D:
( a ) x 3 - 2 x - 5 , [ 0 , 3 ]
( b ) s i n ( x ) , [ 1 , 4 ]
1
( c ) , [ 0 , 5 ]
x -
4 . Z n a l e z m e t o d p o Bo w i e n i a p i e r w i a s t e k n a s t p u j c e g o r w n a n i a :
x 3 + x 2 - 3 x - 3 = 0
P o s z u k i w a n i a p i e r w i a s t k a n a j l e p i e j r o z p o c z w p r z e d z i a l e 1 , 2 .
5 . R w n a n i e 2 x 4 + 2 4 x 3 + 6 1 x 2 - 1 6 x + 1 = 0 m a d w a p i e r w i a s t k i w o t o c z e n i u p u n k t u
0 . 1 . P o s Bu g u j c s i m e t o d a N e w t o n a z n a l e z j e .
6 . K o r z y s t a j c z m e t o d y N e w t o n a z n a l e z p r z y b l i |e n i a n a s t p u j c y c h w a r t o [c i :
"
3
( a ) 8
"
3
( b ) 2 0
P r z y j d o k Ba d n o [ = 1 0 - 4 . Z w r c i u w a g " s z y b k o [ z b i e |n o [c i w z a l e |n o [c i o d
n a
n
d o b r a n e g o p u n k t u s t a r t o w e g o . W s k a z w k a : c , c " R + j e s t r o z w i z a n i e m r w n a n i a
n i e l i n i o w e g o x n - c = 0 .
7 . K o r z y s t a j c z m e t o d y s i e c z n y c h , c i c i w o r a z r e g u By f a l s i , w y z n a c z y r o z w i z a n i a
n a s t p u j c y c h r w n a D:
( a ) c o s x = 0 . 5 - s i n ( x ) , x " ( 1 , 2 )
( b ) x = e - x , x " ( 0 , 2 )
Z a Bo |y d o k Ba d n o [ r o z w i z a D n a p o z i o m i e = 1 0 - 6 . P o r w n a s k u t e c z n o [ m e t o d .
8 . W y z n a c z y ( j e [l i t o m o |l i w e ) p i e r w i a s t k i p o n i |s z y c h r w n a D z a p o m o c d o w o l n e j z
p o z n a n y c h m e t o d :
( a ) s i n ( x 2 ) - x 2 = 0
( b ) x 2 = 0
W s k a z w k a : d o k Ba d n a w a r t o [ p i e r w i a s t k a o b u r w n a D w y n o s i = 0 .
2
W s k a z w k a : z a s t o s o w a f u n k c j e s o l v e o r a z v p a .
P r z y b l i |o n e m e t o d y r o z w i z y w a n i a r w n a D n i e l i n i o w y c h 6
L i t e r a t u r a
[ 1 ] B j r c k A k e i D a h l q u i s t G e r m u n d . M e t o d y n u m e r y c z n e . P W N , W a r s z a w a , 1 9 8 7 .
[ 2 ] J e r z y B r z z k a i L e c h D o r o b c z y Ds k i . P r o g r a m o w a n i e w M A T L A B . W a r s z a w a ,
W y d a n i e I , 1 9 9 8 .
[ 3 ] Z e n o n F o r t u n a , B o h d a n M a c u k o w i J a n u s z W s o w s k i . M e t o d y n u m e r y c z n e . W N T ,
W a r s z a w a , 1 9 9 5 .
[ 4 ] J e r z y K l a m k a i i n . M e t o d y n u m e r y c z n e . P o l i t e c h n i k a Zl s k a , G l i w i c e , 1 9 9 8 .
[ 5 ] D a v i d K i n c a i d i W a r d C h e n e y . A n a l i z a n u m e r y c z n a . W N T , W a r s z a w a , 2 0 0 6 .
[ 6 ] A n n a K a m i Ds k a i B e a t a P a Dc z y k . M a t l a b . w i c z e n i a z . . . , P r z y k Ba d y i z a d a n i a .
W a r s z a w a , W y d a n i e I , 2 0 0 2 .
[ 7 ] W a n a t K a z i m i e r z . A l g o r y t m y n u m e r y c z n e . H e l i o n , G l i w i c e , 1 9 9 4 .
[ 8 ] B o g u m i Ba M r o z e k i Z b i g n i e w M r o z e k . M A T L A B i S i m u l i n k . P o r a d n i k u |y t k o w n i k a .
W y d a n i e I I , 2 0 0 4 .
[ 9 ] J u r i j P o v s t e n k o . W p r o w a d z e n i e d o m e t o d n u m e r y c z n y c h . A k a d e m i c k a O f i c y n a
W y d a w n i c z a E X I T , W a r s z a w a , W y d a n i e d r u g i e p o p r a w i o n e i u z u p e Bn i o n e , 2 0 0 5 .
[ 1 0 ] R u d r a P r a t a p . M A T L A B 7 d l a n a u k o w c w i i n |y n i e r w . P W N , 2 0 0 7 .
[ 1 1 ] W i e s Ba w a R e g e l . W y k r e s y i o b i e k t y g r a f i c z n e w M A T L A B . W a r s z a w a , W y d a n i e I ,
2 0 0 3 .
[ 1 2 ] M a r c i n S t a c h u r s k i . M e t o d y n u m e r y c z n e w p r o g r a m i e M a t l a b . W a r s z a w a , W y d a n i e I ,
2 0 0 3 .