Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
Właściwości metod iteracyjnych
iteratio=powtarzanie (procesu numerycznego w celu ulepszenia
wcześniejszych wyników)=kolejne przybliżanie
metoda iteracji prostej:
x=F(x)
równanie iteracji xi +1 = F( xi )
dostateczny warunek zbieżności: F' ( x ) < 1
szybkość zbieżności tym większa im mniejszy F' ( x )
Def.:
Niech xi będzie ciągiem kolejnych przybliżeń zbieżnej metody iteracyjnej:
lim xi = a . Jeżeli istnieje liczba p e" 1taka, że
i "
xi +1 - a
lim = C `" 0, C < 1 gdy p = 1
p
i "
xi - a
to mówimy, że metoda jest rzędu p w punkcie a. Liczba C jest nazywana
stałą asymptotyczną błędu.
W6 - 1
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
1
K
Jeżeli z jedną iteracją związany jest koszt K to E = p nazywamy
wskaz
nikiem efektywności metody.
Tw.
Jeżeli równaniem iteracji jest xi +1 = Ś( xi ) i dla k=1,..,p-1 Ś( k )( a ) = 0,
to metoda jest rzędu p.
dow.
( xi - a )2 Åš'' ( a )
xi +1 = Åš( xi ) = Åš( a ) + ( xi - a )Åš' ( a ) + + L+
2!
( xi - a )p Åš( p )( a )
p+1
+ + O( ( xi - a )
p!
xi +1 - a Åš( p )( a )
lim =
i "
( xi - a )p p!
W6 - 2
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
Metody iteracyjne rozwiązywania równań nieliniowych
Szukamy rzeczywistego pierwiastka równania f ( x ) = 0. Jeżeli jest nim ¾
, a xi jest przybliżeniem ¾ ( xi leży w otoczeniu ¾ ), to
f (¾ ) = 0 =
(¾ - xi )2 (¾ - xi )3
( 3 )
= f ( xi ) + (¾ - xi ) f' ( xi ) + f'' ( xi ) + f ( xi ) +L
2! 3!
zaniedbujÄ…c wyrazy rzÄ™dy wiÄ™kszego niż ½ otrzymujemy równanie do
wyznaczenia kolejnego przybliżenia xi +1
Dla ½ = 1 (metoda Newtona-Raphsona stopnia I):
0 = f ( xi ) + ( xi +1 - xi ) f' ( xi )
f ( xi )
xi +1 = xi -
f' ( xi )
W6 - 3
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
Dla ½ = 2 (metoda Newtona-Raphsona stopnia II):
( xi +1 - xi )2
0 = f ( xi ) + ( xi +1 - xi ) f' ( xi ) + f'' ( xi )
2!
f' ( xi )Ä… f' ( xi )2 - 2 f' ( xi ) f'' ( xi )
xi+1 = xi -
f'' ( xi )
Zbieżność lokalna!
RzÄ…d zbieżnoÅ›ci metody N-R I dla jednokrotnego zera ( f' (¾ ) `" 0):
f ( x )
xi +1 = Åš( xi ), Åš( x ) = x -
f' ( x )
îÅ‚ f' ( x ) f ( x ) f'' ( x )Å‚Å‚
Åš' (¾ ) = - = 0, czyli p=2
ïÅ‚1 f' ( x ) + f' ( x )2 śł
ðÅ‚ ûÅ‚
x=¾
W6 - 4
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
Rząd zbieżności metody N-R I dla m-krotnego zera
( f ( x ) = ( x - ¾ )m g( x ), g(¾ ) `" 0):
f' ( x ) = m( x -¾ )m-1 g( x ) + ( x - ¾ )m -1 g' ( x ),
( x - ¾ )m g( x )
Åš( x ) = x - ,
m( x - ¾ )m-1 g( x ) + ( x -¾ )m-1 g' ( x )
1 1
Åš' (¾ ) = 1 - , czyli p=1 C = 1 -
m m
W6 - 5
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
Metoda siecznych
f ( xi ) f ( xi )( xi - xi -1 ) f ( xi )xi -1 - f ( xi -1 )xi
xi +1 = xi - H" xi - =
f' ( xi ) f ( xi ) - f ( xi -1 ) f ( xi ) - f ( xi -1 )
p=1.618..
Regula falsi
dane xi , ai , f ( xi ) f ( ai ) < 0
ai f ( xi ) - xi f ( ai )
obliczamy µi = ,
f ( xi ) - f ( ai )
xi+1 = µi
üÅ‚
wybieramy Ð! f ( xi ) f ( µi ) > 0
ai+1 = ai żł
þÅ‚
xi +1 = µi
üÅ‚
Ð! f ( xi ) f ( µi ) < 0
ai +1 = xi żł
þÅ‚
p=1
W6 - 6
Instytut Automatyki Politechniki A
ódzkiej - Metody Numeryczne wykład 6
Układy równań nieliniowych
fi ( x1 , x2 ,L, xn ) = 0, i = 1,...,n
f1( Å" )
îÅ‚ Å‚Å‚
ïÅ‚
f2( Å" )śł
T
ïÅ‚ śł
F( X ) = 0, X = [x1 , x2 ,L, xn] , F(Å" ) =
M
ïÅ‚ śł
ïÅ‚
fn (Å" )śł
ðÅ‚ ûÅ‚
Dla ½ = 1 (metoda Newtona-Raphsona stopnia I):
0 = F( Xi ) + F' ( Xi )( Xi +1 - Xi )
"f1(x1,Lxn) "f1(x1,Lxn) "f1(x1,Lxn)
îÅ‚ Å‚Å‚
L
ïÅ‚
"x1 "x2 "xn śł
ïÅ‚ śł
"f2(x1,Lxn)
2
ïÅ‚"f (x1,Lxn) "f2(x1,Lxn) śł
L
F'(X ) =
ïÅ‚
"x1 "x2 "xn śł
ïÅ‚ śł
M M M
ïÅ‚"f (x1,Lxn) "fn(x1,Lxn) M śł
"fn(x1,Lxn)
n
ïÅ‚ śł
L
ïÅ‚ "x1 "x2 "xn śł
ðÅ‚ ûÅ‚
W6 - 7